Ist 341 eine Primzahl?
Basis 2 sagt: True
Basis 3 sagt: False


RSA-Beispiel

m = 253 = 11 * 23, phi = 220

Suche passendes e:
e = 25, ggt(e,phi) = 5, geeignet: False
e = 17, ggt(e,phi) = 1, geeignet: True
e = 17; d = 13
e * d = 17 * 13 = 221 = 1 (mod 220)

Geheime Nachricht an Alice
x = 47
Verschluesselung: y = x^e = 47^17 = 185 (mod 253)
Entschluesselung: y^d = 185^13 = 47 (mod 253)
x = 118
Verschluesselung: y = x^e = 118^17 = 200 (mod 253)
Entschluesselung: y^d = 200^13 = 118 (mod 253)

Geheime Nachricht an Bob
Bobs oeffentlicher Schluessel: m' = 323, e' = 5
x = 16
Verschluesselung: y = x^e' = 16^5 = 118 (mod 323)

Alice signiert
Signatur: x' = x^d = 16^13 = 26 (mod 253)
Verschlüsselung: y' = x'^e' = 26^5 = 144 (mod 323)

Bob's Schluessel knacken:
Wir suchen die Faktoren von m' = 323
m' = 323 = 17 * 19 = p'*q'
phi' = 288, d' = 173

Nachricht fälschen:
z = 66
Signieren: z' = z^d' = 66^173 = 138 (mod 323)
Carol erhält die Nachricht 138.
und liest: z'^e' = 138^5 = 66 (mod 323)
Sie glaubt daher sicher sein zu koennen, dass sie von Bob stammt
...und ist ganz traurig.


Große Zahlen:

Ist 17 eine Primzahl? True
Ist 18 eine Primzahl? False
Ist 341 eine Primzahl? False
Ist 42347889747234892347492346746474788484834939394834893 eine Primzahl? False
11 ist groesser gleich 11 und prim.
29 ist groesser gleich 24 und prim.
347 ist groesser gleich 341 und prim.
464634893939474589431 ist groesser gleich 464634893939474589409 und prim.
7 ist eine 1-stellige Primzahl
17 ist eine 2-stellige Primzahl
641 ist eine 3-stellige Primzahl
3407629457 ist eine 10-stellige Primzahl
21862669487347722868940643553139067725741608780169 ist eine 50-stellige Primzahl


RSA Verfahren:

mit 2-stelligen Primzahlen
Modul: m = 1273
Oeffentlicher Schluesel: e = 1165
Geheimer Schluessel: d = 1033

Nachricht: x = 788
Verschluesselt: y = x^d = 788 ^ 1165 = 329 (mod 1273)
Test: y^d = 788
Signiert: z = x^d = 61
Test: z^e = 788

Nachricht: x = 569
Verschluesselt: y = x^d = 569 ^ 1165 = 797 (mod 1273)
Test: y^d = 569
Signiert: z = x^d = 797
Test: z^e = 569

mit 10-stelligen Primzahlen
Modul: m = 7345911592835108837
Oeffentlicher Schluesel: e = 1526892708074022539
Geheimer Schluessel: d = 995935821539815559

Nachricht: x = 5459673583565973870
Verschluesselt: y = x^d = 5459673583565973870 ^ 1526892708074022539 = 2371273660989428397 (mod 7345911592835108837)
Test: y^d = 5459673583565973870
Signiert: z = x^d = 7197368284311622337
Test: z^e = 5459673583565973870

Nachricht: x = 6298086246296004635
Verschluesselt: y = x^d = 6298086246296004635 ^ 1526892708074022539 = 7011032513290784176 (mod 7345911592835108837)
Test: y^d = 6298086246296004635
Signiert: z = x^d = 6933257050162478831
Test: z^e = 6298086246296004635

mit 50-stelligen Primzahlen
Modul: m = 1519154492791063099614191423848398661450374090825079752009132853082337866109541884987745857182059681
Oeffentlicher Schluesel: e = 103060701800635990536860581501630411777421575831940432734306268162583623245366220061968828467247753
Geheimer Schluessel: d = 1358474040161071272777284442480533621589603701177519424388788896794091538689037225519938512497097657

Nachricht: x = 634797971979099405845672905405154266695876681176507490407894966263784101491887356207991899924500931
Verschluesselt: y = x^d = 634797971979099405845672905405154266695876681176507490407894966263784101491887356207991899924500931 ^ 103060701800635990536860581501630411777421575831940432734306268162583623245366220061968828467247753 = 1432461699986825266407077893394151458615746987600585697038587747505913216189724478241860920725854327 (mod 1519154492791063099614191423848398661450374090825079752009132853082337866109541884987745857182059681)
Test: y^d = 634797971979099405845672905405154266695876681176507490407894966263784101491887356207991899924500931
Signiert: z = x^d = 27933469364973921951123846957278269379722652008128484225681415475398622708634878878142775762651545
Test: z^e = 634797971979099405845672905405154266695876681176507490407894966263784101491887356207991899924500931

Nachricht: x = 50487895634309352460006716472890811840592059960934426563609066144328424397787679896572492032844353
Verschluesselt: y = x^d = 50487895634309352460006716472890811840592059960934426563609066144328424397787679896572492032844353 ^ 103060701800635990536860581501630411777421575831940432734306268162583623245366220061968828467247753 = 281065254007990099312313725270097986867690897554214807219590143309014242842371332976565210079350223 (mod 1519154492791063099614191423848398661450374090825079752009132853082337866109541884987745857182059681)
Test: y^d = 50487895634309352460006716472890811840592059960934426563609066144328424397787679896572492032844353
Signiert: z = x^d = 402454510833564037674487495829356040805939645872021037580214687577431132610234978889483001451446542
Test: z^e = 50487895634309352460006716472890811840592059960934426563609066144328424397787679896572492032844353
(3053, 1807, 1723)
