Das RSA-Verfahren

Aus ProgrammingWiki

Das RSA-Verfahren ist ein asymmetrische Verschlüsselungsverfahren, d.h. der zu übermittelnde Text wird mit einem öffentlichen Schlüssel verschlüsselt und mit einem privaten (also "geheimen") Schlüssel entschlüsselt.
Es wurde 1977 von Ronald L. Rivest, Adi Shamir und Leonard Adleman am MIT in Boston entwickelt und galt damals als das erste asymmetrische Verschlüsselungsverfahren.
Man nutzt dazu die Tatsache, dass es praktisch unmöglich ist, eine Primfaktorzerlegung sehr großer Zahlen (ca. 200 Stellen und mehr) in einem vertretbaren (Zeit-)Aufwand vorzunehmen.

RSA-Algorithmus

1. Lege zwei (große) Primzahlen $p$ und $q$ fest mit $p \neq q$.
   Bilde das Produkt $N = p \cdot q$.
   Suche eine weitere Zahl $e$, für die gilt:
   • $e$ ist Primzahl und größer als p und q oder
   • $e$ ist teilerfremd zu $(p-1) \cdot (q-1)$.
   Die Zahlen $e$ und $N$ bilden den öffentlichen Schlüssel.
2. Ermittle den privaten Schlüssel $d$ mit:
   • $d \le (p-1) \cdot (q-1)$ und
   • $(d \cdot e) \bmod [(p-1) \cdot (q-1)] = 1$
3. Ein Klartext-Zeichen mit dem Code $c$ wird mit

   $c^e \bmod N = m$

   zu $m$ verschlüsselt.

4. Der verschlüsselte Code $m$ wird mit

   $m^d \bmod N = c$

   zum Code $c$ des Klartext-Zeichens entschlüsselt.

Implementation

Wir definieren wieder das zulässige Alphabet, bestehend aus Groß- und Kleinbuchstaben sowie Ziffern. Die Sonderzeichen werden diesmal in die Verschlüsselung einbezogen. Weiterhin sollen uns einige nützliche Prozeduren bei der Umsetzung des RSA-Algorithmus unterstützen:

