【密码学】公钥密码

技术博客 (163) 2023-10-19 09:01:01

开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第5天,点击查看活动详情


相关原理

(一)DH协议                                                                 

     算法描述:用户A和用户B通过公开信道建立共同的密钥。  

     1.公用参数生成算法                                               

     这一步骤将为用户A和B生成公用的参数,执行如下操作:    

①选择大素数p。②令g为Zp*(2≤g≤p-2)的生成元。               

     2.协商密钥                                                        

     ①用户A随机选择数x(1≤x≤p-2),计算g^x modp,并将之发送给B。②用户B随机选择数y(1≤y≤p-2),计算g^y modp,并将之发送给A。③用户B收到g^x modp后,计算共享的密钥K=(g ^x)^y modp。④用户A收到g^y modp后,计算共享的密钥K=(g ^y)^x modp。

(二)RSA密码                                                           

     RSA加密算法是一种非对称加密算法,所谓非对称,就是指该算法加密和解密使用不同的密钥,即使用加密密钥进行加密、解密密钥进行解密。在RAS算法中,加密密钥(即公开密钥)PK是公开信息,而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的,由于无法计算出大数n的欧拉函数phi(N),所以不能根据PK计算出SK。也就是说,对极大整数做因数分解的难度决定了RSA算法的可靠性。理论上,只要其钥匙的长度n足够长,用RSA加密的信息实际上是不能被解破的。                                      

     RSA算法通常是先生成一对RSA密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开。为提高保密强度,RSA密钥至少为500位长,一般推荐使用1024位。这就使加密的计算量很大。为减少计算量,在传送信息时,常采用传统加密方法与公开密钥加密方法相结合的方式,即信息采用改进的DES或IDEA密钥加密,然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后,用不同的密钥解密并可核对信息摘要。                           

     RSA的加密过程可以使用一个通式来表达:密文=明文^EmodN   也就是说RSA加密是对明文的E次方后除以N后求余数的过程。从通式可知,只要知道E和N任何人都可以进行RSA加密了,所以说E、N是RSA加密的密钥,也就是说E和N的组合就是公钥。其中E必须满足两个条件:E是一个比1大比L小的数,E和L的最大公约数为1(L 是 p-1 和 q-1的最小公倍数)。                                                               

     RSA的解密过程可以使用一个通式来表达:明文=密文^DmodN   也就是说对密文进行D次方后除以N的余数就是明文,这就是RSA解密过程。知道D和N就能进行解密密文了,所以D和N的组合就是私钥。数D是由数E计算出来的,数D必须保证足够大。D、E和L之间必须满足:1 < D < L;E*D mod L = 1。                                  

(三)椭圆曲线密码                                           

     椭圆加密算法ECC,是基于椭圆曲线数学理论的一种非对称加密算法(公钥加密算法),与RSA相比可以使用更短的密钥实现与RSA相当或者更高的安全性。这里的椭圆曲线是指具有以下形式的三次方程:y^2+axy+by=x^3+cx^2+dx+e其中a、b、c、d、e是满足某些简单条件的实数。定义中包括一个称之为无穷远点的元素,记为O,椭圆曲线上的加法运算定义如下:如果其上的3个点位于同一直线上,那么它们的和为O,进一步可以定义如下运算律:①O为加法单位元,即对椭圆曲线上的任意一点P,有P+O=P。②设P1=(x,y)是椭圆曲线上一点,它的加法逆元定义为P2=-P1=(x,-y)。③设Q和R是椭圆曲线上x坐标不同的两点,Q+R的定义如下:画一条通过Q、R的直线,与椭圆曲线交于P1(这一交点是唯一的,除非所做的直线是Q点或R点的切线,此时分别取P1=Q和P1=R)。由Q+R+P1=O,得Q+R=-P1。④点Q的倍数定义如下:在Q点做椭圆曲线的一条切线,设切线与椭圆曲线交于点S,定义2Q=Q+Q=-S,类似的,可以定义3Q=Q+Q+Q,等等。以上定义的加法具有加法运算的一般性质,如交换律、结合律等。                                                 

    椭圆曲线密码体制:设P∈E(Fp),点O是P的倍数,即存在正整数x,使Q=dP,则椭圆曲线离散对数问题(ECPLP)是指由给定的P和Q确定出x。系统构造:选取基域Fp,椭圆曲线E,在E上选择阶为素数n的点P(xp,yp)。公开信息为:基域Fp、椭圆曲线E、点P及其阶n。密钥生成:用户 Alice随机选取整数d,1<d≤n—1,计算Q=dP,将点Q作为公开密钥,整数d作为秘密密钥。加密与解密:若要给 Alice发送秘密信息M,需执行以下步骤:①将明文M表示为域Fp中的一个元素m。②在[1,n-1]内随机选择整数k。③计算点(x1,y1)=kP。④计算点(x2,y2)=kQ,若x2=0,则重新选择k。⑤计算c=mx2.⑥将(x1,y1,c)发送给 Alice。Alice收到密文后,利用秘密密钥d,计算:d(x1,y1)= dkP= K(dP)=kQ=(x2,y2) 。                        

