Berechnung von pow(a,b) mod n

Ich möchte a berechnen^B 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;
}

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.

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 ¹⁾ 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.

¹⁾ Primzahltest: Nichtdeterministische Algorithmen – Topcoder

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

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?

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