デジタル署名と暗号技術
公開鍵暗号の計算の特徴
公開鍵暗号を実現する計算手順（アルゴリズム）は一つだけではありません。
しかし、アルゴリズムには、以下の条件が必要です。
暗号化の鍵をＥ、
復号化のための鍵をＤ、
平文をＭ、
暗号文をＣとすると、
① 暗号化が容易であること：ＭとＥからＣを求める計算が容易であること。
② 復号化が容易であること：ＣとＤからＭを求める計算が容易であること。
③ 暗号文が破られないこと：ＣとＥからＭを求める計算が非常に困難であること。
④ 暗号化の鍵から復号化の鍵が破られないこと：ＥからＤを求める計算が非常に困難で
あること。
⑤ 暗号化・復号化が出来ること：ＭとＥからＣを求め、ＣとＤから元のＭに戻ること
ＲＳＡのアルゴリズム
有名な公開鍵暗号の一つＲＳＡのアルゴリズムを見てみましょう。
ＲＳＡを使用するには、公開鍵と秘密鍵の組を作成する必要があります。
ここでは、アリスとボブがＲＳＡを使用して通信することにします。
鍵の組を作るのには、まずアリスは、非常に大きな素数ＰとＱを無作為に選択します。
次に、この二つの素数の積をＮとし、さらに、任意の整数ｅを（Ｐ－１）（Ｑ－１）と
互いに素となるように選択します。
Ｎとｅの組が暗号鍵（公開鍵）になります。
（例）アリスが二つの素数として ４７、 ７１ を選択したとします。
（実際には、公開鍵暗号に使用するすべての整数は非常に大きいが、
ここでは、わかりやすいように小さな整数を使用します。）
Ｐ＝４７ Ｑ＝７１
Ｎ＝Ｐ＊Ｑ＝４７＊７１＝３３３７
アリスは、次の式から、暗号鍵を３２２０と互いに素になるように選択します
（オイラー関数）。
Ф（Ｎ）＝（Ｐ－１）＊（Ｑ－１）＝４６＊７０＝３２２０
アリスは、ｅ＝７９を選択したとする。
これで、拡張ユークリッドの互除法と２つの素数（アリスだけが知っている）を使用して、
復号鍵の要素ｄを計算できる。
ｅｄ＝１（ｍｏｄФ（Ｎ））・・・ｄはｍｏｄФ（Ｎ）をとったうえでの逆元
ｄ＝７９－１（ ｍｏｄ３２２０）＝１０１９
アリスは、公開鍵情報すなわち、Ｎ＝３３３７とｅ＝７９を公開する。
たとえば、ボブが整数６８８（平文）を暗号化してアリスに送信する場合、
彼は、公開鍵登録簿を見に行き、アリスの公開鍵を検索する。
自分が暗号化したい数６８８を７９乗して、その結果を３３３７で割った余りを計算する。
アリスの公開鍵 ｅ＝７９
Ｎ＝３３３７
６８８７９ｍｏｄ３３３７＝１５７０
アリスは、１５７０（暗号文）という数を受けると、ボブと同じ操作を復号鍵１０１９を
使用して行う。
１５７０１０１９ｍｏｄ３３３７＝６８８
アリスの秘密鍵 ｄ＝１０１９
ｍｏｄФ（Ｎ）＝３２２０
Ｐ＝４７ Ｑ＝７１
電子署名の仕組み
電子署名システムは、公開鍵方式の暗号鍵を逆に使用し、本人認証に利用するものです。
ある人の公開鍵に対応する秘密鍵は、事実上、世界に一つしかありません。
もし、ある公開鍵でメッセージを復号化出来たら、その公開鍵に対応する唯一の秘密鍵
で暗号化されたことが確認されます。
そもそも、電子署名は何故するのでしょうか？
それは、第１に、文書が改竄されるのを防ぐことにあり、第２に、自分の書いた文書が
本当に、本物であることを相手が確認出来るためにします。
つまり、電子署名には次のような重要な機能があるということです。
完全性：ファイルまたはメッセージが改竄されたかどうか分かる。
認証 ：メッセージに署名した人物の名前を数学的に確認出来る。
参考文献：「ＰＧＰ 暗号メールと電子署名」 Simson Garfinkel 著 山本和彦監訳