C++ manejo de enteros muy grandes

Question

Estoy usando el algoritmo RSA para el cifrado/descifrado, y para descifrar los archivos tiene que lidiar con algunos valores bastante grandes. Más específicamente, cosas como

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

Este es realmente el único cálculo que haré. He intentado usar Biblioteca BigInteger de Matt McCutchen, pero estoy recibiendo una gran cantidad de errores de compilación durante el enlace, tales como:

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&)' 

Así que me preguntaba cuál sería la mejor manera de ir sobre el manejo de los realmente grandes números enteros que salir del algoritmo RSA.

oí que una posibilidad sería declarar las variables como un doble de largo, así que ...

long long decryptedCharacter; 

pero no estoy seguro exactamente qué tan grande de un número entero que puede almacenar.

---

Bueno, por ejemplo, trato de compilar y ejecutar el siguiente programa usando dev C++:

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

en cuando me siento esos errores.

Derek, pensé que al incluir el archivo BigIntegerLibrary.hh, el compilador realizaría y compilaría todos los archivos necesarios que usaría.

¿Cómo debo tratar de compilar el programa anterior para resolver los errores de enlace?

Answer 1

Un int largo suele ser de 64 bits, que probablemente no sea suficiente para manejar un número tan grande. Probablemente necesites una gran biblioteca de algún tipo.

Ver también this question desbordamiento de pila

Answer 2

Para ver el tamaño de un largo tiempo intente esto:

#include <stdio.h> 

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

    return 0; 
} 

En mi máquina devuelve 8, que significa 8 bytes que puede almacenar 2^64 valores.

Answer 3

Revise la documentación del compilador. Algunos compiladores tienen tipos definidos como __int64 que le dan su tamaño. Tal vez tienes algunos de ellos disponibles.

Answer 4

Solo para tener en cuenta: __int64 y long long son extensiones no estándar. Ninguno de los dos está garantizado para ser compatible con todos los compiladores de C++. C++ se basa en C89 (que salió en el 98, por lo que no podría basarse en C99)

(C cuenta con el apoyo de 'long long' desde C99)

Por cierto, no me creo que los enteros de 64 bits resuelven este problema.

Answer 5

Probaría la biblioteca GMP - es robusta, bien probada y comúnmente utilizada para este tipo de código.

Answer 6

Sugiero usar gmp, puede manejar ints arbitrariamente largos y tiene enlaces decentes de C++.

afaik en las longitudes largas de hardware/sofware actual son de 64 bits, por lo que sin signo puede manejar números hasta (2 ** 64) -1 == 18446744073709551615 que es un poco más pequeño que los números que tendría que tratar con RSA .

Answer 7

Para RSA necesita una biblioteca bignum. Los números son demasiado grandes para caber en un largo de 64 bits. Una vez tuve un colega en la universidad que recibió una asignación para implementar RSA, incluida la construcción de su propia biblioteca bignum.

Como sucede, Python tiene una biblioteca bignum. Escribir manipuladores de bignum es lo suficientemente pequeño como para caber en una tarea de ciencias de la computación, pero todavía tiene suficientes errores para que no sea una tarea trivial. Su solución fue usar la biblioteca de Python para generar datos de prueba para validar su biblioteca de bignum.

Debería poder obtener otras bibliotecas bignum.

Como alternativa, intente implementar un prototipo en Python y vea si es lo suficientemente rápido.

Answer 8

El hecho de que tenga un problema al utilizar una biblioteca biginteger no significa que sea un mal enfoque.

Usar long long definitivamente es un mal enfoque.

Como otros dijeron que el uso de una biblioteca biginteger es probablemente un buen enfoque, pero usted tiene que publicar más detalles sobre la biblioteca mencionada para que podamos ayudarlo a resolver esos errores.

Answer 9

Tomek, parece que no está enlazando correctamente el código de BigInteger. Creo que deberías resolver este problema en lugar de buscar una nueva biblioteca. Eché un vistazo a la fuente, y BigInteger::BigInteger(int) es definitivamente definido. Una breve mirada indica que los otros también lo están.

Los errores de enlace que está obteniendo implican que no está compilando el origen de BigInteger o que no incluye los archivos de objeto resultantes cuando realiza el enlace. Tenga en cuenta que la fuente de BigInteger utiliza la extensión "cc" en lugar de "cpp", por lo que debe asegurarse de que está compilando también estos archivos.

Answer 10

Meta-respuesta:

Si está utilizando una biblioteca para la aritmética BIGINT, a continuación, preguntarse por qué no está utilizando una biblioteca para toda la aplicación RSA.

Por ejemplo, http://www.gnu.org/software/gnu-crypto/ contiene una implementación de RSA. Tiene la misma licencia que GMP.

Sin embargo, no tienen la misma licencia que http://mattmccutchen.net/bigint/, que me parece que se ha puesto en el dominio público en los EE. UU.

Answer 11

Si no está implementando RSA como una tarea escolar o algo así, entonces yo sugeriría mirar el cripto ++ biblioteca http://www.cryptopp.com

Es tan fácil de implementar cosas cripto mal.

Answer 12

He tenido mucho éxito utilizando la biblioteca LibTomCrypt para mis necesidades de cifrado. Es rápido, delgado y portátil. Puede hacer su RSA por usted, o simplemente manejar las matemáticas si lo desea.

Answer 13

Openssl también tiene un tipo Bignum que puede usar. Lo he usado y funciona bien. Fácil de envolver en un lenguaje oo como C++ o Object-C, si lo desea.

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

Además, en caso de que no lo sabía, para encontrar la respuesta a la ecuación de esta forma x^y% z, buscar un algoritmo llamado exponenciación modular. La mayoría de las bibliotecas crypto o bignum tendrán una función específica para este cálculo.

Answer 14

Utilicé GMP cuando escribí la implementación de RSA.

Answer 15

Aquí está mi enfoque, combina una exponenciación rápida usando cuadratura + exponenciación modular que reduce el espacio requerido.

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 16

Hay más para asegurar la implementación de RSA que solo grandes cantidades. Una simple implementación de RSA tiende a filtrar información privada a través de canales laterales, especialmente el tiempo (en palabras simples: el tiempo de cálculo depende de los datos procesados, lo que permite a un atacante recuperar algunos, posiblemente todos, los bits de clave privada). Las buenas implementaciones de RSA implementan contramedidas.

Además, más allá de la exponenciación modular, está todo el negocio de relleno, que no es conceptualmente difícil, pero, como todas las E/S y el código de análisis, tiene espacio para errores sutiles. El código más fácil de escribir es el código que ya ha sido escrito por otra persona.

Otro punto es que una vez que tenga su código RSA en funcionamiento, puede comenzar a visualizar extensiones y otras situaciones, p. "¿Qué sucede si la clave privada que deseo utilizar no está en la memoria RAM sino en una tarjeta inteligente?". Algunas implementaciones de RSA existentes son en realidad API que puede manejar eso. En el mundo de Microsoft, desea buscar CryptoAPI, que está integrado en Windows. También puede consultar NSS, que es lo que usa el navegador Firefox para SSL.

En resumen: se puede construir una aplicación RSA-compatible de enteros grandes, pero esto es más difícil de hacer correctamente de lo que parece por lo general, por lo que mi consejo es utilizar una implementación de RSA existente.