public key cryptography

RSA cryptography¶

this paradigm of public / private keys is at the heart of modern cryptography
and is used all over the place, from SSH to TLS, and many more

in this notebook, we will focus on the RSA algorithm, knowing that it is just one of many
that is widely used for secure data transmission (RSA name comes from the initials of its inventors:
Rivest, Shamir, and Adleman, who introduced it in 1977)

the invariant in all these algorithms is that they rely on the mathematical properties of finite groups, so what we’re going to learn about RSA has some features in common with other public-key algorithms, such as e.g. elliptic curves cryptography (ECC)

finite groups¶

• a finite group is a set of elements with a binary operation that satisfies four properties:

  • closure: the result of the operation on two elements in the set is also in the set
    $\forall a, b \in G, a * b \in G$

  • associativity: the operation is associative (a+b)+c = a+(b+c)
    $\forall a, b, c \in G, (a * b) * c = a * (b * c)$

  • identity element: there exists an element in the set that acts as an identity for the operation
    $\exist e \in G, \forall a \in G, e * a = a * e = a$

  • invertibility : for every element in the set, there exists an inverse element such that the operation on them yields the identity element
    $\forall a \in G, \exist b \in G, a * b = b * a = e$

somes examples¶

• consider the set of integers modulo 5, denoted as $\mathbb{Z}/5\mathbb{Z}$

  • the elements are {0, 1, 2, 3, 4}

  • the operation is addition modulo 5

  • this set satisfies the properties of a finite group

• as we will see below, the same holds for multiplication modulo $n$ (denoted $\mathbb{Z}_n^*$)

  • except we need to restrict ourselves to the integers that are coprime to $n$

• the set of permutations on a finite set of cardinal $n$

  • together with the composition of functions as the operator

  • is also a finite group, denoted as $S_n$,

  • which is not commutative (i.e. $a*b ≠ b*a$ in general)

multiplicative group $\mathbb{Z}_n^*$¶

now we are looking at the multiplicative group of integers modulo n
two cases arise, let’s start with the simplest case

if n is prime¶

• we can take all the integers $i \in \{1, .., n-1\}$, with multiplication modulo n

• in that case indeed, all these numbers $1 <= i <= n-1$ are coprime to n

• and so after Bézout, $\exists (a, b) \in \mathbb{Z}^2$, such that $a.i + b.n = 1$

• in other words, $a.i ≡ 1 (n)$

• which establishes invertibility: a is the inverse of i

• the other 2 properties are easy to verify

if n is not prime¶

we can make the same construction, still with multiplication modulo $n$ ...
except that we consider only the set of all the integers from 1 to $n-1$ that are coprime to $n$

• the same Bézout argument proves that multiplication is invertible in this structure

• the other 2 properties are easy to verify

• what is a little less trivial is that the operation is stable in this set, but:

  • assume $a$ and $b$ are coprime to $n$

  • then their product is also coprime to $n$

  • and so this subset is stable under multiplication modulo $n$

this is what is called the multiplicative group of integers modulo n - denoted $\mathbb{Z}_n^*$
let’s now see how to compute the order (the number of elements) of this group...

the order of $\mathbb{Z}_n^*$¶

in the general case¶

the number of elements in this group (also called the order of this group)
is given by Euler’s totient function $φ(n)$,
which, as we have just seen, amounts to the number of integers up to n that are coprime to n

if $n = p_1^{e_1} . p_2^{e_2} . ... . p_k^{e_k}$ where $p_1$, $p_2$, ..., $p_k$ are distinct prime factors of $n$, then:

$φ(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) ... (1 - \frac{1}{p_k})$

the RSA construction¶

to build an RSA keypair:

• we pick too large primes $p$ and $q$, and state $n = p*q$

• we do all the computations within $\mathbb{Z}_n^*$, the multiplicative group of integers modulo $n$

• which, as we just saw, has order $φ(n) = (p-1)(q-1)$

Lagrange’s theorem¶

in any finite group $G$ of order $n$, the following statements hold:

1. the set of all the powers of a given element g
   $C_g = \{ g^k | k \in \mathbb{Z} \}$ is a subgroup of $G$
   it is called the cyclic subgroup generated by g
   and by definition the order of $g$ is the order of that subgroup

2. the order of any subgroup of $G$ divides the order of $G$ (Lagrange’s theorem)

Putting these two together, we can easily demonstrate that
$∀g∈G, g^n = 1$
where 1 is the identity element of the group (the usual notation for a multiplicative group)

RSA (finally!)¶

So let’s go back to our RSA construction

• we pick 2 large primes $p$ and $q$, and state $n = p*q$

• we consider $G$ the multiplicative group of integers modulo $n$

• it has order $φ(n) = (p-1)*(q-1)$

• and because it is a group: any element in $G$, let’s call it $u$ for public, has an inverse - that we call $v$ for private

• because they are inverse of one another, we have $u.v = 1 (n)$

• which means that
  $∀m∈G, (m^u)^v = m^{(u.v)} = m^1 = m (n)$

Now, this means that:

• $n$ is known to all parties: the public key is $(n, u)$ and the private key is $(n, v)$

• any message (provided it is in the group) can be encrypted with the public key,
  and decrypted with the private key - or the other way around - by a simple exponentiation (mod $n$)

  • encrypted: $c = m^u (n)$

  • decrypted: $m = c^v (n)$

RSA in practice¶

key sizes¶

• for the whole thing to be of any practical use, it must be hard to find the private key v from the public key (n, u)
  we will admit that it is the case, and that it’s hard to factor n into its prime factors p and q

• as an indication, a key size of 2048 bits means n has 2048 bits, so it is in the order of about 617 decimal digits
  this size is considered secure for the next 10 years or so - except if quantum computers was to become a reality

• as a side note, of course all this crucially calls for fast exponentiation

message sizes¶

• also a concrete message may of course be larger than the modulus n

• so its first needs to be encoded as a collection of integers, each smaller than n

all in all this encoding scheme is non trivial and rather compute-intensive
so it’s generally used once at the beginning of a session (SSH, TLS, etc..),
and used to agree on lightweight symmetric keys for the rest of the session

other schemes¶

the interested reader can check a construction called Ellipctic Curve Cryptography (ECC) that allows to build a similar public/private key pair;

you can easily create such a key using ssh-keygen with the -t ecdsa option

SSH¶

• the basics:

  • ssh (secure shell) is a protocol for secure remote login over an insecure network

  • it uses public key cryptography

  • its primary use is to let you connect to a remote server once it has been provisioned in the cloud

• other uses:

  • you have used it many times when interacting with github

  • it can also be used to create tunnels (like a network pipe) to cross firewalls

  • you can use it with vs-code to edit files on a remote server

• configuration:

  • ~/.ssh/id_rsa: the private key (do not show it to anyone)

  • ~/.ssh/id_rsa.pub: the public key (this is the one you share)

  • ~/.ssh/config: allows to define shortcuts and predefined options per host

  • ~/.ssh/known_hosts: a list of known hosts and their public keys

🔑 Public Key Infrastructure (PKI)¶

• each browser and OS comes with a list of trusted CAs

  • CA = Certificate Authority

  • in practical terms, their public key

  • e.g. Verisign, Let’s Encrypt, etc..

• a certificate is a chain of trust

  • signed by a CA

  • which in turn is signed by another CA

  • and so on until we reach a self-signed root CA

  • which should be trusted by the browser

• like always, signing is based on a public/private key pair

  • the CA signs the certificate with its private key

  • and the browser verifies it with the CA’s public key