Still a little new to programming so can't say too much here other than what I learned in my Discrete Math class about message encryption. Now keep in mind this is message encryption, not any sort of compression encryption or anything like that, but a simple encryption algorithm that used to be used by the CIA. I'll try to explain it to the best of my abilities.
/*-------------------BEGIN LESSON--------------------*/
The RSA Cryptosystem
This form of encryption is known as the RSA cryptosystem. The discovery of the system comes from two sources. It was believed to have been discovered by MIT researchers, but then the CIA released documentation that contained proof that they had actually discovered it first but did not reveal that they did because it added additional security to their messaging systems that used this algorithm. The system uses a public key and a private key. These keys usually contain large prime numbers as their basis for the algorithm. What prime numbers are used are completely up to the users, but generally something that needs to remain secret such as a CIA document uses prime integers that have a length of at least a hundred digits. However, due to integer limits on computers, you might have to deal with smaller prime numbers or alternative methods for computing large numbers. But trust me when I say that decrypting a message with just one, two, or three digit primes numbers is still a bitch. This algorithm also uses a lot of modular exponentiation, so make sure you brush up on your modulus division and exponential math.
Each encryption key consists of a modulus n = pq where 'p' and 'q' are large primes. There is also an exponent 'e' that is relatively prime to (p-1)(q-1). To produce a usable key, two large primes must be found. The idea behind these being so large is that the larger they are, the longer it takes for a computer program to factor these numbers out of the product of the two primes because it is only the product the public gets to see.
RSA Encryption
First change all letters into integers using a Caesar cipher (Example: a=0, b=1, c=2, ..., y=24, z=25) or a shift cipher which is a Ceasar cipher but with all the letter's numerical values shifted by a chosen integer. Now assuming the letter 'M' represents a integer that has yet to be encypted (aka plaintext) and C represents an integer that has been encypted (aka ciphertext), you should use the following function:
C = M^e mod n
Let me use the following example to illustrate how the encyption process works. I am going to encrypt the message STOP using RSA encryption. For this example I will set p = 43 and q = 59. So n = 43 * 59 = 2537, and e = 13. Note that gcd(e, (p-1)(q-1)) = gcd(13, 42 * 58) = 1 and gcd means "greatest common denominator." I translate the letters of STOP into their numerical equivalents and then group them into blocks of four. We get:
1819 1415
We now encrypt the message using the mapping:
C = M^13 mod 2537
Computations using modular multiplication show that 1819^13 mod 2537 = 2081 and 1415^13 mod 2537 = 2182. The message is now encrypted as 2081 2182 and is ready to be sent to the reciever to the message.
RSA Decryption
The plaintext message can be quickly recieved when the decryption key 'd' and an inverse of 'e' modulo (p-1)(q-1) is known. [Such an inverse exists because gcd(e, (p-1)(g-1)) = 1.] To see this, note that if de = 1 (mod (p-1)(q-1)), there is an integer 'k' such that de = 1 + k(p-1)(q-1). It follows that:
C^d = (M^e)^d = M^ed = M^(1+k(p-1)(q-1)) (mod n)
By a thing called Fermat's Little Theorem [assuming gcd(M, p) = gcd(M, q) = 1, which holds true except in rare cases], it follows that M^(p-1) = 1 (mod p) and M^(q-1) = 1 (mod q). Consequently,
C^d = M * (M^(p-1))^(k(q-1)) = M * 1 = M (mod p)
and
C^d = M * (M^(p-1))^(k(p-1)) = M * 1 = M (mod q)
Because gcd(p , q) = 1, it follows by something called the Chinese Remainder Theorem that
C^d = M (mod pq)
Now here is an example to explain all the shit I just said which was pretty much copied out of my discrete math book. The situation here is we received the message 0981 0461. We need to find the decrypted message. Now we will assume the cipher we are using hasn't changed from the encryption exercise above. So we used n = 43 * 59 and exponent 13. d = 937 is an inverse of 13 modulo 42 * 58 = 2436. I use 937 as my decryption exponent. Consequently, to decrypt a block C, we compute
P = C^937 mod 2537
To decrypt the message, we use the fast modular exponentation algorithm to computer 0981^937 mod 2537 = 0704 and 0461^937 mod 2537 = 1115. Consequently the numberical version of the original message is 0704 1115. Translating that back to English letters (assuming only a Caesar cipher was used) we see that the message is HELP.
/*--------------END LESSON----------------*/
Now for some of you kiddies, this might be a bit over your head, but if you understand the concept of modulus division and prime numbers, it shouldn't be too hard to get. My best advice is to try to follow the examples as best as possible.
