首先声明，这个系列所分享的“好题” 仅代表我个人在解这道题时可能觉得这道题某一个知识点很有趣；或是很新颖；或是出题人对这道题各个知识点的衔接处理的很好，而不是单纯套娃；或是看了出题人的题解觉得特别优雅，或是觉得自己的解法很妙…… 但并不保证这道题目的实时性、原创性，可能我看到这道题的时候它已经是被抄袭过的，但我并没有遇到过原题。 （题好，但不对比赛给予评价）另外为了避免纯粹的拿来主义，以给读者一定的思考、操作空间，这个系列也不会直接给出完整的解题 exp，大家自己也多试试叭！
今天这道题目来自 2023 网信柏鹭杯 - fractRSA
题目内容
12345678910111213141516171819202122232425262728293031323334353637383940 |
#python3import sys sys.path.append("..") from Crypto.Util.number import *from random import *from sage.all import *from secret import flag1 as flagnum1 = 3num2 = 5while(num1<num2): num1 = getPrime(512) num2 = getPrime(512)pt = bytes_to_long(flag) + num2ring = 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: breakN = p*qe = 65537leak = pow(p-q, num1, num1*num2)ct = pow(pt, e, N)print("ct = ", ct)print("N = ", N)print("leak = ", leak)"""num3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956ct = 31011170589632318837149853165664224847925206003567781692767655474759523146503572164952138829336342836023903919700264739071138739105931471740973631326608186969523753119546323993892359278563753903149741128282349467136720827132122619177620866305659196267641453819504766216964516467658995724859657544518337771393N = 61860727516406742636690805639158184396057779906729165734489212939937929906456706343476469874085504076991779041906401043694401076841639925611957258119417559980829238154105119701407722069260962772947894516879731956778127512764229384957918619863998939985369399189275568362193066167855420897196095587732512368673leak = 23213363443983005040318061737977092634638640953366787443691593387275645092922646169818923792205696350020369122807136306157118385984272980615310163206933078119776935167207473544453080959202803743994251355133953187110546017667004996272367137522351606700447920805532616096125523674597551449412004735397779511371""" |
题目给出了四个输出 num3,ct,N,leak 其中 ct,N 是 RSA 的密文和模数，基本没什么可操作的空间，因此重点就在 num3,leak 上了。
题目还给出了几个关系 $num3 = \frac{num1}{num2}$，其中 $num1>num2$ 且是两个 512 比特的素数；
另外 $leak \equiv (p-q)^{num1} \pmod {num1\cdot num2}$
心路历程
显然我们要从 leak 和 num3 入手。根据 $leak \equiv (p-q)^{num1} \pmod {num1\cdot num2}$，我们有$$leak \equiv (p-q)^{num1} \pmod {num1}$$由于 num1 是素数，再走一个费马小定理，我们有$$leak \equiv p-q \pmod {num1}$$因此我们如果能知道 num1 我们就能够得到 $p-q$ 的值（正常来说 $p-q$ 肯定是小于 num1 的，所以直接 $leak \pmod {num1}$ 就会是 $p-q$ 的值了，然后再根据 $N = p\cdot q$，解一个方程组就可以得到 $p,q$ 了，后面就没啥了。
那么现在题目的重点就在于如何根据 $num3 = \frac{num1}{num2}$ 恢复 num1 了。
本地测试
理论上 $\frac{num1}{num2}$ 是一个有理数，由于 num1,num2 都是素数，所以应该也是个无限循环小数。不过虽然这里用的精度已经比较高了 ring = RealField(1100)，但还是没走到它的循环节。不过这么高的精度，应该也能做一些事情了。
尝试通分一下，我们直接使用 sagemath，里头有一个 QQ，代表有理数的类型。例如我们定义 $a=0.25$，直接走一个 $QQ(a)$，就能直接出来 $\frac{1}{4}$
12345 |
sage: a=0.25sage: a0.250000000000000sage: QQ(a)1/4 |
那么我们直接对 num3 应用一下呢？
123 |
sage: ring = RealField(1100)sage: QQ(ring(num3))27714495913865858197112266003296632001404181823697534106211762432621951228420396951285629763840231667318552711317747751803736439799704150681657112217837660033921787582191772736/22460906974269151983527383579480274910002322616837987158437326900881916880800182097205056972191314686835849128639740399117553858122602145347590837862015308594141255394793343627 |
好像还挺像那么回事儿的，不过这个分子显然不是一个素数啊。再看到这个分子分母的比特长度
12345 |
sage: de = 224609069742691519835273835794802749100023226168379871584373269008819....: 16880800182097205056972191314686835849128639740399117553858122602145347590....: 837862015308594141255394793343627sage: de.nbits()583 |
也不符合我们 512 比特的预期。想来估计是这点儿误差造成的。怎么办呢？怎么办呢？怎么用一个分数近似地表示一个无限小数呢？而且对分子分母的长度还有一定要求。
不觉得有一个工具非常适配么？连分数哇！还没接触过连分数的读者可以先去我博客的这篇文章看看，当然，网上的资料也已经有很多了。
于是我们直接进行一手对 num3 连分数的算，对收敛分数的取：
1234567891011 |
from sympy import isprimenum3 = 1.23389923415003373900567515471436168841941584796842188964423737295914869304653496800649965063081353720701415762591488370228399019899893688681309320356016722276295236528757306976510687729729934668311830828756908988350841843676900575414367123810470585198055372776278588638204471298838884740198056387082949710435502826460830711429956for 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 |
bingo ! 点到为止。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论