N1CTF 2020 | babyproof - crypto-writeup-public

from hashlib import sha256

from Crypto.Util.number import getRandomRange
from Crypto.PublicKey import DSA

from secret import proof_of_work, flag


x = int.from_bytes(flag, 'big')
assert x.bit_length() == 247


def baby_proof():
    key = DSA.generate(3072)  # It takes time to generate, plz be patient...
    p, q, g = key.domain()
    y = pow(g, x, p)

    v = getRandomRange(1, x)
    t = pow(g, v, p)

    gyt = b"".join(
        map(
            lambda x: int.to_bytes(len(str(x)), 4, 'big') + str(x).encode(),
            (g, y, t)
        ))
    c = int.from_bytes(sha256(gyt).digest(), 'big')
    r = (v - c*x) % q

    print("I want to prove to you that I am in the knowledge of the discrete "
          "logarithm x that satisfies g^x = y modulo p, with the order of g "
          "modulo p being q.")
    print("However, I don't want to leak any information about x.")
    print("So, I use a non-interactive zero-knowledge proof for my purpose.")
    print("=================================================================")
    print("Here is my proof: ")
    print("Firstly, I choose a random (secret) v and compute t = g^v in Zq.")
    print("Secondly, I compute c = SHA256(g, y, t).")
    print("Then, I compute r = v - cx modulo q.")
    print("Finally, I will send you my proof (t, r).")
    print("You can check it by determining whether t == g^r * y^c or not.")
    print("Since there's negligible probability that I could forge the value "
          "r, you should believe that I really have knowledge of x.")
    print(g, y, p, q, t, r, sep="\n")


if __name__ == "__main__":
    if proof_of_work():
        baby_proof()

DSAを使ったzkpの問題。特に非対話なやつはnon interactve zkp って言われるけど限られた条件でしか有効じゃない。

さて、問題は $p, q, g$ 用意して、 $p$ はmod、 $g$ はその元、 $q$ は部分群の位数で $q | (p-1)$

$y = p^x$

$t = p^v$

$c$ は適当な値（ここではハッシュ関数を使ってる）

$r = v - cx \mod q$

として、 $t = g^r y^c = g^{v-cx}g^{cx} = g^v$ なので $x$ を知っているという主張

主張はどうでもよくて、ここから $x$ を取り出したい

使えそうなのは $r = v-cx$ 、もっと言えば $r - kq = v - cx$ という式。この式のうち、 $k, v, x$ が未知で $q, r, x$ は既知。これはHidden Number Problem

$v,x \simeq 2^{247}$

$k, c, r \simeq 2^{256}$

ということで適当な格子を貼ってみる。 $K = 2^{247}$ として

$\begin{pmatrix} k & 1 & x \end{pmatrix} \begin{pmatrix} -q & 0 & 0 \ r & 0 & K \ c & 1 & 0 \end{pmatrix} = \begin{pmatrix} v & x & K \end{pmatrix}$

なんとなく良さそうに見えるが、やってみるとうまくいかない。こういうときは要素をふやすとうまく行くことになっているのでいくつかインスタンスを収集する

結局手元だと29インスタンス必要だった。しんど……

from hashlib import sha256
import random

def generate_dsa_domain():
    qSize = 256
    pSize = 3072

    q = random_prime(1<<(qSize + 1), False, 1<<qSize)
    while True:
        p = randint(1 << (pSize - 1), 1<<pSize)
        c = p % (2 * q)
        p = p - c + 1
        if p.nbits() == pSize and is_prime(p):
            break

    g = randint(2, p-1)
    g = pow(g, (p-1)//q, p) # g has order q now

    return p, q, g

# params = eval(open("params").read())
# lines = open("param").read().strip().split("\n")
# params = []
# for line in lines:
#     params.append(map(int, line.strip("()").split(",")))
params = []
for _ in range(30):
    params.append(generate_dsa_domain())


x = random.getrandbits(247)

qs = []
cs = []
rs = []
vs = []

for param in params:
    p, q, g = param
    v = random.randrange(1, x)
    c = int(sha256(randint(0, 1<<1024).to_bytes(1024 // 8, "little")).hexdigest(), 16)
    r = (v - c*x) % q

    qs.append(q)
    cs.append(c)
    rs.append(r)
    vs.append(v)

K = 1<<247

N = len(qs)
M = Matrix(ZZ, N + 2, N + 2)
for i in range(N):
    M[i, i] = -qs[i]

for i in range(N):
    M[N, i] = rs[i]
M[N, N+1] = K

for i in range(N):
    M[N+1, i] = cs[i]
M[N+1, N] = 1

B = M.LLL()

print(B[0])
print()
print(K)
print(x)
print(vs)