Cryptography and RSA
Alexander Richard Pierson
Math 89S
Professor Hubert Bray
1 November 2016
Abstract
This paper will begin with a brief overview of cryptography in general and the history of cryptography, because it is important to understand what it is on a fundamental level. The paper will then delve deeper into modern cryptography, especially symmetric key and public key cryptography, and cryptanalysis. There will be a brief discussion of RSA specifically and the RSA problem, reviewing some of the basic mathematics involved in this complex topic. Finally we will touch on Quantum cryptography and its impact on classical cryptography.
Cryptography is, essentially, the relaying of messages that cannot be interpreted into valuable information by someone who intercepts it. Cryptography works by first encoding a message, taking it from a readable, usable form into a jumble of useless data. Then the message is transmitted, and since it has been encoded, if it is intercepted the message would mean nothing to the person who intercepts it. After that, the message is decoded by whoever was meant to receive it. Cryptography, in this way, is a three-step process, and what allows it to work is that only the sender and recipient know how to encode or decode the messages.Cryptography has been used throughout history, primarily as a way of concealing military messages. The ancient Greeks used a device called a scytale, which was essentially a cylindrical rod, to encode messages. A piece of paper would be wrapped around the rod and written on so that each letter was on a different loop of paper and the message went down the rod and then continued around it. Then the paper was sent unraveled and it looked like a strip with a bunch of random letters on it. Only when the recipient wrapped the paper around a rod of the same size did the message come out looking right. The Romans used Caesar ciphers, in which messages were shifted a certain number of positions up or down the alphabet. This was very similar to the creation of modern cryptography, which works by replacing individual characters or bits of data with something else.
Modern cryptography relies on the use of keys, basically sets of rules that outline how to change certain characters to encode or decode messages. There are two main types of cryptography in such a way: symmetric key and public key. Symmetric key works by having one shared secret key that both the sender and recipient know and use. The diagram below shows an example of this:
This method is effective most of the time but not ideal because it assumes that both parties have a secure means of exchanging keys without anyone intercepting them. Keys have to be sufficiently long, as well, and have to be continuously generated to work properly and so no one can decipher the key, which is done by analyzing the frequency with which certain letters appear and finding connections between letters. The keys can be long and complicated, ensuring a very secure message, but in the end the keys must be distributed via some way, which is an inconvenience. This is where public key encryption comes into play. The diagram below details the message transmission process:
In this case, the eventual recipient of the message creates a key that allows anyone to encrypt a message, and has a specific way to decrypt the message, but such that the encryption key does not offer enough information as to how to decrypt the message. This encryption or “public” key is then transmitted as a completely open message for the sender (or anyone else) to receive. Now anyone can send encrypted messages but only the one person with the secret decryption key can decrypt them. And if multiple parties create such keys, then obviously messages can be sent back and forth without having any shared key. Public key cryptography was first proposed in 1976 by Whitfield Diffie and Martin Hellman, but they were unable to find any system for generating keys in such a way. Two years late Ronald Rivest, Adi Shamir, and Len Adleman became the first people to find an algorithm for public key encryption, and they called it the RSA algorithm, after the first letter of each of their last names.
RSA was just one of many techniques developed, as there were the Cramer-Shoup cryptosystem, ElGamal encryption, and numerous ways using elliptic curves. However, RSA became very widely used and as the first public key ecryption system it is very interesting. It is a complex algorithm that while not too difficult to understand for the context of this paper, it is certainly too long and relies on ideas that to explain would take a very long time and could even be a paper on their own. In essence, though, RSA relies on factorization of large numbers. The problem at the heart of RSA is that is quite simple to multiply numbers together to get a large number, but with very large numbers it becomes quite difficult to find their factors because you will be circling through so many numbers. In this way, with some clever use of modulus and primes, RSA uses this so create a key that can easily encrypt, but not so easily decrypt messages. This is a very effective way of transmitting information, but since the algorithm is complex, it takes a while to send data using it, so it is mostly used to send private keys that are then used to send longer messages or more information.
Quantum cryptography is a step beyond what has been done so far in public key encryption. Quantum key distribution is a method of sending keys that rely on quantum mechanical properties to be entirely random and completely secure. A sufficiently long quantum key has been mathematically proven to be a completely unbreakable code, but since quantum cryptography relies on the transmission and detection of single photons, it is very inconvenient to use at the current time. However, the future of practical cryptography may very well rely on quantum randomness.
Bibliography
Al-Kadi, Ibrahim A. (April 1992). "The origins of cryptology: The Arab contributions".Cryptologia.16(2): 97–126.doi:10.1080/0161-119291866801.
Calderbank, Michael (2007-08-20)."The RSA Cryptosystem: History, Algorithm, Primes"(PDF).
Ekert. A. Physical Review Letters, 67, pp.661-663, (1991)
Heisenberg, W. (1927), "Über den anschaulichenInhaltderquantentheoretischenKinematik und Mechanik", ZeitschriftfürPhysik (in German), 43 (3–4): 172–198, Bibcode:1927ZPhy...43..172H, doi:10.1007/BF01397280.. Annotated pre-publication proof sheet of Über den anschaulichenInhaltderquantentheoretischenKinematik und Mechanik, March 21, 1927.
Kahn, David(1967).The Codebreakers.ISBN0-684-83130-9.
Rivest, R.; Shamir, A.; Adleman, L. (February 1978)."A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"(PDF).Communications of the ACM.21(2): 120–126.doi:10.1145/359340.359342.
Rosenoer, Jonathan (1995). "CRYPTOGRAPHY & SPEECH".CyberLaw.
ArchivedDecember 1, 2005, at theWayback Machine.
Surender R Chiluka."Public key Cryptography".