2.RSA算法

RSA公鑰密碼算法是以發(fā)明者R.Rivest、A.Shamir和L.Adleman的名字命名的，它的安全性是基于整數(shù)因子分解問題的困難性。RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，易于理解和操作；是被研究得最廣泛的公鑰算法，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受；也被普遍認(rèn)為是目前最優(yōu)秀、應(yīng)用最廣泛的公鑰算法之一。

1) RSA算法描述

選取兩個(gè)大素?cái)?shù)p和q，計(jì)算其乘積：n= pq和歐拉函數(shù)巾(n)=（p一1）(q-l)；然后隨機(jī)選取加密密鑰e，l<e<中(n)，滿足e和( p-1)(q-l‘)互素。最后用歐幾里德擴(kuò)展算法計(jì)算解密密鑰d，以滿足ed=l（mocl（p-l）(q-l))，即

d= e-1 mod（（p-l） （q-l）） e和n是公鑰，d和n是私鑰。

RSA算法對(duì)明文以分組為單位進(jìn)行加密，每個(gè)分組的二進(jìn)制均小于n。即分組的大小必須小于或等于1092（朋）位；在實(shí)際應(yīng)用中，分組的大小是啦，其中2k<n≤2.k+1。對(duì)明文分組M，加密過程如下C=lVfmodn：。對(duì)密文分曉亂，解密過程如下：M_Cdmodn。