暗号理論（１）
はじめに
こんにちは、No.5です。
みなさんは暗号について興味を持ったことはあるでしょうか？
難しそうであまり興味がわかないと思っている方が多いと思いますが、暗号の中には理論がとても分かりやすいものがあります。
今回は、そのうちの公開鍵暗号とRSA暗号について紹介します。
公開鍵暗号とは
RSA暗号とは
まとめ
参考文献
公開鍵暗号とは
暗号では鍵を使って秘密を秘匿しますが、使用する鍵には次の種類があります。
共通鍵
公開鍵 [1]
共通鍵を使用する暗号が共通鍵暗号、公開鍵を使用する暗号が公開鍵暗号となります。
共通鍵暗号
共通鍵を生成する
暗号化するために鍵を使用して、復号するためにも同じ鍵を使用する
公開鍵暗号
公開鍵と秘密鍵のペアを生成する
公開鍵で暗号化したデータは秘密鍵で復号できる。公開鍵では復号できない
秘密鍵で暗号化したデータは公開鍵で復号できる。秘密鍵では復号できない
利用用途
公開鍵暗号の主な利用用途は次のとおりです。
SSL/TLS通信
電子署名
公開鍵暗号の種類
公開鍵暗号の性質を持つ主な暗号は次のとおりです。
このうち、RSA暗号を紹介します。
RSA暗号
Rabin暗号
ElGamal暗号
楕円曲線暗号
RSA暗号とは
1977年にRon Rivest、Adi Shamir、Leonard Adlemanの３人の暗号学者が発明しました。
この３人の名前のイニシャルをとってRSA暗号と名付けられました。
RSA暗号の仕組みは次のとおりです [2]
異なる２つの素数 𝑝,𝑞を用意して、𝑝∙𝑞を法𝑛とする
(𝑝−1)∙(𝑞−1)と互いに素な値を秘密鍵𝑑とする
𝑒∙𝑑≡1 (mod(𝑝−1)∙(𝑞−1)) となる値を公開鍵𝑒とする
秘密𝑀を暗号化するには𝐶=𝑀^𝑒 (mod 𝑛)とする
暗号化した値𝐶を復号するには𝑀=𝐶^𝑑 (mod 𝑛)とする
RSA暗号の例
仕組みを理解するために具体例で確認してみましょう。
まずは異なる２つの素数を𝑝=3, 𝑞=11、法𝑛を𝑝∙𝑞=33とします。
(3−1)∙(11−1)=20と互いに素な値である7を秘密鍵𝑑とします。
𝑒∙7≡1 (mod(3−1)∙(11−1))となる𝑒=3を公開鍵𝑒とします。
最後に、秘密𝑀を24とします。
秘密𝑀の24を公開鍵𝑒の3でべき乗すると、暗号化した値𝐶の30となります。
暗号化した値𝐶の30を秘密鍵𝑑の7でべき乗すると、秘密𝑀の24に復号できます。
秘密を求める
ここで、公開鍵𝑒で暗号化した値𝐶の30を取得した場合、秘密鍵𝑑を使用することなく秘密𝑀の24に復号できるでしょうか？
秘密𝑀をべき乗したした値（公開鍵𝑒）である3が公開されているので復号できそうですが、剰余演算（mod）を行っているので非常に困難なのです。
なお、剰余演算（mod）を行っていない場合は、
となり、次の計算で簡単に復号できてしまいます。
次に、公開されている値を利用して秘密鍵𝑑を求められるでしょうか？
公開される情報は次の２つです。
法𝑛 (=𝑝∙𝑞)
公開鍵𝑒
ここから秘密鍵𝑑を求めるには次の式を解けばよいのです。
法𝑛 (=𝑝∙𝑞)が公開されているので、ここから𝑝,𝑞を求められるでしょうか？
法𝑛 (=𝑝∙𝑞)から𝑝,𝑞を求めるということは𝑛を素因数分解するということになります。
問題１
素数𝑝と𝑞を掛けて91となる場合、𝑝と𝑞をそれぞれ求めよ。
答え
𝑝,𝑞={7,13}
小さな値の素因数分解は簡単ですね。
問題２
素数𝑝と𝑞を掛けて7031となる場合、𝑝と𝑞をそれぞれ求めよ。
答え
𝑝,𝑞={79,89}
こちらは難しかったのではないでしょうか？
問題３（RSA-129）
素数𝑝と𝑞を掛けて114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541（10進数）となる場合、𝑝と𝑞をそれぞれ求めよ [3]
答え
𝑝,𝑞={3490529510847650949147849619903898133417764638493387843990820577,32769132993266709549961988190834461413177642967992942539798288533}（10進数）
こちらは1977年、RSA暗号解読の懸賞問題として出題されましたが、
1994年、コンピューターを1600台用いて解読されています。
129桁（10進数）の値の素因数分解ができるまで17年かかったことになります。
実際に利用される値
電子証明書等で実際に使用されている法𝑛 (=𝑝∙𝑞)は300から1000桁（10進数）の値が使用されており、素因数分解は非常に困難です。
また、実際に使用されている公開鍵は次のように非常に大きな値（16進数）です。
3082010a0282010100d7283339d4d733e42cf2646e45f505ffc6bc05db5b7d894c1092d75ea7a213056adc927702277bcbbfcbeeb81852cb4b2cf8bb8813dc3f4f0af37eef18a96e7020764315b7b3719ee757204e29722902e1aff5d2f0ebd70c90b308cd6c5f2785b77de6d24d7b036eaf2d8159f2f76e4582b4c1e294df2a952a07d1dfb772198f3771ca01279f04a0d906d85cc64e671dea5196c5600f2a9b347f577737076c19ff259d5b450dbec9e29645f7eda7b475bf474f6dd5892e4d3829deb6f2d66b8e3af5c86b0daba9faf7632a439278516faa1eb2e4a2321f6ff5908594baddbb80a0fe2735ed579ef109e6416bdb916480a0f0334437f38fec83550d970acef8290203010001
安全性
RSA暗号は大きな値の素因数分解が非常に困難（効率的なアルゴリズムが発見されていない）であることにより安全性を確保しているのです。
ただし、量子コンピューターは素因数分解が高速に解けると言われているため、将来的にRSA暗号が現実的なコストで解読されてしまう可能性があります [4]
そこで、量子コンピューターでも解読が困難な暗号として耐量子暗号が研究されています。
まとめ
公開鍵暗号は公開鍵と秘密鍵のペアを生成し、一方の鍵で暗号化、もう一方の鍵で復号する。暗号化した鍵で復号することはできない
RSA暗号では、秘密𝑀を公開鍵𝑒でべき乗して暗号化し、秘密鍵𝑑でべき乗して復号する
RSA暗号は大きな値の素因数分解が非常に困難であることにより安全性を確保している
量子コンピューターでは素因数分解が高速に解けると言われている
いかがでしたか？
公開鍵暗号の１つであるRSA暗号は、素数と剰余演算を用いることによって暗号化と復号を簡単に実現していることがお分かりいただけたでしょうか？
アルゴリズムや安全性などについてさらに詳しく知りたい方は参考文献を参照してみてください。
参考文献
[1] WHITFIELD DIFFIE AND MARTIN E. HELLMAN, "New Directions in Cryptography", IEEE TRANSACTIONS ON INFORMATION THEORY, pp 644-654, Nov 1976.
[2] R.L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, Volume 21, Issue 2, pp 120-126, Feb 1978.
[3] Martin Gardner, "MATHEMATICAL GAMES A new kind of cipher that would take millions of years to break", Scientific American, Volume 237, Number 2, pp 120-124, Aug 1977.
[4] Peter W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, pp 124–134, Nov 1994.