How to work RSA encryption/decryption

Question

I need an array populated with characters and integer keys for each, and I want to, using this set, encode messages, and then decode them later on . Essentially I am trying to write RSA algorithm for this. However, the maths of it is what I am still kind of lost on. In order to encode, I would have to encode bits of the input string, and this after reading the corresponding key for each character, M.

     Ciphertext=0

     for i from 1 to length(message) do
         M:= ltable[message[i]] // Read the number that corresponds to the Character
        ciphertext:= ciphertext * ((M^encryptionkey) mod modfactor);//encode the returned number and add to ciphertext
    Loop next
       return ciphertext;

//To Convert all the input message at once, and then encode I have this algorithm
 ** for i from 1 to length(message) do
         M:= ltable[message[i]]//get the number that corresponds to character
        ciphertext:= ciphertext * M;//perform operation to update
    Loop next
       return ((ciphertext^encryptionkey) mod modfactor);**

i.e Ciphertext = M^e mod n where C is the resulting ciphertext, e is my encryption key and modfactor is the product of my primes.

The code above spews out my input message in an encrypted form. However, when I am to decode to resulting ciphertext, I run into some problem reversing the operations above to get the exact message that was sent as input to my encryption program. Essentially given a String of length 100, I encrypt each character of the input string with the above, but to reverse/decode, I don't seem to be getting the same message.

cipher = cyphertext; while cipher> 0 do rest = (cipher ^decryptionkey) mod modfactor message = concatenate(ntable[rest],message): wrk = (cipher/rest)/modfactor
End While

Return message

The code/algorithm above does not seem to work. Test primes used are p=263 and q=911, and encryptionkey= 27 How do I accomplish this please?

Answer 1

You're not supposed to encrypt one character at a time! You need to turn an entire message into a single number, and then perform the modulo exponentiation on that plaintext number to get the ciphertext number. Then you do the exponentiation with the private decryption key to reverse the process from the cipher to the plaintext, and then turn that number back into the message.

Answer 2

Well, here are the things you want to do:

1. Convert the plaintext string into a numeric plaintext.
2. Encrypt the numeric plaintext to produce a ciphertext.
3. Decrypt the ciphertext to produce the numeric plaintext again.
4. Convert the numeric plaintext back into a string.

Judging by your code, you are producing your numeric plaintext (which, for some reason, is called ciphertext) by taking all of the characters in the plaintext string and multiplying them together. That won't work, because multiplication is not injective: given a*b, it is impossible to tell what a and b are.

If you want to convert a string into a big number, do this:

Set num to 0.
For char in string:
    Shift num left by 8 bits.
    Add char to num.
End for.
Return num.

To convert it back:

While num > 0:
    Set char to (num mod 2^8).
    Prepend char to string.
    Shift num right by 8 bits.
End while.
Return string.

This algorithm only works if all of your characters are less than 2^8. If some of them aren't, replace 8 with a bigger number.

By the way, if your algorithm still doesn't work, try isolating the problem by skipping steps 1 and 4 entirely. If you can successfully encrypt and decrypt a number, that means steps 2 and 3 are working correctly, and so the problem lies in steps 1 and 4. If you can't, that means steps 2 and 3 are not working correctly, and so the problem lies there.