RSA Encryption | 01 | Introduction to RSA¶
Cyber security is becoming increasingly important in the world, as well as increasingly newsworthy. We send important data over the internet on a regular basis, and the mechanisms that keep us secure are essentially unknown to the typical user. In fact, most people do not consider internet security until they hear of a recent security breach. In order to understand the underlying system, I decided to implement my own RSA algorithm and then crack it for fun!
Brief History¶
The RSA system is named after its "official" creators, Ron Rivest, Adi Shamir, and Leonard Adleman, who published their work in 1977. However, an equivalent system was created by English mathematician Clifford Cocks, but his work was not known until 1997 when it was declassified by the British government.
System Overview¶
RSA is a public-key cryptosystem, giving it a fairly novel implementation. A typical cryptosystem would have a secret key that the sender and receiver would both use in order to encrypt and decrypt some data. Unfortunately, when communicating over the internet, how does one securely send a secret key without already having a secure connection?!
A public-key system uses two keys that are generated together and mathematically linked. One key is known as the public key and is openly shared to everyone. The public key is used to encrypt data, but cannot decrypt it. The second key is the private key as is never known to anyone except the keyset creator. Once the keyset creator receives the encrypted data, he/she can decrypt it with the private key.
Interestingly, the private key can be used to encrypt data, allowing only the public key to decrypt it. This initially seems useless, but it can be used to ensure that a message did originate from a particular source.
Mathematics¶
The primary characteristic that keeps RSA systems secure is their use of very large prime numbers. The algorithms that allow the encryption and decryption of data can be circumvented if the keys can be separated into their smaller factors. By using prime numbers in their generation, there is only one possible factoring solution, and by keeping these values large, there is no practical way to find these factors without basic brute force techniques.
Let's get cracking!