Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das RSA-Verfahren
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
[[Datei:Rivest_Shamir_Adleman.jpg|miniatur|hochkant=1.5|Ron Rivest, Adi Shamir, Leonard Adleman, 2003]]
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.<br />
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.<br />
Man nutzt dazu die Tatsache, dass es praktisch unmöglich ist, eine Primfaktorenzerlegung sehr großer Zahlen (ca. 200 Stellen und mehr) in einem vertretbaren (Zeit-)Aufwand vorzunehmen.
== RSA-Algorithmus ==
<ol>
<li>
Lege zwei (große) Primzahlen <math>p</math> und <math>q</math> fest mit <math>p \neq q</math>.<br />
Bilde das Produkt <math>N = p \cdot q</math>.<br />
Suche eine weitere Zahl <math>e</math>, für die gilt:
* <math>e</math> ist Primzahl und größer als <math>p</math> und <math>q</math> <u>oder</u>
* <math>e</math> ist teilerfremd zu <math>(p-1) \cdot (q-1)</math>.
Die Zahlen <math>e</math> und <math>N</math> bilden den ''öffentlichen Schlüssel''.
</li>
<li>
Ermittle den ''privaten Schlüssel'' <math>d</math> mit:
* <math>d \le (p-1) \cdot (q-1)</math> <u>und</u>
* <math>(d \cdot e) \bmod [(p-1) \cdot (q-1)] = 1</math>
</li>
<li>
Ein Klartext-Zeichen mit dem Code <math>c</math> wird mit
<blockquote><math>c^e \bmod N = m</math></blockquote>
zu <math>m</math> ''verschlüsselt''.
</li>
<li>
Der verschlüsselte Code <math>m</math> wird mit
<blockquote><math>m^d \bmod N = c</math></blockquote>
zum Code <math>c</math> des Klartext-Zeichens ''entschlüsselt''.
</li>
</ol>
== 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:
<code id="4cb0c6951151c" hidden>
(define sqr
(lambda (x)
(* x x)))
;Prozeduren mit Strings
(require-extension (srfi 13))
(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 (modulo (- 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))])))
</code>
<code id="4f9071c2c333b">
(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))))
</code>
Eine geringe Erweiterung der Prozedur <tt>pos-char</tt> soll die späteren Implementationen erleichtern:
<code id="4c836f2794ceb">
(set! pos-char
(lambda (n str)
(if (= n 0)
platzhalter
(string-ref str (modulo (- n 1) (string-length str))))))
</code>
Nun können wir öffentliche und private Schlüssel bilden und diese auf ihre Korrektheit überprüfen:
<code id="4bc41d6fbd86c">
(define p 97)
(define q 103)
(define N (* p q))
(define e (public-key p q))
(define d (private-key p q e))
</code>
<check>
(and (not (= p q)) (primzahl? p) (primzahl? q)
(= (ggt e (* (- p 1) (- q 1))) 1) (= (modulo (* e d) (* (- p 1) (- q 1))) 1))
</check>
Zum Ver- bzw. Entschlüsseln müssen wir nun die entsprechenden Prozeduren implementieren.<br />
Dazu bietet sich die sehr effiziente Prozedur <tt>potmod</tt> mit der folgenden Syntax an:
(potmod <x> <y> <n>) ; ... x<sup><small>y</small></sup> mod n
<code id="4bc41d6fbe80a" hidden>
(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)))])))
</code>
<code id="4bc41d6fbf7aa">
(define codieren
(lambda (str key n)
...))
</code>
<check>
(listequal? (codieren "Informatik" e n) (codieren-lsg "Informatik" e n))
</check>
<code id="4bc41d6fc074a">
(define decodieren
(lambda (ls key n)
...))
</code>
<check>
(equal? (decodieren '(9 40 32 41 44 39 27 46 35 37) d n)
(decodieren-lsg '(9 40 32 41 44 39 27 46 35 37) d n))
</check>
Wir ver- und entschlüsseln nun eine Zeichenkette:
<code id="4f2d73b140c80">
(define klartext "Das ist ein brisanter Informatik-Text!")
(define geheimcode (codieren klartext e N))
</code>
<run id="4f2d73b140e0a">
geheimcode
</run>
<code id="4f2d73b140d39">
(define neutext (decodieren geheimcode d N))
</code>
<run id="4f2d73b140e7e">
neutext
</run>
Welche Auswirkungen haben Änderungen des privaten Schlüssels?<br />
Wir wollen <math>d</math> ausgeben, um anschließend damit zu experimentieren:
<run id="4bc32617dbfb6">
d
</run>
<run id="4bc32617dcf50">
(set! d 2772)
(set! neutext (decodieren geheimcode d N))
neutext
</run>
== Zusammenfassung ==
<ul>
<li>
Mit der Idee der asymmetrischen Verschlüsselung entfällt beim RSA-Verfahren der unsichere Schlüsselaustausch.
</li>
<li>
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.<br />
'''Beispiel:'''
<pre>
"Informatik" --> unverschlüsselte Codeliste: (9 40 32 41 44 39 27 46 35 37)
--> modifizierte Codeliste : (940 3241 4439 2746 3537)
</pre>
<popup name="Implementation">
<code id="4f91e41747b36">
(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))))))
</code>
<code id="4f91e41747ba4">
(define klartext "Informatik")
(define geheimcode (codieren2 klartext e N))
</code>
<run id="4f91e36e046a2">
geheimcode
</run>
<code id="4f91e36e04571">
(define neutext (decodieren2 geheimcode d N))
</code>
<run id="4f91e36e0476f">
neutext
</run>
Test des privaten Schlüssels:
<run id="4f91e36e04808">
d
</run>
<run id="4f91e36e04899">
(set! d 2772)
(set! neutext (decodieren2 geheimcode d N))
neutext
</run>
</popup>
</li>
<li>
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.
</li>
<li>
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.
</li>
</ul>
Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Ausgewählte Algorithmen der Kryptologie|ausgewählten Algorithmen der Kryptologie]].