Modulo und Potenzen Zahlenbereich



  • Hallo Programmierer!

    Ich möchte für ein Privatprojekt (RSA Verschlüsselung) einen C++ Code schreiben, der mir ermöglicht, alles den Computer ausrechnen zu lassen.
    Es klappt soweit gut, aber mein Problem ist, dass bei einer Potenz von 2^101 oder höher der Datentyp long long oder unsigned int nicht groß genug ist und ich daher keine Möglichkeit finde zu verhindern, dass es Durchläufe gibt.
    Was kann ich machen??? Das Programm klappt soweit, aber es kann so große Zahlen nicht verwerten.

    #include <iostream>
    #include <math.h>
    #include <windows.h>
    
    using namespace std;
    
    int ggt (int a, int b)
    {
       if (b==0) return a;
       else return ggt(b, a%b);
    }
    
    int main()
    {
        int p,q,m,y,k,s,t,erg,klartext,rech;
        long long ausgabe,schritt;
        cout << "p definieren (Primzahl):"; cin >> p;
        cout << "q definieren (Primzahl):"; cin >> q;
        m=(p-1)*(q-1);
        k=p*q;
    
        for (y=100;y<500;y++)
        {
            erg = ggt(y, m%y);
            if(erg==1){cout <<y << "-";};
        }
        cout << "k=" <<k;
        cout <<"\nm=" <<m<<endl;
    
        cout << "Waehle eine der vorangegangenen Zahlen:";
        cin >> s;
    
        for (t=1;t<99999;t++)
        {
            rech=(s*t)%m;
            if(rech==1)
            {
                cout<<"\nt="<<t<<endl;
                break;
            }
        }
        cin.ignore(1000,'\n');
        cin.get();
    
        system("CLS");
        cout<<"Privater Schluessel:\nt="<<t<<endl<<"k="<<k<<endl;
        cout<<"\nOeffentlicher Schluessel:\ns="<<s<<endl<<"k="<<k<<endl;
    
        cout<<"\nKlartext eingeben:";
        cin>>klartext;
        schritt=pow(klartext,s);
        ausgabe=schritt%k;
        cout<<"Geheimtext:"<<schritt;
    
        cin.ignore(1000,'\n');
        cin.get();
        return 0;
    }
    

    Danke im Voraus!

    Michael


  • Mod



  • 21012^{101} ist eine sehr hohe Zahl. Für sowas musst du dann schon GnuMP nehmen.

    Aber brauchst du das!?



  • Danke vorerst mal, ich schau mir das gleich an.
    Ja, ich brauche für die Verschlüsselung leider diese hohen zahlen.

    Die Formel lautet ja: a^b mod c

    da kann aber leider alles recht hoch sein.



  • Danke für den Link, aber wenn man kein Mathematikstudent ist, ist das schwer zu realisieren und verstehen, oder???

    Gibt es keine "einfachere" Methode wie ich eine hohe Zahl zur weiteren Rechnung mit Modul verwenden kann? Die Zahl muss ich mir gar nicht anzeigen lassen und das Endergebnis ist zum Vergleich recht klein.


  • Mod

    MichaelMAS schrieb:

    Danke für den Link, aber wenn man kein Mathematikstudent ist, ist das schwer zu realisieren und verstehen, oder???

    Wenn du es nicht verstehst, nun ja, dann kannst du kein RSA implementieren. Das die die Methode. Informatik (und damit indirekt programmieren) und Mathematik sind eben sehr nah verwandte Wissenschaften.

    Sone schrieb:

    21012^{101} ist eine sehr hohe Zahl. Für sowas musst du dann schon GnuMP nehmen.

    Sone, wie war das mit dem Ahnung haben? Er hat klar gesagt, wofür er das braucht. Eine MP-Bibliothek ist hier fehl am Platz.



  • Danke, wie gesagt, aber könntest du mir vielleicht noch etwas helfen, wie ich sowas einbauen kann in meinen Code???


  • Mod

    MichaelMAS schrieb:

    Danke, wie gesagt, aber könntest du mir vielleicht noch etwas helfen, wie ich sowas einbauen kann in meinen Code???

    In der Zeit kannst du unmöglich den Link und die dort weiterführenden Links durchgearbeitet haben und zu dem Schluss gekommen sein, dass du es nicht verstehst. Ich gehe daher davon aus, dass du dir den Link und die dort aufgeführten Beispiele (und Beispielimplementierungen!) gar nicht richtig angesehen hast und stattdessen bloß darauf wartest, dass jemand dir die fertige Lösung gibt.



  • MichaelMAS schrieb:

    Danke, wie gesagt, aber könntest du mir vielleicht noch etwas helfen, wie ich sowas einbauen kann in meinen Code???

    Such einfach mal nach RSA Implementierung C++



  • Hat geklappt!

    Ihr seid toll!
    Ist sogar recht einfach und ich kann auch weiterrechnen mit der Zahl!

    Danke für den Tipp.

    lg

    Michael

    Ich hoffe das habt ihr gemeint (Funktion pow definieren)

    int pow(int a, int b, int m)
    	{
    	    int res = 1 % m;
    	    for (; b; b /= 2)
    	        {
    	        if (b % 2)
    	            res = (res * a) % m;
    	        a = (a * a) % m;
    	    }
    	    return res;
    	}
    


  • MichaelMAS schrieb:

    Ich hoffe das habt ihr gemeint (Funktion pow definieren)

    int pow(int a, int b, int m)
    	{
    	    int res = 1 % m;
    	    for (; b; b /= 2)
    	        {
    	        if (b % 2)
    	            res = (res * a) % m;
    	        a = (a * a) % m;
    	    }
    	    return res;
    	}
    

    Jepp. Das ist der Square-and-Multiply-Algorithmus mit der Erweiterung für Modulo. Damit berechnest du "a hoch b modulo m". Allerdings kann hier m nicht besonders groß sein, da es sonst Überläufe gibt. Ich hoffe, du bist dir darüber im Klaren, dass so ein 'm' mindestens 1000 Bits groß sein muss, damit das mit der Sicherheit langsam anfängt. 😉


Anmelden zum Antworten