Simple RSA Encryption or Human-Calculable Encryption
by b3ard
At first glance, learning cryptography can be as tedious and time consuming as many other things in life, just as learning a new language can be difficult in getting familiar with the strange syntax.
There are different kinds of cryptographic methods, one of them being the RSA public-key cryptosystem. For a quick overview for those of you who aren't familiar with RSA, the RSA cryptosystem encrypts and decrypts messages/data by the use of public- and private-key pairs.
Public- and private-key pairs work like this: Bob and Sue have their own private and public keys.
Bob and Sue both generate their own unique key pairs (using a program like the open-source GnuPG), which each contain a public key and a private key. Bob doesn't know Sue's private key and vice versa; they only share their public keys.
Bob uses Sue's public key to encrypt a message. Sue's public key can be received in any number of ways, such as an online repository, in an email to Bob, or copy-pasted from Sue's website. Even a hardcopy print-out of Sue's public key would suffice in a pinch. Sue receives Bob's encrypted message, and uses her private key to decrypt the message encrypted by her public key.
In practice, public and private keys are generated by using large prime numbers, and by large I mean prime numbers that are over a hundred-digits long. But for quick and fast encryption when all you have is a pen, paper, and maybe a calculator, you will use extremely small prime numbers or "weak" keys to generate your cipher.
For those of you who are wondering why on Earth would we want to do something like this, it is because it really only works with the notion that those around us have no formal experience with cryptography, which means that there will virtually be no general or special purpose methods of attack against our cipher.
So where might this be effective? The work environment where Big Brother is always watching, prison as a get-out-of-jail-free card with the inmates by teaching them how they might communicate openly should you ever find yourself there, who knows. Where I am at currently, all electronic communication is constantly monitored, but not Post-its with numbers on them.
In getting started, the only tool that you may want is just a calculator that supports the modulus or "mod" function. Windows has a sufficiently advanced calculator and so do most Linux distributions, otherwise get ready for some mind-working, elementary long division, and multiplication. All the modulus function does is take the remainder of two numbers when divided into each other.
An example for clarity would be: 7 mod 5
5 goes into 7 one time with a remainder of 2 and thus: 7 mod 5 = 2
I will refer to the "modulus" result as the actual number that will be used in both keys and "mod" as the function when performing mathematical calculations.
With that, we will now choose two small prime numbers.
Continuing with our example numbers of 5 and 7, let:
Two other numbers we need are our modulus (also called N) and r.
We multiply both p and q to receive our modulus:
So, N = 35 and that will be our modulus for both our private and public key.
Note that the message chunks must not exceed the size of the modulus itself.
For r, let:
So, r = 24.
From here, we need to find two more numbers, e (encryption exponent) and d (decryption exponent), such that their product mod r is equal to 1, or in equation form:
The method we will use to generate e and d is:
What we are essentially doing here is reverse-engineering numbers whose modulus e and modulus d will be 1.
This gives us a list of candidates to then factor out, thereby obtaining e and d.
The list of candidates from r = 24 is: 25, 49, 73, 97, 121, 145
The list goes on, but 145 will do.
We'll let: k = 145
We now factor out k to obtain e and d, which is 5 and 29.
Let e = 29 and d = 5.
To double-check this, we plug e and d back into the previous equation:
which equal 1, so we're good.
The reason we did not pick any of the previous candidates is that we never want a number that, when factored, gives us a result of the same number.
An example would be 49, which results in 7 and 7.
This would leave us with the same public and private key, which isn't a good idea. Also, picking a prime number is no good, for obvious reasons (clue: you can't factor primes).
We now have our public and private keys: e = 29, d = 5, also expressed as:
The next step involves actual encryption, since we have our algorithm and the variables we need to generate the message.
Because it is impossible to multiply "A" by 5 (not counting hexadecimal), we need a substitution method for our letters in order to turn them into numbers.
It can be as simple as A = 1, B = 2, C = 3, and so on, but nonetheless this is important because the recipient of your encrypted message will need to know how to turn the decrypted numbers back into readable text.
The message we are going to encrypt will be just one word: problem
After substituting each letter for its number according to the simple substitution method mentioned above, we get:
Now we will use the RSA algorithm to encrypt and decrypt each number, using our public and private keys that we just made. Remember, in practice you would use your counterpart's public key, not your own. And he or she would use their own private key to decrypt the cipher.
To encrypt:
So we take the first number, 16, and raise it to the 5th power which is 1,048,576.
Then we apply mod N to this result, which gives us: 1,048,576 mod 35 = 11
By doing the same operation for all six remaining numbers our cipher: 11 23 15 32 17 10 13
And that's it - this is the encrypted message.
To decrypt:
Decrypting with our private key transforms our ciphered message back into its original form, which then can be substituted into its readable format:
Ideally, for this kind of fast and quick encryption method, announcing or publishing your public key in some wide open area is not recommended. At least not in the way conventional public keys are implemented or intended to be used.
Instead, including them in your cipher is much more effective for our purpose. This eliminates others (who might know a thing or two about ciphers) from easily cracking your cipher through factoring out your modulus, which would be extremely easy given such small numbers.
A way to do this is by including your public key at the end or beginning of each cipher, or just your first one to make it known to the recipient(s). Many other ways exist, but this is just one method to get the ball rolling.
In summary, remember to ensure that your p and q are prime and that your k factors out to two different numbers.
Break your message into chunks so that the message length is shorter than your modulus.
Also, remember: (e * d) mod r must equal 1, otherwise the cipher will not work.
A special thanks to l0j1k for giving me the idea and encouraging me to write this article.