|
|
7#
大 中
小 發表於 2012-12-22 19:15 只看該作者
4.選擇n的注意事項－\( gcd(p-1,q-1) \)要很小
循環攻擊(Cycling Attack)就是將密文c多次用加密函數運算，直到\( \displaystyle c^{e^k}=\overbrace{((…(c^e)^e…)^e)^e}^{k次}=c \)，此時明文為\( \displaystyle m=c^{e^{(k-1)}} \)。
當\( gcd(p-1,q-1) \)很大時，循環攻擊就會奏效。而廣義循環攻擊，則是將密文c多次用加密函數運算，直到\( \displaystyle gcd(n,c^{e^k}-c)>1 \)。當\( p-1 \)與\( q-1 \)都只有小質數時，廣義循環攻擊特別有效。
(本段落節錄自《密碼學-加密演算法》p211)
因為書上沒有例子，所以我採用Simmons和Norris在1977年所發表的論文中所舉的例子來示範循環攻擊是如何運作的。
G. T. Simmons and J. N. Norris, Preliminary comments on the M.I.T. public-key cryptosystem, Cryptologia 1 (1977), 406–414.
http://www.tandfonline.com/doi/abs/10.1080/0161-117791833219
檔案需要大學的IP才能下載
公鑰n=215629和e=49
(%i1)
n:215629;
e:49;
(%o1) 215629
(%o2) 49
加密後的訊息c=1603
(%i3) c:1603;
(%o3) 1603
定義循環攻擊的副程式
我用c1,c2來儲存前一次計算的結果
c2=c1^e(mod n),若c2=c時,c1就是原訊息
c1=c2^e(mod n),若c1=c時,c2就是原訊息
(%i4)
CyclingAttack(c,e,n):=block
([c1,c2],
c1:c,
while true=true do
(c2:power_mod(c1,e,n),
print(c2),
if c2=c then
(return(c1)),
c1:power_mod(c2,e,n),
print(c1),
if c1=c then
(return(c2))
)
)$
經過十次計算後又得到原來的c
所以第九次的123456就是原來的訊息
(%i5) CyclingAttack(c,e,n);
180661
109265
131172
98178
56372
63846
146799
85978
123456
1603
(%o5) 123456
論文中還提供另一個例子，解密後的訊息是WARS ARE EVIL。
公鑰n=2773,e=17
(%i1)
n:2773;
e:17;
(%o1) 2773
(%o2) 17
密文c
(%i3) c:[2596,818,1,2423,508,1504,1444];
(%o3) [2596,818,1,2423,508,1504,1444]
定義循環攻擊的副程式
我用c1,c2來儲存前一次計算的結果
c2=c1^e(mod n),若c2=c時,c1就是原訊息
c1=c2^e(mod n),若c1=c時,c2就是原訊息
(%i4)
CyclingAttack(c,e,n):=block
([c1,c2],
c1:c,
while true=true do
(c2:power_mod(c1,e,n),
if c2=c then
(return(c1)),
c1:power_mod(c2,e,n),
if c1=c then
(return(c2))
)
)$
利用循環攻擊解密
(%i5) create_list(CyclingAttack(c,e,n),c,%o3);
(%o5) [2301,1819,1,1805,5,2209,1200]
每兩個數字視為一個字母
(%i6) create_list(append([floor(m/100),mod(m,100)]),m,%);
(%o6) [ [23,1],[18,19],[0,1],[18,5],[0,5],[22,9],[12,0] ]
將各組拆開
(%i7) flatten(%);
(%o7) [23,1,18,19,0,1,18,5,0,5,22,9,12,0]
還原出原英文訊息
空白=0,A=1,B=2,...,Z=26
(%i8) makelist(ascii(i+64),i,%);
(%o8) [ W,A,R,S,@,A,R,E,@,E,V,I,L,@]
轉換成字串
(%i9) simplode(%);
(%o9) WARS@ARE@EVIL@
將@符號用空白取代
(%i10) ssubst(" ","@",%);
(%o10) WARS ARE EVIL
循環攻擊時運算的次數會是\( φ(φ(n)) \)的因數，不同的\( e \)值所需的次數就會不同，假若\( φ(φ(n)) \)很大的話循環攻擊就會失敗。
公鑰n=2773,e=17
(%i1)
n:2773;
e:17;
(%o1) 2773
(%o2) 17
密文c
(%i3) c:[2596,818,1,2423,508,1504,1444];
(%o3) [2596,818,1,2423,508,1504,1444]
定義循環攻擊的副程式
這次我改求c=c^e^k(mod n)的k值
(%i4)
CyclingAttack(c,e,n):=block
([c1,steps],
c1:c,
steps:0,
while true=true do
(c1:power_mod(c1,e,n),
steps:steps+1,
if c1=c then
(return(steps))
)
)$
最多要經過44次方才能得到原訊息
m=c^e^43(mod n)
(%i5) create_list(CyclingAttack(c,e,n),c,%o3);
(%o5) [22,44,1,44,44,4,44]
其實1,4,22,44都是φ(φ(n))的正因數
(%i6)
totient(totient(n));
divisors(%);
(%o6) 1232
(%o7) { 1,2,4,7,8,11,14,16,22,28,44,56,77,88,112,154,176,308,616,1232 }
可以讓e^x(mod φ(n))=1最小的值x為44
對e=17來說,任何的密文最多經過43次次方就可以得到原訊息
(%i8) map(lambda([x],if power_mod(e,x,totient(n))=1 then x),%o7);
(%o8) { 44,88,176,308,616,1232,false }
我嘗試求出RSA129的φ(φ(n))，但φ(n)有很大的因數，該因數是否還可以分解仍不得而知，至少知道φ(φ(n))也會是很大的數，循環攻擊失敗。
\( p=3490529510847650949147849619903898133417764638493387843990820577 \)
\( q=32769132993266709549961988190834461413177642967992942539798288533 \)
\( \phi(n)=(p-1)(q-1) \)
\( =114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432 \)
\( =2^7 \times 3^2 \times 41 \times 2421697699819801568200283282015299204145881959714650291382152839165126878845264594586028238338845391099120671178712729570851 \)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
原本Simmons和Norris的方法可以在不分解n的情況下將原來的訊息解出來，之後Berkovits將密文c多次用加密函數運算，直到\( \displaystyle gcd(n,c^{e^k}-c)>1 \)，所得到的最大公因數就是n的因數。
S. Berkovits, Factoring via superencyrption, Cryptologia 6 (1982), 229-237.
http://www.tandfonline.com/doi/abs/10.1080/0161-117791833219
檔案需要大學的IP才能下載
FACTORING ALGORITHM 1: Let m be a square-free product of distinct primes and e an RSA enciphering exponent relatively prime to φ(n). Suppose c is an enciphered message.
1. Set x = c.
2. If f = gcd(c,n)≠1, go to step 6. (Note: otherwise, c is in \( R_n \).)
3. Replace x by \( x^e \) reduced modulo n.
4. If x = c, stop.
5. If f = gcd(x-c,n) = 1, go to step 3.
6. f is a divisor of n. Set n = n/f. Reduce x and c modulo the new n. Return to step 3 to seek further factors.
公鑰n=215629,e=49
(%i1)
n:215629;
e:49;
(%o1) 215629
(%o2) 49
密文c=1603
(%i3) c:1603;
(%o3) 1603
GCD=gcd(c^(e^k)-c,n)
若GCD>1則找到n的因數
(%i4)
x:c$
GCD:1$
while GCD=1 do
(x:power_mod(x,e,n),
GCD:gcd(x-c,n)
)$
GCD;
(%o7) 383
在論文中還提供另外一種循環攻擊的方法直接針對n值進行分解，這種方法不需要e和c值。
FACTORING ALGORITHM 2: Let n be a square-free product of distinct primes and F a multiplicative function from \( R_n \) to \( R_n \). Suppose c is a randomly chosen starting value.
1. Set x = c.
2. If f = gcd(c,n)≠1, go to step 6.
3. Replace x by F(x) reduced modulo n.
4. If x = c, stop.
5. If f = gcd(x-c,n) = 1, go to step 3.
6. Set m = m/f. Reduce x modulo the new n. Set c = x. Return to step 3.
要分解的n=215629
(%i1) n:215629;
(%o1) 215629
隨意選的c=1603
(%i2) c:1603;
(%o2) 1603
定義f(x)函數
(%i3) f(x):=mod(x^53,n);
(%o3) \( f(x):=mod(x^{53},n) \)
GCD=gcd(f(x)-c,n)
若GCD>1則找到n的因數
(%i4)
x:c$
GCD:1$
while GCD=1 do
(x:f(x),
GCD:gcd(x-c,n)
)$
GCD;
(%o7) 563
關於循環攻擊的補充資料
http://books.google.com.tw/books ... ge&q&f=true
|
