RSA暗号ってなに?

暗号

歴史

1977年に発明され、発明者であるロナルド・リベストアディ・シャミアレオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる

Wikipediaより引用

RSAというのは3人の頭文字を繋げて付けられた名前なんですね。

もともと公開鍵暗号方式という考え方は提案されていたのですが、それを実現する良い方法は見つかっていませんでした。難しいですよね、秘密鍵を持っている人だけが復号できる暗号方式なんて。

そんな中、この天才3人が考案したRSA暗号はとても素晴らしい方法ですぐに広まりました。

さらにすごいところはこのRSA暗号は40年経った今でも用いられていることです。ちなみに私達がよく使っているLINEの文章もこの方法を用いて暗号化してから送られています。

RSA暗号は公開鍵暗号の1つ!

暗号は主に2種類、共通鍵暗号方式と公開鍵暗号方式があります。その違いは以下で説明しているのでぜひ先にそっちを読んでください!

共通鍵暗号方式と公開鍵暗号方式
はじめに 暗号化の方法ってどんなのが有名なんですかね??1つも聞いたことねえよって方は普通だと思います(笑) 文字を1体1に対応する別の文字に置き換える置換や、前後の文字にずらす(例えば3つ前にずらすならeがbになる)シーザー暗号な...

具体的なアルゴリズム

公開鍵暗号方式はみんなが知っている鍵で暗号化し、自分だけが知っている鍵で復号しますよね。

RSA暗号は数学を用いてそれを可能にしています。その方法はすごく簡単なのに斬新です!!!私は考えた人をマジな天才だと思っています。

んじゃまずは具体例から見ていきましょう。

今回はAliceがBobに”Hello”という文章を送るという設定にしましょう。ちなみに暗号の例ではAさんとBさんではなく、AliceさんとBobさんがよく使われるんで覚えておいてください(笑)

数字への置換

まずは平文(暗号化されていない文章)を数字に置換します。置換の方法は簡単に以下の方法にします。

英字abcdefghijkl
数字010203040506070809101112
mnopqrstuvwxyz
1314151617181920212223242526

するとHelloは”0805121215″と変換されます。ちなみに置換だけでも暗号の一種ですよ。これだけだとすぐにバレちゃいますが。

 

暗号化

次は公開鍵と秘密鍵の設定ですね。RSA暗号では公開鍵は2つあります。1つ目は2つの素数の積\(n\)です。今回は2つの素数5と11の積である55にしましょう。そして2つ目は\((5-1) \times (11-1) = 40\)と互いに素で40以下であるような整数な数を選びます。今回は7にします。

そして次は大事な秘密鍵です。今回の場合、秘密鍵\(t\)が満たすべき条件は40未満で$$7 \times t \equiv 1 \bmod 40$$です。つまり\(t=23\)となります。

これで準備は整いました!それでは暗号化してみましょう。

今回は公開鍵が55と小さいので、平文(”0805121215″)も小さく区切って暗号化しましょう。ということで数字2桁ずつ暗号化します。

まずは08からですが、暗号化は簡単です。08を公開鍵7乗し、もう一つの公開鍵55で割った余りを求めるだけです。つまり、\[8^7 \equiv 2 \bmod 55\]となるので、02に暗号化されます。

同様にして05,12,12,15はそれぞれ25,23,23,05と変換されるので、全部をつなげ合わせると\[“0225232305″\]となります。これで暗号化は完了です!

 

復号

では受け取った側は”0225232305″をどうやって復号すればよいのでしょうか。

それも簡単です。2つずつ区切って秘密鍵を用いて同様の作業を行えばよいのです!具体的には秘密鍵は23なので、最初の02を取り出して23乗して55で割った余りを求めます。つまり、\[2^{23}\equiv 8 \bmod 55 \]となります。

同様に25,23,23,05に対しても同じ作業を行うと、05,12,12,15となります。これらを繋げると\[0805121215\]となり見事復号に成功しました!

どうですか、凄くないですか??

私は初めてこの方法を知ったときはかなり感動しましたね~。まさに天才です。

おわりに

ざっとどんな流れなのかは掴めたと思いますが、考えることはまだまだあります。例えば

  • 公開鍵から秘密鍵はバレないのか?
  • なんで復号できるのか??
  • 公開鍵から条件を満たす復号鍵はちゃんと存在するのか???

などですね。ここからは理論的なところを解説していきたいと思います。が、長くなりそうなので別の記事にしますね。高校生以上なら誰でも分かるように解説したいと思っているので興味がある人はぜひ見てください!!

RSA暗号 ~理論編~
はじめに こちらがRSA暗号の入門編の記事です。あまり詳しくない方はこっちから読んだほうがイメージできると思います! 今回は理論的な側面からRSA暗号を見ていきます。 アルゴリズム ここから数式たくさん出てきますよ~! ...

コメント

タイトルとURLをコピーしました