2024-N1CTF-crypto-n0tr5a

n0tr5a

题目

It's not RSA!

---

from Crypto.Util.number import *
from secret import flag

def gen(nbit, m):
    kbit = int(nbit * 0.4512)
    key = getPrime(kbit)
    
    while True:
        p = getPrime(nbit // 2 - 1)
        if isPrime(p * 2 + 1):
            p = p * 2 + 1
            break
    while True:
        q = getPrime(nbit // 2 - 1)
        if isPrime(q * 2 + 1):
            q = q * 2 + 1
            break   
    n = p * q
    phi = (p - 1) * (q - 1)
    
    e, k = [], []
    for i in range(m):
        dd = key + 2 * i + 2
        ee = inverse(dd, phi)
        kk = (ee * dd - 1) // phi
        e.append(ee % 2 ** (nbit - kbit))
        k.append(kk)
    
    return n, e, k

n, e, k = gen(1024, 12)
enc = pow(bytes_to_long(flag), 65537, n)

with open("data.txt","w") as f:
    f.write(f"{n = }\n{enc = }\n{e = }\n{k = }\n")

---

n = 82699881935193109791472212259236125591789180928354081401868164018417228277481034922264132029171387301840769422435233519725339633533151517379984801310897094212731380971539763520078187279519479595450340858225632773423726273875857681742976022998251134553236897670416440247498103588885527592983304472279634643957
enc = 36794479248642872612364238056628323098776595394584051168003253681308381469543148020365981382945118247106425767548419728448043683874348775891060829403456974633618540620271474325940287199561651410530249693150249056719801828452373946254944967790634308791835260415588851915975925342336816758487259438650490430459
e = [8888429835496095643535631191491505388277997809079089914782728064936463291203724475916011147975968533541243766266627762336328575049254500085648004975612619037464278832991, 10520875896679093312405671804517920324087646023792222747154447628464758710245963882871820387158134686949159913616463457692301596583039366392879522319633770989600617793993, 10601203527211713579180750988795815135916059018550710650265113080975290409723984434909955571406050178911560767494058644740527759576770265488136304573804742084915697171019, 14622236712746402638071905642098139610445903171562565245220543995502178907758821801160631615531163735803555926497329822620058537286662778517871290983128596096302228266209, 13754445300340270191221556210805776985685382903218031894668871565239317628261744219992643635369635181508144912605084390638097003753479943161757716583483371428111258641999, 12460010632813615553769774340135585477760327095310449594534663078794374775415503111884611193451554799744919010772785354797945533347796386998533715641130155450020923742093, 13453716597070478297648899092689370236302303280643930607214496697603184305419894290940911668951264509281914356651376372996746606791176528956862446530034762390956440975743, 9094611196190891372488960864378207737592838879869747718773801183985658899847575852673983345117604950170885723017205969782710348697632364573814601979741607809886580452089, 6208536025163051261514520489326917558898635960331271412905419257732637120279699170648486672913828237574848376496958272367037120192950777084064981617441543021966571267615, 12222783896133215551045666761401890068457062194802465729916062142356007806837055121210344156062210736292529151537109874603945090163748106129066462428445187619153477674477, 12614188721315363674299785508736495244859114088280924894674179341352352570584522323159835229814636248801721832488735354744616443270824945572498647598651837749451947061719, 1152998684313785798360794952776294245536465631931933802028441841686020994002404128005468864877622660410537371162754781745360983347732927142593427077571775783417497297097]
k = [1420437810145904840211095643676412643944076218177458138046274525430773202929328250820697290122977318065170030510975153884301846687954934017, 3940861961324077864997765290105972644424759701256821322813075596188909751606433001282290039081974406373664979502491212469917425748074824949, 9413004926123376989637174399517514326721338378609741980303584526041973145706068370477394363722601798762946415087687748257511626645382494821, 7428184730507734867291435325705251542125906508735340171046981085055137680467341685699246562820294813340827360115146667698628846494205603434, 5807754291508765665701362465833864063188458758878871682965086597196662689504909848658274758620320439529911831751168255058459646445501084679, 4757450447044159731910445277826227301213629775871240625040932054281107227037248484860063739616068171487636025286033326826668030840136004650, 5996697334509086666652114545471399499880715834871318018958944856630439665570432872031097645146070471243016581178433327374429447296670643144, 34948977643936917247938455046939890895031986466384330025838204273490152867215005144463212975331851051065343323158463423475270019458998722, 2108517589993394132588916598627794212409854321151001283809351367884838987309441276260578523735992656738890197115589763805165681991611220869, 7529989400759036686155222444072464272422956186987614547747593414852898515920566835606491795646900457120392171067632339816915038614860409008, 5919516150531691402185931957988063032510639008912552676259537229103356758278878266990953285696298526725065525943655778090084815308411600528, 6143553530848821997030657441615076975797083210691917101599644261591827822351051233391184584862183963084085114519636359680935327311007033284]

1. 理解RSA加密和密钥生成

RSA加密的核心是利用大整数的因数分解困难性。在这个问题中，首先生成一个462位的素数key，然后生成两个512位的安全素数p和q。这些素数被用来构造RSA的模数n = p * q，其位数为1024位。

2. 生成公钥和私钥

对于每个hint，生成一个公钥指数e和一个私钥指数k。公钥指数e是通过计算dd（key加上一个与轮次相关的值）关于phi(n)的模逆得到的，然后对2^(nbit - kbit)取模，这里nbit - kbit = 562。私钥指数k是通过计算(ee * dd - 1) // phi得到的。

3. 构造线性同余方程组

根据题目中的提示，我们可以构造一个线性同余方程组。每个hint提供了一个关于e和k的方程，这些方程可以被用来构造一个线性方程组。这个方程组的形式是：
$$
ee_{i,l} \cdot (key + 2i + 2) = 1 + kk_i(n + 1 - (p + q)) \pmod{2^{562}}
$$

4. 应用LLL算法

LLL算法被用来解决这个线性同余方程组。通过将方程组转化为矩阵形式，LLL算法可以找到这个矩阵的短向量，这些短向量对应于方程组的解。在这个过程中，p + q和key在模2^{562}下都不大，这使得LLL算法能够有效地找到解。

5. 解密RSA密文

一旦我们通过LLL算法找到了p和q的值，我们就可以计算出n = p * q和phi(n) = (p-1)(q-1)。然后，我们可以计算出私钥d，它是公钥指数e关于phi(n)的模逆。最后，使用私钥d来解密RSA密文。

6. 实现和测试

实现上述过程需要编写代码来生成密钥对、构造线性同余方程组、应用LLL算法，并最终解密密文。这需要对Python的加密库和数学库有深入的了解，以及对LLL算法的实现。

from Crypto.Util.number import *
from gmpy2 import *

kbit = int(1024 * 0.4512)
n = 82699881935193109791472212259236125591789180928354081401868164018417228277481034922264132029171387301840769422435233519725339633533151517379984801310897094212731380971539763520078187279519479595450340858225632773423726273875857681742976022998251134553236897670416440247498103588885527592983304472279634643957
enc = 36794479248642872612364238056628323098776595394584051168003253681308381469543148020365981382945118247106425767548419728448043683874348775891060829403456974633618540620271474325940287199561651410530249693150249056719801828452373946254944967790634308791835260415588851915975925342336816758487259438650490430459
e = [8888429835496095643535631191491505388277997809079089914782728064936463291203724475916011147975968533541243766266627762336328575049254500085648004975612619037464278832991, 10520875896679093312405671804517920324087646023792222747154447628464758710245963882871820387158134686949159913616463457692301596583039366392879522319633770989600617793993, 10601203527211713579180750988795815135916059018550710650265113080975290409723984434909955571406050178911560767494058644740527759576770265488136304573804742084915697171019, 14622236712746402638071905642098139610445903171562565245220543995502178907758821801160631615531163735803555926497329822620058537286662778517871290983128596096302228266209, 13754445300340270191221556210805776985685382903218031894668871565239317628261744219992643635369635181508144912605084390638097003753479943161757716583483371428111258641999, 12460010632813615553769774340135585477760327095310449594534663078794374775415503111884611193451554799744919010772785354797945533347796386998533715641130155450020923742093, 13453716597070478297648899092689370236302303280643930607214496697603184305419894290940911668951264509281914356651376372996746606791176528956862446530034762390956440975743, 9094611196190891372488960864378207737592838879869747718773801183985658899847575852673983345117604950170885723017205969782710348697632364573814601979741607809886580452089, 6208536025163051261514520489326917558898635960331271412905419257732637120279699170648486672913828237574848376496958272367037120192950777084064981617441543021966571267615, 12222783896133215551045666761401890068457062194802465729916062142356007806837055121210344156062210736292529151537109874603945090163748106129066462428445187619153477674477, 12614188721315363674299785508736495244859114088280924894674179341352352570584522323159835229814636248801721832488735354744616443270824945572498647598651837749451947061719, 1152998684313785798360794952776294245536465631931933802028441841686020994002404128005468864877622660410537371162754781745360983347732927142593427077571775783417497297097]
k = [1420437810145904840211095643676412643944076218177458138046274525430773202929328250820697290122977318065170030510975153884301846687954934017, 3940861961324077864997765290105972644424759701256821322813075596188909751606433001282290039081974406373664979502491212469917425748074824949, 9413004926123376989637174399517514326721338378609741980303584526041973145706068370477394363722601798762946415087687748257511626645382494821, 7428184730507734867291435325705251542125906508735340171046981085055137680467341685699246562820294813340827360115146667698628846494205603434, 5807754291508765665701362465833864063188458758878871682965086597196662689504909848658274758620320439529911831751168255058459646445501084679, 4757450447044159731910445277826227301213629775871240625040932054281107227037248484860063739616068171487636025286033326826668030840136004650, 5996697334509086666652114545471399499880715834871318018958944856630439665570432872031097645146070471243016581178433327374429447296670643144, 34948977643936917247938455046939890895031986466384330025838204273490152867215005144463212975331851051065343323158463423475270019458998722, 2108517589993394132588916598627794212409854321151001283809351367884838987309441276260578523735992656738890197115589763805165681991611220869, 7529989400759036686155222444072464272422956186987614547747593414852898515920566835606491795646900457120392171067632339816915038614860409008, 5919516150531691402185931957988063032510639008912552676259537229103356758278878266990953285696298526725065525943655778090084815308411600528, 6143553530848821997030657441615076975797083210691917101599644261591827822351051233391184584862183963084085114519636359680935327311007033284]

L = Matrix(ZZ, 3+len(e), 3+len(e))
for i in range(3):
    L[i,i] = 1
for i in range(len(e)):
    Ci = e[i]*(2*i+2) - 1 - k[i]*(n+1)
    L[0, 3+i] = e[i]
    L[1, 3+i] = k[i]
    L[2, 3+i] = Ci
for i in range(len(e)):
    L[-i-1,-i-1] = 2^(1024 - kbit)
L[0,0] = 2^(513-kbit)
L[2,2] = 2^513
L[:,3:] *= n

res = L.LLL()[0]
key = abs(res[0])
pplusq = abs(res[1])

pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p
d = inverse(65537,(p-1)*(q-1))
assert p*q == n
print(long_to_bytes(int(pow(enc,d,n))))

#n1ctf{7hE_Br1l1!4nCe_0f_D5tErm1Nan7_4Nd_C0PP5R4m|Th!}

这个解题过程展示了如何利用RSA加密的数学原理和LLL算法来解决一个复杂的密码学问题。通过构造和解决线性同余方程组，我们可以找到加密密钥，从而解密RSA密文。这种方法不仅需要数学知识，还需要编程技能来实现算法和处理大整数运算。参考以下博客：https://tangcuxiaojikuai.xyz/post/cd7e8e10.html#more（用到了sage11环境）