Die 2. Lösung der Gleichung e*d+k*Phi(N)=1

Neue Frage »

loosm Auf diesen Beitrag antworten »
Die 2. Lösung der Gleichung e*d+k*Phi(N)=1
Weil es auch mit dem Thema: Überraschungen bei der Schlüsselerstellung beim RSA -Verfahren zu tun hat, will ich erzählen, wie ich überhaupt auf das Thema gestoßen bin. Ich hatte ein Buch geschenkt bekommen:
Mathematik, die faszinierende Welt der Zahlen von Bertram Maurer
Die Art, wie er in diesem Buch die Phi Funktion erklärt hatte, war wirklich gut, und hat deshalb mein Interesse an dem Thema geweckt. Ich freue mich immer, wenn mir in der Mathematik Beispiele gezeigt werden, wo komplexe Zusammenhänge durch Verwendung von kleinen Zahlen besser verständlich gemacht werden. Falls irgendjemand, der diesen Text liest, vorhat, Mathematiklehrer zu werden, sollte er es seinen Schülern auch bieten, dass er komplexe Zusammenhänge durch Verwendung von kleinen Zahlen besser verständlich macht.

Hier ist diese Erklärung der Phi Funktion aus dem Buch:
ist 1, denn nur 1 ist kleiner als 2 und teilerfremd zu 2
ist 4, denn 1,3,5,7 sind kleiner als 8 und teilerfremd zu 8
ist 10 denn 1,2,3,4,5,6,7,8,9,10 sind kleiner als 11 und teilerfremd zu 11
Man kann jetzt leicht nachvollziehen das für eine Primzahl p gilt = p-1
Mit ein bisschen Mühe sogar, dass für 2 Primzahlen p und q und die Formel:
= (p-1) mal (q-1) gilt.
Etwas weniger naheliegend ist der Satz von Euler, der in der Kryptologie eine prominente Rolle spielt. Er sagt, dass die Potenz bei Division durch N den Rest 1 ergibt, wenn N und B teilerfremde Zahlen sind. Vielleicht hilft ein Zahlenbeispiel: Nehmen wir B = 11 und N= 8, dann ist gleich 4, und man erhält: = 14641 Da sich 14640 durch 8 teilen lässt, 1830 mal 8 = 14640, bleibt bei der Division von 14641 durch 8 wie erwartet der Rest 1. Möglicherweise hat das Zahlenbeispiel nichts klarer gemacht, dann wollen wir wenigstens noch eine einigermaßen eindrucksvolle Formel nachreichen. mod N = 1

Das Zahlenbeispiel für die RSA-Verschlüsselung aus dem Buch lautet:
Üblicherweise verwendet man 600-stellige Primzahlen. Hier begnügen wir uns mit zweistelligen:
p=13 und q = 17 n ist damit 221. Dann gilt = = (p-1) mal (q-1) = 192
Wir wählen nun für k z.B den Wert 8 und erhalten für k mal +1 den Wert 8 mal 192 + 1 = 1537 diese Zahl kann man in 53 mal 29 aufspalten.
Zum Verschlüsseln verwenden wir nun 221 und 53 und zum entschlüsseln 221 und 29
Ist z.B Klar 75 dann ist cod = mod 221 = 147
und mit = 75 erhält man wieder den Klartext.

Dieses Beispiel aus dem Buch, hat mich wieder animiert, ein kleines Programm zu schreiben, bei dem man 2 Primzahlen eingibt und dann in einer Schleife alle K von 5 bis 9 ausprobiert werden, um zu sehen, welche Schlüsselpaare bei Verwendung der verschiedenen K entstehen. Wenn ich in dieses Programm die Primzahlen 13 und 17 eingebe, wird der folgende Output erzeugt:

= (a-1) mal (b-1) = (13-1) mal (17 -1) = 192

192 mal 5 + 1 = 961 kann auch zerlegt werden in:
31 mal 31

192 mal 6 + 1 = 1153 kann nicht zerlegt werden

192 mal 7 + 1 = 1345 kann auch zerlegt werden in:
5 mal 269

192 mal 8 + 1 = 1537 kann auch zerlegt werden in:
29 mal 53

192 mal 9 + 1 = 1729 kann auch zerlegt werden in:
19 mal 91
13 mal 133
7 mal 247

Wenn man bei der Erzeugung der Schlüsselpaare solche Art von Überraschung nicht erleben will, sollte man nicht irgendein K wählen , sondern ein e wählen, welches die Bedingungen erfüllt : 1< e < und teilerfremd zu dann würde, in der Liste der 64 möglichen e welche diese Bedingungen erfüllen auch die 53 erscheinen.
Wenn man diese 53 in die Gleichung e mal d + k mal = 1 eingesetzt hätte :
d mal 53 - k mal 192 = 1 und mit Hilfe des euklidischen Algorithmus gelöst hätte, dann könnte man auch die Lösung : 53 mal 29 - 8 mal 192 = 1 finden können.
In diesem Fall wäre das K negativ ( -8) Was aber egal wäre, weil es für die weitere Schlüsselerstellung nicht gebraucht werden würde. 29 mal 53 - 8-mal 192 = 1 ist aber nicht die einzige Lösung der Gleichung d mal 53 - k mal 192 = 1 die andere Lösung lautet: -163 mal 53 + 45 mal 192 = 1

