Entwickler-Ecke :: Thema anzeigen

epsodus - 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.

Ralf Jansen - 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 - 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 zusammengefasst

Hallo 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 zusammengefasst

Hm, in c# bin ich wohl zu blöd oder denke verkehrt.
In c würde es so aussehen :

C#-Quelltext

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));

  /* Setzen n, e, d */
  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:
  /* Alle Variablen muessen initialisiert werden */
  mpz_inits(K, g, t, x, x1, y, p, NULL);

  /* K = d * e */
  mpz_mul(K, d, e);
  /* K = K - 1 */
  mpz_sub_ui(K, K, 1);

  gmp_printf("K=d*e-1=%Zd\n", K);

schritt2:

  /* Wähle g = 2.. N-1 */
  do {
    mpz_urandomm(g, randomstate, N);
  } while (mpz_cmp_ui(g, 2) < 0);

  gmp_printf("Trying g = %Zd\n", g);

  /* t = K */
  mpz_set(t, K);

schritt3:
  do {
    /* Wenn t durch zwei teilbar */
    if (mpz_divisible_ui_p(t, 2)) {
      /* t = t / 2 */
      mpz_divexact_ui(t, t, 2);
      gmp_printf("t= %Zd\n", t);
      /* x = g ^ t mod N */
      mpz_powm_sec(x, g, t, N);
      gmp_printf("x= g^t mod N=%Zd\n", x);
    }
    else
      goto schritt2;

    /* Wenn x > 1 */
    if (mpz_cmp_ui(x, 1) > 0) {
      /* y = ggT(x - 1, N) */
      mpz_sub_ui(x1, x, 1);
      mpz_gcd (y, x1, N);
      gmp_printf("y= gcd(x-1,N)=%Zd\n", y);
      /* Wenn y > 1 */
      if (mpz_cmp_ui(y, 1) > 0)
        goto schritt4;
    }
  } while (1);
schritt4:
  /* p = N / y */
  mpz_cdiv_q(p, N, y);
  gmp_printf("p= %Zd\n", p);
  gmp_printf("q= N/p = y =%Zd\n", y);

  return 0;
}

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!