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

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 Soau 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))