Litctf-wp

1.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}")

签到题

$\phi(n) = n-1$

rsa解密即可

from Crypto.Util.number import *
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505
phi = n - 1
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

flag:LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

2.ez_math

rom 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(')', ']'))

矩阵RSA，本质上没区别

$B = A^e (GF(p))$

由于在有限域上，相当于就是整数环上的模运算

那么和整数环中的RSA同构

于是计算

$d = e^{-1} \mod p-1$ $flag = B^{d} = A[0][0]$

B = matrix(GF(p),B)
d = inverse(e,p-1)
A = B^d
flag = A[0][0]
print(long_to_bytes(int(flag)))

flag:LitCTF{13dd217e-9a67-4093-8a1b-d2592c45ba82}

3.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}")

注意到

$hint = pq+noise*p+noise*q+noise^2 = n+noise(p+q+noise)$

于是

$hint -n = noise(p+q+noise)$

注意到noise是个小因子，可以通过Pollard-rho等算法求出，不过，这里我直接用factorb了

40位二进制数在十进制约为12位

于是得到了noise，然后就能求出p+q

利用韦达定理构造二次方程，求解即可

$x^2 - (p+q)+pq = 0$

n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164
hint = hint - n
noise = 942430120937
p_q = hint / noise - noise
u = gmpy2.iroot(int(p_q**2 - 4*n),2)[0]
p = (p_q + u) / 2
q = (p_q - u) / 2
phi = (p-1)*(q-1)
d = inverse(e,int(phi))
m = pow(c,d,n)
print(long_to_bytes(m))

flag:LitCTF{db6f52b9265971910b306754b9df8b76}

4.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和t的范围，可以看到t远远小于g，可以考虑规约成格中的SVP问题

$data = tm^{-1} \mod g$

后面简称data为d

$dm - t - kg = 0$

可以造格

$(m,-k) \begin{pmatrix}1 & d \\ 0 &g \end{pmatrix} = (m,t)$

不过这个规约不出来，得调一下系数，让(m,t)成为最短向量

t是150位，简单粗暴，乘以个2^150就行了

$(m,-k) \begin{pmatrix}1 & 2^{150}d \\ 0 &2^{150}g \end{pmatrix} = (m,2^{150}t)$

from Crypto.Util.number import *
import gmpy2

# Given values
g = 7835965640896798834809247993719156202474265737048568647376673642017466116106914666363462292416077666356578469725971587858259708356557157689066968453881547
data = 2966297990428234518470018601566644093790837230283136733660201036837070852272380968379055636436886428180671888655884680666354402224746495312632530221228498
print(data.nbits())
M = Matrix(ZZ,[[1,2^150*data],[0,2^150*g]])
print(M.LLL())
m = abs(M.LLL()[0][0])
print(long_to_bytes(m))

5.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}")

注意到

$temp*e \equiv 1 \mod p-1$

而

$de \equiv 1 \mod (p-1)(q-1)$

子群上

$de \equiv 1 \mod (p-1)$

所以

$temp = d \mod p-1 = dp$

这里dp高位泄露，一开始想的是用常规的dp泄露来做，遍历e求k，然后逐个Coppersmith求小根，但是失败了

后面考虑到

$(dp_{high}+x)e -1 =kp$

那么

$dp_{high}e -1+ex = kp$

不妨记

$dp_{high}e -1 = \widetilde{p}\\ ex -> x$

那么有

$\widetilde{p}+x = kp$

这就是一个最经典的coppersmith问题了

令

$f(x) =\widetilde{p}+x$

f在模p情况下等于0

此事于文献亦有记载，我从此得到灵感

27290027.pdf

这个x，我们自己试验一下

from Crypto.Util.number import *
p,q,e = getPrime(1024),getPrime(1024),getPrime(101)
n = p*q
temp = gmpy2.invert(e,p-1)
hint = temp>>180
dphigh = hint << 180
pw = dphigh*e -1
k = (temp*e - 1)//(p-1)
print(Integer(k*p-pw).nbits())
//279

大概就279,280这样，我们稍微留出几个

求出x，记作x_0之后，

$f(x_0) = kp \\ p=GCD(kp,n)$

exp

