Guide to Elliptic Curve Cryptography - 2005/11/28

Public-key cryptography 常用的方法：

1. Integer Factorization Problem (ex：RSA)
   
2. Discrete Logarithm Problem (ex：ElGamal、DSA)
   
3. Elliptic Curve Discrete Logarithm Problem
   

RSA：(在這本書上寫 "It has been proven that the problem of determining the private key d from the public key (n,e) is computatuinally equivalent to the problem of determining the factors p and q of n; the latter is the integer factorization problem (IFP)"，但並沒有引用文獻，需要再去查)

• Key 的產生：輸入 Security parameter l，輸出 public key (n,e) 與 private key d。
1. 先隨機選擇兩個質數 p 與 q，其 bitlength 為 l/2。
2. 計算 n = pq 與 Φ = (p-1)(q-1)。
3. 隨機選擇 e 使得 e 與 Φ 互質。
4. 利用輾轉相除法找到 d，使得 ed ≡ 1 (mod Φ)。
5. 技巧：m^ed ≡ m (mod n)。