02.5 Public Key Cryptography

The table following the torus rule will not always be filled.

The placing $[k{]}_{m_1,m_2}\mapsto ([k{]}_{m_1},[k{]}_{m_2})$ is the action of a map

$$\psi :\mathbb{Z}/m_1{m}_2\mathbb{Z}\to \mathbb{Z}/m_1\mathbb{Z}\times \mathbb{Z}/m_2\mathbb{Z}$$

The Chinese Remainders Theorem

When filling a table going down diagonally, we follow the torus rule If $m_1$ and $m_2$ are relatively prime, then the map $\psi$ is

1. bijective
2. an isomorphism with respect to $+$ and $\cdot$

Theorem

With $p$ and $q$ be distinct prime numbers and let $k$ be a multiple of both $(p-1)$ and $(q-1)$

Using both fermat’s theorem and the chinses remainders theorem. For every integers $a$, and every non-negative integer $l$

$$([a{]}_{pq}{)}^{lk+1}=[a{]}_{pq}$$

RSA

Stands for Rivest, Shamir, Adleman

Using 3 integers $m$, $e$ and $d$, we have for any plaintext $t$

$$[(t^e{)}^d{]}_m=[t{]}_m$$

The encoder encrypts the cryptogram $c=t^e\mathrm{mod}m$

To decode, we run $t=c^d\mathrm{mod}m$

m

To find $m$, we generate 2 random large primes $p$ and $q$. We have $m=pq$

e

To find $e$, we find a number which has no common divisor with $k$, which is a multiple of $(p-1)$ and $(q-1)$

d

Using Bézout, the receiver produces $d$, such that $de+kl=1$

Hash function

A hash function is a many-to-one function, that maps a sequence to a fixed length sequence.

Digital Signature

If we want to sign a document — to verify authenticity of the document — we use a hash function

We have the digital signature of the document $s=f_A^{-1}(h(t))$, where $f_A$ is the public trapdoor hash function specific to the signer $A$

Trusted Agency

How do we know that a key that we receive to encrypt/decrypt a document has not been tampered with ?

We have a trusted agency (hardcoded) which signs keys, we can then verify that the key is authentic.