2600 Magazine_ The Hacker Quarterly - Digital Edition - Summer 2011 - 2600 Magazine [21]
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 printout 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 distros, otherwise get ready for some mind-working, elementary long division, and multiplication. All the mod 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 p=5 and q=7. Two other numbers we need are our modulus (also called N) and r. We multiply both p and q to receive our modulus. (p)(q) = modulus = N. 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 r = (p-1)(q-1). 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: ((e)(d) mod r) = 1. The method we will use to generate e and d is: (r+1), ((r+1)+r), (((r+1)+r)+r), etc. 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 ((e)(d) mod r) = 1, which ((29)(5) mod 24 does 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,