19 12
發新話題
打印

用Maxima學密碼學-RSA

推到噗浪
推到臉書

用Maxima學密碼學-RSA

緣起

之前我在圖書館看到一本用mathematica介紹密碼學的書,閱讀之後覺得滿有趣的,於是就想能不能改用maxima來實作看看,所以這篇文章算是我這段時間學習密碼學的心得,假如我沒有寫其中的數學知識或證明的話還是要請網友自行閱讀參考書藉。


以下是我參考的書籍
1.沈淵源,“密碼學之旅-與MATHEMATICA同行”
http://web.thu.edu.tw/billshen/www/
這裡可以下載書上的Mathematica程式碼


2.鄧安文,“密碼學-加密演算法”
像Wiener低冪次d攻擊就有詳細的證明及範例,數位簽章的部份也寫的比較多,算是為前一本書補充內容。


3.賴溪松、韓亮、張真誠,“近代密碼學及其應用”
http://uploadingit.com/file/c9hi ... %87%89%E7%94%A8.pdf
這本書提到很多密碼學的應用,如秘密分享、身分認證、電子投票機制等。


4.Fundamentals of Cryptology:A Professional Reference and Interactive Tutorial
作者:Henk C.A. van Tilborg
http://www.win.tue.nl/~henkvt/cryptobook/
這本書也是用mathematica當範例,最重要的是作者還提供pdf檔提供下載。


5.Introduction to Cryptography with Coding Theory
作者:Wade Trappe and Lawrence C. Washington
http://www2.math.umd.edu/~lcw/book.html
沈淵源書中的習題就是取自這本書,在網頁能下載Mathematica,Maple,MATLAB程式碼,我也嘗試著用maxima重新實作電腦習題。


網頁的部份可以看台科大所提供的密碼學與資訊安全教材
http://ec2.ba.ntust.edu.tw/mic/edu_ppt_security.htm
其他從google找到的相關論文、wiki網頁等,之後各單元提到時會附上連結。

101.12.17補充
密碼之過去、現在與未來
ftp://ftp.im.must.edu.tw/downloa ... FB%A4%E5%A5%F32.pdf

[ 本帖最後由 bugmens 於 2013-4-29 07:10 AM 編輯 ]

TOP

關於公鑰密碼及RSA加密演算法的歷史及介紹可以看這篇文章
沈淵源,公鑰密碼之旅
http://w3.math.sinica.edu.tw/media/media.jsp?voln=354



本次範例取自wiki,數字比較小比較容易了解RSA加密及解密的步驟。
http://en.wikipedia.org/wiki/RSA_(algorithm)#A_working_example


選兩個不同的質數
(%i1) 
p:61;
q:53;

(%o1) 61
(%o2) 53

計算n和φ(n)
(%i3) 
n:p*q;
phi_n: (p-1)*(q-1);

(%o3) 3233
(%o4) 3120

選取e(1<e<φ(n)),檢查是否和φ(n)互質
(%i5) 
e:17;
gcd(e,phi_n);
 
(%o5) 17
(%o6) 1

計算d=e^-1(mod φ(n))
(%i7) d:inv_mod(e,phi_n);
(%o7) 2753

公鑰是n=3233,e=17
私鑰是d=2753,p,q,φ(n)


要加密的訊息m(1<m<n)
(%i8) m:65;
(%o8) 65

用m^e(mod n)進行加密,密文為c
(%i9) c:power_mod(m,e,n);
(%o9) 2790

用c^d(mod n)進行解密,得到原訊息m
(%i10) power_mod(c,d,n);
(%o10) 65

檢查結果是否和原訊息相同
(%i11) is(%=m);
(%o11) true



線上執行網頁http://maxima-online.org/index.h ... c%2Cd%2Cn)%3B%0A%0A


101.11.14補充
為了加快加密速度,公鑰的e可以選65537,65537不僅是質數所以和\( \phi(n) \)互質,而且\( \displaystyle m^{65537}=m^{2^{16}+1}=\overbrace{(((m^2)^2)^2...)^2}^{16次} \cdot m \)只要17次模n乘法運算。



