[HaBo]

Elderan

Anzeige

Hallo,
wie kann man Modula einfach berechnen, irgendwie versteht ich das noch nicht ganz richtig.

Wenn ich 801^17 mod 2773 habe wie kommt man dort dann auf 2480 ?

Also am besten ein Beispiel in Excel.
Also ich habe es bisher so gemacht in Excel, allerdings sind da so große Zahlen das excel damit nicht umgehen kann:

Rest von 801^17 / 2773 (bekomme immer einen Error weil die Zahlen zugroß sind.

Ich denke mal da gibt es auch noch einfachere Möglichkeiten, denn wenn man z.B. 801^65537 mod 16977218433902659955017 (...) hat würde es so ja bestimmt sehr lange dauern bis man das Ergebnis hat, oder?

hants

servuz,

korrigier mich, wenn ich mich irre - aber du meinst sicher modulO ^^

modulo ist der rest bei einer integer division.

bsp 5 mod 3 = 2 oder (801^17) mod 2773 = 2480

der computer macht divisionen durch mehrfache subtraktion, da entsteht der modulo als nebenprodukt.

wenn du das modulo selbst berechnen willst machst du das so:
einfach eine ganzzahlige Division (9 idiv 5 = 1), dann das Ergebnis mal den Divisor (5 * 1 = 5) und abschließend die Differenz zum ursprünglichen Dividenden bestimmen (9 - 5 = 4).

so einfach ist das^^

zu deiner letzten frage: das einzige was an der berechnung lange dauern würde ist die berechnung der potenz, und mit einem programm, das so grosse zahlen unterstützt würde das auf einem durchschnittsrechner nicht länger als 5sec (und das sind eigentlich schon fast 5 sec zuviel ) benötigen.

wozu willst du überhaupt den modulo so grosser zahlen ausrechnen?

cya, hants

Elderan

Hallo,
danke so geht es.

Also ich beschäfige mich gerade mit RSA (Schlüsselberechnung).

Ne kleine Frage hätte ich noch, wie man folgendes schnell Berechnen kann:

d*17 = 1 mod 2668

Am Ende sollte d = 157 rauskommen.

Beim CrypTool steht auch noch folgende Formel:
d = 17^-1 mod 2668

Also
d = 1/17 mod 2668

Danke

hants

servuz,

die frage war ja wie man das "schnell" berechnen kann - so wie oben beschrieben ist das falsch(= langsam)^^

CDQ
MOV EAX,123
MOV EBX,7
IDIV EBX

hier wird 123 idiv 7 gerechnet, das ergebnis der division liegt am ende in eax, der modulo in edx.

schneller würde es mit shiften gehen, aber so tief bin ich nicht in assembler mathematik eingestiegen.

deine letzten beispiele hmm - ergeben für mich keinen sinn..

wie man das trotzdem schnell berechnen kann - ist leicht erledigt:

wenn bei einem modulo der divisor kleiner als der divident ist, ist der rest der dabei rauskommt(also das modulo) der divisor selbst. also 5 mod 9 = 5 oder 1 mod 2668 = 1 und daraus folgt: 17*d = 1 => d= 1/17

die restlichen berechnungen bei dir sind... interessant

gib mal mehr infos oder anständige auszüge

cya, hants

Elderan

Hallo,
http://www-aix.gsi.de/~peter/Kryptographie/sld025.htm
http://www-aix.gsi.de/~peter/Kryptographie/sld026.htm


um den privaten Schlüssel d zu berechnen gilt folgende Formel:

de = 1 mod ((p-1)*(q-1))

Bei den Primzahlen 47/59 und e = 17 würde folgendes Rauskommen:
d*17 = 1 mod 2668
157*17 = 1 mod 2668
2669 = 1 mod 2668

Aber wenn man z.B. e = 3 nimmt, wäre d = 1779
1779 * 3 = 1 mod 2668


Eine Möglichkeit d zu berechnen wäre mit einer Schleife
while(true)
{
$wert = (2669+2668*$a)/2668;
$a++;

if(Wenn $wert keine Komma Stellen hat, ist $a = d)
}

Also in jeder Runde wird zum 2669 Wert die Zahl 2668 addiert. Das Ergebnis daraus wird durch 2668 geteilt. Wenn da eine Zahl ohne Komma Stellen raus kommt, ist die Runde/Schleife der geheime Key d.

Allerdings würde man bei größeren Werten (600 und mehr Stellen) recht lange dauern, denn da braucht man dann ja extrem viele Schleifendruchläufe (manchmal 10 ^1200 wenn man immer (p-1)*(q-1) addiert.). Deswegen frage ich mich wie PGP/CrypTool das so schnell berechnet, ich denk mal das es dafür ne viel leichtere/schnellere Möglichkeit gibt.



P.S. (p-1)*(q-1) ist bei meinen Primzahlen (47/59) zusammen 2668

silenced

Versuch doch mal ne mathematische funktion 2ten grades daraus zu stricken :-)

Elderan

Hallo,
wenn ich bloß wüsste wie das geht...

silenced

Bin gerade am einarbeiten

TheVoid

elderan: google mal nach "square and multiply"
das ist genau das was du suchst, denke ich

s&m splittet die multiplikation in log(n) quadrierungen und ~n/2 multiplikationen.
nach jedem schritt kannst du dann modden. für grosse zahlen (wie bei rsa)
ist das effektiver als klartext^publickey mod n
( bin("hallo")^1024bit-zahl kann ich persönlich mir nicht vorstellen, und will das ergebnis auch nicht mod n rechnen )