Re: Maximum size of RSA message, was: Re: RSA Encrypt/Decrypt fails

[Guus Sliepen]

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

[Harry Whitehouse]

-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]