No279 どうして公開鍵から秘密鍵がバレないのか？

多少でも電子署名や暗号化のことを調べますと必ずと言っていいほど「公開鍵」と「秘密鍵」の話が出てきます。

そしてその多くでは「秘密鍵があれば公開鍵はカンタンに計算できるが、公開鍵から秘密鍵を求めることはできない」といった記述があります。

ですが、いったいどんな仕組みでそれを実現しているのでしょうか？

今回はその根拠を述べます。

1. 計算できないわけじゃない

最初によくある誤解を解いておきます。

公開鍵から秘密鍵を計算することは可能です。

そりゃそうです。計算なんですから、逆算ができないはずがないんです。

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

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

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

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

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

どちらも数学の話ではありますが、それほど難しい話ではありませんので、是非おつきあいください。

2. 素数とは？

今回は素因数分解の難しさについてです。

素数というものがあります。
これは、「2 以上の自然数で、正の約数が 1 と自分自身のみであるもののこと」になっています。

これではわかりにくいので具体例でいきましょう。
7は2とか3とかのどれでも割り切れません。もっと言うと1と7以外では割り切れません。こういった数を素数と呼びます。
一方、6＝2x3と分解できますので素数ではありません。（合成数と言います）

ですので、以下はいずれも素数です。
　2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...

なお、素数は無限に存在するそうです。

3. 素因数分解とは？

次に、素数と素数の掛け算を考えてみます。

例えば 13×19 としましょう。

これ、手でも筆算すれば答えが出せますよね。

13×19＝ 247

ですが、この逆算はどうでしょうか？
答えしかわからない状態で逆算できますか？

247＝？×？
として、この二つの？を求める方法ってことです。

「いや、数学よく知ってる人ならこんなのちょちょいと計算する方法知ってるでしょ」となりそうなものです。
ところが、意外なことに、人類はその方法を未だ見い出していません。

ですから、247がどの数字なら割り切れるかを一つづつしらみつぶしに調べるしかありません。

247÷2 は？　→　末尾が奇数だから計算するまでもなくムリだ
247÷3 は？　→　計算すると82あまり1だからダメ
247÷5 は？　→　末尾が0でも5でもないからムリ
247÷7 は？　→　計算すると35あまり2だな。やっぱダメだ
247÷11は？　→　計算すると22あまり5で、これもダメだ
247÷13は？　→　お、これなら19で割り切れる。

と、答えを得るまでに６回の試行が必要です。

この手順を素因数分解と言います。

最初の掛け算に比べると、かなり面倒なことがわかります。
上の例では、実際に6倍の計算をやっているのですから。

余談：
　上記では、4,6,8,9,10,12などの割り算は省略しています。
　だって2で割れなければ、4,6,8,10で割れないのは明らかですものね。

4. 大きな数の素因数分解はコンピュータでもキツい

前述の例くらいの小さな値なら電卓を使えば何とかなります。

ですが、少し大きな数になると、人には手に負えなくなります。
例えば、379241は２つの値の掛け算なのですが、こんなの電卓使ったって苦行でしかありません。

この答えは 541×701なのですが、541は100番目の素数、701は126番目の素数です。
つまり、試行しないといけない回数は100倍となります。

勘の良い方はお気付きでしょうが、これが100万番目の素数だとか、1億番目の素数を使えば、100万倍とか1億倍の試行回数が必要となるわけです。

ここまで試行回数が多くなるとコンピュータといえどもかなりの苦行となります。

たかだか3ケタの数値ですら100倍以上の試行が必要ですが、実際に暗号や署名に使われる素数は300ケタ以上ですので、1億倍どころではなく、1兆倍の1兆倍の1兆倍の1兆倍の1兆倍といった試行回数となります。

つまり、あまりに手間がかかるので事実上逆算ができないということです。

この素因数分解の難しさを根拠としている暗号方式にはRSA方式などがあります。

余談：
　たまに、誤解した解説記事を見かけるので補足しておきます。
　RSAの公開鍵は上記の素数を掛けた値ではありません。
　公開鍵から秘密鍵を逆算する過程で素因数分解が必要だという話です。

5. まとめ

一方向性関数というものがあります。

これは、ある計算はごくシンプルだけれど、その逆算をやろうとすると全ての組み合わせを試行錯誤するしかないから、膨大な時間がかかるというものです。

暗号方式や電子署名で使われる公開鍵と秘密鍵というのは、この性質を利用しています。

今回は、代表的な一方向性関数として、素因数分解の難しさを利用した一方向性関数について解説をしました。

これを書いている2022年時点では素因数分解を効率良く行う方法は見つかっていません。

ですが、もし方法が見つかったとしますと、素因数分解を根拠とした公開鍵／秘密鍵方式は使えなくなります。これは大変なことです。

次回は今回書ききれなかった離散対数問題の難しさについて解説をします。

次回もお楽しみに。

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

本Noteはメルマガ「がんばりすぎないセキュリティ」からの転載です。
当所はセミナーなどを通して皆さんが楽しく笑顔でITを利用いただくために、 難しいセキュリティ技術をやさしく語ります。
公式サイトは https://www.egao-it.com/ です。