趣题分享[2] -- ISCTF 2023 -- Signin
题目附件
from Crypto.Util.number import *
from secret import flag
def genKey(nbits):
p = getPrime(nbits)
q = getPrime(nbits)
N = p*p*q
d = inverse(N, (p-1)*(q-1)//GCD(p-1, q-1))
return N,d
def encrypt(message,N):
m = bytes_to_long(flag)
c = pow(m, N, N)
return c
nbits = 1024
m = bytes_to_long(flag)
N,d = genKey(nbits)
c = encrypt(m,N)
print('c =', c)
print('N =', N)
print('d =', d)
"""
c = 29897791365314067508830838449733707533227957127276785142837008063510003132596050393885548439564070678838696563164574990811756434599732001622138564176327233154381380717648392357672642893142367607369679906940371540867456654151408884171467638060523066406441697453971996011548195499549200103123841556085936672833238264876038160712793697159776332101536779874757463509294968879216810485825310481778472384531442206034564488532399171243463881900578407746982324779260941957792455217641883334131366614310644607114128868153897806362954456585661855569432513785225453501792356175649676419772626548071916379318631677869452985829916084336045071072493567871623113923140668031380684940109024609167449291380675124701557542736834722898328082888430566229322840781411336263268594978558564310744076581639469210462567543585251718744340216155557606004995449505782302864725856877289388008819135023371948017425832082773421030256964953984562211638060
N = 3231913372897424708803097969843687520868057190788284975066875241636436021279559026753076528399891936983240045179193386905918743759145596242896507856007669217275515235051689758768735530529408948098860529277921046146065473333357110158008648799207873976745048714516868561754202543130629713461365314627535982379718931633528922076268531363809414255082933615667770491818402126891370106045838695484124212397783571579791558324350069782623908757815983802849109451590357380624488436968737140312471089662428308113246310588336044438265822574558816510054763215983649467009345458480077882624118620789015758507736272402998721366662352794082495441303895025585316667229865533166614969641012195668280586477033200418153345241668242651407009849656745509386158276185301334443855737552801531617549980843398648751032649895403939319648954908487619711555700124294191702406981128355348449748466449951568451135718146828444185238617155432417897711198169
d = 220908195398117048628110042133057032501548264225985823161565460390793825899523662424732910718579350524590368287207857059670558852106434615134645183432670023784725430385048028248108677670095524205518013647694485975996499747580966911259433184798952372110628624294686853944766950244209186984164963987120416687012811346656498861438432610431705868541829977481875385468143747334359481673214618931159403123892213161430602430294790913847722073762999311674428134241956293914716183107414340330449465142849402354034926378025006749405210014879947411570380433942279355488861684317611066949685697268714760755591128598654573304969
"""
思路
定义模数 和 解密指数 之间的关系
解密指数 的计算公式
对于任意整数 ,计算 的 次幂模
题目中对公钥 的构造
模数 和欧拉函数 之间的关系
的 次幂模
从而
恒等式转为等式且对 移项得
模数 ,解密指数 ,和 之间的关系
求解
求解
加密指数
与 phi
不互素,可以尝试非预期
Sage
a = 2 # 取 a > 1, 例如 2, 符合条件且相对好算
k2n = power_mod(a, (N * d), N) - a # 但是为什么 mod N 是对的, 见下方
n = GCD(k2n, N)
p = N / n
q = n / p
assert p * p * q == N
phi = (p - 1) * (q - 1) * p
# assert GCD(phi, N) == 1 # 不互素
# dd = inverse_mod(N, phi)
# m = power_mod(c, dd, N)
# m = long_to_bytes(m)
# print(m)
ans_list = Mod(c, p * p * q).nth_root(p * p * q, all=True)
print('完成枚举')
print('len: ' + len(ans_list))
for ans in ans_list:
if b'ISCTF' in long_to_bytes(ans):
print(long_to_bytes(ans))
break
思路补充
为什么 k2n = power_mod(a, (N * d), N) - a
中进行 是对的?
因为接下来操作是求最大公约数,需要 , 且 所以可以取模来触发快速幂,否则会很慢
不过这里的 就不真实了,但意义也不大,因为核心在 也就是
Exploit
更优雅的办法, 是 的真因子,在较小的模数下解密
a = 2
k2n = power_mod(a, (N * d), N) - a
n = GCD(k2n, N)
p = N / n
q = n / p
assert p * p * q == N
m = power_mod(c, d, n)
print(long_to_bytes(m)) # b'ISCTF{aeb8be10-ff19-42cf-8cfd-2ce71ac418e8}'
出题者(Dexter)说
考虑 Schmidt-Samoa 密码系统:
- 任意整数 ,有
- 因此
给定 来公然发送即可得到 ,再用 解密即可