# How to work RSA encryption/decryption

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?

-
You have to compute $\text{cipher}^{\,d}$ mod $n$ where $d=e^{-1}$ mod $\varphi(n)$ is the decryption key. Could you point out more specifically what "some problem" is? – anon Mar 5 '12 at 12:31
I do have my encryption and decryption keys worked out. The problem is the how of encryption and then decryption the message input, I mean the algorithm for encryption 1 character at a time and then decryption to yield each character at a time. – Kobojunkie Mar 5 '12 at 12:35
The problem is that your message is way bigger than your modfactor, so even without encryption if you turned the message into a number and then reduced modulo pq and then turned back into a string of characters, you'd get something different. – anon Mar 5 '12 at 13:18
That is why I had it encoding my information one character at a time initially. If I have an input that hundreds of lines long, I still would like to be able to handle that without needing to keep looking for bigger and bigger prime numbers each time. – Kobojunkie Mar 5 '12 at 13:50
I see. I imagine you're supposed to break the message into pieces, each piece as big as possible without letting the corresponding number go over modfactor - though the primes involved still preferably large. I'm not the go-to guy for details on the protocol though, sorry. – anon Mar 5 '12 at 14:04

## 2 Answers

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.

-
when I convert all my message at once, I get this cipher = 230958. How then do I decode this using my code above? That remains a problem. – Kobojunkie Mar 5 '12 at 12:56
@Kobojunkie: How are you turning strings of characters into numbers, first of all? Just concatenating bits together? If so, after you compute the cipher, the math in your code is correct in that you take it to the power of the decryption key modulo modfactor. After that, you would split the digits up into pieces and convert each piece into a character. I can't vouch for your code or what protocol you're using because I'm only familiar with the number theoretic aspects of RSA.. – anon Mar 5 '12 at 13:02
I have a table/array where each character has a number assigned. So whenever I look up the character in my array, I return the number that corresponds and then perform operations on the number that way. When I go to decode, I get the number, check the table for the character that corresponds to it and concatenate that to be decoded plaintext. – Kobojunkie Mar 5 '12 at 13:03
The problem is in mainly decoding the ciphertext so I can get back the code for the initial ciphertext at least. How do I get back M=14891505242871484726569672376320000000000000 from the ciphertext=230958. That is what I am having problems with, at the moment. – Kobojunkie Mar 5 '12 at 13:07
@Kobo: Okay. How do you put the numbers for each character of the message together? In RSA, the message as a whole becomes one single number. (Or are you doing some strange RSA-lite problem as an exercise you were given? Encrypting each character independently seems a rather pointless substitution cipher..) | Edit: How about you give the values for modfactor as well as encryptionkey and decryptionkey and if possible the message in the OP? (Plus the prime factors of modfactor wouldn't hurt either...) – anon Mar 5 '12 at 13:07

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.

-
I am not working with the bits or able to shift bits. Like I explained, I have an array with random numbers assigned to unique characters, and using that information, I need to encrypt my string. And then decrypt afterwards. – Kobojunkie Mar 5 '12 at 20:03
Shifting left by $n$ bits is the same as multiplying by $2^n$; and shifting right by $n$ bits is the same as dividing by $2^n$ and rounding down. – Tanner Swett Mar 6 '12 at 4:07