標題: 用Maxima學密碼學－RSA [打印本頁]

---

作者: bugmens    時間: 2012-11-6 22:23     標題: 用Maxima學密碼學－RSA

緣起

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


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


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


3.賴溪松、韓亮、張真誠，“近代密碼學及其應用”
h ttp://uploadingit.com/file/c9hi2jkmmzrf7xly/%E8%A8%88%E7%AE%97%E6%A9%9F%E5%AF%86%E7%A2%BC%E5%AD%B8%E5%8F%8A%E5%85%B6%E6%87%89%E7%94%A8.pdf　連結已失效
這本書提到很多密碼學的應用，如秘密分享、身分認證、電子投票機制等。


4.Fundamentals of Cryptology:A Professional Reference and Interactive Tutorial
作者：Henk C.A. van Tilborg
h ttp://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重新實作電腦習題。


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

111.4.2補充
密碼學與資訊安全，https://math.pro/db/attachment.p ... 44&t=1648893908
第1章資訊安全整體架構
第2章密碼技術安全評估
第3章密碼學數學基礎
第4章對稱密碼系統
第5章非對稱密碼系統
第6章數位簽章技術
第7章橢圓曲線密碼系統
第8章IC卡密碼演算法
第9章不可否認機制
第10章機密共享機制
第11章公開金鑰基礎建設與憑證機構

101.12.17補充
密碼之過去、現在與未來
f tp://ftp.im.must.edu.tw/download/tbg/CC/Acrobat%209.0%20demo%20file/03%20%B7%BE%B3q-0/04%20%A4%F1%B8%FB%A4%E5%A5%F3-0/1%20%A4%E5%A6r-0/%A4%F1%B8%FB%A4%E5%A5%F32.pdf　連結已失效

---

作者: bugmens    時間: 2012-11-11 21:02

關於公鑰密碼及RSA加密演算法的歷史及介紹可以看這篇文章
沈淵源，公鑰密碼之旅
https://web.math.sinica.edu.tw/m ... cle18.jsp?mID=35404



本次範例取自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



線上執行網頁h ttp://maxima-online.org/index.html?in=p%3A61%3B%0Aq%3A53%3B%0An%3Ap*q%3B%0Aphi_n%3A%20(p-1)*(q-1)%3B%0Ae%3A17%3B%0Agcd(e%2Cphi_n)%3B%0Ad%3Ainv_mod(e%2Cphi_n)%3B%0Am%3A65%3B%0Ac%3Apower_mod(m%2Ce%2Cn)%3B%0Apower_mod(c%2Cd%2Cn)%3B%0A#?in=%2F*%E4%BB%8A%E5%A4%A9%E5%A4%A9%E6%B0%A3%E5%A5%BD*%2F%0A%0Ap%3A61%3B%0Aq%3A53%3B%0An%3Ap*q%3B%0Aphi_n%3A%20(p-1)*(q-1)%3B%0Ae%3A17%3B%0Agcd(e%2Cphi_n)%3B%0Ad%3Ainv_mod(e%2Cphi_n)%3B%0Am%3A65%3B%0Ac%3Apower_mod(m%2Ce%2Cn)%3B%0Apower_mod(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



線上執行網頁h ttp://maxima-online.org/index.html?in=p%3A61%3B%0A%0Aq%3A53%3B%0A%0An%3Ap*q%3B%0A%0Aphi_n%3A%20(p-1)*(q-1)%3B%0A%0Ae%3A17%3B%0A%0Agcd(e%2Cphi_n)%3B%0A%0Ad%3Ainv_mod(e%2Cphi_n)%3B%0Adp%3Amod(d%2Cp-1)%3B%0Adq%3Amod(d%2Cq-1)%3B%0AqInv%3Ainv_mod(q%2Cp)%3B%0A%0Am%3A65%3B%0A%0Ac%3Apower_mod(m%2Ce%2Cn)%3B%0A%0Am1%3Apower_mod(c%2Cdp%2Cp)%3B%0Am2%3Apower_mod(c%2Cdq%2Cq)%3B%0Ah%3Amod(qInv*(m1-m2)%2Cp)%3B%0Am2%2Bh*q%3B　連結已失效

---

作者: bugmens    時間: 2012-11-17 11:57

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 ] \)



線上執行網頁h ttp://maxima-online.org/index.html?in=n%3A3233%3B%0A%0Aphi_n%3A3120%3B%0A%0Ax%5E2-(n-phi_n%2B1)*x%2Bn%3D0%3B%0A%0Asolve(x%5E2-(n-phi_n%2B1)*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] \)



線上執行網頁h ttp://maxima-online.org/index.html?in=n%3A3233%3B%0A%0Ae%3A17%3B%0A%0Ad%3A2753%3B%0A%0Ab%3Aifactors(e*d-1)%5B1%5D%5B2%5D%3B%0A%0Am%3A%20(e*d-1)%2F2%5Eb%3B%0A%0Aa%3Arandom(n)%3B%0A%0Ax0%3Apower_mod(a%2Cm%2Cn)%3B%0A%0Axi%3Acreate_list(power_mod(x0%2C2%5Ei%2Cn)%2Ci%2C0%2Cb)%3B%0A%0Acreate_list(gcd(x-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-23 19:51

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)。
(以上節錄自沈淵源，公鑰密碼之旅，https://web.math.sinica.edu.tw/m ... cle18.jsp?mID=35404)

參考資料
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-12-1 10:55

在使用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 \)



線上執行網頁h ttp://maxima-online.org/index.html?in=n%3A8834884587090814646372459890377418962766907%3B%0A%0Aa%3A2%3B%0AB%3A100%3B%0A%0Ab%3Apower_mod(2%2CB!%2Cn)%3B%0A%0Ap%3Agcd(b-1%2Cn)%3B%0A%0Aq%3An%2Fp%3B%0A%0Afactor(p-1)%3B%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 \)



