🕌

暗号であまりの世界に素数が必要な理由〜離散対数問題ではない何か〜

2024/02/29に公開

はじめに

暗号理論を学んでいくと、「あまりの世界」つまりmodの世界で素数が必ず出現してきます。素数が用いられる理由で、離散対数問題の困難さ、つまり「公開鍵から秘密鍵を導出することが難しい」ことを数学的に保証してくれるから、というのはよく聞きます。
実は他にもあります。それは、有限体における割り算(正確には除算)を可能にしてくれるという理由もあります。なぜあまりの世界で素数が割り算を可能にしてくれるのか、素数でないとダメな可能性が出てくるのか、私の学習した範囲で記していきます。

有限体上の除算

「有限体上で除算ができる」というのは何を示しているのかというと、乗法逆元が存在するということです。つまり、ある元に掛けたら1になる元が有限体上に存在するということです。
整数で5÷5について見てみると、

5 / 5 = 5 * 1/5 = 5 * 5^{-1} = 1

このようになります。これは5に対してかけると1になる「5^-1」が逆元にあたります。これをあまりの世界はどうなるのか見ていきます。

まずは具体例

実際に有限体上に逆元が存在する例(mod 5)としない例(mod 6)をそれぞれ見てみます。
(整数でも同様ですが0以外で考えます。)

mod 5 (5で割ったあまりの世界) -> 素数

5で割ったあまりの世界(つまり素数で割ったあまりの世界)について、modのおさらいも兼ねてみてみます。元は全部で5つ(0, 1, 2, 3, 4)あります。割り切れたら0。あとはあまりが1から4まで存在して、あまり5は存在しません。この中で0以外で掛けたら1になる元をそれぞれの元で見つけていきます。

1 * 1 = 1 (mod 5)
2 * 3 = 1 (mod 5) -> 3 * 2も同じ
4 * 4 = 1 (mod 5)

このように0以外の要素で逆元を見つけることができました。

mod 6 (6で割ったあまりの世界) -> 合成数(素数ではない数)

さて6で割ったあまりの世界(素数ではない数で割ったあまりの世界)ではどうでしょうか。こちらは具体的に2で逆元を見つけてみます。(元の要素は0~5の6つです。)

2 * 1 = 2 (mod 6)
2 * 2 = 4 (mod 6)
2 * 3 = 0 (mod 6)
2 * 4 = 2 (mod 6)
2 * 5 = 4 (mod 6)
2 * 0 = 0 (mod 6)

このように6で割ったあまりの世界では、逆元をもたない元(今回の例では2)が存在することがわかります。

素数で割ったあまりの世界で逆元が存在する証明

ある数で割ったあまりの世界を考えるためにある数をmとします。つまり mod mこのことですね。

`m`が合成数の時

mが素数でない数(合成数)の場合について考えます。
mは素数ではないので下記のような掛けてmになるような元aと bが有限体上に存在します。

m = a * b, (1<a<m, 1 < b < m) \text{...①} (`a`か`b`が1の場合は素数なので2以上の数になります。)

この式を mod mの世界で表すと下記になります。

0 (\text{mod} \ m) = a * b (\text{mod} \ m) \text{...②}

もし a に逆元があったとすると、それをcとすると下記のように表せます。

a * c = 1 (\text{mod} \ m)

上記②の両辺にcをかけると、 a * cが1になるので、結果0=bになります。

0 = c * a * b = b

①でa, bともに2以上なので b = 0に矛盾が起きる。

`m`が素数の時

mod m で m が素数の場合に、「0以外の元に対して逆元があること」を見てみます。つまり0以外の元aに対して下記が成り立ちます。

a * b = 1 (\text{mod} \ m), a \neq 0 (\text{mod} \ m)\text{...①}

aは0以外なのでmで割り切れません、つまりmの倍数ではないと言えます。 aに0からm-1までの自然数をかけたm個の数に注目します。これらは全てmで割ったあまりが異なります。

a*0, a*1, a*2, a*3 ... a*(m-1)

本当に全ての要素は`m`で割ったあまりが異なる？

もしあまりが等しい元(i, j)があったとすると、0以上m-1以下の要素で同じaをかけてもあまりが等しいiとjが存在することになります。

0 \leq i \leq j \leq m-1, a*i = a*j (\text{mod} \ m)

つまりa*i = a*j (mod m)は移行して計算すると a(j-i) = 0 (mod m)となり、mで割り切れる、つまりmの倍数ということになります。

ただmは素数と仮定しているので、掛けてmの倍数ということは、aかj-iのどちらかがmの倍数ということになります。ただ上記①でaは(mod 0)にならないことが前提、つまりmの倍数にならないことに、注目するとj-iがmの倍数ということになります。jとiは0以上m-1以下の要素なので、jとiの差が一番小さくて0一番大きくて(m-1)-0でm-1が考えられます。

0 \leq j-1 \leq m-1

この中でmの倍数となれる逃げ道は0となる時です。

j-i = 0, i=j

iとjには同じ値が入ります。つまりaかけたもののあまりが等しくなるような下記の式

a*i = a*j (\text{mod} \ m)

が成り立つとすると、iとjは等しくなり、反対に言えばこの**iとjが異なればaをかけたあまりは異なる**ということが言えます。

a*0, a*1, a*2, a*3 ... a*(m-1)

上記のiを1としたり、jを2としたりしてもaと掛け合わせたあまりは必ず異なります、ということですね。

「掛けて1が存在するということ」は「逆元が存在するといういこと」に等しいのでmが素数であるmod mの有限体上で除算ができるということが言えます。

まとめ

暗号で使われる有限体(mod)の世界では、除算(逆元)を実現するのに素数が必ず必要になります。Diffie-Hellman鍵交換やRSA暗号、楕円曲線暗号やデジタル署名などにも逆元が必ず用いられます。
今回はなぜ有限体の中で逆元を必ずもつためには mod m のmが素数ではなくてはならないのかという、暗号を学んでいく中で疑問に思ったことを調べて記録してみました。これで仕事が増えるわけではないですが、面白いですね笑