RSAの公開鍵暗号のアルゴリズム4つ！RSA暗号の安全性について2つ

RSAとは？

RSAとはインターネット通信で用いられる公開鍵暗号の1つです。RSAは、2つの桁数が大きい素数をかけ合わせて積を求めるのは簡単でも、素因数分解が困難であるという非対称性により安全性を導き出したものです。1977年にRSAを発明したロナルド・リベスト氏、アディ・シャミア氏、レオナルド・エーデルマン氏の頭文字を取って名づけられました。この記事では公開鍵暗号であるRSAについて解説していきます。インターネット通信などの知識に触れることがほとんどないという人もいるかと思いますが、参考にできる部分や面白いと感じる部分があるかもしれません。

公開鍵暗号とは

公開鍵暗号とは「公開鍵」と「秘密鍵」という対となる2つの鍵を利用した仕組みです。公開鍵暗号では、まずは受信者が暗号化できる公開鍵と復号化できる秘密鍵の2つを作成します。公開鍵は送信者に渡すことでデータを暗号化して送信してもらい、受け取った暗号文は秘密鍵で復号化することで、平文に戻すという仕組みになります。暗号化に使用した鍵では複合できず、対となるもう片方の鍵が必要となるという特徴があります。

公開鍵暗号と共通鍵暗号のしくみ

共通鍵暗号方式では暗号化と復号化に同じ鍵を利用します。前述のとおり、公開鍵暗号方式では暗号化に使用する公開鍵と復号化に使用する秘密鍵の2つの鍵を使用しましたが、共通鍵暗号方式では暗号化と復号化に同じ鍵を使用するため鍵は1つだけになります。共通鍵暗号方式の場合は通信先ごとに鍵を作成する必要があり、さらに鍵交換の際に不正アクセスされないようにセキュリティを厳重に行う必要があります。

RSAに必要な前提の知識

RSAを知るためには前提として2つの知識が必要です。ここまで簡単にRSAについてご紹介しましたが、具体的な仕組みなどがわからないという方が多いでしょう。ここではRSAのアルゴリズムを知るために必要な前提知識として合同式の基礎やフェルマーの小定理について解説しますので、ぜひRSAを詳しく知るうえで参考にしてみてはいかがでしょうか。

合同式の基礎

合同式とは整数問題で多く登場する「余り」のみに注目した問題です。合同式では整数全体を特定の数で割ることで発生した剰余ごとに分類し、同じ剰余の整数をすべて合同とみなします。たとえば、11と6は5で割るとどちらも余りが1になるため、合同式では「11≡6mod5」と記述します。整数よりもその余りの方に関心がある場合、合同式を用いることで余りを導き出すことが可能になります。

フェルマーの小定理

フェルマーの小定理とは整数論分野で頻出する素数の性質についての定理です。pを素数とし、aをpの倍数でない素な自然数であるとした場合、aのp−1乗をpで割った余りは1になるという定理です。数学の定理では「フェルマーの最終定理」が有名ですが、それとは異なるため小定理と名づけられています。

RSAの応用について

RSAでどのような応用ができるか知りましょう。公開鍵暗号のアルゴリズムであるRSAを活用することにより、2つの応用が可能になります。ここではRSAの応用についてご紹介しますので、ぜひ参考にしてみてはいかがでしょうか。

RSAの応用1：通信の暗号化

RSAを応用することにより、通信の暗号化が実現します。暗号化とは、データを外部の人間にとって意味を持たない値に変換することを指します。RSAを利用することにより、通信データの暗号化が実現できます。RSAの応用でデータの暗号化と復号化が可能になるため、仮に送信途中で第三者の不正アクセスを受けた場合でも、内容を読み取られることはありません。そのため、情報漏えいの防止に繋がります。

RSAの応用2：デジタル署名

RSAを応用することにより、デジタル署名という技術が実現します。デジタル署名とは、送信データが送信元本人のデータで間違いないことを証明する仕組みです。データと一緒に、データをハッシュ値に変換したものを署名として送信し、受信者は受け取ったデータからハッシュ値を算出して、実際のハッシュ値と比較します。この仕組みにより、デジタル署名付きのデータであればデータの改ざんが行われていないことの証明になります。

RSAの歴史について

RSAの歴史についてご紹介します。RSAは1977年に開発者であるロナルド・リベスト氏、アディ・シャミア氏、レオナルド・エーデルマン氏の頭文字を取って名づけられた技術です。ここではRSAの歴史についてさらに詳しくご紹介しますので、RSAに興味が出てきた方はぜひ知っておくとよいでしょう。

歴史について1：1973年に考案していたが秘匿された

RSAは1973年にほぼ同じ暗号方式が考案されましたが、軍事機密として秘匿されていました。RSAに相当する暗号方式は、1969年に英諜報機関GCHQの職員ジェイムズ・エリス氏がアイデアとして理論を発見しました。さらにエリス氏からアイデアを聞いた数学者であるクリフォード・コックス氏が具体的な方法を考案しましたが、軍議機密として秘匿され、1997年まで世の中に公開されることはありませんでした。

歴史について2：1983年に特許登録された

