RSA
RSA ist ein asymmetrisches Verschlüsselungsverfahren. Es ist nach den Initialen der Nachnamen seiner Erfinder Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt.
Asymmetrische Verschlüsselungsverfahren haben zwei Schlüssel: einen öffentlichen Schlüssel, den der Sender zum Verschlüsseln der Nachricht verwendet und einen privaten Schlüssel, mit dem der Empfänger die Nachricht entschlüsselt.
Der öffentliche Schlüssel besteht aus zwei natürlichen Zahlen n und e.
(defstruct rsa-public-key (e n)
(and
(integer? e)
(integer? n)
(> e 0)
(> n e)))
Der private Schlüssel besteht aus zwei natürlichen Zahlen n und d, wobei d im Vergleich zu n eine gewisse Bitlänge besitzen muss.
(defstruct rsa-private-key (d n)
(and
(integer? d)
(integer? n)
(> d 0)
(> (length d) (/ (length n) 3))))
Die Methode create-rsa-key-pair erzeugt ein Paar aus einem privaten und einem zugehörigen öffentlichen Schlüssel. Eingabeparameter ist die Bitlänge der Zahl n.
Im ersten Schritt werden zwei zufällige Primzahlen p und q erzeugt, deren Produkt die gewünschte Bitlänge hat. Dabei wird darauf geachtet, dass sich p und q signifikant in ihrer Bitlänge unterscheiden.
(defmethod create-rsa-key-pair (bit-count)
(and
(integer? bit-count)
(>= bit-count 512))
(let
((half-bit-count (ash bit-count -1)))
(create-rsa-key-pair
(random-prime (power-of-2 (- half-bit-count 64)))
(random-prime (power-of-2 (+ half-bit-count 63))))))
(defproc power-of-2 (bit-count)
(ash 1 bit-count))
(defproc random-prime (limit)
(let
((r (+ limit (random (ash limit -2)))))
(if
(prime? r)
r
(random-prime limit))))
Das Produkt n von p und q entspricht den Instanzvariablen n von privatem und öffentlichem Schlüssel. Die Hilfsgröße z ist das kleinste gemeinsame Vielfache von p - 1 und q - 1. Die Instanzvariable e des öffentlichen Schlüssels bekommt den Wert 65537. Dabei wird sichergestellt, dass e und z teilerfremd sind. Die Instanzvariable d des privaten Schlüssels ist das multiplikative Inverse von e modulo z.
(defmethod create-rsa-key-pair (p q)
(and
(prime? p)
(prime? q))
(let
((n (* p q))
(z (lcm (- p 1) (- q 1))))
(let
((e (choose-public-exponent z)))
(list
(new rsa-private-key (modinv e z) n)
(new rsa-public-key e n)))))
(defproc lcm (x y)
(/ (* x y) (gcd x y)))
(defproc choose-public-exponent (z)
(let
((e 65537))
(if
(= (gcd z e) 1)
e
(throw (quote error) "public exponent not acceptable"))))
Eine Nachricht m wird verschlüsselt, indem sie zunächst encodiert und dann modulo der Zahl n mit dem Exponenten e potenziert wird.
(defmethod encrypt ((key rsa-public-key) m)
t
(exptmod
(encode (octet-length (. key n)) m)
(. key e)
(. key n)))
Beim Encodieren werden mehrere Bytes vor der eigentlichen Nachricht m hinzugefügt, so dass die Sequenz 0x00 || 0x02 || r || 0x00 || m entsteht. Dabei sind r mehrere zufällige Bytes, die nicht den Wert 0 haben. Die Gesamtlänge der Sequenz entspricht der Länge der Zahl n.
(defproc encode (d m)
(let
((o (octet-length m)))
(if
(> (- d o) 10)
(logior
(ash 2 (* 8 (- d 2)))
(ash (non-zero-octets (- d 3 o)) (* 8 (+ o 1)))
m)
(throw (quote error) "message too long"))))
(defproc octet-length (n)
(let
((b (integer-length n)))
(if
(= (logand b 7) 0)
(ash b -3)
(+ (ash b -3) 1))))
(defproc non-zero-octets (o)
(if
(>= o 1)
(logior
(ash (non-zero-octets (- o 1)) 8)
(+ (random 254) 1))
0))
Beim Entschlüsseln wird zunächst modulo n mit dem Exponenten d potenziert und dann werden die beim Encodieren hinzugefügten Bytes abgestreift.
(defmethod decrypt ((key rsa-private-key) cipher)
t
(decode
(octet-length (. key n))
(exptmod
cipher
(. key d)
(. key n))))
(defproc decode (s m)
(if
(and
(= (get-octet s 0 m) 0)
(= (get-octet s 1 m) 2))
(skip-random-octets s 2 m)
(throw (quote error) "does not start with 0x00 || 0x02")))
(defproc mask-octets (o)
(- (ash 1 (* 8 o)) 1))
(defproc get-octet (s i m)
(logand
(ash m (* -8 (- s i 1)))
255))
(defproc skip-random-octets (s i m)
(if
(= (get-octet s i m) 0)
(logand
(mask-octets (- s i))
m)
(skip-random-octets s (+ i 1) m)))
Die Sicherheit des Verfahrens beruht darauf, dass n nicht in seine Faktoren p und q zerlegt werden kann, um im zweiten Schritt aus e und z den privaten Exponenten d zu bestimmen. Dafür ist es wichtig, dass sich p und q in ihrer Größe deutlich unterscheiden. Sonst kann n recht einfach in Faktoren zerlegt werden.
Für die Sicherheit ist es ebenfalls wichtig, dass beim Encodieren genügend zufällige Bytes hinzugefügt werden.
Asymmetrische Verschlüsselungsverfahren haben zwei Schlüssel: einen öffentlichen Schlüssel, den der Sender zum Verschlüsseln der Nachricht verwendet und einen privaten Schlüssel, mit dem der Empfänger die Nachricht entschlüsselt.
Der öffentliche Schlüssel besteht aus zwei natürlichen Zahlen n und e.
(defstruct rsa-public-key (e n)
(and
(integer? e)
(integer? n)
(> e 0)
(> n e)))
Der private Schlüssel besteht aus zwei natürlichen Zahlen n und d, wobei d im Vergleich zu n eine gewisse Bitlänge besitzen muss.
(defstruct rsa-private-key (d n)
(and
(integer? d)
(integer? n)
(> d 0)
(> (length d) (/ (length n) 3))))
Die Methode create-rsa-key-pair erzeugt ein Paar aus einem privaten und einem zugehörigen öffentlichen Schlüssel. Eingabeparameter ist die Bitlänge der Zahl n.
Im ersten Schritt werden zwei zufällige Primzahlen p und q erzeugt, deren Produkt die gewünschte Bitlänge hat. Dabei wird darauf geachtet, dass sich p und q signifikant in ihrer Bitlänge unterscheiden.
(defmethod create-rsa-key-pair (bit-count)
(and
(integer? bit-count)
(>= bit-count 512))
(let
((half-bit-count (ash bit-count -1)))
(create-rsa-key-pair
(random-prime (power-of-2 (- half-bit-count 64)))
(random-prime (power-of-2 (+ half-bit-count 63))))))
(defproc power-of-2 (bit-count)
(ash 1 bit-count))
(defproc random-prime (limit)
(let
((r (+ limit (random (ash limit -2)))))
(if
(prime? r)
r
(random-prime limit))))
Das Produkt n von p und q entspricht den Instanzvariablen n von privatem und öffentlichem Schlüssel. Die Hilfsgröße z ist das kleinste gemeinsame Vielfache von p - 1 und q - 1. Die Instanzvariable e des öffentlichen Schlüssels bekommt den Wert 65537. Dabei wird sichergestellt, dass e und z teilerfremd sind. Die Instanzvariable d des privaten Schlüssels ist das multiplikative Inverse von e modulo z.
(defmethod create-rsa-key-pair (p q)
(and
(prime? p)
(prime? q))
(let
((n (* p q))
(z (lcm (- p 1) (- q 1))))
(let
((e (choose-public-exponent z)))
(list
(new rsa-private-key (modinv e z) n)
(new rsa-public-key e n)))))
(defproc lcm (x y)
(/ (* x y) (gcd x y)))
(defproc choose-public-exponent (z)
(let
((e 65537))
(if
(= (gcd z e) 1)
e
(throw (quote error) "public exponent not acceptable"))))
Eine Nachricht m wird verschlüsselt, indem sie zunächst encodiert und dann modulo der Zahl n mit dem Exponenten e potenziert wird.
(defmethod encrypt ((key rsa-public-key) m)
t
(exptmod
(encode (octet-length (. key n)) m)
(. key e)
(. key n)))
Beim Encodieren werden mehrere Bytes vor der eigentlichen Nachricht m hinzugefügt, so dass die Sequenz 0x00 || 0x02 || r || 0x00 || m entsteht. Dabei sind r mehrere zufällige Bytes, die nicht den Wert 0 haben. Die Gesamtlänge der Sequenz entspricht der Länge der Zahl n.
(defproc encode (d m)
(let
((o (octet-length m)))
(if
(> (- d o) 10)
(logior
(ash 2 (* 8 (- d 2)))
(ash (non-zero-octets (- d 3 o)) (* 8 (+ o 1)))
m)
(throw (quote error) "message too long"))))
(defproc octet-length (n)
(let
((b (integer-length n)))
(if
(= (logand b 7) 0)
(ash b -3)
(+ (ash b -3) 1))))
(defproc non-zero-octets (o)
(if
(>= o 1)
(logior
(ash (non-zero-octets (- o 1)) 8)
(+ (random 254) 1))
0))
Beim Entschlüsseln wird zunächst modulo n mit dem Exponenten d potenziert und dann werden die beim Encodieren hinzugefügten Bytes abgestreift.
(defmethod decrypt ((key rsa-private-key) cipher)
t
(decode
(octet-length (. key n))
(exptmod
cipher
(. key d)
(. key n))))
(defproc decode (s m)
(if
(and
(= (get-octet s 0 m) 0)
(= (get-octet s 1 m) 2))
(skip-random-octets s 2 m)
(throw (quote error) "does not start with 0x00 || 0x02")))
(defproc mask-octets (o)
(- (ash 1 (* 8 o)) 1))
(defproc get-octet (s i m)
(logand
(ash m (* -8 (- s i 1)))
255))
(defproc skip-random-octets (s i m)
(if
(= (get-octet s i m) 0)
(logand
(mask-octets (- s i))
m)
(skip-random-octets s (+ i 1) m)))
Die Sicherheit des Verfahrens beruht darauf, dass n nicht in seine Faktoren p und q zerlegt werden kann, um im zweiten Schritt aus e und z den privaten Exponenten d zu bestimmen. Dafür ist es wichtig, dass sich p und q in ihrer Größe deutlich unterscheiden. Sonst kann n recht einfach in Faktoren zerlegt werden.
Für die Sicherheit ist es ebenfalls wichtig, dass beim Encodieren genügend zufällige Bytes hinzugefügt werden.