RSA的加密系統

(由Ronald Rivest,  Adi Shamir,  Len Adelman 所提出)

(1) 將文字編碼，如：

文字	對應的數	文字	對應的數	文字	對應的數	文字	對應的數
A	01	H	08	O	15	V	22
B	02	I	09	P	16	W	23
C	03	J	10	Q	17	X	24
D	04	K	11	R	18	Y	25
E	05	L	12	S	19	Z	26
F	06	M	13	T	20	空白	27
G	07	N	14	U	21

(2) 選取兩個不同且較大的奇質數p,q，令m=pq。在取正整數e，使得
(e,φ(m))=1。將(e,m)作為共同的加密鑰匙。如：3127=53*59，
φ(3127)=3016，(11,3016)=1。取(11,3127) 為共同的加密鑰匙。

(3) 將原文的文字轉為對應的兩位數且把文字間的間隔用27補上，並將這些數分割成最大的偶數長度區塊的格式，使得每區塊的數字串 (看作一個正整數)都比m小。如果最後區塊的數字串比所需的數字少，則空的數字，用27填補，以使數字串的長度足夠。如：
原文為「I AM HAVING FUN NOW」翻譯成對應的數為「0927011327 0801220914072706211427141523」，將上述數字分割成長度為4的區塊，即「0927,0113,2708,0122,0914,0727,0621,1427,1415,2327」，其對應的文字變為「I ,AM, H,AV,IN,G ,FU,N ,NO,W 」且每個區塊的數都比3127小。

(4) 將每一區塊的數P，透過
      P^e≡C (mod m),0≦C 得到一個新的區塊C。如：
   0927¹¹≡2982 (mod 3127), 0113¹¹≡0570 (mod 3127)
   2708¹¹≡2617 (mod 3127), 0122¹¹≡3121 (mod 3127)
   0914¹¹≡1659 (mod 3127), 0727¹¹≡1382 (mod 3127)
   0621¹¹≡0269 (mod 3127), 1427¹¹≡2024 (mod 3127)
   1415¹¹≡0589 (mod 3127), 2327¹¹≡0245 (mod 3127)
加密後的數碼為「2982,0570,2617,3121,1659,1382,0269,2024,0589,0245」。

(5) (e,m)是共同的加密鑰匙，(d,m)是私自的解密鑰匙，其中d是e模φ(m)的反元素。將加密後的區塊的數C，透過
      C^d≡P (mod m),0≦P 來得到新的區塊數字串P。並將P還原回原來的文字，且重新組合成有意義的文句。如：
11模φ(3127)的反元素為1371，因此
     2982¹³⁷¹≡0927 (mod 3127), 0570¹³⁷¹≡0113 (mod 3127)
     2617¹³⁷¹≡2708 (mod 3127), 3121¹³⁷¹≡0122 (mod 3127)
     1659¹³⁷¹≡0914 (mod 3127), 1382¹³⁷¹≡0727 (mod 3127)
     0269¹³⁷¹≡0621 (mod 3127), 2024¹³⁷¹≡1427 (mod 3127)
     0589¹³⁷¹≡1415 (mod 3127), 0245¹³⁷¹≡2327 (mod 3127)
         
解密後的數字串為「0927,0113,2708,0122,0914,0727,0621,1427,1415,2327」，帶回相對應的文字為「I ,AM, H,AV,IN,G ,FU,N ,NO,W 」，再將逗號去掉變為有意義的文句，「I AM HAVING FUN NOW 」。

(6) 因為ed≡1 (mod φ(m))，所以存在k使得 ed=kφ(m)+1，
 當(P,m)=1，由尤拉定理(定理2.17)
     C^d≡(P^e)^d≡P^ed≡P^kφ(m)+1≡(P^φ(m))^kP≡P (mod m).
 如果(P,m)¹1，也能得到同樣結果C^d≡P (mod m)。

(7) 當給出共同的加密鑰匙(e,m)，要導出(d,m)不見得是容易的事，因為d是e模φ(m)的反元素，也就是當你要求得d須知道φ(m)，如果知道m的兩個大質數p,q，則φ(m)=φ(p)φ(q)=(p-1)(q-1)。如果只知道m，要將m作因數分解，而求出p,q，特別當p,q 大約是150位數時，m就有大約300位數，以今日的超級電腦每秒大約10⁹次運算，大約要花掉(4.9)*10¹²年。

RSA加密系統在MATHEMATICA上的操作        陳創義

*****************加密碼****************

*輸入(e,m)

In[1]:=

e=11;m=3127;

*計算每個區塊數字的長度a1

In[2]:=

a0=Length[IntegerDigits[m,10]];If[Mod[a0,2]==0&&m>28*10^(a0-2),a1=a0, If[Mod[a0,2]==1,a1=a0-1,a1=a0-2]]

Out[2]:=

4

*輸入英文字句，字與字的間隔用空白補上

In[3]:=

alpha="I  AM  HAVING  FUN  NOW"

Out[3]=

I  AM  HAVING  FUN  NOW

*將文字編碼

In[4]:=

a2=StringReplace[alpha,{"A"->"01","B"->"02","C"->"03","D"->"04",
"E"->"05","F"->"06","G"->"07","H"->"08","I"->"09","J"->"10",
"K"->"11","L"->"12","M"->"13","N"->"14","O"->"15","P"->"16",
"Q"->"17","R"->"18","S"->"19","T"->"20","U"->"21","V"->"22",
"W"->"23","X"->"24","Y"->"25","Z"->"26"," "->"27"}]

Out[4]=

09270113270801220914072706211427141523

*計算串列a2可分成a4區塊

In[5]:=

a3=StringLength[a2];If[Mod[a3,a1]==0,a4=Quotient[a3,a1],
Do[a2=StringJoin[a2,"27"],{i,1,(a1-Mod[a3,a1])/2}]; a4=Quotient[a3,a1]+1]

Out[5]=

10

*將上述編碼後的數字串列a2，分成每a1個數字一個串列

In[6]:=

p0[j_]:=StringTake[a2,{a1*(j-1)+1,a1*j}]

*將區塊的數字串列以完全形式表列

In[7]:=

FullForm[Table[p0[j],{j,1,a4}]]

Out[7]:=

List["0927","0113","2708","0122","0914","0727","0621","1427","1415",
"2327"]

*將上式輸出的完全形式複製到下一個輸入，並消去引號等，然後加上大刮號成為集合p1

In[8]:=

p1={0927,0113,2708,0122,0914,0727,0621,1427,1415,2327};

*將數字串列轉成數

In[9]:=

p[j_]:=p1[[j]]

*將e化成2進位，並取出等於1的位數，形成集合e3

In[10]:=

e1=IntegerDigits[e,2];e2=Length[e1];e3={};

Do[If[e1[[k]]==1,e3=Union[e3,{e2+1-k}],],{k,1,e2}]

*先計算p[j]^(2^i)模m的值

In[11]:=

b[j_][1]:=p[j];Do[b[j][i]=Mod[b[j][i-1]*b[j][i-1],m],{i,2,e2},
{j,1,a4}]

*將編碼的數碼加密

In[12]:=

c[j_]:=1;Do[c[j]=Mod[c[j]*b[j][e3[[k]]],m],{k,1,Length[e3]},{j,1,a4}];

Table[c[j],{j,1,a4}]

Out[12]=

{2982,570,2617,3121,1659,1382,269,2024,589,245}

 ******************解碼***************

*輸入(d,m)

In[1]:=

d=1371;m=3127;

*將d化成2進位，並取出等於1的位數

In[2]:=

d1=IntegerDigits[d,2];d2=Length[d1];d3={};

Do[If[d1[[k]]==1,d3=Union[d3,{d2+1-k}],],{k,1,d2}]

*輸入已經加密的訊息c0，並計算有多少個區塊c1

In[3]:=

c0={2982,0570,2617,3121,1659,1382,0269,2024,0589,0245};c1=Length[c0];

*計算每個區塊數字的長度a1

In[4]:=

a0=Length[IntegerDigits[m,10]];If[Mod[a0,2]==0&&m>28*10^(a0-2),a1=a0, If[Mod[a0,2]==1,a1=a0-1,a1=a0-2]];c2=a1/2

Out[4]:=

2

*定義每區塊的數

In[5]:=

cc[j_]:=c0[[j]]

*先計算cc[j]^(2^i)的值

In[6]:=

f[j_][1]:=cc[j];Do[f[j][i]=Mod[f[j][i-1]*f[j][i-1],m],{i,2,d2},
{j,1,c1}]

*解碼

In[7]:=

pp[j_]:=1;Do[pp[j]=Mod[pp[j]*f[j][d3[[k]]],m],{k,1,Length[d3]},
{j,1,c1}];

ppp=Table[IntegerDigits[pp[j],100],{j,1,c1}]

Out[7]=

{{9,27},{1,13},{27,8},{1,22},{9,14},{7,27},{6,21},{14,27},{14,15},
{23,27}}

*輸入數字與文字的對應關係

In[8]:=

h[1]="A";h[2]="B";h[3]="C";h[4]="D";h[5]="E";h[6]="F";h[7]="G";
h[8]="H";h[9]="I";h[10]="J";h[11]="K";h[12]="L";h[13]="M";
h[14]="N";h[15]="O";h[16]="P";h[17]="Q";h[18]="R";h[19]="S";
h[20]="T";h[21]="U";h[22]="V";h[23]="W";h[24]="X";h[25]="Y";
h[26]="Z";h[27]="  ";

*翻譯回文句

In[9]:=

ppp1=Table[h[ppp[[j]][[i]]],{j,1,c1},{i,1,c2}]

Out[9]=

{{I,  },{A,M},{  ,H},{A,V},{I,N},{G,  },{F,U},{N, },{N,O},{W,  }}

*將逗點刮號去掉

In[10]:=

ppp2="";Do[Do[ppp2=StringJoin[ppp2,ppp1[[i]][[j]]],{j,1,c2}],
{i,1,c1}];ppp2

Out[10]=

I  AM  HAVING  FUN  NOW