RSA暗号体験入門

元のデータ（平文）を送信者と受信者以外の人には解読不可能なデータ（暗号文）に変換する（暗号化）， または元に戻す（復号化）ための技法

　ここで，暗号技術で使われる基本用語を整理しておきましょう。

平文 ：	元のデータ（普通は第三者にも解読できる）
暗号文 ：	第三者に解読不可能な形式に変換されたデータ
暗号化 ：	平文を暗号文に変換する処理
復号 ：	暗号文を平文に変換する処理（復号化ともいう）

　一般的に暗号化と復号化には，平文と暗号文を関連付けるためのアルゴリズムと， 鍵と呼ばれる秘密の値が必要とされます。
　現在普及しているすべての暗号方式（RSA暗号やDES暗号等）では，そのアルゴリズムを知っていても， 鍵の値が分からなければその暗号文を解読することはできません。 つまり，暗号文を解読しようと試みる者を含めて誰に暗号化・復号化のアルゴリズムを知られていようと 全く問題がないのです。

　ところで，この暗号の概念は，金庫に例えて考えることができます。 例えば，メッセージを（鍵を使って）暗号化するということは， 「メッセージを金庫に入れて鍵を掛ける」ということに例えられます。 また，暗号文を（鍵を使って）復号化するということは， 「金庫の鍵を開けて中のメッセージを取り出す」ということに例えられます。 つまり，たとえ金庫の鍵が掛かる仕組み（アルゴリズム）を知っていても， その金庫の鍵を持っていなければ元のメッセージを読むことができないというわけです。
　また，異なる種類の鍵を用いて二重に暗号化する場合も，同様にして考えられます。 つまり，元のメッセージを金庫に入れて鍵を掛けて， さらにその金庫を別のさらに大きな金庫に入れて異なる鍵を掛けるというイメージです。
　さらに，三重あるいはそれ以上に暗号化する場合についても同様に考えることが可能です。
　ここで注目すべき事は，暗号化と復号化で同じ鍵を用いる場合 （秘密鍵暗号）と，異なる鍵を用いる場合（公開鍵暗号）があるということです。 後述しますが，これらの使い分けは暗号化の目的によります。 どちらにしても，復号化に必要な鍵の値を知らなければ，簡単に暗号文が解読されることはありません。

　暗号アルゴリズムでは，鍵の値を知っている者が行う計算は効率的でなければなりません。
　しかし，暗号文を復号するために，必ずしも鍵が必要というわけではありません。 例えば，時間さえかければあらゆる鍵を順に使って暗号文を解読しようと試みることもできます。 それを暗号文が正しく復号できる（意味のある文が現れる）まで繰り返せば， 暗号文から平文を導き出すことができます。
　このように，暗号文と公開されている暗号アルゴリズムから平文を導き出すことが理論上不可能だとは 限りません。
　一般に暗号方式の安全性は，復号化に必要な鍵を知らない状態で暗号文を復号するのにかかる 仕事の量（計算量）によって決まります。 もしそれが人間の寿命よりはるかに大きな時間を必要とするのであれば， それは安全とみなされるでしょう。
　暗号アルゴリズムの中には，可変長の鍵を持っているものがあります。 このような方式は，鍵の長さを長くすることでより安全にすることができます。 鍵の長さを１ビット増やした場合，その鍵を使って正当に暗号化（復号化）するための計算量は ほんの少しだけしか大きくなりませんが，不正に解読するための計算量は２倍になります （これはあり得る鍵の数が２倍になるからです）。 現在知られている様々な暗号方式の中には鍵が固定長になっているものがありますが， その鍵の長さを長くして類似のより強力な暗号アルゴリズムを作り出すことも可能です。

　ところで，一見すると，暗号アルゴリズムを秘密にしておけばアルゴリズムを公開するより 安全性を高く保てると思われるかもしれませんが，果たしてそうなのでしょうか。 実際のところ，米国では軍用の暗号方式のアルゴリズムは秘密にされています。 しかし，逆に商用の暗号方式のアルゴリズムはほとんどが公開されています。
　アルゴリズムを公開する理由は，たとえアルゴリズムを秘密にしていたとしても， それがいつ暗号を解読しようと企む者に知られてしまうか分からないからです。 例えば，攻撃者がリバースエンジニアリングを試みたり， 秘密にされているアルゴリズムを開発したチームの一員が漏らしてしまう場合などが考えられます。
　それならば，悪意を持たない一般の多くの人々に先にアルゴリズムを知らせてしまえば， もしアルゴリズムに欠陥があったとしても，積極的にその欠陥を警告してくれることを期待できます。 それにより，暗号の解読を企む者がアルゴリズムの欠陥を利用して企業秘密などを盗んだりする前に， 不正な解読を防止することができるわけです。
　どちらにしても，アルゴリズムを秘密にすることによって安全性が永遠に保証されるということには なりません。

