RSA -> d

[Dragonfire]

Hi!

So e habe ich nun berechnet, nur d bekomm ich irgendwie nicht hin:
1. ist meine Rechnung richtig?
2. woher bekomm ich d?

p = 101
q = 383

N = 38683
phi = 38200

e = 38219

int n = p*q;
    int phi = (p-1)*(q-1);
    /*e berechnen*/
    int e = phi+2;
    while(!primzahl(e))
    {
      e ++;
    }
    /*ende berechnung*/
    int d = (phi+1)/e;

thx

[Turing]

es muss gelten:

$gcd(\phi, e) = 1$
und
$1 < e < \phi$

Zweiteres trifft schonmal nicht zu.

An d kommst Du mit dem erweiterten euklidischen Algorithmus (siehe z.B. Knuth oder googeln).

[Dragonfire]

gut das mit d hab ich nun (anderer Ansatz), die frage ist nun, wonach such ich mir e aus?

[Turing]

wonach such ich mir e aus?

Wie gesagt, e muss kleiner phi sein und beide haben keine gemeinsamen Teiler. Ein erster Schritt wäre p-1 und q-1 zu faktorisieren. Alle darin vorkommenden Faktoren dürfen in e nicht enthalten sein.

Beispiel: p = 23, q = 17
p-1 = 22 = 2*11, q-1 = 16 = 2^4 => e kann z.B. 3, 5, 7, 9, 11, 13, 15 sein.

Was ist Dein anderer Ansatz für d?

[Dragonfire]

void TForm1::schluesselBerechnen()
{
  if(error)
  {
    StartV->Enabled = false;
    return;
  }
  if(P->Text.Length() != 0 && Q->Text.Length() != 0)
  {
    p = P->Text.ToInt();
    q = Q->Text.ToInt();
    n = p*q;
    int phi = (p-1)*(q-1);
    e = phi;
    while(!primzahl(e) || teiler(phi,e))
    {
      e --;
    }
    /*ende berechnung*/
    d = rsa_genkey(p, q, e);
    N->Text = (AnsiString)n;
    Phi->Text = (AnsiString)phi;
    E->Text = (AnsiString)e;
    D->Text = (AnsiString)d;
    SchluesselV->Text = E->Text + "/" + N->Text;
    StartV->Enabled = true;
  }else{
    N->Text = "-";
    E->Text = "-";
    SchluesselV->Text = "-/-";
    Phi->Text = "-";
    D->Text = "-";
    StartV->Enabled = false;
  }
}

long rsa_genkey(long p, long q, long e) 
{ 
    return inverse(e, (p-1)*(q-1));
}

long inverse(long a, long n)
{ 
    long d, x, y; 

    extended_euclid(a, n, &x, &y, &d); 
    if (d == 1) return x;

    return 0; 
}

void extended_euclid(long a, long b, long *x, long *y, long *d)   /* erweiterter Euklid */
{
    long q, r, x1 = 0, x2 = 1, y1 = 1, y2 = 0;

    if (b == 0) {
        *d = a; 
        *x = 1;
        *y = 0; 
        return;
    } 

    while (b > 0) { 
        q = a / b;
        r = a - q * b; 
        *x = x2 - q * x1;
        *y = y2 - q * y1; 
        a = b;
        b = r; 
        x2 = x1;
        x1  = *x; 
        y2 = y1;
        y1 = *y; 
    } 

    *d = a; 
    *x = x2; 
    *y = y2; 
}

[Turing]

Was mir zunächst auffällt:

1. Schipsel:

Zeile 10,11: p und q müssen prim sein.
Zeile 15: e muss nur relativ prim zu phi sein, d.h. keine gemeinsamen Primfaktoren.

Funktioniert der euklidische Algorithmus?

Ansonsten probier mal:

void ext_euclid(unsigned int m, unsigned int n,
                unsigned int& gcd, unsigned int& inv)
{
   unsigned int a[3] = { 0, 1, m }; 
   unsigned int b[3] = { 1, 0, n }; 
   unsigned int t[3];
   unsigned int q;

   for (;;)
   {
      if ( b[2] == 0 )
      {
         gcd = a[2];
         inv = 0;    // does not exist
         return;
      }
      if ( b[2] == 1 )
      {
         gcd = b[2];
         inv = b[1];
         return;
      }

      q = a[2] / b[2];
      t[0] = a[0] - q * b[0];
      t[1] = a[1] - q * b[1];
      t[2] = a[2] - q * b[2];

      // swap
      a[0] = b[0]; a[1] = b[1]; a[2] = b[2];
      b[0] = t[0]; b[1] = t[1]; b[2] = t[2];      
   } 
}

In inv steht 0, wenn kein Inverses existiert.

Ansonsten sieht es ja schon ganz gut aus. Was Du später beim Ver-/Entschlüsseln beachten solltest ist, dass

$a^b \, mod \, n = ((a^{b\_1} \, mod \, n)(a^{b\_2} \, mod \, n)) \, mod \, n$
mit
$b\_1 + b\_2 = b$

gilt. Ansonsten rennst Du sehr schnell in einen Überlauf.

[Dragonfire]

Danke für die Tips!