No280 どうして公開鍵から秘密鍵がバレないのか？（２）

前回に続いて、公開鍵から秘密鍵を計算することの難しさについての解説を行います。

前回は巨大な素因数分解の難しさについて書きました。

今回は、離散対数問題と呼ばれる考え方について解説します。

今回は前回よりも数学の話が多い目になりますが、是非ご一読ください。

1. （再録）計算できないわけじゃない

大切なことなので、前回と同じ内容をもう一度書いておきます。

まず、大前提として、公開鍵から秘密鍵を計算することは不可能ではありません。可能は可能です。
そりゃそうです。計算なんですから、逆算ができないはずがないんです。

秘密鍵から公開鍵を計算するアルゴリズム（手順）のことを一方向性関数と呼びますが、一方向「性」であって、逆算ができないという意味ではないのです。

じゃ、何が一方向性なんだ？ってなるじゃないですか。

ここでの一方向性は逆算にメチャクチャ手間がかかる、ってことを意味します。

だから、可能といえば可能なんだけど、何百年とか何万年とか計算にかかるようなら現実的じゃないから事実上計算は不可能、だから安全だ、という理屈です。

ですが、そんな都合の良いアルゴリズムなんてあるんでしょうか？
それが今回のテーマです。

ここでは、以下の２種類の一方向性関数を紹介します。
　1.　素因数分解の難しさ
　2.　離散対数問題の難しさ

素因数分解の難しさについては前回お話しましたので、今回は離散対数問題にフォーカスします。

2. 対数とは？

対数というもの高校で習うのですが、文系のクラスの方など習っていない方もおられることでしょう。

ですが、対数をよくご存知でなくとも離散対数問題は理解できますので、ご安心を。

ここで必要となるのは、小学校でやる割り算のあまりの話と中学校で習う累乗の二つです。

これなら大丈夫ですよね。

3. 累乗

念のため、累乗について簡単におさらいしておきます。

例えば2×2×2のように同じ数字を何度か掛けることを累乗と呼び、左の例であれば、2の3乗と呼びます。
教科書などでは、2の右肩に小さな3を書いて累乗を示すのですが、メルマガではそのような表記ができませんので、2^3と書くことにします。

さて、累乗というのは何度も掛け算をすることになりますので、式には小さな数字しか出てこなくてもものすごく大きな値にすぐになってしまいます。

例えば、2の累乗をいくつか拾ってみます。
　2^2　＝　4
　2^3　＝ 8
　2^4　＝ 16
　　（中略）
　2^8　＝ 256

以下、10乗毎の値を示します。
　2^10 ＝ 1024
　2^20 ＝ 1,048,576
　2^30 ＝ 1,073,741,824
　2^40 ＝ 1,099,511,627,776
　2^50 ＝ 1,125,899,906,842,624
　2^60 ＝ 1,152,921,504,606,846,976
　2^70 ＝ 1,180,591,620,717,411,303,424
　2^80 ＝ 1,208,925,819,614,629,174,706,176
　2^90 ＝ 1,237,940,039,285,380,274,899,124,224
　2^100 ＝ 1,267,650,600,228,229,401,496,703,205,376

2を100回掛け合わせただけで31ケタもの数字になるのですね。

ここでは累乗をすると簡単に大きな値になることを覚えておいてください。

4. あまり

次は少々拍子抜けする話ですが、割り算の「あまり」が重要になります。

小学校で割り算を習った時に「あまり」のことを習いましたよね。
小学校ではその後、小数や分数を習いますので、「あまり」のことはそれ以降ほとんど触れられません。

ですが「あまり」というのはかなり奥が深く17世紀くらいから様々な性質が発見されているそうです。

とはいえ、ここでのあまりはひとつの割り算の結果のことを示すわけではありません。
ある計算をしたら、その結果をある値で割りそのあまりが答えになる、という妙なルールにもとづいた計算方法があるのです。

これを「法」と呼ぶのですが、これまた言葉では意味がわからないので、例を示します。

ここでは7を法とすることにします。
つまり、計算結果を必ず7で割ってそのあまりが答えになる、ということです。
この世界では、全ての答えが0～6になります。
なぜなら、7で割ったあまりですから、7より大きな値になるはずがないからです。

この世界ではこんな妙な答えになるのが正しいのです。

2×2×2＝1　　　　　（2×2×2÷7＝8÷7＝1あまり1 だから）
2×2×2×2＝2　　　 （2×2×2×2÷7＝16÷7＝2あまり2 だから）
2×2×2×2×2＝4　　（2×2×2×2×2÷7＝32÷7＝4あまり4 だから）
2×2×2×2×2×2＝1 （2×2×2×2×2×2÷7＝64÷7＝9あまり1 だから）

一見むちゃくちゃなのですが、妙に辻妻が合っているのにお気付きでしょうか？
例えば、二つ目の式は最初の式に×2を加えたものですが、答えもちゃんと2倍になっています。三つ目の式も同様で二つ目の式の値の2倍です。
ですが、四つ目の式では倍になりません。だって、7で割るのですからあまりが8になることはないからです。そのため、2倍しているはずなのに、答えは3つ目の式より小さい値になってしまいます。

