1.1 Authentication

Previous post in this series is here.

Okay, time to dive into this in more technical depth. Let's go phase by phase:

1.1 Authentication

Authentication, or proving you are who you say you are, is often described as something you have (a physical key), something.you know (a secret password), or something you are (biometrics, or physically unclonable functions, or PUFs).

The authentication phase can be accomplished using a pre-shared secret key and symmetric encryption of some message and response, or it can be done via asymmetric, public-key cryptography.

The best-known and most-used form of public key crypto is RSA, developed by Rivest, Shamir and Adelman (but also previously discovered by Cocks, of a British intelligence agency):

1. Pick two large primes, $p$ and $q$, let $n = pq$.
2. Calculate $\phi(p,q) = (p-1)(q-1)$.
3. Pick $e$, prime relative to $\phi(p,q)$.
4. Calculate $d$, s.t. $de = 1 \bmod \phi(p,q)$, which we can call the inverse of $e$ modulo $\phi(p,q)$.

The tuple $\langle n,e\rangle$ is now your public key, and $d$ is your private key. You can publish $\langle n,e\rangle$ any way you like, including in the New York Times. To send you a message $m$, I calculate the ciphertext $c$,

$c = m^e \bmod n$

and send $c$ to you.  You can recover the message $m$ by

    $m = c^d \bmod n$

That's all there is to it!  Except that it's expensive, so we don't use it for every message.  If I send you "Hi, Bob, it's Tuesday, let's use 42 as our key," using your public key and you reply, "Tuesday is beautiful, Alice, and 42 is fine," using my public key, we confirm that we are definitely Bob and Alice, known as authentication -- assuming, of course, that you trust that the key that you are holding really and truly belongs to me, and I haven't leaked it out somehow!

As you might guess from the publication of $n$, RSA is the one that's vulnerable to factoring larger integers, and hence of interest to spooks once Shor's algorithm came about.

Current EU recommendations are for 3072-bit RSA keys, recently (2018) upgraded from 2048, for "near-term protection" (up to ten years). They recommend an extraordinary 15360 bits for "long-term protection" (thirty to fifty years). [Cloudflare, Keylength.com, Ecrypt, Lenstra]

(Note: there are many more references to come; they will be delivered in a batch at the end.  It's not practical to list them all here in every article as we go, but I'll try to give you some of the key(ha!) ones.)