from Crypto.Util.number import *
# # from enc import flag
from gmpy2 import *
from tqdm import *
e = 1915595112993511209389477484497
n = 12058282950596489853905564906853910576358068658769384729579819801721022283769030646360180235232443948894906791062870193314816321865741998147649422414431603039299616924238070704766273248012723702232534461910351418959616424998310622248291946154911467931964165973880496792299684212854214808779137819098357856373383337861864983040851365040402759759347175336660743115085194245075677724908400670513472707204162448675189436121439485901172477676082718531655089758822272217352755724670977397896215535981617949681898003148122723643223872440304852939317937912373577272644460885574430666002498233608150431820264832747326321450951
c = 5408361909232088411927098437148101161537011991636129516591281515719880372902772811801912955227544956928232819204513431590526561344301881618680646725398384396780493500649993257687034790300731922993696656726802653808160527651979428360536351980573727547243033796256983447267916371027899350378727589926205722216229710593828255704443872984334145124355391164297338618851078271620401852146006797653957299047860900048265940437555113706268887718422744645438627302494160620008862694047022773311552492738928266138774813855752781598514642890074854185464896060598268009621985230517465300289580941739719020511078726263797913582399
hint = 10818795142327948869191775315599184514916408553660572070587057895748317442312635789407391509205135808872509326739583930473478654752295542349813847128992385262182771143444612586369461112374487380427668276692719788567075889405245844775441364204657098142930
dphigh = hint << 180
F.<x> = PolynomialRing(Zmod(n))
f = int(e*dphigh) + x- 1
f = f.monic()
x0 = f.small_roots(X=2 ^ (282), beta=0.44,episilon = 0.01)[0]
p = GCD(f(x0),n)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

flag:LitCTF{03ecda15d1a89b06454c6050c1bd489f}

6.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()

看上去很普通的一道题，不过卡了挺久的

背包密码，利用的是子集和问题的困难性

给定一个正整数集合

$(pubkey_1,pubkey_2,..pubkey_n)$

以及整数

求子集的和使得

$enc = \sum_{i=1}^nx_ipubkey_i \\ x\in\{0,1\}$

x就是flag的二进制编码

先计算这个背包的密度

$d = \frac{n}{log_2(Max(pubkey))} = \frac{127}{128} \approx 0.992$

？

一般来说，可以使用格密码求解的密度需要小于0.94，这里很明显超了，不太行

卡住了，后面尝试爆破八位

变成

$\frac{120}{128} = 0.9375$

但是，也失败了

后面发现，原来前后缀都已经给定了

我们只需要计算中间部分就行了，那实际上

flag = ‘LitCTF{‘ + ‘’.join(random.choice(characters) for _ in range(length)) + ‘}’

一共16个字节，也就是128位，需要127个数字来表示

去掉前后8个，其实只有63个要解

这直接把d砍半了，完全可行

我们构造这样的格

$\mathcal{L} = \begin{bmatrix}2 & 0 & 0 &\cdots & 0 &pubkey_1 \\0 & 2 & 0 & \cdots & 0 & pubkey_2 \\ 0&0&2&\cdots&0&pubkey_3\\ \vdots & \vdots &\vdots &2 & 0 & pubkey_n \\ 0 & 0 & 0 &\cdots &0 & p \\ 1 & 1 & 1 &\cdots&1 &enc \end{bmatrix}$

考虑线性组合

$t =(x_1,x_2,\cdots,x_n,k,-1)\mathcal{L} = (2x_1-1,2x_2-1,\cdots,2x_n-1,-1,0)$

t显然是格中的向量，而且这里2x_1-1,2x2-1都是-1或者1

显然t的长度是相当小的,使用LLL算法，t应该就是最小的基

于是就回复出x了

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


prev = 'LitCTF{'.encode()
prev_bits = bin(bytes_to_long(prev))[2:]

end = '}'.encode()
end_bits = bin(bytes_to_long(end))[2:]

