1
$\begingroup$

When RSA is used in a fashion where both the private key and the public key are both secret (for example, when the public key in a KEM is never leaked) could RSA be then evaluated as a symmetric cipher? And how would its security compare vs. standard symmetric ciphers such as AES?

Would a quantum computer for instance, be able to break such a ciphertext assuming existing known plaintext-ciphertext pairs? And if no such pairs are known?

$\endgroup$
2
  • 1
    $\begingroup$ Two things. 1. It is not clear to me what a KEM's public key is in the first place, as I've always viewed KEMs as interactive protocols (where the first message is generally ephemerally generated, e.g. not static). 2. If you are asking about using asymmetric crypto in a symmetric setting, it is generally much slower (think orders of magnitude) for no real benefit (security or otherwise). There are some settings where it may still make sense to do (say you want a private-key notion of FHE), but outside of those settings just use symmetric stuff imo $\endgroup$
    – Mark Schultz-Wu
    Feb 2 at 23:34
  • 3
    $\begingroup$ A KEM is just a PKE scheme that can encrypt only random payloads. So instead of $\textsf{Enc}(PK,M) = C$, you have $\textsf{Enc}(PK) = (C,M)$ -- i.e., the encryption algorithm chooses $M$ for you. As a result, $C$ can generally be smaller than if it needed to encode a specific choice of $M$. $\endgroup$
    – Mikero
    Feb 3 at 1:22

1 Answer 1

1
$\begingroup$

Assume RSA with modulus $n$ product of large secret distinct primes $p$ and $q$, large secret encryption and decryption exponents $e$ and $d$ with $e\,d\equiv1\pmod{p-1}$ and $e\,d\equiv1\pmod{q-1}$. Without loss of generality, assume $e,d\in\bigl[0,\operatorname{lcm}(p-1,q-1)\bigr)$ so that there are no equivalent keys.

Compared to a block cipher, RSA has serious functional issues:

  • Encryption and decryption is comparatively very slow (even if we use knowledge of the factorization of $n$ to speed up operations using the Chinese Remainder Theorem).
  • The message space $[0,n)$ does not map directly to bitstrings.
  • $0$ and $1$ are known stationary points (that is, are not changed by encryption). This is enough to break security under Chosen Plaintext Attack.
  • $E(x)\,E(y)\bmod n= E(x\,y\bmod n)$. This becomes a very serious issue if $n$ gets known.

Ways $n$ could get known:

  • If the cryptosystem allows submitting the plaintext $-1$, the corresponding ciphertext is $(-1)^e\bmod n=n-1$, and reveals $n$.
  • If the plaintext is validated to be in $[0,n)$ and no ciphertext is output otherwise (or some other distinguishable thing happens), that can be be used to find $n$ by bisection.
  • If we use cycling techniques to make both plaintext and ciphertext in $\bigl[0,2^{\lfloor\log_2 n\rfloor}\bigr)$, then timing or other side channel attacks tend to leak $n$ by bisection.
  • If instead we restrict plaintext to $\bigl[0,2^{\lfloor\log_2 n\rfloor}\bigr)$ on encryption and the ciphertext to $\bigl[0,2^{\lceil\log_2 n\rceil}\bigr)$ on decryption, we can find $n$ under chosen ciphertext attack as $n=2^{\lceil\log_2 n\rceil}-1-E(D(2^{\lceil\log_2 n\rceil}-1))$

Hiding $n$ is possible with symmetric cryptography, but that's drifting from the question.


Would a quantum computer for instance, be able to break such a ciphertext assuming existing known plaintext-ciphertext pairs?

That depends on the quantum computer. The currently existing ones can't do anything considered useful that a classical computer can't do for less. And there is no full blueprint for a Cryptographically Relevant Quantum Computer.

Yes with an hypothetical CRQC, if $n$ is of practical size and gets known, which is hard to avoid (see above). We can factor $n$, then using known plaintext/ciphertext pairs we can find $e$ and $d$ by solving discrete logarithm problems modulo $p$ and $q$, yielding $e$ and $d$ modulo $(p-1)$ and $(q-1)$, thus $e$ and $d$.

And if no such pairs are known?

Unless some characteristic of the plaintext is known, ciphertext-only attack is not possible regardless of computing mean, since RSA is a bijection on $[0,n)$.

It's hard to tell how redundant plaintext (e.g. English) could be exploited.


A variant of what the question proposes has been considered: the Pohlig-Hellman exponentiation cipher. It's like RSA, except $n$ is a large public safe prime, and $e$ and $d$ are secret (thus it's not public-key crypto). Compared to a block cipher, it has the same issues as listed above for RSA. That's probably why its not used in practice. And it fails to CRQC under known plaintext attack.

$\endgroup$
2
  • 1
    $\begingroup$ I noticed that finding n requires an active attack in all the cases you listed. Is it possible to find n when you only passively obtained plaintext-ciphertext pairs that you had no influence on? And plaintexts which were chosen entirely at random (as in a KEM). This seems like it would qualify as "Hiding n is possible with symmetric cryptography"? $\endgroup$ Feb 3 at 15:52
  • $\begingroup$ @JackieLanhorn: in standard RSA with small encryption exponent $e$, we can find $(n,e)$ from a few arbitrary $(\mathsf{plaintext}_i,\mathsf{ciphertext}_i)$ pairs because $n$ is the Greatest Common Divisor of the ${\mathsf{plaintext}_i}^e-\mathsf{ciphertext}_i$ (or a usually small multiple thereof) for correct $e$, and usually $1$ (or small) for a wrong guess of $e$. But in the question $e$ is large and secret, and I do not see how to recover both $e$ and $n$, even with access to an encryption oracle if it's restricted to e.g. $\bigl[0,2^{\lfloor\log_2 n\rfloor}\bigr)$. $\endgroup$
    – fgrieu
    Feb 3 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.