Cryptographie à clé publique

Vignette écrite par Graeme L. Cohen (University of Technology, Sydney), Steven Galbraith (University of Auckland) et Edoardo Persichetti (University of Auckland).
How can we safely send our credit card details over the internet, or using a mobile phone, when others can intercept our messages? How can we trust software updates, when we know that computer viruses are common? Cryptography (the study of techniques for secure communication in the presence of adversaries) provides answers to these questions, and mathematics provides its foundations.

A little history

Secure communication has been important for thousands of years: there is evidence of Julius Caesar using a simple cryptographic method to communicate with his generals. The scheme is known as the “Caesar cipher” and it consists of shifting the letters in a message by a certain number of positions to obtain a new document called the ciphertext. The message can be recovered at the other end by inverting this operation, i.e. shifting back the letters of the received ciphertext by the same number of positions.

The crucial idea is that the sender and receiver both know a secret value (in this case, the number of positions) that is assumed to be unknown to the people trying to learn the message. The secret value is called the key. In the case of the Caesar cipher the key $K$ is a number between $0$ and $26$ . The encryption algorithm ${\textsf{Enc}}$ takes as input a message $M$ and a key $K$ , for example ${\textsf{Enc}}_3$ (HELLO)=KHOOR. The ${\textsf{Dec}}$ algorithm takes as input a ciphertext $C$ and the same key $K$ , for example ${\textsf{Dec}}_3$ (KHOOR)=HELLO.

Cryptosystems where the same key is used for encrypting and decrypting are called symmetric-key schemes.

The Caesar cipher itself is much too simple to be secure in the modern world, but there are modern symmetric-key ciphers that are currently used in many situations; an example is the very famous AES, one of the US government standards for transmitting data. These systems are efficient and secure, but there is one problem: both sender and receiver must already share a secret. How can we communicate securely over the internet with people we have never met?

An amazing concept called public-key cryptography, initiated in 1976 in the paper “New directions in cryptography” by Whitfield Diffie and Martin Hellman, solves this problem.
In this setting, instead of using the same key for encrypting and decrypting, there is a public key, available to all potential users, and a private key that remains secret to a specific user. In other words, everybody can send a message but only one person can receive it: Anyone can drop a letter in the posting slot, but only the person who has the key of the mailbox can get the letter. To communicate securely with Alice one looks up their public key and uses it to generate a ciphertext. Only Alice can decrypt the ciphertext, as only she knows the private key.

Public key cryptosystems must be based on computational problems that are hard to solve. Mathematics provides such problems. For example, the RSA cryptosystem is based on the difficulty of finding the prime factors of a very large integer.

Some Number Theory

Before describing the very popular RSA public-key encryption scheme we need to develop some results in number theory. This requires a modest familiarity with the binomial theorem and modular arithmetic.

In modular arithmetic, we collect integers into classes according to their remainder after division by a certain number $p$ , called modulus. So for example if $p=7$ we have that 9 is in the class of 2, and 5, 12 and 19 are all in the same class. We write $9\equiv 2 \pmod 7$ and $12\equiv19\equiv 5 \pmod 7$ . It is easy to see that there are only 7 possible classes, represented by $\{0,1,2,3,4,5,6\}$ when working modulo $7$ . It is possible to perform addition and multiplication modulo 7 by simply reducing the result after performing the operation normally, so $3+8=11\equiv 4 \pmod 7$ and $3\cdot 5=15\equiv 1 \pmod 7$ . Note that if $a \equiv b \pmod{p}$ then $(a-b)$ is a multiple of $p$ .

Let $p$ and $q$ be primes, $p \ne q$ and let $t > 0$ be an integer that is not a multiple of $p$ or $q$ . We will now show that the formula $t^{(p-1)(q-1)}\equiv1 \pmod{pq}$ holds. This formula is a special case of the Fermat-Euler theorem.

The proof begins with the formula for binomial coefficients:

$\binom pi=\frac{p!}{i!(p-i)!},$

where $i$ is an integer with $0 < i < p$ . From

$i! \ \binom pi= p(p-1)(p-2)\cdots(p-i+1),$

it follows that $p$ must be a divisor of $\binom pi$ , since $p$ divides the right-hand side but does not divide $i!$ .

Then, for any integers $A$ and $B$ , by the binomial theorem,

$(A+B)^p=A^p+\binom p1 A^{p-1}B+\binom p2 A^{p-2}B^2+\cdots+B^p\equiv A^p+B^p \pmod p .$

Taking a further integer $C$ ,

$(A+B+C)^p=((A+B)+C)^p\equiv(A+B)^p+C^p\equiv A^p+B^p+C^p \pmod p.$

In this way, for any integers, $A_1$ , $A_2$ , …, $A_t$ ,

$(A_1+A_2+\cdots+A_t)^p\equiv A_1^p+A_2^p+\cdots+A_t^p \pmod p.$

Now put $A_1=A_2=\cdots=A_t=1$ and we obtain

$t^p\equiv t \pmod p.$

This equation means that $(t^p - t) = t( t^{p-1} - 1)$ is a multiple of $p$ . Since $p$ does not divide $t$ and $p$ is prime it follows that

$t^{p-1}\equiv 1 \pmod p.$

Now raise both sides of this congruence to the power $q-1$ :

$t^{(p-1)(q-1)}\equiv 1 \pmod p.$

Repeating the argument but using $q$ instead of $p$ , we find

$t^{(p-1)(q-1)}\equiv 1 \pmod q.$

These say, respectively, that there are integers $h$ and $k$ such that

$t^{(p-1)(q-1)}=1+ph, \quad t^{(p-1)(q-1)}=1+qk,$

