RSA public key encrypts ASCII value to 0, how to decrypt?

4
votes

I've decided to learn about RSA encryption since learning about the vernal cipher in a comp sci lecture. I grasp the idea behind RSA (it's very clever), however while trying to write my own C program to encrypt and decrypt a string of characters I have run into a few problems.

I am encrypting each character's ASCII value using the public key then decrypting the cipher text. However, I have found that sometimes the public key I have created will encrypt an ASCII value to 0, then there is no way to decrypt it as 0^anything = 0. I surely must be wrong here as binary can be encrypted/decrypted using RSA.

E.g.

  • p = 3
  • q = 5
  • N = 15 (p*q)
  • m = (p-1)(q-1) = 8
  • e = 7 (coprime to m)
  • d = 7 (7d(mod8) = 1 ... Before people have a go, I am only using 7 because it's convenient for this example (not for a secure encryption)

Now take the char "T" (ASCII value 84)

Run the encryption, the cipher text is = 0

0^7 (mod 8) = 0 ... not 84!

Can someone point me in the right direction please.

Thanks in advance

1
encryptionrsa
The most obvious problem is that you're encrypting a string directly with RSA. You should encrypt a key for a symmetric cypher and use that symmetric cypher to encrypt the message. You should also use correct padding. – CodesInChaos
Also you can only apply RSA to integers 0<=i<N – CodesInChaos

1 Answers

4
votes

RSA encryption is limited to encrypting positive numbers in the range 1 to (p*q)-1, which are not multiples of p or q. In practical applications, p*q will generally be much bigger than the largest message to be encrypted, and messages will be padded with random bits to fill up the range 1 to (p*q)-1. While it's theoretically possible that the random padding chosen for a message might cause it to be a multiple of p or q, in practice the only way that can happen is if there is something severely wrong with the random number generator.

In "toy applications", however, problematic values represent a much larger portion of the possible message space. Even if you chose p and q to be large enough that the p*q was larger than your message (e.g. 13 and 17) there would still be many possible message values that would fail (e.g. 65 or 85). I would suggest 13 and 17 as reasonable values to use for demonstration purposes, with the caveat that not all message values will work.