何回かでRSA暗号の原理を解説します。RSA暗号の歴史は結構古く、1977年に数学者リベスト、シャミア、エーデルマンによって発表されました。頭文字を取って「RSA暗号」と呼ばれます。原理は高校数学の範囲は少し超えるくらいで、単純と言えます。しかし暗号文をどう作るか、どう解読するかは明らかにされていますが、第三者には事実上解読できないということになっています。その辺の事情は原理を勉強すれば理解できます。通常は見通しのよいすっきりした説明のために合同式を用いるところですが、今回は使わずに済ませます。
古い暗号にシーザー暗号というのがあります。決まった字数分、文字をずらすというものです。「こんにちは」→「しいねてふ」という感じです。ここではあいうえお順で2文字ずらしました。ずらす文字数が鍵です。この鍵は暗号をやりとりする者同志で共有しなければなりません。一応暗号と言えば暗号ですが、機密保持能力は極めて低く、第三者でも「シーザー暗号かな?」と思われてしまったらもう一気に鍵もバレ、解読されてしまいます。シーザー暗号では暗号化のための鍵と解読の鍵が一致しています(2文字ずらして作った暗号は2文字逆にずらして解読する)。こういう暗号は共通鍵暗号と呼ばれます。RSA暗号は公開鍵暗号のひとつです。公開鍵暗号では暗号化の鍵と復号化の鍵が異なっています。暗号化の鍵は公開され(公開鍵と言います)、復号化の鍵は暗号の受信者だけの秘密です(秘密鍵と言います)。暗号化前の通信文は平文(ひらぶん)と呼ばれます。黙って使ってしまいましたが、平文を暗号文に直すことを「暗号化する」と言い、暗号文を平文に戻すことを「復号化する」と言います。
公開鍵暗号は鍵の配送問題を解決しました。共通鍵暗号だと、何らかの方法で発信者と受信者が鍵を共有しなければなりません。鍵はもちろん発信者と受信者のペア毎に変えなければなりませんから、n人が相互に暗号をやりとりする状況では
の鍵が必要です。ご存じの通り、この式の値はnが増えると急速に大きくなります。これは鍵の管理に大きな手間がかかることを意味します。公開鍵暗号だとn人がそれぞれが自分の公開鍵と秘密鍵を持つだけでよいので2n個が必要なだけなのです。
さて、RSA暗号の原理です。以降、文字はすべて整数とします。を頻繁に使うので、簡単に説明しておきましょう。左辺は2項定理で展開すると
となりますから、の項(r=0の項)以外はすべてzで割り切れます。よって先の式が成立するわけです。
これで導入も準備も完了。次回にRSA暗号の原理を解説します。今回の記事は主に以下を参考にしています。このブログでも何回も紹介しています。大変優れた暗号の入門書だと思います。