現在知られているRSAは1983年にアメリカで特許登録されました。現在知られているRSA暗号のアルゴリズムは、前述の3氏によって考案され、1983年にアメリカで特許登録されました。さらに3氏によって設立されたRSA Data Security社がライセンスを独占していましたが、2000年9月6日に特許期間満了になって以降は、誰でも自由にRSAを使用できるようになりました。

RSAの公開鍵暗号のアルゴリズム4つ

RSAの公開鍵暗号には4つのアルゴリズムがあります。RSAの仕組みには、鍵ペアの作成、秘密鍵の作成、暗号化、複合という4つの段階があります。ここではRSAの公開鍵暗号のアルゴリズム4つをご紹介しますので、仕組みを知るうえで参考にしてみてはいかがでしょうか。

アルゴリズム1：鍵ペアを作る

RSAの公開鍵暗号では、まずは鍵生成アルゴリズムにより鍵ペアを作成します。公開鍵暗号方式では、事前準備である鍵生成アルゴリズムにより2つの鍵のペアを用意するところから始まります。データの受信者側は、鍵生成アルゴリズムにより「公開鍵」と「秘密鍵」という対になる2つの鍵を作成します。鍵生成アルゴリズムは実行するたびに異なる乱数を使用するため、ユーザーごとに異なる鍵ペアが作成されることになります。

アルゴリズム2：秘密鍵を作る

RSAの公開鍵暗号では、受信者側が秘密鍵を作成します。秘密鍵とは復号鍵とも呼ばれ、暗号化したデータからメッセージを復号化するために用いられる鍵です。受信者側で作成された秘密鍵は作成したユーザーにより秘密裏に保管され、公開鍵は他のユーザーにも公開されます。公開鍵を使用することで全てのユーザーはメッセージを暗号化することができますが、暗号化したメッセージを元の状態に戻せるのは受信者側のみです。

アルゴリズム3：暗号化

RSAの公開鍵暗号では、公開鍵による暗号化アルゴリズムを使ってメッセージを暗号化します。送信者側は受信者が公開している公開鍵を使い、暗号化アルゴリズムによって送信するメッセージを暗号化します。公開鍵はすべてのユーザーに公開されているため、送信者も事前に鍵を手に入れることができます。メッセージは暗号化された状態で送信され、受信者は暗号化されたメッセージを受け取ることになります。

アルゴリズム4：複合する

RSAの公開鍵暗号では、暗号化されたメッセージを復号アルゴリズムにより受信者が復号します。受信者が受け取った暗号文は、受信者が秘密裏に保管している復号鍵を使って復号されます。暗号化された文章を復号できるのは、公開鍵とペアになっている秘密鍵だけです。また、公開鍵はすべてのユーザーに公開されていますが、暗号化されたメッセージを復号できるのは秘密鍵を保管している受信者本人だけとなっています。

RSA暗号の安全性について

RSA暗号の安全性についてご紹介します。RSAを利用した公開鍵暗号方式を利用することで、メッセージ内容を悪意のある第三者に盗まれる心配はなくなります。しかしRSA暗号は素因数分解の難解さを根拠にしていますが、実際に同程度の安全性を担保しているわけではありません。ここではRSA暗号の安全性について解説しますので、RSAの安全性について詳しく知りたい方はぜひ参考にしてみてはいかがでしょうか。

素因数分解問題の計算は困難

RSA暗号が安全性の根拠としている素因数分解問題の計算は困難です。RSA暗号は素因数分解問題の計算の困難性を根拠として、素因数分解と同程度の安全性を期待した暗号方式ですが、実際には安全性が同じ値である証拠はありません。ただし、鍵の大きさが非常に大きい場合、素因数分解の計算には膨大な時間がかかります。民間であっても解読まで数年、軍事用であれば数億年かかる計算になるため、まず解読は不可能だと言えます。

NP問題とは

NP問題とは非決定性多項式時間を略した言葉です。NPは「量子コンピュータなどで多項式を解ける時間で解くことができる問題」であり、かつ「証拠があれば本当に正しいことを判定できる問題」を指します。RSAの安全性については安全であると期待されており、その反証はありません。ただしRSAはNP問題なので、仮に多項式時間では解けないことが証明できれば、P≠NP予想が肯定的に解決すると言えるでしょう。

初等整数論の知識が必要

RSA暗号の正しい理解には初等整数論の知識が必要です。RSAを正しく理解するためには、前述のとおり前提として合同式の基礎知識やフェルマーの小定理などが理解できている必要があるため、初等整数論の知識が必要です。そのため、初等整数論の知識がない場合はRSA暗号がどういったアルゴリズムで成り立っているのか理解することは難しいと言えるでしょう。詳しく知りたい場合は整数論の参考書を読んでみるとよいでしょう。

RSA暗号は代表的な公開鍵暗号の一つ

RSA暗号は送受信するデータの安全性を保つために必要な技術です。RSA暗号は公開鍵暗号の一つで、素数をかけ合わせて積を求めるのは簡単でも素因数分解は困難であるという非対称性を安全性の根拠とした技術です。ぜひこの記事でご紹介したRSA暗号のしくみや前提知識、応用などを参考に、RSA暗号について正しい見識を深めてみてはいかがでしょうか。