|
|
4#
大 中
小 發表於 2019-2-10 21:55 只看該作者
3.解決子集合加總問題－Lagarias和Odlyzko方法
雖然背包加密已經被 Shamir破解了，但後續有更多學者針對子集合加總問題( subset sum problem)進行研究。像 Lagarias和 Odlyzko在1985年提出基於 LLL演算法解決子集合加總問題。
子集合加總問題為找出 x_1,x_2,\ldots,x_n 的值讓 x_1a_1+x_2a_2+\ldots+x_na_n=s，其中 x_1,x_2,\ldots x_n \in \{\;0,1 \}\;。
Lagarias和 Odlyzko的解決辦法如下，利用 a_1,a_2,\ldots,a_n 和 s(註1)，建構 (n+1)\times (n+1) 的矩陣 B
B=\left[ \matrix{1&0&0&\ldots&0&-a_1 \cr
0&1&0&\ldots&0&-a_2 \cr
0&0&1&\ldots&0&-a_3 \cr
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots \cr
0&0&0&\ldots&1&-a_n \cr
0&0&0&\ldots&0&s} \right]
其中 B矩陣的每一列向量 b_1,b_2,\ldots,b_{n+1}都是線性獨立，形成 lattice的基底( basis)。
註1：
雖然前面wiki文章採用公鑰 \beta和密文 c，但一般介紹子集合加總問題卻採用 a_i和 s，這裡也用相同符號。
設 b_1,b_2,\ldots,b_{n+1}的線性組合為
x_1 b_1+x_2 b_2+\ldots+x_n b_n+1\cdot b_{n+1}=
\matrix{x_1 \left[1,0,0,\ldots,0,-a_1 \right]+ \cr
x_2 \left[0,1,0,\ldots,0,-a_2 \right]+ \cr
\ldots \cr
x_n \left[0,0,0,\ldots,1,-a_n \right]+ \cr
1 \left[0,0,0,\ldots \ldots,0,s \right]}=
\left[x_1,x_2,\ldots,x_n,-x_1a_1-x_2a_2-\ldots-x_na_n+s \right]
經 LLL演算法化簡後，第一行向量是整個 lattice中長度較短的向量，若最後一元為0，則 -x_1a_1-x_2a_2-\ldots-x_na_n+s=0，符合子集合加總問題的 x_1a_1+x_2a_2+\ldots+x_na_n=s，而答案就是前面 x_1,x_2,\ldots,x_n。
論文中還定義了 a=(a_1,a_2,\ldots,a_n)的密度 \displaystyle d(a)=\frac{n}{log_2 max_i(a_i)} ， d(a)用來測量明文和密文轉換時的資訊比率(information rate)
\displaystyle d(a)\approx \frac{明文的bits數}{密文平均的bits數}
利用本論文所定義的 lattice和使用 LLL演算法化簡可以破解低密度子集合加總問題，在密度 d(a)<0.645的子集合加總問題幾乎可以(almost all)在多項式時間內解出來。以維基百科為範例計算密度 \displaystyle d(a)=\frac{8}{log_2 592}=0.869 ，雖然沒符合 d(a)<0.645，但還是得到解答，代表高密度背包問題不一定解不出來只是成功率會下降。
參考資料
J. C. Lagarias and A. M. Odlyzko. 1985. Solving low-density subset sum problems. J. ACM 32, 1 (January 1985), 229-246.
https://web.stevens.edu/algebrai ... m/p229-lagarias.pdf
請下載LLL.zip，解壓縮後將LLL.mac放到C:\maxima-5.42.2\share\maxima\5.42.2\share目錄下
要先載入LLL.mac才能使用LLL指令
(%i1) load("LLL.mac");
(%o1) C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac
物品重量
(%i2) a:[295,592,301,14,28,353,120,236];
(%o2) \left[295,592,301,14,28,353,120,236 \right]
總和
(%i3) s:1129;
(%o4) 1129
形成lattice
(%i4)
B:matrix([1,0,0,0,0,0,0,0,-295],
[0,1,0,0,0,0,0,0,-592],
[0,0,1,0,0,0,0,0,-301],
[0,0,0,1,0,0,0,0,-14],
[0,0,0,0,1,0,0,0,-28],
[0,0,0,0,0,1,0,0,-353],
[0,0,0,0,0,0,1,0,-120],
[0,0,0,0,0,0,0,1,-236],
[0,0,0,0,0,0,0,0,1129]);
(%o4) \left[ \matrix{1&0&0&0&0&0&0&0&-295\cr
0&1&0&0&0&0&0&0&-592\cr
0&0&1&0&0&0&0&0&-301\cr
0&0&0&1&0&0&0&0&-14\cr
0&0&0&0&1&0&0&0&-28\cr
0&0&0&0&0&1&0&0&-353\cr
0&0&0&0&0&0&1&0&-120\cr
0&0&0&0&0&0&0&1&-236\cr
0&0&0&0&0&0&0&0&1129} \right]
經LLL化簡
(%i5) B: LLL(B);
0 errors, 0 warnings
(%o5) \left[ \matrix{0&1&1&0&0&0&0&1&0\cr
0&0&0&-2&1&0&0&0&0\cr
1&-1&0&0&-2&1&0&0&0\cr
-2&1&0&0&0&0&0&0&-2\cr
0&-1&1&0&2&0&0&1&-1\cr
0&-1&0&0&0&0&1&2&0\cr
0&1&0&0&0&-1&-2&0&1\cr
1&1&-1&0&0&-2&1&0&0\cr
0&2&-1&1&0&1&-1&0&-1}\right]
第1列向量最後一元為0，且x_i數字為0或1
(%i6) B[1];
(%o6) \left[0,1,1,0,0,0,0,1,0 \right]
去掉最後一元，得到解答
(%i7) x:rest(B[1],-1);
(%o7) \left[0,1,1,0,0,0,0,1 \right]
驗證a乘上x是否等於s
(%i8) is(a.x=s);
(%o8) true
－－－－－－－－－－－
另一個範例取自Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications的第7章範例7.6
https://books.google.com.tw/book ... e&q&f=false
物品重量 a=\left[a_1,a_2,\ldots,a_{15} \right]
a_1 = 929737936, a_2 = 970987227, a_3 = 787514290,
a_4 = 322163533, a_5 = 926801380, a_6 = 662236970,
a_7 = 572718201, a_8 = 499197496, a_9 = 270712809,
a_{10} = 142942483, a_{11} = 994479591, a_{12} = 143064843,
a_{13} = 724883274, a_{14} = 285884973, a_{15} = 71532418.
總和 s=4740166124
試找出 x_1,x_2,\ldots,x_n， x_i \in \{\;0,1 \}\;使得 \displaystyle \sum_{i=1}^n x_i\cdot a_i=s
要先載入LLL.mac才能使用LLL指令
(%i1) load(LLL);
(%o1) C:\maxima-5.42.2\share\maxima\5.42.2\share\LLL.mac
物品重量
(%i2)
a:[929737936,970987227,787514290,322163533,926801380,662236970,572718201,499197496,270712809,142942483,
994479591,143064843,724883274,285884973,71532418];
(%o2) [929737936,970987227,787514290,322163533,926801380,662236970,572718201,499197496,270712809,142942483,
994479591,143064843,724883274,285884973,71532418 ]
a個數n
(%i3) n:length(a);
(%o3) 15
總和s
(%i4) s:4740166124;
(%o4) 4740166124
將-a和s放在一起
(%i5) column:transpose(matrix(append(-a,[s])));
(%o5) \left[ \matrix{-929737936\cr -970987227\cr -787514290\cr -322163533\cr -926801380\cr -662236970\cr -572718201\cr -499197496\cr -270712809\cr -142942483\cr -994479591\cr -143064843\cr -724883274\cr -285884973\cr -71532418\cr 4740166124}\right]
產生左半邊矩陣
(%i6) B:genmatrix(lambda([i,j],if i=j then 1 else 0),n+1,n);
(%o6) \left[ \matrix{1&0&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&1&0&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&1&0&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&1&0&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&1&0&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&1&0\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0}\right]
將兩個矩陣合併
(%i7) B:addcol(B,column);
(%o7) \left[ \matrix{1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&-929737936\cr
0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&-970987227\cr
0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&-787514290\cr
0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&-322163533\cr
0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&-926801380\cr
0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&-662236970\cr
0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&-572718201\cr
0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&-499197496\cr
0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&-270712809\cr
0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&-142942483\cr
0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&-994479591\cr
0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&-143064843\cr
0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&-724883274\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&-285884973\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&-71532418\cr
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&4740166124}\right]
經LLL化簡
(%i8) B: LLL(B);
0 errors, 0 warnings
(%o8) \left[ \matrix{2&-1&-2&0&-1&0&1&1&2&0&0&0&0&0&0&0\cr
1&0&0&-1&0&-2&1&0&1&0&-1&1&1&0&0&1\cr
-1&0&-1&0&1&-1&0&2&-1&-1&0&1&1&0&0&-1\cr
0&1&2&1&-2&-1&0&1&0&1&-1&0&0&0&0&2\cr
-2&0&3&-1&-1&-1&0&0&1&1&1&0&0&0&0&2\cr
0&1&1&-1&-1&-2&0&2&2&0&0&0&-1&0&0&0\cr
0&0&1&-1&1&-1&0&-2&-1&0&2&0&-2&0&0&0\cr
1&0&-2&0&0&0&1&-1&0&2&0&0&0&1&0&0\cr
1&0&1&0&0&0&1&-1&0&-1&-1&0&-1&0&1&-1\cr
0&0&1&0&1&1&1&0&0&0&1&0&1&0&1&0\cr
1&0&0&-1&1&-1&1&2&1&1&-2&-1&-1&0&0&1\cr
0&-2&1&0&1&0&-1&1&-1&1&0&1&0&1&0&-1\cr
1&0&1&0&0&1&-2&0&1&0&-1&1&-1&0&1&1\cr
1&0&1&0&0&0&1&-1&0&1&-1&1&-1&-1&-1&-1\cr
-1&1&1&0&-1&0&0&-1&-1&2&0&0&1&-1&2&1\cr
-133&-99&-15&528&272&-278&-63&-129&302&78&0&-78&-17&-122&102&-40} \right]
第10列向量各個數字為0或1且最後一元為0
(%i9) B[10];
(%o9) \left[ 0,0,1,0,1,1,1,0,0,0,1,0,1,0,1,0 \right]
去掉最後一元得到解答
(%i10) x:rest(B[10],-1);
(%o10) \left[ 0,0,1,0,1,1,1,0,0,0,1,0,1,0,1 \right]
驗證a乘上x是否等於s
(%i11) is(a.x=s);
(%o11) true
|