線上執行網頁h ttp://maxima-online.org/index.html?in=n%3A8834884587090814639656521335894475316521399%3B%0A%0Aa%3A2%3B%0AB%3A100%3B%0A%0Ab%3Apower_mod(2%2CB!%2Cn)%3B%0A%0Agcd(b-1%2Cn)%3B%0A%0Afactor(2972353375204707154867-1)%3B%0Afactor(2972353375204707157997-1)%3B%0A%0Afactor(495392229200784525811-1)%3B%0Afactor(743088343801176789499-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 \)



線上執行網頁h ttp://maxima-online.org/index.html?in=p%3A3490529510847650949147849619903898133417764638493387843990820577%3B%0Aq%3A32769132993266709549961988190834461413177642967992942539798288533%3B%0A%0Afactor(p-1)%3B%0Afactor(q-1)%3B%0A%0Afactor(q%2B1)%3B　連結已失效

---

作者: bugmens    時間: 2012-12-8 09:19

2.選擇n的注意事項－p和q的差要很大
若p,q的差很小時就可以用Fermat的因數分解法
https://en.wikipedia.org/wiki/Fermat%27s_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



線上執行網頁h ttp://maxima-online.org/index.html?in=n%3A8834884587090814639656521335894475316521399%3B%0A%0Aa%3Aisqrt(n)%2B1%24%0Ab2%3Aa*a-n%24%0Awhile%20integerp(sqrt(b2))%3Dfalse%20do%0A%20%20(a%3Aa%2B1%2C%0A%20%20%20b2%3Aa*a-n%0A%20%20)%24%0Ab%3Asqrt(b2)%24%0Aa-b%3Ba%2Bb%3B　連結已失效


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

---

作者: bugmens    時間: 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

---

作者: bugmens    時間: 2013-1-5 08:03

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　https://cado-nfs.gitlabpages.inria.fr/，這三位也是該軟體的開發者。
詳細內容請見
連結已失效h ttp://maths-people.anu.edu.au/~bai/paper/rsa704.pdf

---

作者: bugmens    時間: 2013-1-5 09:02

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
h ttp://zh.scribd.com/doc/57524064/Attack-of-RSA-1#page=190　連結已失效

---

作者: bugmens    時間: 2013-1-12 10:04

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 11:57

1.選擇d的注意事項－d要大於\( \displaystyle \frac{1}{3}\root 4 \of n \)

在許多應用場合中，我們常希望使用位元數較短的秘密金匙d，以降低解密或簽署的時間。例如在IC卡應用中，IC卡CPU的計算能力遠低於主電腦。長度較短的d可以減少IC卡的解密或簽署時間，而讓較複雜的加密或驗證運算(e長度較長)由快速的主電腦執行。
一個直接的問題產生了，解密金匙d的長度減少後是否會造成安全性的降低，使用RSA變得不安全呢？很明顯地，若d的長度太小，我們可利用已知明文m加密後得\( c=m^e \pmod{n} \)，再直接猜測d，求出\( c^d \pmod{n} \)是否等於m。若是，則d為正確，否則繼續猜測d。若d的長度很小，則此猜測d之空間變小，猜對的機率相對地變大。因此，d的長度不能大小。1990年Wiener進一步提出一種針對d長度較小的攻擊法。他證明了若d的長度小於n長度的\( \displaystyle \frac{1}{4} \)時，利用連分數演算法，可以在多項式時間(Polynomial Time)內求出正確的d。
(本段落節錄自《近代密碼學及其應用》p7-18)

範例取自http://en.wikipedia.org/wiki/Wiener's_attack#Example


要先載入basic.mac才能使用push指令
(%i1)　load("basic.mac");
(%o1)　C:/PROGRA~1/MAXIMA~1.0-2/share/maxima/5.28.0-2/share/macro/basic.mac

公鑰e=17993,n=90581
(%i2)
e:17993;
n:90581;
(%o2)　17993
(%o3)　90581

求出e/n的連分數表示法
(%i4)　List:cf(e/n);
(%o4)　[0,5,29,4,1,3,2,4,3]

取出e/n的近似分數
(%i5)
L:[]$
L:create_list(reverse(push(x,L)),x,List);
(%o6)　[[0],[0,5],[0,5,29],[0,5,29,4],[0,5,29,4,1],[0,5,29,4,1,3],[0,5,29,4,1,3,2],[0,5,29,4,1,3,2,4],[0,5,29,4,1,3,2,4,3]]

(%i7)　fractions:map(lambda([x],ratsimp(cfdisrep(x))),L);
(%o7)　[\( \displaystyle 0,\frac{1}{5},\frac{29}{146},\frac{117}{589},\frac{146}{735},\frac{555}{2794},\frac{1256}{6323},\frac{5579}{28086},\frac{17993}{90581} \)]

從e/n的近似分數k/d猜測可能的φ(n)=(e*d-1)/k
代入方程式x^2-(n-φ(n)+1)x+n=0
若方程式有正整數解，則該解為n的因數
(%i8)
for fraction in fractions do
  (k:num(fraction),
   d:denom(fraction),
   if k>0 then
     (phi_n: (e*d-1)/k,
      if integerp(phi_n)=true then
        (equation:x^2-(n-phi_n+1)*x+n,
         solution:solve(equation,x),
         print(fraction),
         print(equation,"=0"),
         print(solution)
        )
     )
  )$
\( \displaystyle \frac{1}{5} \)
\( x^2-618x+90581=0 \)
\( [x=379,x=239] \)

除了上面的方法來找正確的φ(n)之外
還可以計算a^(e*d-1)(mod n)是否為1
若計算結果為1，則d是正確的密鑰
(%i9)
a:2$
for fraction in fractions do
  (d:denom(fraction),
   if power_mod(a,e*d-1,n)=1 then
     print("d=",d)
  )$
d=5

此時密鑰d會小於1/3*n^(1/4)
(%i11)　float(1/3*n^(1/4));
(%o11)　5.78279801148755



