C ++ tratando inteiros muito grandes

Eu estou usando o algoritmo RSA para criptografia / descriptografia e, a fim de descriptografar os arquivos que você tem que lidar com alguns valores muito grandes. Mais especificamente, coisas como

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

Agora, esses são realmente os únicos cálculos que estão fazendo. Eu tentei usar BigInteger Library de Matt McCutchen, mas estou recebendo um monte de erros de compilador durante a vinculação, tais 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&)' 

Então eu queria saber qual seria a melhor maneira de lidar com os inteiros realmente grandes que saem do algoritmo RSA.

Ouvi dizer que uma possibilidade seria declarar suas variables ​​como um double long, então …

 long long decryptedCharacter; 

mas eu não tenho certeza exatamente quão grande de um inteiro que pode armazenar.


Bem, por exemplo, eu tento compilar e executar o seguinte 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; } 

então eu recebo esses erros.

Derek, eu pensei que incluindo o arquivo BigIntegerLibrary.hh , o compilador iria passar e compilar todos os arquivos necessários que ele usaria.

Como devo tentar compilar o programa acima para resolver os erros de vinculação?

Meta-resposta:

Se você estiver usando uma biblioteca para a aritmética bigint, pergunte-se por que você não está usando uma biblioteca para toda a implementação do RSA.

Por exemplo, http://www.gnu.org/software/gnu-crypto/ contém uma implementação RSA. Tem a mesma licença que o GMP.

No entanto, eles não têm a mesma licença que http://mattmccutchen.net/bigint/ , que me parece ter sido colocada em domínio público nos EUA.

Eu sugiro usar gmp , ele pode manipular arbitrariamente longos ints e tem ligações C ++ decentes.

afaik no hardware / sofware atual long longs são 64bit, então unsigned pode manipular números até (2 ** 64) -1 == 18446744073709551615, o que é um pouco menor do que os números que você teria que lidar com o RSA.

Tomek, parece que você não está ligando para o código BigInteger corretamente. Acho que você deve resolver esse problema em vez de procurar uma nova biblioteca. Eu dei uma olhada na fonte, e BigInteger::BigInteger(int) está definitivamente definido. Um breve relance indica que os outros também estão.

Os erros de link que você está obtendo implicam que você está negligenciando a compilation da origem do BigInteger ou negligenciando include os arquivos de object resultantes ao vincular. Por favor, note que o código fonte do BigInteger usa a extensão “cc” ao invés de “cpp”, então tenha certeza que você está compilando estes arquivos também.

Para ver o tamanho de um longo tempo tente isto:

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

Na minha máquina, ele retorna 8, o que significa 8 bytes, que podem armazenar 2 ^ 64 valores.

Para o RSA, você precisa de uma biblioteca bignum. Os números são muito grandes para caber em um longo período de 64 bits. Certa vez, tive um colega na universidade que conseguiu uma tarefa para implementar a RSA, incluindo a construção de sua própria biblioteca bignum.

Quando isso acontece, o Python tem uma biblioteca bignum. Escrever manipuladores bignum é pequeno o suficiente para caber em uma atribuição de ciência da computação, mas ainda tem dicas suficientes para torná-lo uma tarefa não trivial. Sua solução foi usar a biblioteca Python para gerar dados de teste para validar sua biblioteca bignum.

Você deve conseguir outras bibliotecas bignum.

Como alternativa, tente implementar um protótipo no Python e veja se ele é rápido o suficiente.

Se você não estiver implementando o RSA como uma tarefa da escola ou algo assim, sugiro consultar a biblioteca crypto ++ http://www.cryptopp.com

É tão fácil implementar coisas de criptografia mal.

Aqui está a minha abordagem, combina exponenciação rápida usando quadratura + exponenciação modular que reduz o espaço necessário.

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

Há mais para garantir a implementação da RSA do que apenas grandes números. Uma simples implementação RSA tende a vazar informações privadas através de canais secundários, especialmente o tempo (em palavras simples: o tempo de computação depende dos dados processados, o que permite que um invasor recupere alguns, possivelmente todos, os bits de chave privados). Boas implementações RSA implementam contramedidas.

Além disso, além da exponenciação modular, há todo o negócio de preenchimento, que não é conceitualmente difícil, mas, como todo código de E / S e análise, tem espaço para bugs sutis. O código mais fácil de escrever é o código que já foi escrito por outra pessoa.

Outro ponto é que uma vez que você tenha seu código RSA funcionando, você pode começar a imaginar extensões e outras situações, por exemplo, “e se a chave privada que eu quero usar não estiver na RAM, mas em um cartão inteligente?”. Algumas implementações RSA existentes são, na verdade, API, que podem lidar com isso. No mundo da Microsoft, você deseja pesquisar o CryptoAPI , que está integrado no Windows. Você também pode querer olhar para o NSS , que é o que o navegador Firefox usa para SSL.

Resumindo: você pode construir uma implementação compatível com RSA a partir de inteiros grandes, mas isso é mais difícil de fazer do que o que normalmente parece, então meu conselho é usar uma implementação de RSA existente.

Eu experimentaria a biblioteca GMP – ela é robusta, bem testada e comumente usada para esse tipo de código.

Openssl também tem um tipo Bignum que você pode usar. Eu usei e funciona bem. Fácil de embrulhar em uma linguagem oo como C ++ ou object-C, se você quiser.

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

Além disso, caso você não saiba, para encontrar a resposta para a equação desta forma x ^ y% z, procure um algoritmo chamado exponenciação modular. A maioria das bibliotecas crypto ou bignum terá uma function específica para este cálculo.

Um long int normalmente é de 64 bits, o que provavelmente não seria suficiente para manipular um inteiro tão grande. Você provavelmente precisará de uma biblioteca bigint de algum tipo.

Veja também esta pergunta no Stack Overflow

Confira sua documentação do compilador. Alguns compiladores têm tipos definidos, como __int64, que fornecem o tamanho deles. Talvez você tenha alguns deles disponíveis.

Apenas para observar: __int64 e long long são extensões não padrão. Nenhum deles é garantido para ser suportado por todos os compiladores C ++. C ++ é baseado em C89 (ele foi lançado em 98, então não poderia ser baseado em C99)

(C tem suporte para ‘long long’ desde C99)

By the way, eu não acho que os inteiros de 64 bits resolver este problema.

O fato de você ter um problema usando uma biblioteca de bigintegers não significa que é uma abordagem ruim.

Usando muito tempo é definitivamente uma má abordagem.

Como outros já disseram que já está usando uma biblioteca biginteger é provavelmente uma boa abordagem, mas você tem que postar mais detalhes no haw você usa a biblioteca mencionada para podermos ajudá-lo a resolver esses erros.

Eu usei o GMP quando escrevi a implementação do RSA.

Eu tive muito sucesso usando a biblioteca LibTomCrypt para minhas necessidades de criptografia. É rápido, enxuto e portátil. Ele pode fazer o seu RSA para você, ou apenas lidar com a matemática, se quiser.