SECCON 2021 | pppp - crypto-writeup-public

#seccon2021

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

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q

mid = len(flag) // 2

e = 65537

m1 = int.from_bytes(flag[:mid], byteorder='big')
m2 = int.from_bytes(flag[mid:], byteorder='big')

assert m1 < 2**256
assert m2 < 2**256

m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]

# add padding
for i in range(4):
    for j in range(4):
        m[i][j] *= getPrime(768)

m = matrix(Zmod(p*q), m)

c = m^e

print("n =", n)
print("e =", e)
print("c =", list(c))

行列 $m = \begin{bmatrix} p & p & p & p \ 0 & m_1 & m_1 & m_1 \ 0 & 0 & m_2 & m_2 \ 0 & 0 & 0 & 1 \end{bmatrix}$

ただし各要素に何らかのノイズが掛けられている

で、 $m^e \mod N$ が計算されているのでRSAの亜種

$m$ は上三角行列なので $\det{m} = pm_1m_2$

したがって $\det{m^e} = p^em_1^em_2^e$

なので行列式計算して $n$ とgcdとると $p$ が求まる

あるいは、 $m^e = \begin{bmatrix} p^e & \ 0 & m_1^e & \ 0 & 0 & m_2^e \ 0 & 0 & 0 & 1 \end{bmatrix}$

であることを利用しても良い

$p, q$ がわかれば単純に複号すればいい。適当な係数がかかっているので、エイヤで復号してgcdをとる

位数は一般線形群の項に載っている方法で計算できる

import ast
from Crypto.Util.number import long_to_bytes
with open("output.txt") as f:
    n = ast.literal_eval(f.readline().strip().split(" = ")[1])
    e = ast.literal_eval(f.readline().strip().split(" = ")[1])
    c = ast.literal_eval(f.readline().strip().split(" = ")[1])

C = matrix(Zmod(n), c)
p = int(gcd(C[0, 0], n))
q = n // p

def order_glfp(n, p):
    order = 1
    for i in range(n):
        order *= (p**n - p**i)
    return order

order = order_glfp(4, p) * order_glfp(4, q)
d = inverse_mod(e, order)
M = C**d

flag1 = gcd(int(M[1,1]), int(M[1,2]))
flag2 = gcd(int(M[2,2]), int(M[2,3]))
print(long_to_bytes(flag1) + long_to_bytes(flag2))

実装上の注意：flag1 を求めるときにintを書かないとZn上のgcdが発生して1になってしまう