Splitting Messages for RSA
For your particular pair of RSA primes, there is a fixed size to the messages that can be encrypted with the product, n, of those primes. During decryption, you will always end up with the smallest positive integer message that satisfies the algorithm. That means that the value of your message has to be smaller than the value n to be unique. With a 1024 bit product of primes, you can only send a 1024 bit message. On the other hand, if the message value is too small, such that the modulus operation during encryption doesn't do anything, then cracking the message becomes much easier. This means that each message should be approximately the same size but slightly smaller than n. Like many other problems, this is a job for message chunking.
There is a defined standard for chunking RSA messages included in PKCS #1 (Public Key Cryptography Standard #1). There's been several versions of the standard due to discovered vulnerabilities. I'll use the original version since it's the simplest but obviously you should not be using this version in your applications today.
If your value of n is k-bits long, then each block is going to be k/8 bytes long. The contents of a block look like
0x00 0x02 padding 0x00 data
The 0x02 stands for the block type. We'll look at another block type tomorrow for use when signing messages instead of encrypting. The padding is then eight or more random non-zero bytes. The padding bytes prevents people from attempting to guess the original text and encrypting with the public key to check their guess. With padding, you would need to guess both the plain text and the random bytes, which can be made more expensive than attempting to crack the product of primes. During decryption, the padding is stripped off by starting from the third byte and scanning until the first non-zero byte. The data consists of the remaining bytes in the message.
The padding requirement means that there's a minimum of 11 bytes overhead in each chunk. For 1024 bit chunks, that works out to roughly 1 byte of overhead per 10 bytes of actual data.
Next time: Using RSA for Signing Messages
Comments
Anonymous
September 18, 2006
myITforum Daily Newsletter Daily Newsletter September 18, 2006 The myITforum.com newsletter is deliveredAnonymous
September 18, 2006
One of the key points made about the Diffie-Hellman algorithm is that it doesn’t actually allow you to...Anonymous
September 19, 2006
PingBack from http://blogs.msdn.com/drnick/archive/2006/09/19/761726.aspxAnonymous
September 27, 2006
This post is to tie up some loose ends in regards to actually performing the RSA computations. I've...Anonymous
October 17, 2006
This post is to tie up some loose ends in regards to actually performing the RSA computations. I've avoidedAnonymous
October 17, 2006
A nice property of RSA is that if we swap the role of the encryption and decryption keys, it's still