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

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 2

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); 
      }
  }
}

Answer 3

Zu einer sicheren RSA-Implementierung gehören mehr als nur große Zahlen. Eine einfache RSA-Implementierung neigt dazu, private Informationen über Seitenkanäle preiszugeben, insbesondere über die Zeit (in einfachen Worten: die Rechenzeit hängt von den verarbeiteten Daten ab, was es einem Angreifer ermöglicht, einige, möglicherweise alle Bits des privaten Schlüssels wiederherzustellen). Gute RSA-Implementierungen sehen Gegenmaßnahmen vor.

Über die modulare Potenzierung hinaus gibt es auch noch das ganze Padding-Geschäft, das konzeptionell nicht schwer ist, aber wie jeder E/A- und Parsing-Code Raum für subtile Fehler bietet. Der am einfachsten zu schreibende Code ist der Code, der bereits von jemand anderem geschrieben wurde.

Ein weiterer Punkt ist, dass Sie, sobald Sie Ihren RSA-Code zum Laufen gebracht haben, vielleicht beginnen, sich Erweiterungen und andere Situationen vorzustellen, z. B. "Was ist, wenn der private Schlüssel, den ich verwenden möchte, nicht im RAM, sondern auf einer Smartcard gespeichert ist?". Einige bestehende RSA-Implementierungen sind eigentlich APIs, die damit umgehen können. In der Microsoft-Welt möchte man nachschlagen KryptoAPI , das in Windows integriert ist. Vielleicht möchten Sie sich auch Folgendes ansehen NSS was der Firefox-Browser für SSL verwendet.

Kurz gesagt: Sie kann eine RSA-konforme Implementierung aus großen Ganzzahlen aufzubauen, aber das ist schwieriger, als es gewöhnlich scheint, daher rate ich, eine bestehende RSA-Implementierung zu verwenden.

Answer 4

Openssl hat auch eine Bignum Typ, den Sie verwenden können. Ich habe es verwendet und es funktioniert gut. Leicht zu wickeln in einer oo-Sprache wie C++ oder Objective-C, wenn Sie wollen.

https://www.openssl.org/docs/crypto/bn.html

Falls Sie es noch nicht wussten: Um die Antwort auf eine Gleichung der Form x^y % z zu finden, können Sie einen Algorithmus namens modulare Potenzierung nachschlagen. Die meisten Krypto- oder Bignum-Bibliotheken haben eine Funktion speziell für diese Berechnung.

Answer 5

Ein Long-Int hat in der Regel 64 Bits, die wahrscheinlich nicht ausreichen, um eine so große ganze Zahl zu verarbeiten. Sie werden wahrscheinlich eine bigint Bibliothek irgendeiner Art benötigen.

Siehe auch diese Frage auf Stack Overflow