暗号、電子署名

暗号

共通鍵暗号

秘密をやりとりする双方が同じ鍵を持つ

公開鍵暗号

秘密鍵 \(s\)、公開鍵 \(p\) :

• 公開鍵 \(p\) は公表する
• 公開鍵 \(p\) から秘密鍵 \(s\) は求められない
• 平文 \(m\) を送りたい相手の公開鍵 \(p\) を使って暗号化
• 暗号文は秘密鍵 \(s\) でしか平文 \(m\) に復号できない

よくある共通鍵ブロック暗号

入力

共有鍵: \(k\)、鍵幅 \(n\)ビット、 平文: \(m\)

暗号化

• メッセージ \(m\) を \(n\) ビットのブロック \(m_1, .., m_s\) に分ける
• \(k_1 = k\)
• 各ブロックの暗号文 \(c_i = m_i \oplus k_i\) (\(\oplus\): XOR (排他論理和))
• \(k_{i+1} = K(k_{i}, m_i)\) 　なにかいい \(k_{i+1}\) を作る
• 暗号文: \(c_1,..,c_s\) を結合

復号化

暗号化と同じ操作 ( \(c_i \oplus k_i = m_i \oplus k_i \oplus k_i = m_i\) なので )

公開鍵電子署名

ブロックチェーンでは公開鍵暗号を使用。暗号よりもむしろ電子署名が使われる。

• メッセージ(のハッシュ) \(h\) に秘密鍵 \(s\) で署名 \(\sigma\) を作成
• 公開鍵 \(p\), メッセージと署名 \((h, \sigma)\) を作る
• \((p, h, \sigma)\) から、\(s\) を知っている人しか \(\sigma\) を作成できないことを確認

電子署名方式

このごろは楕円曲線暗号がよく使われる。
ハッシュのようにいくつか種類がある:

Secp256k1

Bitcoin, Ethereum, Tezos tz2

Ed25519

Tezos tz1

P256

Tezos tz3

BLS12-381

Ethereum POS

楕円曲線暗号

\(E : y^2 = x^3 + ax + b\)

楕円でもなんでもない…

楕円曲線から暗号システムを作る

\(E\) : 曲線上の点

\(O\) : 無限遠点

\(E \cup \{O\}\) は加群をなす:

• 単位元 : \(O\)
• 逆元: \(-P\): \(P\) の \(x\) 軸対象にある点
• \((+)\) : \(P + Q = R\)
  \(-R\) : 直線 \(PQ\) と \(E\) のもう一つの交点

楕円曲線上の点を制限する

コンピュータ上で \(R^2\) 平面上の楕円曲線の点を扱うのは困難

\(Q^2\) に制限すれば誤差なく取り扱いできる

楕円曲線上の点をさらに制限する

\(Q\) の元は 多倍長整数x2 で表現できるが、必要なメモリサイズの上限がない。 不便なのでさらに制限する。

\(q\) が素数のとき、剰余類環 \(F_q = Z/qZ\) は有限体になる:

• \(F_q = \{0, ..., q-1\}\)
• 加算、減算、乗算は \(\mathrm{mod}~q\) で計算
• 除算は乗算の逆操作として定義できる:
  
  • \(x / y = z\) when \(y \times z = x ~(\mathrm{mod}~ q)\)
  • ユークリッドの互除法による演算
    • \(ay + bq = 1\) なる \(a\),\(b\)を互除法で計算
    • \(yz = x ~(\mathrm{mod}~ q)\) から \(ayz = ax~(\mathrm{mod}~ q)\)
    • \(ayz = (1-bq)z = z = ax ~(\mathrm{mod}~ q)\)

楕円曲線上の点をさらに制限する

平面を \(F_q^2\) に制限しても、今までの楕円曲線の話はなりたって加群を作ることができる:

\[f : Q \rightarrow F_q\] \[f(a/b) = a/b ~(\mathrm{mod}~q)\]

巡回群 \(G\)

先ほどの \(E \cup \{O\}\) の加群から適当な \(P \neq O\) を選び、
素数位数 \(p\) の巡回群 \(G\) を構成する:

\[G := \langle P \rangle := \{ O, P, 2P, 3P, .., (p-1)P \} ~~~ p は大きい素数\]

\(G\) も有限体: 四則演算が使える

\(G = Z/pZ\) なので、除算を導入でき、有限体になる。

注意

