Larger RSA keys (Modulus bits > 16384)

[Jakob Bohm]

On 26/12/2021 16:21, Grégory Widmer via openssl-users wrote:
>
> Dear OpenSSL users,
>
> I have a question about OpenSSL. Recently, I asked myself if there was 
> a maximum bit length for the modulus of a RSA key.
>
> I tried to type :
>
> user at host:~$ openssl genrsa 32768
> Warning: It is not recommended to use more than 16384 bit for RSA keys.
>          Your key size is 32768! Larger key size may behave not as 
> expected.
> Generating RSA private key, 32768 bit long modulus (2 primes)
>
> I got this warning, and I wonder why a larger key size may behave not 
> as expected.
>
I don't know, but maybe it is a reference to other RSA libraries not working
with keys larger than 2 Kibibytes.  In particular the GPG documentation 
warns
that using larger RSA or DH keys is much less efficient in terms of security
overhead that they recommend ECC instead.

However only the author of that warning message can answer why they 
wrote it.
>
> Could anyone explain or give resources on why this doesn't work ?
>
> My guess is that, having the following : (M = message, C = Ciphered)
>
 > C = M^e ≡ n
 >
 > e = 65537
 >
 > n = p X q
>
> If M^e is < n, we could easily compute the original message ?
>
In general the formula is C = (M^e % n) also written as C ≡ M^e (mod n),
I am not sure why you used the ≡ congruence symbol as a modulus operator
(% in C, C++ etc. mod in many textbooks).

Also, many systems for using RSA pad M to enough bits that M^e > n, thus
ensuring that the modulo operation affects the result.  In particular,
both versions of PKCS#1 do that in different ways.  There was an
unfortunate ISO standard that forgot to do that and it was found to be
insecure.

For signing, the keys are swapped so S = (M^d % n) or S ≡ M^d (mod n),
where d is the secret key, while the recipient checks that M ≡ S^e (mod n)
or that M2 = (S^e % n) can be securely unpadded back to the actual M.


> Also, I want to apologize if my question is redundant, I tried to 
> search on GitHub and through the mailing list, but there is no search 
> feature in the mailing list.
>
> Have a nice day !
>
> Grégory Widmer
>
>
> PS : This question is for knowledge purpose only, I don't use RSA keys 
> anymore (except with GPG), I prefer ECC :)
>

-- 
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded