Voicyでバックエンドエンジニアをしているmasaです。
Voicyは音声配信プラットフォームなのですが、私自身もVoicyでvoi-chordというVoicyエンジニアが運営しているチャンネルでの発信をしており、そこでビットコインについての話から公開鍵暗号の技術について話したことをきっかけに、公開鍵暗号の仕組みについて興味を持ったので色々と調べてみました。
(voi-chordぜひみなさん聴いてみてください！)
公開鍵暗号とは？
まず、そもそも公開鍵暗号とは？というところですが、エンジニアであればこの暗号方式にはすごく耳馴染み自体はあると思います。
公開鍵暗号は、暗号化と復号に異なる鍵を使う暗号方式です。共通鍵暗号方式とは異なり、公開鍵と秘密鍵という2つの異なる鍵を使うことで安全性の高いものになっています。
(正直、私は今回ちゃんと調べてみるまではこの粒度くらいの理解で終わらせていました...)
公開鍵暗号は、「暗号化は誰でも行えるが、復号はメッセージの受信者のみが行える」というものになっています。
そのため、
- 暗号化は誰でも行えるため、暗号化のための鍵は公開される（公開鍵）
- 復号は正当な受信者のみが行うべきことなので、復号のための鍵は秘密にする（秘密鍵）
という2つの異なる鍵を使ってメッセージをやり取りします。
この方式によって、共通鍵暗号のように、事前に鍵交換を行わなくても安全なメッセージのやり取りが可能になりました。
そして、公開鍵と秘密鍵のペアを生成するための代表的なアルゴリズムとして、これまた耳馴染みのあるRSA暗号があります。
RSA暗号の仕組み
RSA暗号の安全性は、大きな整数Nは、素因数分解することが計算的に困難であるということに基づいています。
素因数分解の計算困難性とは？
大きな整数Nを作るのはとても簡単で、二つの大きな素数p, qを単純に掛け算するだけで作れます（N = p × q）。
p, qがいかに大きな値であっても単純な掛け算をするだけなのでNは簡単に求められます。
一方で、大きな整数Nを二つの素数p, qに分解する（素因数分解する）のは非常に難しいようです。
素因数分解のアルゴリズムは少し調べてみた感じではいくつか存在するようです(詳細は省きます)が、Nが大きくなればなるほど計算時間は爆発的に増加し、現実的な時間内で計算結果を求めることが不可能となります。
現在の実用的なRSA暗号では、約300桁ずつの2つの素数p, qをもとに、約600桁の数字Nが作られているそうです。
例えば、232桁（768ビット）のRSA暗号(RSA-768)の素因数分解は、単一のプロセッサで計算した場合、約2000年かかると推定されているそうです。
現在一般的に使われているRSA-2048は、現在では十分な安全性を提供できています。(2030年ごろには十分安全とは言えない可能性が出てくるとされ、新たなものが研究されているそうです。)
鍵生成のアルゴリズムとオイラーの定理
鍵生成アルゴリズムのステップ
RSA暗号の鍵生成は以下のステップで行われます。
-
2つの大きな素数p, qを選ぶ
- 必要なビット長の奇数を生成
- 例えば、RSA-2048では、Nが2048ビットの整数になるため、p, qはそれぞれ約1024ビット程度になります
- 「確率的素数判定法」を使って素数かどうかを判定
- ここでは、「確実に素数である」と言い切れるものではなく、「素数である確率が非常に高い数」を使っています
-
公開鍵の一部となる合成数Nを計算する
- N = p × q
-
Nと互いに素である数の個数を計算する
- Φ(N) = (p-1) × (q-1)
- これは整数Nと「互いに素である数」の個数を計算しています
- この式はNがどんなに大きな数字でも必ず成り立ちます
-
公開指数eを選ぶ
- よく使われる値は65537（2¹⁶+1）だそうです
- 公開指数eは、Φ(N)と互いに素である必要があります
- つまり、「公開指数e」と「Nと互いに素である整数の個数」が互いに素である必要があります
-
秘密指数dを計算する
- d × e ≡ 1 (mod Φ(N)) となるdを求めます
- つまり、(d × e) ÷ Φ(N)の余りが1となるdを求めます
これにより、公開鍵は(N, e)、秘密鍵は(N, d) という2つの数字のペアがそれぞれ生成されます。
暗号化と復号の計算式
RSA暗号での暗号化と復号は以下の数式で表されます。
- 暗号化の計算式: c = m^e mod N
- 復号の計算式: m = c^d mod N
(mはメッセージを文字列から整数に変換した数値です（ただし、N > mでなければならない）。)
ここまでだと、「このステップを踏めば公開鍵と秘密鍵を計算できる」ということは分かっても、「なぜこの計算で求めることができるのか？」ということは分かりませんね...
オイラーの定理とRSA暗号
実は、RSA暗号の基盤はオイラーの定理によって作られています。
オイラーの定理とは、互いに素な二つの整数mとNについて、m^φ(N) ≡ 1 (mod N) が成り立つというものです。
このおかげで、暗号化と復号が互いに打ち消し合うという重要な性質が生まれます。
数学的な詳細を知りたい方へ
これだけではよく分からないと思うので、実際にどうなっているのかを式を色々と見ていきましょう。
(個人的にはかなりややこしいと感じるので、「なぜこの計算で求められるか？」までに今は関心がない場合は読み飛ばしていただいても問題ないかと思います。)
オイラーの定理とRSA暗号
オイラーの定理とは上述の通り、mとNが互いに素な2数であるなら、以下の式が成り立つという定理です。
m ^ Φ(N) ≡ 1(mod N)
これを式変形していってみましょう。
まず、オイラーの定理の公式をk乗(kは任意の正の整数)すると、
(m ^ Φ(N)) ^ k ≡ 1^k(mod N)
となります。
これをさらに式変形していくと、
m ^ (Φ(N) * k) ≡ 1^k(mod N)
m ^ (Φ(N) * k) ≡ 1(mod N)
となります。
つまり、オイラーの定理の元の公式をk乗したとしても、「mod Nをとると余りが必ず1になる」という性質があることがわかります。
次に、このオイラーの定理をk乗した式に、さらに両辺にmを掛けてみましょう。
そうすると、
m * m ^ (Φ(N) * k) ≡ m(mod N)
m ^ (Φ(N) * k + 1) ≡ m(mod N)
という形で性質を変えないまま式を変形していくことができます。
一度、頭の片隅にm ^ (Φ(N) * k + 1) ≡ m(mod N)という式を置いておいていただきつつ、次は暗号化と復号の計算式に着目してみましょう。
こちらも上述の通りにはなるのですが、
暗号化の計算式 c = m^e mod N
復号の計算式 m = c^d mod N
と、それぞれなっております。
ここで、復号の式に、暗号化の式を代入してみましょう。そうすると、
m = (m^e mod N)^d mod N
m = (m^e)^d modN
m = m^(e*d) modN
という形にすることができます。
これはつまり、「mを、ed乗した値をNで割った余りはmになる」ということになり、
m^(ed) ≡ m(mod N)
ということになります。
この右辺の、m(mod N)ってどこかで見覚えありますよね...??
そうです、実は先に式変形したオイラーの定理の応用した式にも同じ形のものがあるのです！
つまり、これらを組み合わせて考えると、
m^(e*d) = m ^ (Φ(N) * k + 1)
となり、この両者が等しくなるためには、指数部分が等しくなければならないので、
e*d = (Φ(N) * k + 1)
ed ≡ 1(mod Φ(N))
という式を作ることができるのです。
つまり、RSA暗号の要件は、オイラーの定理を派生させることで満たせることができ、この「e*d ≡ 1 (mod φ(N)) 」という条件が、RSA暗号の核心となります。
これにより、暗号化と復号が互いに打ち消し合い、元のメッセージに正確に戻ることを保証することができます。
鍵生成アルゴリズムの簡単な例
鍵生成アルゴリズムを簡単な例で見てみましょう。
2つの素数p, qは、p=11, q=13とする。
N = 11 * 13 = 143
Φ(N) = (11 - 1) * (13 - 1) = 120
e = 31 (120と互いに素である数)
d = 151(d × e ≡ 1 (mod Φ(N))を満たす値)
公開鍵(N, e) = (143, 31)
秘密鍵(N, d) = (143, 151)
ここで、すごくシンプルな計算をするため、文字列"a"(以下、単に"a"と表記)を公開鍵暗号によってメッセージのやり取りをするとします。
まず、"a"を暗号化/復号できるようにするために、文字列から10進数の値に変換していきます。
"a"はASCIIだと、10進数で97になるので、97をそのまま使っていきます。
暗号化した数字は、
c = m^e mod N
で求めることができるので、これを今回の例で計算(繰り返し二乗法により計算)すると、
c = 97 ^ 31 mod 143 = 20
となり、"a"は、20という数字になって受信者と送信者間でやり取りされます。
次に復号の方を見てみましょう。
復号をするには、
m = c^d mod N
で求めることができるので、暗号化の時と同様に今回の例に当てはめて計算すると、
m = 20 ^ 151 mod 143 = 97
となり、きちんと復号でき受信者側は受け取ったメッセージを"a"と判断することができます。
まとめ
いかがだったでしょうか？
今回、ひょんな事から公開鍵暗号について関心を持ち、色々と調べてみましたがかなり数学的な知識が必要となり、理解に時間がかかった(完全にも理解していない)のですが、聞き馴染みはあるもののちゃんと知らない技術について学べてすごく良い学びになりました。
本記事が読んでくださっている皆さまの理解の一助になれると幸いです。
Discussion