so $ph=qk$ . Then $p$ divides $k$ (since $p$ and $q$ are distinct primes), and so $k=pl$ , say, for some integer $l$ . Now we have $t^{(p-1)(q-1)}=1+pql$ , or

$t^{(p-1)(q-1)}\equiv1 \pmod {pq}.$

This completes the proof. $\Box$

The RSA cryptosystem

The acronym RSA stands for Rivest, Shamir and Adleman, who first proposed this scheme in 1977. It works as follows.

First choose two distinct primes, $p$ and $q$ . Calculate $N=pq$ and $\phi=(p-1)(q-1)$ . Choose an integer $e$ at random between 3 and $N-2$ , but such that $e$ and $\phi$ have no prime factors in common. The public key is the pair $(N,e)$ . The private key $d$ , which the sender will keep secret, is calculated so that $d\equiv e^{-1}\pmod\phi$ , that is, the number such that $de\equiv1\pmod\phi$ (this is easily done using Euclid’s algorithm). For example, take $N = 437 = 19 \cdot 23$ , $\phi = 396$ , $e = 5$ and $d = 317$ .

Messages in the RSA system are integers $x$ such that $0 < x < N$ . It might not initially be clear how to encrypt text messages with a scheme that uses integer numbers. However, cryptographic schemes are implemented on computers and all documents are just binary data, which can be encoded using integers.

The encryption process is the following. Suppose Bob wants to send a message $x$ to Alice. He looks up Alice’s public key $(N,e)$ , calculates $y\equiv x^e \pmod{N}$ , and sends $y$ to Alice. To decrypt the ciphertext $y$ , Alice makes use of the private key $d$ , by calculating $x\equiv y^d \pmod{N}$ .

It is important to point out that, even though $e,d$ and $N$ are huge, it is possible to efficiently compute, for example, $y^d \pmod N$ , using a technique called modular exponentiation.

Decryption works since $de=1+k\phi$ , for some integer $k$ , and as we showed above

$x^\phi=x^{(p-1)(q-1)}\equiv1 \pmod N$

(in practice the case when $x$ is a multiple of $p$ or $q$ can be ignored), and so

$y^d\equiv (x^e)^d= x^{1 + \phi k} = x(x^\phi)^k\equiv x\cdot1^k=x \pmod N.$

A malicious user that does not know the private key $d$ would need to factor $N$ to recover $p$ and $q$ . This is beyond the limits of current computing if these primes are sufficiently large, say 200 digits each (the current world records for factoring $N = pq$ are where $p$ and $q$ are around 100 digits each).

This is actually defining the level of security of the scheme. The main notion about public-key cryptography, in fact, is that a cryptosystem is secure as long as the computational effort required to break it is beyond the attacker’s resources. This is fixed a priori (usually $2^{128}$ or $2^{256}$ bit operations) and depends on the context and aim of the communication. Clearly, a CIA secret message and an email between two internet users are expected to meet very different standards of security!!!

Signatures

We can now turn to the problem of software updates. In other words the problem of authentication. As before, we have a public key and a private key. Alice, using her private key, constructs a digital signature to be sent along with a document, in order to prove its authenticity (the signature depends on the document and cannot be cut-and-pasted to a different document). The receiver then verifies the digital signature using the public key.

Suppose, for example, that your computer tells you it found an update for Adobe. How does the computer know the software comes from Adobe and is not a virus disguised as an update? The solution is that the update has a digital signature with respect to the Adobe public key. This public key is already installed on your computer in the Adobe software, so your computer can verify the signature before installing the update; a successful verification proves the update is really from Adobe and no one else.

We now show how to construct digital signatures using RSA.
The private and public keys are the same as for encryption. When Alice wants to authenticate a document (e.g., a software update) she encodes it as an integer $0 < x < N$ , computes $\sigma\equiv x^d \pmod{N}$ , and attaches the signature $\sigma$ to the document. To verify the signature Bob looks up Alice’s public key, and verifies the signature by calculating $x'\equiv \sigma^e \pmod{N}$ and checking that $x=x'$ . It is clear that, just as for the RSA cryptosystem, a malicious user aiming to produce a valid signature (for example a hacker designing a virus) would need the exponent $d$ , hence requiring to factor $N$ .

Current Research

We have sketched the RSA cryptosystem and digital signature schemes, but there are many other systems based on mathematical objects like finite fields, elliptic curves, systems of non-linear multivariate equations, error-correcting codes and more.
Public key cryptography is a very active research area, and there are still open questions being studied.

A post-quantum scenario

Are all our problems solved with RSA? Unfortunately, the answer is no. The security of RSA, as well as many other schemes based on number theory, is seriously threatened by the potential development of quantum computers. Shor’s algorithm, published in a 1994 paper with the portentous title “Polynomial time algorithms for discrete logarithms and factoring on a quantum computer”, is capable of breaking the RSA cryptosystem as long as a large enough quantum computer can be built. Quantum computers of a very small size are already a reality and it is plausible to expect improvements in the near future.

It is therefore important to provide alternative systems whose security won’t be affected in case this scenario becomes real. The cryptographic community is very active in this direction, and current research is focusing on developing new cryptosystems from various areas of mathematics, based on computational problems that will hopefully not suffer the same vulnerabilities to quantum algorithms.

References

[1] Simon Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (2000), Anchor.

Cryptographie à clé publique

Related

Leave a Reply Cancel reply

Receive notice of every new vignette.

Search

Meta

Cryptographie à clé publique

Share this:

Related

Leave a Reply Cancel reply

Receive notice of every new vignette.

Search

Meta