Rustで楕円曲線暗号の署名アルゴリズムをフルスクラッチ実装してみた話

Transcript

1. Rustで楕円曲線暗号の署名アルゴ リズムをフルスクラッチ実装してみた 話 しんぶんぶん
2. しんぶんぶんです
3. @shinbunbun_
4. https://shinbunbun.info
5. しんぶんぶん基本情報 • 会津大学学部二年 • 普段はフロントエンドとかバックエンドとかインフラまわりとか認証 とかiOSアプリとかAndroidアプリを開発してる
6. インターン歴 • 2022/09~2022/11 株式会社アンドパッド インターンシップ • 2022/03~2022/06 ピクシブ株式会社 長期インターンシップ（インフラ部SAチーム） • 2022/02~2022/03 株式会社ゆめみ インターンシップ（Rustを使ったWebアプリケーション開発） • 2021/08 ヤフー株式会社 インターンシップ（認証・アクセス制御に関するプロダクト開発） • 2021/07~2022/03 株式会社 dott 福島県新型コロナウイルス対策サイト保守業務 • 2021/01~2021/05 LasTrust株式会社 インターンシップ（R&D） • 2018/12~2019/12 株式会社 Nature Innovation Group（アイカサ） バックエンド開発
7. ハッカソン！！！！ • 2021/11/07 わたしたちのウェルビーイングのためのハッカソン 2021 富士通 つながる 豊かさ賞 • 2021/10/09 Civictech Challenge Cup[U-22] 2021 Code for Japan賞 • 2021/02/28 Epson Hack Trek 2021 優勝 • 2020/05/24 レッドハッカソン オンライン 2020 奨励賞 • 2018/09/02 LINE BOOT AWARDS×サイボウズ ビジネス/ワーク部門賞狙いのハッカ ソン LINE賞・サイボウズ賞
8. HONDAI
9. みなさん、普段楕円曲線暗号使ってますよね？？
10. やはり普段使っているものの仕組みは知っ ておくべき
11. 今回実装したもの • secp256k1という楕円曲線とECDSAという署名アルゴリズムを使った 電子署名CLIアプリケーション • それに必要な有限体と楕円曲線ライブラリ • リポジトリ: shinbunbun/secp256k1-rust • 参考: プログラミング・ビットコイン - O'Reilly Japan
12. 楕円曲線暗号とは • 有限体上の楕円曲線を用いた暗号 • スカラー倍算の逆が困難であることが安全性の根拠になっている ◦ Y=xG(Gは生成点)のxを計算すること ◦ 楕円曲線上の離散対数問題（ECDLP）
13. 有限体とは • 別名: ガロア体 • 以下の定義を満たす有限集合 • モジュロ演算を使うことで比較的簡単に作れる
14. 実装してみよう！
15. まずは有限体ライブラリ
16. 有限体の定義 • num: 値 • prime: 位数（集合の大きさ）
17. 四則演算を実装 • 任意の多倍長整数ライブ ラリなどに対応できるよ う、全てジェネリクスで実 装 • Traitを使って演算子オー バーロード • トレイト境界無限型パズ ル😇
18. 冪乗を実装 • 繰り返し二乗法を使って高速化 &オーバーフローを防止 • トレイト境界が大変なことになっ てる...
19. こんな感じで使えます • ジェネリクスのおかげでi32でも多倍長整数でも使える
20. 外部crateを極力使わない • stdとnum_traits以外未使用 • これならフルスクラッチを謳っても怒られないはずw
21. 次は楕円曲線ライブラリ
22. Point • 楕円曲線上の点の座 標と(x, y)、曲線のパラ メータ(a, b)をフィール ドに持っている • ジェネリクスで実装す るためPhantomData を使用
23. 点の加算 • 以下の場合分けをして計算 ◦ 加法単位元との加算 ◦ 加法逆元との加算 ◦ 異なる点同士の加算 ◦ 同じ点同士の加算 • もちろん違う曲線の点同士は計 算不可
24. スカラー倍算 • 点の加算が定義され、 点の加算に結合性があ ることからスカラー倍算 が可能 • スカラー倍算を繰り返す と無限遠点に至る（有限 巡回群） • 2進展開を用いて O(log_2n)で実装できる
25. こんな感じで使える • Pointはジェネリクスで 実装しているので、 FieldElement(有限体 上の値)をフィールド に持てる
26. スカラー倍算 • スカラー倍算もジェネリクスなので多倍長整数が使える
27. SignatureのTrait
28. ECDSAのTrait
29. 外部クレートを極力使わない こちらもstdとnum_traits以外未使用
30. いよいよsecp256k1の実装
31. Secp256k1 • フィールドはprivate_keyとpublic_key • 多倍長整数ライブラリに依存する実装が多いのでジェネリクスは未使 用 • public_keyは多倍長整数を型パラメータに受け取ったFieldElement で、private_keyは多倍長整数
32. 鍵生成 • 意外と単純で、秘密鍵はsecretとなる文字列をsha256でhashとって多 倍長整数に変換するだけ • 公開鍵は秘密鍵に楕円曲線の生成点をスカラー倍算したものになる
35. ECDSAのDeterministicな使用 • RFC6979で定義されている • デジタル署名生成の際に使用するnonceを、乱数ではなく署名と鍵か ら一意に生成される値にする • HMAC（メッセージ認証コード）の生成を何回も繰り返す感じ • 詳しくはRFC読んでください！！
37. こんな感じで使える
38. 完成形を動かしてみよう！！
39. 感想 • トレイト境界が無限型パズル編だった • 楕円曲線暗号の仕組みがちょっとだけ理解できたので、やっぱりフルス クラッチは正義
40. 今後の展望 • 今回は署名だけだったので、 楕円曲線ElGamal暗号を実装して暗号 化にも対応させたい • ライフタイム怖くて無限に.clone()してしまったので、ちゃんと参照で渡し てパフォーマンス上げていきたい