Re: Maximum size of RSA message, was: Re: RSA Encrypt/Decrypt fails
On Sun, Feb 25, 2001 at 08:04:55PM -0500, Greg Stark wrote: It is not a bug, it is a known fact. As Joseph Ashwood notes, you end up trying to encrypt values that are larger than the modulus. The documentation and most literature do tend to refer to moduli as having a certain "length" in bits or bytes. This is fine for most discussions, but if you are planning to use RSA to directly encrypt/decrypt AND you are not willing or able to use one of the padding schemes, then you'll have to understand *all* the details. One of these details is that it is possible to supply RSA_public_encrypt() with plaintext values that are greater than the modulus N. It returns values that are always between 0 and N-1, which is the only reasonable behavior. Similarly, RSA_public_decrypt() returns values between 0 and N-1. I have to confess I totally overlooked that and just assumed that if RSA_size(key) would be 1024, then I would be able to encrypt messages of 1024 bits. There are multiple solutions to this problem. A generally useful one is to use the RSA PKCS#1 ver 1.5 padding (http://www.rsalabs.com/pkcs/pkcs-1/index.html). If you don't like that padding scheme, then you might want to read the PKCS#1 document for the reasons behind that padding scheme and decide for yourself where you can modify it. It sounds like it be easiest if you just follow Mr. Ashwood's advice. Is there some problem with that? Yes well, upon reading the PKCS#1 v1.5 document I noticed that Mr. Ashwood solves this problem by not only making the most significant bit zero, but in fact the 6 most significant bits. I don't want to use one of the padding schemes because I already know the message size in advance, and so does a possible attacker. Using a padding scheme would therefore add known plaintext, which does not improve security. But thank you for the link! I think this solves my problem now :). --- Met vriendelijke groet / with kind regards, Guus Sliepen [EMAIL PROTECTED] --- See also: http://tinc.nl.linux.org/ http://www.kernelbench.org/ --- PGP signature
RE: Maximum size of RSA message, was: Re: RSA Encrypt/Decrypt fails
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Reddie, Steven Sent: Sunday, February 25, 2001 4:26 PM To: [EMAIL PROTECTED] Subject: RE: Maximum size of RSA message, was: Re: RSA Encrypt/Decrypt fails The message being encrypted/decrypted MUST be smaller than the modulus of the key. Think about the operation that takes place during encryption: c = m^e mod n where: m is the message to be encrypted, (n,e) is the public key (modulus and exponent) c is the ciphertext (encrypted output) The "mod n" results in the output value, c, being limited to a value in the range 0 to n-1 inclusive. If m is bigger than n then too much data will be thrown away by the modulo operation and it will not be possible to recover the original message. It is not just a matter of clearing the top bit of the message. The message must be a smaller value than the modulus. Steven -- Steven Reddie [EMAIL PROTECTED] Senior Software Engineer Computer Associates Pty Ltd (Australia) -Original Message- From: Guus Sliepen [SMTP:[EMAIL PROTECTED]] Sent: Monday, February 26, 2001 3:55 AM To: [EMAIL PROTECTED] Subject: Maximum size of RSA message, was: Re: RSA Encrypt/Decrypt fails On Wed, Feb 14, 2001 at 02:44:02PM -0800, Joseph Ashwood wrote: Just a guess, but a fairly educated one, try setting flen to 1 byte (or even 1 bit) smaller than the key. What I suspect is happening is you are sometimes trying to encrypt values that are larger than the modulus so you're getting a modular reduction of the value encrypted. Joe I'm having a similar problem. For authentication and key exchange purposes, I generate a random string which is exactly as long as my RSA key is. Then I encrypt it without padding (since the message it is totally random noise and just used once). However, the message is not decrypted properly on the other end when the first bit of the plaintext was set. Why is this? Nowhere in documentation or literature can I find that the first bit should not be set. Is this a bug in OpenSSL? Or is this a known fact? __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED] __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: RSA Encrypt/Decrypt fails
Jan Zoellner wrote: At 15.02.01 13:04, you wrote: point of using RSA if not ?, so I will insist once again on the fact that you SHOULDN'T do that. I reimplemented the whole thing to be padded with random data (which are discarded upon decryption). PKCS#1 padding is worse than that, if I interpret the source correctly. It sounds much better. If your protocol _ever_ sends the same data block to two different recipients, you are dead and buried. Different recipients dont matter: The data is privately encrypted and can be read by many recipients, all having posession of the same public key. (Symmetric or hybrid cryptography is not applicable.) Data is never sent to different recipients, as there is only one (at least from the viewpoint of used keys). You are right, I spoke a bit too fast. What's more, the attack I was refering to, as someone made me notice already, requires "e" messages, not 2, so it's more difficult to do if you use a large e, like 65535. I remembered how I was told of an actual implementation, not using padding, that could be broke this way very easily, but it sounds like it used e=3. __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
RE: RSA Encrypt/Decrypt fails
PKCS#1 padding type 1 pads with 0xff bytes, and padding type 2 pads with random data (terminated with a 0x00 byte). You probably observed that RSA_eay_public_encrypt uses padding type 2 (random data), though RSA_eay_private_encrypt uses padding type 1. Since "RSA encryption" typically means encrypting with a public key (not a private key as in your case), then this implementation does use random padding bytes. You're encrypting with a private key which is not usually done other than for a signing operation. I'm guessing that RSA_eay_private_encrypt uses padding type 1 since this function isn't intended for encrypting data, just signing it, because data that can be decrypted with a "public" key isn't really secure. Steven -- Steven Reddie [EMAIL PROTECTED] Senior Software Engineer Computer Associates Pty Ltd (Australia) -Original Message- From: Jan Zoellner [SMTP:[EMAIL PROTECTED]] Sent: Friday, February 16, 2001 12:13 AM To: [EMAIL PROTECTED] Subject: Re: RSA Encrypt/Decrypt fails I reimplemented the whole thing to be padded with random data (which are discarded upon decryption). PKCS#1 padding is worse than that, if I interpret the source correctly. __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
RE: RSA Encrypt/Decrypt fails
At 16.02.01 01:52, you wrote: I'm guessing that RSA_eay_private_encrypt uses padding type 1 since this function isn't intended for encrypting data, just signing it, because data that can be decrypted with a "public" key isn't really secure. Youre right about that. The main goal is indeed providing authenticity (without the need for a real digital signature, but MACs wont do), the encryption being a nice add-on effect. Im reimplemented it with my own padding (random data), which I shouldve done from the beginning indeed. That still wouldve sent me into the modulo trap, though. :) Ciao Jan __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: RSA Encrypt/Decrypt fails
At 15.02.01 18:19, you wrote: What's more, the attack I was refering to, as someone made me notice already, requires "e" messages, not 2, so it's more difficult to do if you use a large e,like 65535. Ive read this post as well. Thanks for all the info, guys, the code is now working as intended and is probably secure enough. Ciao Jan __ OpenSSL Project http://www.openssl.org User Support Mailing List[EMAIL PROTECTED] Automated List Manager [EMAIL PROTECTED]
Re: RSA Encrypt/Decrypt fails
Just a guess, but a fairly educated one, try setting flen to 1 byte (or even
1 bit) smaller than the key. What I suspect is happening is you are
sometimes trying to encrypt values that are larger than the modulus so
you're getting a modular reduction of the value encrypted.
Joe
- Original Message -
From: "Jan Zoellner" [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Sent: Wednesday, February 14, 2001 2:25 PM
Subject: RSA Encrypt/Decrypt fails
Hello,
I have a problem for which I found no real solution in the manual or the
list archives.
The basic idea is to encrypt data using RSA_private_encrypt and retrieve
it
using RSA_public_decrypt. For RSA_private_encrypt, I set flen to
RSA_size()
to encrypt just one block and decrypt it later. If there is more data, it
is processed blockwise in a loop.
RSA_NO_PADDING is used (yeah, I know one shouldnt do that). For most
blocks, the decryption works fine. For some block it just doesnt work. I
dont get any error reports, the decrypted data just isnt what it should
be.
Below you find an excerpt from the code (some NULL checkings and the like
omitted). What am I doing wrong? Once again: There is no overlapping
memory
or the like, the process functions properly in most cases, but in some
cases (it seems to be depending on the data actually!) the routine fails,
either at encryption or decryption (or even both?).
Ciao
Jan
// get key
rsaStruct = PEM_read_RSAPrivateKey(fp, NULL, NULL, password);
// srcLen is original length given as a function parameter
unsigned long destLen = srcLen;
// Now pad to correct block size, resulting in a destination length of
// N*RSA_size()
unsigned long blocklength = RSA_size(rsaStruct);
destLen = (((destLen - 1)/ blocklength) + 1) * blocklength;
// create destination array
dest = new unsigned char[destLen];
memset(dest, 0, destLen);
// create source array
unsigned char *tmpSrc = new unsigned char[destLen];
memset(tmpSrc, 0, destLen);
// copy original source data, result is an array of correct length
containing
// the source and trailing zeroes
memcpy(tmpSrc, src, srcLen);
// now encrypt blockwise
for (unsigned long i = 0; i destLen; i+= blocklength) {
if (blocklength!=RSA_private_encrypt(blocklength, (tmpSrc+i),
(dest+i), rsaStruct, RSA_NO_PADDING)) {
printf("RSA Encrpytion Error.\n");
delete [] dest;
delete [] tmpSrc;
return 0;
}
}
// and now decrypt the data again
// array to contain the decrypted data
unsigned char *tmpDest = new unsigned char[destLen];
for (i = 0; i destLen; i+= blocklength) {
if (blocklength!=RSA_public_decrypt(blocklength, (dest+i),
(tmpDest+i), rsaStruct, RSA_NO_PADDING)) {
printf("RSA Decryption Error.\n");
delete [] dest;
delete [] tmpDest;
delete [] tmpSrc;
return 0;
}
}
--
Jan Zoellner - VidSoft GmbH
eMail: [EMAIL PROTECTED] - Tel: ++49 351 435 34 17
WWW: http://www.vidsoft.de
__
OpenSSL Project http://www.openssl.org
User Support Mailing List[EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
__
OpenSSL Project http://www.openssl.org
User Support Mailing List[EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
