好题分享系列:fractRSA

密码学 9个月前 admin
107 0 0
首先声明,这个系列所分享的“好题” 仅代表我个人在解这道题时可能觉得这道题某一个知识点很有趣;或是很新颖;或是出题人对这道题各个知识点的衔接处理的很好,而不是单纯套娃;或是看了出题人的题解觉得特别优雅,或是觉得自己的解法很妙…… 但并不保证这道题目的实时性、原创性,可能我看到这道题的时候它已经是被抄袭过的,但我并没有遇到过原题。(题好,但不对比赛给予评价)另外为了避免纯粹的拿来主义,以给读者一定的思考、操作空间,这个系列也不会直接给出完整的解题 exp,大家自己也多试试叭!
今天这道题目来自 2023 网信柏鹭杯 – fractRSA

题目内容

#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 上了。
题目还给出了几个关系 ,其中 且是两个 512 比特的素数;
另外

心路历程

显然我们要从 leaknum3 入手。根据  ,我们有

由于 num1 是素数,再走一个费马小定理,我们有

因此我们如果能知道 num1 我们就能够得到 的值(正常来说 肯定是小于 num1 的,所以直接 就会是 的值了,然后再根据 ,解一个方程组就可以得到 了,后面就没啥了。
那么现在题目的重点就在于如何根据 恢复 num1 了。

本地测试

理论上 是一个有理数,由于 num1,num2 都是素数,所以应该也是个无限循环小数。不过虽然这里用的精度已经比较高了 ring = RealField(1100),但还是没走到它的循环节,仍然是有误差。不过这么高的精度,应该也能做一些事情了。
尝试通分一下,我们直接使用 sagemath,里头有一个 QQ,代表有理数的类型。例如我们定义 ,直接走一个 ,就能直接出来
sage: a=0.25
sage: a
0.250000000000000
sage: QQ(a)
1/4
那么我们直接对 num3 应用一下呢?
sage: ring = RealField(1100)
sage: QQ(ring(num3))
27714495913865858197112266003296632001404181823697534106211762432621951228420396951285629763840231667318552711317747751803736439799704150681657112217837660033921787582191772736/22460906974269151983527383579480274910002322616837987158437326900881916880800182097205056972191314686835849128639740399117553858122602145347590837862015308594141255394793343627
好像还挺像那么回事儿的,不过这个分子显然不是一个素数啊。再看到这个分子分母的比特长度
sage: de = 224609069742691519835273835794802749100023226168379871584373269008819
....: 16880800182097205056972191314686835849128639740399117553858122602145347590
....: 837862015308594141255394793343627
sage: de.nbits()
583
也不符合我们 512 比特的预期。想来估计是这点儿误差造成的。怎么办呢?怎么办呢?怎么用一个分数近似地表示一个无限小数呢?而且对分子分母的长度还有一定要求。
不觉得有一个工具非常适配么?连分数哇!还没接触过连分数的读者可以先去我博客的文章(密码学学习笔记之连分数)看看,当然,网上的资料也已经有很多了。
于是我们直接进行一手对 num3 连分数的算,对收敛分数的取:
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
bingo ! 点到为止。


原文始发于微信公众号(Van1sh):好题分享系列:fractRSA

版权声明:admin 发表于 2023年10月12日 下午12:03。
转载请注明:好题分享系列:fractRSA | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...