3
$\begingroup$

I'm sort of a beginner on cryptography so this is probably a really elementary question. I only know the historic ciphers and the general background on cryptography as well as it's general meaning. I'm just starting to dive into modern ciphers like RSA and DES.

When looking at RSA, aside from using different keys for encryption and decryption, it seemed to me that the encryption process is sort of like a substitution cipher or better the shift or caesar's cipher (since this one does some kind of math at least), and that it operates on the characters' Unicode or ASCII instead.

Is there any way in which I'm correct or is there any way that the RSA could be sort of like a shift cipher that operates on the coded text instead of the normal one? I'm probably not correct so if so could you tell me the ways by which it makes it different or unique? Thanks in advance!

New contributor
Sofonias Ayele is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
$\begingroup$

(in RSA) the encryption process is sort of like a substitution cipher...

That's the case in RSA encryption as explained in some introductory courses, where several small blocks of text are enciphered independently, often with a public modulus of only a few decimal digits (perhaps 2 to 8). RSA encryption as actually used works quite differently:

  • The public modulus is several hundred decimal digits; therefore, much more data is encrypted in a single chunk. That's necessary for security, for integers below $\approx300$ decimal digits (give or take a factor of two) are too easy to factor.
  • There most often is a single RSA chunk going thru the $x\mapsto x^e\bmod N$ public-key transformation in a given communication using RSA encryption. And that $x$ never is directly the plaintext that's actually encrypted.
  • Most often, $x$ is essentially a random value, then used as key to encipher the actual plaintext using a symmetric cipher. That's hybrid encryption. It is much more efficient in term of computing effort and ciphertext size, especially for large plaintext.
  • More rarely, $x$ is a combination of a short plaintext (few hundred bytes) and random data. The addition of randomness is critical for security: otherwise, it would be possible to verify a guess of the message. A modern RSA encryption scheme with random padding is RSAES-OAEP.
$\endgroup$
2
$\begingroup$

You are close but not exactly. In short, RSA is a trapdoor permutation.

Let $(n,e)$ is a RSA public key, then $y = f(x) = x^e \bmod n$ is a trapdoor permutation. RSA is a permutation since the function $f:\mathbb{Z}_n^*\to \mathbb{Z}_n^*$ is bijective.

RSA is a trapdoor permutation. Normally you can find the inverse a permutation if it is given explicitly. In RSA, however, given $x$ and the public key $(n,e)$, we can easily compute $f(x)$. If one is given a $y$ and the public key $(n,e)$, it is difficult to compute $f^{-1}(y)$. If one has the private key (the trapdoor), can compute $f^{-1}(y)$.

RSA is not a shift-cipher. Although, a shift-cipher is also a permutation, seeing a randomly generated 2048-bit RSA public key that acts like just a shift-cipher will amuse any cryptographer. Actually, this is not possible with small public exponents.

Like any permutation, for textbook RSA, one can write a table and store it, so that you can revert it very easily. The encryption oracle is free. However, there are problems with this;

  1. Today RSA requires at least 2048 or more bits to be secure. Therefore the table for the reverse permutation is infeasible. You cannot store it, however, you may perform short message attacks if textbook RSA is used. Generate all small short messages and compare them.
  2. Textbook RSA is not used in practice and should never be used. For encryption there are padding schemes like PKCS#1 v1.5 padding or Optimal Asymmetric Encryption Padding (OAEP). The former is hard to implement and has attacks occur, again and again, Bleichenbacher and Manger attack. PKCS#1 v1.5 padding has no security proof, however, OAEP has one. If one ever consider encrypting with RSA should consider OAEP. These paddings have random bits that prevent getting the same result for the same input. Therefore with these paddings, the RSA permutation is randomized.

In practice, RSA is not used for encryption. It can be used for;

$\endgroup$

Your Answer

Sofonias Ayele is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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