美团杯——strangeRSA1复现

sage！

strange_rsa1

task

from Crypto.Util.number import *
from sage.all import RealField
from secret import flag1


Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

gift = RealField(prec=Bits*2)(p) / RealField(prec=Bits*2)(q)
e = 0x10001
m = bytes_to_long(flag1)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

此题突破口在gift上，通过RealField()将p，q设定为了1024比特的浮点数。pq之商很明显是一个不知道循环节的无限循环小数，但在RealField(prec=1024)的条件下，只会给出前1024比特

做的时候思路就是将gift这个小数恢复到分数形式，就能得到p，q。所以花了大量的时间在看这个怎么实现，但其实不需要这么做将n也规定为1024比特的浮点数，除以gift后开方，在这个值附近对q进行爆破，当n%q=0时输出

import gmpy2
n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
gift=0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938
n = RealField(prec=1024)(n)
tmp = n / gift
_q = gmpy2.iroot(int(tmp), 2)[0]
print(_q)
for i in range (_q - 10000000, _q + 10000000):
  S = n % i
  if s == 0:
     q = i
     break
print(q)
#q = 10481297369477678688647473426264404751672609241332968992310058598922120259940804922095197051670288498112926299671514217457279033970326518832408003060034369

算出来的q与开方得到的值非常接近，真是太神奇辣

接着就是RSA解密

from Crypto.Util.number import *

n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
q = 10481297369477678688647473426264404751672609241332968992310058598922120259940804922095197051670288498112926299671514217457279033970326518832408003060034369
e = 65537
p = n // q
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#b'flag{a5537b232c1ab750e0db61ec352504a301b7b212}'

Canzik's Blog

美团杯——strangeRSA1复现

strange_rsa1