rsa公钥密码和签名

RSA是目前使用最广泛的公钥密码*之一。它是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA算法的安全性基于RSA问题的困难性,也就是基于大整数因子分解的困难性上。但是RSA问题不会比因子分解问题更加困难,也就是说,在没有解决因子分解问题的情况下可能解决RSA问题,因此RSA算法并不是完全基于大整数因子分解的困难性上的。
**

1.欧拉函数

什么是欧拉函数
  欧拉函数是小于x的整数中与x互素的数的个数,一般用φ(x)表示。特殊的,φ(1)=1.
如何计算欧拉函数
  通式:φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)(1-1/pn),其中p1, p2……pn为n的所有素因数,n是不为0的整数.
欧拉函数的一些性质  
  1. 对于素数p,φ§=p−1  2. 若p为素数,n=pk,则φ(n)=pk-p^(k-1)   3. 欧拉函数是积性函数,但不是完全积性函数;若m,n互素,则φ(m∗n)=φ(m)∗φ(n),特殊的,当m=2,n为奇数时,φ(2
n)=φ(n)  4. 当n>2时,φ(n)是偶数  5. 小于n的数中,与n互素的数的总和为:φ(n) * n / 2 (n>1)  6. n=∑d∣n​φ(d),即n的因数(包括1和它自己)的欧拉函数之和等于n

欧拉定理

欧拉定理是指:如果两个正整数a和n互素,则n的欧拉函数φ(n)可以让下面的式子成立:

即a的φ(n)次方减去1,可以被n整除. 比如,3和4互质,φ(4)=2,(3^2-1)/4=2. 当a为正整数,n为素数且a不能被n整除时,则有           a^(n-1) ≡ 1 (mod n)这就是费马小定理.

模反元素

如果两个正整数a和n互素,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1. 这时,b就叫做a对模数n的模反元素.

欧拉定理可以用来证明模反元素必然存在,如下图,可以看到:a的 φ(n)-1 次方,就是a对模数n的模反元素.

RSA算法

5.1 密钥的生成过程

  1. 随意选择两个大的素数p和q,p不等于q,计算n = pq.
  2. 根据欧拉函数的性质3,求得r=φ(n)=φ§φ(q)=(p-1)(q-1).
  3. 选择一个小于r的整数e,且e与r互素;并求得e关于r的模反元素,命名为d.(模反元素存在,当且仅当e与r互质; 求d令ed≡1(mod r))
  4. 将p和q的记录销毁
      其中(n,e)是公钥,(n,d)是私钥. 例如:
  5. A随机选两个不相等的质数61和53,并计算两数的积n=61*53=3233,n的长度就是密钥长度。3233的二进制是110010100001,一共12位,
    所以这个密钥就是12位. 实际应用中,RSA密钥一般是1024位,重要的场合是2048位.
  6. 计算n的欧拉函数; φ(n)=(p-1)(q-1)=60*52=3120.
  7. A在1到3120上随机选择了一个随机数e=17,与3120互素.
  8. 计算e对φ(n)的模反元素d,即时,ed-1=kφ(n)。
    即使求解:17x+3120y=1.用扩展欧几里得算法求解。可以算出一组解(x,y)=(2753,-15),即d=2753. 公钥(3233, 17),私钥(3233,2753)
      至此完成计算.5.2 RSA的可靠性    在RSA私钥和公钥生成的过程中,共出现过p,q,n,φ(N),e,d,其中n,e组成公钥,其他的都不是公开的,一旦d泄露,就等于私钥泄露;  那么能不能根据n,e推导出d呢?    1. ed ≡ 1(mod φ(n)) 只有知道e和φ(n),才能算出d     2. φ(n)=(p-1)(q-1) 只有知道p和q,才能算出φ(n)    3. n=pq,只有将n分解才能算出p和q  所以,只有将n素因数分解,才能算出d; 也就意味着私钥破译. 但是,大整数的质因数分解是非常困难的. 所以理论上来说,如果我们找到  了快速对大整数进行质因数分解的方法,那么RSA加密也就没什么安全性可言了;遗憾的是,目前数学上并没有找到这样快速的质因数分解方法.5.3 RSA的加密过程    假设A要向B发送加密信息m,他就要用B的公钥(n,e)对m进行加密,但m必须是整数(字符串可以取ascii值或unicode值),且m必须小  于n. 所谓加密就是计算下式的c:    m^e ≡ c (mod n)  假设m=65,B的公钥(3233,17),所以等式如下:    65^17≡2790(mod 3233)  所以c等于2790,A就把2790发给B.5.4 RSA的解密过程    B收到A发来的2790后,就用自己的私钥(3233,2755)进行解密      c^d ≡ m (mod n)  也就是c的d次方除以n的余数就是m      2790^2753 ≡ 65 (mod 3233)  因此得到原文65.

C语言代码

**

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int xy[22];
int myPow(int a, int b, int m) {
    int res = 1;
    a %= m;
    while (b != 0) {
    if ((b & 1) == 1)
    	res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}


int calculate(int h,int p,int q){
	int a = (p-1)/q;
	int k=1;
	for(int i = 0;i<a;i++){
		k=k*h;
	}
	return k%p;
}
int calculate1(int g,int x,int p){
	int k=1;
	for(int i = 0;i<x;i++){
		k=k*g;
	}
	return k%p; 

} 
// 求 a mod b 的逆元
void exGcd(int a, int b) {
    if (b == 0) {
        xy[0] = 1;
        xy[1] = 0;
    } else {
        exGcd(b, a % b);
        int x = xy[0];
        xy[0] = xy[1];
        xy[1] = x - (a / b) * xy[1];
    }
}
main()
{
	int p,q,g,x,y,s,k,m,w,u1,u2,v,h,r;
	//初始化 
	printf("请输入大素数 p和q ,且满足(p-1)能够被q整除");
	scanf("%d%d",&p,&q);//素数p和q 
	srand(time(NULL)); //随机数种子
	h=12;//rand()%p-1+2 ;//随机数 
	g=calculate(h,p,q); 
	x=10;//rand()%p-1+2 ;//私钥 
	y=calculate1(g,x,p);//计算公钥 
	printf("公钥是(%d,%d,%d,%d)\n",p,q,g,y);
	printf("私钥为%d\n",x);
	
	//签名过程 
	k=9;//rand()%p-1+2 ;//随机数k 
	r=calculate1(g,k,p)%q;	
	exGcd(k, q);
	k = xy[0];
    if(k < 0) k += (p-1);  
	m=13;
	s=(m+x*r)*k%q;
	printf("签名为(%d,%d)\n",r,s);
	
	//验证
	exGcd(s,q);
	w =xy[0];
	if(w < 0) w += (q);
	u1=(m*w)%q;
	u2=r*w%q;
	v=myPow(g, u1, p)*myPow(y, u2, p)%p%q;
	printf("(w,u1,u2,v)=(%d,%d,%d,%d)\n",w,u1,u2,v);
	if(v==r){
		printf("接受");
	}else{
		printf("不接受");
	}
	
	
	
	
	
	
	
	
	
	
}
上一篇:简单配置 PotPlayer、LAVFilters 和 xy-VSFilter 满足基本 BDRIP 回放需求


下一篇:iOS图片模糊效果与阴影效果