Skip Navigation
technology @hexbear.net PaX [comrade/them, they/them] @hexbear.net
Locked

The RSA Cryptosystem - New General Megathread for the 20th of September 2023

On this day in 1983, a patent was granted to MIT for a new cryptographic algorithm: RSA. "RSA" stands for the names of its creators Rivest, Shamir, and Adlemen. RSA is a "public-key" cryptosystem. Prior to the creation of RSA, public-key cryptography was not in wide use.

Public-key cryptography

Cryptography is the study and practice of secure communication. Throughout most of its historical use, cryptographic techniques were entirely dependent on the involved parties already sharing a secret that could be used to reverse an encryption process. In early cryptography, the secret was itself the encryption process (for example, a Caesar cipher that substitutes letters in a secret message with letters a fixed number of steps down the alphabet). As cryptography became more systematic and widespread in use, it became necessary to separate cryptographic secrets from the cryptographic techniques themselves because the techniques could become known by the enemy (as well as static cryptographic schemes being more vulnerable to cryptanalysis). Regardless, there is still the issue of needing to share secrets between the communicating parties securely. This has taken many forms over the years, from word of mouth to systems of secure distribution of codebooks. But this kind of cryptography always requires an initial secure channel of communication to exchange secrets before an insecure channel can be made secure by the use of cryptography. And there is the risk of an enemy capturing keys and making the entire system worthless.

Only relatively recently has this fundamental problem been addressed in the form of public-key cryptography. In the late 20th century, it was proposed that a form of cryptography could exist where the 2 parties, seeking to communicate securely, could exchange some non-secret information (a "public" key) derived from privately held secret information (a "private" key), and use a mathematical function (a "trap-door" function) that is easy to compute in one direction (encryption) but hard to reverse without special information (decryption) to encipher messages to each other, using each other's respective public keys, that can't be easily decrypted without the corresponding private key. In other words, it should be easy to encipher messages to each other using a public key but hard to decrypt messages without the related private key. At the time this idea was proposed there was no known computationally-hard trap-door function that could make this possible in practice. Shortly after, several candidates and cryptosystems based upon them were described publicly πŸ‘, including one that is still with us today...

RSA

Ron Rivest, Adi Shamir, and Leonard Adleman at MIT had made many attempts to find a suitably secure trap-door function for creating a public-key cryptosystem over a year leading up to the publication of their famous paper in 1978. Rivest and Shamir, the computer scientists of the group, would create a candidate trap-door function while Adleman, the mathematician, would try to find a way to easily reverse the function without any other information (like a public key). Supposedly, it took them 42 attempts before they created a promising new trap-door function.

As described in their 1978 paper "A method for obtaining digital signatures and public-key cryptosystems", RSA is based upon the principle that factoring very large numbers is computationally difficult (for now!). The paper is a great read, if you're interested in these topics. The impact of RSA can't be overstated. The security of communications on the internet have been dependent on RSA and other public-key cryptosystems since the very beginning. If you check your browser's connection info right now, you'll see that the cryptographic signature attached to Hexbear's certificate is based on RSA! In the past, even the exchange of symmetric cipher keys between your web browser and the web server would have been conducted with RSA but there has been a move away from that to ensure the compromise of either side's RSA private keys would not compromise all communications that ever happened.

The future of RSA?

In 1994, a mathematician named Peter Shor, developed an algorithm for quantum computers that would be capable of factoring the large integers used in the RSA scheme. In spite of this, RSA has seen widespead and increasing use in securing communications on the internet. Until recently, the creation of a large enough quantum computer to run Shor's algorithm at sufficient scale was seen as very far off. With advances in practical quantum computers though, RSA is on its way out. Although current quantum computers are still a very long way off from being able to break RSA, it's looking more and more plausable that someone could eventually build one that is capable of cracking RSA. A competition being held by the US National Institute of Standards and Technology, similar to the one that selected the Advanced Encryption Algorithm, is already underway to select standard cryptographic algorithms that can survive attacks from quantum computers.

Megathreads and spaces to hang out:

reminders:

  • πŸ’š You nerds can join specific comms to see posts about all sorts of topics
  • πŸ’™ Hexbear’s algorithm prioritizes comments over upbears
  • πŸ’œ Sorting by new you nerd
  • 🌈 If you ever want to make your own megathread, you can reserve a spot here nerd
  • 🐢 Join the unofficial Hexbear-adjacent Mastodon instance toots.matapacos.dog

Links To Resources (Aid and Theory):

Aid:

Theory:

402
402 comments
You've viewed 402 comments.