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
39
40
41

#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算法安全性就要打折扣了。道高一尺魔高一丈，加密技术和破解技术必是在相互磨练中前进。