這種基於 16x16 s-table 的非對稱（公鑰）密碼系統安全且有用嗎？
可能這絕對是題外話，但這裡是。密碼系統描述如下。歡迎任何有關如何處理它的提示或發現的缺陷。
這個描述也在這裡。
我們將使用替換 16x16 表，這是其中之一：
7 9 13 10 15 2 0 6 3 12 8 4 1 5 14 11 1 15 6 3 9 4 11 13 10 5 14 2 7 12 8 0 3 0 12 1 11 8 9 5 7 13 2 14 10 6 4 15 4 6 15 8 13 1 5 9 14 11 10 7 2 0 3 12 0 3 8 15 10 12 7 14 9 2 13 5 11 4 6 1 10 11 5 7 0 14 15 12 1 6 4 8 3 13 2 9 5 14 10 13 8 11 4 3 6 1 15 0 12 7 9 2 15 1 4 0 7 6 10 2 11 14 5 13 9 8 12 3 12 8 3 6 14 0 2 10 13 7 9 11 5 1 15 4 13 2 7 5 4 9 8 1 12 3 0 15 6 10 11 14 6 4 1 12 2 15 14 7 5 10 11 9 13 3 0 8 9 7 2 11 1 13 3 4 0 8 12 6 15 14 5 10 11 10 14 9 3 5 1 8 15 4 6 12 0 2 13 7 14 5 11 2 12 10 6 0 4 15 1 3 8 9 7 13 8 12 0 4 5 3 13 11 2 9 7 10 14 15 1 6 2 13 9 14 6 7 12 15 8 0 3 1 4 11 10 5定義一個函式 $ c=f(a,b) $ ， 在哪裡 $ c $ 是中的元素 $ a $ -第行和 $ b $ - 第列。
以下三個性質成立：
$ f(f(a,b),c)\neq f(a,f(b,c)) $ – 一般的非關聯性
$ f(a,b)\neq f(b,a) $ – 一般的不可交換性
$ f(f(a,b),f(c,d))=f(f(a,c),f(b,d)) $ – 受限交換性
接下來我們定義一個列表 $ N $ 範圍內的整數 $ [0,15] $ 以滿足所需的尺寸。為了 $ 256 $ 我們需要的位 $ N=64 $ . 這個列表可以解釋為 $ 64 $ 數字基礎—— $ 16 $ 數字。
接下來我們定義這種元素的混合過程， $ t $ 和 $ k $ , 整數範圍內的 N 元素數字列表 $ [0,15] $ .
但在此之前，我們在區間內定義了一個確定性的固定數字序列 $ [0,N-1] $ ，以偽隨機方式。frist_seq 獲取序列的第一個元素， next_seq 獲取下一個元素。
混合過程是：
function m(t,k) returns r //one-to-one mixing of k and t for i in 0..N-1 r[i] <- f(t[i],k[i]) end for i <- first_seq for M number of applications of f -- 4096 for example // accumulative mixing of r with itself j <- next_seq r[j]<-f(r[j],r[i]) i <- j end for //one-to-one mixing of k and r for i in 0..N-1 r[i] <- f(r[i],k[i]) end for return r函式 m 既不結合也不可交換，並且滿足受限交換性：
$ m(m(a,b),m(c,d))=m(m(a,c),m(b,d)) $
提出的計算難題是：
在 $ c=m(t,k) $ , 知道 $ c $ 和 $ t $ ， 尋找 $ k $ .
關於差分和線性密碼分析。如果我們將每一行和每一列作為一個 4 位長度的替換錶，i 結果表明，線性方程成立的機率最多為 14/16，並且對於微分特徵或多或少是相同的。當我們在 s 表上進行 4096 次迭代時，儘管 14/16 的機率很高， $ log_2((14/16)^{4096}) $ 遠遠小於 $ 2^{-256} $ . 所以這裡沒有明顯的攻擊可行。
現在讓我們使用混合函式定義秘密協議和數字簽名 $ m $ . 為了更清楚，我們將使用以下符號：
$ m(a,b) $ 寫成 $ (a b) $
$ m(m(a,b),m(c,d)) $ 寫成 $ (a b)(c d) $
$ m(m(a,b),c\dots) $ 寫成 $ (a b c\dots) $
對於秘密協議，程序如下：
愛麗絲和鮑勃都同意一些常數 $ C $ . Alice 選擇一個隨機密鑰 $ K $ , Bob 做同樣的選擇隨機密鑰 $ Q $ . 愛麗絲發送給鮑勃 $ (C K) $ , Bob 發送給 Alice $ (C Q) $ . Alice 使用 bob 發送的值進行計算 $ (C Q)(K C) $ , Bob 做同樣的事情併計算 $ (C K)(Q C) $ .
受限交換性 $ (C Q)(K C)=(C K)(Q C) $
對於簽名，程序如下：
簽名者 Alice 選擇一個公共值 $ C $ 和兩個隨機密鑰 $ K $ , $ Q $ . 它的憑據是 $ C $ , $ (C K) $ 和 $ (K Q) $ . 唱出價值， $ H $ , Alice 計算 $ S=(H Q) $ .
Bob 需要驗證 Alice 是否已經簽名 $ H $ . 計算 $ (C K)(H Q) $ 和 $ (C H)(K Q) $ . 由於有限的交換性，兩個值必須相等，如果 $ (H Q) $ 是來自 Alice 的有效簽名。
在本文件中，還提供了算法正確性的證明。
您的混合函式是可以使用矩陣表示的某些組的同構，除非維度太高，否則通常不難找到矩陣的逆矩陣（即使是行列式值為 0 的逆矩陣）。在這之後我的頭髮花了幾個月的時間才重新長出來。
例如，第 0 行的排列表示 $ p(x) = f(0,x) $ 可以表示為以下矩陣：
$$ \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} $$
這只是設置 $ f(0,i) $ 第’列 $ i $ ‘第 1 行為 1，每隔一個單元格為 0。
如圖所示，這是一個相當大的矩陣。或許可以簡化，但簡化到什麼程度取決於功能 $ f $ . 什麼時候 $ f $ 用於混合功能 $ m $ ，那麼擴展矩陣可能與對 AES 的 XSL 攻擊一樣不切實際。
已知的唯一與矩陣相關的問題是“晶格縮減”，它被用於後量子方案，如 Kyber、NTRU、Sabre、Dilithium、Falcon 等。如果你設法建構一個需要在不切實際的高矩陣維度上進行密碼分析的密碼有意義且高效的交換函式，那麼您絕對應該將其發佈在IACR ePrint上，並進行同行評審。
首先，我嘗試創建一個類似但二次方的sbox $ \mathbb{Z}_{17} $ ，並發現所有非平凡的候選者都是線性的。
雖然我還不能證明所有滿足“限制交換”要求的函式都是同構線性的，但我認為它可能對您的方案的安全性有一些嚴重的影響。
沒有可證明的方法來建構非線性 16x16 sbox 是目前破壞安全性信心的最大事情。
其次，我已經檢查了問題提出的 sbox，但在其中還找不到顯著有意義的線性關係。
C程序1：二次sbox搜尋程序
編譯以下 C 程序，然後使用 1 個參數呼叫它，指定（十進制）要創建的執行緒數；與
libc和連結libpthread是必需的。#include <stdio.h> #include <stdlib.h> #include <pthread.h> #define mod 17 #define ANY 0 #define ALL 1 void long2vec(long s, int *v, int c) { for(int i=0; i<c; i++) { v[i] = s % mod; s /= mod; } } int f(int a, int b, int c[]) { a %= mod; b %= mod; return (c[0] + c[1]*a + c[2]*b + c[3]*a*a + c[4]*a*b + c[5]*b*b) % mod; } int thrdcnt; int cmax = mod*mod*mod*mod*mod*mod; void *t(void *argp) { long ind = (long)argp; int c[6], x[4], u, v; for(; ind<cmax; ind+=thrdcnt) { long s; long comm = 0, assoc = 0, fail = 0; s = ind; long2vec(s, c, 6); if( (!c[1] && !c[3] && !c[4]) || (!c[2] && !c[4] && !c[5]) ) continue; // Exclude ones ignoring either operand. if( c[1] == c[2] && !c[3] && !c[5] ) continue; // Exclude ones that are commutative non-trivials. if( !c[3] && !c[4] && !c[5] ) continue; // Exclude all linear results. for(s=0; s<mod*mod*mod*mod; s++) { long2vec(s, x, 4); if( f(x[0], x[1], c) == f(x[1], x[0], c) && x[1] != x[0] ) comm++; if( f(f(x[0], x[1], c), x[2], c) == f(x[0], f(x[1], x[2], c), c) ) assoc++; u = f(f(x[0], x[1], c), f(x[2], x[3], c), c); v = f(f(x[0], x[2], c), f(x[1], x[3], c), c); if( u != v ) { fail++; break; } } if( fail == 0 ) dprintf( 1, "%d\t%d\t%d\t%d\t%d\t%d : %d, %d\n", c[0], c[1], c[2], c[3], c[4], c[5], comm, assoc); } return NULL; } int main(int argc, char *argv[]) { thrdcnt = argc >= 2 ? atoi(argv[1]) : 1; pthread_t *threads = malloc(sizeof(pthread_t) * thrdcnt); for(int i=0; i<thrdcnt; i++) { pthread_create(threads+i, NULL, t, (void *)(intptr_t)i); } for(int i=0; i<thrdcnt; i++) { pthread_join(threads[i], NULL); } return 0; }C程序2：線性關係搜尋程序
編譯並呼叫以下 C 程序；連結
libc是必需的。#include <stdint.h> #include <stdio.h> #include <stdlib.h> int latinsquare[256] = { +7, 9, 13, 10, 15, 2, 0, 6, 3, 12, 8, 4, 1, 5, 14, 11, +1, 15, 6, 3, 9, 4, 11, 13, 10, 5, 14, 2, 7, 12, 8, 0, +3, 0, 12, 1, 11, 8, 9, 5, 7, 13, 2, 14, 10, 6, 4, 15, +4, 6, 15, 8, 13, 1, 5, 9, 14, 11, 10, 7, 2, 0, 3, 12, +0, 3, 8, 15, 10, 12, 7, 14, 9, 2, 13, 5, 11, 4, 6, 1, 10, 11, 5, 7, 0, 14, 15, 12, 1, 6, 4, 8, 3, 13, 2, 9, +5, 14, 10, 13, 8, 11, 4, 3, 6, 1, 15, 0, 12, 7, 9, 2, 15, 1, 4, 0, 7, 6, 10, 2, 11, 14, 5, 13, 9, 8, 12, 3, 12, 8, 3, 6, 14, 0, 2, 10, 13, 7, 9, 11, 5, 1, 15, 4, 13, 2, 7, 5, 4, 9, 8, 1, 12, 3, 0, 15, 6, 10, 11, 14, +6, 4, 1, 12, 2, 15, 14, 7, 5, 10, 11, 9, 13, 3, 0, 8, +9, 7, 2, 11, 1, 13, 3, 4, 0, 8, 12, 6, 15, 14, 5, 10, 11, 10, 14, 9, 3, 5, 1, 8, 15, 4, 6, 12, 0, 2, 13, 7, 14, 5, 11, 2, 12, 10, 6, 0, 4, 15, 1, 3, 8, 9, 7, 13, +8, 12, 0, 4, 5, 3, 13, 11, 2, 9, 7, 10, 14, 15, 1, 6, +2, 13, 9, 14, 6, 7, 12, 15, 8, 0, 3, 1, 4, 11, 10, 5, }; #define P 0x11 int mulb(int a, int b) // multiplication in F_{2^4} { int x = 0; for(int i=0; i<4; i++) { x ^= b&1 ? a : 0; b >>= 1; a <<= 1; a ^= a&0x10 ? P : 0; } return x; } int mulf(int a, int b) // modular multiplication in Z_{16} { return (a * b) & 15; } int (*mul)(int a, int b) = mulf; // either mulb or mulf void mksbox(int x[16], uint64_t s) { int i; for(i=0; i<16; i++) x[i] = i; for(i=16; i>1; i--) { int p = s % i; int j = 16 - i; int t = x[p+j]; x[p+j] = x[j]; x[j] = t; s = (s - p) / i; } } float misses(int ab, int map[256]) { int a = ab >> 4, b = ab & 15; int x, y; int cand = 0; float min = -1; float num = 0, den = 0; if( !a || !b || a == b ) return min; for(x=0; x<256; x++) map[x] = 0; for(x=0; x<16; x++) { for(y=0; y<16; y++) { int u = mul(a,x) ^ mul(b,y); int v = latinsquare[x*16+y]; map[u*16+v]++; } } for(x=0; x<16; x++) { for(y=0; y<16; y++) { num += map[x*16+y]; if( map[x*16+y] ) den++; } } for(x=0; x<16; x++) { for(y=0; y<16; y++) { num += map[x*16+y]; if( map[x+16*y] ) den++; } } dprintf( 1, "\na: % 2d, b: % 2d\n", ab>>4, ab&15); for(int i=0; i<256; i++) dprintf(1, "% 3d%c", map[i], i%16==15?'\n':' '); min = num / den; return min; } int thrdcnt; void *t(void *argp) { long ind = (long)argp; int rec = -1; int map[256]; float max = 0; float subret; for(; ind<256; ind+=thrdcnt) { subret = misses((int)ind, map); if( subret > max ) { max = subret; rec = (int)ind; } } return NULL; } int main() { thrdcnt = 1; t(0); return 0; }