2
$\begingroup$

I have the following set-up:

Bob has an RSA Cryptosystem with a large modulus $n$ for which the factorization cannot be found in a reasonable amount of time. Alice sends a message to Bob by representing each alphabetic character as an integer between $0$ and $25$ (that is, $A ↔ 0$, $B ↔ 1$, etc.), and then encrypting each residue modulo 26 as a separate plaintext character.

I want to figure out how Oscar can easily decrypt a message in this case. However, I don't really understand how the encryption works here.

For RSA we have

$e_k(x)=x^b\bmod{n}$

But I don't understand what $b$ would be in this case and I don't fully understand what 'then encrypting each residue modulo 26 as a separate plaintext character' implies. Would this mean that each character is encrypted as

$e_k(x)=x^b\bmod{26}$?

$\endgroup$
3
$\begingroup$

Let's assume textbook RSA, which is not apparent from the question. In that case $b$ is the public exponent (usually this is $e$). So yes, encryption is then the first-to-last formula if $x$ is the index in the alphabet of the character. However, the $\bmod 26$ in the last formula doesn't need to be used; I think that the text is just used to indicate that $x$ is within the range $[0, 26)$. The word residue is out of place here; no division is performed on the alphabet, so there is no residue. The modulus for RSA encryption is just $n$.

There are many ways how this crypto system is vulnerable:

  1. textbook RSA is deterministic, so you can do frequency analysis of the ciphertext if the characters are encrypted separately;
  2. indices 0 and 1 (A and B) produce the values 0 and 1 after encryption;

but the main reason that this is insecure is that an attacker could just take the public exponent and then encrypt each character of the alphabet, creating a table from a specific ciphertext to a letter. After that you can iterate over find each ciphertext and replace it with the letter.

These attacks are not feasible if a good padding scheme such as RSA / OAEP is used.

$\endgroup$
  • 1
    $\begingroup$ Small note: even OAEP doesn't authenticate the message or protect the integrity (especially if it is applied multiple times). It just protects the confidentiality of the message. You need a signature over the messages before encryption and with a different key pair to add additional protection. $\endgroup$ – Maarten Bodewes Mar 25 '18 at 19:53

Your Answer

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