Diffie Hellman 參數檢查

在玩openssl的dh相關指令時，順手把之前玩過的snmpv3用的dh key拿來跑跑看
那把key的參數是

p=FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
  29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
  EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
  E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
  EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
  FFFFFFFF FFFFFFFF"

g=2

先把它轉成der格式

package require asn
package require math::bignum

set p "
FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
FFFFFFFF FFFFFFFF"

set p  [::math::bignum::fromstr 0x[string tolower [join [split $p " \n"] ""]]]

set key ""
append key [::asn::asnBigInteger $p]
append key [asn::asnInteger 2]
set key [::asn::asnSequence $key]

set fd [open dh_der w]
fconfigure $fd -translation binary
puts -nonewline $fd $key

再丟給openssl去跑一下，檢查順便轉檔

the g value is not a generator !!
於是爬了一下source code
在openssl\crypto\dh\dh_check.c裡
int DH_check(const DH *dh, int *ret)
當g=2時，檢查 p mod 24 == 11
在openssl\crypto\dh\dh_gen.c的註解裡有更詳細的挑選方法說明

敗了一下google大神
整理以下心得

1.generator

意思是 g^n mod p 可以產生出 1~(p-1)的結果，而snmpv3用的這一組數字在g^((p-1)/2) mod p 就是 1 了，只能生成一半的數字
雖然DH演算法不一定要g是個generator，不過openssl實作時會挑generator

2.safe prime
若 \(p\) 是質數，\(p=2q+1\)，\(q\) 也是質數，\(p\) 就是 safe prime

3. generator 驗證方法

當 \(p\) 選擇為 save prime 時可以用以下方法驗證 \(g\) 是否為 generator (*1)

\(g^2 \mod p \neq 1\)
\(g^{(p-1)/2} \mod p \neq 1\)

若符合兩式 \(q\) 就是 generator


當\(g=2\)時，可以用以下方法驗證 (*2)

\(p \mod 24 == 11,q\) 是 generator
\(p \mod 24 == 23,q\) 不是 generator

4.是否為 generator 的比較

generator : 可以生成所有的值，但可以輕易知道private key的 1 個 bit(LSB)，openssl 用這種方式 (*3)
非generator : 只能生成一半的值，無法輕易知道private key的任何bit,snmpv3 選的是這一種


(*1)
\(p=2q+1\)，\(p,q\)為質數
\(g^{(p-1)} \equiv 1 \pmod p\)
\(g^{2q} \equiv 1 \pmod p\)
\(g^2 g^q \equiv 1 \pmod p\)
這時只要檢查
\(g^2 \mod p \neq 1\)
\(g^q \mod p \neq 1\)
即可

證明:
假設存在 \(x ,1 < x < 2q\)
\(g^x \equiv g^{2q} \equiv 1 \pmod p\)
則 \(2q\) 可以寫成 \(k_1 x + r_1\),(這邊及以下的值符合正整數除法規則)
\(g^x \equiv g^{k_1x+r_1} \equiv g^{r_1} \equiv 1 \pmod p\)
則 \(x\) 可以寫成 \(k_2 r_1 + r_2\)
\(g^{k_2 r_1 + r_2} \equiv g^{r_2} \equiv g^{r_1} \equiv 1 \pmod p\)
重複這個步驟(輾轉相除法)，最後會得到\(\gcd (x,2q)\)
\(g^{\gcd (x,2q)} \equiv 1 \pmod p\)
因為\(2,q\)都是質數
若\(x \neq 2, x \neq q \Rightarrow \gcd (x,2q)=1\)
\(g \equiv 1 \pmod p\)
\(g=1\)，我們不會選1來當key
所以\(x=2\) 或 \(x=q\) \(\gcd (x,2q) = 2 \text{或} q \)
所以只要檢查\(g^2 , g^q\)即可

(*2) RFC4419 section-6.1有提到這個檢查方法


(*3)
Diffie-Hellman Parameter Check (when g = 2, must p mod 24 == 11?)
當 \(g\) 是 generator 可求出 private key (x) 的 LSB

public key (C) 就是
\(C=g^x \mod p\)
透過以下計算
\(C^{(p-1)/2} \mod p\)
\(\Rightarrow g^{x (p-1)/2} \mod p\)
就能分辨出\(x\) 為奇數或偶數，相當於得知LSB

令\(x=2n+r\)
\(g^{x(p-1)/2}\)
\(= g^{(2n+r)(p-1)/2}\)
\(= g^{(2n+r)(p-1)/2}\)
\(= g^{n(p-1)}g^{r(p-1)/2}\)
則源式可寫成
\(g^{n(p-1)}g^{r(p-1)/2} \mod p\)
因為 \(p\) 是質數
\(= g^{(p-1)} \equiv 1\pmod p\)
所以可以化簡成
\(g^{r(p-1)/2} \mod p\)

\(r=0\)時，結果為\(1\)
\(r=1,\)時，
\(g^{(p-1)/2} \mod p \neq 1\)
因為 \(g\) 是 generator

透過這個運算，就能輕易得知 private key 的 1 個 bit