LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mikecat_mixc

Ed25519 署名の計算方法

Posted at

RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
に基づいて、Ed25519 署名の生成・検証方法をまとめる。

この記事の方法で、
Ed25519 Online Tool
の動作にマッチした結果が得られる。

今回の記事は「値の求め方」にフォーカスしており、タイミング攻撃やサイドチャネル攻撃などへの対策は考慮していない。

準備

基本事項

Ed25519 の公開鍵 (検証鍵) と秘密鍵 (署名鍵) は、それぞれ 32 バイト (256 ビット) である。
Ed25519 の署名は、64 バイト (512 ビット) である。

計算に用いる整数の定数 p・d・L を

p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
d = 0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3
L = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed

座標の定数 B = (B_x, B_y) を

B_x = 0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a
B_y = 0x6666666666666666666666666666666666666666666666666666666666666658

とする。

座標の処理

Ed25519 の計算では、2個の整数からなる座標 (x, y) を扱う。

座標の処理において、整数の演算は$\mod p$ で行う。
すなわち、通常の演算結果を「基本事項」で用意した定数 $p$ で割った余りである非負の値を演算結果とする。

エンコード

座標 (x, y) を 32 バイトのバイト列で表すため、以下の表現を用いる。

y を 32 バイト (256 ビット) で表した際、(p 未満なので) 最上位ビットは常に 0 となる。
そこで、この最上位ビットを x の最下位ビットに置き換えた数 y' を用意する。
そして、この y' をリトルエンディアンのバイト列で表す。

デコード

32 バイトのバイト列から、それが表す座標 (x, y) を求める。

まず、バイト列をリトルエンディアンで整数として解釈する。
この整数の最上位ビットを $x_0$ とし、最上位ビットを 0 にした値を座標の成分の一つ y とする。
この y が p 以上の場合、デコードは失敗である。

次に、以下の計算を行う。
ただし、$p$ および $d$ は「基本事項」で用意した定数である。

\begin{eqnarray*}
u &=& y^2 - 1 \\
v &=& d y^2 + 1\\
x_1 &=& u v^3 (u v^7)^{(p-5)/8}
\end{eqnarray*}

$\frac{p-5}{8}$ は整数であるため、累乗は通常の繰り返し二乗法で求めることができる。

$v x_1^2$ と $u$ の値の関係に応じて、$x_2$ を以下のように定める。

$v x_1^2$ の値 $x_2$ の値
$u$ $x_1$
$p - u$ $2^{(p-1)/4} x_1$
それ以外 なし (デコードは失敗である)

$\frac{p-1}{4}$ も整数である。

$x_0$ と $x_2$ から、座標の成分 x を以下のように求める。

  • $x_0 = 1$ かつ $x_2 = 0$ のとき、デコードは失敗である
  • $x_0$ が $x_2$ の最下位ビットと等しい場合、$x = x_2$ とする
  • そうでない場合、$x = p - x_2$ とする

足し算

計算上の都合で、座標 (x, y) を整数の四つ組 (X, Y, Z, T) で表す。
ただし、x = X/Z, y = Y/Z, x*y = T/Z である。
座標 (x, y) は、(x, y, 1, x*y) と表すことができる。

四つ組で表した座標の足し算

(X1, Y1, Z1, T1) + (X2, Y2, Z2, T2) = (X3, Y3, Z3, T3)

は、以下のように求めることができる。
ただし、d は「基本事項」で用意した定数であるが、B は座標の定数とは関係ない。

A = (Y1-X1)*(Y2-X2)
B = (Y1+X1)*(Y2+X2)
C = T1*2*d*T2
D = Z1*2*Z2
E = B-A
F = D-C
G = D+C
H = B+A
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

また、同じ座標同士の足し算

(X1, Y1, Z1, T1) + (X1, Y1, Z1, T1) = (X3, Y3, Z3, T3)

は、少しステップ数が少ない以下の手順でも求めることができる。

A = X1*X1
B = Y1*Y1
C = 2*Z1*Z1
H = A+B
E = H-(X1+Y1)*(X1+Y1)
G = A-B
F = C+G
X3 = E*F
Y3 = G*H
T3 = E*H
Z3 = F*G

署名の計算方法

鍵生成

秘密鍵 (署名鍵)

任意の 32 バイト (256 ビット) のデータを、秘密鍵として用いることができる。
暗号学的に強力な乱数を用いることが推奨される。

公開鍵 (検証鍵)

秘密鍵から、以下の方法で対応する公開鍵を生成する。

まず、秘密鍵の SHA-512 ハッシュ値 (64 バイト) を求め、前半の 32 バイトをリトルエンディアンで解釈した整数を s' とする。
この s' の値に以下の加工を行った値を s とする。

  • 最上位ビットを 0 にする
  • 最上位から1個下のビットを 1 にする
  • 下位3ビットを 0 にする

「基本事項」で用意した座標の定数 B を s 個足した座標を A とする。
(B に s を掛けるイメージ)

