Berechnung von pow(a,b) mod n

Lesezeit: 7 Minuten

Berechnung von powab mod n
Moein Hosseini

Ich möchte a berechnenB Mod n zur Verwendung bei der RSA-Entschlüsselung. Mein Code (unten) gibt falsche Antworten zurück. Was ist daran falsch?

unsigned long int decrypt2(int a,int b,int n)
{
    unsigned long int res = 1;

    for (int i = 0; i < (b / 2); i++)
    {
        res *= ((a * a) % n);
        res %= n;
    }

    if (b % n == 1)
        res *=a;

    res %=n;
    return res;
}

  • -1: Haben Sie versucht, Ihren Code in einem Debugger schrittweise durchzugehen? Können Sie ein Beispiel geben, wo es schief geht?

    – Oliver Charlesworth

    13. Dezember 2011 um 21:08 Uhr


  • Was ist die Gruppierung Ihrer Operatoren?

    – Daniel A. Weiß

    13. Dezember 2011 um 21:09 Uhr

  • warum machst du nicht pow(a,b) % n?

    – Jeremy D

    13. Dezember 2011 um 21:11 Uhr

  • Scheinbar brauchst du % 2 anstelle von % n zuletzt if

    – Lol4t0

    13. Dezember 2011 um 21:15 Uhr

  • Für dieses Beispiel int überläuft, aber ein 64-Bit-Typ würde ausreichen. Wenn Sie sich jedoch ernsthaft für RSA entscheiden, benötigen Sie große Ganzzahlen, gmp wäre eine Option (und hat modulare Leistung).

    – Daniel Fischer

    13. Dezember 2011 um 21:17 Uhr

Berechnung von powab mod n
Hochofen

Sie können diesen C++-Code ausprobieren. Ich habe es mit 32- und 64-Bit-Ganzzahlen verwendet. Ich bin mir sicher, dass ich das von SO habe.

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

Sie finden diesen Algorithmus und die zugehörige Diskussion in der Literatur auf S. 244 von

Schneider, Bruce (1996). Angewandte Kryptographie: Protokolle, Algorithmen und Quellcode in C, zweite Ausgabe (2. Aufl.). Wiley. ISBN 978-0-471-11709-4.


Beachten Sie, dass die Multiplikationen result * base und base * base unterliegen in dieser vereinfachten Version einem Überlauf. Wenn der Modul mehr als die Hälfte der Breite beträgt T (also mehr als die Quadratwurzel des Maximums T Wert), dann sollte man stattdessen einen geeigneten modularen Multiplikationsalgorithmus verwenden – siehe die Antworten zu Möglichkeiten zur Modulo-Multiplikation mit primitiven Typen.

  • +1 (Ich wollte früher einen Kommentar hinterlassen) Das war sehr hilfreich für diese Frage. Es wäre großartig, die Originalquelle zu finden.

    – Shafik Yaghmour

    28. März 2014 um 9:52 Uhr

  • Aber was wenn modulus > sqrt(std::numeric_limits<T>::max())? In diesem Fall (result * base) kann überlaufen, und das Ergebnis wird falsch sein.

    – Ruud

    31. Mai 2014 um 14:09 Uhr

  • @RuudvA: Um dies zu vermeiden, können Sie diese Multiplikationen durch Ihre bevorzugte modulare Multiplikationsfunktion ersetzen. Zum Beispiel: Möglichkeiten zur Modulo-Multiplikation mit primitiven Typen

    – Hochofen

    31. Mai 2014 um 14:22 Uhr


  • T result = 1; –> T result = modulus > 1; oder result = 1%modulus damit richtig funktionieren modpow(x, 0, 1).

    – chux – Wiedereinsetzung von Monica

    15. Januar 2018 um 23:42 Uhr


  • Wie vermeidet dieser Code das Überlaufen des Bereichs von T bei der Berechnung von result * base und base * base?

    – Toby Speight

    6. Dezember 2018 um 13:06 Uhr

1646947813 699 Berechnung von powab mod n
Shubham Khatri