　暗号には様々な方式がありますが，代表的な暗号方式は秘密鍵暗号方式と 公開鍵暗号方式の２種類に分類できます。
　秘密鍵暗号は，暗号化するための鍵と復号化するための鍵が同一の方式です。 つまり，金庫を閉めるための鍵と開くための鍵が同一ということであり， そのため鍵は送信者と受信者以外に知られてはなりません。
　公開鍵暗号は，暗号化するための鍵と復号化するための鍵が異なる方式です。 つまり，金庫を閉めるための鍵と開くための鍵が異なるということですが， 一方の鍵は秘密にしておく必要がありません。 普通は暗号化のための鍵を公開しておき，復号化のための鍵を秘密にしておきます （ただし第４章で詳述しますが，認証の場合は暗号化の鍵を秘密に，復号化の鍵を公開します）。

　秘密鍵暗号ではただ１つの鍵を必要とします。 そのため，受け手と送り手で同じ鍵を使うので，暗号通信をする前に外部に盗まれないように 鍵データを配送し，通信者が同じ鍵データを保有する必要があります。 しかも，通信する相手ごとに鍵データを共有しなくてはなりません。 このため，複数の人と通信する場合には，通信相手の数だけ複数の鍵を持たなくてはなりません。
　このことは，上述した金庫の例を使って説明され得ます。 まず送信者と受信者は予めメッセージを入れておくための金庫の鍵を１本ずつ保有しておきます。 これらは同じものですが，同種のものという意味であり同一のものではありません。 したがって，鍵を作成した者がもう一方の通信相手にその複製を何らかの方法で渡さなくてはなりません。 送信者はメッセージを金庫に入れて，鍵を掛けます。 そして，その金庫を受信者に送り，受信者は送信者が使った鍵と同じ（同種の）鍵を使って 金庫を開けて，メッセージを取り出します。 このように，金庫を閉める（暗号化）のと開ける（復号化）のに同じ鍵を用いるので， 金庫を閉めた鍵で再びその金庫を開けることができる事が秘密鍵暗号の特徴です。

　秘密鍵暗号の原理は比較的単純で，基本的には換字と置換を組み合わせたものです。 換字とは，文字を別の文字に置き換えるものです。
　例えば，秘密鍵暗号の一種のシーザー暗号では，ａはｄに，ｂはｅにというふうにアルファベットを ３文字後ろにずらすことで暗号化するというルールが決められています。 暗号化する際には，そのルール通りにすべての文字を３文字後ろの文字に置き換えます。 置き換えてできた文字列が暗号文です。 その暗号文を復号する際には，すべての文字を暗号化と逆の置き換え，つまり３文字前の文字への 置き換えを行えば正しく復号できるのです。
　以上のことから分かるように，秘密鍵暗号で送信者と受信者の間で同じ鍵を共有するというのは， 上の例では３という値を共有するということなのです。 アルゴリズムをお互いが知っているならば，送信者と受信者は鍵の値だけを共有していれば正しく 暗号化と復号化を行うことができます。

　一方，置換とは文字の順序を置き換えるものです。 このとき，どのように順序を置き換えたかのルールが暗号化の鍵に相当します。 シーザー暗号のような非常に単純な暗号方式を除いて，ほとんどの秘密鍵暗号はこのような 置換と換字の組み合わせによって成り立っています。 このような換字と置換を組み合わせる方法は無数に存在し，新たな秘密鍵暗号を作り出すことは 非常に簡単です。
　しかし，広範な利用形態で長期間使われる場合には，その安全性が保たれ続ける保証はありません。 現在，安全性がある程度保証されている最も有名な秘密鍵暗号の一つとして1977年にＩＢＭによって発表されたDES暗号があります。

