Asymetrická šifra RSA

RSA je jedna z nejfrekventovaněji využívaných šifer, název je akronymem autorů (Rivest, Shamir, Adleman), kteří ji představili v roce 1978, skutečným autorem byl však pouze Ron Rivest. Stejný kryptosystém byl objeven již v roce 1973 pracovníkem britských tajných služeb, právě z tohoto důvodu však musel zůstat utajen.

Princip

Šifra je postavena primárně na složitost řešení problému diskrétního logaritmu. Způsobů, jak se dá zavést je více, níže je ten nejjednodušší možný.

1. Zvolme 2 prvočísla stejné bitové délky p a q. Dále vypočítejte jejich součin n = pq (bitová délka n je udávaná velikost klíče, v praxi se využívá velikost 1024, 2048 a 4096 bitů, případně i více dle místa využití).

2. Vypočtěte hodnotu Eulerovy funkce φ(n) v bodě n, to se provede jako φ(n)=(p-1)(q-1)

3. Zvolte přirozené číslo e takové, že 1 < e < φ(n) a zároveň je číslo e nesoudělné s φ(n). Čísla e a n představují veřejný klíč.

4. Vypočtěte privátní klíč d, který se rovná multiplikativní inverzi e mod φ(n). O hledání multiplikativní inverze viz ZDE.

Dvojce n, d se využívá při dešifrování, dvojce n, e se využívá při šifrování. V praxi se zveřejňují pouze čísla n a e (vše ostatní zůstává utajeno).

Šifrování

Předpokládejme, že máme zprávu m, 1 < m < n, šifrování, tedy hledání zašifrované hodnoty c, se provádí dle vzorce:

c = m^e mod n

Dešifrování

Předpokládejme, že máme zašifrovanou zprávu c, 1 < c < n, šifrování, tedy hledání původní hodnoty m, se provádí dle vzorce:

m = c^d mod n

Programování

V některých programovacích jazycích je možné šifru implementovat velmi snadno, následuje ukázka z jazyka Java:

import java.math.BigInteger;
import java.security.SecureRandom;

public final class RSA {
    BigInteger n,e,d;

    public RSA(int bitLength) {
        this.setRandomValues(bitLength);
    }
    private void setRandomValues(int bitLength) {
        //Random stream:
        SecureRandom rand = new SecureRandom();
        //Compute primes p and q:
        BigInteger p = BigInteger.probablePrime(bitLength, rand);
        BigInteger q = BigInteger.probablePrime(bitLength, rand);
        //Compute n:
        this.n = p.multiply(q);
        //Compute Euler's totient function phi(n) = (p-1)*(q-1):
        BigInteger phiN = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
        //Find random e, such that 1 < e < phi(n) and GCD(n,phi(n)) = 1:
        this.e = new BigInteger("65537");
        //If GCD(n,phi(n)) != 1:
        while(!e.gcd(phiN).equals(BigInteger.ONE)) {
            e = e.add(BigInteger.ONE);
        }
        //Compute the value of d = e^(-1) mod phi(n):
        this.d = e.modInverse(phiN);
    }
    
    public BigInteger encrypt(BigInteger m) {
        //Find cipher c = m^e mod n:
        return m.modPow(e, n);
    }
    public BigInteger decrypt(BigInteger c) {
        //Find cipher c = m^e mod n:
        return c.modPow(d, n);
    }
}