這個例子比較大，可以觀察要好幾次的試驗後才能找到正確的\( \phi(n) \)
e:60728973;
n:160523347;

而RSA-129的d為\( 1.0669861436857801*10^{128} \)，\( \displaystyle \frac{1}{3}\root 4 \of n \)為\( 3.4472105605815344*10^{31} \)，Wiener的連分數攻擊法失敗。
https://math.pro/db/viewthread.php?tid=1500&page=1#pid7305

---

作者: bugmens    時間: 2013-1-26 21:52

之前n、e及d等參數的選擇，都會關係到RSA系統的安全性。若這些參數的選擇不當，則以這些參數所構成的RSA系統，在理論上會造成不安全。但就算參數選得好，若不當的使用即使安全的RSA系統亦會造成不安全的情況。

1.使用RSA時的注意事項－不可以使用共同的模n(Common Modulus Protocol Failure)
若將相同明文m用不同的公鑰加密成密文後發送給兩位使用者
$$ c1 \equiv m^{e1}\pmod{n} $$
$$ c2 \equiv m^{e2}\pmod{n} $$
若被人擷取到這兩個密文，只要e1和e2是互質的話，就可以用輾轉相除法計算符合\( e1*x+e2*y=1 \)的整數x和y。只要計算以下的式子就可以得到明文m。
$$ c1^x*c2^y \equiv (m^{e1})^x*(m^{e2})^y \equiv m^{e1*x+e2*y} \equiv m \pmod{n} $$

這個範例取自Cryptanalytic Attacks on RSA第162頁


公鑰e1=9007,e2=65537,n
(%i1)
e1:9007;
e2:65537;
n:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
(%o1)　9007
(%o2)　65537
(%o3)　114381625757888867669235779976[69 digits]058989075147599290026879543541

相同明文m用不同的公鑰(e1,e2)加密得到不同的密文(c1,c2)
(%i4)
c1:104202250941196238413638382607974125774449084724929591257433745889265297771717182413024642938078351979089945343407464161377977212;
c2:76452750729188700180719970517544574710944757317909896041340987488285573190280783480309084978021563396490759750600519496071304348;
(%o4)　104202250941196238413638382607[69 digits]979089945343407464161377977212
(%o5)　764527507291887001807199705175[68 digits]396490759750600519496071304348

因為e1和e2互質，存在整數x,y使得e1*x+e2*y=1，可用gcdex指令得到x,y
(%i6)　[x,y,k]:gcdex(e1,e2);
(%o6)　[-8877,1220,1]

計算mod(c1^x*c2^y,n)得到明文m
(%i7)　m:mod(power_mod(c1,x,n)*power_mod(c2,y,n),n);
(%o7)　19050321180920251905182209030519

計算明文的長度
(%i8)　length:floor(float(log(%)/log(100)));
(%o8)　15

每兩個數字視為一個字母
(%i9)　makelist(mod(floor(m/100^i),100),i,length,0,-1);
(%o9)　[19,5,3,21,18,9,20,25,19,5,18,22,9,3,5,19]

用01=A,02=B,...,26=Z,00=@代換成英文字母
(%i10)　makelist(ascii(i+64),i,%);
(%o10)　[S,E,C,U,R,I,T,Y,S,E,R,V,I,C,E,S]

組合成一個字串
(%i11)　simplode(%);
(%o11)　SECURITYSERVICES


112.3.22補充
這個範例取自
GUSTAVUS J. SIMMONS (1983) A “WEAK” PRIVACY PROTOCOL USING THE RSA CRYPTO ALGORITHM, Cryptologia, 7:2, 180-182, DOI: 10.1080/0161-118391857900
https://www.tandfonline.com/doi/abs/10.1080/0161-118391857900

公鑰e1=127,e2=149,n
(%i1)
e1:127;
e2:149;
n:101014219618813;
(%o1)　127
(%o2)　149
(%o3)　101014219618813

相同明文m用不同的公鑰(e1,e2)加密得到不同的密文(c1,c2)
(%i4)
c1:72263729504163;
c2:33411612782365;
(%o4)　72263729504163
(%o5)　33411612782365

因為e1和e2互質，存在整數x,y使得e1*x+e2*y=1，可用gcdex指令得到x,y
(%i6)　[x,y,k]:gcdex(e1,e2);
(%o6)　[-61,52,1]

計算mod(c1^x*c2^y,n)得到明文m
(%i7)　m:mod(power_mod(c1,x,n)*power_mod(c2,y,n),n);
(%o7)　19051212021282

將後6位時間戳記刪除
(%i8)　m:floor(m/10^6);
(%o8)　19051212

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

每兩個數字視為一個字母
(%i10)　makelist(mod(floor(m/100^i),100),i,length,0,-1);
(%o10)　[19,5,12,12]

用01=A,02=B,...,26=Z,00=@代換成英文字母
(%i11)　makelist(ascii(i+64),i,%);
(%o11)　[S,E,L,L]

組合成一個字串
(%i12)　simplode(%);
(%o12)　SELL

---

作者: bugmens    時間: 2013-2-3 10:24

2.使用RSA時的注意事項－不可將私鑰洩漏出去

前面提到如果私鑰d或φ(n)洩漏出去會導致n被分解。
https://math.pro/db/viewthread.php?tid=1500&page=1#pid7291
更進一步只要洩漏部份訊息也能將n分解

令\( n=pq \)為m bits，如果知道p的前\( \displaystyle \frac{m}{4} \)bits或後\( \displaystyle \frac{m}{4} \)bits，則能在多項式時間內將n分解。
D. Coppersmith, "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerability", Journal of Cryptology, 10, (1997), pp 233-260.
http://link.springer.com/article/10.1007%2Fs001459900030?LI=true

