Re: The minimum RSA message size

Dmitry Sychov <dmitry.sychov@xxxxxxxxx> wrote:

RSA Masters!

I'am trying to figure out what should be the minimum acceptable
message length to encode for RSA-1024, RSA-2048 with e = 3;

If you mean text book RSA, where n is the modulus, solve the following
inequality for m:

m^e > n

If you want this in bits, solve for b:

(2^b)^e > n

For e = 3, this gives m > cbrt n or b > log (cbrt n) / log 2, where
'cbrt' is the cube root function.


so for RSA-1024 i guess it should be >= 11 bits, for RSA-2048 >= 13
bits

For RSA-1024 with a hypothetical modulus of 2^1023 (i.e. modelling
relatively small prime factors) I get >341 bits. For RSA-2048 with a
hypothetical modulus of 2^2047 I get >682.33 bits.

This assumes that the message is a string of b+1 bits, of which 1 is the
most significant digit and the rest are 0. This is of course not what
your messages are going to look like, so in general you won't want to
set a fixed lower limit.

Instead you need to test for each message, whether it wraps at the
modulus after exponentiation (i.e. whether m^e > n). If no, the message
is too small.


but what are the 'safe' numbers?

Your question alone suggests that you are using RSA incorrectly, which
is commonly known as 'text book RSA'. This is good for academia, but
not good for real world implementations. Have a look at padding schemes
like OAEP. Also consider using hybrid encryption.


internet search reveals nothing!

That's because the question is irrelevant to implementations. Using a
proper padding scheme you don't need to bother with message length.


Greets,
Ertugrul.


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/

.

Relevant Pages

  • Re: Speed/safety trade-offs and types vs. system classes
    ... (unsigned-byte 8), and no traps or errors either. ... You may be able to have this occur for certain implementations, ... the really lazy way to do this is to write your own macro to ... define these modulus operators. ...
    (comp.lang.lisp)
  • Re: Mod operator
    ... Some implementations of MOD work differently when the arguments have different ... The worksheet function uses the definition that the modulus is always ... divided by +3 is -3 with a remainder of -1. ...
    (microsoft.public.excel.programming)
Loading