A をエンコードした 32 バイトのバイト列が、公開鍵である。

署名の生成

まず、秘密鍵の SHA-512 ハッシュ値 (64 バイト) を求める。
公開鍵の生成と同様に、整数 s および座標 A を求める。
また、このハッシュ値の後半 32 バイトの後に署名対象のメッセージを接合したデータの SHA-512 ハッシュ値を求め、これをリトルエンディアンで解釈した整数を r とする。

「基本事項」で用意した座標の定数 B を r 個足した座標を R とする。

以下のデータをこの順で接合したデータの SHA-512 ハッシュ値を求め、これをリトルエンディアンで解釈した整数を m とする。

  1. 座標 R をエンコードしたバイト列 (32 バイト)
  2. 座標 A をエンコードしたバイト列 (32 バイト)
  3. 署名対象のメッセージ

r + m * s を「基本事項」で用意した定数 L で割った余りを S とする。

以下のデータをこの順で接合したデータが、署名である。

  1. 座標 R をエンコードしたバイト列 (32 バイト)
  2. 整数 S を 32 バイトのリトルエンディアンで表したバイト列

署名の検証

署名 (64 バイト) を前半 32 バイトと後半 32 バイトに分け、前半をデコードした座標 R と、後半をリトルエンディアンで解釈した整数 S を用意する。
公開鍵 (32 バイト) をデコードした座標 A を用意する。

座標 R または A のデコードに失敗するか、整数 S が L 以上の場合、署名の検証は失敗 (署名は無効) とする。

以下のデータをこの順で接合したデータの SHA-512 ハッシュ値を求め、これをリトルエンディアンで解釈した整数を h とする。

  1. 署名の前半 32 バイト (座標 R をエンコードしたバイト列)
  2. 公開鍵 (座標 A をエンコードしたバイト列)
  3. 署名対象のメッセージ

以下の座標をそれぞれ計算する。ただし、B は「基本事項」で用意した座標の定数である。

  • 座標 B を $8S$ 回足した座標
  • 「座標 R を 8 回足した座標」と「座標 A を $8h$ 回足した座標」を足した座標

これらの座標が一致すれば署名の検証は成功 (署名は有効)、一致しなければ署名の検証は失敗 (署名は無効) とする。

足す回数の「8倍」を省略し、

  • 座標 B を S 回足した座標
  • 「座標 R」と「座標 A を h 回足した座標」を足した座標

を比較してもよい。

実装例

ここまで紹介したアルゴリズムを、Python で実装した。
typing.Self を用いているため、Python 3.11 以降用である。

Ed25519.py
from hashlib import sha512
from typing import Union, Self

p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed

class ModInt():
    def __init__(self, value: int):
        self.value = value % p

    def __add__(self, other: Self) -> Self:
        return ModInt((self.value + other.value) % p)

    def __sub__(self, other: Self) -> Self:
        return ModInt((self.value - other.value) % p)

    def __mul__(self, other: Self) -> Self:
        return ModInt((self.value * other.value) % p)

    def __pow__(self, n: int) -> Self:
        return ModInt(pow(self.value, n, p))

    def inv(self) -> Self:
        return ModInt(pow(self.value, p - 2, p))

class PointDecodeError(Exception):
    pass

