/ informatics / algorithm /

[edit]

Definition

RSA is a public-key cryptosystems and is used for secure data transmission.

The RSA algorithm involves four steps: key generation, key distribution, encryption, and decryption.

Key sizes: 1024 b, 2048 b, 4096 b

Principle

$${\displaystyle (m^{e})^{d}\equiv m{\pmod {n}}}$$

with the message $m$, private key $d$, public key $e$.

Key generation

  1. Choose two distinct prime numbers $p$ and $q$ with $n = pq$.
  2. choose random private key $d$ with $1 \lt d \lt n-1$
  3. find public key $e$ with $de \equiv 1 (\mod (p-1)(q-1))$
Example

Here is an example of RSA encryption and decryption. The parameters used here are artificially small.

Generate Keypair $(d, e)$

  1. Choose two distinct prime numbers, such as
    $p=61$ and $q=53$
  2. Compute $n = pq$ giving
    $n=61\times 53=3233$
  3. Compute the Carmichael's totient function of the product as $\lambda(n) = lcm(p -1, q - 1)$ giving
    $\lambda (3233)={\mathop{lcm}} (60,52)=780$
  4. Choose any number $1 \lt e \lt 780$ that is coprime to $780$. Choosing a prime number for $e$ leaves us only to check that $e$ is not a divisor of 780.
    Let $e=17$
  5. Compute d, the modular multiplicative inverse of $e \mod \lambda(n)$ yielding, $d=413$
    $d\times e=1{\mod {\lambda }}(n)$
    $413\times 17=1{\mod {7}}80$

The public key is $(n = 3233, e = 17)$. Encryption function is $c(m)=m^{17}{\mod {3}}233$.

The private key is $(n = 3233, d = 413)$. Decryption function is $m(c)=c^{413}{\mod {3}}233$.

Encrypt message $m = 65$:
$c=65^{17}{\mod {3}}233=2790$

Decrypt cipher $c = 2790$:
$m=2790^{413}{\mod {3}}233=65$

Attack Model

homomorphic multiplication

RSA is multiplicatively homomorphic. That means you can exchange the order of operations without affecting the result. The product of the encryption of two messages is equal to the encryption of the product of the messages.

$$E(x)E(y) \equiv x^ey^e \equiv (xy)^e \equiv E(xy) (\pmod n)$$

Thus, you can perform calculations on encrypted data, without knowing the data, which is used in zero-knowledge proofs.

References

-->