Zahlentheoretische Grundlagen der Kryptografie

Multiplikativ inverses Element modulo n

 aufwärts

Das multi­plikativ 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.

Beispiels­weise 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.

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 Linear­kombination von a und b:

ggt(a, b) = u·a + v·b   mit  u, v Element ganze Zahlen.

Die multi­plikative 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 Linear­kombination 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).

Multi­plikation 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

Multi­plikation mit a-1 ergibt

aφ(n) – 1 mod n  =  a-1

 

Als Spezialfall ergibt sich für Primzahlen p

a p – 2 mod p  =  a-1

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

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 nahe­liegenden 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 Primfaktor­zerlegung von (p-1)·(q-1), ist im allgemeinen nicht bekannt.

Implementierung

Die folgende Python-Funktion modinverse berechnet das multi­plikativ 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 ent­sprechende Implementation in der funktionalen Programmier­sprache 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   ©   Created: 29.04.2002   Updated: 28.02.2017
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