---
# System prepended metadata

title: RSA@SEC@VSU

---

---
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.$$


* * *
