Cryptography
Cryptography is the art of disguising a message so that only its legitimate recipient could understand it. The message must first be encrypted by the writer so that it becomes disguised text, otherwise known as cipher text or a cryptogram. Then, the recipient must use a key to decrypt the cryptogram in order to recover the original message. Julius Caesar developed a simple cipher, an algorithm for performing encryption and decryption, in which he replaced each letter of the alphabet with a different one. For example, the letter A would be replaced in the message by the letter B, B would be replaced by C, etc. People throughout history, like Caesar, have utilized cryptography in order to protect important messages from being read by unwanted recipients.
With the invention of powerful computers, ciphers like Caesar’s have quickly become obsolete. Since there are more and more hackers searching for personal information today, the process of encrypting and decrypting a message must be more advanced. Today, the RSA algorithm is one of the most difficult-to-break ciphers, commonly used to protect online accounts. The RSA is a public key cryptosystem that was developed by three men, Ron Rivest, Adi Shamir, and Leonard Adleman in 1978. RSA receives its name from the initials of its inventors.
In a public key cryptosystem, two keys are utilized: a public key and a private key. Any person that wishes to send a message to the recipient would encrypt the message using the public key, and then the recipient would decrypt the message with his/her private key. With this method, the sender and the recipient in a public key cryptosystem do not have to agree on a shared key in order to decipher a cryptogram. The public key can be published so that anyone can conveniently send an encrypted message to the recipient. The private key is kept secret so unwanted recipients cannot decipher the message. Specifically, the RSA utilizes two different prime numbers, p and q. The product of the two primes, n, is the public key of the RSA, while p and q are essentially the private keys. The value of n can be made public to the world so that encrypted messages could be sent, but the values of p and q are kept secret so that the message can be decoded.
Why is the RSA algorithm so difficult to break? One only needs to factor n to find p and q. However, p and q tend to be primes that are over 100 digits in length. The amount of time and calculations to factor n would be overwhelming. However, it is not impossible. In 1986, an encryption key, named RSA-129 for its 129 digits, was broken after “only” eight months due to the advent of more powerful computers and new factorization methods. In comparison, using the factorization methods utilized just a decade earlier would have taken 40 quadrillion years. The security of the RSA relies on the difficulty of factoring n and finding p and q, since they are enormous numbers. As you will see, a great deal of math is involved in the process of creating a coded message and recovering the original message. The retrieval of a message can be a painstakingly long process if done by hand.
The RSA Cryptosystem
A Basic Overview
Utilizing the RSA incorporates three main components: key generation, encryption, and decryption. First the recipient will generate the public and private key pair. The public key would be published, while the private key is only known to the recipient. These keys will allow the sender and recipient to encrypt and decrypt messages, respectively. We must first find two very large prime numbers, p and q. It is virtually impossible for a person to accomplish this without the aid of computers. As we have already discussed, for a number n, n = pq. For the sake of simplicity, we will first use two small prime numbers:
Let p = 11 and q = 23
Thus n = 11 × 23 = 253
The next step is to determine m, which is the value of (p-1)(q-1). In this situation,
m = (p-1)(q-1)
m = (11-1)(23-1) = 10 × 22 = 220
Now we will choose a small number e, which is co-prime to m. This means that the greatest common divisor (or GCD) of e and 220 must be 1. The variable e essentially represents “encryption,” and will be featured as part of the public key.
e=2 GCD (2, 220) = 2
e = 3 GCD (3,220) = 1
We will use e = 3 since it is co-prime to 220.
The final value that we must determine is the integer d, featured in the decryption process of cipher text. It is defined as:
d = (1 + km) / e
In which k is any integer. We must utilize a value of k that will allow d to be an integer. Thus, we must substitute the known values of m and e, as well as integers starting at 0 and increasing by 1 for k.
k = 0: d = (1 + (0)(220)) / 3 = d = 1/3 (not an integer)
k = 1: d = (1 + (1)(220)) / 3 = d = 221/3 (not an integer)
k = 2: d = (1+(2)(220)) / 3 = d = 441/3 = 147 (integer)
When the value of k is 2, d = 147, an integer. In conclusion, we have determined that:
n = 253 m = 220 e = 3 d = 147
The public key includes the variables nand e, while the private key includes the variables n and d.
Now that we have determined the public and private keys, we can now move on to the components of encrypting and decrypting messages. The sender of a message wishes to encrypt it using the public key, but does not know the values of p and q, only the values of n and e. In this example we will encrypt the number “9.” The equation:
C = Pe % n
will be utilized, in which C represents the cipher text (encrypted text), P is the plaintext message (“9”), and e and n are values in the public key. The percent (%) symbol represents modular arithmetic. For example, 14 % 4 (14 modulo 4) is equal to 2 (the remainder of 14 / 4). In this equation, the plaintext is essentially encrypted by raising it to the “e” power, and then dividing it by “n.” The remainder of this division would be the value of C, the cipher text. The remainder represents the encrypted message itself, while the values of C, d, and n are basically irrelevant to the message.
C = Pe % n
C = 93 % 253
C = 729 % 253
C = 223
Therefore, the cipher text reads “223.”
The decryption process is similar to encryption, but features larger exponents. It is broken down into several steps that simplify each of the large exponents. The equation:
P = Cd % n
will be used to decipher the message, in which P is the plaintext, C is the cipher text (“223”), and d and n are values of the private key. The cipher text is deciphered by raising it to the “d” power and dividing it by n. The remainder of this division is P, the plaintext. Like the encryption process, the remainder represents the plaintext message.
P = Cd % n
P = 223147 % 253
The expression 233147 is much too large to calculate by hand or a normal calculator, so it must be simplified.
P = 223 * 223146 % 253
P = 223 * (2232)73 % 253
The expression 233146 is equivalent to (2232)73according to the exponent rules.
P = 223 * 4972973 % 253
P = 223 * (49729% 253)73 % 253
The expression (49729 % 253)73% 253 is equivalent to the expression 4972973 % 253. Thus, (49729% 253)73 = 14173. The entire process of simplifying the exponent is repeated until it is reduced to 1.
P = 223 * 14173 % 253
P = 223 * 141 *( 1412)36 % 253
P = 31443 * (19881 % 253)36 % 253P = 31443 * 14736 % 253
P = 31443 * (1472)18 % 253
P = 31443 * (21609% 253)18 % 253
P = 31443 * 10418 % 253
P = 31443 * (10816% 253)9 % 253
P = 31443 * 1909 % 253
P = 31443 * (1903)3 % 253
P = 31443 * (6859000 % 253)3 % 253
P = 31443 * 1703 % 253
P = 31443* 4913000 % 253
P = 9
“9” is the original plaintext that we had encrypted! Thus, this simple example of the RSA algorithm worked.
Without the aid of a computer, utilizing RSA cryptography to encrypt or decrypt messages is very difficult. However, attempting to break the RSA is next to impossible. Despite having knowledge of the public key (the values of n and e), it is extremely difficult to find a pair of prime numbers that can divide into n, which is hundreds of digits long in real practice. Using traditional factorization techniques could take quadrillions of years to accomplish this task. Therefore, recovering the original message is a simple task for those that know the keys, but an overwhelming obstacle for hackers and other unwanted recipients.
Sources
1. Coutinho, S. C. The Mathematics of Ciphers: Number Theory and RSA Cryptography. Natick, MA: A K Peters, Ltd. 1999. Print.
2. "Is the RSA Cryptographic Method Secure? More about Prime Numbers." Web. 27 Feb. 2011. <http://motivate.maths.org/moodle/mod/resource/view.php?id=420>.
3. Johnston, Paul A. "Cryptography: RSA: RSA Algorithm." Paj's Home. Web. 27 Feb. 2011. <http://pajhome.org.uk/crypt/rsa/rsa.html>.