Encryption with ECDH (Diffie–Hellman key exchange)－好人勿用™

Diffie–Hellman key exchange (aka DH)

一種安全協定, 讓雙方在完全沒有對方任何預先信息的條件下,
於不安全通信通道中建立起一個共享金鑰(Shared Secret)的金鑰交換(Key Exchange)方法!!!

Patent for ECC @ Cryptographic apparatus and method @ US 4200770 A

This is known as the Diffie-Hellman problem

Given three points P, aP and bP, what is the result of abP?

or
Given three integers k, k^x and k^y, what is the result of k^xy?

The principle behind the Diffie-Hellman problem @ 02m37s

Let's Practices @ ECDH

1.) 首先,志明與春嬌選擇一組相同參數的橢圓曲線,其中包括{質數p,a,b},
    此橢圓曲線也必需滿足y² = x³ + ax + b (mod p)
2.) 在橢圓曲線上, 志明與春嬌都選擇一個小於p且公共點P(x,y) as Public Key
3.) 志明任選擇一小於p的亂數d_志明,接著計算d_志明乘以公共點P(x,y), 得到一點Q_志明(x,y) = d_志明*P(x,y)
    志明私鑰 = {d_志明} ; 志明公鑰 = {Q_志明(x,y)}
4.) 志明將公鑰Q_志明傳送給春嬌
5.) 春嬌任選擇一小於p的亂數d_春嬌,接著計算d_春嬌乘以公共點P(x,y), 得到一點Q_春嬌(x,y) = d_春嬌*P(x,y)
    春嬌私鑰 = {d_春嬌} ; 春嬌公鑰 = {Q_春嬌(x,y)}
6.) 春嬌將公鑰Q_春嬌傳送給志明
7.) 志明可利用春嬌傳送過來的公鑰Q_春嬌來計算出共享金鑰S_{志明與春嬌} = d_志明*Q_春嬌
8.) 春嬌可利用志明傳送過來的公鑰Q_志明來計算出共享金鑰S_{志明與春嬌} = d_春嬌*Q_志明
9.) 最後, 現在志明與春嬌都會擁有對方的公鑰與共享一把相同的共享金鑰S_{志明與春嬌}
     (S_{志明與春嬌} = d_志明*Q_春嬌 = d_春嬌*Q_志明) as Shared Secret!!!

共享金鑰(Shared Secret) @ Setp5 by DH

1.) 志明與春嬌產生自己所擁有的私鑰(Private Key)與公鑰(Public Key) by {Public;Private}

{d_志明=203;Q_志明(130,203)} & _{d_春嬌=121;Q_春嬌(115,48)}

2.) 志明與春嬌於一個"不安全的通信通道中"互相交換的自己所擁有的公鑰

Q_志明 to 春嬌 & Q_春嬌 to 志明

3.) 志明計算S_志明= d_志明*Q_春嬌 & 春嬌計算S_春嬌= d_春嬌*Q_志明

          S_{志明與春嬌}= S = d_志明*Q_春嬌 = d_春嬌*Q_志明

而... S稱之為共享金鑰(Shared Secret)!!!

The Diffie-Hellman key exchange:

    志明與春嬌可以"很簡單"計算出S
    而康寶必須解出"極度難"的問題當只有{Q_志明;Q_春嬌}!!!

1.) 志明將 {E_p(a,b), P_公共點 , Q_志明}傳送給春嬌 @ {規則,最初點,最終點}

2.) Encryption with ECDH

     a.) 春嬌將明文編碼到E_p(a,b)曲線上的一點(C1,C2), 並且產生一個亂數r (r<q) (q as order)
     b.) 春嬌計算C1 = r*P_公共點 ;C2 = M+r*Q_志明
     c.) 春嬌將(C1, C2)傳給志明