若要加快解密速度,則採用中國餘數定理的修訂版。證明請參閱"密碼學-加密演算法"P181。
範例取自http://en.wikipedia.org/wiki/RSA_(algorithm)#A_working_example
從私鑰d再計算\( d_p,d_q,q_{Inv} \)
\( d_p =d\pmod {p-1})=2753\pmod{61-1}=53 \)
\( d_q=d\pmod {q-1})=2753\pmod {53-1})=49 \)
\( q_{Inv}=q^{-1}\pmod{p}=53^{-1}\pmod{61}=38 \)
解密時計算
\( m_1=c^{d_p}\pmod{p}=2790^{53}\pmod{61}=4 \)
\( m_2=c^{d_q}\pmod{q}=2790^{49}\pmod{53}=12 \)
\( h=(q_{Inv}\times(m_1-m_2))\pmod{p}=(38\times -8)\pmod{61}=1 \)
\( m=m_2+h \times q=12+1 \times 53=65 \)


選兩個不同的質數
(%i1) 
p:61;
q:53;

(%o1) 61
(%o2) 53

計算n和φ(n)
(%i3) 
n:p*q;
phi_n: (p-1)*(q-1);

(%o3) 3233
(%o4) 3120

選取e(1<e<φ(n)),檢查是否和φ(n)互質
(%i5) 
e:17;
gcd(e,phi_n);
 
(%o5) 17
(%o6) 1

為了加快解密的速度,先計算
dp=d(mod (p-1))
dq=d(mod (q-1))
qInv=q^-1(mod p)

(%i7)
d:inv_mod(e,phi_n);
dp:mod(d,p-1);
dq:mod(d,q-1);
qInv:inv_mod(q,p);

(%o7) 2753
(%o8) 53
(%o9) 49
(%o10) 38

公鑰是n=3233,e=17
私鑰是d=2753,p,q,φ(n),dp,dq,qInv


要加密的訊息m(1<m<n)
(%i11) m:65;
(%o11) 65

用m^e(mod n)進行加密,密文為c
(%i12) c:power_mod(m,e,n);
(%o12) 2790

解密時計算m1,m2,h,還原出m
m1=c^dp(mod p)
m2=c^dq(mod q)
h=(qInv*(m1-m2))(mod p)
m=m2+h*q

(%i13)
m1:power_mod(c,dp,p);
m2:power_mod(c,dq,q);
h:mod(qInv*(m1-m2),p);
m2+h*q;

(%o13) 4
(%o14) 12
(%o15) 1
(%o16) 65

檢查結果是否和原訊息相同
(%i17) is(%=m);
(%o17) true



線上執行網頁http://maxima-online.org/index.h ... p)%3B%0Am2%2Bh*q%3B

[ 本帖最後由 bugmens 於 2012-11-17 09:35 AM 編輯 ]

TOP

RSA密碼是建立在要分解n是非常困難的基礎上,但假若私鑰不小心洩漏就能找出n的因數。

(1)已知\( \phi(n) \)來分解n
∵\( n=pq \),\( \phi(n)=(p-1)(q-1) \),∴\( p+q=n-\phi(n)+1 \)
\( \phi(n) \)定義http://en.wikipedia.org/wiki/Euler's_totient_function
\( p,q \)為一元二次方程式\( x^2-(p+q)x+pq=0 \),\( x^2-(n-\phi(n)+1)x+n=0 \)的兩根
利用公式解可以解出\( \displaystyle p,q=\frac{(n-\phi(n)+1) \pm \sqrt{(n-\phi(n)+1)^2-4n } }{2} \)


已知公鑰n=3233
(%i1) n:3233;
(%o1) 3233

若私鑰φ(n)不小心洩漏出去
φ(n)=3120

(%i2) phi_n:3120;
(%o2) 3120

p,q為二次方程式x^2-(n-φ(n)+1)x+n=0的兩根
(%i3) x^2-(n-phi_n+1)*x+n=0;
(%o3) \( x^2-114x+3233=0 \)

用公式解得到p,q
(%i4) solve(%,x);
(%o4) \( [ x=61,x=53 ] \)



線上執行網頁http://maxima-online.org/index.h ... )*x%2Bn%3D0%2Cx)%3B

(2)已知d來分解n
Universal Exponent Factorization Method
http://books.google.com.tw/books ... ge&q&f=true
按照網頁所描述的步驟寫成程式的話要比較多的if判斷式,假如不管那麼多的話程式碼會比較簡潔。


已知公鑰n=3233,e=17
(%i1)
n:3233;
e:17;

(%o1) 3233
(%o2) 17

