RSA非对称加密算法

算法步骤:

  1. 随机选择两个不相同的素数
  2. 计算
  3. 计算n的欧拉函数
  4. 选择一个,使互质,且(公约数只有1的两个自然数称互质数)
  5. 计算 对于 的模反元素 ,即找到一个 满足,就是求方程 的整数解(这个方程可以用扩展欧几里得算法求解)
  6. 最后公钥为 , 私钥为公钥
  • 模反元素:
    模反元素:如果两个正整数e和r互质,那么一定能找到整数d,使得 ed%r=1 ,即 (ed-1)%r=0,则称d为e的模反元素
  • 扩展欧几里得算法(辗转相除法)求二元一次方程整数解:
    用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止
    如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数
内容 说明
公钥
私钥
加密
解密

实例

这里找简单的例子熟悉一下算法流程:

1.选择p,q

假设 p=23,q=29

2.计算n

n=23*29=667

3.计算欧拉函数

φ(n)=(23-1)*(29-1)=616

4.选一个e,(1<e<φ (n))

假设e=13,13和616是互质的满足条件

5.计算e对于φ(n)的模反元素d

ed–kφ(n)=1 带入值得 13d-616k=1

辗转相除法
616/13=13*47+5 5=616-13*47 1式
13/5=5*2+3 3=13-5*2 2式
5/3=3*1+2 2=5-3*1 3式
3/2=2*1+1 1=3-2*1 4式

我们求解最后都要化成1=13d-616k的形式,所以要消去多余的2,3,5

3代入4得5

2代入5得6

1代入6得到13d-616k的形式

得1=237x13-5x616

即d=237,k=-5

因为模反元素不止一个,d+kφ(n) 都是e的模反元素,这里k就取0

d=d+kφ(n)=237-0x616=237

6.公钥(13,667),私钥(237,667)

下面加密解密验证一下

假设明文是55

c=m^e mod n=55^13mod667=242

解密

m=c^d mod n=242^237mod667=55

流程图

补充:大数模幂运算快速算法

计算像9%2,4%2这种简单的很容易,也很好表示,但是像上面的242^237%667就不太好表示了,242^237的结果有多少位不知道,累乘是肯定会溢出的,而且效率不高,这里补充一个大数模幂运算快速算法
假设有整数a, b与除数m ,那么假设
a % m = j , b % m = t , 有整数 i , s , 使
a=im+jb=sm+t
a=im+jb=sm+t

所以有
a⋅b=(im+j)⋅(sm+t)=ism2+jsm+itm+jt
a⋅b=(im+j)⋅(sm+t)=ism2+jsm+itm+jt

推出
(a⋅b) mod m=(ism2+jsm+itm+jt) mod m=jt mod m=((a mod m)(b mod m))mod m
(a⋅b) mod m=(ism2+jsm+itm+jt) mod m=jt mod m=((a mod m)(b mod m))mod m

因为
abc mod m=((ab)⋅c) mod m=(((ab) mod m)(c mod m)) mod m=(((a mod m)(b mod m) mod m)(c mod m)) mod m
abc mod m=((ab)⋅c) mod m=(((ab) mod m)(c mod m)) mod m=(((a mod m)(b mod m) mod m)(c mod m)) mod m

依次类推既可.
我们再考虑大数幂m要如何分解成形如m=m1+m2+…+mnm=m1+m2+…+mn的形式.
可以把大数幂m写成二进制,然后只取值为1的位,和这一位在二进制中从右到左的位数(从0开始计算),就可以得到这个大数幂的分解式了.

1
2
3
4
5
6
7
8
9
10
11
int runFermatPow(int a, int b, int m)
{
int result = 1;
while (b > 0) {
if ((b & 1) == 1)
result = (result * a) % m;
a = (a * a) % m;
b >>= 1;
}
return result;
}

RSA实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

int runFermatPow(int a, int b, int m)
{
int result = 1;
while (b > 0) {
if ((b & 1) == 1)
result = (result * a) % m;
a = (a * a) % m;
b >>= 1;
}
return result;
}
int main()
{
int p, q, e, d, n, fai_n, m, c;
printf("输入p,q,e\n");
scanf_s("%d%d%d", &p, &q, &e);
n = p*q;
fai_n = (p - 1)*(q - 1); //Φ(n)
int i = 1;
while ((i * fai_n + 1) % e) {
i++;
}
d = (i * fai_n + 1) / e;//d * e ≡ 1 (mod Φ(n))
printf("公钥(%d,%d)\n", e, n);
printf("私钥(%d,%d)\n", d, n);
printf("请输入明文");
scanf_s("%d", &m);
c = runFermatPow(m, e, n);
printf("密文%d\n", c);//加密
printf("解密%d\n", runFermatPow(c, d, n));//解密
system("pause");
return 0;
}

结果

代码实现了简易的RSA算法,只能加密数值,不能满足真正的加密需求;实际上要想获得一定的安全性,公钥n的长度要达到1024位

RSA安全性

算法安全性在于只知道密文和公钥,但是想要破解就要进行逆运算,最直接的是大整数的因数分解,但是对现在的计算水平或算法来说是一件非常困难的事。所以这里说的安全也只是相对的,基于现在的水平导致解决这个问题很困难,但是当随着计算水平的提高或者有了优秀的算法,RSA算法安全性就要打折扣了。道高一尺魔高一丈,加密技术和破解技术必是在相互磨练中前进。