(四)ELGamal加密体制                                                                               

     EIGamal加密算法是一种非对称加密算法,可以应用在任意一个循环群(Cyclic Group)上。在群中有的运算求解很困难,这些运算通常与求解离散对数(Discrete Iogarithm)相关,求解的困难程度决定了算法的安全性。其中涉及以下几个重要的数学定义。                       

     公钥生成:①选取一个循环群G,且循环群G的阶数为q。②选择一个随机数x,l<x<q-1。③计算h=g ^xmodq。h和g,G,q就构成公钥;x是保密的,x与h,g,G,q一起构成密钥。                  

     公钥加密:①选取一个随机数y,1<y<q-1。②计算c1=g^ymodq③计算s=h^y=(g^x)^y=g^(x*y)mod q。④加密数字m得c2=m *smodq。c1、c2构成加密结果,交给私钥解密                               

     私钥解密:①通过c1计算得到s=c1^x=(g^y)^x=g(xy)mod q。②计算c2(s^-1)=(m*s)(s^-l)(md q),得到明文数字m。


实现过程

**(一)DH协议   **                                                              

     基于大整数库GMP,使用自带的函数实现随机数生成、大素数生成和求本原根,接着按照密钥协商顺序实现算法。

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第1张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第2张

(二)RSA密码                                                           

RSA加密算法的过程如下:

①取两个随机大素数p和q(保密)。

②计算公开的模数r=pq(公开)。

③计算秘密的欧拉函数φ(r)=(p-1)(q-1)(保密),两个素数p和q不再需要,为了不泄露最好丢弃。④随机选取整数e,满足 gcd(e,φ (r))=1(公开e,加密密钥)。

⑤计算d,满足de=1(modφ(r))(保密d,解密密钥,陷门信息)。

⑥将明文(其值的范围在0到r-1之间)按模为r自乘e次幂以完成加密操作,从而产生密文y(其值也在0到r-1范围内):y=x^e(mod r)

⑦将密文y按模为r自乘d次幂,完成解密操作:x=y^d (mod r)

int candp(int a, int n, int p){//数据处理函数,实现幂的取余运算                        

 int r=1;                                                                       

    n=n+1;                                                                       

    while(n!=1){                                                 

r=(r*a)%p;                                                 

n--;     }                                                                                                  

return r;                                                                                                  

}                                                                                                  

int fun(int x, int y){  //x与y的互素判断                                                                                                  

int t;                                                           

while(y){                                                           

t=x;                                                           

x=y;                                                           

y=t%y;  }                                                           

if(x==1)                                                           

return 0; //x与y互素时返回0                                                           

else                                                           

return 1; //x与y不互素时返回1                                                           

}                                                           