令\( n=pq \)為m bits，如果知道d的後\( \displaystyle \frac{m}{4} \)bits，則在\( O(e log_2 e) \)時間內得到完整的d。
D. Boneh, G. Durfee and Y. Frankel, "An Attack on RSA Given a Small Fraction of the Private Key Bits", Advances in Cryptology - Asiacrypt '98, Lecture Notes in Computer Science 1514, Springer, 1998, pp 25-34.
http://crypto.stanford.edu/~dabo/pubs/abstracts/bits_of_d.html

此範例取自Cryptanalytic Attacks on RSA第204頁
已知公鑰\( n=1633 \)，\( e=23 \)，部分私鑰\( d_0=(011)_2=3 \)，試求出完整的私鑰d。
第1步
\( e \cdot d \equiv 1 \pmod{\phi(n)} \)
\( e \cdot d=1+k \cdot \phi(n) \)，\( k \)為整數
\( e \cdot d=1+k \cdot(p-1)(q-1) \)
\( e \cdot d=1+k \cdot (pq-p-q+1) \)
將\( n=pq \)，\( s=p+q \)代入
\( e \cdot d=1+k \cdot(n-s+1) \)
假設\( d_0=(011)_2=3 \)為d後3 bits
\( e \cdot d_0\equiv 1+k \cdot(n-s+1)\pmod{2^{3}} \)
\( 23 \cdot 3 \equiv 1+k(1633-s+1)\pmod{8} \)
\( s \equiv 6 \pmod{8} \)

第2步
\( p^2-(p+q)p+pq=0 \)
假設\( p_0 \)是p的後3 bits
\( \displaystyle p_0^2-sp_0+n \equiv 0 \pmod{8} \)
\( p_0^2-6p_0+1633 \equiv 0 \pmod{8} \)
\( (p_0-3)^2 \equiv -1633+9 \pmod{8} \)
\( (p_0-3)^2 \equiv 0 \pmod{8} \)
\( p_0 \equiv 7,3 \pmod{8} \)

第3步
假設\( q_0 \)是q的後3 bits
\( p_0 \cdot q_0 \equiv 1633 \pmod{8} \)
(1)當\( p_0 \equiv 7 \pmod{8} \)時
\( 7 \cdot q_0 \equiv 1633 \pmod{8} \)，得\( q_0 \equiv 7 \pmod{8} \)
(2)當\( p_0 \equiv 3 \pmod{8} \)時
\( 3 \cdot q_0 \equiv 1633 \pmod{8} \)，得\( q_0 \equiv 3 \pmod{8} \)

第4步
(1)當\( p_0 \equiv 7 \pmod{8} \)，\( q_0 \equiv 7 \pmod{8} \)時
假設\( p=8x+7 \)，\( q=8y+7 \)，x,y為整數
代入\( n=pq \)得\( (8x+7)(8y+7)=1633 \)
找到\( x=2 \)，\( y=8 \)符合上式
\( p=8 \cdot 2+7=23 \)，\( q=8 \cdot 8+7=71 \)
(2)當\( p_0 \equiv 3 \pmod{8} \)，\( q_0 \equiv 3 \pmod{8} \)時
假設\( p=8x+3 \)，\( q=8y+3 \)，x,y為整數
代入\( n=pq \)得\( (8x+3)(8y+3)=1633 \)
找不到x,y符合上式

第5步
\( \phi(n)=(p-1)(q-1)=1540 \)
\( e \cdot d \equiv 1 \pmod{\phi(n)} \)
\( d=67 \)
將n轉成二進位\( n=(11001100001)_2 \)，長度\( m=11 \)
將d轉成二進位\( d=(1000011)_2 \)後\( \displaystyle \lceil\; \frac{m}{4}\rceil\;=3 \)位的確是\( (011)_2 \)

---

作者: bugmens    時間: 2013-2-24 10:25

3.使用RSA時的注意事項－不可以使用共同的模n

已知一對加/解密金鑰為\( e_1,d_1 \)，和另一組加密金鑰\( e_2 \)，在不分解n的情況下，可求出密鑰\( d_2 \)。
1.計算\( e_1\times d_1-1 \)和\( e_2 \)的最大公因數g。
2.求出\( \displaystyle f=\frac{e_1\times d_1-1}{g} \)。
3.利用歐幾里德演算法，找出整數\( a,b \)，滿足\( a\times f+b\times e_2=1 \)。
所求的b值和\( d_2 \)在\( \pmod{\phi(n)} \)下同餘
[證明]
已知私鑰\( d_1 \)滿足\( d_1=e_1^{-1}\pmod{\phi(n)} \)，可得\( d_1\times e_1-1=k\times \phi(n) \)，\( k \in N \)

已知公鑰\( e_2 \)滿足\( GCD(e_2,\phi(n))=1 \)，若\( GCD(e_2,k\times \phi(n))=g \)，則g被k整除。
(因為\( e_2 \)和\( \phi(n) \)互質，所以最大公因數g不可能整除\( \phi(n) \)，推得g被k整除)

\( \displaystyle f=\frac{e_1 \times d_1-1}{g}=\frac{k \times \phi(n)}{g}=\frac{k}{g}\phi(n) \)
因為g可被k整除，所以f是個正整數。

利用歐幾里德演算法，求出整數a,b滿足\( a \times f+b \times e_2=1 \)
此時\( \displaystyle b\times e_2\equiv 1-a \times f \equiv 1-a \times \frac{k}{g}\phi(n)\equiv 1 \pmod{\phi(n)} \)
私鑰\( d_2 \equiv b \pmod{\phi(n)} \)

