破解加密数据 之 Rabin算法

本题来自于:2019年工业信息安全技能大赛个人线上赛,第二场第一题,破解加密数据,题目如下,即解密密文109930883401687215730636522935643539707对应的明文数据

m = "unknown"
e = 2
n = 0x6FBD096744B2B34B423D70C8FB19B541

assert(int(m.encode('hex'), 16) < n)
c = pow(int(m.encode('hex'), 16),e,n)
print c
#109930883401687215730636522935643539707

加密方法是,把明文转码成16进制,再转成对应的十进制的一个大数,然后平方后模n,看着非常像rsa,不过这其实是rabin算法。解法参考:RSA 衍生算法——Rabin 算法

解题思路

发现把n分解为两个质数

利用yafu分解命令:factor(148525842361836932303997638207312868673),得到p和q,然后测试:

>>> p = 13691382465774455051
>>> q = 10848126018911527523
>>> p % 4
3L
>>> q % 4
3L

可以发现这两个质数都是模四余三,根据e=2可知,这是一个rabin算法,n是公钥,pq为私钥,所以解出pq就可以直接解密了:

image

运算规则

按照上图q在模p上的逆p在模q上的逆可以直接用扩展欧几里得求出:

m1 = pow(c,(p+1)/4,p)
m2 = (p-pow(c,(p+1)/4)) % p
m3 = pow(c,(q+1)/4,q)
m4 = (q-pow(c,(q+1)/4)) % q

a=q*ModReverse(q,p)
b=p*ModReverse(p,q)

M1 = (a*m1+b*m3)%n
M2 = (a*m1+b*m4)%n
M3 = (a*m2+b*m3)%n
M4 = (a*m2+b*m4)%n

但其中m2 = (p-pow(c,(p+1)/4)) % p因为太大不能直接运算,所以利用模运算性质:

(a-b)%p == (a%p - b%p)%p 

:

m2
= (p-pow(c,(p+1)/4)) % p
= (p%p - pow(c,(p+1)/4,p))%p
= (-pow(c,(p+1)/4),p)%p
= (-m1)%p

同理:

m4 = (-m3)%p

负数取模直接用python计算即可

解密脚本

def EX_GCD(a,b,arr):
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - int(a / b) * arr[1]
    return g

def ModReverse(a,n):
    arr = [0,1,]
    gcd = EX_GCD(a,n,arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1

def decrypt_rabin(c,p,q):
	n = p*q
	m1 = pow(c,(p+1)/4,p)
	m2 = (-m1)%p
	m3 = pow(c,(q+1)/4,q)
	m4 = (-m3)%q
	a=q*ModReverse(q,p)
	b=p*ModReverse(p,q)
	M1 = (a*m1+b*m3)%n
	M2 = (a*m1+b*m4)%n
	M3 = (a*m2+b*m3)%n
	M4 = (a*m2+b*m4)%n
	print str(hex(M1))[2:-1].decode("hex")
	print str(hex(M2))[2:-1].decode("hex")
	print str(hex(M3))[2:-1].decode("hex")
	print str(hex(M4))[2:-1].decode("hex")

if __name__ == '__main__':
	c = 109930883401687215730636522935643539707
	p = 13691382465774455051
	q = 10848126018911527523
	decrypt_rabin(c,p,q)

解密出四组数据,有意义的为flag_EnCryp1即为flag

思考区别

rabin和rsa的区别是什么呢?