题目内容
#python3
import sys
sys.path.append("..")
from Crypto.Util.number import *
from random import *
from sage.all import *
from secret import flag1 as flag
num1 = 3
num2 = 5
while(num1<num2):
num1 = getPrime(512)
num2 = getPrime(512)
pt = bytes_to_long(flag) + num2
ring = RealField(1100)
num3 = ring(num1) / ring(num2)
print("num3 = ", num3)
while True:
p = randint(2**511, num1)
q = randint(2**511, num2)
if isPrime(p) and isPrime(q) and p!=q:
break
N = p*q
e = 65537
leak = pow(p-q, num1, num1*num2)
ct = pow(pt, e, N)
print("ct = ", ct)
print("N = ", N)
print("leak = ", leak)
"""
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393
N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673
leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371
"""
num3,ct,N,leak 其中 ct,N 是 RSA 的密文和模数，基本没什么可操作的空间，因此重点就在 num3,leak 上了。心路历程
leak 和 num3 入手。根据 ，我们有
num1 是素数，再走一个费马小定理，我们有
num1 我们就能够得到 的值（正常来说 肯定是小于 num1 的，所以直接 就会是 的值了，然后再根据 ，解一个方程组就可以得到 了，后面就没啥了。num1 了。本地测试
num1,num2 都是素数，所以应该也是个无限循环小数。不过虽然这里用的精度已经比较高了 ring = RealField(1100)，但还是没走到它的循环节，仍然是有误差。不过这么高的精度，应该也能做一些事情了。sage: a=0.25
sage: a
0.250000000000000
sage: QQ(a)
1/4
sage: ring = RealField(1100)
sage: QQ(ring(num3))
27714495913865858197112266003296632001404181823697534106211762432621951228420396951285629763840231667318552711317747751803736439799704150681657112217837660033921787582191772736/22460906974269151983527383579480274910002322616837987158437326900881916880800182097205056972191314686835849128639740399117553858122602145347590837862015308594141255394793343627
sage: de = 224609069742691519835273835794802749100023226168379871584373269008819
....: 16880800182097205056972191314686835849128639740399117553858122602145347590
....: 837862015308594141255394793343627
sage: de.nbits()
583
from sympy import isprime
num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956
for yx in continued_fraction(num3).convergents():
y = yx.numerator()
x = yx.denominator()
if y.nbits() == 512:
assert isprime(x) and isprime(y)
print("[+] ",x,y)
[+] 9050477566333038464101590216458863799039754468566791821195736389139213194857548339787600682491327798736538059818887575696704421576721592454156775006222517 11167377337790397338811417806698264734026040696284907854286100186126887838302430726803014418419121360514985339992064951270502853852777225947659429837569693
原文始发于微信公众号（Van1sh）：好题分享系列：fractRSA
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论