A cipher uses an encryption key ``Ke`` and a decryption key ``Kd``.
A symmetric cipher as ``Ke = Kd`` and an asymmetric one has ``Ke != Kd``.
For an asymmetric cipher, there are ``Ciphertext = Encryption(Plaintex, Ke)`` and ``Plaintext = Decryption(Ciphertext, Kd)``. The ``Encryption`` and ``Decryption`` functions might be the same.
## Keys
### Private and Public keys
A typical configuration uses a public (encryption) and a private key (decryption). Anybody can encrypt a message to the owner of the private key, but only the owner can decrypt these messages.
If the private key is used to encrypt, the the messages are public but only the public key distributed by the owner can decrypt them (this is a signature).
### Session keys
For many reason it is useful to have a session key (temporal and unique in order to limit the amount of ciphertext provided to adversaries, shared for symmetric encryption because asymmetric encryption is costly, ...).
A & B want to communicate: A create the session key Ks is encrypted using the public key of B (Kpb) so only B has it. It is vulnerable to replays attack so A adds a timestamp in the message in order to avoid an attacker to send an encrypted message already sent during the transmission.
### Man-in-the-middle
Someone can impersonate someone else and claims to be him, distributing his own public key.
Example of normal communication (U = encryption key)
A -> E(P, Ub) -> B
Example of MIM attack (U = encryption key)
A -> E(P, Uc) -> C -> E(D(E(P, Uc), Ub) -> B
## AES (Advanced Encryption Standard)
### Maths
#### Congurent Modulot
(a, b) are **congurent modulo n** if: ``a mod n = b mod n``
#### Fermat
if p is **a prime number**, then: ``i ^ (p-1) mod p = {0 if i mod p = 0, else 1}``
and if p is **a prime number**, then: : ``i^p mod p = i mod p``
#### Multiplicative inverse modulo n
if ``0 < a < n`` and ``a, n`` relatively prime, then a has a **multiplicative inverse modulo n``
So ``a*u mod n = 1``
Example
a = 3 ; n = 7
a * -2 mod n = 1 (mod 7 = -7 or + 0 or +7 or +14 or ...
-6 mod 7 = 1
Example
a = 5 ; n = 13
a * -5 mod 13 = 1 (mod 13 = -13 or + 0 or +13 or +26 or +39 or ....)
-25 mod 13 = 1
#### Test of primality
To get big prime numbers, we have performant probabilistic algorithms that say: "YES" if it is a prime number or "NO" if it is maybe no a prime number.
#### Relatively Prime
``(a, b)`` are relatively prime if ``gcd(a, b) = 1``
### General approach
Base
C = P^e mod n
P = C^d mod n
(e, n) and (d, n) are the keys to encrypt and decrypt
Decryption undo Encryption
P = (P^e mod n)^d mod n
= P^e^d mod n
= P^(e*d) mod n
If must be hard to determine d given (e, n)
### Half-backed
- Let ``n = p`` a big prime number.
- Choose *e* relatively prime to ``p - 1`` and ``0 < e < p - 1``
- Choose *d* a multiplicative inverse of *e* modulo *p - 1*
So
e * d mod(p - 1) = 1
=> e * d - k * (p - 1) = 1
=> e * d = k * (p - 1) + 1
Example
n = p = 7
(p - 1) = 6
e = 5
5 * d mod(6) = 1 => 5 * d = {1, 7, 13, 19, 25, ...}
d = 5
So
P^(e*d) mod p
= P^(k*(p - 1)+1) mod p ; multiplicative inverse
= P^(k*(p - 1)) * P mod p ; develop the P^(...+1) into P^... * P
= (P^(p - 1) mod p)^k * P mod p ; develop P^(...*k) into P^...^k and add a modulo
= (1^k) * P mod p = P mod p = P ; if 0 < P < p; P mod p != 0; using fermat P^(p-1) mod p = 1
- Decryption undo Encryption
- but it is not computationally secure
### RSA implementation
- Let *p* and *q* big prime numbers
- Let ``n = p * q``
- Let ``X = (p - 1) * (q - 1)``
- Let *e* relatively prime to X
- Choose *d* a multiplicative inverse of *e* modulo *X*:
So
d * e mod X = 1
d * e = k * X + 1 = k * (p - 1) * (q - 1) + 1
Example
p = 3
q = 7
n = 21
X = 12
e = 5
5 * d mod 12 = 1
5 * d = 12*k + 1 = {1, 13, 25, 37, 49, 61, 73, 85, ...}
5 * 17 = 85
d = 17
So with ``P != 0``
P^(e*d) mod p
= P^(k*(p - 1)*(q - 1) + 1) mod p ; multiplicative inverse e * d
= (P^(p-1))^(k*(q-1)) * P mod p ; develop P^(... * (p-1)) = (P^(p-1))^...
= 1^(k*(q-1) * P mod p ; if 0 < P; P mod p != 0; using fermat P^(p-1) mod p = 1
= 1 * P mod p = P mod p
The same goes for q.
Furthermore
P^a mod p = P mod p implies P^a - P mod p = P - P mod p = 0
so ``P^a - P`` is a multiple of *p*. The same goes for *q*.
And ``(p, q)`` are distinct and prime numbers. So ``P^a - P`` is the multiple of their product ``p*q = n``
So
P^a mod n = P mod n = P
- Decryption undo Encryption
- ``X = (p - 1) * (q - 1)`` from n requires to find p and q, which is very difficult (factorization)
- Difficult to find e from (d, n) and d from (e, n)
#### Improve security
- don't share n
- padding / salting
- constant time encryption / decryption
- big keys (e >= 65537, n should be at least 3072 bits, d >= sqrt(n))