リング署名
実装 > オリジナルのスキーム > Python実装

RSA暗号を使用した元の論文のPython実装を以下に示す。サードパーティモジュールPyCryptodomeが必要である。
import os
import hashlib
import random
import Crypto.PublicKey.RSA

import functools

class Ring:
    """RSA implementation."""

    def __init__(self, k, L: int = 1024) -> None:
        """初期化する。

        Args:
            k: 鍵のリスト。署名者の分に関しては公開鍵と秘密鍵のペア
            L: 鍵の長さ
        """
        self.k = k
        self.l = L
        self.n = len(k)
        self.q = 1 << (L - 1)

    def sign_message(self, m: str, z: int):
        """メッセージに対する署名を返す。

        Args:
            m: 署名対象のメッセージ
            z: リストkの中で署名者の位置

        Returns:
          整数のリスト。最初の値は糊値であり、残りはトラップドア関数への
          引数x_iである。
        """

        # 方針:
        # リングは輪になっているので、どこから計算を始めても1周すると元の値に
        # 戻る。
        # そこで、zの位置から計算を始めて、戻ってきた値が繋がるように
        # y_zおよびx_zを決める。

        # self.pにmのハッシュ値を入れる。
        self._permut(m)
        # x_iのリスト。
        s = [None] * self.n
        # y_z ⊕ E_k(y_{z-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c)))
        # ただしcはC_{k,v}(y_1, y_2, ..., y_n)。
        u = random.randint(0, self.q)
        # cは最終的にC_{k,v}(y_1, y_2, ..., y_n)となる値。
        # vは最終的にE_k(y_{z-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c)))となる値。
        c = v = self._E(u)

        # 範囲 [z + 1, n)
        first_range = list(range(z + 1, self.n))
        # 範囲 [0, z)
        second_range = list(range(z))
        # [z + 1, z + 2, ..., n, 0, 1, ..., z - 1] (zは含まない)
        whole_range = first_range + second_range

        for i in whole_range:
            # x_iをランダムに決める。
            s[i] = random.randint(0, self.q)
            # y_iに相当する値。x_iを鍵k_iで暗号化した値。
            e = self._g(s[i], self.k[i].e, self.k[i].n)
            # E_k(y_i ⊕ E_k(y_{i-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c))))
            v = self._E(v ^ e)
            if (i + 1) % self.n == 0:
                c = v

        # この時点において、
        # v = E_k(y_{z-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c)))となっている。
        # 一方、リングが繋がるためには
        # u = y_z ⊕ v
        # である必要がある。
        # よって
        # y_z = v ⊕ u
        # これをzの秘密鍵で復号してx_zを得る。
        s[z] = self._g(v ^ u, self.k[z].d, self.k[z].n)
        return [c] + s

    def verify_message(self, m: str, X) -> bool:
        """メッセージmと署名Xを検証する。"""

        # リングを先頭から計算していき、最初の値に戻ればOKとする。

        self._permut(m)

        def _f(i):
            return self._g(X[i + 1], self.k[i].e, self.k[i].n)

        y = map(_f, range(len(X) - 1))
        y = list(y)

        def _g(x, i):
            return self._E(x ^ y[i])

        r = functools.reduce(_g, range(self.n), X[0])
        return r == X[0]

    def _permut(self, m):
        """self.pにmのハッシュ値を入れる。"""
        msg = m.encode("utf-8")
        self.p = int(hashlib.sha1(msg).hexdigest(), 16)

    def _E(self, x):
        """xとmのハッシュ値を連結したもののハッシュ値を返す。"""
        msg = f"{x}{self.p}".encode("utf-8")
        return int(hashlib.sha1(msg).hexdigest(), 16)

    def _g(self, x, e, n):
        """xを鍵(e, n)を使ってRSAによる暗号化(あるいは復号)をして返す。"""
        q, r = divmod(x, n)
        if ((q + 1) * n) <= ((1 << self.l) - 1):
            result = q * n + pow(r, e, n)
        else:
            result = x
        return result
4人のユーザからなるリングにおいて、2つのメッセージの署名と検証をする場合:
size = 4
msg1, msg2 = "hello", "world!"

def _rn(_):
    return Crypto.PublicKey.RSA.generate(1024, os.urandom)

key = map(_rn, range(size))
key = list(key)

r = Ring(key)

for i in range(size):
    signature_1 = r.sign_message(msg1, i)
    signature_2 = r.sign_message(msg2, i)
    assert r.verify_message(msg1, signature_1) and r.verify_message(msg2, signature_2) and not r.verify_message(msg1, signature_2)