　このように秘密鍵暗号は比較的単純なので，暗号化の計算時間は（公開鍵暗号と比べて）短くて済みます。 しかし，通信相手の数だけ鍵を保有しなくてはならないので，大勢を相手とする場合には適しません。
　また，秘密鍵暗号では，暗号文を送る前に送信者と受信者の間で安全な通信路を使って鍵を予め 送信することが要求されます。 例えば，送信者と受信者がお互いに遠く離れた場所に住んでいたとして，今すぐに電子メールを使って 電気的に通信をしたいとすると，まず最初に鍵をお互いに共有するために鍵を送信する必要があります。 ここで，送信中に鍵の値を盗聴されては困るので，盗聴されないような信頼できる通信路を利用する， あるいは鍵をさらに暗号化して送る必要があります。
　しかし，信頼できる安全な通信路を今すぐに利用することは不可能であり，また，鍵をさらに暗号化 したとしても，その暗号を解くための鍵がさらに必要になります。 このように，秘密鍵暗号では鍵の配送の方法が問題となるのです。 したがって，秘密鍵暗号では１対１で暗号通信する場合には暗号化の処理時間が短くて済むこともあり 実用上問題ありませんが，複数，特に不特定多数の人々と暗号通信する場合には問題が多く困難である といえます。

　公開鍵暗号では暗号化と復号化にそれぞれ一つずつ異なる鍵を必要とします。 つまり２種類の鍵が必要となります。 各利用者は一対の暗号化用の鍵データと復号化用の鍵データを生成し， 暗号化用の鍵データ（公開鍵）を公開し，復号化用の鍵データ（秘密鍵）を秘密にしておきます。 公開鍵は誰に知られても問題ないので秘密にしておく必要は全くありません。 例えば，平文データを送ってもらうときには，公開してある（知らせてある）公開鍵で暗号化して 送ってもらいます。 そして，その暗号文を受け取ったら，自分だけしか知らない秘密鍵によって復号化します。
　このことは，上述した金庫の例を使って説明され得ます。 まず，受信者はメッセージを入れる金庫を閉めるための鍵（公開鍵）と開けるための鍵（秘密鍵）を １本ずつ作成しておきます。 そして，受信者は金庫を閉めるための鍵（公開鍵）のみを送信者に渡します（知らせる）。 送信者はメッセージを金庫に入れて，受け取った公開鍵を使って金庫を閉めます。 そして，その金庫を受信者に送り，受信者は自分しか知らない秘密鍵を使って金庫を開けて， メッセージを取り出します。 このように，金庫を閉める（暗号化）ときと開ける（復号化）ときとで異なる鍵を用いますが， 金庫を閉めた鍵でその金庫を再び開けることはできません。
　ただし，暗号化に秘密鍵を，復号化に公開鍵を使っても正しく元の平文を得ることができます。 これは実はディジタル署名（後述する）を行う際に使う技法です。
　このように，一方の鍵で暗号化したものを復号化するには，もう一方の鍵を用いればよいのです。 ここで注意しなければならないのは，一方の鍵で暗号化すれば，もう一方の鍵を使わなければ それを復号化することができないということです。

　公開鍵暗号の原理は秘密鍵暗号のそれと比べて複雑です。 秘密鍵暗号を実現する原理はたった二つの仕掛け，つまり換字と置換の組み合わせだけでしたが， 公開鍵暗号を実現するにはそれとはまったく異なった仕掛けが必要となります。 公開鍵と秘密鍵が特別な関係で結ばれ，暗号化と復号化がきちんと機能するための原理を実現するには， 換字と置換といった単純な仕掛けだけでは不十分なのです。 つまり，もう少し数学的な仕掛けが必要となります。 この数学的な仕掛けこそが整数論なのです。
　公開鍵暗号を実現する代表的な方式としては，ＲＳＡ暗号，楕円曲線暗号，エルガマル暗号などがあります。 いずれも，整数論を利用した方式です。
　これらのうちで，ＲＳＡ暗号は1978年に発表された公開鍵暗号で，現在最も広く使われている暗号方式です。 この原理は，大きな数の素因数分解が難しいことに基づいており，経験的に安全性が確かめられています。
　また，エルガマル暗号の原理は離散対数と呼ばれる問題が難しいことに基づいており， 楕円曲線暗号の原理は，楕円曲線と呼ばれる曲線上の点の間で演算が定義でき， その上で離散対数問題の類似物（楕円離散対数問題）が作れることに基づいています。

　ここで，秘密鍵暗号と公開鍵暗号の長所と短所をそれぞれ整理してみましょう。

秘密鍵暗号

• 長所 ： ロジックが比較的単純なので，暗号化の計算時間は公開鍵暗号と比べて短くて済む。
• 短所 ： 送信者と受信者の間で安全に鍵の受け渡しを行うことが困難である。

• 長所 ： ロジックが比較的複雑なので，暗号化の計算時間は秘密鍵暗号と比べて長くかかる。
• 短所 ： 送信者と受信者の間で安全に鍵の受け渡しを行うことが容易である。