p = 173537234562263850990112795836487093439
pubkey = [184316235755254907483728080281053515467, 301753295242660201987730522100674059399, 214746865948159247109907445342727086153, 190710765981032078577562674498245824397, 331594659178887289573546882792969306963, 325241251857446530306000904015122540537, 183138087354043440402018216471847480597, 184024660891182404534278014517267677121, 221852419056451630727726571924370029193, 252122782233143392994310666727549089119, 175886223097788623718858806338121455451, 275410728642596840638045777234465661687, 251664694235514793799312335012668142813, 218645272462591891220065928162159215543, 312223630454310643034351163568776055567, 246969281206041998865813427647656760287, 314861458279166374375088099707870061461, 264293021895772608566300156292334238719, 300802209357110221724717494354120213867, 293825386566202476683406032420716750733, 280164880535680245461599240490036536891, 223138633045675121340315815489781884671, 194958151408670059556476901479795911187, 180523100489259027750075460231138785329, 180425435626797251881104654861163883059, 313871202884226454316190668965524324023, 184833541398593696671625353250714719537, 217497008601504809464374671355532403921, 246589067140439936215888566305171004301, 289015788017956436490096615142465503023, 301775305365100149653555500258867275677, 185893637147914858767269807046039030871, 319328260264390422708186053639594729851, 196198701308135383224057395173059054757, 231185775704496628532348037721799493511, 243973313872552840389840048418558528537, 213140279661565397451805047456032832611, 310386296949148370235845491986451639013, 228492979916155878048849684460007011451, 240557187581619139147592264130657066299, 187388364905654342761169670127101032713, 305292765113810142043496345097024570233, 303823809595161213886303993298011013599, 227663140954563126349665813092551336597, 257833881948992845466919654910838972461, 291249161813309696736659661907363469657, 228470133121759300620143703381920625589, 337912208888617180835513160742872043511, 252639095930536359128379880984347614689, 306613178720695137374121633131944714277, 328627523443531702430603855075960220403, 283995291614222889691668376952473718279, 185992200035693404743830210660606140043, 175575945935802771832062328390060568381, 239709736751531517044198331233711541211, 325191992201185112802734343474281930993, 285825734319916654888050222626163129503, 260820892372814862728958615462018022903, 271109638409686342632742230596810197399, 195432366301516284662210689868561107229, 252351678712166898804432075801905414141, 175869608753229067314866329908981554323, 212291732707466211705141589249474157597, 299891357045144243959903067354676661051, 271237385422923460052644584552894282763, 268702576849722796315440463412052409241, 198273535005705777854651218089804228523, 177684355989910045168511400849036259973, 189237944200991357454773904466163557789, 175427967765368330787115337317676160499, 270446056495616077936737430232108222303, 243318639972702711024520926308402316247, 223872107662231922057872197123261908053, 268995355861070998347238198063073079851, 244478236168888494353493404999149985963, 230731375083676409248450208772518041369, 231630208287176700035265642824425872113, 187649298194887119502654724235771449423, 264924369987111619306245625770849264491, 327092811483332202721992798797117253283, 274967838920225995524024619709213673571, 313836314009366857157961838519499192671, 181860768653760352435352944732117309357, 184011200837375425882494435177626368109, 246455975565763627776562816894916143559, 262208917125258935991543552004318662109, 334006940602786701813813048552124976177, 241119397420390120456580389194328607351, 255370083166310325724283692646412327547, 280056982387584554076672702548437488901, 190822826881447578202544631446213911541, 206119293866065537243159766877834200177, 289535246575130471484249052043282790337, 222004375767927951747133364917437739627, 186041951615746748538744491355290007923, 299120276948597373232905692530626175519, 268645812049699572580085139845553457511, 231990902203442306941381714523426756489, 259677531562170067444672097354970172129, 232573792063456357545735601063504090387, 268451806037215206985127877726665463011, 324266632324016349795115268035757999593, 323952615081869295386415078624753400501, 302316593553669781596237136546083536339, 235576231941572491681115931798290883659, 202271277470197960243533508432663735031, 172391954991101354275650988921310984563, 215333185856183701105529790905068832303, 335916893044781805453250006520700519353, 217268288923298532517983372665872329797, 265455575922780577837866687874732212733, 182194442259001995170676842797322170297, 180222796978664332193987060700843734759, 332629077640484670095070754759241249101, 238815683708676274248277883404136375767, 246167709707533867216616011486975023679, 188375282015595301232040104228085154549, 230675799347049231846866057019582889423, 290911573230654740468234181613682439691, 173178956820933028868714760884278201561, 340087079300305236498945763514358009773, 215775253913162994758086261347636015049, 286306008278685809877266756697807931889, 175231652202310718229276393280541484041, 230887015177563361309867021497576716609, 306478031708687513424095160106047572447, 172289054804425429042492673052057816187]
enc = 82516114905258351634653446232397085739
# 分段
pubkey1 = pubkey[:55]
pubkey2 = pubkey[-7:]
pubkey3 = pubkey[55:-7]

# 去掉前后的
enc = (enc - sum(int(prev_bits[i]) * pubkey1[i] for i in range(55))) % p
enc = (enc - sum(int(end_bits[i]) * pubkey2[i] for i in range(7))) % p

# 构造格
n = len(pubkey3)
M = matrix(ZZ, n + 2, n + 2)
for i in range(n):
    M[i, i] = 2
    M[i, -1] = pubkey3[i]
M[-2,-1] = p
M[-1, :-1] = 1
M[-1, -1] = enc

# BKZ 规约
res = M.BKZ(block_size=10)

# 找
for row in res:
    if row[-1] == 0 and all(abs(v) == 1 for v in row[:n]):
        bits = [(1 if v == -1 else 0) for v in row[:n]]  
        mid_bits = ''.join(map(str, bits))
        full_bits = prev_bits + mid_bits + end_bits
        print(long_to_bytes(int(full_bits, 2)))
        break

flag:LitCTF{Am3xItsT}