一、RSA介绍
RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。
二、已知条件
RSA的加密规则：$ \color{blue}{m^e \equiv c\pmod n}$
RSA的解密规则：$\color{red}{c^d \equiv m\pmod n}$
约束条件及规则说明：
- m为明文字符，c为密文字符
- m为0到n-1之间的数值
- n=pq，p,q为素数
- φ(n)=(p-1)*(q-1) [根据欧拉定理]
- e与φ(n)互素
- $ ed \equiv 1\pmod {φ(n)}$
- 欧拉公式$m^φ(n) \equiv 1\pmod n$
要根据加密规则，数论及欧拉定理，来证明解密公式正确性：$\color{red}{c^d \equiv m\pmod n}$
三、证明过程
step1、根据加密规则公式$ \color{blue}{m^e \equiv c\pmod n}$
可以得出 $$c=m^e-kn$$
step2、 将C带入解密公式，得到
$$(m^e-kn)^d \equiv m\pmod n$$
step3、左边的展开中，除了第一项以外，其他项都与n相乘过，所以可以直接忽略左边括号中的kn项目，即：
$$m^{ed} \equiv m\pmod n$$
step4、因为 $ed\equiv1 \pmod {φ(n)}$ 即：
$$ed=hφ(n)+1$$
step5、上述结论代入step3的公式，得到
$$m^{hφ(n)+1} \equiv m \pmod n $$
step6、分情况讨论
6.1 、m与n互质（如果你已经忘了m和n是什么了，请往前再看一遍）
根据欧拉定理$m^φ(n) \equiv 1\pmod n$ 得到 $m^{φ(n)}=kn+1$
然后左右两边分别h次方得到(kn+1)的h次方还是kn+1只不过这里的k变了：
$$(m^{φ(n)})^h=kn+1$$
然后左右两边乘以m即得到$$m^{hφ(n)+1} \equiv m \pmod n $$
6.2 、m与n不互质
此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。
以 m = kp为例，这时k与q必然互质。如果k与q 不为互质关系，则k=tq, m= tqp=tn, 但是按照RSA规范，m∈(0…n−1) m\in(0…n-1)m∈(0…n−1), m < n的，所以k与q肯定是互质关系的。由于k与q互质，p与q互质，kp与q肯定互质，则根据欧拉定理，下面的式子成立：
$$\Large (kp)^{ q-1} \equiv 1\pmod q$$
进一步扩展，可得：
$$ \Large [(kp)^{ q-1}]^{h(p-1)}\times kp \equiv kp\pmod q$$
即
$$\Large (kp)^{ed} \equiv kp\pmod q$$
进一步改写成等式：
$$\Large (kp)^{ed} = kp+tq$$
显然，t能被p整除， 即t=t’p,可以得出
$$\Large (kp)^{ed} = kp+t’pq$$
因为m=kp, n=pq, 最后得出
$$\Large m^{ed} \equiv m\pmod n$$
解密公式得到完全证明。
四、关于共模攻击脚本（其他的脚本要求安一堆奇怪的包，在win10还装不上，这里贴一个野生的共模攻击脚本
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
42
43
44
45
46
47
48
49
50
51
52
53
| # coding=utf-8
import sys
sys.setrecursionlimit(10000000)
"""
选择相同的模 n 加密相同的信息 m
"""
helpstr = '''
usage:
c1 = m ^ e1 % n
c2 = m ^ e2 % n
'''
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def main():
print(helpstr)
n = int(input("input n: "))
c1 = int(input("input c1: "))
c2 = int(input("input c2: "))
e1 = int(input("input e1: "))
e2 = int(input("input e2: "))
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1 < 0:
s1 = - s1
c1 = modinv(c1, n)
elif s2 < 0:
s2 = - s2
c2 = modinv(c2, n)
m = (c1**s1)*(c2**s2) % n
print(m)
if __name__ == '__main__':
main()
|
分解模数脚本
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| # 分解模数n
def rsa_moder(n):
base = 2
while base < n:
if n % base == 0:
return base, n // base
base += 1
# 求欧拉函数f(n)
def rsa_get_euler(prime1, prime2):
return (prime1 - 1) * (prime2 - 1)
# 求私钥
def rsa_get_key(e, euler):
k = 1
while True:
if (((euler * k) + 1) % e) == 0:
return (euler * k + 1) // e
k += 1
# 根据n,e计算d(或根据n,d计算e)
def get_rsa_e_d(n, e=None, d=None):
if e is None and d is None:
return
arg = e
if arg is None:
arg = d
primes = rsa_moder(n)
p = primes[0]
q = primes[1]
d = rsa_get_key(arg, rsa_get_euler(p, q))
return d
def test():
str_fmt = 'n: {:<10} e: {:<10} d: {:<10}'
# 导入rsa库
import rsa as rsa
key = rsa.newkeys(24)
# 产生rsa密钥对
if isinstance(key[1], rsa.PrivateKey):
print(str_fmt.format(key[1].n, key[1].e, key[1].d))
# 解密
n = 14666299
d = 2101153
e = get_rsa_e_d(n, None, d)
print(str_fmt.format(n, e, d))
n = 12748507
e = 65537
d = get_rsa_e_d(n, e, None)
print(str_fmt.format(n, e, d))
if __name__ == '__main__':
test()
|