RSA公開鍵暗号を紙上体験
相手以外の誰にも知られたくないメッセージを送りたいとき、どうすればよいでしょうか。電話は盗聴の危険性があります。メールだってシステム管理者が内容を盗み見ている可能性があります。
直接会って耳元で囁けば問題解決ですが、距離が離れていたり、大量の情報だったりするとお手上げです。そこで仮にメッセージを読まれたとしても、当事者以外の人には内容が分からないように秘匿化すればよいと考えます。この問題に人類は何世紀も取り組んできました。それが暗号化技術です。
暗号化されたメッセージであれば当事者以外には意味不明で読めません。そのため、第三者に分からずに安心して情報を伝え合うことができます。特に戦争状態にある国同士では部隊間の通信内容を傍受されてもいいように暗号化は欠かせません。
暗号と戦争の歴史や現代暗号に必須な素数に関する話が応用コーナーのプライバシーは素数が守るにあります。興味のある人は閲覧ください。
共通鍵方式による暗号
現在の暗号には大きく分けて共通鍵方式と公開鍵方式の2つがありますが、その歴史のほとんどは共通鍵方式によるものでした。共通鍵とは名前が示すとおり、暗号化する鍵と復号する鍵が送信側と受信側で共通、つまり同一鍵を使用するものです(対称鍵とも言う)。
暗号には送信側と受信側が存在します(送信側と受信側が同じなら、そもそも暗号に頼る必要がありません)。相手に送りたい可読なメッセージを平文(ひらぶん)と言います。その平文を一定のルールで可読不能にすることを暗号化、暗号文を平文に戻すことを復号と言います。
これまで強固で破られにくい共通鍵暗号が作られてきましたが、この方式にはずっと致命的な問題が付きまとっていました。それは暗号文を送る前に暗号化に使用した鍵を知らせる必要があるということです(相手はその鍵を復号に使う)。
共通鍵暗号で有名なのはDES(データ暗号化規格)です。IBMで開発されたDESはNSA(国家安全保障局:アメリカ)との繋がりから、バックドア(秘密の抜け道)があるのではないかとの噂が絶えませんでした。事実、NSAはDESの頑強さを検証しており、脆弱性をなくす名目で数々の見直しをIBMに指示していますが、当初128bitあった鍵長は最後には56bitにまで縮められるなど不可解な点もあります。そうは言っても、トリプルDESなどの手法で暗号強度を保全してきたDESが鍵長の割に堅固な暗号を提供したことは事実です(ちなみにDESの開発名はルシファー)。
ある意味、矛盾しています。どんなに完璧な暗号でも鍵が安全に相手に伝わらなければ意味がありませんよね。しかし、暗号の世界で鍵を安全に引渡すことは原理上不可能であろうとずっと思われてきました。
公開鍵方式による暗号 - 数百年に一度の発明 -
有史以来、解決方法はないと思われてきた安全な鍵の引渡しに関する方式が1976年(昭和51年)に発表されました。それが数百年に一度の発明と言われる公開鍵方式による暗号(公開鍵暗号)です。
公開鍵方式では、対になった鍵Aと鍵Bの2種類を使います。鍵Aで暗号化すると鍵Bでのみ復号でき、鍵Bで暗号化すると鍵Aでのみ復号できることになっています。要は一方通行な仕組みですね(非対称鍵とも言う)。
公開鍵の仕組みを発明したのは個人のプライバシーを守るべく、暗号技術を追い続けたホイットフィールド・ディフィーです。彼なしには公開鍵方式の暗号は生まれませんでした。初対面同士での安全なメッセージ交換、送信者と受信者の認証(デジタル署名)の恩恵は全て公開鍵暗号なしには考えられません。その後、彼はヘルマンと共に論文を発表。暗号界における革命を起こすことになります。
鍵Aは広く世間に公開します(インターネットや広報、メール等)。そして、みんなには鍵A(公開鍵)で暗号化して送ってもらいます。受け取った暗号文は自分だけの鍵B(秘密鍵)を使うことでのみ復号できます。
これで、事前に鍵を秘密裏に相手に伝える必要はありません。相手に「鍵Aで暗号化して送って」と伝えればいいだけです。不可能と思われていた安全な鍵の引渡しの概念が示されたわけです。
また、別の利用法もあります。鍵B(秘密鍵)で暗号化された文は鍵A(公開鍵)で復号できる限り、途中で改竄されていないことが証明できるのです。つまり、文が間違いなく鍵B(秘密鍵)を持った本人が作ったものでない限り、公開鍵Aでは復号できないのですから。
公開鍵暗号(RSA暗号)
理論的には素晴らしい公開鍵方式なのですが、実現できるかどうかは別問題でした(一方向性関数の発見がキーポイント)。ベイパーウェアのように概念上だけで存在する暗号方式だと考えられていましたが、なんと次の年にはMITの3人の研究者(リベスト、シャミル、エイドルマン)が4ヶ月の試行錯誤の末、大きな素数を利用した実現可能な方式を発表しました。
素数同士の掛け算は簡単なのに、その結果から元の素数を導くこと(素因数分解)は難しいという問題を提示したのはクヌースです。MITの3人組も同じ問題に辿り着き、RSA暗号における一方向性関数としました。
実はGCHQ(政府通信本部:イギリス)のジェームス・エリスが1969年に既に公開鍵暗号を着想していました。そして、1973年にはコックス、ウイリアムソンが実現可能な手法を僅か数時間で開発しています。ただ、認証や署名までは発想が及んでいなかったようです。そして所属する機関の性質上、画期的な発明はずっと機密扱いでした(公になるのはエリス没の1年後、1997年)。
それがRSA暗号です(3人の頭文字を功績のあった順に繋げたもの)。今では実績も確かで、多くの業界で使用されています。
他にも公開鍵方式の暗号が発表されており、楕円曲線暗号、エルガマル暗号、ナップザック暗号(後に破られる)などがあります。
RSA暗号以外にも誰にも知られずに二者間で鍵を共有する方法があります。ディフィー・へルマン鍵共有です。この方法で鍵を共有してから共有鍵暗号を使えば秘匿化が実現できます。
RSA暗号の実践
ここでは、RSA暗号自体の難しい理論は飛ばして、実際にRSA暗号をrpnで体験してみましょう。目的は平文を送信側で暗号化して、受信側に送り、復号することです。
-------------------- | --------------------
送信側 | 受信側
v
傍受(解読)
送りたい平文を次のようにします。極秘に手にいれた競合会社の見積額かも知れませんし、機密ファイルへのパスワードかも知れません。
「142857」
とにかく、このメッセージを途中で傍受されても解読されないように暗号化しましょう。「142857」を6つの数字と解釈して、「1」「4」「2」「8」「5」「7」を暗号化します。
一般的に解読とは鍵を使わないで暗号文から平文を得ようとする行為のことです。
本格的な暗号にするのなら、ジマーマンのPGP(Pretty Good Privacy)がお勧めです。PGPは信頼の輪というシステムで相手の公開鍵を取得できます。中央集権的な色合いの少ない公開鍵の管理システムと言えます。
RSA暗号を体験するために必要なステップは3つです。第一に準備、次に暗号化、最後に復号です。順に説明していきましょう。
RSA暗号の作り方(準備)
一番面倒な手順がこの準備段階です。公開する情報と秘密にする情報を先に算出しておきます。その手順は以下のとおりです。
1.素数の選択 |
2つの異なる素数を選び、それぞれをpとqとする。
|
|---|---|
2.法の計算 |
pとqを掛け合わせ、その結果をmとする(mを法(モジュロ)と呼びます)。
|
3.準備計算 |
p-1とq-1の最小公倍数を求め、その結果をrとする。
|
4.公開鍵計算 |
rとの最大公約数が1となる数を公開鍵aとする(1<a<(p-1)(q-1))。
|
5.秘密鍵計算 |
aと掛け合わせた後、rの剰余が1となる数を秘密鍵bとする。
|
6.周知と秘匿 |
mとaを公開、bを知られないように隠す。pとqの情報を破棄する。
|
まず、2つの素数を5と7にしてみます。すると法(モジュロ)はそれぞれの掛け合わせのことなので簡単な掛け算になります。
35
35ですね。この数値は公開されます。次に公開鍵の作成です。先にそれぞれの素数から1を減じた数同士の最小公倍数を計算します。
12
lcmは最小公倍数を求めるrpnプログラムです。応用コーナーの分数計算できない大学生にあります。興味のある人は閲覧ください。
5-1=4と7-1=6の最小公倍数は12になります。次に12との最大公約数が1になる数値を探します。ここでは1から30までの数値を試しています。
1 1
1 5
1 7
1 11
1 13
1 17
1 19
1 23
1 25
1 29
gcmは最大公約数を求めるrpnプログラムです。応用コーナーの分数計算できない大学生にあります。興味のある人は閲覧ください。
30までの間で1より大きい数値を公開鍵として使用できます。今回は公開鍵を5としましょう。
最後に秘密鍵の作成です。同じく30までの数値で秘密鍵と掛け合わせた数値のうち、12(それぞれの素数-1の最小公倍数)の剰余が1になる数値を計算します。
1 5
1 17
1 29
5, 17, 29が出てきましたので、秘密鍵として5を使用します。準備段階における結果をまとめると次のようになります。
1.素数の選択 |
2つの異なる素数を選び、それぞれをpとqとする。p=5,q=7
|
|---|---|
2.法の計算 |
pとqを掛け合わせ、その結果をmとする(mを法と呼びます)。m=35
|
3.準備準備 |
p-1とq-1の最小公倍数を求め、その結果をrとする。r=12
|
4.公開鍵計算 |
rとの最大公約数が1となる数を公開鍵aとする(1<a<(p-1)(q-1))。a=5
|
5.秘密鍵計算 |
aと掛け合わせた後、rの剰余が1となる数を秘密鍵bとする。b=5
|
6.周知と秘匿 |
mとaを公開、bを知られないように隠す。pとqの情報を破棄する。
|
モジュロの35と公開鍵の5を相手に知らせます。秘密鍵の5は誰にも見られないように自分で管理します。その他の情報は全て破棄しておきます(特に2つの素数)。
公開情報 |
モジュロ(m=35)と公開鍵(a=5)
|
|---|---|
非公開情報 |
秘密鍵(b=5)
|
RSA暗号の使い方(暗号化：平文⇒暗号文)
準備が整ったので、さっそく平文を暗号文にしましょう。暗号化の手順は少なく簡単です。
1.暗号化 |
暗号化したい数値(平文)のそれぞれを公開鍵aで冪乗、mで剰余する。
|
|---|---|
2.送信 |
得られた一連の数字(暗号文)を相手に送信する。
|
平文の「1」「4」「2」「8」「5」「7」を暗号化してみます。
1 9 32 8 10 7
それぞれの数値「1」「4」「2」「8」「5」「7」を公開鍵の5で冪乗して、モジュロの35で剰余計算しています。得られた数値は「1」「9」「32」「8」「10」「7」です。これが暗号文になります。
RSA暗号の使い方(復号化：暗号文⇒平文)
次は復号です。暗号化された数値を秘密鍵を使って元の平文に戻します。
1.受信 |
暗号文を受信する。
|
|---|---|
2.復号化 |
得られた一連の数字(暗号文)のそれぞれを秘密鍵bで冪乗、mで剰余する。
|
暗号文の「1」「9」「32」「8」「10」「7」を復号してみます。
1 4 2 8 5 7
秘密鍵の5で冪乗して、モジュロの35で剰余計算です。使用する鍵が異なる(今回は一致)だけで計算過程は暗号化と同じです。計算結果は「1」「4」「8」「8」「5」「7」。きちんと平文に戻りましたね。これが公開鍵方式によるRSA暗号です。
他の素数を使ってみよう
上の例題では簡単に説明するため、2つの素数を5と7にしました。偶然、公開鍵と秘密鍵は同じ5になりましたが、鍵が必ず同じになるわけではありません。もう少し大きな素数を使ってみると分かります。
例えば、素数を11と17にして追実験してみましょう。まず、公開鍵を計算するために(11-1)(17-1)の最小公倍数を求めます。
80
次に、この80との最大公約数が1になる数値を探します。
1 1
1 3
1 7
1 9
10まで試しましたが、1より大きい数値は3, 7, 9になりますね。このうちの3を公開鍵とすると、対応する秘密鍵はどうなるでしょう。
10まで調べましたが、該当なしです。一気に200まで調べてみましょう。
1 27
1 107
1 187
答えが出てきました。27、107、187です。つまり、公開鍵は3、秘密鍵は27になります。先ほどの例題よりは、ちょっと本格的になりますね。この鍵を使って暗号化と復号を行なってみましょう。
ここで暗号化と復号を行なうrpnプログラムを用意します。プログラム名はrsaです。引数に数値と鍵番号とモジュロ数を指定すれば、平文から暗号文へ、暗号文から平文に変換します。
では、モジュロ187(11*17)の公開鍵3で暗号化してみます。rpn式では以下のように書けます。
1 64 8 138 125 156
次に秘密鍵27で復号してみましょう。
1 4 2 8 5 7
このように、rsaプログラムがあれば暗号化と復号は簡単ですね。
rpnでのRSA暗号は極めて限定的で、RSAの暗号化に使用する冪乗の数が大きくなると、rpnの数値計算の精度オーバーとなってしまいます。実際に暗号を使用するには、平文からの数値化も含め、本格的にプログラムする必要があります。
次は…
公開鍵方式によるRSA暗号化の概要と実際を見てきました。暗号化と復号を2つの鍵(公開鍵と秘密鍵)で行なう方式は、それまで懸念材料だった鍵の引渡しに関して安全性をもたらしました。
適切に選択された素数から作り出されるRSA暗号であれば、破られることはほぼありません。しかし、小さな素数から作られたモジュロの場合、解読される可能性があります。
本記事ではRSA暗号の体験がメインなので、暗号の強度はありません。そこで、暗号文の「1」「9」「32」「8」「10」「7」を元の平文である「1」「4」「2」「8」「5」「7」に解読してみることにしましょう。
rpnプログラムを実行するには、rpn試用版かrpn標準版が必要です(バージョンの違いはこちら)。
seq, lookupはユーティリティーパッケージに同梱されています。rownumはカンタン分析パッケージに同梱されています。xypとnpdはrpnの姉妹ソフトウェアです。詳しくはプロダクトを参照ください。
/