2024_newstar_week1_crypto

baby_mod

题目

from Crypto.Util.number import *
from enc import flagm = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(777)
t = getPrime(777)
tmp = getPrime(15)
e = 65537
n = p*q
print(f"c = {pow(m,e,n)}")
print(f"leak = {p*r-q*t-tmp}")
print(f"r = {r}")
print(f"t = {t}")
'''
c = 96982039932229986062184914601615337593043855203774154540088390154342582088831916489058244587175957104358890145287495969283908143946922141956046788682712898363783402241560976405970315671672552923522701316678810485294674195630815050476285989575640450156805391161033493965873279278988644128282368833511866391272
leak = -1180847553193702442682855971492433867077531621553705895665752944261387978020725138310978347411094960600631015411043321869598234964934461520124654252289173034818656892126034947337615252211847926165805347819958028791051889055142629057511345515311653746760688497024706371522772992776170510122534956283296780261674873647586541530925594367695865226079797779932907310916426415306226059601393833
r = 555797339419088018088392353722632677120529486185502253668037127566019016793303651597662002588421521808545398217688858573947882275827648269186472877116322039993971951402872097987262258339281612189840025558776368111961623523680175402251
t = 615237327593075592111714628640541559188263387826820275486949838611939171990255175077060052605716988822434177843980140335848735957800630838341686578454114569595081005934167126914965088689925981903197468471981207054308719385834371435283
'''

思路：

由题目获悉：

tmp比较小，所以可以通过遍历来找到tmp

已知p*r-q*t=tmp+leak

r，t已知，等号右边是已知的

前提知识：同余方程ax+b≡0 mod m 有解当且仅当(a,m) |b

其实这里可以转换成:p*r≡tmp+leak mod t  等式一

因为r和t都是素数，gcd(r,t)=1，满足求逆元的条件即

r*reverse_r≡1 mod t

reverse_r≡invert(r,t) mod t   等式二

等式一与等式二左右互相乘得到

p≡(tmp+leak)*invert(r,t) mod t

 得到p后,正常RSA即可

脚本代码

from Crypto.Util.number import *
import gmpy2
import random
e=65537
c = 96982039932229986062184914601615337593043855203774154540088390154342582088831916489058244587175957104358890145287495969283908143946922141956046788682712898363783402241560976405970315671672552923522701316678810485294674195630815050476285989575640450156805391161033493965873279278988644128282368833511866391272
leak = -1180847553193702442682855971492433867077531621553705895665752944261387978020725138310978347411094960600631015411043321869598234964934461520124654252289173034818656892126034947337615252211847926165805347819958028791051889055142629057511345515311653746760688497024706371522772992776170510122534956283296780261674873647586541530925594367695865226079797779932907310916426415306226059601393833
r = 555797339419088018088392353722632677120529486185502253668037127566019016793303651597662002588421521808545398217688858573947882275827648269186472877116322039993971951402872097987262258339281612189840025558776368111961623523680175402251
t = 615237327593075592111714628640541559188263387826820275486949838611939171990255175077060052605716988822434177843980140335848735957800630838341686578454114569595081005934167126914965088689925981903197468471981207054308719385834371435283for i in range(2**14,2**15):if isPrime(i):m=i+leakreverse_r=gmpy2.invert(r,t)p=(m)*reverse_r%tq=(p*r-m)//tphi=(p-1)*(q-1)n=p*qtry:d=gmpy2.invert(e,phi)m=long_to_bytes(pow(c,d,n)).decode()print('m=',m)if "SHCTF" in m:print(m)breakexcept:print('error=',i)

d_known

题目

from Crypto.Util.number import *
from gmpy2 import*
from flag import flagm = bytes_to_long(flag)
p = getPrime(1024)
q = next_prime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(m, e, n)
print(c)
print(d)'''
c = 8403005375036059507668949476573899369837076550693144629696007329133738521122588246908668180262007583822485069032471230229549770088907327492388166010486964325710415178606379749545343189793702142141767762980168940368804592747996874261288443645015850756539154813150178362722924342723559439994909937372080935730144313164028471482815902766596987410476536851653179862928574243638806370225834643622307886196327090667639015773736760975825026730042601141073120344825434342776953353880893841021796908686865952628635659489153801608107977991641511819655554954728559776830459369692383459501715070991568406261564744500687976022691
d = 1281547902553859084293414419691638897259210312435297418784234419527800281969029795243656339270541966215028646560597711203810636432840182193309150385941111722862919651864511924052800894612960620402770864208616639177876428714431968751785435983752685651775450406691250991111356087508576749134112503921935196726490012713717428813187789532934984608690497645602362447401532583629361369243217877261931238807810829854090482021242655140085436883719126264624674661878500582573099068229419791284814598160647661913954583323359110846608678647386673439063560883714693030315336131614665692294033299011254428100383418733928067811833
'''

思路：

这里只知道p和q的关系，如果我们能知道其中一个就很好做了，但我们p和q都不知道

我们知道两个素数之间间距大概不超过1500

如果我们能获得p和q中间的某个数，那是不是就能找到q

所以我们可以对n开平方根求出p和q中间的某个数x

常规的sqrt函数这里行不通，因为n数值太大

这里推荐一种牛顿法求平方根

def closest_integer_sqrt(n):if n == 0:return 0x = n // 2  # 初始猜测while True:new_x = (x + n // x) // 2if new_x >= x:  # 当已有的估计接近真实平方根breakx = new_x# 此时 x 是接近 sqrt(n) 的整数# 检查 (x + 1) 是否更接近if (x + 1) ** 2 - n < n - x ** 2:return x + 1else:return x

脚本代码

from Crypto.Util.number import *
from gmpy2 import*
import math
import decimaldef closest_integer_sqrt(n):if n == 0:return 0x = n // 2  # 初始猜测while True:new_x = (x + n // x) // 2if new_x >= x:  # 当已有的估计接近真实平方根breakx = new_x# 此时 x 是接近 sqrt(n) 的整数# 检查 (x + 1) 是否更接近if (x + 1) ** 2 - n < n - x ** 2:return x + 1else:return xc=8403005375036059507668949476573899369837076550693144629696007329133738521122588246908668180262007583822485069032471230229549770088907327492388166010486964325710415178606379749545343189793702142141767762980168940368804592747996874261288443645015850756539154813150178362722924342723559439994909937372080935730144313164028471482815902766596987410476536851653179862928574243638806370225834643622307886196327090667639015773736760975825026730042601141073120344825434342776953353880893841021796908686865952628635659489153801608107977991641511819655554954728559776830459369692383459501715070991568406261564744500687976022691
d = 1281547902553859084293414419691638897259210312435297418784234419527800281969029795243656339270541966215028646560597711203810636432840182193309150385941111722862919651864511924052800894612960620402770864208616639177876428714431968751785435983752685651775450406691250991111356087508576749134112503921935196726490012713717428813187789532934984608690497645602362447401532583629361369243217877261931238807810829854090482021242655140085436883719126264624674661878500582573099068229419791284814598160647661913954583323359110846608678647386673439063560883714693030315336131614665692294033299011254428100383418733928067811833
e=65537for k in range(1,100000):if (e*d-1)%k==0:print(k)phi=(e*d-1)//kmiddle= closest_integer_sqrt(phi)q=gmpy2.next_prime(middle)try:if phi%(q-1)==0:p=phi//(q-1)+1n=p*qflag=long_to_bytes(pow(c,d,n)).decode()print(flag)breakexcept:continue