eli5 can someone explain to me what the RSA algorithm in cybersecurity is please
In: 7
The [Wikipedia article](https://en.m.wikipedia.org/wiki/RSA_(cryptosystem)) does a pretty good job
An RSA user creates and publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers are kept secret. Messages can be encrypted by anyone, via the public key, but can only be decoded by someone who knows the prime numbers
It is an encryption algorithm. It takes a message, plus a key, performs some mathematical operations on it, and you get an encrypted message.
It’s notable in that it is a form of *asymmetric* encryption meaning you must use a different key to decrypt it; the key used to encrypt it won’t work.
It relies on a number of different mathematical principles to achieve this effect while remaining secure, but each of those would constitute their own ELI5 posts. But an overview of the process is this:
1. You choose two large prime numbers: p and q.
2. You calculate n = p * q
3. You calculate lambda(n) which is equal to the least common multiple of p-1 and q-1.
4. You choose an integer, e, such that e is greater than 1, less than lambda(n) and shares no factors with lambda(n).
5. You choose an integer, d, such that d * e, when divided by lambda(n), gives you a remainder of 1.
The public key (the key typically used for encryption) consists of n and e. To encrypt a message, M, you would convert it into a number, raise it to the power of e, then find the remainder if it was divided by n^(*). This gives you the cipher text C.
The private key (the key typically used for decryption) consists of n and d. To decrypt you would take your cipher text C, raise it to the power of d, then find the remainder if it was divided by n^(*). This gives you back your original message, M.
The magic works based on how d and e are related with respect to lambda(n), but, again, is it’s own ELI5 post. But the strength of the algorithm rests on an attacker not being able to figure out d. But since lambda(n) is based on n (or, rather, its factors of p and q) and since an attacker knows e and n, if the attacker was able to figure out p and q, it could figure out lambda(n) and therefore d. This is why we use large primes as p and q: it makes n extremely difficult to factor. It would take modern computers many many years to factor the n’s of the sizes we use today.
^(*) ^(this is a simplification. Computers don’t actually take the message or cipher text, raise it to e or d, then divide by n and look at the remainder. The numbers involved are simply too large. Rather there are a number of mathematical shortcuts and simplifications computers use to get to that answer.)
The RSA algorithm is a public-key cryptography algorithm that is used in many different applications, including securing communications and digital signatures. It is named after its inventors, Ron Rivest, Adi Shamir, and Len Adleman.
RSA works by using a large prime number to generate a public and private key pair. The public key can be used to encrypt messages, and the private key can be used to decrypt them.
To encrypt a message, the sender first generates a random number, called a “session key.” This key is then used to encrypt the message using a symmetric-key algorithm, such as AES. The encrypted message and the session key are then both encrypted using the recipient’s public key.
To decrypt the message, the recipient first decrypts the session key using their private key. They can then use the session key to decrypt the message using the symmetric-key algorithm.
It’s one of the most popular asymmetric encryption algorithms. This means that each sender / recipient creates 2 sets of keys. The private key (which they keep private) and the public key (which they share with others).
If I want to send you an encrypted message I would encrypt the message with your public key. Then you would decrypt it with your private key. When you want to reply to me you would encrypt with my public key and I would decrypt with my private key.
Any eavesdropper would not be able to decrypt the message with just the public key. So the message remains secure.
For this to work the public and private keys need to be related but it should be mathematically prohibitively difficult (practically impossible with today’s technology) to derive the private key from the public key. The way this works is by using trap door mathematical functions. In other words calculations that are really easy to do in one direction but really difficult to do in reverse such as multiplying to very large prime numbers together.
This is an oversimplification but it’s also ELI5. Also I’d be lying if I told you I fully understand the mathematics behind it in a detailed level, just a high level understanding of the underlying principle.
Latest Answers