Zahlentheoretische Grundlagen der Kryptografie

Das multiplikativ inverse Element a^-1 eines Elements a in der Gruppe ℤ_n* ist das eindeutig bestimmte Element, für das gilt

a^-1· a  =  a · a^-1  =  1

wobei 1 das neutrale Element der Gruppe ist.

Beispielsweise ist 5 das inverse Element zu 3 in der Gruppe ℤ₁₄*. Denn in ℤ gilt 5 · 3  ≡  15  ≡  1 (mod 14), und in ℤ₁₄* gilt damit 5 · 3 = 1.

Berechnung des multiplikativ inversen Elements modulo n

Das inverse Element eines Elements a ∈ ℤ_n* lässt sich mit Hilfe des erweiterten euklidischen Algorithmus berechnen. Eine andere Möglichkeit besteht darin, das inverse Element durch modulare Exponentiation auf Grundlage des Satzes von Euler zu berechnen.

Und für den sehr speziellen Fall, dass n eine Zweierpotenz ist, gibt es noch eine weitere, superschnelle Alternative.

Berechnung mit dem erweiterten euklidischen Algorithmus

Der erweiterte euklidische Algorithmus berechnet für zwei Zahlen a, b ∈ ℕ den größten gemeinsamen Teiler ggt(a, b) sowie die Darstellung des ggt als ganzzahlige Linearkombination von a und b:

ggt(a, b) = u·a + v·b   mit  u, v ∈ ℤ.

Die multiplikative Gruppe ℤ_n* besteht aus den Elementen von ℤ_n, die teilerfremd zu n sind. Für jedes a ∈ ℤ_n* gilt dann

ggt(a, n) = 1

und die 1 lässt sich nach dem Lemma von Bézout als ganzzahlige Linearkombination von a und b darstellen:

1 = u·a + v·n.

Modulo n gerechnet ergibt sich

1   ≡   u·a + v·n   ≡   u·a   (mod n).

Multiplikation mit a^-1 ergibt

a^-1   ≡   u   (mod n).

Damit ist u mod n das inverse Element von a in ℤ_n*.

Berechnung durch modulare Exponentiation

Nach dem Satz von Euler gilt für jedes Element a ∈ ℤ_n*

a^φ(n) mod n  =  1

Multiplikation mit a^-1 ergibt

a^{φ(n) – 1} mod n  =  a^-1

Als Spezialfall ergibt sich für Primzahlen p, für die ja φ(p) = p-1 gilt:

a ^p – 2 mod p  =  a^-1

Die Berechnung des multiplikativ inversen Elements durch modulare Exponentiation ist zwar vom Konzept her einfacher als die Berechnung mithilfe des erweiterten euklidischen Algorithmus, aber sie ist etwas langsamer. Außerdem ist die Kenntnis von φ(n) und damit die Kenntnis der Primfaktorzerlegung von n erforderlich.

Berechnung für n Zweierpotenz

Wenn der Modul n eine Zweierpotenz ist, lässt sich das multiplikativ inverse Element sehr schnell berechnen – nicht wie bei den beiden vorgenannten Verfahren mit der Zeitkomplexität Θ(log(n)), sondern mit der Zeitkomplexität Θ(log(log(n))). Das Verfahren beruht auf einer zahlentheoretischen Methode, die als Hensel-Liftung bekannt ist. Das multiplikativ inverse Element modulo einer Zweierpotenz wird beispielsweise bei der Montgomery-Multiplikation gebraucht.

Berechnung der Schlüssel e und d für das RSA-Verfahren

Für die Schlüssel e und d des RSA-Verfahrens muss gelten

e·d mod φ(n) = 1,

d.h. e und d sind zueinander inverse Elemente in der Gruppe ℤ_φ(n)*.

Die Zahl e wird beliebig gewählt, sie muss nur in ℤ_φ(n)* liegen, d.h. es muss gelten

ggt(e, φ(n)) = 1.

Aus naheliegenden Gründen sollte allerdings nicht e = 1 und auch nicht e = φ(n)-1 gewählt werden.

Das zu e inverse Element d lässt sich am besten mit der ersten der oben angegebenen Methoden berechnen, denn für das RSA-Verfahren wird das inverse Element in der Gruppe ℤ_φ(n)* und nicht in der Gruppe ℤ_n* gebraucht, und φ(φ(n)), also die Primfaktorzerlegung von (p-1)·(q-1), ist im Allgemeinen nicht bekannt.

Implementierung

Die folgende Python-Funktion modinverse berechnet das multiplikativ inverse Element a^-1 eines Elements a in einer Gruppe ℤ_n* (n ist hier ein beliebiges n, nicht das n des RSA-Verfahrens). Es ist darauf zu achten, dass a auch tatsächlich ein Element von ℤ_n* ist, d.h. dass ggt(a, n) = 1 gilt. Die Funktion extgcd ist eine Implementierung des erweiterten euklidischen Algorithmus.

Eine entsprechende Implementation in der funktionalen Programmiersprache Haskell ist die folgende: