EdDSA - crypto-writeup-public

PoC

from hashlib import sha256
from random import randrange
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse

p = 208053691657152142396309207664840706929
a = 106
d = 1
q = 208053691657152142368110593084285429184
c = 6
gx = 192217116159845343943848738627289660061
gy = 146486504425718591283424926785441299471

def is_on_curve(P):
    x, y = P
    return (a*x**2 + y**2) % p == (1 + d*x**2*y**2) % p

def add(P, Q):
    (x1, y1) = P
    (x2, y2) = Q

    x3 = (x1*y2 + y1*x2) * inverse(1 + d*x1*x2*y1*y2, p) % p
    y3 = (y1*y2 - a*x1*x2) * inverse(1 - d*x1*x2*y1*y2, p) % p
    return (x3, y3)

def mul(x, P):
    Q = (0, 1)
    x = x % q
    while x > 0:
        if x % 2 == 1:
            Q = add(Q, P)
        P = add(P, P)
        x = x >> 1
    return Q

def to_bytes(P):
    x, y = P
    return int(x).to_bytes(128 // 8, "big") + int(y).to_bytes(128 // 8, "big")
    

def h(msg):
    return int(sha256(msg).hexdigest(), 16)


G = (gx, gy)
k = randrange(0, q)
hk = h(long_to_bytes(k))
s = hk % 2**128
P = mul(s, G)

def sign(m, hk, P):
    s = hk % 2**128
    r = h(long_to_bytes(hk >> 128) + m)
    R = mul(r, G)
    S = (r + h(to_bytes(R) + to_bytes(P) + m)*s) % q
    return R, S

def verify(m, s, P):
    R, S = s

    x = h(to_bytes(R) + to_bytes(P) + m)
    (ax, ay) = mul(2**c * S, G)
    (bx, by) = add(mul(2**c, R), mul(2**c*x, P))

    return (ax == bx) and (ay == by)


m = long_to_bytes(randrange(0, q))
S = sign(m, hk, P)
print( verify(m, S, P) )

Protocol

public parameter

curve: ed25519 (適当なedwards curve)
G: base point
q: order of the curve
$h$ : $2b$ bit出力の暗号学的ハッシュ関数
where $2^{b-1} > q$

keygen

適当な $b$ bitの整数 $k$ をシードとする
$h(k)$ の下位 $b$ ビット（≒下位半分）を $x$ と置いて、 $x$ が秘密鍵、 $A = sG$ が公開鍵

sign

$h(k)$ の上位 $b$ ビットを $y$ と置いて、 $r = h(y || m), R = rG$
$e = h(R || A || m)$
- ここで $R, A$ は適当にエンコードされてる
$S \equiv r + es \mod q$
署名は $(R, S)$

verify

$e = h(R || A || m)$ を計算して
$2^{c}S*G = 2^{c}*R + 2^{c}es*A$ が成り立つかどうかをみる
$2^{c}l = q$ がなりたつような最大の $c$ （ $q$ の素因数である2のべき数）

Attack

$m$ に対する署名 $(m, A, R, S)$ と、不正な公開鍵 $A'$ を用いて計算された署名 $(m, A', R, S)$ から秘密鍵 $s$ が計算可能
$S \equiv r + es \mod q, S' \equiv r + e's \mod q$ で、 $s, r$ が未知なので、減算して
$S - S' \equiv (e - e')s \mod q$ とすると $s \equiv \frac{S - S'}{e - e'} \mod q$
ECDSA の nonce reuse attack と似た手法