[Crypto, Python] Diffie-Hellman (迪菲-赫爾曼) 演算法

以前大四修過資訊安全的課, 不知道哪根經不對, 還特別做了網站紀錄, 現在由高醫陳以德老師接收管理(他上的課嘛XD)

我古老的Crypto講義: http://itchen.class.kmu.edu.tw/Crypto/Web/

廢話說完, 最近我又稍微在看以前的一些加密演算法, 其中正在看Diffie-Hellman key exchange, 順道紀錄整個過程

中文Wiki實在翻譯的不太看得懂阿.....建議要看的要看英文

Wiki: http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

其實DH已經是RFC標準了, RFC 2631: http://tools.ietf.org/html/rfc2631

而且網路上居然還有影片特別介紹這演算法!! (主題在2:40秒之後), 相當清楚

Video: http://www.youtube.com/watch?v=YEBfamv-_do


其實有一個相當完整的英文教學甚至還有python實作

我基本上是從這邊跟上述影片學的(密碼學的課本我已經不知道丟去哪了....)

Reference Website: http://blog.markloiseau.com/2013/01/diffie-hellman-tutorial-in-python/

這邊簡短解釋一下, DH是做Key exchange, 這用途是, 通常我們會加密一些檔案資料

然後傳送給別人, 別人跟你要密碼之後, 再解開檔案, 但是這有問題, 要是你給別人密碼

中間有人偷聽,　密碼就被偷走啦!!, 所以DH這招, 就是教你怎麼"安全的"跟別人講你密碼!!

其實我有稍微查網路上其他大部分的教學, 有趣的是所有教學都喜歡用Alice & Bob, 還有一個偷聽的壞人Eve !!

(Alice跟Bob當然是因為A, B的關係, 而會簡稱Eve 我猜來由是eavesdropper - 竊聽者)

首先這方法是利用質數來達成的Key exchange, 以及配合Public Key跟Private Key

Public Key就是可以公開跟所有人說的, Private Key只能自己知道

再來是有一個公式來計算出要如何加密傳送給對方的內容, 這公式牽扯到了Discrete Logarithm(離散對數)

公式:

聽起來好像很玄, 看起來很厲害, 但其實很簡單, g, x, b, p都是實數

g稱呼為generator, p為prime, 這兩個會是Alice跟Bob兩邊先說好的機制

x則是Alice會有一個, Bob會有一個, 兩個並不一樣的私鑰

以下來舉例(影片中的例子),  假設g我選3, x為29, p選17, 你會得到b = 12

如果今天Eve拿到12這個數字, 他有辦法回推出私鑰29嗎? 或許29太小有可能

但是如果今天是大到不行的數字, 就相當困難了吧!!

PS1: 其實有演算法提出如何破解( Shor's Algorithm )

PS2: 但是可破解要素的量子電腦尚未正式發明...

下列就是開始應用的展開

1. 由於已經先定好基本公式的參數了

剩下的就是Alice跟Bob都要先自己選一把私鑰, 假定Alice選15, Bob選13, 那在Alice這邊用DL公式結果就是

而Alice將6傳出去給Bob, 假設Eve可以看到傳出來的東西, Eve也收到了6, Bob這時候也用DL公式, 結果

而Bob將12傳出去給Alice, Eve也看到了12

接下來就是見證奇蹟的時刻, 前面有先講好的a, 這時候換掉它

換成收到的public key, 再做一次DL公式, 奇蹟就會發生了!!!

Alice這時候只要再將收到的public key(g)跟自己的private key(x), 帶入DL公式, 她將會得到訊息10

而Bob這時候只要再將收到的public key(a)跟自己的private key(x), 帶入DL公式, 他也會得到訊息10

有發現了嗎, 兩邊都是一樣的結果

再往python下去之前, 講個簡單應用範例

假如我今天有兩台機器(M1, M2), 我要互相溝通並且要作DH加密

可行的流程

首先M1先產生出generator - g跟prime - p, 並且自行設計private key - x, 然後透過DL公式, 產生出public key - A

將A, g, p傳送給要溝通的第二台機器M2, M2收到A, g, p之後, 利用g跟p產生出public key - B

然後將B回傳給M1

接下來M1收到B之後, 就可以用B, g, p產生出一組secret key

通常故事到這邊就結束了,　然後就會有問題說, 再來勒??

我文章開其有解釋, 其實DH只是教你做安全的key exchange, 當手上拿到這把鑰匙的時候

接下來就是要做密碼學的加密,  簡單的例如XOR Encrypt, 複雜的如AES

感覺上就好像M1先把secret key + content做加密, 然後傳送到M2之後

M2用secret key對收到的結果再解密, 就可以看到content了, 這步驟說起來簡單, 其實還是有使用上的限定就是了

接下來用Python示範, 首先是這個DL公式, 本來應該是要輸入的方式是

(g**x) % p

但是python有內建!! 不用這麼麻煩而且還最佳化速度過

pow(g, x, p)

相當的好用阿!!

再來是要自訂一個private key, 最好是大一點的數字

那英文網頁範例是用python的ramdom裡面的getrandbits來generate

getrandbits是python的一個random裡的函數, 透過Mersenne twister演算法

會產生出一個隨機的數字, getrandbits(32)就是會產生一個32bit的隨機數

這邊我用32bit, print p我選: 62603, generator g設定13

p = 62603
g = 13

Alice做出public kety

a = getrandbits(32)
A = pow(g, a, p)

Bob做出public kety

b = getrandbits(32)
B = pow(g, b, p)

這樣Alice要給Bob她的A key, Bob要給Alice他的B key

Alice帶入DL公式

secret = pow(B a, p)

Bob帶入DL公式

secret = pow(A, b, p)

兩個secret應該是一樣的, 以上是簡易應用

Mersenne Twister wiki: http://en.wikipedia.org/wiki/Mersenne_twister