ctf之RSA解密

ctf之RSA解密"/>

ctf之RSA解密

小明得到了一个RSA加密信息，你能帮他解开吗？

c=27990707239527629138352696377606718299992092729307910015562504696905353450041n=41069065654959614597750207738698085798765257876378561837894254544512565197793e=11

直接分解模数Ｎ

直接分解模数N是最直接的攻击方法，也是最困难的方法。具体的解析同上RSA安全性分析。
如果n小于256bit，可以使用本地工具进行暴力分解，例如windwods平台的RSATool，可以在数分钟之内完成256bit的n的分解。
如果n大于768bit，可以尝试利用在线网站， 这一类在线网站的原理是储存了部分n分解成功的的值。
首先对n分解

分解Ｎ可以通过在线网站.php
分解n可以得到p和q的值为218538667198531171522213512860093810267和187925853952657607512617865502535480179，现在已知p、q、e以及c，可以通过前三个参数求出d
mac安装gmpy2可以参考.html

import gmpy2
p = gmpy2.mpz(218538667198531171522213512860093810267)#初始化大整数
q = gmpy2.mpz(187925853952657607512617865502535480179)
e = gmpy2.mpz(11)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)#invert（x，m）返回y使得x * y == 1 modulo m，如果不存在y，则返回0
print("p=%s,q=%s,e=%s"%(p,q,e))
print("d is:\n%s"%d)

d为14934205692712587126454620995890213017585015765537226566857972060418158511763

到目前为止，已经求出p,q,e,d,n,c，然后可以求出相应的明文M
#求明文

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

import gmpy2
from binascii import a2b_hexc = hex(27990707239527629138352696377606718299992092729307910015562504696905353450041)
n = hex(41069065654959614597750207738698085798765257876378561837894254544512565197793)
e = hex(11)
p = 218538667198531171522213512860093810267
q = 187925853952657607512617865502535480179
d = hex(14934205692712587126454620995890213017585015765537226566857972060418158511763)flag = a2b_hex(hex(pow(c,d,n))[2:])
print(flag)from binascii import a2b_hexe = 11
d = 14934205692712587126454620995890213017585015765537226566857972060418158511763
c = 27990707239527629138352696377606718299992092729307910015562504696905353450041
n = 41069065654959614597750207738698085798765257876378561837894254544512565197793#flag = hex(pow(c,d,n))[1:].decoding("hex")
#flag = a2b_hex(hex(pow(c,d,n))[2:])
flag = pow(c,d,n)
print(flag)

import gmpy2
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034# 1.已知的p和q求出n
n = p * q# 2.根据已知的条件求出d
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e,phi_n)
#print(d)#求出明文
m = pow(c,d,n)
print("m=\n%s"%m)
'''