Würde man diese andere Lösung der Gleichung benutzen dann wäre d = -163 und k = +45

Es würde sich die Frage stellen:

Könnte man dieses negative d innerhalb der Formel m= mod N einsetzen? Oder

Kann man mod 221 berechnen?
Laut dem Link: [URL]https://de.wikipedia.org/wiki/Division_mit_Rest#Modulo [/URL] ist Modulo eine mathematische Funktion, die den Rest aus einer Division zweier natürlicher Zahlen benennt. ist keine natürliche Zahl. Außerdem steht dort, dass die Division mit Rest auch für Polynome definiert ist. Ich weiß nicht, ob als Polynom darstellbar ist. Ein Programm für Mod Berechnungen : ModularPower von dem Link:[URL] https://de.wikipedia.org/wiki/RSA-Kryptosystem [/URL] rechnet bei der Eingabe eines negativen Exponenten als Ergebnis immer eine 1 aus. Wenn ich mod 221 berechnen wollte, ergäbe sich nach meiner Logik die folgende Rechnung: Der Rest von geteilt durch 221 = weil = (0 mal 221) + Wäre diese Berechnung richtig oder wäre sie, weil keine natürliche Zahl ist unzulässig?

Ich behaupte das der erweiterte euklidischen Algorithmus nicht der Algorithmus ist, mit dem immer die Lösung der Gleichung e mal d + k mal Phi(N) = 1 gefunden werden kann, bei der das d positiv ist. Wie komme ich darauf ? Es liegt an der Art wie man damit beginnt den erweiterten euklidischen Algorithmus auszuführen.

Im Internet kann man sich auf der Mathe Seite von Arndt Brünner die Berechnung des erweiterten
euklidischen Algorithmus sehr anschaulich vorführen.

Auf dieser Webseite wird bei der Eingabe von a = 16380 und b = 43
die Berechnung des des erweiterten euklidischen Algorithmus gestartet durch die Anfangsgleichung :

16380 = 380·43 + 40

Was dazu führt das man am Ende die Gleichung

die Gleichung 14·16380 - 5333·43 = 1 ausgerechnet bekommt.


Auf dieser Webseite wird bei der Eingabe von a = 43 und b = 16380
die Berechnung des des erweiterten euklidischen Algorithmus gestartet durch die Anfangsgleichung :

43 = 0·16380 + 43

Was dazu führt das man am Ende die Gleichung

die Gleichung -5333·43 + 14·16380 ausgerechnet bekommt.



Bei Eingabe dieser beiden Zahlen ist es nicht möglich 11047 mal 43 -29 mal 16380 = 1 als Lösung der Gleichung : 43 mal d + k mal 16380 = 1 zu finden.

Noch ein Beispiel :

Auf dieser Webseite wird bei der Eingabe von a = 8 und b = 7
die Berechnung des des erweiterten euklidischen Algorithmus gestartet durch die Anfangsgleichung :

8 = 1·7 + 1

Was dazu führt das man am Ende die Gleichung

die Gleichung 1·8 - 1·7 = 1 ausgerechnet bekommt.


Auf dieser Webseite wird bei der Eingabe von a = 7 und b = 8
die Berechnung des des erweiterten euklidischen Algorithmus gestartet durch die Anfangsgleichung :

7 = 0·8 + 7

Was dazu führt das man am Ende die Gleichung

die Gleichung -1·7 + 1·8 = 1 ausgerechnet bekommt.


Bei Eingabe dieser beiden Zahlen ist es nicht möglich 7 mal 7 – 6 mal 8 = 1 als Lösung der Gleichung :
7 mal d + k mal 8 = 1 zu finden.

Auch die Funktion getPrivateKey. von dem Link:[URL] https://de.wikipedia.org/wiki/RSA-Kryptosystem [/URL]
findet nicht immer für die Gleichung e mal d + k mal Phi(N) = 1 die Lösung, bei der das d positiv ist. Manchmal findet es die andere Lösung und gibt dabei das unbrauchbare d manchmal ohne negatives Vorzeichen aus. Manchmal findet es die Lösung, bei der das d positiv ist und verdreht einfach das Vorzeichen des d ins Negative.

Die Funktion getPrivateKey und die Mathe Seite von Arndt Brünner auf der man sich
die Berechnung des erweiterten die Berechnung des erweiterte euklidischen Algorithmus vorführen kann haben 2 Gemeinsamkeiten :

