summary of asymmetric cryptography

asymmetric-cryptography.md

Over Simplfied Asymmetric Cryptography

Group

Definitions:

• Operator: +

• Unit: 0

Scalar multiplication

P = kG = G + G + ... + G

Double and add algorithm: P = kG = (0|1) * G * (2^k) + (0|1) * G * (2^(k-1)) ...

Discrete logarithm problem: it's really hard to calculate k with only P and G with some groups.

• Instance 1: integer multiplication over finite field

  • P = (G ^ k) mod N

• Instance 2: Elliptic curve over finite field

When used in asymmetric cryptography, k is the private key, P is the public key, G is a constant.

Hellman-Diffie key exchange

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

• A generates random integer a
• B generates random integer b.
• A send aG to B
• B sends bG to A
• A calculates the shared secret r = a(bG)
• B calculates the shared secret r = b(aG)

Public key encryption

https://en.wikipedia.org/wiki/ElGamal_encryption

Definitions:

• P: recipeient's public key
• k: recipeient's private key
• G: the base point in the group

Steps to encrypt :

• Choose random integer r
• Encrypt: cipher = plain + rP (map the plain text to the points on group)
• send (rG, cipher)

Steps to decrypt:

• Calculate rP = r(kG) = k(rG)
• Decrypt: plain = cipher - rP

Digital Signature Algorithm

https://en.wikipedia.org/wiki/ElGamal_signature_scheme

https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

Not so generic over the two groups.

Schnorr signature

https://en.wikipedia.org/wiki/Schnorr_signature

Signer's keypair: P = kG

Steps to sign:

• Choose random number r
• R = rG
• e = H(R || M)
• s = r - k * e
• publish (e, s)

Steps to verify:

• Recover r by compute: sG + eP = (r - ke)G + e(kG) = r
• Compute e' by compute: H(rG || M)
• Check e' == e