暗号コラム④
第4回 RSA暗号 後編：そしてRSA暗号へ…
前回までのあらすじ
こんにちは、鈴木です。前回は不思議な整数剰余の世界を紹介しました。一体何に役に立つのだろうとか思った方もいるかと思います。読んでいて心拍数がみるみる上昇したという人もいたそうですね。後編となる今回は、RSA暗号のココロを紹介したいと思います。
暗号のココロとは
暗号と聞いて我々はどのような動作を期待するのでしょうか。簡単にまとめると次の2点になります。
・ 暗号化したい文章が暗号化できて、暗号文から元に戻せる。
・ 鍵が無いと暗号文から解読できない。鍵があると簡単に戻せる。
それぞれ詳しくみてみましょう。
暗号化したら戻したい
暗号は秘密の通信を行うための道具です。ですが、暗号化した後に元の文章（平文、「ひらぶん」と読みます）に戻せないと意味がありません。暗号化して戻す、そのロジックを実現するために初等整数論が利用されます。RSA暗号では、整数を整数剰余の世界へ送ってしまう、というアイデアを活用します。整数剰余は普段の常識とは異なる不思議な世界ですか、きれいな性質を持っています。RSA暗号にはそのきれいな性質が上手く使われています。
鍵が無ければわからないはずだ
暗号は情報を秘匿するために使います。ですが、鍵なしで解読出来てしまうと元も子もありません。鍵が無いと解読が難しい状況にする必要があります。RSA暗号では、素因数分解の難しさを利用する、というアイデアでその難しさを保証しています。記念すべき第一回目のコラム『アルゴリズムとは何か』でいかに素因数分解が難しいのか、という話をしました。その難しさがRSA暗号の安全性を担保しています。
これがRSAだ
これらを念頭にRSA暗号の構成を具体例と共にみていきましょう。暗号は鍵とアルゴリズムで構成されるのでした。RSA暗号もまた、鍵の作り方、暗号化、復号の手順の3つ組となります。
鍵の作り方
1. 2つの異なる素数 p, q を選ぶ。
2. n = p * q を計算する。
3. (e * d) -1 が (p-1)(q-1)で割り切れるような整数 e, d を選ぶ。
4. 公開鍵として(e, n)の2つ組、秘密鍵として(d, n)の2つ組とする。
暗号化
1. 暗号化したいメッセージ(自然数)を m とする。ただし、m < n を満たす必要がある。
2. c = meを計算し、 n で割った剰余を求める。
3. c を暗号文とします。
復号化
1. m’ = cd を計算し、 n で割った剰余を求める。
2. m’ を復号文とする。正しい鍵の組み合わせならば m = m’ となる。
もったいぶった割にはシンプルな構成です。公開鍵 n を因数分解して p と q が判明すると簡単に d が計算できてしまいます。しかし、「n を因数分解」するのが難しいという事実がそれを防いでいます。
具体例を見てみましょう
シンプルとはいえ、数式の羅列だけではわかりづらいものです。せっかくなので簡単な例を計算して見ましょう。
鍵の作り方
1. 2つの異なる素数 p = 3, q = 7 を選びます。
2. n = 3*7 = 21 を計算します。
3. 整数 e, d としてe = 5, d = 17 を選びます。
4. 公開鍵として(5, 21)の2つ組、秘密鍵として(17, 21)の2つ組とします。
暗号化
1. 暗号化したいメッセージ(自然数)を m = 11 としましょう。
2. c = 115 = 161051を n = 21 で割った余りは 2 となります。
3. 2 を暗号文とします。2から11を導くことができますか？
115を暗算や手計算でやろうとすると大変だと思います。計算機の場合は、上手いアルゴリズムが存在するので比較的簡単に計算することができます。
復号化
1. 217 = 131072 を n = 21 で割った余りは 11 となります。
2. 暗号化したいメッセージと復号した結果が一致しました。
何だか狐に包まれた…じゃなくてつままれたような気分になります。
理想と現実
これでもう秘密の通信がやりたい放題…と言いたいところですが現実はそう甘くありません。まず、RSA暗号は計算に時間がかかるという問題があります。上記の例だと数値が小さいので簡単に計算できますが、 2015年現在使われているものは n が最低でも617桁(2048bit)もあります。より安全性を高めるために4096bitまで桁を大きくする必要があるとすら言われています。そんな桁数ではいくら計算機といえども時間が掛かります。
また、 n を素因数分解する以外にもRSA暗号への攻撃方法は複数存在します。素因数分解の難しさだけでは攻撃を防ぐことはできません。現実に使われているRSA暗号は上記のような素朴な実装ではなくそれをベースに様々な工夫を施した実装がされています。
鍵の作成や暗号・復号といった操作は、理屈を抜きにすれば かけ算、わり算といった小学校3, 4年生でやるような計算しか登場しません。とある知人は「RSA暗号って、算数だよね」と言い放ちました。身も蓋もなく、確かにその通りです。ですが、裏を返せば小学校で習う算数にも面白い世界があり、情報通信を支える応用もある、といえるのではないでしょうか。
参考文献
- 楫元 『工科系のための初等整数論入門』 培風館 2000