Faktorisieren einer Zahl mit GGNFS WIN32

Hier haben wir einen RSA Datenblock mit 768 Bits

Modulus:
C19789371E66666726902D8377C7BF621CD021BA5DA24BD8A95AB622245466BACF33314D1DC

5991EADCA7538A33E2D87821C8042CA9CF750BE887BFFB8F9B172A88BF657E78AD7AA180F4C

2FED26F4DBA849DD0AD3857A0ED68B18ECA8399AC7

Dieser wird nun in DEZ umgewandelt, hier für benutz ich Maple 12, da es große Zahlen rechnen kann und keine Ausgabe wie z.B. 4232342342343+100 gibt sondern die ganze Zahl. Formel ist :

convert("XXXXXXXXXXXX", decimal, hex)

Der Modulus ist in Dezimal jetzt:
117404291201521812831742820600420827651671610123674232845074410915453961299
142673400324608790706577390247997676383055013519435585689766514645281416359
321120042405754278299516617394066043872810240117015502164366969343710438187
4510535

Dieser wird mit GGNFS als WORKFILE gespeichert. Einfach mit einem Editor eine Datei anlegen wie worktodo.ini . In diese Datei kommt der Befehl:
n:1174042912015218128317428206004208276516716101236742328450744109154539612
991426734003246087907065773902479976763830550135194355856897665146452814163
593211200424057542782995166173940660438728102401170155021643669693437104381
874510535
speichern.

Das machen wir mit der DOS BOX (CMD) von Windoof.
Im Verzeichniss msieve -p -v -np eintippen und er übernimmt automatisch die Worktodo.ini File und erstellt eine Poly Datenbank

C:\Temp\**>cd ggnfs-svn340-win32-p4

C:\Temp\**\ggnfs-svn340-win32-p4>msieve -p -v -np

Msieve v. 1.41
Thu Apr 16 11:43:42 2009
random seeds: 58f06418 b7921dd2
factoring 1174042912015218128317428206004208276516716101236742328450744109154539
612991426734003246087907065773902479976763830550135194355856897665146452814
16359
321120042405754278299516617394066043872810240117015502164366969343710438187
45105
35 (232 digits)
p1 factor: 5
prp231 factor: 23480858240304362566348564120084165530334322024734846569014882183
090792259828534680064921758141315478049599535276611002703887117137953302929
05628
327186422400848115085565990332347881320877456204802340310043287339386874208
76374
902107
elapsed time 00:00:01

OK, dieser Modulus ist sehr einfach, deswegen hat es 1 Sekunde gebraucht ihn zu faktorisieren. P1 ist 5 PRP231 ist auch da.

So mit Hexprob Calculator übersetzt man sich jetzt die DEZ in HEX und bekommt die 2Prime in HEX:

26 B7 E8 3E 39 47 AE 14 A1 50 09 1A 4B 27 F3 13 9F 5C D3 8B AC 53 A8 C4 EE AB BE 06 D4 10 E1 58 8F D7 09 DC 39 27 85 06 22 C2 17 71 BA 3F A2 B4 B3 9F 4C DA 28 85 CB 10 26 1B 4B FF F1 CB 89 E3 BB 4F 31 44 C7 E8 91 88 6B 36 42 6F FC 3A FD C5 88 0E C5 CE F7 1A B2 02 F7 B5 6B 62 88 0B 85 5B

Das heisst wir haben den Modulus und die 2 Primes, die den Modulus errechnen N=P*Q.

Um den Privaten Exponenten zu errechnen ist eine andere Sache. Vieleicht erweitert jemand das Tutorial.

Ja RSA hört sich echt böse an, ist es aber nicht.

Du hast in der RSA Verschlüssellug immer 2 Faktoren gegeben.

Ein Beispiel unser Geheimniss ist: 104743345685891479405330289372302737802

Das ist die verschlüsselte Nachricht.

Es gibt 2 Arten RSA zu verschlüsseln, einmal im Block oder als Flusstext.
Der Block Algo ist meist in gebrauch bzw interessant für uns, da diese Art bei Smartcards sehr häufig eingesetzt wird.
Dabei bleibt der Algo aber gleich.

Unser Modulus ist:170417866921416591174447414014771777641
Public Exponent:10001

Also fehlt uns zum entschlüsseln der Private Exponent um unser Geheimniss zu entschlüsseln.

Woher nehmen?

Jetzt versuch mal den Modulus aus 2 Primzahlen zu errechnen.
Das machen wir aber bei großen Modi mit GGNF, bei kleinen mit dem
Taschenrechner bzw im Kopf.

In einer Applikation, wirst du so einfach nicht an die Zahlen gelangen.
Diese sind dann im HEX Code und da gibt es viele

AES ist da einfacher zu finden, man hat in der Appl. immer sine S-Box

Rechnen mit unekannten ist Stoff der 5 Klasse, nicht bei jedem platzt der Knoten gleich.

Beispiele:
Kryptographie - RSA-Verfahren

LÖSUNG:

p:11463516005908572899
q:14866107992833883459

Privat Exponent=100409166017724037575620189262232879321