沒有e沒法求d p和q也沒給 我郁悶
先說歐幾里得算法,這個(gè)是一個(gè)函數(shù),求的話累死.
歐幾里得算法是求最大公約數(shù)的,求逆元用擴(kuò)展的歐幾里得算法
原理：
如果gcd(a,b)=d,則存在m,n,使得d = ma + nb,稱呼這種關(guān)系為a、b組合整數(shù)d,m,n稱為組合系數(shù).當(dāng)d=1時(shí),有 ma + nb = 1 ,此時(shí)可以看出m是a模b的乘法逆元,n是b模a的乘法逆元.
int gcd(int a,int b ,int&； ar,int &； br)
{
int x1,x2,x3；
int y1,y2,y3；
int t1,t2,t3；
if(0 == a)
{//有一個(gè)數(shù)為0,就不存在乘法逆元
ar = 0；
br = 0 ；
return b；
}
if(0 == b)
{
ar = 0；
br = 0 ；
return a；
}
x1 = 1；x2 = 0；x3 = a；
y1 = 0；y2 = 1；y3 = b；
int k；
for( t3 = x3 % y3 ； t3 != 0 ； t3 = x3 % y3)
{
k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
if( y3 == 1)
{ //有乘法逆元
ar = y2；
br = x1；
return 1；
}
else
{ //公約數(shù)不為1,無乘法逆元.這個(gè)是存在逆元的充要條件
ar = 0；
br = 0；
return y3；
}
}
核心是
for( t3 = x3 % y3 ； t3 != 0 ； t3 = x3 % y3)
{
k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
一共有三行
x1 ,x2 ,x3
y1 ,y2 ,y3
t1 ,t2 ,t3
每次循環(huán)第三行都是算出來的 然后 把第一行y的值放到x t的值放到y(tǒng)
這三行都滿足一個(gè)共同的性質(zhì)
第一個(gè)數(shù)*a+第二個(gè)數(shù)*b=第三個(gè)數(shù)
比如x1*a+x2*b=x3
每次循環(huán)問題都會(huì)簡(jiǎn)化,距離結(jié)果更進(jìn)
直到
當(dāng)最終t3迭代計(jì)算到1時(shí),有t1× a + t2 × b = 1,顯然,t1是a模b的乘法逆元,t2是b模a的乘法逆元.
生成p,q兩個(gè)素?cái)?shù),產(chǎn)生方法就是隨機(jī)產(chǎn)生一個(gè)數(shù),然后用素性檢驗(yàn)算法判斷是不是素?cái)?shù),如果不是再隨機(jī)產(chǎn)生一個(gè)判斷.關(guān)于素性經(jīng)驗(yàn),這個(gè)問題很大,是本數(shù)論書都有,這里沒法展開講.
比如p=3,q=11
生成n=p*q=33
生成n的歐拉函數(shù) N=(p-1)*(q-1)=20
選取公鑰e=3 然后計(jì)算d
e*d=1（mod N） e和d是關(guān)于模N的互為逆元的關(guān)系,用擴(kuò)展的歐幾里得算法
得出來d=7 也就是說3*7=1（mod 20）
加密用e M的每個(gè)字母轉(zhuǎn)換成ASCII碼 設(shè)明文字母為m 密文為c
c=m的e次方（mod n） 也就說c=m的三次方（mod 33）
m=c的d次方（mod n） 也就是說m=c的7次方（mod 33）
百度知道沒有公式編輯器讓我很痛苦
注意別把N=（p-1）*（q-1）和n=p*q搞混了 N用于求d n用于加密解密
RSA我熟的很 還做過一個(gè)ppt 實(shí)現(xiàn)還有簡(jiǎn)單的一些弱點(diǎn) 本來想發(fā)給樓主 但是貌似我換了7-zip后把我以前的壓縮包打不開了 也可能損壞了