このプロジェクトは、Rust 言語を用いて RSA ベースのリング署名を実装したものです。情報セキュリティの授業で学習した RSA 署名を拡張し、対称鍵暗号（ChaCha20）を内部で使用しています。 リング署名の概念とその数学的背景を理解し、実際に動作するコードを提供することを目的としています。
このプログラムは、学習目的で作成されたサンプルプログラムです。実際のセキュリティアプリケーションでの使用は推奨いたしません。なお、著者はセキュリティの専門家ではなく、また専門家による検証を受けていないため、潜在的な脆弱性が存在する可能性があります。
数学的な誤り等がございましたら、Issue や Pull Request にてご指摘いただけると幸いです。
リング署名は、公開鍵暗号の署名技術の一種で、複数の公開鍵の中から誰が署名したかを特定できないようにしつつ、その中の誰かが署名したことを証明できる技術です。
- 匿名性: 署名者を特定できない。
- 自発性: グループ内の他のメンバーの協力は不要。署名者は自身の秘密鍵と、他のメンバーの公開鍵（公開されているもので良い）のみで署名可能。
リング署名は、Monero などの匿名性の高い暗号通貨で採用され、取引のプライバシー保護に貢献しています。
2001 年に発表された論文「How to Leak a Secret」を参考に、プログラミング言語 Rust でリング署名を実装しました。
- RSA 署名をベースに設計。
- 対称鍵暗号として ChaCha20 を使用。
このセクションでは、リング署名の理解に必要な RSA 署名とその拡張について解説します。
RSA 署名は、公開鍵暗号方式の一つで、以下の要素で構成されます。
-
鍵生成:
- 2 つの大きな素数
$p$ ,$q$ を選びます。 -
$n = p \cdot q$ を計算します。(これがモジュラス(modulus)となり、公開鍵の一部になります) -
$\phi(n) = (p - 1)(q - 1)$ を計算します。(オイラーの φ 関数) -
$1 < e < \phi(n)$ であり、$e$ と$\phi(n)$ が互いに素(最大公約数が 1)となるような$e$ を選びます。($e$ は公開指数と呼ばれ、公開鍵の一部です) -
$d \cdot e \equiv 1 \pmod{\phi(n)}$ を満たす$d$ を計算します。($d$ は秘密指数と呼ばれ、秘密鍵の一部です)
- 2 つの大きな素数
-
鍵ペア:
- 公開鍵:
$(n, e)$ - 秘密鍵:
$(d, n)$ (または$d$ のみ)
ここで、
$n$ (モジュラス)と$e$ (公開指数)は公開され、$d$ (秘密指数)は秘密に保持されます。 - 公開鍵:
-
署名生成:
- メッセージ
$m$ のハッシュ値$x = H(m)$ を計算します。 - 署名
$y = x^d \bmod n$ を計算します。(ここで秘密鍵の要素$d$ を使用します) - メッセージ
$m$ と署名$y$ を送信します。
この署名生成の計算式は、
$f(x) = x^d \bmod n$ と表され、RSA のトラップドア関数と呼ばれます。 - メッセージ
-
署名検証:
- (受信者は)メッセージ
$m$ のハッシュ値$x = H(m)$ を計算します。 -
$x' = y^e \bmod n$ を計算します。(ここで公開鍵の要素$e$ を使用します) -
$x'$ と$x$ が一致すれば、署名は有効と判断します。
署名検証の計算式は、
$f^{-1}(y) = y^e \bmod n$ と表され、これは署名生成関数の逆関数です。 - (受信者は)メッセージ
リング署名では、通常の RSA のべき乗剰余演算を拡張した「拡張トラップドア関数」を導入します。これにより、異なる公開鍵を持つ複数のメンバーの計算結果を、同じ空間上で扱えるようになります。
-
拡張トラップドア関数
$g_i$ :入力
$x$ に対して、以下の計算を行います。-
$x$ を$n_i$ (署名者$i$ のモジュラス)で割った商$q_i$ と余り$r_i$ を求めます ($x = q_i \cdot n_i + r_i$ )。 -
$g_i(x_i) = q_i \cdot n_i + f(x_i) = q_i \cdot n_i + r_i^{e_i} \mod n_i$ を計算します。 ($f(x_i)$ は通常の RSA のトラップドア関数、$r_i^{e_i} \mod n_i$ と等価)
-
-
拡張トラップドア関数の逆関数
$g_i^{-1}$ :入力
$y$ に対して、以下の計算を行います。-
$y$ を$n_i$ で割った商$q_i$ と余り$r_i$ を求めます ($y = q_i \cdot n_i + r_i$ )。 -
$g_i^{-1}(y_i) = q_i \cdot n_i + f^{-1}(y_i) = q_i \cdot n_i + r_i^{d_i} \mod n_i$ を計算します。($f^{-1}(y_i)$ は RSA トラップドア関数の逆関数、$r_i^{d_i} \mod n_i$ と等価)
-
これらの関数は、公開鍵(
重要な注意点:
リング署名は、特定のグループ（リング）のメンバーの誰かが署名したことを証明しつつ、具体的な署名者は秘匿する署名方式です。
記号:
-
$R$ : リング (署名に参加する全メンバーの公開鍵の集合) -
$P_i$ : リングの$i$ 番目のメンバーの公開鍵 -
$s$ : 署名者のインデックス ($0 \le s < r$ ,$r$ はリングサイズ) -
$S$ : 署名者の秘密鍵 -
$k$ : メッセージのハッシュ値 (対称鍵暗号の鍵として利用) -
$E_k(x)$ : 鍵$k$ による$x$ の対称鍵暗号化関数 (例: ChaCha20) -
$D_k(y)$ : 鍵$k$ による$y$ の対称鍵暗号復号関数 -
$v$ : グルー値 (リング署名の開始点と終了点をつなぐランダムな値) -
$x_i$ : 各メンバー ($i$ ) に対応する値 (署名者以外はランダム生成、署名者は逆算) -
$y_i$ :$x_i$ に拡張 RSA トラップドア関数$g(x_i, P_i)$ を適用した値 -
$g(x, P)$ : 拡張 RSA トラップドア関数 -
$g^{-1}(y, S)$ : 拡張 RSA トラップドア関数の逆関数 -
$C_{k,v}(y_1, y_2, \dots, y_r)$ : 結合関数
結合関数
結合関数は、各メンバーの
つまり、各
署名生成:
-
グルー値の生成: ランダムな値
$v$ を生成します。 -
署名者以外の
$x_i$ ,$y_i$ の生成: 署名者 ($i = s$ ) 以外のメンバーについて、- ランダムな値
$x_i$ を生成します。 -
$y_i = g(x_i, P_i)$ を計算します。 ($P_i$ は$i$ 番目のメンバーの公開鍵)
- ランダムな値
-
$y_s$ の逆算: 結合関数$C_{k,v}(y_1, y_2, \dots, y_r) = v$ という方程式が成り立つように、署名者の$y_s$ を逆算します。(結合関数が一対一対応であるため、$y_s$ は一意に定まります) -
$x_s$ の計算: 署名者は、$x_s = g^{-1}(y_s, S)$ を計算して自身の$x_s$ を求めます。(ここで署名者の秘密鍵$S$ が必要になります) -
署名の完成: 全ての
$x_i$ が揃ったら、署名が完了します。署名は$(P_1, P_2, \dots, P_r; , v; , x_1, x_2, \dots, x_r)$ の形式になります。
署名検証:
-
署名形式: 検証者は、署名
$(P_1, P_2, \dots, P_r; , v; , x_1, x_2, \dots, x_r)$ を受け取ります。 -
$y_i$ の計算: 各$x_i$ に対して、$y_i = g(x_i, P_i)$ を計算します。 -
鍵の算出: メッセージ
$m$ からハッシュ関数で鍵$k = H(m)$ を計算します。 -
結合関数の計算:
$y_i$ 、$k$ 、$v$ を用いて結合関数$C_{k,v}(y_1, y_2, \dots, y_r)$ を計算します。 -
検証: 計算結果が
$v$ と一致すれば、署名は正当と判断し、検証成功。一致しなければ署名は無効と判断します。
ポイント:
- 署名者は、自分の秘密鍵を使って
$x_s$ を計算する部分以外は、他のメンバーの公開鍵のみを使って署名を生成できます。 - 検証者は、リングメンバー全員の公開鍵と署名データを使って検証を行いますが、誰が署名したかは特定できません。
- 結合関数が、リング署名の匿名性と検証可能性を実現する鍵となっています。
- 対称鍵暗号関数
e_k/d_k(ChaCha20) - 拡張 RSA トラップドア関数
g/g_inverse - RSA 署名生成・検証関数
- リング署名生成・検証関数
main 関数の処理フロー:
- RSA 鍵ペアの生成（複数）。
- 各鍵ペアで RSA 署名の生成と検証テスト。
- 複数の鍵ペアでリング署名を生成し、検証。
(スライド資料 3.2 のコード例と実行結果を参照)
- 定数定義:
E,COMMON_DOMAIN_BIT_LENGTH_ADDITION,FIXED_NONCE - 構造体定義:
PublicKey,SecretKey,KeyPair,RingSignature - 利用クレート:
num-bigint,num-integer,num-traits,chacha20,rand,sha3,num_prime
(スライド資料 3.3 を参照)
ユニットテストを多数実装し、以下の観点で各関数の正当性を確認しています。
- 対称鍵暗号の正当性
- RSA 署名（成功/失敗ケース）
- リング署名（成功/失敗、空リング）
g関数,g_inverse関数（正当性、ゼロ、境界値）- 数論関数（素数生成、モジュラ逆数、拡張ユークリッド互除法）
- 各種関数の境界値、エラー処理
RSA 署名を基にリング署名を実装し、その仕組みの理解を深めました。 今後は、他の暗号方式を用いたリング署名の実装や、実際のアプリケーションへの応用を検討したいと考えています。
cargo build --releaseまず OpenSSL で鍵を生成します。
mkdir -p keys
# 署名者の鍵ペアを生成 (秘密鍵と公開鍵)
openssl genpkey -algorithm RSA -out keys/signer_private.pem -pkeyopt rsa_keygen_bits:2048
openssl rsa -pubout -in keys/signer_private.pem -out keys/signer_public.pem
# メンバー1の鍵ペアを生成 (コードでは公開鍵のみ使用)
openssl genpkey -algorithm RSA -out keys/member1_private.pem -pkeyopt rsa_keygen_bits:2048
openssl rsa -pubout -in keys/member1_private.pem -out keys/member1_public.pem
# メンバー2の鍵ペアを生成 (コードでは公開鍵のみ使用)
openssl genpkey -algorithm RSA -out keys/member2_private.pem -pkeyopt rsa_keygen_bits:2048
openssl rsa -pubout -in keys/member2_private.pem -out keys/member2_public.pemその後、実行します。
# 実行
cargo run
# テスト
cargo testバグ報告、機能提案、プルリクエストなど、歓迎します。
このプロジェクトは MIT License のもとで公開されています。
- Rivest, R. L., Shamir, A., & Tauman, Y. (2001). How to leak a secret. In Advances in Cryptology—ASIACRYPT 2001 (pp. 552-565). Springer Berlin Heidelberg. (https://www.iacr.org/archive/asiacrypt2001/22480554.pdf)