RSA加密算法

RSA加密算法属于公钥加密算法,是一种非对称密码算法
非对称加密算法:
图片.png

数论基础
质数(素数)

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

互质数

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

欧拉函数

在数论中,对于正整数N,小于或等于N([1,N]),且与N互质的正整数(包括1)的个数,记作φ(n)。
任意两个数p、q,如果p、q存在互质关系,有φ(pq)=(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

题目
公钥{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即可。

# 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生成明文

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

RSA中的参数

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/
手工:

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为止。

 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

公钥 = {n ,e1}
公钥 = {920139713,19}
私钥 = {n ,e2}
私钥 = {920139713,96849619}

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