class Point():
    def __init__(self, x: ModInt, y: ModInt):
        self.x = x
        self.y = y
        self.z = ModInt(1)
        self.t = x * y

    def __add__(self, other: Self) -> Self:
        A = (self.y - self.x) * (other.y - other.x)
        B = (self.y + self.x) * (other.y + other.x)
        C = self.t * ModInt(2) * d * other.t
        D = self.z * ModInt(2) * other.z
        E = B - A
        F = D - C
        G = D + C
        H = B + A
        res = Point(ModInt(0), ModInt(1))
        res.x = E * F
        res.y = G * H
        res.t = E * H
        res.z = F * G
        return res

    def double(self) -> Self:
        A = self.x * self.x
        B = self.y * self.y
        C = ModInt(2) * self.z * self.z
        H = A + B
        E = H - (self.x + self.y) * (self.x + self.y)
        G = A - B
        F = C + G
        res = Point(ModInt(0), ModInt(1))
        res.x = E * F
        res.y = G * H
        res.t = E * H
        res.z = F * G
        return res

    def times(self, num: int | ModInt) -> Self:
        try:
            t = num.value
        except AttributeError:
            t = num
        res = Point(ModInt(0), ModInt(1))
        delta = self
        while t > 0:
            if (t & 1) != 0:
                res = res + delta
            delta = delta.double()
            t >>= 1
        return res

    def encodeToInt(self) -> int:
        inv_z = self.z.inv()
        x = self.x * inv_z
        y = self.y * inv_z
        res = y.value
        if (x.value & 1) != 0:
            res |= 1 << 255
        return res

    def encode(self) -> bytes:
        return self.encodeToInt().to_bytes(32, "little")

    @staticmethod
    def decodeFromInt(value: int) -> Self:
        x_0 = (value >> 255) & 1
        y = ModInt(value & ((1 << 255) - 1))
        if y.value >= p:
            raise PointDecodeError()
        u = y * y - ModInt(1)
        v = d * y * y + ModInt(1)
        x_1 = u * (v ** 3) * ((u * (v ** 7)) ** ((p - 5) // 8))
        test = v * x_1 * x_1
        if test.value == u.value:
            x_2 = x_1
        elif test.value == p - u.value:
            x_2 = (ModInt(2) ** ((p - 1) // 4)) * x_1
        else:
            raise PointDecodeError()
        if x_0 == 1 and x_2.value == 0:
            raise PointDecodeError()
        if x_0 == (x_2.value & 1):
            x = x_2
        else:
            x = ModInt(p - x_2.value)
        return Point(x, y)

    @staticmethod
    def decode(data: bytes) -> Self:
        if len(data) != 32:
            raise PointDecodeError()
        return Point.decodeFromInt(int.from_bytes(data, "little"))

d = ModInt(0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3)
L = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
B_x = ModInt(0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a)
B_y = ModInt(0x6666666666666666666666666666666666666666666666666666666666666658)
B = Point(B_x, B_y)

def getPublicKey(privateKey: bytes) -> bytes:
    hash = sha512(privateKey).digest()
    s = int.from_bytes(hash[0:32], "little")
    s &= ~(1 << 255)
    s |= 1 << 254
    s &= ~7
    A = B.times(s)
    return A.encode()

def sign(privateKey: bytes, message: bytes) -> bytes:
    hash = sha512(privateKey).digest()
    s = int.from_bytes(hash[0:32], "little")
    s &= ~(1 << 255)
    s |= 1 << 254
    s &= ~7
    A = B.times(s)
    r = int.from_bytes(sha512(hash[32:] + message).digest(), "little")
    R = B.times(r)
    m = int.from_bytes(sha512(R.encode() + A.encode() + message).digest(), "little")
    S = (r + m * s) % L
    return R.encode() + S.to_bytes(32, "little")

def verify(publicKey: bytes, message: bytes, signature: bytes) -> bool:
    if len(signature) != 64:
        return False
    try:
        R = Point.decode(signature[0:32])
        A = Point.decode(publicKey)
    except PointDecodeError:
        return False
    S = int.from_bytes(signature[32:], "little")
    if S >= L:
        return False
    h = int.from_bytes(sha512(signature[0:32] + publicKey + message).digest(), "little")
    p1 = B.times(8 * S)
    p2 = R.times(8) + A.times(8 * h)
    return p1.encodeToInt() == p2.encodeToInt()

if __name__ == "__main__":
    import sys
    import os
    argc = len(sys.argv)
    if argc == 2:
        print(getPublicKey(bytes.fromhex(sys.argv[1])).hex())
    elif argc == 3:
        print(sign(bytes.fromhex(sys.argv[1]), sys.argv[2].encode()).hex())
    elif argc == 4:
        print(verify(bytes.fromhex(sys.argv[1]), sys.argv[2].encode(), bytes.fromhex(sys.argv[3])))
    else:
        myName = os.path.basename(__file__)
        print("get public key from private key:")
        print("  %s private_key_hex" % myName)
        print("create a signature:")
        print("  %s private_key_hex message" % myName)
        print("verify a signature:")
        print("  %s public_key_hex message signature_hex" % myName)

さらに、RFC 8032 で紹介されていたテストケース https://ed25519.cr.yp.to/python/sign.input を読み込み、テストを行うプログラムを用意した。

run_test.py
import sys
import Ed25519

for lineno, case in enumerate(sys.stdin.readlines(), 1):
    privateKeyHex, publicKeyHex, messageHex, signatureHex, _ = case.rstrip().split(":")
    privateKey = bytes.fromhex(privateKeyHex)[0:32]
    publicKey = bytes.fromhex(publicKeyHex)
    message = bytes.fromhex(messageHex)
    signature = bytes.fromhex(signatureHex)[0:64]
    try:
        if Ed25519.getPublicKey(privateKey) != publicKey:
            print("line %d: public key mismatch" % lineno)
        if Ed25519.sign(privateKey, message) != signature:
            print("line %d: signature mismatch" % lineno)
        if not Ed25519.verify(publicKey, message, signature):
            print("line %d: verify failed" % lineno)
    except Exception as e:
        print("line %d:" % lineno)
        print(e)

このプログラムとテストケースを用いてテストを行った結果、エラーは検出されなかった。

このテストにより「正しい署名は検証に成功する」らしいことは確かめているが、「間違った署名は検証に失敗する」かどうかの確認は行っていない。

まとめ

RFC 8032 の情報をもとに、Ed25519 署名の公開鍵生成・署名・検証の数学的な計算方法を確認した。

今回は、ハッシュ関数やその使い方などが異なる Ed25519ph や Ed25519ctx は扱っていない。
また、タイミング攻撃対策など、コンピュータでの詳しい計算 (実装) 方法についても扱っていない。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?