例子取自RSA wiki(http://en.wikipedia.org/wiki/RSA_(algorithm))


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

已知一對加/解密金鑰e1,d1，和另一組加密金鑰e2
(%i2)
e1:19;
d1:2299;
e2:133;
(%o2)　19
(%o3)　2299
(%o4)　133

計算e1*d1-1和e2的最大公因數g
(%i5)　g:gcd(e1*d1-1,e2);
(%o5)　7

求出f=(e1*d1-1)/g
(%i6)　f: (e1*d1-1)/g;
(%o6)　6240

利用歐幾里德演算法，找出整數a,b，滿足a*f+b*e2=1
(%i7)　[a,b,c]:gcdex(f,e2);
(%o7)　[12,-563,1]

(%i8)　b;
(%o8)　-563

雖然得到的b值是負的，但仍可以用來解密\( m=c^b \pmod{n} \)
此時b和d2在\( \pmod{\phi(n)} \)下是同餘的
\( b=-563 \)，\( d2=2557 \)，\( \phi(n)=3120 \)



參考資料
J. M. DeLaurentis, A further weakness in the common modulus protocol for the RSA  ryptoalgorithm, Cryptologia 8 (1984), no. 3, 253–259.
http://www.tandfonline.com/doi/abs/10.1080/0161-118491859060
需要大學的IP才能下載

---

作者: bugmens    時間: 2013-3-9 09:54

4.使用RSA時的注意事項－短明文要加上補綴(padding)

若明文太小的話攻擊者就可以窮舉\( m_1,m_2 \)，並檢查\( (m_1 \cdot m_2)^e \pmod{n} \)是否等於密文c，假若相等的話那原訊息為\( m=m_1 \cdot m_2 \)。
要避免短明文攻擊，就要加上適當的補綴(padding)來擴大明文m的值，這個協定稱為Optimal Asymmetric Encryption Padding(OAEP)

補充資料
http://en.wikipedia.org/wiki/Opt ... _encryption_padding
10.2.6  最优非对称加密填充(OAEP)
h ttp://book.51cto.com/art/200901/105944.htm　連結已失效
範例
ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/oaep-int.txt




使用RSA-129的公鑰n和e
(%i1)
n:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
e:9007;
(%o1)　114381625757888867669235779976[69 digits]058989075147599290026879543541
(%o2)　9007

密文c
(%i3)　c:68193531754636943624909394435722333362077664424688398841028357013967155604558046305915102664104100299314379759233825500764020031;
(%o3)　681935317546369436249093944357[68 digits]299314379759233825500764020031

已知原訊息m很小，可以窮舉m1,m2來找出m。(執行時間需要三分鐘)
(%i4)
for m1:1 thru 1000 do
  (for m2:m1 thru 1000 do
     (c1:power_mod(m1,e,n),
      c2:power_mod(m2,e,n),
      if mod(c1*c2,n)=c then
        (print("m=",m1,"*",m2,"=",m1*m2)
        )
     )
  );
m=192 * 643 = 123456
(%o4)　done

---

作者: bugmens    時間: 2013-4-5 16:54

5.使用RSA時的注意事項－避免明文為n的不動點

有些明文m在計算次方時是有規律的，此時m就稱為不動點。而這些不動點無法將明文隱藏起來，所以使用時要避免明文為n的不動點。例如\( m=0,1,n-1 \)都是顯然易知的不動點，但另外還有6個和n的因數有關的明文也會是不動點。
\( 0^e \equiv 0 \pmod{n} \)　，　\( 1^e \equiv 1 \pmod{n} \)　，　\( (n-1)^e \equiv (-1)^e \pmod{n} \)

其中6個不動點可以從\( x^2 \equiv 1,x,n-x \pmod{n} \)得到
(1)
\( x^2 \equiv 1 \pmod{n} \)
\( x^2-1 \equiv 0 \pmod{n} \)
\( (x+1)(x-1) \equiv 0 \pmod{n} \)
又\( n=pq \)
假設\( x+1=2ap \)，\( x-1=2bq \)，此時不動點為\( x=2ap-1=2bq+1 \)
假設\( x+1=-2bq \)，\( x-1=-2ap \)，此時不動點為\( x=n-2bq-1=n-2ap+1 \)
其中a,b為正整數且符合\( ap-bq=1 \)

(2)
\( x^2 \equiv x \pmod{n} \)
\( x^2-x \equiv 0 \pmod{n} \)
\( x(x-1) \equiv 0 \pmod{n} \)
又\( n=pq \)
假設\( x=ap \)，\( x-1=bq \)，此時不動點為\( x=ap=bq+1 \)
假設\( x=-bq \)，\( x-1=-ap \)，此時不動點為\( x=n-bq=n-ap+1 \)
其中a,b為正整數且符合\( ap-bq=1 \)

(3)
\( x^2 \equiv n-x \pmod{n} \)
\( x^2+x \equiv 0 \pmod{n} \)
\( x(x+1) \equiv 0 \pmod{n} \)
假設\( x=bq \)，\( x+1=ap \)，此時不動點為\( x=bq=ap-1 \)
假設\( x=-ap \)，\( x+1=-bq \)，此時不動點為\( x=n-ap=n-bq-1 \)
其中a,b為正整數且符合\( ap-bq=1 \)

而這6個不動點還可以配成3組
(1)已知x為不動點且\( x^2 \equiv 1\pmod{n} \)，則\( n-x \)亦為不動點
\( (n-x)^2 \equiv n^2-2nx+x^2 \equiv x^2 \equiv 1 \pmod{n} \)

(2)已知x為不動點且\( x^2 \equiv x \pmod{n} \)，則\( x-1 \)亦為不動點
\( (x-1)^2 \equiv x^2-2x+1 \equiv x-2x+1 \equiv -(x-1) \pmod{n} \)

(3)已知x為不動點且\( x^2 \equiv n-x \pmod{n} \)，則\( x+1 \)亦為不動點
\( (x+1)^2 \equiv x^2+2x+1 \equiv n-x+2x+1 \equiv x+1 \pmod{n} \)


例子取自RSA wiki(http://en.wikipedia.org/wiki/RSA_(algorithm)#A_working_example)
以\( p=61,q=53,n=3233 \)為例，用輾轉相除法計算出符合\( ap-bq=1 \)的正整數\( a=20,b=23 \)。
\( n=3233 \)的不動點為\( 2439,794,1220,2014,1219,2013 \)再加\( 0,1,3232 \)共有9個
\( x=2ap-1=2bq+1=2439 \)
\( x=n-2bq-1=n-2ap+1=794 \)
\( x=ap=bq+1=1220 \)
\( x=n-bq=n-ap+1=2014 \)
\( x=bq=ap-1=1219 \)
\( x=n-ap=n-bq-1=2013 \)

這6個不動點還可以配成三組
(1)已知x為不動點且\( x^2 \equiv 1 \pmod{n} \)，\( n-x \)亦為不動點
\( 2439^2 \equiv 1 \pmod{n} \)，\(794^2 \equiv 1 \pmod{n} \)
(2)已知x為不動點且\( x^2 \equiv x \pmod{n} \)，\( x-1 \)亦為不動點
\( 1220^2 \equiv 1220 \pmod{n} \)，\( 1219^2 \equiv -1219 \pmod{n} \)
(3)已知x為不動點且\( x^2 \equiv n-x \pmod{n} \)，\( x+1 \)亦為不動點
\( 2013^2 \equiv -2013 \pmod{n} \)，\( 2014^2 \equiv 2014 \pmod{n} \)

已知n的因數p,q
(%i1)
p:61;
q:53;
n:p*q;
(%o1)　61
(%o2)　53
(%o3)　3233

用輾轉相除法求出ap-bq=1的a,b
再將b換成正整數
(%i4)
[a,b,k]:gcdex(p,q);
b:-b;
(%o4)　\( [20,-23,1] \)
(%o5)　23

n的6個不動點
(%i6)
2*a*p-1;
2*b*q+1;
(%o6)　2439
(%o7)　2439

(%i8)
n-2*b*q-1;
n-2*a*p+1;
(%o8)　794
(%o9)　794

(%i10)
a*p;
b*q+1;
(%o10)　1220
(%o11)　1220

(%i12)
n-b*q;
n-a*p+1;
(%o12)　2014
(%o13)　2014

(%i14)
b*q;
a*p-1;
(%o14)　1219
(%o15)　1219

(%i16)
n-a*p;
n-b*q-1;
(%o16)　2013
(%o17)　2013

計算6個不動點的1到10次方，發現結果有規律
(%i18)
create_list(power_mod(%o6,e,n),e,1,10);
create_list(power_mod(%o8,e,n),e,1,10);
create_list(power_mod(%o10,e,n),e,1,10);
create_list(power_mod(%o12,e,n),e,1,10);
create_list(power_mod(%o14,e,n),e,1,10);
create_list(power_mod(%o16,e,n),e,1,10);
(%o18)　\( [2439,1,2439,1,2439,1,2439,1,2439,1] \)
(%o19)　\( [794,1,794,1,794,1,794,1,794,1] \)
(%o20)　\( [1220,1220,1220,1220,1220,1220,1220,1220,1220,1220] \)
(%o21)　\( [2014,2014,2014,2014,2014,2014,2014,2014,2014,2014] \)
(%o22)　\( [1219,2014,1219,2014,1219,2014,1219,2014,1219,2014] \)
(%o23)　\( [2013,1220,2013,1220,2013,1220,2013,1220,2013,1220] \)

參考資料
張卜仁，「找尋公開金鑰密碼系統RSA不動點之方法」，東海大學資訊工程與科學系碩士論文，民國九十三年。
連結已失效h ttp://thuir.thu.edu.tw/retrieve/7620/092THU00392011-001.pdf
Blakely, R.G., and Borosh, I., "Rivest-Shamir-Adleman Public Key Cryptosystems Do Not Always Conceal Messages", Computers & Mathematics with Applications, 5 (3), 1979.
http://www.sciencedirect.com/science/article/pii/0898122179900397

---

作者: bugmens    時間: 2013-6-4 22:07

6.使用RSA時的注意事項－避免公鑰e為n的不動點

有些公鑰e是無法將明文m隱藏起來的( \( m^e \equiv m \pmod{n} \) )，也就是m經過e次方後的結果仍是自己，作者將這類公鑰e稱為degenerate keys。

以論文所提到的例子舉例\( p=5,q=13 \Rightarrow n=pq=65 \)，取公鑰\( e=13 \)。
無論明文\( m=4,5,6,64 \)或是其他的值經過e次方後還是自己，無法將m隱藏起來
\( 4^{13} \pmod{65}=4 \)，
\( 5^{13} \pmod{65}=5 \)，
\( 6^{13} \pmod{65}=6 \)，
\( 64^{13} \pmod{65}=64 \)。

此時e滿足\( lcm(p-1,q-1)+1=lcm(4,12)+1=13 \)，另外\( e=13,25,37,\ldots \)也都是degenerate keys
所以當\( e=k \times lcm(p-1,q-1)+1 \)，\( k \in N \)時，e是degenerate key
[證明]
由費馬小定理可知，若p是質數，則\( m^{p-1} \equiv 1 \pmod{p} \)
　　　　　　　　　若q是質數，則\( m^{q-1} \equiv 1 \pmod{q} \)
可得\( m^{lcm(p-1,q-1)} \equiv 1 \pmod{pq} \)
\( m^{k \times lcm(p-1,q-1)} \equiv 1 \pmod{pq} \)，\( k \in N \)
\( m^{k \times lcm(p-1,q-1)+1} \equiv m \pmod{n} \)
得到\( e=k \times lcm(p-1,q-1)+1 \)，\( k \in N \)
滿足\( m^e \equiv m \pmod{n} \)

而公鑰e要滿足\( 1<e<\phi(n) \)，且\( gcd(e,\phi(n))=1 \)
所以\( k \times lcm(p-1,q-1)+1<\phi(n) \)
degenerate keys的個數有\( \displaystyle N=\Bigg\lfloor\; \frac{\phi(n)}{lcm(p-1,q-1)+1} \Bigg\rfloor\;=\frac{\phi(n)}{lcm(p-1,q-1)}-1 \)個
以剛才的例子\( \displaystyle N=\frac{(5-1)(13-1)}{lcm(5-1,13-1)}-1=\frac{48}{12}-1=3 \)個
分別是\( e=13,25,37 \)

公鑰n=65，e=13
(%i1)
n:65;
e:13;
(%o1)　65
(%o2)　13

隨機的明文m
(%i3)　m:random(n);
(%o3)　4

計算m^e (mod n)，結果還是自己
(%i4)　power_mod(m,e,n);
(%o4)　4

只是在實務上公鑰e常取65537，而這個數不僅是個質數而且在計算次方時有比較快速的方法，所以這個公鑰e不會是任何n的degenerate key。

參考資料
Bergmann, Seth D. ACM SIGCSE Bulletin vol. 41 issue 2 June 25, 2009. p. 95-98
連結已失效h ttp://www.rowan.edu/colleges/csm/departments/computerscience/research/reports/tr2010-2.pdf

---

作者: bugmens    時間: 2014-3-30 11:04

在實務上RSA需要計算高次方的同餘運算(加密\( c=m^e \pmod{n} \)、解密\( m=c^d \pmod{n} \))，假如一次只乘一次方的話很耗費時間，因此實作上都會採用平方-相乘的方式來簡化計算。

例如要計算\( c^{19} \)，將19以二進位表示\( 19=(10011)_2 \)，從最高位開始
\( \displaystyle \matrix{
(1)_2 & 　 & c^1 \cr
(10)_2 & 平方 & c^2 \cr
(100)_2 & 平方 & c^4 \cr
(1000)_2 & 平方 & c^8 \cr
(1001)_2 & 相乘 & c^9 \cr
(10010)_2 & 平方 & c^{18} \cr
(10011)_2 & 相乘 & c^{19}} \)

原本需要18次乘法運算，現在只剩下6次乘法運算

另一個例子
計算\( c^{23} \)，將23以二進位表示\( 23=(10111)_2 \)，從最高位開始
\( \displaystyle \matrix{
(1)_2 & 　 & c^1 \cr
(10)_2 & 平方 & c^2 \cr
(100)_2 & 平方 & c^4 \cr
(101)_2 & 相乘 & c^5 \cr
(1010)_2 & 平方 & c^{10} \cr
(1011)_2 & 相乘 & c^{11} \cr
(10110)_2 & 平方 & c^{22} \cr
(10111)_2 & 相乘 & c^{23}} \)

原本需要22次乘法運算，現在只剩下7次乘法運算


再加上同餘運算，要計算\( mod(c^d,n) \)寫成演算法為
Square_Multiply(c,d,n)
{
\( x=c; \)
for(\( i=n-2;i \ge 0;i-- \) )
　{\( x=mod(x^2,n); \)
　if (\( d_i \)==1) then
　　\( x=mod(x \cdot c,n); \)
　}
return x
}
其中次方d以二進位表示\( d=(d_{n-1}d_{n-2}d_{n-3} \ldots d_1 d_0)_2 \)，\( d_i=0 or 1 \)，\( d_{n-1}=1 \)


要先載入bitwise.lisp才能使用bit_length,bit_onep指令
(%i1)　load("bitwise.lisp");
(%o1)　"C:/PROGRA~2/MAXIMA~1.2/share/maxima/5.31.2/share/contrib/bitwise/bitwise.lisp"

平方-相乘副程式
(%i2)　
Square_Multiply(c,d,n):=block
  (x:c,
   for i:bit_length(d)-2 thru 0 step -1 do
     (x:mod(x^2,n),
      if bit_onep(d,i)=true then
        (x:mod(x*c,n)
        )
     ),
   x
  )$

給定c,d,n值
(%i3)
c:3;
d:19;
n:17;
(%o3)　3
(%o4)　19
(%o5)　17

計算mod(c^d,n)的結果
(%i6)　Square_Multiply(c,d,n);
(%o6)　10

就和maxima內建指令power_mod算出來的相同
(%i7)　power_mod(c,d,n);
(%o7)　10


附註：
maxima的power_mod也是採用相同的方法，在C:\Program Files (x86)\Maxima-5.31.2\share\maxima\5.31.2\src\ifactor.lisp可以找到用lisp寫的原始碼
(defun power-mod (b n m)
  (if (zerop n)
      (mod 1 m)
      (do ((res 1))
   (())
(when (logbitp 0 n)
   (setq res (mod (* res b) m))
   (when (= 1 n) (return res)))
(setq n (ash n -1))
(setq b (mod (* b b) m)))))

---

作者: bugmens    時間: 2014-4-4 17:43

在1996年Paul Kocher提出一種全新思維的攻擊方式，稱為時序攻擊(Timing Attack)，而這個新的攻擊方式，開創了側面管道攻擊(Side Channel Attack)的先河。時序攻擊主要針對在相同的密碼系統、相同金鑰在輸入不同的資料時，會有不同的處理時間。而處理時間的多寡就足以洩漏密鑰的部分位元甚至是所有的位元。

103.4.12補充
h ttp://blog.conversionconference.com/wp-content/uploads/2013/06/onlinedialogue1.jpg　連結已失效
這張圖非常適用用來形容側面管道攻擊，也就是攻擊者或許無法從正面攻破，但藉由實作時所造成的漏洞，改從側面的管道攻擊。

這裡我採用Mark Stamp所寫的Information Security : Principles and Practice書中第6.6節，一種簡化的時序攻擊，讓各位能掌握時序攻擊的精神。

請各位再回顧前一篇平方-相乘的演算法
Square_Multiply(c,d,n)
{
\( x=c; \)
for(\( i=n-2;i \ge 0;i-- \) )
　{\( x=MyMod(x^2,n); \)
　if (\( d_i \)==1) then
　　\( x=MyMod(x \cdot m,n); \)
　}
return x
}
次方d以二進位表示\( d=(d_{n-1}d_{n-2}d_{n-3} \ldots d_1 d_0)_2 \)，\( d_i=0 or 1 \)，\( d_{n-1}=1 \)

其中同餘運算MyMod(x,n)若以下面的方式實作的話，當x大於n時需要額外的運算，當x小於n時不需要額外的運算，假如我們能仔細挑選輸入的密文的話，那解密時從運算時間的差異就可以知道目前密鑰的位元到底是0還是1。
MyMod(x,n)
{
if \( x \ge n \) then
  \( x=mod(x,n) \)
return x
}

接下來的問題是要怎麼挑選需要額外運算的密文及不需要額外運算的密文呢？Mark Stamp在書中挑了兩個值y,z，其中\( y^3<n \)且\( z^2<n<z^3 \)，我們來看這兩個值在執行程式時會有什麼差異？

	\( c=y \)代入，其中\( y^3<n \)	\( c=z \)代入，其中\( z^2<n<z^3 \)
Square_Multiply(c,d,n) { \( x=c; \) for(\( i=n-2;i \ge 0;i-- \) ) 　{\( x=MyMod(x^2,n); \) 　if (\( d_i \)==1) then 　　\( x=MyMod(x \cdot c,n); \) 　} return x }	\( x=y \) \( x=y^2 \)這在MyMod沒有額外的運算 若\( d_i=1 \) \( x=y^3 \)這在MyMod沒有額外的運算	\( x=z \) \( x=z^2 \)這在MyMod沒有額外的運算 若\( d_i=1 \) \( x=z^3 \)這在MyMod有額外的運算

從上面的表格可知當\( d_i=1 \)時\( y^3 \)和\( z^3 \)運算時間明顯不同(\( y^3<n<z^3 \))
　　　　　　　　當\( d_i=0 \)時\( y^2 \)和\( z^2 \)運算時間幾乎相同(\( y^2,z^2<n \))
實作時會計算非常多的y和z值，讓運算時間的差異突顯出來。



要先載入bitwise.lisp才能使用bit_length,bit_onep指令
(%i1)　load("bitwise.lisp");
(%o1)　"C:/PROGRA~2/MAXIMA~1.2/share/maxima/5.31.2/share/contrib/bitwise/bitwise.lisp"

解密副程式,其中密鑰\( d=(1011)_2=11 \)藏在程式碼內並沒有公開
(%i2)
Decrytion(c,n):=block
  (d:11,
   x:c,
   for i:bit_length(d)-2 thru 0 step -1 do
     (x:MyMod(x^2,n),
      if bit_onep(d,i)=true then
        (x:MyMod(x*c,n)
        )
     ),
   x
  )$

計算同餘的副程式
(%i3)
MyMod(x,n):=block
  (if x>=n then
     x:mod(x,n),
   return(x)
  )$

使用RSA-129的公鑰n
(%i4)　n:114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541;
(%o4)　114381625757888867669235779976[69 digits]058989075147599290026879543541

已知一組明文m密文c
(%i5)
m:1478917592175622858989156344511152884894894864123;
c:102538809613607680612410977953782245367747072436413651092913061790220811932683669849208723086005918228769758114101739338725029103;
(%o5)　1478917592175622858989156344511152884894894864123
(%o6)　102538809613607680612410977953[69 digits]228769758114101739338725029103

已知密鑰\( d_{n-1}=1 \),這時\( d=(1???)_2=1 \)
(%i7)　d:1;
(%o7)　1

各有一萬筆密文y,z要解密,其中\( y^3<n \)、\( z^2<n<z^3 \)
若執行時間沒有很明顯的差異代表\( d_{n-2}=0 \)
　　　　　　有　　　　　　　　\( d_{n-2}=1 \)
(%i8)
Y:create_list(Decrytion(inrt(n,3)-i,n),i,1,10000)$
time(%);
Z:create_list(Decrytion(inrt(n,2)-i,n),i,1,10000)$
time(%);
(%o9)　[4.68]
(%o10)　[4.51]

兩個執行時間差異不大,所以\( d_{n-2}=0 \)，這時\( d=(10???)_2=2 \)
(%i12)　d:2;
(%o12)　2

計算\( c^d \pmod{n} \)是否能解密,失敗代表這還不是完整的密鑰
(%i13)　is(power_mod(c,d,n)=m);
(%o13)　false

再找一萬筆密文y,z來解密,其中\( y^5<n \)、\( z^4<n<z^5 \)
若執行時間沒有很明顯的差異代表\( d_{n-3}=0 \)
　　　　　　有　　　　　　　　\( d_{n-3}=1 \)
(%i14)
Y:create_list(Decrytion(inrt(n,5)-i,n),i,1,10000)$
time(%);
Z:create_list(Decrytion(inrt(n,4)-i,n),i,1,10000)$
time(%);
(%o15)　[2.88]
(%o17)　[3.61]

兩個執行時間差異很大,所以\( d_{n-3}=1 \),這時\( d=(101???)_2=5 \)
(%i18)　d:5;
(%o18)　5

計算\( c^d \pmod{n} \)是否能解密,失敗代表這還不是完整的密鑰
(%i19)　is(power_mod(c,d,n)=m);
(%o19)　false

再找一萬筆密文y,z來解密,其中\( z^{11}<n \)、\( z^{10}<n<z^{11} \)
若執行時間沒有很明顯的差異代表\( d_{n-4}=0 \)
　　　　　　有　　　　　　　　\( d_{n-4}=1 \)
(%i20)
Y:create_list(Decrytion(inrt(n,11)-i,n),i,1,10000)$
time(%);
Z:create_list(Decrytion(inrt(n,10)-i,n),i,1,10000)$
time(%);
(%o21)　[1.1]
(%o23)　[1.94]

兩個執行時間差異很大,所以\( d_{n-4}=1 \),這時\( d=(1011???)_2=11 \)
(%i24)　d:11;
(%o24)　11

計算\( c^d \pmod{n} \)是否能解密,成功代表找到完整的密鑰了
(%i25)　is(power_mod(c,d,n)=m);
(%o25)　true

---

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0