(define sqr (lambda (x) (* x x))) (define quotient (lambda (m n) (floor (/ m n)))) (define remainder quotient) (define mod (lambda (n m) (if (< n 0) (- m (modulo (abs n) m)) (modulo n m)))) (define string-car (lambda (str) (string-ref str 0))) (define string-cdr (lambda (str) (substring str 1 (string-length str)))) (define char-pos (lambda (z str) (letrec ([pos (lambda (n str) (cond [(= (string-length str) 0) 0] [(equal? z (string-car str)) n] [else (pos (+ n 1) (string-cdr str))]))]) (pos 1 str)))) (define pos-char (lambda (n str) (string-ref str (mod (- n 1) (string-length str))))) (define char-cons (lambda (z str) (string-append (string z) str))) (define char-in-string? (lambda (z str) (cond [(= (string-length str) 0) #f] [(equal? z (string-car str)) #t] [else (char-in-string? z (string-cdr str))])))

(define gross "ABCDEFGHIJKLMNOPQRSTUVWXYZ") (define klein "abcdefghijklmnopqrstuvwxyz") (define number "1234567890") (define sonder "+-./,;:!? ") (define platzhalter #\*) (define alphabet (string-append gross klein number sonder)) (define ggt (lambda (m n) (if (= n 0) m (ggt n (modulo m n))))) (define primzahl? (lambda (n) (letrec ([prim? (lambda (n t) (cond [(> t (sqrt n)) #t] [(= (modulo n t) 0) #f] [else (prim? n (+ t 2))]))]) (cond [(= n 2) #t] [(or (< n 2) (= (modulo n 2) 0)) #f] [else (prim? n 3)])))) (define potmod (lambda (x y n) (cond [(= y 1) x] [(odd? y) (modulo (* x (potmod x (- y 1) n)) n)] [else (modulo (sqr (potmod x (quotient y 2) n)) n)]))) (define public-key (lambda (p q) (letrec ([key (lambda (e) (cond [(> e (* (- p 1) (- q 1))) 1] [(= (ggt e (* (- p 1) (- q 1))) 1) e] [else (key (+ e 2))]))]) (key 3)))) (define private-key (lambda (p q e) (letrec ([key (lambda (d) (cond [(> d (* (- p 1) (- q 1))) 1] [(= (modulo (* e d) (* (- p 1) (- q 1))) 1) d] [else (key (+ d 2))]))]) (key 3))))

Eine geringe Erweiterung der Prozedur pos-char soll die späteren Implementationen erleichtern:

(set! pos-char (lambda (n str) (if (= n 0) platzhalter (string-ref str (mod (- n 1) (string-length str))))))

Nun können wir öffentliche und private Schlüssel bilden und diese auf ihre Korrektheit überprüfen:

(define p 97) (define q 103) (define N (* p q)) (define e (public-key p q)) (define d (private-key p q e))

Zum Ver- bzw. Entschlüsseln müssen wir nun die entsprechenden Prozeduren implementieren.
Dazu bietet sich die sehr effiziente Prozedur potmod mit der folgenden Syntax an:

(potmod <x> <y> <n>) ; ...  xy mod n

(define codieren-lsg (lambda (str key n) (if (= (string-length str) 0) () (cons (potmod (char-pos (string-car str) alphabet) key n) (codieren-lsg (string-cdr str) key n))))) (define decodieren-lsg (lambda (ls key n) (if (null? ls) "" (char-cons (pos-char (potmod (car ls) key n) alphabet) (decodieren-lsg (cdr ls) key n))))) (define listequal? (lambda (ls1 ls2) (cond [(and (null? ls1) (null? ls2)) #t] [(or (null? ls1) (null? ls2)) #f] [(and (list? (car ls1)) (list? (car ls1))) (and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))] [else (and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))])))

(define codieren (lambda (str key n) ...))

(define decodieren (lambda (ls key n) ...))

Wir ver- und entschlüsseln nun eine Zeichenkette:

(define klartext "Das ist ein brisanter Informatik-Text!") (define geheimcode (codieren klartext e N))

geheimcode

ausführen

(define neutext (decodieren geheimcode d N))

neutext

ausführen

Welche Auswirkungen haben Änderungen des privaten Schlüssels?
Wir wollen $d$ ausgeben, um anschließend damit zu experimentieren:

d

ausführen

(set! d 2772) (set! neutext (decodieren geheimcode d N)) neutext

ausführen

Zusammenfassung

• Mit der Idee der asymmetrischen Verschlüsselung entfällt beim RSA-Verfahren der unsichere Schlüsselaustausch.
• Die Verschlüsselung einzelner Zeichen entspricht einer monoalphabetischen Verschlüsselung und wäre durch Häufigkeitsanalysen sehr schnell zu "knacken". In der Praxis wird man deshalb die Codes mehrerer Zeichen vor der RSA-Verschlüsselung zusammenfassen.
  Beispiel:

  "Informatik" --> unverschlüsselte Codeliste: (9 40 32 41 44 39 27 46 35 37)
               --> modifizierte Codeliste    : (940 3241 4439 2746 3537)
  

  Implementation anzeigen

  Implementation verstecken
  

  (define codieren2 (lambda (str key n) (letrec ([string->list (lambda (str) (if (= (string-length str) 0) () (cons (char-pos (string-car str) alphabet) (string->list (string-cdr str)))))] [list->doublelist (lambda (ls) (cond [(null? ls) ()] [(null? (cdr ls)) ls] [else (cons (+ (* 100 (car ls)) (cadr ls)) (list->doublelist (cddr ls)))]))] [codieren (lambda (ls) (if (null? ls) () (cons (potmod (car ls) key n) (codieren (cdr ls)))))]) (codieren (list->doublelist (string->list str)))))) (define decodieren2 (lambda (ls key n) (letrec ([decodieren (lambda (ls) (if (null? ls) () (cons (potmod (car ls) key n) (decodieren (cdr ls)))))] [doublelist->list (lambda (ls) (if (null? ls) () (let ([n (quotient (car ls) 100)] [m (modulo (car ls) 100)]) (if (> n 0) (cons n (cons m (doublelist->list (cdr ls)))) (cons m (doublelist->list (cdr ls)))))))] [list->string (lambda (ls) (if (null? ls) "" (char-cons (pos-char (car ls) alphabet) (list->string (cdr ls)))))]) (list->string (doublelist->list (decodieren ls))))))

  (define klartext "Informatik") (define geheimcode (codieren2 klartext e N))

  geheimcode

  ausführen

  (define neutext (decodieren2 geheimcode d N))

  neutext

  ausführen

  Test des privaten Schlüssels:

  d

  ausführen

  (set! d 2772) (set! neutext (decodieren2 geheimcode d N)) neutext

  ausführen

• Der RSA-Algorithmus gilt als sehr sicher, wenn große Primzahlen verwendet werden. Es gibt aber nach wie vor intensive Bemühungen, das Produkt sehr großer Primzahlen wieder effizient zu faktorisieren (vgl. Primfaktorzerlegung).
• Das RSA-Verfahren wird heute in der Regel mit symmetrischen Verschlüsselungsverfahren kombiniert. Dabei wird ein Schlüssel für eine symmetrische Verschlüsselung generiert, der dann per RSA-Algorithmus verschlüsselt und zusammen mit der Nachricht übertragen wird.

Zurück zu ausgewählten Algorithmen der Kryptologie.