若私鑰d不小心洩漏出去
d=2753

(%i3) d:2753;
(%o3) 2753

計算ed-1=2^b*m的b和m
(%i4)
ifactors(e*d-1);
b:%[1][2];
m: (e*d-1)/2^b;

(%o4) \( [ [2,4],[3,2],[5,2],[13,1] ] \)
(%o5) 4
(%o6) 2925

1.隨機選擇a值
2.計算\( \displaystyle x_0=a^m \pmod{n} \)
3.計算\( \displaystyle x_1=(x_0)^2 \pmod{n} \)
   \( \displaystyle x_2=(x_0)^4 \pmod{n} \)
   \( \displaystyle x_3=(x_0)^8\pmod{n} \)
   ...
   \( \displaystyle x_b=(x_0)^{2^b}\pmod{n} \)
4.計算各\( x_i-1 \)和n的最大公因數

隨著不同a值,可能會得到n的非顯然因數(53,61),也有可能只得到1或n,這時就要重新選取a再算一次

(%i7)
a:random(n);
x0:power_mod(a,m,n);
create_list(power_mod(x0,2^i,n),i,0,b);
create_list(gcd(x-1,n),x,%);

(%o7) 3159
(%o8) 2256
(%o9) \( [2256,794,1,1] \)
(%o10) \( [1,61,3233,3233,3233] \)



線上執行網頁http://maxima-online.org/index.h ... 1%2Cn)%2Cx%2Cxi)%3B

以下是不同a值計算的結果,有些得到因數(53或61),有些則沒有(1和3233)。
15
1
\( [1,1,1,1,1] \)
\( [3233,3233,3233,3233,3233] \)

318
2014
\( [2014,2014,2014,2014,2014] \)
\( [61,61,61,61,61] \)
得到n的因數61

2029
1
\( [1,1,1,1,1] \)
\( [3233,3233,3233,3233,3233] \)

2331
794
\( [794,1,1,1,1] \)
\( [61,3233,3233,3233,3233] \)
得到n的因數61

3056
560
\( [560,3232,1,1,1] \)
\( [1,1,3233,3233,3233] \)

3067
743
\( [743,2439,1,1,1] \)
\( [53,53,3233,3233,3233] \)
得到n的因數53

[ 本帖最後由 bugmens 於 2012-11-18 06:12 AM 編輯 ]

TOP

RSA-129挑戰