この「7を法とした世界」は妙な世界なのですが、意外にも演算結果に矛盾が出ずちゃんと辻妻が合うのです。

法という考え方で着目していただきたい点は以下の二点です。
　・たくさん掛け算したからといって答えが大きくなるとは限らない
　・たくさん掛け算しても答えが小さくなる場合がある。

離散対数ではこの「法」の妙な性質をフル活用します。

5. 何乗したかの乗数が秘密鍵になるのだが...

離散対数では、「何乗したか？」という値（乗数と言います）を秘密鍵とします。

さて、２の累乗の表の一部を再掲示しましょう。

　2^10 ＝ 1024
　2^20 ＝ 1,048,576
　2^30 ＝ 1,073,741,824
　2^40 ＝ 1,099,511,627,776
　2^50 ＝ 1,125,899,906,842,624
　2^60 ＝ 1,152,921,504,606,846,976
　2^70 ＝ 1,180,591,620,717,411,303,424
　2^80 ＝ 1,208,925,819,614,629,174,706,176
　2^90 ＝ 1,237,940,039,285,380,274,899,124,224
　2^100 ＝ 1,267,650,600,228,229,401,496,703,205,376

この式の2^n のnの部分が乗数で、これを暗号鍵とし、計算結果を公開鍵とします。

ここで「なるほど」と思った方、甘いです。
このままでは乗数は秘密鍵として使いものになりません。
というのは、上記を公開鍵とした場合、大した労力をかけなくても秘密鍵である乗数を逆算できてしまうからです。

上の表でわかると思いますが、10乗する毎にほぼ3ケタずつ答えが大きくなっています。
つまり、ケタ数がわかれば、ほとんど計算なしでも乗数はほぼわかってしまいます。これでは秘密鍵としてはスジが悪すぎます。

実際、この程度の値であればexcelや関数電卓でもカンタンに逆算ができてしまいます。

6. 「法」の世界では大小関係がわからなくできる

そこで登場するのが、上述の「法」の世界です。
法の世界では、たくさん掛け算したあるからといって答えが大きくなるとは限りません。

これを活用すれば、乗数を隠すことができるのです。

今回は251を法とした場合の計算です。
　2^10 ＝ 65
　2^20 ＝ 115
　2^30 ＝ 77
　2^40 ＝ 113
　2^50 ＝ 1
　2^60 ＝ 20
　2^70 ＝ 149
　2^80 ＝ 219
　2^90 ＝ 115
　2^100 ＝ 34

いかがでしょうか。
公開鍵である計算結果の大きさと秘密鍵である乗数の大きさは無関係となっています。
つまり、形算結果を見ても、何乗した結果なのかわかりませんから、単純に公開鍵から秘密鍵を得ることができません。

実際、これをExcelなどで逆算する方法はありません。

秘密鍵を知りたければ、全ての乗数についてしらみつぶしに計算をするしかないのです。

7. 数百ケタもあれば現実的な時間で計算できない

さて、実際の離散対数を用いた暗号方式でははるかに大きな値を使います。

まず、秘密鍵である乗数は十分に大きな値でなければなりません。（通常は100ケタ以上の値）
また、それに劣らず大切なのはどんな値を法とするかです。
法の値を大きくすればするほど、逆算に必要な計算量が増えますので、安全性が高まることになります。どのようなアルゴリズムを使うかにもよりますが、これも通常は100ケタを越える値を利用します。

この離散対数を使うアルゴリズムもいろいろあるのですが、代表的なものがDSAやECDSAと呼ばれる電子署名に使われるアルゴリズムです。

素因数分解を使うRSA方式では250ケタを越える値を二つ使いますが、それに比べるとDSAの方が秘密鍵はコンパクトです。

だからといって、ケタ数の多いRSA方式の方が安全とは一概に言えません。
計算方法の異なる方式を並べて、ケタ数だけで安全度を測るのはあまりに乱暴な話です。

8. まとめ

前回と今回で、公開鍵と秘密鍵を使う公開鍵暗号方式の代表的な数学のアルゴリズムについて解説を行いました。

どんな方式でも秘密鍵から公開鍵を得ることはカンタンなのはいいのですが、その逆に公開鍵から秘密鍵が簡単に計算できるようでは秘密鍵として役に立ちません。

この一見矛盾した関係を実現してくれるのが一方向性関数というものです。

前回は素因数分解の困難さについての解説を行い、今回は離散対数問題の難しさについて解説をしました。

これを書いている2022年時点ではいずれも効率良く行う方法は人類は見い出していませんが、もしそんな方法が見つかりますと、その一方向性関数を根拠とした公開鍵／秘密鍵方式は使えなくなります。

これは大変なことです。

ですが、幸いなことに既に二種類の一方向性関数が見つかっています。万一、どちらかの方式が危殆化してもまだもう一つの方法が残っていることは僥倖だと思います。
その意味で当分は公開鍵と秘密鍵を使った暗号方式や電子署名方式は安泰でしょう。

また、今後も新たな一方向性関数が見つかる可能性もあることと思いますので期待したいと思います。

次回もお楽しみに。

（本稿は 2022年10月に作成しました）