C++ im Umgang mit sehr großen ganzen Zahlen

Question

Ich verwende den RSA-Algorithmus für die Ver-/Entschlüsselung, und um die Dateien zu entschlüsseln, müssen Sie mit einigen ziemlich großen Werten umgehen. Genauer gesagt, mit Dingen wie

P = C^d % n
  = 62^65 % 133

Nun, das ist wirklich die einzigen Berechnungen, die ill tun werden. Ich habe versucht, mit Matt McCutchen's BigInteger Library, aber ich bin immer eine Menge von Compiler-Fehler während der Verknüpfung, wie:

encryption.o(.text+0x187):encryption.cpp: undefined reference to `BigInteger::BigInteger(int)'

encryption.o(.text+0x302):encryption.cpp: undefined reference to `operator<<(std::ostream&, BigInteger const&)'

encryption.o(.text$_ZNK10BigIntegermlERKS_[BigInteger::operator*(BigInteger const&) const]+0x63):encryption.cpp: undefined reference to `BigInteger::multiply(BigInteger const&, BigInteger const&)'

Also fragte ich mich, was wäre der beste Weg, um über den Umgang mit den wirklich großen ganzen Zahlen, die aus dem RSA-Algorithmus kommen zu gehen.

Ich habe gehört, dass es eine Möglichkeit wäre, die Variablen als double long zu deklarieren, also...

long long decryptedCharacter;

aber ich bin mir nicht sicher, wie groß eine ganze Zahl sein kann, die gespeichert werden kann.

---

Ich versuche zum Beispiel, das folgende Programm mit dev C++ zu kompilieren und auszuführen:

#include iostream

#include "bigint\BigIntegerLibrary.hh"

using namespace std;

int main()
{
    BigInteger a = 65536;
    cout << (a * a * a * a * a * a * a * a);
    return 0;
}

dann erhalte ich diese Fehler.

Derek, ich dachte, dass durch die Einbeziehung der BigIntegerLibrary.hh Datei, die der Compiler durchgehen und alle notwendigen Dateien kompilieren würde, die er verwenden wird.

Wie sollte ich versuchen, das obige Programm zu kompilieren, um die Verknüpfungsfehler zu beheben?

Answer 1

Tomek, es klingt wie Sie sind nicht die Verknüpfung mit der BigInteger-Code korrekt. Ich denke, Sie sollten dieses Problem beheben, anstatt nach einer neuen Bibliothek zu suchen. Ich habe einen Blick auf den Quellcode geworfen, und BigInteger::BigInteger(int) ist eindeutig definiert. Ein kurzer Blick zeigt, dass dies auch für die anderen gilt.

Die Link-Fehler, die Sie erhalten, deuten darauf hin, dass Sie entweder versäumt haben, den BigInteger-Quellcode zu kompilieren, oder dass Sie versäumt haben, die resultierenden Objektdateien beim Linken mit einzubeziehen. Bitte beachten Sie, dass der BigInteger-Quellcode die Erweiterung "cc" und nicht "cpp" verwendet, stellen Sie also sicher, dass Sie auch diese Dateien kompilieren.

Answer 2

Ich würde vorschlagen, dass Sie gmp Es kann mit beliebig langen Ints umgehen und hat anständige C++ Bindungen.

afaik auf aktueller Hardware/Sofware sind Longs 64bit, so dass unsigned mit Zahlen bis zu (2**64)-1 == 18446744073709551615 umgehen kann, was ein ganzes Stück kleiner ist als Zahlen, mit denen man bei RSA zu tun hätte.

Answer 3

Wenn Sie RSA nicht als Schulaufgabe oder ähnliches implementieren, dann würde ich vorschlagen, sich die crypto++ Bibliothek anzusehen http://www.cryptopp.com

Es ist einfach so einfach, Krypto-Zeug schlecht zu implementieren.

Answer 4

So können Sie die Größe eines langen Stücks sehen:

#include <stdio.h>

int main(void) {
    printf("%d\n", sizeof(long long));

    return 0;
}

Auf meinem Rechner wird 8 zurückgegeben, was 8 Bytes bedeutet, die 2^64 Werte speichern können.

Answer 5

Hier ist mein Ansatz, der eine schnelle Potenzierung durch Quadrierung mit einer modularen Potenzierung kombiniert, die den benötigten Platz reduziert.

long long mod_exp (long long n, long long e, long long mod)
{
  if(e == 1)
  {
       return (n % mod);
  }
  else
  {
      if((e % 2) == 1)
      {
          long long temp = mod_exp(n, (e-1)/2, mod);
          return ((n * temp * temp) % mod);
      }
      else
      {
          long long temp = mod_exp(n, e/2, mod);
          return ((temp*temp) % mod); 
      }
  }
}