Os algoritmos de criptografia assimétricos como RSA são limitados matematicamente na quantidade de dados que podem criptografar

Question

"Os algoritmos de criptografia assimétricos como RSA são limitados matematicamente na quantidade de dados que podem criptografar."

Eu lí essa informação no site msdn, mas mesmo entendendo como o RSA funciona, nao ficou claro quais limites matematicos seriam estes.

Gostaria que alguem pudesse me explicar quais limitações matematicas são essas.

Answer 1

Para isso vc tem que entender como funciona o metodo:

http://en.wikipedia.org/wiki/RSA_(algorithm)

Lembrando que RSA deve ser utilizado somente como auxiliar.. normalmente vc envia a chave de um outro tipo criptografia e nao a mensagem criptografada.

Att

---

William John Adam Trindade
Analyste-programmeur
----------------------------------------------------------

Sogi Informatique ltée

Answer 2

Ola William, obriado pela sua resposta.

Conforme eu havia mencionado, eu compreendo o RSA. Entretanto essa informação sobre limites matemáticos é o que não ficou exatamente claro. Eu não conheço outra fonte que cite isso alem do artigo msdn em questão e gostaria de uma resposta mais objetiva dizendo, estrita e sucinta, qual limitação matematica seria esta, especificamente.

Answer 3

A limitaçao é devida à transformaçao da mensagem string em um inteiro. Quando vc tem uma chave de 1024bits a saida maxima é 117 bytes, porque é a quantidade de bytes para se armazenar o maior inteiro com 1024bits (teoricamente seria 128, mas o RSA adiciona alguns blocos que consomem 11 bytes).

Segundo a explicaçao fornecida aqui (achei o mais simples):

"

A string is a contiguous sequence of symbols, so the string "cat" is a sequence of the letters 'c', 'a' and 't'. A bit string is sequence of binary digits (bits) '0' and '1'. A byte string is similar except it consists of bytes, which are in turn sequences of 8 bits. So a bit string and a byte string are the same thing, except the latter is restricted to multiples of 8 bits. For example, using hexadecimal representation, the byte string "8002EA" is a sequence of 3 bytes, 0x80, 0x02 and 0xEA; and is equal to the bit string "100000000000001011101010".

A string can be split into sub-strings (e.g. "8002" and "EA") and two strings can be concatenated (joined up) to make another string. The order of symbols is important. The usual convention is to write byte strings with the most significant byte first ("big-endian" or network byte order).

An integer is a whole number that obeys the usual rules of integer arithmetic (1+1=2, 5-2=3, 3x2=6, 6/3=2) and modular arithmetic (10+6≡4 (mod 12)). There is no limit in theory as to how large an integer can be: you can always add one to any integer. The integer 8,389,354 in decimal is the same as the number 0x8002EA in hexadecimal notation, but is not the same as the byte string "8002EA", even though it looks the same and may well be stored in your computer in the same form.

You can increment the integer 8389354 to get 8389354+1=8389355 (0x8002EB); but you cannot "increment" the byte string "8002EA". On the other hand, you can concatenate the byte strings "8002" and "EA" to make "8002EA"; but the integers 8389 and 354 do not add to make 8389354. The byte string "00008002EA" is strictly not the same as "8002EA"; but the integers 0x008002EA and 0x8002EA are equal.

With RSA encryption, we typically want to encrypt a session key which is a bit string, but the RSA arithmetic c = m^e mod n is done with integers, so we need to <dfn>represent</dfn> the bit string as an integer first (in practice, we usually add some random bytes and other padding, but we'll ignore that for the time being). Once the RSA operation has been completed, we have another integer, c, but we need to store the result as a bit string, so we <dfn>encode</dfn> the integer as a bit (byte) string and pass that string onto our recipient.

Example: Suppose we wish to encrypt the 3-byte/24-bit key bit string "8002EA" using the RSA public key (n=25009997=0x017D9F4D, e=5)^†. For simplicity in this insecure example, we will use the basic RSA algorithm with no padding.

1. The message block is the byte string "8002EA".
2. Compute the message representative

   m = StringToInteger("8002EA") = 8389354
   

3. Encrypt with the RSA algorithm

   c = 8389354^5 mod 25009997 = 2242555
   

4. Encode the result as a byte string

   OB = IntegerToString(2242555, 4) = 002237FB
   

Note that the maximum length of the output block is 4 bytes, because the largest possible integer result is 0x017D9F4C (= n-1), which requires 4 bytes to store in encoded form.

"

fonte:http://www.di-mgt.com.au/rsa_alg.html

Mas isso é citado em todas as fontes, mesmo na documentaçao oficial do RSA:

http://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf

att

---

William John Adam Trindade
Analyste-programmeur
----------------------------------------------------------

Sogi Informatique ltée