1. Sie können beide sehr schnell rechnen.

2. Es ist Zufall ob bei der Eingabe eines e und eine Gleichung mit einem d gefunden wird welches, wenn es in die Gleichung
m= mod N eingesetzt werden würde, den richtigen Klartext anzeigen würde.

Die Mathe Seite von Arndt Brünner für den erweiterten euklidischen Algorithmus verdreht aber keine Vorzeichen. Arndt Brünner hat bei der Programmierung dieser Seite nichts falsch gemacht.

Wie ist es mir aufgefallen, dass es für die Gleichung e mal d + k mal Phi(N) = 1 eine brauchbare und eine unbrauchbare Lösung gibt ? Ich habe selber ein kleines Programm geschrieben, welches den Zweck hat die Schlüsselerstellung beim RSA verfahren vorzuführen. Mein Programm zeigt standardmäßig die brauchbare Lösung und wenn man will zusätzlich die unbrauchbare Lösung der Gleichung e mal d + k mal Phi(N) = 1.
Mann kann mir in Bezug auf das Programm vorwerfen, dass es sicherlich noch besser hätte programmiert werden können. Aber man kann mir nicht vorwerfen, das mein Programm falsch rechnet, in Gegensatz zur der Funktion getPrivateKey von dem Link:[URL] https://de.wikipedia.org/wiki/RSA-Kryptosystem [/URL]
Wenn man sich mein Programm unter dem Link :[URL] https://www.vb-paradise.de/index.php/Thr...391#post1176391 [/URL]
zu eigen machen will, sollte man die Version nehmen, bei welcher ich im Projektmappen Explorer unter
Compile /Allgemein die Option Strikt von Off auf On umgestellt hatte. Diese Version kann schneller rechnen als die erste Version.
loosm Auf diesen Beitrag antworten »

Ich möchte meinen Beitrag zum RSA Verfahren noch um den Spezialfall ergänzen, wenn bestimmte Zahlen so ausgewählt werden, dass keine Verschlüsselung stattfindet.

Der erste Fall bezieht sich auf das Beispiel aus dem Buch von Betrtam Mauer :
p=13 und q = 17 n ist damit 221. Dann gilt
= (a-1) mal (b-1) = (13-1) mal (17 -1) = 192

Wenn man für k den Wert 5 auswählt und für k mal +1 den Wert 5 mal 192 + 1 = 961 erhält, diese Zahl kann man in 31 mal 31 aufspalten.

In diesem Fall wäre bezogen auf die Gleichung e*d+k* =1

Sowohl das e= 31 als auch das d = 31 was zur Folge hätte, dass keine Verschlüsselung stattfindet.

Das eine Primzahl in 2 gleich große Zahlen zerlegt wird kann einem aber auch dann passieren wenn man zur Schlüsselerstellung ein e wählt , welches die Bedingungen erfüllt : 1< e < und teilerfremd zu

Das erste Beispiel wäre p = 7 und q = 11

= (a-1) mal (b-1) = (7-1) mal (11 -1) = 60

Zu diesem Beispiel könnte man 15 mögliche e auswählen : 7,11, 13,17,19,23,29,31,37,41,43,47,49,43,59

wenn man als e die 31 auswählen würde wäre bezogen auf die Gleichung e*d+k* =1
31 mal 31 minus 16 mal 60 = 1 eine Lösung

Auch in diesem Fall wäre sowohl das e= 31 als auch das d = 31 was zur Folge hätte, dass keine Verschlüsselung stattfindet.

Noch ein Beispiel : p = 7 und q = 5

Dann gilt = mal q) = (p-1) mal (q-1) = 24

Zu diesem Beispiel könnte man 7 mögliche e auswählen : 5,7,11,13,17,19,23

wenn man als e die 13 auswählen würde wäre bezogen auf die Gleichung e*d+k* =1
13 mal 13 minus 7 mal 24 = 1 eine Lösung
In diesem Fall wäre sowohl das e= 13 als auch das d = 13 was zur Folge hätte, dass keine Verschlüsselung stattfindet.

Dann gibt es aber noch andere Fälle in dem sich dass e vom d unterscheidet aber trotzdem keine Verschlüsselung stattfindet.
Das Beispiel hierzu wäre p=7 und q = 13

Zu diesem Beispiel könnte man 23 mögliche e auswählen : 5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71

wenn man als e die 25 auswählen würde wäre bezogen auf die Gleichung e*d+k* =1
49 mal 25 minus 17 mal 72 = 1 eine Lösung

N wäre in diesem Fall 7 mal 13 = 91

Es gäbe bei der Erstellung des Chifrats im Bereich für den Klartext von -90 bis + 90 nur Gleichungen vom Typ
= Klartext obwohl es eigentlich ein Chiffrat sein soll.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »