HEBCTF-easy_RSA-WriteUp

很久之前做的一道题了，当时还没搭博客，只写了md，现在刚好放博客上，nice~😎

HEBCTF-easy_RSA

题目代码

from gmpy2 import *
from Crypto.Util import number

#e = have a try~
p = number.getPrime(1024)
q = number.getPrime(1024)

nothing = 251560377963038761190200797029988859033 # getPrime(128)

n = p*q
fn = (p-1)*(q-1)
d =inverse(e, fn)
something=(p-1)d+nothing
enc = pow(flag, e, p*q)

print (n)
#n=14284898343409519110893988467316511926370451139898930447913929171639157662416924629721731319745621456628886461208084701377746738712806909510733763533111440296587773645965346813837315287791601828684827959213005394017782134099259170149915437025962624405554913909119787918969678680969013413675883687099548278972115691260909326823826733899687527221094134484324195895781497056688836390217827814939835994217942643008875830529445666479044655104422017227768913567208280346040068940328073829553819676484041944265736136407848750757258471249497666545068872011229067294045688552723745158600169354377516976789338341197514239514943
print(s)
#something=286513783515614922964487317633030845022199764334523704172857900468207328275601546483407711018702750569030377856457729134725585035340273850696372794971562057097878568322145360455616114805337204320995794956912354651091693657156422658881160865975268727450032165425473533693410304381371095831091118583746948774725405739487325458903660189348971842364607739242225293967215501191421774709879078076074161789004913628127600135108988375932151821980659991278616990695976636258955726402697510230023838942094639019441749484792888646404524697026596867444210593464034174763857812793583906156073077832265794741963441612539965049158860120119167347530684129840646220683525848056119433617113962506545054683798313759769240061077256966777326661431711874356368294140866366364716767053776009140934309044595124213623948792672967896390820967208318303287692916619220370506456013211642234660990531096377697018415439879456848769444607806947569088449625
print(enc)
#enc=4881342612605167945566362034399587836635894621851547317823874228263412784935124440289546702719504165280607577300320293348921200397520285704213654018930232712940345612671113541266347784516634193958010265082924711886924437824841465114124020180216977559637341458252243825701112061216139287782944762861273904099742150098423639841865509382899243178009016015415485229031954926669538913188143653236257937229799801229863924027941144675212479223330496722053292471015086437410831685022807918456036289520338369388719529672585641297779845250083115247220743517626420017412100344704837819753505113936564984505444789009239645210810

代码分析

• 1、代码中没有给出e的值，猜测是常见的e值，尝试了65535、65537。
• 2、代码中给出了d和p的关系，因此可利用费马小定理求解。
  【费马小定理】如果p是一个质数，而整数a不是p的倍数，则有a^(p-1)≡1 mod p。

解题过程

1、我们可以设A = m^(p-1)-1，其中m^(p-1) ≡ 1 mod p，故A是p的倍数，由于N = p*q，因此gcd(A,N)=p。
2、由m^e ≡ c mod N得到 c = m^e - b*N（b是整数）。
3、又因为 c^d ≡ m mod N，所以(m^e - b*N)^d = m mod N，进一步(m^e)^d = m mod N。
4、等式两边取p-1次方，得到：(m^ed)^(p-1) mod N = m^(p-1) mod N，即：m^e(s-n) mod N = m^(p-1) mod N。
5、得到A = (m^e(s-n) mod N)-1，即可求得p = gcd(A,N)。

代码如下

import gmpy2
from Crypto.Util.number import *

n=14284898343409519110893988467316511926370451139898930447913929171639157662416924629721731319745621456628886461208084701377746738712806909510733763533111440296587773645965346813837315287791601828684827959213005394017782134099259170149915437025962624405554913909119787918969678680969013413675883687099548278972115691260909326823826733899687527221094134484324195895781497056688836390217827814939835994217942643008875830529445666479044655104422017227768913567208280346040068940328073829553819676484041944265736136407848750757258471249497666545068872011229067294045688552723745158600169354377516976789338341197514239514943
enc=4881342612605167945566362034399587836635894621851547317823874228263412784935124440289546702719504165280607577300320293348921200397520285704213654018930232712940345612671113541266347784516634193958010265082924711886924437824841465114124020180216977559637341458252243825701112061216139287782944762861273904099742150098423639841865509382899243178009016015415485229031954926669538913188143653236257937229799801229863924027941144675212479223330496722053292471015086437410831685022807918456036289520338369388719529672585641297779845250083115247220743517626420017412100344704837819753505113936564984505444789009239645210810
something=286513783515614922964487317633030845022199764334523704172857900468207328275601546483407711018702750569030377856457729134725585035340273850696372794971562057097878568322145360455616114805337204320995794956912354651091693657156422658881160865975268727450032165425473533693410304381371095831091118583746948774725405739487325458903660189348971842364607739242225293967215501191421774709879078076074161789004913628127600135108988375932151821980659991278616990695976636258955726402697510230023838942094639019441749484792888646404524697026596867444210593464034174763857812793583906156073077832265794741963441612539965049158860120119167347530684129840646220683525848056119433617113962506545054683798313759769240061077256966777326661431711874356368294140866366364716767053776009140934309044595124213623948792672967896390820967208318303287692916619220370506456013211642234660990531096377697018415439879456848769444607806947569088449625
nothing=251560377963038761190200797029988859033
e = 65537

A=pow(2,e*something-e*nothing,n)-1
p = gmpy2.gcd(A,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))

m = pow(enc, d, n)
flag = long_to_bytes(m)
print(flag)