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
