Grundlagen der funktionsorientierten Programmierung mit SCHEME/Das RSA-Verfahren
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
[[Datei:Rivest_Shamir_Adleman.jpg|miniatur|Ron Rivest, Adi Shamir, Leonard Adleman, 2003]]
Das RSA-Verfahren 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 />
Es nutzt 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="4cb0c69511681">
(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)
(letrec
([mod
(lambda (x y)
(if (> (modulo y 2) 0)
(cons x y)
(mod (modulo (sqr x) n) (quotient y 2))))]
[pot
(lambda (x y erg)
(if (= y 0)
erg
(let ([p (mod x y)])
(pot (car p)
(- (cdr p) 1)
(modulo (* erg (car p)) n)))))])
(pot x y 1))))
(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="4bc32617d90d1">
(define klartext "Das ist ein brisanter Informatik-Text!")
</code>
<eval id="4bc32617da071">
(define geheimcode (codieren klartext e N))
geheimcode
</eval>
<eval id="4bc32617db010">
(define neutext (decodieren geheimcode d N))
neutext
</eval>
Welche Auswirkungen haben Änderungen des privaten Schlüssels?<br />
Wir wollen <math>d</math> ausgeben, um anschließend damit zu experimentieren:
<eval id="4bc32617dbfb6">
d
</eval>
<eval id="4bc32617dcf50">
(set! d 2772)
(set! neutext (decodieren geheimcode d N))
neutext
</eval>
== 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 mehrere 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>
</li>
<li>
Der RSA-Algorithmus gilt als sehr sicher, wenn große Primzahlen verwendet werden.
Es gibt aber nach wie vor intensive Bemühungen, große Primzahlen 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]].