4. Probleme mit fmod/ElGamal Entschlüsselung (dringend)

Probleme mit fmod/ElGamal Entschlüsselung (dringend)

  • M

    Hey
    ich programmier derzeit das ElGamal - Kryptografieverfahren für c habe aber irgendeinen Fehler beim entschlüsseln...
    Ich hab mal den Quellcode meiner Testklasse gepostet:

    #include <stdio.h>
    #include <math.h>
    void main(void)
    {
    double prim=127,b=3,a=6,g=7,m=126;
    double crypt,A,B,plain;

    A = fmod(pow(g,a),prim);
    printf("A=%0.lf\n",A);
    B = fmod(pow(g,b),prim);
    printf("B=%0.lf\n",B);
    crypt = fmod((pow(A,b)*m),prim);
    printf("Geheimtext=%0.lf\n",crypt);
    plain = fmod((pow(B,(p-1-a))*c),prim);
    printf("Klartext=%0.lf\n",plain);
    }

    Das Problem liegt dabei in der Berechnung von plain. Hab die Werte auch einzeln berechnet und damit dem fmod(double,double) übermittelt aber auch damit kommen die falschen Werten raus.

    Kurzfassung ElGamal:
    a,b geheime Schlüssel
    p Primzahl
    m Klartext (Werte je nach Zeichen des ASCII von 32 bis 126)
    g Primitivwurzel
    Schlüsselerzeugung: A = ga mod p (Übermittlung von [(p).(g).(A)]
    B = gb mod p
    Verschlüsselung : c = A b * m mod p (Übermittlung von [(B).(c)])
    Entschlüsselung: m = Bp-1-a * c mod p

    Am Beispiel: a=6,p=127,g=7 und b=3 kommt A = 47,B=89,crypt=63 richtig jedoch laut Programmierung plain=120...wobei eigentlich plain=126=m kommen müsste

    Wie gesagt keine Ahnung wobei der Fehler auftritt aber ich wäre unendlich dankbar wenn ihr mir ne Antwort geben könntet und mir meinen Fehler erklären könnt!
    Denn die Zahlen sind net zu groß für double...

    0
  • K

    Mix84 schrieb:

    void main(void)

    Schon der zweite heute. Das Programm kann ja gar nicht funktionieren...

    0
  • M

    Auch mit
    int main()
    hab ich keinen Erfolg...

    0
  • P

    Huhu,
    liefert fmod Primitivwurzeln ?

    Vielleicht solltest du es mal im Mathematik - Forum probieren.

    0
  • F

    Es ist ja auch nicht Bp-1-a sondern (Ba)-1. Du berechnest doch

    pubkey von A: A = ga mod p
    pubkey von B: B = gb mod p

    c = A b * m ≡ gab mod p

    d.h. du verschlüsselst mit dem gemeinsamen Key von A und B.

    m = (B a)-1 * c ≡ (gab)-1 * c mod p

    heißt, du nimmst den public key von B, nimmst ihn hoch a. Dann hast du den Sessionkey zwischen A und B. Von dem musst du allerdings das Inverse bilden, weil du mit gab verschlüsselst und mit dem Inversen entschlüsseln musst. Daher brauchst du ne Funktion wie den erweiterten Euklid. Wundert mich, warum das so komisch in Wikipedia steht ..

    0
  • M

    Also laut der Arbeit die Taher ElGamal über digitale Verschlüsselung schrieb ist Bp-1-a * c mod p = m also der Klartext und so steht das auch überall.
    Hab das gleiche schon in Java geschrieben und da funktioniert es ohne Probleme. Trotzdem danke für denn Beitrag!

    0
  • F

    Mhh, möglicherweise ist Bp-1-a das Gleiche wie (Ba)-1, halt nur anders geschrieben. Ka, ob man das mit dem Satz des Fermat irgendwie zeigen kann. Ich kenne es halt nur mit (Ba)-1), aber wenn du sagst, dass es in Java klappt, würde ich einfach mal vermuten, dass die Berechnung zu groß für Double wird. Entweder speziellen Datentyp verwenden oder Algorithmen wie Sqare&Multiply verwenden, damit die Zahlen nicht so groß werden - http://de.wikipedia.org/wiki/Schnelles_Potenzieren.

    0
Anmelden zum Antworten