ASIS CTF Finals 2021 | mDLP

#asisctffinals2021

#!/usr/bin/env sage

from sage.all import *
from Crypto.Util.number import *
from secret import gen_prime, gen_base_matrix, flag

def keygen(nbit, l):
    #
    ## Create the n-bit prime and base square matrix of size l over Ring Z_p
    #
    p = gen_prime(nbit)
    A = gen_base_matrix(p, l)

    d = randint(2, p)
    Q = A ** d
    pubkey = (p, A, Q)
    privkey = d
    return pubkey, privkey

def encrypt(M, pubkey):
    p, A, Q = pubkey
    l = A.nrows()
    assert M.nrows() == l
    r = randint(2, p)
    C, D = A ** r, Q ** r
    E = D * M
    return C, E

def msg_to_matrix(p, msg):
    l = len(msg)
    return matrix(Zmod(p), [[bytes_to_long(msg[0:l//4]), bytes_to_long(msg[l//4:l//2])], 
            [bytes_to_long(msg[l//2:3*l//4]), bytes_to_long(msg[3*l//4:l])]])

nbit, l = 256, 2
pubkey, privkey = keygen(nbit, l)
p, A, Q = pubkey
M = msg_to_matrix(p, flag)
ENC = encrypt(M, pubkey)

print(f'pubkey = {pubkey}')
print(f'ENC = {ENC}')

で が公開されている

暗号化はとして。これは普通のElGamal暗号

ところでが小さい素因数をたくさん持つのでPohlig-Hellman Attackができる。位数がこれで計算できる根拠はわかってない

from Crypto.Util.number import long_to_bytes

p = 94413310751917369305079812653655619566021075449954923397392050181976939189891
A = [
  [38199337272663519912859864066101528484023656231849338967558894235177040565160, 39708167173513090810083500967474691943646789486489990958101592717502452906918],
  [8216211510625558273096642057121313417997488994504871245106775381995665925783, 56213973479253849392219948587554091081997419218105584429833155946799898624740],
]
Q = [
  [61709241598677561125021718690991651934557899286972116933820920757636771220273, 1945367449329759288724720626216309893787847192907494307536759223359193510642],
 [37495232301500074672571996664644922614693962264764098174213150757616575323566, 7348269231944161963123250652171976847627786311806728904368575861561449853500],
]

C = [
  [47566868540912475779105819546118874217903268597017385039977593878486632022506, 86073162301954995219912739344010659248720823814557810528618517154406350653517],
  [23443866424088482893369441934221448179896589659663581973508963775891809430857, 74567333640177484678138574534395714128854315440076840728428649074147859070975],
]
E = [
  [56937964695156855099385034285428853461603799261684034842341841781057485084327, 82459328835322885824854425864023809222717401981993182346342472865578156162544],
  [85092677346274708324092648597361729755305119435989183201786866456596369562681, 22228861714953585357281182780002271505668586948202416054453861940155538803489],
]

def solve_dlp(G, H, upper):
  """
  find x such that G^x == H
  """
  for x in range(upper):
    if G**x == H:
      return x
  raise ValueError("not found")


def pohlig_hellman(g, h, p, limit=100000):
    factors = [f[0]**f[1] for f in (p-1).factor(limit=limit) if f[0] <= limit]
    bs = []
    mods = []
    for f in factors:
        k = (p-1)//f
        print(f, end="->", flush=True)
        b = solve_dlp(g**k, h**k, f)
        print(b)
        bs.append(b)
        mods.append(f)

    return CRT(bs, mods)

A = matrix(GF(p), A)
Q = matrix(GF(p), Q)
C = matrix(GF(p), C)
E = matrix(GF(p), E)

d = pohlig_hellman(A, Q, p)
assert A**d == Q

r = pohlig_hellman(A, C, p)
assert A**r == C

D = Q**r
assert D == C**d

M = D.inverse() * E

print(M)

flag = long_to_bytes(M[0,0]) + long_to_bytes(M[0,1]) + long_to_bytes(M[1,0]) + long_to_bytes(M[1,1])
print(flag)