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.
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)
https://en.wikipedia.org/wiki/ElGamal_encryption
Definitions:
P
: recipeient's public keyk
: recipeient's private keyG
: 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
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.
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