鍵交換の話【新歓ブログリレー2020 15日目】

こんにちは、minyです。この記事は新刊ブログリレー2020 15日目の記事となります。
現在、車校に合宿で通い仮免を取って路上を練習で走っています。正直事故りそうで怖いです。(自分の出身では教習所を自動車学校と呼び、略して車校って呼んでました)
今回は、自分の中で流行ってる暗号化の中から鍵交換の話をしていきます。

余談
ホントは暗号化のRSA書いたりとかしたかったけど教習所で時間がない(書く気力がない)のでやめます

はじめに

東工大といえば素数が好きな奴が多いって偏見がありますよね。自分のことを言えば確かに特別感があって好きです。なので、素数の活用例として暗号化を調べてたらハマってしまったのです。今回は、素数の判定法の有名なのを一つと鍵交換の有名なのを一つ紹介しようと思います。

ミラーラビン素数判定法

素数好きならほぼ知ってると思う有名な判定法(だと思っている)
証明は省きますが、以下を行うことで素数である確率を最低 $1 - 4^{k}$ で判定できます

$n > 1$ の奇数と、正確度 $k \in N$ を入力
$n - 1$ を $2^{s} \cdot t (t \in O)$ という表示にする
以下を $k$ 回行う
- $1 \leq a \leq n - 1$ の $a \in N$ を無作為に選ぶ
- $a^{d} \neq \equiv 1 m o d n$ で、かつ $0 \leq r \leq s - 1$ の全ての $r \in N$ について $a^{2^{r} d} \neq \equiv - 1 m o d n$ ならば $n$ は合成数として終了する
$n$ は素数として終了する

pythonの実装例

main.pyimport random

def miller_prime(n, k):
    if n < 2:
        print('invalid number')
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d //= 2
    for i in range(k):
        a = random.randint(1, n - 1)
        m = pow(a, d, n)
        if m != 1:
            for j in range(s + 1):
                if m != n - 1:
                    m = pow(m, 2, n)
                else:
                    break
            else:
                print(f'{n} is composite.')
    else:
        print(f'{n} is probably prime.')

miller_prime(279151800551159, 100)
# 279151800551159 is probably prime.
# これは、最低 1 - 4^(-100) ~ 1 - 6.2*10^(-61)の確率で素数です

miller_prime(4, 10)
# 4 is composite.
# 確実に合成数です　何から構成されているかはわかりません(今回は2^2ですが)

Diffie-Hellman鍵交換

他人に通信を傍受されている可能性のあるインターネットでは、送信するデータを暗号化したいと思うものです。ですが、残念なことに鍵をそのまま送ってしまってはそれも傍受される恐れがあり意味がありません！なのでメールで別にパスワードを送る風潮はさっさと消えればいいと思います（自分はしたことないです）。
脱線したので戻ります。何とかして鍵を交換する方法はないでしょうか？世の中には頭がいい人がいるもので、計算は楽だが逆算が非常に難しい問題をうまく用いて、鍵を交換する方法を見つけた人がいるのです。なのでその名前が鍵交換にそのままなりました。
その計算とは何でしょうか？それは以下のような奴です。

x^{g} \equiv y m o d p

...はい。何が難しいんだという話です。多分以下の問題は誰でも解けるでしょう。

x = 2, g = 10, p = 11 の 時 、 y の 値

ですが、次のように出されるとどうでしょうか？

x = 3, y = 5, p = 17 の 時 、 g の 値

少なくともさっきの問題に比べ、時間がかかったのではないかと思います。実は $p$ が非常に大きい素数の時、上の問題と下の問題には非常に大きな計算時間の差が存在し、下の方が非常に時間がかかることが知られています(離散対数問題と呼ばれる)。なので、この計算量の非対称性を利用した鍵を交換する方法をDiffie-Hellman鍵交換(DH)と呼んでいます。方法は以下の通りです。

AさんとBさんは適当に $x, p$ を決め、交換する。( $p$ は非常に大きい素数)
AさんとBさんはそれぞれ $g$ を $1 < g < p$ の範囲で決め、その計算結果の $y$ を交換する。(それぞれ、 $g$ の決めた値を $g_{a}, g_{b}$ とし、計算結果を $y_{a}, y_{b}$ とします。
Aさんは、Bさんからきた $y_{b}$ で、 $F \equiv y_{b}^{g_{a}} m o d p$ を、Bさんは $E \equiv y_{a}^{g_{b}} m o d p$ を計算します。
この計算をすると、実は $F = E$ となっています。これは、 $m o d$ の性質から証明できます。（省略します)
この $F = E$ を共通の鍵として用いることで、安全に鍵を交換できたことになります。

もし傍受されていたら

とは言え、もし傍受されていたらどうなるでしょうか。通信下に流れた数字は $x, p, y_{a}, y_{b}$ の4つです。先ほども述べた通り、これらから $g_{a}, g_{b}$ を導くのは計算量が非常に大きく現実的ではありません。なので、あとは強力な共通鍵暗号であるAESなどを用いて通信することで、傍受者に情報が流出することを防げます。

終わりに

先ほどあげた離散対数問題はRSA暗号にも用いられています。最近はpが1024bitとかだと解けるかもしれないなどと言われており、2048bitが推奨されています。その他に楕円関数やツイストエドワーズ曲線を用いたものがあるようです。僕は詳しくは知りません。
個人的にDiffie-Hellman鍵交換がとても好きで、その計算ができるline botを家のラズパイ上に稼働させて誰かと試してみたいな(弱い素数の時の解読とか)と思っていたのですが、特に相手になる人の当ても無かったためline botを作ってほかってあるという悲しい状態になってます。何のために作ったのか
もしよかったら、以下の簡易暗号化をした会話を解読してみてください。誰もしないと思うけど

会話

A:10進数でx=2, p=10290167にしようぜ
B:わかった
A:y=128319になった
B:y=778219だわ
A:どうやって暗号化する？
B:文字をutf-8で16進数にして、それを10進数に変換して鍵を掛け算したものにしようぜ
A:17251172461440826145321712257071953
B:1366754403316462314609423949179452429892591507863840954729792730
A:695125992857415759437425992237922826287122025171847127047405122960788955058204588627709408219786320691909183610740418094398344153560560705333731283491
B:2414849730928897046413963985337039398081643695800525011414280232192890064628257980279475018439078230590699849915427709517354176259605540
A:130909222324838499554314807451477793698896331025834129751848938919270007998896315509276408611470172646116922970523705
A:39483945373018821852062691733195220861498877
B:39483955234115567703063705161959697374955577
A:41919307805660593617464838668705847427963574763733459911556535538466065
B:74065015888951858607141414637999770477436318119233074289149632175135319165138248829190394376653885608822183568683627920449111906723181750855697
A:1242625604917647739868954028073795930487971097242174659449312018833865610108059546241050767578657758654953440347060792779676388858909828165349042275421
B:703290604623794904273867990939764595247718513964049710310258007484470206849931

予告

明日書いてくれるのはebiくんと、sappi_redくんです。個人的に気になる内容とか上げてくれるみたいなので楽しみですね