# Cryptography: Asymetric ciphers and key rings

## RSA Cipher: how to generate keys, encrypt and decrypt

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
``````

### 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```au 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