CTF中RSA的相关知识

字符及相关知识简单介绍

p ， q：两个大的质数，是另一个参数N的的两个因子。
N ：模数，也可以说是一个大整数
e ， d : 互为无反数，也可以说d为e的模反数
c ：密文
m ：明文
(N,e) ：公钥
(N,d) ：私钥
模反元素：如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。
互质：公约数只有1的两个整数
pow(x,y,z) ：相当于x的y次方，再对z取模，即结果=pow(x,y)%z。(前提是z需要存在)。

–通常的RSA加密，会直接或间接给出公钥。

最终密文转明文示例脚本：

import gmpy2
n = 
d = 
c = """ """
result = ""
c_list = c.split()
#print(c_list)
for i in c_list:
result += chr(pow(int(i),d,n))
print(result)

共模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数N。然后用所有公钥加密同一密文。即：

c1 = pow(m, e1, N)  （ c1=m^e1%n ）
c2 = pow(m, e2, N)  （ c2=m^e2%n ）

此时根据现有的不同密钥可以解出同一明文。即：

m = pow(c1, d1, N)  （ m = c1^d1%n )
m = pow(c2, d2, N)  （ m = c2^d2%n )

默认 e1 与 e2 互质，即：

gcd(e1,e2)=1

则存在s1，s2有：

e1*s1+e2*s2 = 1

其中，s1，s2均为整数，但其中一个为负数。这里假设s1为正数,s2为负数
根据欧几里得算法得到：

(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n

根据模运算性质，可以化简为：

(c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n
即：
(c1^s1*c2^s2)%n = (m^(e1^s1+e2^s2))%n

故有：

(c1^s1*c2^s2)%n = (m^(1))%n 
(c1^s1*c2^s2)%n = m^%n

即：

c1^s1*c2^s2 = m

由此即可解除m