writeup for 2021AntCTFxD^3CTF Crypto

Posted on Edited on In Word count in article: 14k Reading time ≈ 13 mins.

啊这次的这个比赛因为不会Lattice, 导致基本不会做啊, 虽然比赛后半段去学了也试着做了, 虽然格子造出来还被自己蠢到了, 但还是…收获很多hh

记录一下吧

babylattice

当时做题的时候完全没有看到明文就是一个数字, 并不能转换成有语义的字符串….导致格子都造出来了还一直卡着
但也体会到了一些造格子的方法, 以及格约出向量后需要注意的地方

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import namedtuple
PublicKey = namedtuple('PublicKey', ['n', 'b'])
SecretKey = namedtuple('SecretKey', ['p', 'q', 'A'])
def gen_key():
    p = random_prime(2^512, lbound=2^511)
    q = random_prime(2^512, lbound=2^511)
    n = p * q
    a11, a12, a21 = [random_prime(2^100) for _ in range(3)]
    a22 = random_prime(2^100)
    while a11 * a22 == a12 * a21:
        a22 = random_prime(2^100)
    A = Matrix(ZZ, [[a11, a12], [a21, a22]])
    a1 = crt([a11, a21], [p, q])
    a2 = crt([a12, a22], [p, q])
    b = a1 * inverse_mod(a2, n) % n
    PK = PublicKey(n, b)
    SK = SecretKey(p, q, A)
    return (PK, SK)
def encrypt(m, pk):
    assert 0 < m < 2^400
    r = randint(0, 2^400-1)
    c = (pk.b*m + r) % pk.n
    return c
def decrypt(c, sk):
    a2 = crt([sk.A[0,1], sk.A[1,1]], [sk.p, sk.q])
    s1 = a2 * c % sk.p
    s2 = a2 * c % sk.q
    m, r = sk.A.solve_right(vector([s1, s2]))
    return m
def test(pk, sk, num=3):
    for _ in range(num):
        m = randint(0, 2^400-1)
        c = encrypt(m, pk)
        mm = decrypt(c, sk)
        assert m == mm
if __name__ == '__main__':
    from hashlib import sha256
    from secret import m, FLAG
    assert FLAG == 'd3ctf{%s}' % sha256(int(m).to_bytes(50, 'big')).hexdigest()
    PK, SK = gen_key()
    test(PK, SK)
    c = encrypt(m, PK)
    print(f"PK = {PK}")
    print(f"c = {c}")
"""
PK = PublicKey(n=69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361, b=65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196)
c = 64666354938466194052720591810783769030566504653409465121173331362654665231573809234913985758725048071311571549777481776826624728742086174609897160897118750243192791021577348181130302572185911750797457793921069473730039225991755755340927506766395262125949939309337338656431876690470938261261164556850871338570
"""

出现的参数

  • : 明文,
  • : 密文, 其中
  • 四个都是100-Bit
  • : 512-Bit prime

分析

由可以得到

移项有

考虑到都是未知的, 而且都是400位以下, 尝试构造格子将规约出来

这里的式子左边有三个项, 所以构造一个3维的格子

因为是三维的格子, 所以最短向量的大小大概是

而, 所以需要将格子的放大一点

那么会有

即,存在一个格点, 用LLL规约即可

1
2
3
4
5
6
7
8
9
10
11
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
c = 64666354938466194052720591810783769030566504653409465121173331362654665231573809234913985758725048071311571549777481776826624728742086174609897160897118750243192791021577348181130302572185911750797457793921069473730039225991755755340927506766395262125949939309337338656431876690470938261261164556850871338570

v1 = vector(ZZ, [2^200, 0,c])
v2 = vector(ZZ, [0, 1,-b])
v3 = vector(ZZ, [0, 0,-n])
Lattice = matrix([v1,v2,v3])
m = abs(Lattice.LLL()[0][1])
from hashlib import sha256
print( 'd3ctf{%s}' % sha256(m).hexdigest())

注意到实际格约出来的向量是全负的, 因为也在格子里面, 所以记得加个abs()

预期解

