/ 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 mm, private key dd, public key ee.

Key generation

  1. Choose two distinct prime numbers pp and qq with n=pqn = pq.
  2. choose random private key dd with 1<d<n11 \lt d \lt n-1
  3. find public key ee with de1(mod(p1)(q1))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)(d, e)

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

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

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

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

Decrypt cipher c=2790c = 2790:
m=2790413mod3233=65m=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