近年、ビットコインなどの暗号通貨が登場してきました。こうしたものはRSA暗号や楕円曲線暗号などの暗号技術に支えらえています。RSA暗号とは、ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの3人の暗号研究者が1978年に発明した公開鍵暗号の一つです。これは桁数が大きい合成数Nをp×qと素因数分解するのが困難であることを利用した暗号です。p、qが小さい素数の場合に、公開鍵と秘密鍵を求めてみましょう。
・暗号とは
メッセ－ジは文章で書かれていますが、文字と空白を数字に対応させることで、メッセ－ジ（平文）を一つの大きな自然数ｍに対応づけることができます。公開鍵暗号とは、第三者が読めないように、公開鍵を用いて数ｍを別の数値Mに変換して送信する技術です。受信者は、秘密鍵を用いて暗号文Mを元の平文値ｍに復号します。公開鍵暗号では、公開鍵から秘密鍵を推定できないように工夫されています。
・剰余とは
暗号化には平文ｍより大きな数を法とする剰余計算を用います。剰余計算とは、ある数（法）で割った余り（modulo）を与える計算です。例えば法13における50の剰余は、50を13で割った余り11となります。これを
・ 50 mod13＝（3×13+11）mod13＝11
と表記します。剰余計算により、暗号文Mが法より大きくなるのを防ぎます。
剰余計算には
・ A×B mod C＝（A mod C）×（A mod C）mod C
といった性質があります。例えば、A=50、B=41、C=13の場合
・ 41 mod 13=（3×13+2）mod13＝2
ですから、
・ 50×41 mod13＝(50 mod13)×(41 mod13)＝11×2 mod13＝(13+9) mod13＝9
となります。こうした規則を用いると、計算量を減らすことができます。
・オイラ－数φ(N)とは
Nより小さい正の整数のうち、Nと互いに素な自然数の個数をオイラ－数φ(N)と言います。N=10の場合、10より小さく、10と互いに素な数は、｛1、3、5、7｝の4つなので、φ(10)＝4となります。素数pの場合、pより小さく、pと互いに素な数は｛1、3、5、・・・p－1｝のp－1個なので、φ(p)＝p－1となります。pと異なる素数qを用いて、N＝pqと素因数分解できる場合は、｛1、3、5、・・・p－1｝×｛1、3、5、・・・q－1｝によって生ずる(p－1) (q－1)個の数はいずれもNと互いに素であるので、φ(N)＝(p－1) (q－1)となります。
正整数ｍ、Nに対して、ｍ、Nが互いに素であるとき、
・ ｍ^φ(N)≡1 mod N ・・・（1）
が成り立ちます。これをオイラ－の定理といいます。ここでｍ^3＝ｍ・ｍ・ｍの意味です。N＝pqの時は、Nに素な数ｍに対して
・ ｍ^(p－1) (q－1)≡1 mod pq ・・・（2）
が成り立ちます。法pqの下では、平文ｍの指数を増やしていくと、(p－1) (q－1)乗で元に戻る周期的な性質があることを示しています。RSA暗号はこの性質を用いて、作られています。
（1）N=21（p＝3、q＝7）の場合
N＝p×q＝3×７と因数分解できる場合を考えます。(p－1) (q－1)＝2×6＝12です。Nを法とする場合、剰余値には0~20までの21個の数しか現れません。表1にべき乗の21を法とした値を示します。
表1 べき乗の21を法とした値
これは左端のある数ｍ（1≦ｍ≦20）に対して、1乗、2乗、3乗、・・・26乗した値に対して法21をとった結果を表にしたものです。法21の下では、7乗、13乗、19乗、25乗すると、1~20の値が元の値に戻ることが分かります。この表から、指数が6増加すると周期的に同じ値を繰り返すことが分かります。つまり（2）式
・ ｍ^6 mod21≡1
が成り立っていることを示しています。周期6は、(p－1)と (q－1)の最小公倍数（LCM）になっています。平文値ｍがべき乗で同じ値になるのは、指数がn・LCM＋1乗（n=1,2,3,,,）になるときです。つまり、7、13、19、25、31、37、・・・乗の場合です。25は5×5と表せるので、公開鍵を5、秘密鍵を5にすればよいことが分かります。つまり平文値ｍを公開鍵で5乗して暗号化し、秘密鍵で5乗すれば復号できます。秘密鍵d＝5は、（2）式
・ 5×d mod 6 ≡ 1
を満たしています。なぜなら、
・ 25 mod 6 ＝(6×4＋1) mod 6 ≡1
だからです。表1で、例えば平文値が4の場合、4を5乗すると、暗号値は16になります。さらに5乗すると暗号値16は元の平文値4に復号されます。ｍがどんな値であっても
・ （ｍ＾5）^5 mod 21＝ｍ^25 mod 21≡(ｍ^6)^4・m mod 21≡ｍ
が成り立つので、ｍは25乗すると元に戻ります。