科學的美國人(Scientific American)雜誌於1977年8月在數學遊戲專欄中出現了一篇文章題為「數百萬年才解得開的新式密碼(A new kind of cipher that would take millions of years to break)」,作者就是該雜誌的數學遊戲專欄作家馬丁卡德那(Martin Gardner)。文中他介紹了瑞沙葉密碼系統(RSA Cryptosystem)。在解釋完加密方式如何運作後,卡德那代替M.I.T的作者群向讀者提出一項挑戰(簡稱RSA-129)。
(以上節錄自沈淵源,公鑰密碼之旅,http://w3.math.sinica.edu.tw/media/media.jsp?voln=354)

參考資料
http://www.mit.edu:8001/people/warlord/RSA129-announce.txt
http://en.wikipedia.org/wiki/The ... Squeamish_Ossifrage
更多的RSA挑戰,http://en.wikipedia.org/wiki/RSA_numbers
The Magic Words Are Squeamish Ossifrage,網頁右邊有pdf檔可以下載
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.8790



密文c
(%i1) c:96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154;
(%o1) 968696137546220614771409222543[68 digits]628013391990551829945157815154

公鑰n,e
(%i2)
n:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
e:9007;

(%o2) 114381625757888867669235779976[69 digits]058989075147599290026879543541
(%o3) 9007

n可分解為p,q
(%i4)
p:3490529510847650949147849619903898133417764638493387843990820577;
q:32769132993266709549961988190834461413177642967992942539798288533;

(%o4) 3490529510847650949147849619903898133417764638493387843990820577
(%o5) 32769132993266709549961988190834461413177642967992942539798288533

將私鑰d算出來
(%i6)
phi_n: (p-1)*(q-1);
d:inv_mod(e,phi_n);

(%o6) 114381625757888867669235779976[69 digits]512393667541112959643090434432
(%o7) 106698614368578024442868771328[69 digits]306553968544513277109053606095

將c解密後得到明文
(%i8) power_mod(c,d,n);
(%o8) 200805001301070903002315180419000118050019172105011309190800151919090618010705

計算明文的長度
(%i9) length:floor(float(log(%)/log(100)));
(%o9) 38

每兩個數字視為一個英文字母
(%i10) makelist(mod(floor(%o8/100^i),100),i,length,0,-1);
(%o10) \( [20,8,5,0,13,1,7,9,3,0,23,15,18,4,19,0,1,18,5,0,19,17,21,5,1,13,9,19,8,0,15,19,19,9,6,18,1,7,5] \)

用01=A,02=B,...,26=Z,00=@代換成英文字母
(%i11) makelist(ascii(i+64),i,%);
(%o11) \( [T,H,E,@,M,A,G,I,C,@,W,O,R,D,S,@,A,R,E,@,S,Q,U,E,A,M,I,S,H,@,O,S,S,I,F,R,A,G,E] \)

組合成一個字串
(%i12) simplode(%);
(%o12) THE@MAGIC@WORDS@ARE@SQUEAMISH@OSSIFRAGE

將其中的@取代為空白
(%i13) ssubst(" ","@",%);
(%o13) THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE




至於簽名檔說了些什麼?


簽名檔s
(%i1) s:16717861150380844246015271389168398245436901032358311217835038446929062655448792237114490509578608655662496577974840004057020373;
(%o1) 167178611503808442460152713891[68 digits]655662496577974840004057020373

公鑰n,e
(%i2)
n:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
e:9007;

(%o2) 114381625757888867669235779976[69 digits]058989075147599290026879543541
(%o3) 9007

將s解密後得到明文
(%i4) power_mod(s,e,n);
(%o4) 6091819200019151222051800230914190015140500082114041805040004151212011819

計算明文的長度
(%i5) length:floor(float(log(%)/log(100)));
(%o5) 36

每兩個數字視為一個英文字母
(%i6) makelist(mod(floor(%o4/100^i),100),i,length,0,-1);
(%o6) \( [6,9,18,19,20,0,19,15,12,22,5,18,0,23,9,14,19,0,15,14,5,0,8,21,14,4,18,5,4,0,4,15,12,12,1,18,19] \)

用01=A,02=B,...,26=Z,00=@代換成英文字母
(%i7) makelist(ascii(i+64),i,%);
(%o7) \( [F,I,R,S,T,@,S,O,L,V,E,R,@,W,I,N,S,@,O,N,E,@,H,U,N,D,R,E,D,@,D,O,L,L,A,R,S] \)

組合成一個字串
(%i8) simplode(%);
(%o8) FIRST@SOLVER@WINS@ONE@HUNDRED@DOLLARS

將其中的@取代為空白
(%i9) ssubst(" ","@",%);
(%o9) FIRST SOLVER WINS ONE HUNDRED DOLLARS



[ 本帖最後由 bugmens 於 2012-11-24 09:31 AM 編輯 ]

TOP

在使用RSA密碼系統時針對參數(p,q,e,d)的選取有幾個注意事項,以保證RSA密碼系統不會輕易遭受破解。

1.選擇n的注意事項-p與q必須為強質數(Strong Prime)
強質數的定義請看
Strong prime,http://en.wikipedia.org/wiki/Strong_prime
(1)p是一個大質數
(2)\( p-1 \)有大的質因數\( q_1 \)
(3)\( q_1-1 \)有大的質因數\( q_2 \)
(4)\( p+1 \)有大的質因數\( q_3 \)

而在《近代密碼學及其應用》一書中的定義是若質數p滿足下列條件,則此質數稱為強質數。
(1)存在兩個大質數\( p_1 \)及\( p_2 \),使得\( p_1 \bigm| p-1 \)且\( p_2 \bigm| p+1 \)。
(2)存在四個大質數\( r_1 \),\( s_1 \),\( r_2 \),\( s_2 \),使得\( r_1 \bigm| p_1-1 \),\( s_1 \bigm| p_1+1 \),\( r_2 \bigm| p_2-1 \)及\( s_2 \bigm| p_2+1 \)。


另外在RSA提出之際,就曾建議質數p與q的選取,應該為「強質數」,然而在稍後的年代RSA的原創者之一的R與他人合作一篇文章,文中卻又反駁p、q不需要是「強質數」。兩篇文章最主要的依據都是在於當代因數分解技術,要用「強質數」是因為Pollard的\( p-1 \)法及類似的Williams的\( p+1\)法,而不用「強質數」,卻是因為橢圓曲線因數分解(Elliptic Curve Factorization),因為橢圓曲線因數分解的特性是在於可平行處理處理計算,然而在其演算法本質而言,都可算是Pollard之\( p-1 \)法在橢圓曲線之推廣。
(本段落節錄自《密碼學-加密演算法》p204)

Pollard's p − 1 algorithm,http://en.wikipedia.org/wiki/Pollard's_p_%E2%88%92_1_algorithm
Williams' p + 1 algorithm,http://en.wikipedia.org/wiki/Williams'_p_%2B_1_algorithm
Williams, H. C. (1982), "A p+1 method of factoring", Mathematics of Computation 39 (159): 225–234
論文下載http://www.ams.org/journals/mcom ... -1982-0658227-7.pdf
Ron Rivest and Robert Silverman, Are 'Strong' Primes Needed for RSA?, Cryptology ePrint Archive: Report 2001/007.
論文下載http://people.csail.mit.edu/rive ... sion-1999-11-22.pdf


以下僅就Pollard's p − 1 algorithm提供範例
1.選取\( a>1 \),通常選\( a=2 \),選取上限B。
2.計算\( b=a^{B!} \pmod{n} \)。
3.計算\( b-1 \)和n的最大公因數,若找不到n的非顯然因數,則再重新選取更大的B再計算步驟2。



要分解的n
(%i1) n:8834884587090814646372459890377418962766907;
(%o1) 8834884587090814646372459890377418962766907

選擇a=2,B=100
B若比73小就無法分解n

(%i2)
a:2;
B:100;

(%o2) 2
(%o3) 100

計算mod(2^B!,n)
(%i4) b:power_mod(2,B!,n);
(%o4) 961623821657800055077023229270715484248143

n的其中一個因數為p
(%i5) p:gcd(b-1,n);
(%o5) 364438989216827965440001

另一個因數為q
(%i6) q:n/p;
(%o6) 24242424242468686907

因為p-1的質因數都比B值小,所以Pollard's p-1 algorithm才會成功
p-1稱為73-smooth number,因為p-1的所有質因數都比73還小

http://en.wikipedia.org/wiki/Smooth_number
(%i7) factor(p-1);
(%o7) \( 2^{20} \times 3^{11} \times 5^4 \times 7^2 \times 11 \times 13 \times 17 \times 19^2 \times 73 \)

雖然q-1有很大的質因數,卻無法阻止n被分解出來
(%i8) factor(q-1);
(%o8) \( 2 \times 12121212121234343453 \)



線上執行網頁http://maxima-online.org/index.h ... 0A%0Afactor(q-1)%3B



前面的例子因為\( p-1 \)有小的質因數,導致n被分解出來。我另外找另一個n,雖然和前一個n差不多大小,但這次的\( p-1\)有大的質因數導致Pollard's p-1 algorithm失敗。
n:8834884587090814646372459890377418962766907
n:8834884587090814639656521335894475316521399



要分解的n
(%i1) n:8834884587090814639656521335894475316521399;
(%o1) 8834884587090814639656521335894475316521399

選擇a=2,B=100
(%i2)
a:2;
B:100;

(%o2) 2
(%o3) 100

計算mod(2^B!,n)
(%i4) b:power_mod(2,B!,n);
(%o4) 781125290367988008018775069199843756768634

卻無法得到n的非顯然因數
(%i5) gcd(b-1,n);
(%o5) 1

直接對n作分解(這步可以跳過,因為分解n要花近五分鐘)
(%i6)
showtime:true$
factor(n);
showtime:false$

Evaluation took 0.0000 seconds (0.0000 elapsed)
Evaluation took 267.2400 seconds (267.2400 elapsed)
(%o7) \( 2972353375204707154867 \times 2972353375204707157997 \)

發現p-1和q-1都有非常大的質因數
導致Pollard's p-1 algorithm失敗

(%i9)
factor(2972353375204707154867-1);
factor(2972353375204707157997-1);

(%o9) \( 2 \times 3 \times 495392229200784525811 \)
(%o10) \( 2^2 \times 743088343801176789499 \)

再對這兩個大的質因數作-1的質因數分解發現還是有大的質因數
(%i11)
factor(495392229200784525811-1);
factor(743088343801176789499-1);

(%o11) \( 2 \times 3 \times 5 \times 17 \times 162417691 \times 5980612741 \)
(%o12) \( 2 \times 3^2 \times 509 \times 115641403 \times 701353243 \)



線上執行網頁http://maxima-online.org/index.h ... 3801176789499-1)%3B



再來檢驗之前RSA-129挑戰中的n值是否能抵擋Pollard's p-1 algorithm。



n的兩個因數p,q
(%1)
p:3490529510847650949147849619903898133417764638493387843990820577;
q:32769132993266709549961988190834461413177642967992942539798288533;

(%o1) 3490529510847650949147849619903898133417764638493387843990820577
(%o2) 32769132993266709549961988190834461413177642967992942539798288533

對p-1,q-1進行因數分解,都有大質因數Pollard's p − 1 algorithm失敗
(%i3)
factor(p-1);
factor(q-1);

(%o3) \( 2^5 \times 3^2 \times 12119894134887676906763366735777424074367238328102041124968127 \)
(%o4) \( 2^2 \times 41 \times 199811786544309204572938952383136959836449042487761844754867613 \)

對p+1進行因數分解,都有大質因數Williams' p + 1 algorithm失敗
這個質因數大太了,maxima無法分解,我另外從這裡的網頁下載程式分解出來的

http://home.netcom.com/~jrhowell49/math/software.htm
(%i5) factor(p+1);
(%o5) \( 2 \times 1376164939307949996650933 \times 1268208995573953158702179979684459411533 \)

對q+1進行因數分解,都有大質因數Williams' p + 1 algorithm失敗
(%i6) factor(q+1);
(%o6) \( 2 \times 3^4 \times 11 \times 79 \times 197 \times 227 \times  5205207856415260542784378886786939753890016296212410737 \)



線上執行網頁http://maxima-online.org/index.h ... %0Afactor(q%2B1)%3B

[ 本帖最後由 bugmens 於 2012-12-1 10:29 PM 編輯 ]

TOP

2.選擇n的注意事項-p和q的差要很大
若p,q的差很小時就可以用Fermat的因數分解法
http://en.wikipedia.org/wiki/Fermat's_factorization_method
我用wiki的例子講解
\( N=5959 \)
計算\( a=\lceil\; \sqrt{N} \rceil\;=78 \),\( b2=a^2-N=125 \),但\( b2 \)不是完全平方數
計算\( a=78+1=79 \),\( b2=a^2-N=282 \),但\( b2 \)不是完全平方數
計算\( a=79+1=80 \),\( b2=a^2-N=441 \),此時\( b2=21^2 \)是完全平方數
所以\( N=80^2-21^2=(80-21)(80+21)=59 \times 101 \)

知道原理後,我再拿前面例子來檢驗,像這個n可以抵擋Pollard's p-1的分解法,看看Fermat因數分解法能否成功
n:8834884587090814639656521335894475316521399
執行以下的程式後n能被分解,其原因在於n的兩個因數p,q才相差三千多而已
而且在第一次計算\( a=\lceil\; \sqrt{N} \rceil\; \),\( b2=a^2-n \)時,\( b2 \)就是完全平方數
得到\( n=2972353375204707156432^2-1565^2 \)
   \( =(2972353375204707156432-1565)(2972353375204707156432+1565) \)
   \( =2972353375204707154867 \times 2972353375204707157997 \)


要分解的n
(%i1) n:8834884587090814639656521335894475316521399;
(%o1) 8834884587090814639656521335894475316521399

使用Fermat's factorization method分解n
(%i2)
a:isqrt(n)+1$
b2:a*a-n$
while integerp(sqrt(b2))=false do
  (a:a+1,
   b2:a*a-n
  )$
b:sqrt(b2)$
a-b;a+b;

(%o6) 2972353375204707154867
(%o7) 2972353375204707157997



線上執行網頁http://maxima-online.org/index.h ... 24%0Aa-b%3Ba%2Bb%3B


而RSA-129挑戰的兩個因數
p:3490529510847650949147849619903898133417764638493387843990820577;
q:32769132993266709549961988190834461413177642967992942539798288533;
雖然p,q看起來才相差一位數而已,但兩數相差了\( 2.927 \times 10^{65} \),Fermat因數分解法失敗。

[ 本帖最後由 bugmens 於 2012-12-8 10:14 AM 編輯 ]

TOP

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

[ 本帖最後由 bugmens 於 2012-12-25 10:37 PM 編輯 ]

TOP

5.選擇n的注意事項-p,q要足夠大到讓n難以分解

以下是關於RSA因數分解的歷史紀錄。
RSA numbers
http://en.wikipedia.org/wiki/RSA_numbers
RSA Factoring Challenge
http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

最新的紀錄是2012.7.1由Shi Bai, Emmanuel Thomé and Paul Zimmermann破解了RSA-704(704bits,212位數)。
使用的軟體是CADO-NFS http://cado-nfs.gforge.inria.fr/,這三位也是該軟體的開發者。
詳細內容請見
http://maths-people.anu.edu.au/~bai/paper/rsa704.pdf

TOP

1.選擇e得注意事項-e不可以太小

公鑰e只要滿足\( gcd(e,\phi(n))=1 \)即可,有些人會取\( e=3 \)加速加密運算時間( \( e=2 \)不滿足\( gcd(e,\phi(n))=1 \),因為\( \phi(n) \)為偶數 ),可是,若e太小時,會有以下的缺點。
(1)密文\( c=m^3 \pmod{n} \),若\( m^3<n \)時,則在加密中無模n運算,因此c為完全立方數,只要開立方根就可以得到原訊息m。
(2)低指數攻擊(Low Exponent Attack)或稱為Håstad's Broadcast Attack
令網路中三人,其公鑰e均為3,而模分別為\( n_1,n_2,n_3 \)。若有一人欲傳送相同的訊息m給此三人,將其加密後的密文分別為
$$ c_1=m^3 \pmod{n_1} $$
$$ c_2=m^3 \pmod{n_2} $$
$$ c_3=m^3 \pmod{n_3} $$
其中\( n_1,n_2,n_3 \)兩兩互質(若不是,則可利用輾轉相除法求出因數),依據中國餘數定理可得
$$ x_1=(n_2 \cdot n_3)^{-1} \pmod{n_1} $$
$$ x_2=(n_1 \cdot n_3)^{-1} \pmod{n_2} $$
$$ x_3=(n_1 \cdot n_2)^{-1} \pmod{n_3} $$
$$ c=c1 \cdot n_2 \cdot n_3 \cdot x_1+c2 \cdot n_1 \cdot n_3 \cdot x_2+c3 \cdot n_1 \cdot n_2 \cdot x_3 \pmod{n_1 \cdot n_2 \cdot n_3} $$
由於m分別小於\( n_1,n_2,n_3 \),所以\( c=m^3 \)亦小於\( n_1,n_2,n_3 \)的乘積,將c開立方根就可以得到原訊息m。
$$ m=\root 3 \of{c} $$

以下的範例取自
http://zh.scribd.com/doc/57524064/Attack-of-RSA-1#page=189


三人的公鑰e都是3,n1,n2,n3互質
(%i1)
e:3;
n1:16074226778088739019349815403643227770685367817263534943166979954698715554393070406149127242391287149108746723343762489162841829;
n2:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
n3:1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557;

(%o1) 3
(%o2) 160742267780887390193498154036[68 digits]149108746723343762489162841829
(%o3) 114381625757888867669235779976[69 digits]058989075147599290026879543541
(%o4) 180708208868740480595165616440[70 digits]371781887966563182013214880557

同一個訊息m被加密成三個不同的密文c1,c2,c3
(%i5)
c1:7291913358636035240947025637374028196857235660005241522463031241555895619504906815661389620497786790869406527191986148822210607;
c2:14800374214506730032543778558119032707134617660958377942793871641230023464834717560657470071521171252206971742318084225589053107;
c3:1667417213289240211973260079641217729806206725889216707866808971068771946972116581884674553882803753277272900087640189457978330457;

(%o5) 131506270662671828574839340640[68 digits]972337998986378821282435927139
(%o6) 108564166174861010120624729942[69 digits]411389387338344415737745427982
(%o7) 420582619673894243647216164427[69 digits]687865046918793292238332011322

利用中國餘數定理計算密文c
(%i8)
x1:inv_mod(n2*n3,n1);
x2:inv_mod(n1*n3,n2);
x3:inv_mod(n1*n2,n3);

(%o8) 131506270662671828574839340640[68 digits]972337998986378821282435927139
(%o9) 108564166174861010120624729942[69 digits]411389387338344415737745427982
(%o10) 420582619673894243647216164427[69 digits]687865046918793292238332011322

(%i11) c:mod(c1*n2*n3*x1+c2*n1*n3*x2+c3*n1*n2*x3,n1*n2*n3);
(%o11) 809698949404799825175318829599[172 digits]287023918357565845861111152625

再開三次根號解出原訊息m
(%i12) m:c^(1/3);
(%o12) 200805001301070903002315180419000118050019172105011309190800151919090618010705

將原訊息m轉換成英文字母,發現是RSA-129的訊息
(%i13)
length:floor(float(log(m)/log(100)));
makelist(mod(floor(m/100^i),100),i,length,0,-1);
makelist(ascii(i+64),i,%);
simplode(%);
ssubst(" ","@",%);

(%o13) 38
(%o14) [20,8,5,0,13,1,7,9,3,0,23,15,18,4,19,0,1,18,5,0,19,17,21,5,1,13,9,19,8,0,15,19,19,9,6,18,1,7,5
]
(%o15) [ T,H,E,@,M,A,G,I,C,@,W,O,R,D,S,@,A,R,E,@,S,Q,U,E,A,M,I,S,H,@,O,S,S,I,F,R,A,G,E ]
(%o16) THE@MAGIC@WORDS@ARE@SQUEAMISH@OSSIFRAGE
(%o17) THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE




其實接下來還有更多的內容,如兩個訊息有倍數關係( \( M2=\alpha M1+\beta \) ),coppersmith方法等。將來看懂的話再補上。
書名:Cryptanalytic Attacks on RSA
作者:Song Y.Yan
http://zh.scribd.com/doc/57524064/Attack-of-RSA-1#page=190

[ 本帖最後由 bugmens 於 2013-1-5 07:05 PM 編輯 ]

TOP

2.選擇e的注意事項-要讓\( \displaystyle c^{e^k}=c \)的k值越大越好

在之前的循環攻擊中提到,對密文c反覆計算\( c^{e^k} \)直到等於原來的密文為止。假若k很大的話,循環攻擊就會失敗。
https://math.pro/db/viewthread.php?tid=1500&page=1#pid7395


公鑰n=2773
(%i1) n:2773;
(%o1) 2773

計算φ(φ(n))=1232和1232的正因數
[color](%i2)
totient(totient(n));
divisors(%);

(%o2) 1232
(%o3) {1,2,4,7,8,11,14,16,22,28,44,56,77,88,112,154,176,308,616,1232}

當公鑰e=17時,任何的密文c最多經過e的44次次方運算就會等於自己(c^e^44=c)
所以原訊息m=c^e^43
不同的c值所需要的次方運算甚至會更少
c=2596 , c^e^22=c , 需要22次方
c=818  , c^e^44=c , 需要44次方
c=1    , c^e^1 =c , 需要1 次方
c=2423 , c^e^44=c , 需要44次方
c=508  , c^e^44=c , 需要44次方
c=1504 , c^e^4 =c , 需要4 次方
c=1444 , c^e^44=c , 需要44次方

(%i4)
e:17;
map(lambda([x],if power_mod(e,x,totient(n))=1 then x),%o3);

(%o4) 17
(%o5) {44,88,176,308,616,1232,false}

假若e值選的不好,只要e的2次次方運算就會等於自己(c^e^2=c)
所以原訊息m=c^e^1,遭遇循環攻擊時一下子就被破解了
類似的e值還有231,1103,1333,1335,1565,2437,2667共7個

(%i6)
e:231;
map(lambda([x],if power_mod(e,x,totient(n))=1 then x),%o3);

(%o6) 231
(%o7) {2,4,8,14,16,22,28,44,56,88,112,154,176,308,616,1232,false}

所以要選的e值是能讓c^e^k=c的k值越大越好,遭到循環攻擊時就不容易被破解
符合gcd(e,φ(n))=1的所有e值中,最大的k值只能到308次方
類似的e值還有3,11,15,19,21,27,31,37,39,...,2765,2769,2773共501個

(%i8)
e:3;
map(lambda([x],if power_mod(e,x,totient(n))=1 then x),%o3);

(%o8) 3
(%o9) {308,616,1232,false}



[ 本帖最後由 bugmens 於 2013-1-21 10:27 AM 編輯 ]

TOP

 19 12
發新話題