Um zu rechnen pow(a,b) % n für die RSA-Entschlüsselung verwendet werden soll, ist der beste Algorithmus, auf den ich gestoßen bin Primzahltest 1) das ist wie folgt:

 int modulo(int a, int b, int n){
    long long x=1, y=a; 
    while (b > 0) {
        if (b%2 == 1) {
            x = (x*y) % n; // multiplying with base
        }
        y = (y*y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

Weitere Einzelheiten finden Sie in der folgenden Referenz.


1) Primzahltest: Nichtdeterministische Algorithmen – Topcoder

  • Davon scheinst du auszugehen long long hat eine größere Reichweite als int. Weder in C noch in C++ gibt es eine solche Garantie, daher kann dieser Code immer noch überlaufen.

    – Toby Speight

    6. Dezember 2018 um 13:05 Uhr

Normalerweise ist es so etwas:

while (b)
{
    if (b % 2) { res = (res * a) % n; }

    a = (a * a) % n;
    b /= 2;
}

return res;

Der einzige tatsächliche Logikfehler, den ich sehe, ist diese Zeile:

if (b % n == 1)

was soll das sein:

if (b % 2 == 1)

Aber Ihr Gesamtdesign ist problematisch: Ihre Funktion führt O(b)-Multiplikationen und Modulo-Operationen durch, aber Ihre Verwendung von b / 2 und a * a impliziert, dass Sie darauf abzielten, O (log b) -Operationen durchzuführen (was normalerweise der Fall ist, wie die modulare Potenzierung durchgeführt wird).

Die Durchführung der Rohleistungsoperation ist sehr kostspielig, daher können Sie die folgende Logik anwenden, um die Entschlüsselung zu vereinfachen.

Von Hier,

Sagen wir nun, wir wollen die Nachricht m = 7 verschlüsseln,
c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13.
Daher der Chiffretext c = 13.

Um die Entschlüsselung zu überprüfen, berechnen wir
m’ = c^d mod n = 13^7 mod 33 = 7.
Beachten Sie, dass wir hier nicht den vollen Wert von 13 hoch 7 berechnen müssen. Das können wir uns zu Nutze machen
a = bc mod n = (b mod n).(c mod n) mod n
So können wir eine potenziell große Zahl in ihre Bestandteile zerlegen und die Ergebnisse einfacherer, kleinerer Berechnungen kombinieren, um den endgültigen Wert zu berechnen.

Eine Möglichkeit, m’ zu berechnen, ist wie folgt:
Beachten Sie, dass jede Zahl als Summe von Zweierpotenzen ausgedrückt werden kann. Berechnen Sie also zuerst die Werte von
13^2, 13^4, 13^8, … durch wiederholtes Quadrieren aufeinanderfolgender Werte modulo 33. 13^2 = 169 ≡ 4, 13^4 = 4,4 = 16, 13^8 = 16,16 = 256 ≡ 25.
Da 7 = 4 + 2 + 1 ist, haben wir dann m’ = 13^7 = 13^(4+2+1) = 13^4,13^2,13^1
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

  • Nun, das scheint der Algorithmus zu sein, den er zu implementieren versucht hat. Die Frage ist, was er falsch gemacht hat.

    – David Costa

    13. Dezember 2011 um 21:38 Uhr

1646947813 699 Berechnung von powab mod n
Shubham Khatri

Versuchst du zu rechnen (a^b)%noder a^(b%n) ?

Wenn Sie den ersten möchten, funktioniert Ihr Code nur dann B ist deswegen eine gerade Zahl b/2. Die “if b%n==1” ist falsch, weil es dich nicht interessiert b%n hier, sondern etwa b%2.

Wenn Sie die zweite wollen, dann ist die Schleife falsch, weil Sie eine Schleife machen b/2 mal statt (b%n)/2 mal.

In jedem Fall ist Ihre Funktion unnötig komplex. Warum machst du eine Schleife bis b/2 und versuchen, jedes Mal mit 2 a zu multiplizieren? Warum nicht einfach loop until B und jedes Mal in eins multiplizieren. Das würde viel unnötige Komplexität beseitigen und somit potenzielle Fehler ausschließen. Denken Sie, dass Sie das Programm schneller machen, indem Sie die Anzahl der Wiederholungen der Schleife halbieren? Ehrlich gesagt ist das eine schlechte Programmierpraxis: Mikrooptimierung. Es hilft nicht wirklich viel: Sie multiplizieren immer noch mit der gleichen Anzahl von Malen, alles, was Sie tun, ist, die Anzahl der Wiederholungen der Schleife zu reduzieren. Wenn b normalerweise klein ist (wie eine oder zwei Ziffern), ist es die Mühe nicht wert. Wenn b groß ist – wenn es in die Millionen gehen kann – dann ist dies unzureichend, Sie brauchen eine viel radikalere Optimierung.

Auch warum tun die %n jedes Mal durch die Schleife? Warum nicht einfach am Ende?

  • Nun, das scheint der Algorithmus zu sein, den er zu implementieren versucht hat. Die Frage ist, was er falsch gemacht hat.

    – David Costa

    13. Dezember 2011 um 21:38 Uhr

Berechnung von pow(a,b) mod n

  1. Ein Hauptproblem mit dem Code von OP ist a * a. Das ist int Überlauf (undefiniertes Verhalten) wenn a ist groß genug. Die Art von res spielt bei der Multiplikation von keine Rolle a * a.

    Die Lösung besteht darin, sicherzustellen, dass entweder:

    • die Multiplikation erfolgt mit 2x Wide Math bzw
    • mit Modul n, n*n <= type_MAX + 1
  2. Es gibt keinen Grund, einen breiteren Typ als den Typ von zurückzugeben Modul da das Ergebnis immer durch diesen Typ dargestellt wird.

    // unsigned long int decrypt2(int a,int b,int n)
    int decrypt2(int a,int b,int n)
    
  3. Verwenden ohne Vorzeichen Mathe ist sicherlich besser für die RSA-Ziele von OP geeignet.


Siehe auch Modulare Potenzierung ohne Bereichseinschränkung

// (a^b)%n
// n != 0

// Test if unsigned long long at least 2x values bits as unsigned
#if ULLONG_MAX/UINT_MAX  - 1 > UINT_MAX
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  unsigned long long result = 1u % n;  // Insure result < n, even when n==1
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (1ULL * a * a) %n;
    b >>= 1;
  }
  return (unsigned) result;
}

#else
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  // Detect if  UINT_MAX + 1 < n*n
  if (UINT_MAX/n < n-1) {
    return TBD_code_with_wider_math(a,b,n);
  }
  a %= n;
  unsigned result = 1u % n;
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (a * a) % n;
    b >>= 1;
  }
  return result;
}

#endif

  • Dies ist derzeit die einzige Antwort, die die Ursache des Problems identifiziert und eine geeignete Lösung vorschlägt. Die anderen Antworten unterliegen alle dem Überlauf.

    – Toby Speight

    6. Dezember 2018 um 13:03 Uhr

989040cookie-checkBerechnung von pow(a,b) mod n

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy