Zahlentheoretische Grundlagen der Kryptografie

Multiplikativ inverses Element modulo n

 aufwärts

Das multiplikativ inverse Element a-1 eines Elements a in der Gruppe ganze Zahlenn* 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 ganze Zahlen14*. Denn in ganze Zahlen gilt 5 · 3  kongruent  15  kongruent  1 (mod 14), und in ganze Zahlen14* gilt damit 5 · 3 = 1.

Berechnung des multiplikativ inversen Elements modulo n

Das inverse Element eines Elements a Element ganze Zahlenn* 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 superschnelle Alternative.

Berechnung mit dem erweiterten euklidischen Algorithmus

Der erweiterte euklidische Algorithmus berechnet für zwei Zahlen a, b Element natürliche Zahlen 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 Element ganze Zahlen.

Die multiplikative Gruppe ganze Zahlenn* besteht aus den Elementen von ganze Zahlenn, die teilerfremd zu n sind. Für jedes a Element ganze Zahlenn* 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   kongruent   u·a + v·n   kongruent   u·a   (mod n).

Multiplikation mit a-1 ergibt

a-1   kongruent   u   (mod n).

Damit ist u mod n das inverse Element von a in ganze Zahlenn*.

Berechnung durch modulare Exponentiation

Nach dem Satz von Euler gilt für jedes Element a Element ganze Zahlenn*

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 ganze Zahlenφ(n)*.

Die Zahl e wird beliebig gewählt, sie muss nur in ganze Zahlenφ(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 ganze Zahlenφ(n)* und nicht in der Gruppe ganze Zahlenn* 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 ganze Zahlenn* (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 ganze Zahlenn* ist, d.h. dass ggt(a, n) = 1 gilt. Die Funktion extgcd ist eine Implementierung des erweiterten euklidischen Algorithmus.

# berechnet das multiplikativ inverse Element von a modulo n
def modinverse(a, n):
    g, u, v=extgcd(a, n)
    return u%n

 

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

-- berechnet das multiplikativ inverse Element von a modulo n
modinverse :: Integer -> Integer -> Integer
modinverse a n = u `mod` n
        where (g, u, v) = extgcd a n

 

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 29.04.2002   Updated: 18.10.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik