Pythonによる楕円曲線暗号の実装」の入稿記事を技術評論社のご好意で公開したものです。元はLaTeXだったのをマークダウンに修正し、二つに分けています。前半は楕円曲線暗号のPythonによる実装その1(有限体とECDH鍵共有)です。記事中のサンプルコードはサポートページからダウンロードできます。有限体クラスを実装できたので次は楕円曲線クラス\texttt{Ec}を実装します。楕円曲線は有限体\texttt{Fp}とその値aとbで決まります。....からなる集合です。Parameters)。それらの値をクラスメソッド\texttt{init}で設定します。rEc::init楕円曲線の点は2個の\texttt{Fp}の要素で表現できます。Oは整数の0に相当する特別な点(以降0と表示する)で場合分けが必要です。yの他に0か否かを表すフラグisZeroを用意します。y)は方程式y^2=x^3+ax+bを満たさなければなりません。値が正しいか否かを確認する\texttt{isValid}メソッドを用意しましょう。isZeroがTrueのときはTrueです。楕円曲線の点の足し算、引き算の規則を紹介します。点0と任意の点Pに対してP+0=0+P=Pとします。P=(x_1,y_1)のとき、-P=(x_1,-y_1)と定義します。点のマイナスはy座標の値の符号を反転します。Pと-Pを足すと常に0です。一般の点P=(x_1,y_1)とQ=(x_2,y_2)についてR=(x_3,y_3)=P+Qは次の計算をします。式は複雑ですが、四則計算だけなので有限体の節で実装した有限体を使って計算できます。こんな式が現れるのかについてはたとえば拙著『クラウドを支えるこれからの暗号技術』などを参照ください。この式をそのままPythonで実装します。最後に楕円曲線の点の整数倍を実装します。Pと逐次的に求めようとすると、nが256ビット整数のときは宇宙が滅亡しても全く終わりません。そこで効率のよい方法を紹介します。Pつまりnを2進数で表したとき、点Pの上位kビット倍が求まったら、その値を2倍して次のビットが1ならPを足すことでk+1ビット倍が求まり、それを繰り返すのです。この方法では、ループ回数はnのビット長になるので256ビット整数でも高々256回のループで完了します。Pythonで実装するには、まずnを\texttt{bin(n)}で2進数表記し、\texttt{0b...}で始まる最初2文字を取り除いた0と1からなる文字列に対してループさせます。retEc::mul以上でECDH鍵共有に必要なメソッドの実装が完了しました。最後に楕円曲線を用いた署名の一つであるECDSAを実装しましょう。署名は鍵生成、署名(sign)、検証(verify)の3個のアルゴリズムからなります。鍵生成ではアリスが署名鍵sと検証鍵Sを生成します。署名鍵sは自分だけの秘密の値なので秘密鍵、検証鍵Sは他人に渡して使ってもらう鍵なので公開鍵ともいいます。signは署名したいデータmに対して署名鍵sで署名と呼ばれるデータσを作ります。secp256k1曲線の場合は2個の256ビット整数からなる512ビットの固定長データです。署名データmと署名σのペアを他人(ボブ)に渡します。ボブは検証鍵Sを使って(m,σ)の正しさを確認し、受理か拒否します。ECDSAの鍵生成ECDSAの鍵生成アルゴリズムは次の通りです。アリスが\texttt{Fr}の中から乱数sを一つとり、これを署名鍵とします。点Pをs倍したS=sPを検証鍵とします。ECDLPの困難性により検証鍵から署名鍵は求まりません。署名と検証にはハッシュ関数を使います。ハッシュ関数自体の説明は他の書籍に譲ります。PythonでSHA-256を使うにはhashlibをimportします。ハッシュ値は256ビットでPythonでは32個のバイト配列です。それを有限体\texttt{Fr}の値とみなすときは配列の先頭が整数の上位にくるビッグエンディアンとして整数にします。\texttt{b'{\textbackslash}x12{\textbackslash}x34'}は\texttt{0x1234}です。msgToFr(図中のh)はメッセージmから\texttt{Fr}への関数です。byteToFr(H.digest())ハッシュ値の整数化データmの署名を作成するにはまず乱数kを選びます。楕円曲線の点kPを計算し、そのx座標をrとします。\sigma=(r,(h(m)+sr)/k)が署名です。ここで足し算や割り算は有限体\texttt{Fr}を使った計算です。楕円曲線の点を計算するときは素数pを使った有限体でしたが、署名の計算では楕円曲線の点の個数rを使った有限体を利用します。\texttt{Fp}と\texttt{Fr}は素数が違うだけのクラスです。実装するか悩んだのですが、ここでは安直に\texttt{fp.py}をコピーして\texttt{fr.py}を作り、クラス名を置換しました。署名に使う乱数\texttt{sign}で使うkは正しく乱数を生成しなければなりません。乱数を生成するのはなかなかやっかいなため、その代わりに署名鍵やデータなどからkを生成するアルゴリズムがRFC6979で規定されています。興味ある方はご覧ください。最後にverifyを実装します。verifyは、データmと署名\sigma=(r,t)が与えられたときに、まず\texttt{z=msgToFr(msg)}を計算します。rS)/tを計算します。楕円曲線の点をtで割る操作は、有限体\texttt{Fr}の中で逆数w=1/tを掛けることに相当します。w楕円曲線の整数倍は有限体の掛け算に比べてずっと重たい処理なのでR=(zw)P+(rw)Sとすると速くなります。最後に求めた楕円曲線の点Qのx座標がrに等しければ\texttt{True}を返します。以上がECDSAの実装です。実際に使うにはより厳密なチェックや、検証鍵や署名データを相互運用するためのフォーマットなど実装すべき箇所がありますが、手元で数値を確認しながら動作させるにはこれで十分です。この記事が楕円曲線や鍵共有、署名の理解に少しでも役立てば幸いです。GitHubで編集を提案ツイートherumiJITアセンブラXbyakや暗号ライブラリmcl/blsの開発者。暗号技術や最適化周りの話をします。バッジを贈って著者を応援しようバッジを受け取った著者にはZennから現金やAmazonギフト券が還元されます。約6,200字herumiJITアセンブラXbyakや暗号ライブラリmcl/blsの開発者。暗号技術や最適化周りの話をします。署名に使う乱数ECDSAの検証Zennエンジニアのための情報共有コミュニティAboutZennについて運営会社お知らせ・リリースGuides使い方Publicationよくある質問LinksTwitterGitHubメディアキットLegal利用規約プライバシーポリシ。