\(F_q\) と \(E\) の選び方によっては \(\#G\) が素数になるとは限らない。
頑張って \(\#G = p\) が素数になるようなものを探す。
Schoofのアルゴリズム

楕円曲線上の離散対数問題 (ECDLP)

素数 \(p\) が \(2^{256}\) くらいに大きい \[G = \langle P \rangle = \{ O, P, 2P, .., (p-1)P \}\] に対し、

• ある \(a\) に対し、 \(aP \in G\) を \(a\) と \(P\) から計算するのは簡単
• \(P, aP \in G\) から \(a\) を逆算するのはほとんど不可能

この一方向性が暗号のキモ

ECIES (楕円曲線暗号)

• A の秘密鍵: \(s \in \{0,..,\#G-1\}\)
• A の公開鍵: \(p = sP \in G\)

B は 平文 \(m\) を暗号化して A に送りたい

• 乱数 \(r\) を選ぶ
• \(k = rp\) を計算 (\(= rsP\))
• \(c = \mathrm{Enc}(k,m)\), 共通鍵 \(k\) による暗号化
• \((rP, c)\) を B に渡す

A は暗号 \((rP,c)\) を復号したい

• \(s\) を知っているので \(rP\) と \(s\) から \(k = rsP\) を計算できる。
• \(m = \mathrm{Dec}(k,c)\), 共通鍵 \(k\) による復号化

ECDSA (楕円曲線デジタル署名)

• 秘密鍵: \(s \in \{0,..,\#G-1\}\)
• 公開鍵: \(p = sP \in G\)
• メッセージのハッシュ: \(h \in \{0,..,\#G-1\}\)
• 乱数 \(k \in Z_{\#G}\)
• \(r = kP ~の~ x 座標 ~(\mathrm{mod}~\#G)\)
• 署名: \(\sigma = (r, (h+rs)/k ~(\mathrm{mod}~\#G))\)

署名 \(\sigma = (r,t)\) の確認

\((hP+rp)/t = (hP+rsP)/t = (h+rs)/t P = kP\)

になるので、結果の \(x\) 要素と \(r\) が同じなら、 \(s\) と \(k\) を知っている人しか \(\sigma\) を作れないことがわかる。

乱数生成は大切

Pseudo Random Number Generator

• \(s\): シード
• \(R\): 疑似乱数生成関数。
  

\[r_i = R(s, i)\]

\(r_0, r_1, ...\) に規則性がないように見える

あくまで決定的

• よくない \(R\) だとある程度の \(r_i\) を集めると未来が予測できる
• \(R\) がいくらよくても シード \(s\) の取り方に幅がないと意味がない

Playstation 3™️

ECDSA署名: \(\sigma = (r, (h+rs)/k)\)

Sony の秘密鍵 \(s\) による署名がないゲームは動かない、
はずだった

Jailbreak

\(k\) が固定されていた… (乱数以前の問題)

• \(r = kP ~の ~x~座標\)　も固定
• 二つの署名 \(\sigma_1 = (r, (h_1+rs)/k)\) と \(\sigma_2 = (r, (h_2+rs)/k)\) から
• \((h_1 - h_2)/k\) が計算できる
• \(h_1\) と \(h_2\) は既知なので \(k\) が求まる
• \(k\) がわかれば \((h_i+rs)/k\) から \(s\) も求まる

自作ゲームに \(s\) で署名をして動かすことができる

ブロックチェーンでの電子署名の利用

• 秘密鍵 \(s\) を作成し、死守する
• 公開鍵 \(p\) はブロックチェーンへ登録 \(p \approx アカウント名\)
• 送金命令 \(O\) へのECDSA署名を \(s\) で行い、アカウントへの操作の権利を持っている(= \(s\) を知っている)ことを証明する

秘密鍵 \(s\) が漏洩すれば、攻撃者は \(O\) を偽造できる
= そのアカウントはおしまい。

Trust wallet incident

大手交換所 Binance の子会社が作る暗号通貨ウォレット

2022年11月のバージョンのシードフレーズ作成が甘く、
頑張れば秘密鍵を見つけることができ 170,000 USD が盗難。

原因

• 乱数発生器に予測可能な メルセンヌツイスタ MT19937 を使用
  • MT19937 自体は色々良い性質がある。が、暗号学的に安全なPRNGではない
• シードが 32bit幅なのでシードフレーズも \(2^{32}\) 種しかなかった。
  128GB あれば全列挙できてしまう。(本来なら \(2^{256}\))
• 秘密鍵はパスワードでも守られているはずだが、よくあるパスワードを使っていると死。

楕円曲線の実装

• Secp256k1: Bitcoin, Ethereum, Tezos tz2
• Ed25519: Tezos tz1
• P256: Tezos tz3

Secp256k1

\(E: y^2 = x^3 + 7\)

\(q = 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1\)

\(\#G\) も素数。かなり \(2^{256}\) に近くて嬉しい

BLS12-381

楕円曲線暗号の実装

楕円曲線: \(y^2 = x^3 + 4\)

• \(q\) : 381 bit の素数 (BLS12-381 の 381)
• \(G_1 = F_q\)
• \(G_2 = F_{q^2}\)
• \(G_T = F_{q^{12}}\) (BLS12-381 の 12)

安全で効率的なペアリング関数で知られる。

ペアリング関数

巡回群 \(G_1 = \langle P \rangle\), \(G_2 = \langle Q \rangle\), \(G_T\)

双線形性を持つペアリング関数 \(e(\_, \_)\)

\(e : G_1 * G_2 \rightarrow G_T\)

\(e(x, y+w) = e(x,y) * e(x,w)\) \(e(x+z, y) = e(x,z) * e(z,y)\)

これらから、

\(e(aP,bQ) = e(P,Q)^{ab} = e(P,abQ) = e(bP,aQ) = ~..\)

係数 \(a\), \(b\) を移動できる。
(相変わらず \(aP\) から \(a\) を知ることはできないが)

ペアリング関数を使った BLS 公開鍵署名

• 秘密鍵: \(s \in Z_{\#G_2}\)
• 公開鍵: \(p = sQ \in G_2\)
• メッセージのハッシュ: \(h \in Z_{\#G_1}\)
• 署名: \(\sigma = shP \in G_1\)

とすると、

\[e(\sigma, Q) = e(shP, Q) = e(hP, sQ) = e(hP,p)\]

\(s\) が何か知らない者でも、\(e(hP,p)\) と \(e(\sigma, Q)\) が等しい ことを確認すれば \(\sigma\) を作ったものが \(p = sQ\) となる \(s\) を知っていると確認できる。

(ECDSA と違って乱数がいらないのは嬉しい)

ペアリングチェック関数

先ほどの \[e(\sigma, Q) = e(hP,p)\] は、

\[e(hP,p) * e(-hP,p) = 1\]

と変形できるので、\(\{(x_i, y_i)\}_i \in G_1 * G_2\) の集合をもらい、

\[PC(\{(x_i,y_i)\}) = e(x_1,y_1) ~*~ .. ~*~ e(x_n,y_n) \stackrel{?}= 1\] を計算する関数が提供されている。 \(G_T\) のことを考えなくて済む。

BLS12-381 とゼロ知識証明

ゼロ知識証明

ある知識を知っていることを、
その知識そのものを公開せずに証明する。

例: 公開鍵署名

「自分はメッセージ \(m\) に対してこの署名 \(\sigma\) を
　作成できる秘密鍵 \(s\) を知っている」

例: 平方根

「自分はある数 \(n\) の平方根 \(\sqrt n\) を知っている」

匿名コイン

Zcash の Sapling アルゴリズムで使われている。
送金量や送金先を秘匿しつつ、送金が正当だと証明する。

課題

どちらか一方で結構です。両方出した時は良い点の方。

• 課題A 3点満点(部分点あり)
• 課題B 正解3点、不正解0点

課題 A

\(Q^2\) 上での楕円曲線上の点 \((E \cup \{O\}, +)\) が加群になることを証明してください

• 閉包性: \(P + Q \in E \cup \{O\}\)
• 結合則: \((P + Q) + R = P + (Q + R)\)
• 単位元: \(P + O = O + P = P\)
• 逆元: \(\exists Q, P + Q = O\)
• 交換則: \(P + Q = Q + P\)

ヒント

• \(P+P\) の定義が抜けているので適切に決めてやる
• 閉包性: 有理点 \(P\),\(Q\) を通る直線と \(E\) の交点は有理点か
• 結合則: 頑張って座標計算
• それ以外は定義から明らか

課題 B

Hack the secret key

https://dailambda.jp/nus-blockchain-2023/hack-the-secret-key/