RSA暗号の概要
RSA暗号は秘密鍵・公開鍵からなる暗号化理論であり、たとえばブラウザのSSL通信に利用されています。
SSL通信における RSA暗号の利用手順
SSL通信のバックグラウンドで用いられている RSA暗号は, サーバが作成した \( [公開鍵(n, r)], [秘密鍵s] \) から成る。
- クライアントは暗号対応ページ(所謂SSL対応ページ)を読み込むさいにサーバから\( [公開鍵(n, r)] \)を読み込んでおるのだ。
- クライアントはページを介して平文をサーバに送るとき(所謂フォーム送信)、読み込んだ公開鍵で暗号化して送信しておるのだ。
- サーバは暗号文を受け取ったら \( [秘密鍵s] , [公開鍵n] \) を用い復号することで平文をえているのだ。
ふつう隠蔽されており意識しない
これらの工程は ブラウザ(クライアント) 、Apache (OpenSSLモジュール)などのサーバソフトウエアが行っていることであるため、SSL通信のために私たちがこれを実装することは無い。
ただし RSA暗号は SSL 通信のみならず、パッケージソフトウエアのライセンスアクティベート機能の実装などに応用することも可能な理論であるので概要を理解しておくことは有害ではないだらう。
サーバにおける公開鍵・秘密鍵の作成
サーバソフトウエアが作成する公開鍵・秘密鍵の手順
- 任意の素数 \( p, q \)をとる。
- \( [公開鍵 n] = p \times q \)
- \( (p-1)(q-1) \) の最小公倍数を \(L\) とする。
- \(L\) 未満かつ, \(L\) の最小公約数以外の 任意の素数をとり、これを\( [公開鍵 r] \) とする。
- \( (r \times s) \ \rm{mod} \ L =1 \) （注1)を満足する整数を \( [秘密鍵 s] \)とする。
Apache, OpenSSL がバックグラウンドでやっていることであり、サーバサイドプログラムの実装において SSL通信のために このような工程を意識することは全くない。
クライアントにおける暗号化
\( [公開鍵(n, r)] \) を用いて以下のごとき暗号文をえる。
\( [暗号文] = ([平文])^{r} \ \rm{mod} \ n \)
ブラウザがやっていることであり、フロントエンドプログラムの実装において SSL通信のためにこれを意識することは全くない。
サーバにおける復号化
\( [秘密鍵s] , [公開鍵n] \) を用いて以下のごとき平文をえる。
\( [平文] = ([暗号文])^{s} \ \rm{mod} \ n \)
Apache, OpenSSL がバックグラウンドでやっていることであり、サーバサイドプログラムの実装において SSL通信のためにこのような工程を意識することは全くない。
（注1）RSA暗号を説明した多くのサイトでは \( 1 \ \rm{mod} \ x \) という表現になっておるが, ふつう私たちは (剰余 = 被除数 mod 除数）という表現に慣れておるため、此処では見慣れたその表現に書き換えている。
実際の RSA 暗号のために必要な要素
RSA暗号・復号の要領については上記のとおりであるが、実際のRSA暗号方式では、基本となる2つの素数に、非常に桁数が多いものをまず取るため、巨大な数・演算回数を、誤差を発生させずおこなうためのアルゴリズムが必要となる。
多倍長演算
256bit RSA 暗号方式の場合, 最初に任意にとる素数 \(p,q \) はそれぞれ 128bit である。たとえば C言語で実装しようとすれば, このような巨大なデータ型はない。そのため配列を用いて巨大な数を取り扱う「多倍長演算」というプログラム手法を実施しなければならない。
べき乗の高速化
最初にとる素数が非常に大きいため, 暗号・復号に於ける冪乗の乗数も必然的に相当に大きくなり、ふつうの四則演算で行おうとすれば尋常でない演算量となるので種々のアルゴリズムが考案されている。
膨大な回数のべき乗余
そもそも単なるべき乗計算ではなく、その後 mod をする必要がある。したがって一般的な四則演算だけで行おうとすればオーバーフローを起こす可能性がある。そのため、種々のアルゴリズムが考案されている。
そういったアルゴリズムについて
ここでは膨大な数を取り扱うためのアルゴリズムは扱わない。下記サイトによるとモンゴメリ冪乗法が有用のことである。