---
breaks: false
---

# RSA@SEC@VSU

## A gist

'tis quite trivial:

1. Generate such public $(n, \epsilon)$
and private $(n, d)$ keys
that
$$(x^\epsilon\ \%\ n)^d\ \%\ n = x$$
for all $0\leq x\leq x_{\mathrm{max}}$.
2. Encrypt the message $m$
into $c = m^\epsilon \ \%\ n$.
3. Decrypt the message using
$m = c^d = (m^\epsilon)^d \ \%\ n$.

Alternatively:

2. Sign the message: $s = m^d\ \%\ n$.
3. Check the signature $s$ by
verifying that $s^\epsilon \equiv m \mod n$.

## Key generation

1. Take some huge distinct primes $p, q$.
2. Set $n=pq$.
3. Take some $\lambda\in\mathbb{N}_+$ that satisfies
$$\label{eqnlambda}\tag{1}
m^\lambda \equiv 1 \mod pq$$
for every $m$ coprime to $n=pq$.
E.g.:
$$\lambda = (p-1)(q-1)$$

**NB**: After the generation step for the equation $\eqref{eqnlambda}$
to be satisfied for a particular $m$
it will suffice that $m < p,q$
for $p$ and $q$ are both primes,
4. Find some $\epsilon$
coprime to $\lambda$:
$\gcd(\epsilon, \lambda) = 1$.
5. Set $d$ to be multiplicative inverse of $\epsilon$:
$$\epsilon d \equiv 1 \ \mod n$$

## Checking the formulas

Let's check that
$$(m^\epsilon \ \%\ n)^d \ \%\ n = m.$$
Note first that
$$(m^\epsilon \ \%\ n) \equiv m^\epsilon \mod n$$
and hence
$$ (m^\epsilon \ \%\ n)^d \ \%\ n =
m^{\epsilon d} \ \%\ n =
m^{1 + \alpha\lambda} \ \%\ n =
m\ m^{\alpha \lambda} \ \%\ n =
m$$
since $\epsilon d\equiv 1 \mod \lambda$
and $m<p,q$ is coprime to $n=pq$:
$$\epsilon d - 1 = \alpha \lambda\ \text{for some}\ \alpha,$$
$$m^{\lambda} \equiv 1 \mod n,$$
$$m^{\alpha\lambda} \equiv 1 \mod n,$$
$$m m^{\lambda} \equiv m \mod n.$$

* * *