皆さん、こんにちは！
今回は、RSA暗号について紹介したいと思います。
RSA暗号って何？って人もちゃんとわかるように、まずは5分でわかる概要編です。
ちょっと読む時間はないけど、気になるなぁという人は、紹介ムービーを見てくださいね。
「共通鍵暗号」とは、「暗号化するための手順を知ると、暗号を解読することもできてしまう」種類の暗号を言います。
例えば、「文章中の各文字を3文字づつずらす」という暗号(こんにちは→すうのとへ)は、この手順を知ってしまえば解読もできます。
一方、「公開鍵暗号」とは「暗号化するための手順を知っても暗号を解読することができず、解読には秘密の手順を知る必要がある」種類の暗号を言います。
この「公開鍵暗号」には「楕円曲線暗号」や「RSA暗号」などがありますが、ここでは「RSA暗号」について解説します。
「共通鍵暗号」は暗号を作った相手から「暗号化の手順」を教えてもらわないと解読できないですが、「公開鍵暗号」は暗号化する手順をみんなに教えていれば、「秘密の手順」は誰にも教えなくても暗号を解読することができます。
それゆえ、「公開鍵暗号」は「共通鍵暗号」よりも「安全」といえます。
ここで解説した内容は以下の章で詳細を解説しています
変換方法はどんなのでもいいですが、「暗号の送り手」と「暗号の受け手」が同じ変換表をもつようにしましょう。
この変換表は誰にバレてもかまいません。むしろ、世の中に広く公開されている変換表（文字コード表）があるので、それを使いましょう。
さて、RSA暗号は「オイラーの定理」と呼ばれる数学の定理を使って成り立っています。
「オイラーの定理」を使うと、次の2つの事実が成り立つ、特殊な(p,n,s)の数字の組み合わせを沢山つくることができることがわかります。
事実その1 「ある数字をp乗した後でnで割った余り」からは元の数字を推測することは難しい
事実その2 「ある数字をp乗した後でnで割った余り」をs乗した後でnで割った余りは、元の数字と同じになる
ここで解説した内容は以下の章で詳細を解説しています
例えば、送りたいメッセージを「16」とし、(p,n,q)の組み合わせを、(5,34691,13709)だとします。
このとき、先ほどの「事実1」を見てみると、次の通りです。
16を5乗した後で34691で割った余りは、7846になります。
確かに、7846から16を推測しようと思っても難しそうですよね。まったく別の数字になっています。
今度は、「事実2」をみてみましょう。
7846を13709乗した後で34691で割った余りは・・・・・見事「16」になります！（計算すると本当になるんですよ）
元のメッセージ「16」を暗号化した「7846」を全世界の人間に伝えたとしても、元のメッセージ「16」は、秘密の数字「13709」を知っている人しか導き出すことはできません。
こうすることで、秘密の数字「13709」を知っている人以外には元のメッセージを推測されることなく、安全に「16」という数字を伝えることができます。
ここで解説した内容は以下の章で詳細を解説しています
nは、2つの素数を掛け算して作ります。
素数というのは、1とそれ自身以外約数を持たない数のことです。
先ほどの例で使った34691というのは、113という素数と、307という素数を掛け算して作りました。
次に、pとsですが、先ほど選んだ2つの素数をaとbと置くと、p×sの値が、(a-1)×(b-1)の値の「倍数」になるように調整して選びます。
調整は難しいのですが、上手に選ぶとpとsを選ぶことができます。
ここで解説した内容は以下の章で詳細を解説しています
素数は無限にあるので、初めに素数を選ぶときに、とっても大きな桁数の素数を選択すれば、他の人と同じ(p,n,s)になることは滅多にありません。
次に、それぞれが自分のpとnを他の人に知らせます。
(自分のホームページ上に載せるとか、メールで知らせ合うとかします)
メッセージを送りたい人は、自分のメッセージを数字に変換した上で、メッセージの送り先の人のpとnを調べ、「メッセージをp乗してnで割った余り」を求めます。
こうやって計算した数字は、元のメッセージを推測できないほどデタラメなものになるんでしたよね。
ここまで変換すると、安心して暗号化後のメッセージを相手に送ることができます。
(仮に他人にこの暗号化後のメッセージが漏れたとしても、わかりません)
この暗号を受け取った人は、自分のsを使って、「受け取った暗号をs乗してnで割った余り」を計算します。
すると、暗号を受け取った人は無事、元のメッセージを見ることができます。
他人は、受け取った人のsを知らないので、元のメッセージを見ることができません。
ここで解説した内容は以下の章で詳細を解説しています
なんでそうなるの？？？と思われた方は「詳細な解説を見る」をクリックしてくださいね。
今回は、RSA暗号について紹介したいと思います。
RSA暗号って何？って人もちゃんとわかるように、まずは5分でわかる概要編です。
ちょっと読む時間はないけど、気になるなぁという人は、紹介ムービーを見てくださいね。
1分目 「共通鍵暗号」と「公開鍵暗号」
暗号には大きく「共通鍵暗号」と「公開鍵暗号」の2種類があります。「共通鍵暗号」とは、「暗号化するための手順を知ると、暗号を解読することもできてしまう」種類の暗号を言います。
例えば、「文章中の各文字を3文字づつずらす」という暗号(こんにちは→すうのとへ)は、この手順を知ってしまえば解読もできます。
一方、「公開鍵暗号」とは「暗号化するための手順を知っても暗号を解読することができず、解読には秘密の手順を知る必要がある」種類の暗号を言います。
この「公開鍵暗号」には「楕円曲線暗号」や「RSA暗号」などがありますが、ここでは「RSA暗号」について解説します。
「共通鍵暗号」は暗号を作った相手から「暗号化の手順」を教えてもらわないと解読できないですが、「公開鍵暗号」は暗号化する手順をみんなに教えていれば、「秘密の手順」は誰にも教えなくても暗号を解読することができます。
それゆえ、「公開鍵暗号」は「共通鍵暗号」よりも「安全」といえます。
ここで解説した内容は以下の章で詳細を解説しています
2分目 RSA暗号を支える数学
まず、RSA暗号を使うにはメッセージを「数字」に変換します。（例えば、「あ」を「11」、「き」を「22」としたら、「あき」は「1122」になるといった感じです）変換方法はどんなのでもいいですが、「暗号の送り手」と「暗号の受け手」が同じ変換表をもつようにしましょう。
この変換表は誰にバレてもかまいません。むしろ、世の中に広く公開されている変換表（文字コード表）があるので、それを使いましょう。
さて、RSA暗号は「オイラーの定理」と呼ばれる数学の定理を使って成り立っています。
「オイラーの定理」を使うと、次の2つの事実が成り立つ、特殊な(p,n,s)の数字の組み合わせを沢山つくることができることがわかります。
事実その1 「ある数字をp乗した後でnで割った余り」からは元の数字を推測することは難しい
事実その2 「ある数字をp乗した後でnで割った余り」をs乗した後でnで割った余りは、元の数字と同じになる
ここで解説した内容は以下の章で詳細を解説しています
3分目 RSA暗号との関係
先ほどの2つの事実を見ると、うまく暗号の要素を満たしていることがわかります。例えば、送りたいメッセージを「16」とし、(p,n,q)の組み合わせを、(5,34691,13709)だとします。
このとき、先ほどの「事実1」を見てみると、次の通りです。
16を5乗した後で34691で割った余りは、7846になります。
確かに、7846から16を推測しようと思っても難しそうですよね。まったく別の数字になっています。
今度は、「事実2」をみてみましょう。
7846を13709乗した後で34691で割った余りは・・・・・見事「16」になります！（計算すると本当になるんですよ）
元のメッセージ「16」を暗号化した「7846」を全世界の人間に伝えたとしても、元のメッセージ「16」は、秘密の数字「13709」を知っている人しか導き出すことはできません。
こうすることで、秘密の数字「13709」を知っている人以外には元のメッセージを推測されることなく、安全に「16」という数字を伝えることができます。
ここで解説した内容は以下の章で詳細を解説しています
4分目 p,n,sの作り方
まずは、nから。nは、2つの素数を掛け算して作ります。
素数というのは、1とそれ自身以外約数を持たない数のことです。
先ほどの例で使った34691というのは、113という素数と、307という素数を掛け算して作りました。
次に、pとsですが、先ほど選んだ2つの素数をaとbと置くと、p×sの値が、(a-1)×(b-1)の値の「倍数」になるように調整して選びます。
調整は難しいのですが、上手に選ぶとpとsを選ぶことができます。
ここで解説した内容は以下の章で詳細を解説しています
5分目 RSA暗号の実際
暗号をやりとりしたい人は、全員が(p,n,s)の数字の組み合わせを作ります。素数は無限にあるので、初めに素数を選ぶときに、とっても大きな桁数の素数を選択すれば、他の人と同じ(p,n,s)になることは滅多にありません。
次に、それぞれが自分のpとnを他の人に知らせます。
(自分のホームページ上に載せるとか、メールで知らせ合うとかします)
メッセージを送りたい人は、自分のメッセージを数字に変換した上で、メッセージの送り先の人のpとnを調べ、「メッセージをp乗してnで割った余り」を求めます。
こうやって計算した数字は、元のメッセージを推測できないほどデタラメなものになるんでしたよね。
ここまで変換すると、安心して暗号化後のメッセージを相手に送ることができます。
(仮に他人にこの暗号化後のメッセージが漏れたとしても、わかりません)
この暗号を受け取った人は、自分のsを使って、「受け取った暗号をs乗してnで割った余り」を計算します。
すると、暗号を受け取った人は無事、元のメッセージを見ることができます。
他人は、受け取った人のsを知らないので、元のメッセージを見ることができません。
ここで解説した内容は以下の章で詳細を解説しています
終わりに
簡単にRSA暗号の概要を解説しましたがいかがでしょうか。なんでそうなるの？？？と思われた方は「詳細な解説を見る」をクリックしてくださいね。