Public-key cryptography

Public-key cryptography makes use of two keys - a public key which can be shared freely and a private key which only its owner should have access to. The private key can be used to encrypt and decrypt messages, but the public key can only be used to encrypt.

Modular arithmetic

Public-key cryptography makes uses of the properties of modular arithmetic to encrypt and decrypt data using two keys.

There are several rules for working with modular arithmetic: $$ \begin{aligned} (A + B) \mathop{\mathrm{mod}}n &\equiv ((A \mathop{\mathrm{mod}}n)+B) \mathop{\mathrm{mod}}n\\ (A+B) \mathop{\mathrm{mod}}n &\equiv ((A \mathop{\mathrm{mod}}n)+(B \mathop{\mathrm{mod}}n)) \mathop{\mathrm{mod}}n\\ (A \times B) \mathop{\mathrm{mod}}n &\equiv ((A \mathop{\mathrm{mod}}n) \times B) \mathop{\mathrm{mod}}n\\ (A \times B) \mathop{\mathrm{mod}}n &\equiv ((A \mathop{\mathrm{mod}}n) \times (B \mathop{\mathrm{mod}}n)) \mathop{\mathrm{mod}}n\\ x^{A \times B} \mathop{\mathrm{mod}}n &\equiv (x^A \mathop{\mathrm{mod}}n)^B \mathop{\mathrm{mod}}n\\ (x^A \mathop{\mathrm{mod}}n)^B \mathop{\mathrm{mod}}n &\equiv (x^B \mathop{\mathrm{mod}}n)^A \mathop{\mathrm{mod}}n \end{aligned} $$

Primitive roots

$y$ is the primitive root mod $p$ every successive power of $y$ mod $p$ is congruent to a value in the range $[1,p-1]$ and the values are uniformly distributed.

For example, 3 is a primitive root mod 7 but 3 is not a primitive root mod 11.

3 mod 7 $$ \begin{aligned} 3^0 &\stackrel{7}{\equiv} 1\\ 3^1 &\stackrel{7}{\equiv} 3\\ 3^2 &\stackrel{7}{\equiv} 2\\ 3^3 &\stackrel{7}{\equiv} 6\\ 3^4 &\stackrel{7}{\equiv} 4\\ 3^5 &\stackrel{7}{\equiv} 5\\ 3^6 &\stackrel{7}{\equiv} 1\\ 3^7 &\stackrel{7}{\equiv} 3\\ 3^8 &\stackrel{7}{\equiv} 2 \end{aligned} $$

3 mod 11 $$ \begin{aligned} 3^0 &\stackrel{11}{\equiv} 1\\ 3^1 &\stackrel{11}{\equiv} 3\\ 3^2 &\stackrel{11}{\equiv} 9\\ 3^3 &\stackrel{11}{\equiv} 5\\ 3^4 &\stackrel{11}{\equiv} 4\\ 3^5 &\stackrel{11}{\equiv} 1\\ 3^6 &\stackrel{11}{\equiv} 3\\ 3^7 &\stackrel{11}{\equiv} 9\\ 3^8 &\stackrel{11}{\equiv} 5 \end{aligned} $$

For 3 mod 7, the values start repeating at $3^6$ and all values from 1 to 6 are generated uniformly so 3 is a primitive root mod 7. For 3 mod 11, the values start repeating at $3^5$ but not all values are generated so 3 is not a primitive root mod 11.

When using a primitive root, there is an equal chance that a given power maps to a number from 1 to $p-1$. This makes it harder to reverse.

RSA

The RSA public key encryption scheme uses the modular arithmetic and primitive roots. Key generations starts with generating two large prime numbers, $p$ and $q$ and the public key is their product, $n = pq$. RSA also uses another value, $e$, which is relatively prime to $p-1$, $q-1$ and $(p-1)(q-1)$ and between 1 and $(p-1)(q-1)$. For $p=17$ and $q=11$ a possible value of $e$ is 7, as neither 16, 10 or 160 are divisible by 7 and it is between 1 and 160.

Encryption uses the following formula:

$$ c = m^e \mathop{\mathrm{mod}}n $$ where $c$ is the ciphertext and $m$ is the message. This is a one-way function and it is intractable to calculate $m$ given $c$, $e$ and $n$.

The private key, $d$ is a number such that

$$ ed \equiv 1 \mathop{\mathrm{mod}}(p-1)(q-1) $$ Using the example from before with $p=17$, $q=11$, $n=187$ and $e=7$ a possible value of $d$ is 23 as $7 \times 23 \equiv 1 \mathop{\mathrm{mod}}160$.

The private key can then be used to decrypt the ciphertext using

$$ m = c^d \mathop{\mathrm{mod}}n $$ This encryption relies on the fact it's computationally intractable to factorise $n$ or reverse the one way function. The time taken increases with the length of the key and RSA uses 1024, 2048 or 4096 bit public keys, so it is computationally unbreakable at this time.

It is also possible to encrypt a message with the private key and decrypt it with the public key. This is due to a property of modular arithmetic and can be used for digital signatures.

Digital signatures

Digital signatures make use of public key cryptography to sign a message. If the contents of a message are not sensitive then encrypting and decrypting the whole message is unnecessarily slow. Instead, the sender can encrypt the hash of their message with their private key and append the encrypted hash to their message. Anyone with their public key can then decrypt the hash and compare to the hash of the message they received which is much quicker.

Digital signatures provide 3 main features.

• Integrity - Check the contents of the message have not been modified

• Authentication - It is possible to show you sent the message

• Non-repudiation - It is not possible to deny you sent the message

All of these rely on the fact your private key is only accessible to you.

Digital certificates

A digital certificate is some proof that a public key belongs to someone.

Certificate authorities

A certificate authority (CA) is a trusted 3rd party who issues digital certificates. A root certificate is one a CA issues to itself. The certificate consists of the subject and their public key and is signed by the CA with their private key. To verify a certificate the user needs to have the CA root certificates installed. They can then use this to verify the signature on the certificate.

Web of trust

Web of trust is a decentralised method of verifying public keys. Each user creates their own certificate which is signed by other users who trust them. There are two attributes considered when signing another users key, trust and validity. If A is certain B's public key belongs to B then they set validity to full, otherwise they use marginal or unknown. If A is confident B will be careful when signing others' keys then they can set the trust to full, marginal or otherwise unknown.

Users can then decide whether they trust another users public key based on the chain of trust from them to the other user. Usually when the chain of trust gets long the level of validity and trust decreases unless ultimate trust is given.