UoL CS Notes
Menu

Public Key Encryption (One Time Pad & RSA)

COMP315 Lectures

One-time Pads

This method of encryption provides perfect secrecy provided that the following are met:

  • The key should never be reused.
  • The key needs to be at least as long as the message:
    • If a longer key is used then the message should be padded.
  • You have a perfect source of randomness to generate the keys.

Encryption and decryption is completed by:

  • XORing the key with the message.

It is ideal in a scenario where you have:

  • A slow secure channel to transfer keys in advance.
  • A fast insecure channel where you can send your encrypted messages.

This method is too inconvenient to use in e-commerce.

RSA

RSA relies on the following functions:

  • Public key generation function keygen: $K \rightarrow L$
  • Encryption function enc: $X\times L\rightarrow Y$
  • Decryption function dec: $Y\times K\rightarrow X$

It also requires that the following are true:

  • Correctness - dec(end(x, keygen(k)), k)=x for every $x\in X$ and $k\in K$.
  • Efficiency - Given $k$ and $x$, it is feasible to compute keygen(k), enc(x, keygen(k)) and dec(enc(x, keygen(k)), k).
  • Key Secrecy - Given l = keygen(k) and multiple encoded messages using that public key, it is not feasible to compute any of the messages.

Groups

In algebra a group is a pair $(G, \cdot)$ where $G$ is a set and $\cdot:G\times G\rightarrow G$ is an operator with the following properties:

Identity
There is an identity element $\mathbf 1\in G$ such that $\mathbf1\cdot x=x\cdot\mathbf1=x$ for every $x\in G$.
Inverse
For every $x\in G$ there is a $x^{-1}\in G$ such that $x\cdot x:^{-1}=x^{-1}\cdot x=\mathbf 1$.
Associative
$(x\cdot y)\cdot z=x\cdot(y\cdot z)$ for every $x,y,z\in G$.

Additionally, a group is finite if the set $G$ is finite.

Example Finite Group

Consider the following finite group that is used in RSA:

\[((\mathbb Z/n\mathbb Z)^*,\times)\]

This is the group of integers modulo $n$ (except those $x$ where $\text{gcd}(n,x)>1$).

The identity and associative properties for this group are equal to multiplication, however the inverse is calculated differently:

Take any $x\in(\mathbb Z/n\mathbb Z)^*$, we will show that $x$ has an inverse:

  1. We want to show that there is some $z\in (\mathbb Z/n\mathbb Z)^*$ such that $xz=1$.

    $z$ is the inverse.

  2. We can test the inverse if the following holds:

    \[xz=1\mod n\]

    Computing $x^{-1}\mod n$ take logarithmic time with respect to $x$ and $n$. This makes it quite feasible for large numbers on modern hardware.

Order

Let $(G,\cdot)$ be a finite group, and $x\in G$. The order of $x$, denoted by $\text{ord}(x)$, is the lowest number $i$ such that $x^i=\mathbf 1$.

This power is at most $m$ where $m=\left\vert G\right\vert$.

Lagrange’s Theorem

Let $(G,\cdot)$ be a finite group. Take any $x\in G$ and let $m=\mid G\mid$. Then $\text{ord}(x)$ divides $\mid G\mid$.#

This is to prove that:

If we know $\mid G\mid$, we can easily compute $k=e^{-1}$ and therefore $e\times k=1\mod\mid G\mid$.

Therefore $(x^e)^k=x^{e\times k}=x$.

However, for this to be the case we need to know $\mid G\mid$ (we can use this as a key to encrypt $x$).

RSA Group Size

The group used in RSA, $(\mathbb Z /n\mathbb Z)^*$, where $n$ is the product of two large primes $p,q$. To calculate the group size:

  1. There are $n$ numbers in the group $(\mathbb Z /n\mathbb Z)^*$
  2. We must exclude every number $x$ such that k$\text{gcd}(x,n)\neq 1$.
  3. …
  4. In total there are $p\times q-p+1$ elements, which is equal to $(p-1)(q-1)$.

RSA Description

Key Generation:

  1. Find two large prime numbers $p$ and $q$.
  2. Compute $n=pq$ and $m=(p-1)(q-1)$.
  3. Find $e$ such that $gcd(e,m)=1$ and take $k=e^{-1}\mod m$.
  4. The public keys are $n$ and $e$. The private key is $k$.

Encryption:

  1. For plaintext $x$ compute the ciphertext $y=x^e\mod n$.
  2. A large message $x$ may need to be split into several smaller messages.

Decryption:

  1. For cipher text $y$, compute the plaintext $y^k\mod n$.

Public Key Encryption Issues

  • You must gain a third party’s key in order to send a message to them.
    • You must also trust that the key is their’s and not an attacker’s.
  • Public key cryptography is slower than symmetric key.
  • Very large keys are required for good security (4096 bit).

Public Key Encryption Strengths

  • With large keys, RSA is pretty much invulnerable to brute force, known plaintext and chosen plaintext attacks.
  • Similar plaintexts product very different cyphertexts.
  • Public key distributions is much easier as it can be asynchronous.