Ch03_Public_Key_Cryptography_and_RSA

Diffie-Hellman 密钥交换算法

• 仅限于密钥交换
• all users agree on global parameters:
  • large prime integer or polynomial q
  • g being a primitive root mod q (本原根,g及g的幂次%p可以生成0-p-1,即所有余数)
• each user (eg. A) generates their key
  • chooses a secret key (number): xA < q
  • compute their public key: yA = g^{xA} mod q
• each user makes public that key yA

• KAB = g^{xA*xB} mod q

  = yA^{xB} mod q (which B can compute)

  = yB^{xA} mod q (which A can compute)

  中间人攻击

  

RSA

Rivest,Shamir,Adleman

A Method for obtaining Digital signatures and Public-key Cryptosystem

Process

1. By Rivest, Shamir, and Adleman (MIT)
2. RSA is the gold standard in public key crypto
3. Let p and q be two large prime numbers
4. Let N = pq be the modulus
5. Choose e relatively prime to (p-1)(q-1)
6. Find d such that ed = 1 mod (p-1)(q-1)
7. Public key is (N,e)
8. Private key is d
9. To encrypt M we compute
10. C = M^e mod N
11. To decrypt ciphertext C compute
12. M = C^d mod N