这次的题第一题如果不是做的预期解那么第二题就会特别的难, 所以也顺便学习了一下预期解的做法(出题人预期了非预期解

如果不从入手的话, 就先看看前面几个参数的关系

上面这三个式子, 可以得到这么一个方程组

做到这里的时候, 有想过把方程组的两个式子相乘, 得到的会是

但是这里已知的量只有, 也就是说在这个式子里, 有三项一个已知的都没有, 这样是没办法造格子的, 到这里就卡住了, 不得不翻看wp, 才发现, 原来可以把移到左边再相乘, 这样就只有一个项是未知的了!

记再移一下项

然后就是喜闻乐见的造格子

可以看到右侧的向量长度很短, 可以规约出来

1
(1173142580751247504024100371706709782500216511824162516724129,1382843159437215516163973075066558157591473749635266665605630,-211380743487233628797755584958526337321408979158793229985661)

因为四个都是100位的素数, 直接用http://www.factordb.com分解

因为, 猜一下上面四个数哪两个是就可以得到了, 得到就可以分解, 直接得到所有的参数, 跑解密算法就可以得到明文了

simpleGroup

这题比赛的时候也没做出来(第一题都做不出怎么做这题), 比完赛做了第一题才做这题
啊啊啊但是因为太久没做次幂的运算导致做了好久…….

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from random import randint
from secret import FLAG


# A gift for key recovery in challenge [babyLattice]
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487

M = int.from_bytes(FLAG, 'big')
C = []
while M != 0:
    m = M % e
    M //= e
    r = randint(0, n-1)
    c = power_mod(y, m, n) * power_mod(r, e, n)
    C.append(c % n)

print(f"C = {C}")
"""
C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]
"""

分析

用的还是第一题的, 所以第一题分解出来的这题就有用了

加密的式子大概是 ,都是已知的, 而且

因为是不知道的, 肯定要想办法消去 , (有的师傅不消去也可以做, 待会下面补充一下)

这里的比较特殊,

这意味着我们可以直接计算一个, 使得, 欧拉定理yyds

加密的式子两边来个次幂, 就会有

做到这里想把消去再用bsgs求离散对数, 但因为没有逆元卡了好久, 真的蠢…

这里是已知的, 直接看成, 用bsgs就完事了(用bsgs是因为m的范围是已知的)

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from random import randint
n=69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
C = [...]

a11 = 207806651167586080788016046729
a12 = 1151291153120610849180830073509
p = gcd(b * a12 - a11,n)
q = n // p
phi = (p-1) * (q-1)
M = []

assert gcd(e,phi) == e
d = phi // e
assert pow(pow(randint(0,n-1),e,n),d,n) == 1

bounds = ( 1,e )
F = IntegerModRing(n)
for i in C:
    cd = pow(i,d,n)
    yd = pow(y,d,n)
    M.append(bsgs(F(yd),F(cd),bounds))

flag = 0
for i in M[::-1]:
    flag = int(flag) * int(e) + int(i)

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(flag))

不用消去的解

https://www.anquanke.com/post/id/233827#h2-4, 这位师傅做的

一样先看一下加密的式子

这题有一个特殊的点就是可以被分解为和两个素数，这两个素数又分别是和的因子

所以会有

因为是一个比较小的数, 可以通过遍历, 再判断是否是的次剩余, 就可以得到

同理我们也可以得到

再通过中国剩余定理就能得到了

这里有个素数模的次剩余的判断方法, 很简单, 为模的次剩余的充要条件为

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import *
import gmpy2

p = 7669036313101194621345265255994200133006921565596653797956940811601516306410232120057637504305295677357422367597831138570269733177579895994340511712373309
q = 9102122415165681824420871673621781250311822805618731863628192549895693024247220594372897360668046264863189831887100676431439200352775676467952192600956629
n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
e1 = 36493
e2 = 52859

def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm) 

def check(d,p,n):
    if((p - 1) % n == 0):
        return pow(d,(p - 1) // n,p) == 1
    else:
        k = gmpy2.gcd(n, p - 1)
        return pow(d,(p - 1) // k,p) == 1

def getM(c,e,p):
    for i in range(2,e):
        tmpc = (c * gmpy2.invert(pow(y,i,p),p)) % p
        if check(tmpc,p,e):
            return i
    exit(0)

C = [...]
m = 0
for c in C[::-1]:
    cp = c % p
    cq = c % q
    m1 = getM(cp,e1,p)
    m2 = getM(cq,e2,q)
    mm,lcm = GCRT([e1,e2],[m1,m2])
    print("Get mm: " + hex(mm))
    m *= e
    m += mm

flag = long_to_bytes(m)
print(flag)

后记

这题一点都不难, 做了那么久完全就是脑子没转过来…

耗子尾汁, 好好反思

AliceWantFlag

studying~

EasyCurve

studying~