# Security of RSA for paranoids with padding?

RSA for Paranoids (RSAP) (in cryptobytes v3n1), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping computation cost moderate. It is getting renewed interest, as part of a lightweight authentication and key agreement protocol born as SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, paywalled with free extract), renamed ALIKE: Authenticated Lightweight Key Exchange (nice slides), and standardized in ISO/IEC 29192-4:2013 (paywalled with free extract).

RSAP is an asymmetric encryption algorithm, which I simplify to three parameters:

• the bit size $n$ of the public modulus $N=p\cdot q$;
• the bit size $\kappa$ of the private key modulus $p$;
• the odd public exponent $e$.

For key generation, it is drawn a random $\kappa$-bit prime $p$ with $\gcd(p-1,e)=1$; and a random prime $q$ such that $N=p\cdot q$ has $n$ bits and $\gcd(q-1,e)=1$. The public key is $(N,e)$, as in RSA. It is precomputed $d=e^{-1}\bmod(p-1)$ [that would be $dp$ in standard RSA]. The private key is $(p,d)$.

Except for a restriction that the message can be at most $\kappa-1$ bits, encryption in naked RSAP is as in naked RSA: $C=M^e\bmod N$. Decryption uses $M=C^d\bmod p$. That works because $C=M^e\bmod N$ implies $C\equiv M^e\pmod p$, that implies $M\equiv C^d\pmod p$ per Fermat's little theorem, and it holds that $M<2^{\kappa-1}<p$.

The main advantage of RSAP is that decryption is much faster than in RSA: compared to a CRT implementation of RSA with two primes of equal size $n/2$, the speed-up is by a factor of $\approx 2({n\over2\kappa})^3$ [that exponent assumes a classical multiplication algorithm]. That is at least twice faster when using the same modulus as our reference ($\kappa=n/2$); and up to $\approx250$ faster (for $n=5000,\kappa=500$, an aggressive parametrization considered in the original RSAP article).

Naked RSAP is vulnerable to a disastrous attack (in addition to those that plague naked RSA encryption): $N$ can be factored (and thus all security lost) if the plaintext $M$ corresponding to ciphertext $C$ chosen by the adversary leaks; for example if $M$ is the plaintext for ciphertext $C=(2^{\kappa})^e\bmod N$, then $p=2^\kappa-M$ (notice that this choice of $C$ ensures that the corresponding $M$ has at most $\kappa-1$ bits).

An obvious improvement (considered in SPAKE but dismissed as not proven secure) is to use random padding before encryption as in RSAES-OAEP or OAEP+, except parametrized so that the padded message $\tilde M$ has slightly less than $\kappa$ bits instead of slightly less than $n$ in RSA; and perform the corresponding redundancy check after decryption before using (and perhaps releasing) the deciphered message (with, even more than in RSA, the requirement that the check of padding on decryption must not leak information about what in the padding is wrong, e.g. by timing difference).

For a concrete example of parameterization: with $n=2048, \kappa=576, e=17$, the padding of RSAES-OAEP using SHA-1 hash for 576-bit modulus, we can transfer 240-bit messages (padded to 576-bit $\tilde M$ and enciphered to a 2048-bit cryptogram $C=\tilde M^e\bmod N$), but with decryption like 10 times faster than in RSA-CRT with standard 2048-bit modulus, and hopefully security about equivalent to that.

Questions:

1. Are there theoretical (implementation-independent) attacks more efficient than factoring the modulus?
2. Can we prove security of RSAP with padding under some assumptions?
3. What would be implementation attacks, and appropriate countermeasures?
4. How much can we lower $\kappa$ for a given $n$?

I have left aside some other tweaks and considerations:

• $n-\lambda$ bits in $N$ can be predetermined or a function of the holder's identity, in order to reduce the size of the public key certificate, for some parameter $\lambda$; that's the case in Shamir's RSAP and SPAKE/ALIKE.
• The message exponentiated can be reduced to $\gamma$ bits with $\gamma<\kappa$ (rather than $\gamma=\kappa-1$ in my simplified naked RSAP).
• The minimum $e$ depends on $n$ and $\gamma$; $e>2n/\gamma$ seems safe according to Shamir and my understanding of SPAKE/ALIKE.
• When an adversary can obtain extremely many public keys and would be content breaking any, we may need extra precautions; I'll make someone else made a separate question allowing an answer discussing this.
-
One could just apply naked RSAP to something chosen at random and use a random oracle's $\hspace{.68 in}$ value at that thing as a key, although this approach would increase the ciphertext overhead. $\hspace{.96 in}$ –  Ricky Demer Apr 15 at 2:12
@Ricky Demer: Yes. SPAKE/ALIKE use something reminiscent (the padded message is random then used to build AES-128 keys, concatenated with the encryption of zero with such a key). See the slides, they are interesting. –  fgrieu Apr 15 at 2:20
For the setting referenced in your last bullet, it would probably be better to use the random oracle's value at the pair that indicates $r^e$ and the modulus, rather than just at $r^e$. $\;$ –  Ricky Demer Apr 23 at 18:36
@Ricky Demer: I have trouble understanding your comment above. Is it referencing a setting where an adversary can obtain many public keys, or something else? What pair? –  fgrieu Apr 23 at 18:47
It is referencing what you guessed. $\:$ I also incorrectly wrote $r^e$ when I meant just $r$. $\;\;\;$ The pair whose elements are $r$ and $N$, which could be represented as $\:((N\cdot (N\hspace{-0.04 in}-\hspace{-0.05 in}1))/2)+r\;$. $\;\;\;\;\;\;$ –  Ricky Demer Apr 23 at 19:10