void main(){                                                           

int p,q,e,d,m,n,z,c,r;                                                           

    cout<<"①输入两个素数p,q: ";                                                           

cin>>p>>q;                                                           

n=p*q;                                                           

z=(p-1)*(q-1);                                                           

cout<<"②计算n=pq="<<n<<", z=(p-1)*(q-1)="<<z<<endl;                                                           

cout<<"③输入公钥e: ";                                                           

cin>>e;                                                           

if(e<1 || e>z || fun(e,z)){//选取e: e<n,e与z互素                                                           

printf("e不合要求,重新输人:");                                                            

scanf("%d", &e);                                                           

}                                                           

d=1;                                                           

while(((e*d)%z)!=1)//计算私钥d                                                           

d++;                                                                         

cout<<"④满足ed modz=1的d: "<<d<<endl;                                                           

cout<<"⑤公钥("<<n<<","<<e<<"),私钥("<<n<<","<<d<<")"<<endl;

cout<<"1.加密"<<endl<<"2.解密"<<endl<<"3.退出"<<endl;                                                           

    while(1){                                                           

printf("选择你执行的操作:");                                                           

cin>>r;                                                           

switch(r){                                                           

case 1:                                                           

printf("请输入明文m: ");                                                             

scanf("%d", &m);                                                           

c=candp(m, e, n);                                                           

printf("密文为%d\n",c);  //c=m^e modn                                                           

break;                                                           

case 2:                                                           

printf("请输入密文c: ");                                                            

scanf("%d", &c);                                                           

m=candp(c, d, n);                                                           

printf("明文为%d\n", m); //m=c^d modn                                                           

break;                                                           

case 3:                                                           

return;                                                           

default:                                                           

printf("输入错误,请重新输入:\n");                                                           

}  }  }

(三)椭圆曲线密码                                           

①用户A选定一条适合加密的椭圆曲线Ep(a,b)(如:y2=x3+ax+b),并取椭圆曲线上一点,作为基点G。

②用户A选择一个私有密钥k,并生成公开密钥K=kG。

③用户A将Ep(a,b)和点K,G传给用户B。

④用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M,并产生一个随机整数r(r<n)。

⑤用户B计算点C1=M+rK;C2=rG。

⑥用户B将C1、C2传给用户A。

⑦用户A接到信息后,计算C1-kC2,结果就是点M。因为C1-kC2=M+rK-k(rG)=M+rK-r(kG) =M。再对点M进行解码就可以得到明文。

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第3张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第4张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第5张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第6张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第7张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第8张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第9张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第10张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第11张

(四)ELGamal加密体制                                                                               

①密钥产生过程:选择素数p、g、随机整数x、秘密随机整数y,计算h = g^x mod p。h作为公开密钥,x作为秘密密钥。

②加密过程:明文消息m,随机选一整数y<p-1,计算c1 = g^y mod p,c2 = (m* h^ymodp)modp,密文为c=(c1,c2)。

③解密过程:m=(c2/c1^x)modp =mmodp

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第12张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第13张


结果测试

(一)DH协议                                                                                

      运行程序,结果如下图1所示。选取p=69263,计算其本原根g=19360。随机选择数x=11913,那么g ^x mod p=35861;随机选择数y=49075,那么g ^y mod p=21039。用户B计算的共享密钥Kb=54047,同样用户A计算的共享密钥Ka=54047。

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第14张

(二)RSA密码                                                           

      算法测试结果如下图2所示。首先输入两个素数p和q分别为17和11,得到n=1711=187,φ(n)=1610=160。输入e为7,7d=160*k+1得到d=23。此时公钥为(187,7),私钥为(187,23)。选择加密,明文m为71,得到密文c=m^e modn=71^7mod187=113;选择解密,密文113,得到明文m=c^d modn=113^23mod187=71。

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第15张

(三)椭圆曲线密码                                          

     运行程序如下图3,输入要加密的文件路径“E:\测试\1.txt”,加密完成后,加密文件存放在1密文.txt中;输入要解密的文件路径“E:\测试\1密文.txt”,解密完成后,解密文件存放在1密文解密.txt中,结果如下图4所示。

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第16张

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第17张

(四)ELGamal加密体制                                          

     运行程序后如下图5所示,输入明文m、素数p、g、随机整数x、秘密随机整数y,得到h = g^x mod p=449^12mod509=438,c1 = g^y mod p=449^18mod509=231,c2 = (m* h^y modp)mod p=(100438^18 mod509)mod509=492,c=(c1,c2)=(231,492),验证得明文m=(c2(c1^x)^(-1))%p=100。

【密码学】公钥密码 (https://mushiming.com/) 技术博客 第18张

THE END

发表回复