1.選擇d的注意事項－d要大於314n 

在許多應用場合中，我們常希望使用位元數較短的秘密金匙d，以降低解密或簽署的時間。例如在IC卡應用中，IC卡CPU的計算能力遠低於主電腦。長度較短的d可以減少IC卡的解密或簽署時間，而讓較複雜的加密或驗證運算(e長度較長)由快速的主電腦執行。
一個直接的問題產生了，解密金匙d的長度減少後是否會造成安全性的降低，使用RSA變得不安全呢？很明顯地，若d的長度太小，我們可利用已知明文m加密後得c=me(modn)，再直接猜測d，求出cd(modn)是否等於m。若是，則d為正確，否則繼續猜測d。若d的長度很小，則此猜測d之空間變小，猜對的機率相對地變大。因此，d的長度不能大小。1990年Wiener進一步提出一種針對d長度較小的攻擊法。他證明了若d的長度小於n長度的41時，利用連分數演算法，可以在多項式時間(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)　[051291465891177351465552794632312565579280869058117993]

從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)
        )
     )
  )$
51
x2−618x+90581=0
[x=379x=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



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

而RSA-129的d為1066986143685780110128，314n 為344721056058153441031，Wiener的連分數攻擊法失敗。
https://math.pro/db/viewthread.php?tid=1500&page=1#pid7305

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

1.使用RSA時的注意事項－不可以使用共同的模n(Common Modulus Protocol Failure)
若將相同明文m用不同的公鑰加密成密文後發送給兩位使用者

c1me1(modn)

c2me2(modn)

若被人擷取到這兩個密文，只要e1和e2是互質的話，就可以用輾轉相除法計算符合e1x+e2y=1的整數x和y。只要計算以下的式子就可以得到明文m。

c1xc2y(me1)x(me2)yme1x+e2ym(modn)

這個範例取自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

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

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

令n=pq為m bits，如果知道p的前4mbits或後4mbits，則能在多項式時間內將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的後4mbits，則在O(elog2e)時間內得到完整的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，部分私鑰d0=(011)2=3，試求出完整的私鑰d。
第1步
ed1(mod(n))
ed=1+k(n)，k為整數
ed=1+k(p−1)(q−1)
ed=1+k(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

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才能下載

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

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

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

在實務上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)))))

在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