RSA電子署名に挑む
挑むって言っても解読じゃなくて、RSA暗号を利用した電子署名システムを既存のライブラリを使わずに構築してみるという意味で。.NET Frameworkなど使うとわずか数行のコーディングでできてしまうのだけど、組込システムで使うのにはちょっと厳しいので、勉強も兼ねて作ってみた。
電子署名の仕組みを纏めると・・・。
- 元のデータに改ざんが行われているかどうかを検出する
- その方法として、暗号を使用する
- 全体を暗号化して渡すという手もあるが、データ量が大きいと時間がかかる
- そこで、データから固定長のダイジェストを作成して、それを暗号化する
- 「元データに署名をつける」ということは、
- 元データからダイジェストを作成
- ダイジェストを暗号化する
- 「コピーデータの署名を検証する」ということは、
- 暗号化された署名を復号化し、元データのダイジェストを取り出す
- コピーデータからダイジェストを作成する
- 先ほど復号化した元データのダイジェストとコピーデータを比較する
- ダイジェストにはSHA-1でハッシュを作成し、それを利用する
- 電子署名の作成（＝ダイジェストの暗号化）には、秘密鍵を用いたRSA暗号化を行う
- 電子署名の検証の際には、公開鍵を用いたRSA復号化を行う
- 必要な機能は
- ハッシュ生成アルゴリズム
- RSA暗号・復号アルゴリズム
- 多桁整数演算
他にも暗号鍵の生成などあるのだけど、そこは既存のツールを使うことにした。そのおかげで大きな素数の生成の手間が省けた。ここも興味深いところではあるが、とりあえず動くものができるのが先だった。
最も大変なのは多桁整数演算。1024×2ビット程度の整数演算が必要。これを同実現するか、なんだけど、思いついたのは、1バイトあたり下位4ビットを数値の表現に使い、必要な分の配列を用意する方法。これなら、足し算・掛け算の際の繰り上げを上位4ビットに保管できる。掛け算の際も、最大で0xF × 0xF＝0xE1なので収まる。一旦バイトごとに計算して、その後上位4ビットを桁上げ処理すれば楽だろうと思った。
最初は4バイト程度で検算しながらテストして、足し算・引き算・掛け算までは繰り上げ・繰り下げに気をつけてやればなんとかなった。割り算が結構面倒くさかった。割り算ができてしまえば、冪剰余はすんなりうまくいった。
これで計算して、別のライブラリで計算した結果とピタッと合ったときの感動と言ったら。カヤックやスキーで何か新しいことができるようになる、できなかったことができるようになるあの喜びと同じである。このうれしさはいくつになっても変わらない。そうは言っても世の天才が創り上げた世界をなぞってるだけなんだけど。
暗号鍵のeの選び方（ビット数）によって冪剰余の回数が変わる、つまり演算速度がかなり変わる。とりあえず実用範囲になるように素数を選んだ。
帰宅後ちょこちょこC++で作って1週間くらいかかった。多桁整数を扱うクラスを定義してoperatorをオーバーロードしていくとC++の勉強にもなるし数の扱い方などもよくわかるので、高校生くらいで取り組むといい勉強になるかもしれない。
いい勉強にはなったけど、この歳での今更感もある。もっと早く勉強しておけばよかった。若いうちは勉強とか練習とか修行とか鍛錬とか、やっといた方がいいよ。オッサンになるとそんなのが面倒になってくるから。
関連記事
