RSA加密算法
2018-07-19 15:02:29 # RSA

[toc] RSA加密算法属于公钥加密算法，是一种非对称密码算法 非对称加密算法： 图片.png

数论基础
质数（素数）

在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数，也叫素数。

互质数

公因数只有1的两个数，叫做互质数。维基百科上的解释是：互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。

欧拉函数

在数论中，对于正整数N，小于或等于N（[1,N]），且与N互质的正整数（包括1）的个数，记作φ(n)。 任意两个数p、q，如果p、q存在互质关系，有φ(p_q)=(p-1)_(q-1)。

欧拉定理

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：a^φ(n)%n=1

费马小定理

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成：a^(p-1)%n=1

模反元素

两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1：a*b%n=1,这时，b就叫做a的”模反元素”。

算法实现

RSA算法基于一个事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。RSA算法三个参数：N、e1、e2 （1）选择一对不同的、足够大的素数p，q。 （2）计算n=pq。 （3）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。 （4）找一个与f(n)互质的数e1，且1<e1<f(n)。 （5）计算e2，使得e1*e2≡1 mod f(n)。这个公式也可以表达为e2 ≡e1-1 mod f(n)，≡是数论中表示同余的符号。 （6）公钥KU=(n,e1)，私钥KR=(n,e2)。 （7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，则加密过程为：C≡M^e1(mod n)。 （8）解密过程为：M≡C^e2(mod n)。 (N,e1)是公钥，(N,e2)是私钥。

签名消息

RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值，然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。

算法公式

假设： A:明文 B:密文 — —公钥加密私钥解密公式— — A=B^e2 mod n B=A^e1 mod n — —私钥加密公钥解密公式— — A=B^e1 mod n B=A^e2 mod n

题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
公钥{920139713,19}
待解密的密文B为： 405090545
848527664
16293583
475206804
246319030
368270835
828509797
16293583
274704164
583976961
890816461
16293583
583976961
246319030
336124612
336124612
752211152
306220148

已知公钥和明文，即已知A，e1，n。套公式B=A^e1 mod n即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# coding=utf-8
import math
import string
string=string.digits+string.printable
A=[405090545,848527664,16293583,475206804,246319030,368270835,828509797,16293583,274704164,583976961,890816461,16293583,
583976961,246319030,336124612,336124612,752211152,306220148]
B=""
n=920139713
e1=19
for m in A:
    for sTr in string:
        if pow(ord(sTr),e1,n)==int(str(m)):
            B+=sTr
print(B)

还可以用密文和公钥将flag生成明文

1
2
3
4
5
6
Flag="Wpsec{xxx}"
m1=""
for flag in Flag:
    m1+=str(pow(ord(flag),19,920139713))
    m1+="\n"
print(m1)
深入学习

RSA中的参数

1
2
3
4
5
6
7
8
p: 第一个大素数
q: 第二个大素数 
模数n: n = p*q 
f(n):  (p-1)*(q-1) 
公钥指数e: 与 f(n)互质, 且 1 < e < f(n) 
私钥指数d: 满足e * d ≡ 1 (mod f(n))
公钥 = {n, e1} 
私钥 = {n, e2}

RSA的密钥是公钥或私钥，密钥长度通常指模数n的位数。现用RSA的密钥长度1024位、2048位及以上 如果RSA的密钥长度过短,则可以通过分解模数n来获得p和q,获得私钥，从而获得明文。 题目中模数n=920139713,二进制=110110110110000011011111000001,密钥长度只有30位。利用现在的pc，很容易就破解出来了。 分解模数：http://factordb.com/ 手工：

1
2
3
4
5
6
def moder(n):
    base = 2  
    while base < n: 
        if n % base == 0: 
            print base, n/base
        base += 1

得到 p = 18443 q = 49891 欧拉函数 f(n) = (p-1)(q-1)= 18442 × 49890= 920071380 又已知 e1= 19，e1 x e2 ≡ 1 (mod f(n))，求e2 即 (19 x e2) mod 920071380 = 1 欧几里德算法(辗转相除法)求e2 先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个数去除前一个余数，直到余数是0为止。

1
2
3
4
5
6
7
8
9
10
 e1位置    f(n)位置
[e1 * e2 - f(n) *k = 1]

[A]:f(n)位置 mod e1位置 的余数替代 f(n)位置
[B]:e1位置 mod f(n)位置 的余数替代 e位置
[A]:f(n)位置 mod e1位置 的余数替代 f(n)位置

[a式]19×e2 - 920071380×k =1      (k 为正整数，不影响取余结果)
[b式]19×e2 - 9×k =1
[c式]1×e2 - 9×k=1

e1=1，结束，令k=0，得e2=1。 e2=1，带入B式，得k=2。 k=2，带入A式，得e2=96849619

1
2
3
4
公钥 = {n ,e1}
公钥 = {920139713,19}
私钥 = {n ,e2}
私钥 = {920139713,96849619}

RSA史上最强总结 记一次30位密钥长度RSA加密破解过程 轻松学习RSA加密算法原理

Prev
2018-07-19 15:02:29 # RSA
Next