C ++ manejando enteros muy grandes

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

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

Ahora que realmente es el único cálculo que estará haciendo. He intentado utilizar la Biblioteca BigInteger de Matt McCutchen, pero recibo muchos errores de comstackción durante la vinculación, como por ejemplo:

 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 manejar los enteros realmente grandes que surgen del algoritmo RSA.

Escuché que una posibilidad sería declarar tus variables como un doble largo, entonces …

 long long decryptedCharacter; 

pero no estoy seguro de cuán grande de un entero puede almacenar.


Bueno, por ejemplo, bash comstackr y ejecutar el siguiente progtwig 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; } 

entonces obtengo esos errores.

Derek, pensé que al incluir el archivo BigIntegerLibrary.hh , el comstackdor examinaría y comstackría todos los archivos necesarios que usaría.

¿Cómo debo tratar de comstackr el progtwig anterior para resolver los errores de enlace?

Meta-respuesta:

Si está utilizando una biblioteca para la aritmética de Bigint, pregúntese por qué no está utilizando una biblioteca para toda la implementación de 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.

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

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

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

Los errores de enlace que está obteniendo implican que está descuidando la comstackción de la fuente de BigInteger o que no incluye los archivos de objetos 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á comstackndo también estos archivos.

Para ver el tamaño de una prueba larga, prueba esto:

 #include  int main(void) { printf("%d\n", sizeof(long long)); return 0; } 

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

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.

Da la casualidad, 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.

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

Si no está implementando RSA como una tarea escolar o algo, entonces le sugiero que consulte la biblioteca de crypto ++ http://www.cryptopp.com

Es tan fácil implementar mal las criptografías.

Aquí está mi enfoque, combina la exponenciación rápida usando cuadratura + exponentació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); } } } 

Hay más para asegurar la implementación de RSA que solo grandes números. 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 imaginar extensiones y otras situaciones, por ejemplo, “¿qué ocurre si la clave privada que deseo utilizar no está en la 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: puede construir una implementación compatible con RSA a partir de enteros grandes, pero esto es más difícil de hacer correctamente de lo que normalmente parece, así que mi consejo es utilizar una implementación de RSA existente.

Probaría la biblioteca GMP : es robusta, está bien probada y se usa comúnmente para este tipo de código.

Openssl también tiene un tipo de 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 supiera, para encontrar la respuesta a la ecuación de esta forma x ^ y% z, busque 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.

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

Ver también esta pregunta en Stack Overflow

Revisa tu documentación del comstackdor. Algunos comstackdores tienen tipos definidos como __int64 que le dan su tamaño. Tal vez tienes algunos de ellos disponibles.

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 comstackdores de C ++. C ++ se basa en C89 (apareció en 98, por lo que no se podía basar en C99)

(C tiene soporte para ‘long long’ desde C99)

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

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

Usar mucho tiempo es definitivamente 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 el uso de la biblioteca mencionada para que podamos ayudarlo a resolver esos errores.

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

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