【簡単】素数の使い道|RSA法を解説

【簡単】素数の使い道|RSA法を解説 数学

「素数て何? 素数って何の意味があるの? 素数を見つける公式とかあるの? 数学ってなんだか難しそうだな…」

こういった疑問に物理学修士の筆者が答えます。

結論

素数とは、1より大きく、1とそれ意外では割り切れない数です。詳細は本記事にて解説します

本記事の参考文献

本記事の内容

スポンサーリンク

素数とは

素数一覧

素数とは、1より大きく、1とそれ意外では割り切れない数です。例えば上表のように、2と3は素数ですが、4は1と4以外に2で割り切れるので、素数ではありません。
素数は歴史が古く、古代ギリシアの数学者ユークリッドがおよそ2300年も前に記した『原論』にもしるされています。また、オイラーのn×(n+1)+41という式のように、素数の一部を見つけ出す式はありますが、素数の登場のしかたは非常に不規則で、未だに素数を見つけ出す式や法則が発見されていません。

スポンサーリンク

素数の使い道

素数はSUICA、クレジットカードなどに暗号として使われます。なぜ素数が暗号に使えるのかというと、素数と素数を掛け算することは簡単ですが、ある数字が何の素数と何の素数の掛け算かを言い表すことが難しい(コンピュータでも解読するのに時間がかかりるの)です。暗号にはRSA法という代表的なものがあり、RSA法を以下に紹介します。

RSA法

RSA法

1977年、米マサチューセッツ工科大学のロン・リベスト、アンディ・シャミア、レン・アドルマンの3人の研究者によって考案されました。従来では暗号カギがバレると解読されるリスクがありましたが、RSA法では暗号カギがバレても解読ができないというメリットがあります。RSA法で公開カギと秘密カギを作る方法は以下のようになります。

公開カギと秘密カギの作成

n,eを公開カギ、p,q,dを秘密カギとします(p,dは素数、n=pq)
ある数e,dを、ed mod{LCM(p-1,q-1)}=1となるように選びます。

LCM:最小公倍数を求める LCM(2,5)=10
mod:割り算の余りを求める 13mod5=3
  1. まず、秘密カギとなる二つの素数(pとq)を決めます。
    例としてp=3,q=7とします。すると、この二つの素数の積である公開カギ(n)はn=21となります。
  2. 次にもう1つの公開カギ(e)を決めます。
    eは適当な正の整数とします。ここでは、e=5とする。
  3. もう1つの秘密かぎ(d)を求めます。
    dは「eをかけて、p-1とq-1の最小公倍数で割ると、あまりが1となる」ような数にします。
    今回の例では、「p-1とq-1の最小公倍数」は2と6の最小公倍数の6です。dは「5をかけて、6で割ると、余りが1となる」ような数で、これは1から順に考えていくと、d=5です。先ほどつくった公開カギをつくって、平文を暗号化します。

暗号化

先ほど作った平文を暗号化します。
平文をM、暗号文をCとしたとき、暗号化(M→C)の式は、C=Memodnです。

平文(M)を暗号化します。例として、M=12とします。暗号文(C)は、「Mをe乗してnで割った余り」で求められます。暗号化は公開カギ(nとe)だけで行えます。
暗号文は、「12の5乗を21で割った余り」となり、125=248832を21で割ると余りは3。暗号文C=3となります。

複合

秘密ガキを使って、複合文が平文にもどるか確認します。
複合(C→M)の式は、M=Cd mod n
複合は、暗号化(平文Mをe乗してnで割った余り)と逆向き(対照的)の計算を行います。上の式がそれに該当します。
平文(M)は「暗号文Cをd乗してnで割った余り」で求められます。復号には秘密カギ(d)の情報が必要となります。秘密カギ(d)の値を公開カギ(n)から求めることはできません(※nがpとqに素因数分解されてしまった場合を除く)。
平文(M)は、「3を5乗して、21で割った余り」となります。35=243なので、21で割ると余りは12。暗号化する前の平文M=12に戻りました。

↓さらに数学について知りたい方はコチラ↓

スポンサーリンク