Frage zur RSA Verschlüsselung

TheToast

Hi!

Hab grade die RSA Verschlüsselung gelernt, bzw. wies funktioniert, hab da aber noch eine Frage.
Erstmal der ablauf, wie ichs gelernt habe:
1. 2 Primzahlen, p=7 q=11 (eigentlich möglichst groß, aber zum rechnen halt klein.
2. pq=77 (1. Teil des öffentlichen Schlüssels)
3. D ausrechnen, eine Primzahl<(p-1)(q-1) Also eine Primzahl kleiner als 60, ich nehme mal 13 (Privater Schlüssel)
4. e ausrechnen, wobei e*d kongruent 1 mod 60 sein muss.
Jetzt das Problem, wie berechne ich e?
Habs leider nicht mitgeschrieben, habs aber in der Schule auch nicht verstanden...

Danke im Voraus

rüdiger

http://www.wiwi.uni-bielefeld.de/StatCompSci/lehre/material_spezifisch/statalg00/rsa/node9.html

TheToast

Ich blick da ehrlich gesagt nicht ganz durch...

mady

Naja .... dann wollen wir mal.

In Schritt 3 schreibst Du, du bestimmst 'd'. Das ist IMHO unüblich, geht aber genauso In meinem Beispiel steht für den publicKey das 'e' und für den privateKey das 'd'. Den anderen 'passenden' Schlüssel bestimmst DU mit dem 'erweiterten Euklidischen Algorithmus'. Das ist eigentlich ganz einfach, wenn Du eine Implementierung dieses Verfahrens hast. In Standard-C sieht das ganze dann so aus:

#include <math.h>
#include <stdio.h>
#include <assert.h>

long qe2(long x, long y, long n)   /* berechne x^y mod n */
{
    long s, t, u;

    s = 1, t = x, u = y;

    while (u) {
        if (u & 1) s = (s * t) % n;
        u >>= 1;
        t = (t * t) % n;
    }

    return s;
}

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

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

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

    return 0;
}

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

long rsa_encrypt(long m, long e, long n)
{
    assert(m < n);        /* m muss kleiner als n sein */
    return qe2(m, e, n);
}

long rsa_decrypt(long c, long d, long n)
{
    assert(c < n);        /* c muss kleiner als n sein */
    return qe2(c, d, n);
}

int main(void)
{
    long p, q, n, e, d;
    long m, c;

    p = 47; q = 71;            /* zwei Primzahlen, zufällig gewählt */
    n = p*q;                   /* modulus */
    e = 79;                    /* public Key */
    d = rsa_genkey(p, q, e);   /* private Key */

    m = 1234;
    c = rsa_encrypt(m, e, n);
    if (rsa_decrypt(c, d, n) != m)
        puts("ERROR");

    return 0;
}

Sorry für den langen Code ....

Die Funktion 'extended_euclid()' implementiert den oben genannten Algo. 'inverse()' ruft 'extended_euclid()' gleich mal 'passend' auf. Das passende 'd' zum 'e' zu finden ist somit trivial. Die anderen Funktionen sind selbsterklärend.

Was in dem Code noch fehlt: sowohl 'd' als auch 'e' müssen relativ prim zu (p-1)*(q-1) sein. Das muss also noch geprüft werden.

Ich hoffe, ich konnte Dir damit helfen ....

TheToast

Yeah, thx