A simpified version of RSA from "Cryptologia_, Vol. 21, No. 4 (1997). *Cryptography As a Teaching Tool* https://sites.math.washington.edu/~koblitz/crlogia.html Unlike ordinary [[RSA public-key-private-key Encryption]], here the encryption/decryption rules go by multiplication instead of exponentiation $ C = eM \text{ mod }N, M = dC \text{ mod }N, ed = 1 \text{ mod }N$ For which an attacker would need to be able to find the inverse of the encryption exponent $d=e^{-1} \text{ mod }N$ to break the cypher. This can be done by Euler's algorithm. (I.e. the attacker needs to break the "discrete division" problem) (As opposed to ordinary RSA which uses exponentiation, for which an attacker needs to solve the discrete logarithm problem) # Suggested Implementation This system can be implement for any base $N$ as long as you can find $e,d$ so that $e\times d= 1\text{ mod }N$ . The way this is suggested to do this is: 1. Choose $a,b$, set $M=ab - 1$ (so $ab = 1\text{ mod }M$ by definition) 2. The system $e=a$, $d=b$ and $N=M$ would work. However, you can further obscure things even more by adding on some multiples to maintain this property. So they suggest choosing an $\alpha,\beta$ and using: $\begin{align} e &= \alpha M + a \\ d&= \beta M + b \\ N &= \frac{ed-1}{M} = \alpha \beta M + \alpha b + \beta a + 1\end{align}$ By doing this, we still have $ed=1 \text{ mod }N$ but now the numbers are a bit larger! # Mihai's alternative Implementation using Fermat's Little Theorem The whole thing will work because working modulo a prime $p$ , we can compute inverses by using [[Fermat's Little Theorem]] that $a^{p-1} = 1 \text{ mod }p$, and so the inverse of any number can be computed (e.g. $a^{-1} = a^{p-2}$ when working mod $p$ . ) Here is the exact setup: 1. Choose two. primes $p,q$ and set $N=pq$ 2. Given any $e$, set $d$ to be: $d=(eq)^{p-2}q + (ep)^{q-2}p \text{ mod }N$ Why does this work? Notice that $ed = (eq)^{p-1} + (ep)^{q-1}$so working mod $p$ , we have from FLT result $ed=1+0=1\text{ mod }p$ The same exact thing works to show $ed = 1\text{ mod }q$ . Then by the [[Chinese remainder theorem (simple case)]], we have $ed = 1\text{ mod }N$ and therefore $d$ works as the decryption factor.