wassup?

プログラミング、ボドゲ、ボカロ

DH鍵交換を手でやると変な事になった。DH鍵交換の素数は安全素数を選ぶ必要があるらしい。

まとめ

現実逃避に、DH鍵交換を手でやってました。
手で試すと、運悪く不思議なケースを引きました。
調べると、DH鍵交換がうまく行かないケースは次の2つがあるようです。

  • パラメータpが安全素数でないこと。
  • p-1を共有してしまうこと。

失敗した手計算を共有します。
安全素数が良い理由については、まだ理解していないので書いてません。
理解していない部分を課題の形で置いてあります。

DH鍵交換とは?

DH(Diffie–Hellman)鍵交換は、2人で秘密の値を共有する方法です。
秘密の値は、秘密鍵暗号の鍵として利用されることが多いです。

https(TLS)でも利用できる手法です。
手順のわかりやすさから、RSAに並ぶおなじみの暗号手法です。

DH鍵交換の方法

DH鍵交換の方法をAさんBさんの二人が行う様子で簡単に書きます。

巡回群 {\mathbb Z}/p{\mathbb Z}というのは、pで割った余りの世界を考えるということです。
 {\mathbb Z}/p{\mathbb Z}において元 x次数は、 x^ n = 1 \ ({\rm mod \ } p)を満たす最小の nのことを言います。
 {\mathbb Z}/p{\mathbb Z}において元 x生成元であるとは、次数がpであることを言います。

  • パラメータ (p, g)をAさんとBさんで共有する
  • 整数 aをAさんは p未満の数でランダムに決める
  •  g^ a {\rm \ mod\ }p をAさんはBさんに共有する
  • 整数 bをBさんは p未満の数でランダムに決める
  •  g^ b {\rm \ mod\ } p をBさんはAさんに共有する
  • Aさんは受け取った g^ b a乗して、 K=(g^ b)^ a {\rm \ mod\ } pを得る
  • Bさんは受け取った g^ a b乗する、 K'=(g^ a)^ b {\rm \ mod\ } pを得る

 K = (g^ b)^ a = g^ { a b } = (g^ a)^ b = K'なので、AさんとBさんで同じ値を共有できました。

この通信を見ていたCさんは、 g^ a g^ bを見ることができます。
これ同士を掛けてみても、得られるのは g^ {a + b}です。  g^ {ab}を求めたいのですが、行き詰まってしまいます。

Cさんは、 g^ aから aを求めるのが難しいという、離散対数問題に直面するわけです。

手計算でやってみる

パラメータの決定

とりあえず適当に素数巡回群を決めればいいんだろうと、 p=83とg=2としました。
g=2はDH鍵交換で一般的なパラメータのようです。

2のn乗(mod 83)を求めていくと83乗で初めて1になります。 2は83の巡回群の生成元にちゃんとなっていました。

このp=83とg=2を通信先と共有しました。

 g^ aを求める

僕は乱数を振ってa=46としました。
 g^ a = 2^ {46} \ ({\rm mod\ }p) を計算しましょう。
繰り返し2乗法的なテクニックのおかげで、46乗は手でも簡単に求まります。

初めに 2^ 1, 2^ 2, 2^ 4, 2^ 8, 2^ {16}, 2^ {32}を計算します。
前の数を自乗していけば求まります。
 2^ 1 = 2,\ 2^ 2=4,\ 2^ 4=16,\ 2^ 8=256=7,\ 2^ {16}=49,\ 2^ {32}=2401=77です。

そして、46を二進数に展開して掛けます。
 g^ a = 2^ {46} = 2^ {2 + 4 + 8 + 32} = 2^ 2 * 2^ 4 * 2^ 8 * 2^ {32} = 4 * 16 * 7 * 77 = 51

 g^ aが求まったので通信先に共有します。

 K=(g^ b)^ aを求める

通信先からは g^  b = 82が帰ってきました。
 K=(g^ b)^ a=82^ {46}を求めればDH鍵交換が完了します。

完了するはずでした。

82の46乗を同じテクニックで求めます。
すると、 82^ 2=1になってしまうことに気づきます。
そうなると、前の数を自乗して求めるので、 82^ 4, 82^ 8, 82^ {16}‥‥全部が1 になってしまいます。
つまり、82の偶数乗は1だし、奇数乗は 82^ 1だけになってしまい82です。
今回はa=46で偶数なのでK=1となりました。

通信先もK'=1が求まったようです。
これにて、秘密の値 K=1 を通信先と共有できました。
めでたしめでたし。

本当ですか?

DH鍵交換でp-1を共有したときに起こること

 82^ nはnを変えても、1か82のどちらかにしかならないのは致命的な問題です。
攻撃者Cさんは秘密の値が1か82のどちらかでしかないことが、すぐに分かってしまいます。
どうしてこうなったのでしょう。

実は g^ aの結果がp-1になってしまうと、p-1は2乗すると常に1です。
つまり、次数が2になってしまうのでした。

 (p-1)^ 2 = p^ 2 - 2p + 1  = 1 \ ({\rm mod \ } p)

これは大変です。
実は、p-1を共有しないように乱数でaとbを選ぶ必要があったということです。

課題1: 2が生成元のとき、 2^ {(p-1)/2}=p-1 \ ({\rm mod \ } p)は成り立つ?
そうであれば、 (p-1)/2を乱数を選ぶときに避ければいい。

p-1を共有しなければ大丈夫なのか

もし共有した値の次数が2に限らず、とても小さい次数だと大変です。
総当りで試すのが簡単になってしまいます。

実はp=83の場合、p-1と1以外の次数は41か82なのでした。
p-1を共有しなければ、大丈夫だったようです。
通信先から送られてきた g^ b = 82は、運が悪かったということです。

この、次数が小さくならないための条件が、pが安全素数であるということのようです。
pが安全素数であるとは、ある素数qを用いてp=2q+1と表せる素数のことです。

41が素数なので、83は安全素数です。
そのため、p-1以外の次数が大きかったようです。
pとして83を選べたことは運が良かったようです。

課題2: 安全素数だと1とp-1以外の次数は十分に大きい?

メモ:
CTFにおける離散対数問題に対するアプローチ - sonickun.log

φ(p)が小さい素因数に分かれるとダメということらしい。
安全素数だと、 φ(p)=p-1=2xpなので、都合が良さそううということはわかる。
直感的にはわかった。

応用数学6暗号方式 安永憲司 http://www-infosec.ist.osaka-u.ac.jp/~yasunaga/appmath6/encryption.pdf
で、安全素数である必要性を言及されています。
平方剰余である群が出てくるのですが、あんまり良くわかってません。

ちなみに、opensslで実装されている大きい安全素数pはここにあります。

github.com