2025-LitCTF-crypto

水个博客

basic

题目：

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

m = bytes_to_long(flag)
n = getPrime(1024)
e = 65537
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

'''
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505
'''

n是素数 $phi(n) = n - 1$
exp：

from Crypto.Util.number import *


n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505

phi = n-1

d = inverse(e,phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

ez_math

题目：

from sage.all import *
from Crypto.Util.number import *
from uuid import uuid4

flag = b'LitCTF{'+ str(uuid4()).encode() + b'}'
flag = bytes_to_long(flag)
len_flag = flag.bit_length()
e = 65537
p = getPrime(512)
P = GF(p)
A = [[flag,                 getPrime(len_flag)],
     [getPrime(len_flag),   getPrime(len_flag)]]
A = matrix(P, A)
B = A ** e

print(f"e = {e}")
print(f"p = {p}")
print(f"B = {list(B)}".replace('(', '[').replace(')', ']'))

# e = 65537
# p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869
# B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]

其实就可以当rsa做，求出来e的逆元
只不过要查一下这个phi是多少

exp：

from Crypto.Util.number import *

e = 65537
p = 8147594556101158967571180945694180896742294483544853070485096002084187305007965554901340220135102394516080775084644243545680089670612459698730714507241869
B = [[2155477851953408309667286450183162647077775173298899672730310990871751073331268840697064969968224381692698267285466913831393859280698670494293432275120170, 4113196339199671283644050914377933292797783829068402678379946926727565560805246629977929420627263995348168282358929186302526949449679561299204123214741547], [3652128051559825585352835887172797117251184204957364197630337114276860638429451378581133662832585442502338145987792778148110514594776496633267082169998598, 2475627430652911131017666156879485088601207383028954405788583206976605890994185119936790889665919339591067412273564551745588770370229650653217822472440992]]

B = Matrix(GF(p),B)
phi = p*(p-1)*(p+1)
d = inverse(e,phi)
A = B^d
print(A)
m = A[0][0]
print(long_to_bytes(int(m)))
# LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}

Math

题目：

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

m = bytes_to_long(flag)
e = 65537
p,q = getPrime(1024),getPrime(1024)
n = p*q
noise = getPrime(40)
tmp1 = noise*p+noise*q
tmp2 = noise*noise
hint = p*q+tmp1+tmp2
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint = {hint}")
'''
n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164
'''

通过下式：

tmp1 + tmp2 = hint - n = noise(noise - (p + q))

noise只有40bit，尝试使用factordb分解，得到noise

再解方程即可
exp：

from Crypto.Util.number import *
n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164
print(hint-n)
# http://www.factordb.com/
noise = 942430120937
assert (hint - n) % noise == 0
p_q = (hint - n) //noise - noise
from sympy import *
f1, f2 = symbols("f1, f2")
f_solve = solve([f1 * f2 - n, f1  + f2   - p_q], [f1, f2])
print(f_solve)
# [(129112612387117168544548806594598239723269413018237311103183364923990952496526515359646206873258782817688219175077148783763135197336175176198298490617680613026041422778023211198065691901359818038571796833717316365956740856517956965885218769221109327995041603982486823929701783921298556945214132214551199668201, 135792238734020752402738279887728641662483275687137578306012881706639817605483435282163392435044240115684744622670586400181099625735464730483356502221026546220369148578684544694242743301595862672216732669599901182387427975535652315677229160320057058067529240344722506162893596721678195275652905002409883036941), (135792238734020752402738279887728641662483275687137578306012881706639817605483435282163392435044240115684744622670586400181099625735464730483356502221026546220369148578684544694242743301595862672216732669599901182387427975535652315677229160320057058067529240344722506162893596721678195275652905002409883036941, 129112612387117168544548806594598239723269413018237311103183364923990952496526515359646206873258782817688219175077148783763135197336175176198298490617680613026041422778023211198065691901359818038571796833717316365956740856517956965885218769221109327995041603982486823929701783921298556945214132214551199668201)]

p = 129112612387117168544548806594598239723269413018237311103183364923990952496526515359646206873258782817688219175077148783763135197336175176198298490617680613026041422778023211198065691901359818038571796833717316365956740856517956965885218769221109327995041603982486823929701783921298556945214132214551199668201
q = 135792238734020752402738279887728641662483275687137578306012881706639817605483435282163392435044240115684744622670586400181099625735464730483356502221026546220369148578684544694242743301595862672216732669599901182387427975535652315677229160320057058067529240344722506162893596721678195275652905002409883036941
phi = (p-1)*(q-1)
d = inverse(e,phi)

m = pow(c , d , n)
print(long_to_bytes(m))
# LitCTF{db6f52b9265971910b306754b9df8b76}

baby

题目：

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


m = bytes_to_long(flag)
g = getPrime(512)
t = getPrime(150)
data = (t * gmpy2.invert(m, g)) % g
print(f'g = {g}')
print(f'data = {data}')
'''
g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547
data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498
'''

看题目觉得是ntru

data = t * m^{-1} + kg

m = t * data ^{-1} + kg

造格：

(t, k) \left( \begin{matrix} 2^{170} & data ^{-1} \\ 0 &g \\ \end{matrix} \right) = (2^{170} t, m)

exp：

from Crypto.Util.number import *

import gmpy2
from Crypto.Util.number import *

p = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547
h = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498

L = Matrix(ZZ, [[2^170, inverse(h,p)],
                [0, p]])

t, m = L.LLL()[0]


print(long_to_bytes(abs(m)))
# LitCTF{56008a819331c9f3608a718327b7e6ce}

Leak

题目：

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

m = bytes_to_long(flag)
p,q,e = getPrime(1024),getPrime(1024),getPrime(101)
n = p*q
temp = gmpy2.invert(e,p-1)
c = pow(m,e,n)
hint = temp>>180
print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")
print(f"hint = {hint}")
'''
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
'''

通过下式：

0 \equiv 1 - k - dp \cdot e \ (\text{mod } p)

$k$ 和 $d_l$ 都是小数，进行二元copper
exp：

from Crypto.Util.number import long_to_bytes
import itertools


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    k = ZZ(f.coefficients().pop(0))
    g = gcd(k, N)
    k = R(k / g)

    f *= 1 / k
    f = f.change_ring(ZZ)

    vars = f.variables()
    G = Sequence([], f.parent())
    for k in range(m):
        for i in range(m - k + 1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                g = f ** k * prod(subvars) * N ** (max(d - k, 0))
                G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, Integer(1) / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []


e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
dp_high = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930

PR.<x,k> = PolynomialRing(Zmod(n), 2)
f = 1 - k - ((dp_high << 180) + x) * e

x, k = small_roots(f, [2 ** 180, 2 ** 101], m=4, d=1)[0]

p = gcd(int(f(x, k)), n)
q = int(n) // int(p)
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(c, int(d), n)
print(long_to_bytes(int(m)))
# LitCTF{03ecda15d1a89b06454c6050c1bd489f}

new_bag

题目：

from Crypto.Util.number import *
import random
import string

def get_flag(length):
    characters = string.ascii_letters + string.digits + '_'
    flag = 'LitCTF{' + ''.join(random.choice(characters) for _ in range(length)) + '}'
    return flag.encode()


flag = get_flag(8)
print(flag)
flag = bin(bytes_to_long(flag))[2:]

p = getPrime(128)
pubkey = [getPrime(128) for i in range(len(flag))]
enc = 0
for i in range(len(flag)):
    enc += pubkey[i] * int(flag[i])
    enc %= p
f = open("output.txt", "w")
f.write(f"p = {p}\n")
f.write(f"pubkey = {pubkey}\n")
f.write(f"enc = {enc}\n")
f.close()

去掉flag头和尾，只剩8字符未知，造格

\begin{pmatrix} 1 & 0 & … & 0 & 0 &key_1\\ 0 & 1 & … & 0 & 0 & key_2\\ \vdots & \vdots & \ddots & \vdots & \vdots &\vdots \\ 0 & 0 & … & 1 &0 & key_n\\ 0 & 0 & … & 0 & 1 & c \\ 0 & 0 & … & 0 & 0 & p \end{pmatrix}