RSA攻击之共模攻击

引子

假设有一家公司COMPANY,在员工通信系统中用RSA加密消息。COMPANY首先生成了两个大质数P,Q,取得PQ乘积N。并且以N为模数,生成多对不同的公钥及其相应的私钥。COMPANY将所有公钥公开。而不同的员工获得自己的私钥,比如,员工A获得了私钥d1.员工B获得了私钥d2.

现在,COMPANY将一条相同的消息,同时经过所有公钥加密,发送给所有员工。

此时,就可能出现共模攻击。

共模攻击

也称同模攻击,英文原名是 Common Modulus Attack

同模攻击利用的大前提就是,RSA体系在生成密钥的过程中使用了相同的模数n。

我们依然以上面的案例展开。

假设COMPANY用所有公钥加密了同一条信息M,也就是

c1 = m^e1%n
c2 = m^e2%n

此时员工A拥有密钥d1他可以通过

m = c1^d1%n

解密得到消息m

同时员工B拥有密钥d2

他可以通过

m = c2^d2%n

解密得到消息m如果,此时有一个攻击者,同时监听了A和B接收到的密文C1,C2,因为模数不变,以及所有公钥都是公开的,那么利用同模攻击,他就可以在不知道d1,d2的情况下解密得到消息m。

又到了高数时间~

这里就是要论证,当n不变的情况下,知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下,解出m。

首先假设,e1,e2互质

gcd(e1,e2)=1

此时则有

e1*s1+e2*s2 = 1

式中,s1、s2皆为整数,但是一正一负。

通过扩展欧几里德算法,我们可以得到该式子的一组解(s1,s2),假设s1为正数,s2为负数.

因为

c1 = m^e1%n
c2 = m^e2%n

所以

(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

又前面提到

e1*s1+e2*s2 = 1

所以

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

c1^s1*c2^s2 = m

也就是证明了命题:当n不变的情况下,知道n,e1,e2,c1,c2 可以在不知道d1,d2情况下,解出m。

这里还有一个小问题,顺带说明下。

我们知道解出来s2是为负数。

而在数论模运算中,要求一个数的负数次幂,与常规方法并不一样。

比如此处要求c2的s2次幂,就要先计算c2的模反元素c2r,然后求c2r的-s2次幂。

案例

n = 1022117
p = 1013
q = 1009
#936
fn = (p-1)*(q-1)
e = 17
d = 180017
m = int("h1".encode("hex"),16)
c1 = m**e%n
e1 = 5
d1 = 816077
c2 = m**e1%n
print n
print e
print e1
print c1
print c2

假设模数n固定为1022117,并且产生了(e,d),(e1,d1)两个密钥对。

并且打印出m加密后的密文c1,c2.

求通过e,e1,c1,c2解出m来。

以下是一个可供利用的脚本

#coding=utf-8
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():
	n = int(raw_input("input n:"))
	c1 = int(raw_input("input c1:"))
	c2 = int(raw_input("input c2:"))
	e1 = int(raw_input("input e1:"))
	e2 = int(raw_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()

附图一张。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章