| Autor |
Beitrag |
epsodus
Beiträge: 38
|
Verfasst: So 15.11.15 22:22
Hallo,
das Programm läuft jetzt stabil. Da es hier um RSA geht, würde ich gerne noch folgende Berechnung dazu nehmen.
Hierbei geht es um die Berechnung von p und q, wenn nur N, e und d vorhanden sind.
Beschreibung :
Es soll zuerst K=de-1 berechnet werden. Wir wählen eine zufällige ganze Zahl g im Bereich 1 <g <N gewählt werden.
k soll eine gerade Zahl sein.
Input : N,e, d
Output : p und q wenn pq=N
1. Initialisiere Set K <de-1
2. Suche ein zufälliges g. Wählen Sie g zufällig aus {2, ...., N-1} und setzen t <-K
3. Als nächstes t. Wenn t teilbar durch 2, setze t <t / 2 und x <-gt mod N. Andernfalls gehe zu Schritt 2
4. Fertig? Wenn x> 1 und y = ggT (x-1, N)> 1, dann setze p <N / y, Ausgang (p, q)
und beende die Berechnung. Ansonsten gehe zu Schritt 3.
Ein Beispiel :
Input N= 25777, e=3, d= 16971
k=de-1=50912
Trying g = 2
t= 25456
x= g^t mod N=1
t= 12728
x= g^t mod N=1
t= 6364
x= g^t mod N=1
t= 3182
x=g^t mod N=25776
y= gcd(x-1,N)=1
t= 1591
x=g^t mod N=12709
x=g^t mod N=1
Trying g = 5
t= 25456
x= g^t mod N=1
t= 12728
x= g^t mod N=1
t= 6364
x= g^t mod N=1
t= 3182
x= g^t mod N=15050
y= gcd(x-1,N)=149
p= 149
q= N/p=25777/149=173
Output: p=173 und q=149
Dies bekomme ich nicht umgesetzt, kann jemand mal den Anfang machen. Das Programm würde ich später als gesamtes gerne hier zur Verfügung stellen.
|
|
Mathematiker
 
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 16.11.15 00:02
Hallo,
soweit ich dich richtig verstanden habe, möchtest du
faktorisieren. Warum nutzt du dann diesen "merkwürdigen" Algorithmus? K, e und d sind doch gar nicht wichtig für die Primfaktorzerlegung von N.
Für kleine N gibt es extrem schnelle Verfahren (siehe www.entwickler-ecke....hlight=faktorisieren allerdings in Delphi  ), für größere N dürfte dein Algorithmus auch ziemlich langsam sein. Wo hast du den eigentlich her?
Beste Grüße
Mathematiker _________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Mo 16.11.15 00:37
| Zitat: | | Da es hier um RSA geht, würde ich gerne noch folgende Berechnung dazu nehmen. |
Wo ist der Zusammenhang vom bisherigen Problem zu RSA? Ich würd sagen neue Frage neuer Thread.
Da du eine Aufgabenbeschreibung mitlieferst gehe ich davon aus das dir diese Aufgabe in irgendeinem Rahmen gestellt wurde.
Ich fände es, unter anderem deswegen, nett wenn du es erst selbst auf irgendeine Art zu lösen versuchst bevor du es von uns lösen lassen möchtest bzw. von uns Hilfe dazu erfragst (ein ganz klein wenig initiale Eigenleistung). Dir sind 4, recht klare, Steps mitgegeben worden die kannst du doch erstmal umsetzen und sehen wo dich das hinführt.
|
|
epsodus 
Beiträge: 38
|
Verfasst: Mo 16.11.15 08:01
Hallo Mathematiker,
nein, ich möchte nicht faktorisieren, also herkömmlich. Bei mir geht es darum, wenn ich N, e und d gegeben habe, möchte ich daraus p und q errechnen. Dies ist wesentlich einfacher, da d schon
gegeben iost. Ja, doch etwas faktorisieren. Moderiert von  Narses: Beiträge zusammengefasstHallo Ralf,
nein, die Aufgabe wurde nicht gestellt. Wollte es nur als Tool dazunehmen. Ja, da gebe ich Dir recht,
" Ich fände es, unter anderem deswegen, nett wenn du es erst selbst auf irgendeine Art zu lösen " .
Werde heute nochmals schauen ob ich ein Stück weiter komme und dann den bisherigen Code einstellen
und meine Schwierigkeit beschreiben. Moderiert von Narses: Beiträge zusammengefasstHm, in c# bin ich wohl zu blöd oder denke verkehrt.
In c würde es so aussehen :
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
| #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gmp.h>
int main(int argc, char **argv) {
gmp_randstate_t randomstate;
mpz_t N, d, e, K, g, t, x, x1, y, p;
gmp_randinit_default (randomstate);
gmp_randseed_ui(randomstate, time(0));
mpz_init_set_str(N, "25777", 10);
mpz_init_set_ui(e, 3);
mpz_init_set_ui(d, 16971);
gmp_printf("N=%Zd, e=%Zd, d=%Zd\n", N, e, d);
schritt1:
mpz_inits(K, g, t, x, x1, y, p, NULL);
mpz_mul(K, d, e);
mpz_sub_ui(K, K, 1);
gmp_printf("K=d*e-1=%Zd\n", K);
schritt2:
do {
mpz_urandomm(g, randomstate, N);
} while (mpz_cmp_ui(g, 2) < 0);
gmp_printf("Trying g = %Zd\n", g);
mpz_set(t, K);
schritt3:
do {
if (mpz_divisible_ui_p(t, 2)) {
mpz_divexact_ui(t, t, 2);
gmp_printf("t= %Zd\n", t);
mpz_powm_sec(x, g, t, N);
gmp_printf("x= g^t mod N=%Zd\n", x);
}
else
goto schritt2;
if (mpz_cmp_ui(x, 1) > 0) {
mpz_sub_ui(x1, x, 1);
mpz_gcd (y, x1, N);
gmp_printf("y= gcd(x-1,N)=%Zd\n", y);
if (mpz_cmp_ui(y, 1) > 0)
goto schritt4;
}
} while (1);
schritt4:
mpz_cdiv_q(p, N, y);
gmp_printf("p= %Zd\n", p);
gmp_printf("q= N/p = y =%Zd\n", y);
return 0;
} |
|
|
|
