Problem 8

1.

For two distinct prime numbers $p$ and $q$, let $l$ be the least common multiple of $p-1$ and $q-1$. For an integer $d$ that is prime to $l$, there exists an integer $e$ such that $ed \equiv 1 \mod l$. Let $n=pq$, $M$ and $C$ be integers with $0 \leq M$, $C < n$. Furthermore, let $E(M)$ and $D(C)$ be

$$E(M) \equiv M^e \mod n, \quad D(C) \equiv C^d \mod n.$$

Show that

$$M \equiv D(E(M)) \mod n.$$

2.

Describe a public key cryptographic system based on the above fact.

1.

$D(E(M)) \equiv E(M)^d \mod n$
$\equiv (M^e)^d \mod n$
$\equiv M^{ed} \mod n$
$\equiv M^{kl + 1} \mod n$
$\equiv M^{k(p-1)(q-1) + 1} \mod n$
$\equiv M^{k(p-1)(q-1)}M \mod n$
$p$ and $q$ are prime, thus $\phi(p)=p-1$ and $\phi(q)=q-1$.
Euler's function is multiplicative and $p\wedge q=1$, thus $\phi(pq)=\phi(p)\phi(q)$.
$\equiv M^{k\phi(pq)}M \mod n$
$\equiv M^{k\phi(n)}M \mod n$
Euler's theorem says that if $s$ is coprime with $m$, then $s^{\phi(n)\equiv 1\mod m}$.
$\equiv M \mod n$

2.

This system can help describe a public key cryptogaphic system. In such a system, the enciphering key is made public and the deciphering key is keep secret by the owner of the keys. To communicate with the owner of the secret key a message is encrypted with the corresponding public key, this message can only be decrypted using the secret key.

More precisely, this is the RSA system. We generate two large primes $p$ and $q$ (size of about 256 bits) and compute their product $n$. The RSA system is then a block cipher in which the plaintext and ciphertext blocks are integer between 0 and $n-1$. The value of $n$ is public knowledge and the enciphering key $e$ is such that $e \wedge (p-1)(q-1) = 1$. A message block $m$ is then enciphered as $c \equiv m^e \mod n$. For large $n$, it is generally accepted that, unless the factors of $n$ are known, $m \mapsto m^e \mod n$ is a one-way function and thus is very difficult to determine $m$ from knowledge of $m^e$, $n$ and $e$. Since we know the factors of $n$, we can compute $p-1$ and $q-1$ and then compute the integer $d$ such $de \equiv 1 \mod (p-1)(q-1)$. The reason why the interceptor cannot find $d$ is that the modulus of the equation is unknown. Thanks to $d$, we can compute the plaintext ( $c^d \equiv m \mod n$). $d$ is the secret deciphering key and the cryptogram $c$ is deciphered by forming $c^d \mod n$.