Nächste Seite: 100825/tex/sh092625.sh Aufwärts: 100825/tex Vorherige Seite: 100825/tex/quine3dnf100425.txt
(c) David Vajda
RSA-Uebung
10/04/25
auf Grundlage von:
https://www.mi.fu-berlin.de/inf/groups/ag-idm/teaching/Rechnersicherheit/RS4.pdf
klartext = [2, 87, 16, 41, 76, 65, 33, 91, 7, 32]
gesucht: p und q, Primzahlen
p = 5
q = 11
n = p*q = 5*11 = 55
phi (n) = (p-1)*(q-1) = 4 * 10 = 40
oeffentlicher schluessel wird gesucht, bezogen auf die gerade von
GPG dem verschluesselungsprogramm wird mit dem oeffentlichen schluessel,
mit dem zwar verschluesselt wird, der private generiert.
der vor allem deswegen privat ist, weil gpg so scheint es, das verschluesselungs
programm zwei primzahlen selber geheim haelt, die keiner kennt.
e = 7
also:
p = 5
q = 11
n = p*q = 5*11 = 55
phi (n) = (p-1)*(q-1) = 4 * 10 = 40
e = 7
die frage ist ehrlich gesagt nur warum ist d jetzt 23
dahinter liegt das eigentliche geheimniss...
das problem ist, dass ein produkt gefunden werden muss
was
7 * d = phi(n)
aber halt nicht ganz!
falsch, falsch, falsch, aber nicht ganz, prinzipiell richtig, nur
operatorschreibweise, schwierig zugegeben
mache drauf aufmerksam
10 = 1 mod 9
heisst, dass der rest von 10/9 = 1 ist
gleichzeitig ist aber auch
19 = 1 mod 9
28 = 1 mod 9
kurz, 1 mod 9 kann alles sein! muss man wissen, nicht alles, aber so
ziemlich jede 9. ganze zahl.
wozu ist diese schreibweise gut?
sie hat 2 vorteile
20 div 9 = 2 Rest 2
bedeutet, jetzt taucht der Quotient selber auf und nicht nur der Rest
allerdings noch etwas.
20 % 9 = 2
% ist das Zeichen in C zum Beispiel fuer Rest
20/9 = 2 (Division)
20%9 = 2 (Rest)
Der Intel Div Befehl neigt dazu, ein Register
fuer den quotienten und eines fuer den Rest zu nehmen
was es bei der uebersetzung der Programmiersprache C
bequem macht
% und / sind bereits in der CPU vorhanden. wenn es ein x86er ist
gut - aber -
20%9 = 2 hat einen nachteil
1 mod 9
kann eben alles sein
10 = 1 mod 9
19 = 1 mod 9
28 = 1 mod 9
...
aber auch umgekehrt:
1 mod 9 = 10
1 mod 9 = 19
1 mod 9 = 28
deswegen, gute schreibweise. und jetzt:
7 * d = phi(n)
ist vom prinzip her sehr richtig, mit einer ausnahme
7 * d = phi(n) + 1
ganz richtig ist auch das nicht, wegen folgender gleichung:
1 mod 9 = 10
1 mod 9 = 19
1 mod 9 = 28
gefordert ist:
7 * d = phi(n)*n + 1
wobei n eine ganze zahl sein muss
schoen koennte man meinen. dann ist alles gesagt, zwei argumentationen
und zwei dagegen
1.) argumentation dafuer:
7 * d = phi(n) + 1
ist ein spezialfall, er ist nicht ausgeschlossen
es ist durchaus erlaubt, aber es geht noch mehr
2.) argumentation dafuer
das ist nicht dieselbe wie (1) (1) geht davon aus,
dass es durchaus geht, (2) sagt, warum geht.
... wie auch immer
n = 1
7 * d = phi(n)*n + 1
7 * d = phi(n) + 1
1.) argumentation dagegen (vollkommen anders, 1 und 2 dagegen)
es ist kein einschraenkendes kriterium, eben wegen
1 dafuer.
wenn 1 dafuer ist, es ist aber nicht alles
alles mit
phi(n)*d = 1 mod 7
geht eben und nicht nur einiges.
2.) es gibt ein ausschliessendes kriterium
d: muss primzahl sein.
waehrend:
phi(n)*d = 1 mod 7
vieles moegliche beschreibt,
muss
d zwingend primzahl sein
...
also, jetzt
7 * d = n*40 + 1
wobei, n eine beliebige natuerliche zahl ist, groesser 0
angenommen n ist 4
7 * d = 4*40 + 1 = 161
7 * 23 = 140 + 21 = 161
ok!!
so, und jetzt am besten eine tabelle,
bcd kodiert, zum beispiel
werte wie
128^7 lassen sich nicht normal ausdruecken, im pc zwar schon
auch, wenn register nicht reichen, wegen speicherbereich
ich brauche keine mehr als 64/32/16 bit register, habe
speicherbereich
mmx/smd/sse
sind zwar von vorteil, fuer das schnelle wiederholte rechnen,
trotzdem, speicherbereich
das menschliche auge, kann aber auch am taschenrechner!
dem bildschirm inhalt nicht folgen:
Computer und Taschenrechner:
CPU
Speicher
Ein- und Ausgabe
Ausgabe: Sichtgeraet
das Sichtgeraet das Display am Taschenrechner ist zu klein
ok: deswegen:
es gibt einen trick
9^7
laesst sich gerade ausdruecken. jetzt bcd
koennen wir:
abcd...
nehmen wir an, das ist jetzt ASCII Code ueberhaupt sagen
wir mittelmaessig...
ich rede ja vom sichtgeraet aber es gibt beim PC sicher aufgaben
die zwar nicht wie das Sichtgeraet damit nicht klar kommen
generell: 64 bit register sind keine grenze. sie rechnen mit speicherbereichen
trotzdem: somit geht ganz viel?
ja, aber es gibt auch hier loesungen, die liegen dazwischen
fuer die veranschaulichung:
9^7 geht noch
und: das ist dann spaeter ein prinzip
tatsaechlich gibt es bcd zahlen, auch ohne darstellung als ziffer im dezimalsystem
fuer menschliches auge
nebenbei was ist ziffer
1.) ziffer: arabisch: 0, 1, 2, 3, ..., 9
2.) Abakus: aber auch das sind ziffern! sollten wir nicht vergesssen!
also: beim abakus haben sie pro zeile, 10 steinchen
aber eine ziffer sind nicht jeweils ein steinchen, sondern die zeile selber
bestehend aus linken und rechten steinchen
die anzahl der steinchen auf der rechten seite sind unsere ziffern
pro stelle in einer zahl
3.) BCD sind die ziffern von 0 .. 9
allerdings
binaer kodiert, das heisst nach wie vor nicht
0 .. 9
sondern
0000 ... 1001
ok
also, normal hex 4 bit, binaer kodiert
0000
0001
0010
0011
0100
0101
...
1111
und jetzt aber auch
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
das sind 10 ziffern, auch wenn sie aus 4 LOW and HIGH bestehen. ok
und deswegen:
angenommen wir haben ASCII
0x00 bis 0xff
dann, egal, ob wir bis 0xff kodieren, wir koennten auch
0d bis 255d kodieren und im computer so darstellen:
0010 0101 0101
ok, dann koennen wir bei diesem verschluesselungsverfahren, das verfahren
auf diese einzeln anwenden
2, 5, 5
ok.
und dann machen wir eine tabelle...
0^7 =
1^7 =
2^7 =
3^7 =
4^7 =
5^7 =
6^7 =
8^7 =
9^7 =
gefoerdert ist aber in wirklichkeit
n^7 = x mod 55
n = 0..9 (ganz oder natuerlich)
das machen wir schnell mit python 3. erst
n^7, fuer n=0..9
dann
n^7 = x mod 55, fuer n=0..9
# (c) David Vajda
# python 3 - n^7, fuer n=0..9
# ... oder n^7 = x mod 55, fuer n=0..9
# ... fuer RSA Verschluesselungsuebung
# 10/04/25
n=0
while n <= 10:
print (n, "^7=", n**7)
n = n+1
n=0
while n <= 10:
print (n, "^7=", (n**7)%55 ,"mod 55")
n = n+1
0 ^7= 0
1 ^7= 1
2 ^7= 128
3 ^7= 2187
4 ^7= 16384
5 ^7= 78125
6 ^7= 279936
7 ^7= 823543
8 ^7= 2097152
9 ^7= 4782969
10 ^7= 10000000
0 ^7= 0 mod 55
1 ^7= 1 mod 55
2 ^7= 18 mod 55
3 ^7= 42 mod 55
4 ^7= 49 mod 55
5 ^7= 25 mod 55
6 ^7= 41 mod 55
7 ^7= 28 mod 55
8 ^7= 2 mod 55
9 ^7= 4 mod 55
10 ^7= 10 mod 55
ok und jetzt:
klartext = [2, 87, 16, 41, 76, 65, 33, 91, 7, 32]
klartext' = [2, 8, 7, 1, 6, 4, 1, 7, 6, 6, 5, 3, 3, 9, 1, 7, 32]
das geht aus einem grund nicht, was ist 2 und was ist 87?
klartext = [02, 87, 16, 41, 76, 65, 33, 91, 07, 32]
klartext' = [0, 2, 8, 7, 1, 6, 4, 1, 7, 6, 6, 5, 3, 3, 9, 1, 0, 7, 3, 2]
encrypted = [0, 18, 2, 28, 1, 41, 49, 1, 28, 41, 41, 25, 42, 42, 4, 1, 0, 28, 42, 18]
damit das ordentlich funktioniert:
encrypted = [00, 18, 02, 28, 01, 41, 49, 01, 28, 41, 41, 25, 42, 42, 04, 01, 00, 28, 42, 18]
so, ok, jetzt machen wir die sache rueckwaerts...
jetzt muss ich das entschluesseln, dazu muss ich berechnen:
28^23 = x mod 55
weil, sich aber 28^23 nicht berechnen muss, verwende ich zwar nicht gleich die variante,
https://www.mi.fu-berlin.de/inf/groups/ag-idm/teaching/Rechnersicherheit/RS4.pdf
hier steht ein verfahren was sicher nicht schlecht ist. ich denke aber immer, zum verstehen
sollte man sich nicht einfach einfacherer methoden da bedienen
1.) wo es sich anbietet, wo es auch anders geht
2.) sondern die teilschritte
1.) ueber viele varianten verstehen
2.) innerhalb der varianten, sollte man von faellen ausgehen, die als
das klassische beispiel gelten, das alles erklaert
deswegen mache ich
((28 mod 55) * 28) mod 55) ..
23x
und da das per hand so lange dauert, besonders, wenn man sich vergewissern will, das es geht
nehme ich erst mal python...
## es hat funktioniert! hat funktioniert!!!
# (c) David Vajda
# python 3 - n^7, fuer n=0..9
# ... oder n^7 = x mod 55, fuer n=0..9
# ... fuer RSA Verschluesselungsuebung
# 10/04/25
n=0
while n <= 10:
print (n, "^7=", n**7)
n = n+1
n=0
while n <= 10:
print (n, "^7=", (n**7)%55 ,"mod 55")
n = n+1
n=0
x=28
y=1
while n < 23:
y = (y*x)%55
n = n + 1
print (y)
auf die 7 am ende achten!!!
0 ^7= 0
1 ^7= 1
2 ^7= 128
3 ^7= 2187
4 ^7= 16384
5 ^7= 78125
6 ^7= 279936
7 ^7= 823543
8 ^7= 2097152
9 ^7= 4782969
10 ^7= 10000000
0 ^7= 0 mod 55
1 ^7= 1 mod 55
2 ^7= 18 mod 55
3 ^7= 42 mod 55
4 ^7= 49 mod 55
5 ^7= 25 mod 55
6 ^7= 41 mod 55
7 ^7= 28 mod 55
8 ^7= 2 mod 55
9 ^7= 4 mod 55
10 ^7= 10 mod 55
7
28 entspricht 7, bzw. 7 unverschluesselt, 28 verschluesselt!!!
weil, das rechnen in diesem falle wirklich eine muessige sache ist, naemlich, 28*28*...*28 = x mod 55, ob nun mod 55 inzwischen oder nicht... und das nicht zum notwendigen handrechnen gehoert, mache ich das jetzt mit python 3....
# (c) David Vajda
# python 3 - n^7, fuer n=0..9
# ... oder n^7 = x mod 55, fuer n=0..9
# ... fuer RSA Verschluesselungsuebung
# 10/04/25
def decrypt23(x):
n=0
y=1
while n < 23:
y = (y*x)%55
n = n + 1
print (y, end=" ")
n=0
while n <= 10:
print (n, "^7=", n**7)
n = n+1
n=0
while n <= 10:
print (n, "^7=", (n**7)%55 ,"mod 55")
n = n+1
n=0
x=28
y=1
while n < 23:
y = (y*x)%55
n = n + 1
print (y)
encrypted = [0, 18, 2, 28, 1, 41, 49, 1, 28, 41, 41, 25, 42, 42, 4, 1, 0, 28, 42, 18]
i = 0
while i < len (encrypted):
decrypt23 (encrypted[i])
i = i + 1
0 ^7= 0
1 ^7= 1
2 ^7= 128
3 ^7= 2187
4 ^7= 16384
5 ^7= 78125
6 ^7= 279936
7 ^7= 823543
8 ^7= 2097152
9 ^7= 4782969
10 ^7= 10000000
0 ^7= 0 mod 55
1 ^7= 1 mod 55
2 ^7= 18 mod 55
3 ^7= 42 mod 55
4 ^7= 49 mod 55
5 ^7= 25 mod 55
6 ^7= 41 mod 55
7 ^7= 28 mod 55
8 ^7= 2 mod 55
9 ^7= 4 mod 55
10 ^7= 10 mod 55
7
0 2 8 7 1 6 4 1 7 6 6 5 3 3 9 1 0 7 3 2
02 87 16 41 76 65 33 91 07 32
klartext = [2, 87, 16, 41, 76, 65, 33, 91, 7, 32]