S4CTF 2021 | malady

#s4ctf_2021

#!/usr/bin/env sage

from flag import flag

def make_matrix(n):
    Zn = IntegerModRing(n)
    G = GL(2, Zn)
    while True:
        a, b, c, d = [randint(0, n - 1) for _ in range(4)]
        P = G([[a, b], [c, d]])
        if P in G:
            return P

def bpow(P, n):
    if n == 0:
        return P
    for _ in range(n):
        P = P ** 2
    return P

def make_keypair(n):
    Zn = IntegerModRing(n)
    G = GL(2, Zn)
    I = G([[1, 0], [0, 1]])
    r = randint(1, 2 ** 256)
    br = bin(r)[2:][::-1]
    J = I
    while True:
        P, Q = [make_matrix(n) for _ in range(2)]
        try:
            if Q * (~P) != P * Q:
                for i in range(len(br)):
                    if br[i] == '1':
                        J = bpow(Q, i) * J
                B = (~Q) * (~P) * Q
                pubkey = (n, P, B, J)
                privkey = Q
                return (pubkey, privkey)
        except:
            continue

def encrypt(m, pubkey):
    n, P, B, J = pubkey
    Zn = IntegerModRing(n)
    G = GL(2, Zn)
    I = G([[1, 0], [0, 1]])
    s = randint(1, 2 ** 32)
    bs = bin(s)[2:][::-1]
    D = I
    for i in range(len(bs)):
        if bs[i] == '1':
            D = bpow(J, i) * D
    E = (~D) * P * D
    K = (~D) * B * D
    l = len(str(m))
    M = []
    for i in range(0, 4):
        M.append(int(str(m)[i*l // 4: (i+1)*l // 4]))
    U = matrix([[M[1], M[0]], [M[3], M[2]]])
    V = K * U * K
    return (V, E)

p = next_prime(randint(1, 2 ** 72))
q = next_prime(randint(1, 2 ** 72))

n = p * q
pubkey, privkey = make_keypair(n)

flag = flag.encode('utf-8')
m = int(flag.hex(), 16)
enc = encrypt(m, pubkey)

print('pubkey = ', pubkey)
print('enc = ', enc)

overview

• として 一般線形群

  を考えていく

• ランダムな行列 (where ) から、次の計算をする

• • ( は乱数）

  • 

  • ここで が秘密鍵であり、 は公開鍵

• 平文である行列 の暗号化は次のように行われる

• 

• 

• 

• 

• 暗号文のペア

observation

• 復号だが、 がわかれば次のように行える

• • 

  • 

  • 

  • 

• ところでこれは Cayley-Purser Public-key Cryptosystem という暗号方式らしい

solution

• と という2つの式から が計算できる

• と思ったが意外と難しい

solution2

• ケーリーハミルトンの定理 より

• • が成り立ち、 をうまく選べば と言える

• より

• が導けるので、 を求めると がわかる

n, P, B, J =  (2419329577094580148790320061829248654877619, [1181968185527581745853359689584528732855897, 153406550412853584463306785000418170296859,1454322498540966456231711148502103233345812, 1654517770461057329449871572441944497585269], [1268457653971486225679848441105472837265167, 579420771722577779695828127264001257349949, 2351869917091027496266981633084389584522183, 450983777743266243622871312465133743097962], [2358538357277340167153980348659698938509404, 365220208942190647616618122919911425848374, 47691648572918059476944115452005044039782, 1236869052280934587487352533961953209955284])


V, E = [425149944883810928331948322693601721947824, 1442606353540488031613587882680057605691721, 2270690430439772938430962982653361813264189, 1607654191517170510458852398046623728536109], [177396832593088516072893113015799710489963, 2001682469448750676325856357286302774486863, 5338037289866014093970785328310590783999, 239759546300970410440018087181424865073584]


Pinv = ~GL(2, Zmod(n))(P)

P = matrix(Zmod(n), 2, 2, P)
B = matrix(Zmod(n), 2, 2, B)
J = matrix(Zmod(n), 2, 2, J)
Pinv = matrix(Zmod(n), 2, 2, Pinv)
I = matrix.identity(2).change_ring(Zmod(n))

V = matrix(Zmod(n), 2, 2, V)
E = matrix(Zmod(n), 2, 2, E)

a = int(((Pinv*J - J*B) / (B-Pinv))[0,0])

Q = a*I + J
print(Q)

Q = GL(2, Zmod(n))(Q)

Kinv = (~Q) * E * Q
M = Kinv * V * Kinv

print(M)