RSA

#MINTgrün #Informatik #Definition #InfoProp

RSA-Verschlüsselung

Info

die RSA-Verschlüsselung ist eine asymmetrische Verschlüsselungsmethode
Entdeckt von Rivest, Shamir, Adleman
2002 Turing-Award
Bis heute gilt diese Verschlüsselungsmethode als unknackbar

beruht auf mathematischen Funktionen, die in einer Richtung einfach aber in der anderen Richtung (Umkehrfunktion) schwer zu berechnen sind Einwegfunktion (one-way function)
Faktorisierung großer Zahl, d.h. Zerlegen in Primfaktoren, schwierig
Multiplikation einer großen Zahl durch Multiplikation von Primzahlen einfach
manche Einwegfunktionen, sind Falltürfunktionen (trapdoor one-way function) - mit Hilfe einer Zusatzinformation sind sie auch rückwärts leicht zu berechnen
Primzahl ist eine ganze Zahl, $x \in N > 1$ , die nur durch sich selbst und durch $1$ teilbar ist #Definition

Euklidischer Algorithmus

Ziel: Berechnung des größten gemeinsamen Teilers $(ggT)$ zweier natürlicher Zahlen, z. B. $gcd (a, b)$ .
Grundidee:
- Nutzt die Eigenschaft: $gcd (a, b) = gcd (b, a \mod b)$ .
- Reduziert schrittweise das Zahlenpaar, bis ein Rest $0$ erreicht ist. Der letzte Nicht-Null-Rest ist der ggT.
Mathematisches Vorgehen:
1. Anfang: Gegeben $a, b$ mit $a > b$ .
2. Schrittweise Division mit Rest: $\begin{matrix} = q_{1} b + r_{1} \\ b = q_{2} r_{1} + r_{2} \\ r_{1} = q_{3} r_{2} + r_{3} \\ \dots \\ bis r_{k} = 0 \end{matrix}$
3. Der letzte Nicht-Null-Rest $r_{k - 1}$ ist $gcd (a, b)$

_EUCLID_OLD_(a,b)
1  wenn a = 0 dann
2    Ergebnis = b
3  sonst
4    solange b ≠ 0
5      wenn a > b dann
6        a ← a – b
7      sonst
8        b ← b – a
9      //
10   //
11   Ergebnis = a
12 //

_EUCLID_OLD_RECURSIVE_(a,b)
1  wenn b = 0 dann
2    Ergebnis = a
3  sonst
4    wenn a = 0 dann
5      Ergebnis = b
6    sonst
7      wenn a > b dann
8        Ergebnis = _EUCLID_OLD_RECURSIVE_(a – b, b)
9      sonst
10       Ergebnis = _EUCLID_OLD_RECURSIVE_(a, b – a)
11     //
12   //
13 //

_EUCLID_RECURSIVE_(a,b)
1  wenn b = 0 dann
2    Ergebnis = a
3  sonst
4    Ergebnis = _EUCLID_(b, Divisionsrest(a durch b))
5  //

_EUCLID_ITERATIVE_(a,b)
1  solange b ≠ 0
2      h ← Divisionsrest(a durch b)
3      a ← b
4      b ← h
5  //
6  Ergebnis = a

Bedeutung des Euklidischen Algorithmus für RSA
- Der öffentliche Schlüssel-Exponent $e$ muss teilerfremd zu $φ (n)$ sein (also $gcd (e, φ (n)) = 1$ ).
- Der euklidische Algorithmus prüft diese Bedingung effizient.
Erweiterter euklidischer Algorithmus:
- Findet zusätzlich ganze Zahlen $x, y$ mit $x a + y b = gcd (a, b)$ .
- In RSA wird damit der Multiplikative Inverse von $e$ modulo $φ (n)$ berechnet, also $d$ mit $e d \equiv 1 \mod φ (n)$ .
- Somit liefert der erweiterte euklidische Algorithmus den privaten Schlüssel-Exponent $d$ .

Erzeugen des Schlüsselpaars

besteht aus drei Zahlen $e, d$ und $n$
$n$ – RSA-Modul
$e, d$ – Ver-(encrypt) und Entschlüsselungsexponent (decrypt)
$(e, n)$ – public key, $(d, n)$ – private key
Vorgang
1. wähle 2 Primzahlen $p$ und $q$
2. berechne den RSA-Modul $n$ als $n = p \cdot q$
3. berechne $ϕ (n) = (p - 1) \cdot (q - 1)$
4. ermittle Zahl $e$ , die teilerfremd zu $ϕ (n)$ und $< ϕ (n)$
5. berechne $d$ als Kehrwert von $e \mod ϕ (n)$

Signatur:

da man den private key und den public key praktisch vertauschen kann, ist überprüfbar, ob das Gegenüber wirklich den private key besitzt.
Um das zu prüfen kann der Sender mit dem private-key einen text oder eine Zahl verschlüsseln. versucht man nun diese Nachricht mit dem public key zu entschlüsseln bekommt man genau dann die unverschlüsselte Nachricht zurück wenn der Absender wirklich den privaten Schlüssel besitzt

RSA-Verschlüsselung

Euklidischer Algorithmus

Erzeugen des Schlüsselpaars

Signatur:

Ver- und entschlüsseln