I find the description of the RSA math pretty confusing. And I'm saying that with a minor in math and a CS degree specializing in security; I've don't this before, just not in a while.
For example:
>In order to generate e, we'll need to find a random prime number that has a greatest common divisor (GCD) of 1 in relation to ϕ(n).
How can a prime number have any divisor that isn't 1, let alone a gcd? Either that's mistaken, or it's unnecessary to state.
There's also no explanation of what purpose the totient value is. The author simply states it's needed, but not what value it provides.
In short, it feels like it's written for people who already know the answers, not for people trying to learn.
Here's my attempt at trying to explain what, at an abstract level, RSA is doing:
Imagine taking the powers of p mod n. If p and n have no common factor, then successive powers of p will take on all values less than n, in a sequence starting with 1, p, p^2, p^3, ... and eventually loop back to 1. There are exactly n values from 1...n, so the sequence loops back exactly after the nth power; in other words, p^n mod n == p, or p^(n-1) mod n == 1. This is known as Fermat's Little Theorem.
More colloquially, if you start with a number < n, and exponentiate it enough times mod n, you will get back to where you started. If you exponentiate it a fewer number of times, it will become some other number on this "circle", but you can then take that number and exponentiate it a further suitable number of times to get back to the original one. This is the RSA encryption and decryption, with the exponents being the public and private pieces of the key. The details of how those numbers are chosen involve more maths, but this is basically the principle of how RSA works.
Personally, I used [0] to learn most of what I know about RSA quite a while ago (I believe I was about 16 at the time) and found it a bit more approachable than the OP.
Fair point! I think that quote should read "a random coprime to [...] to ϕ(n)". Then it makes sense.
There's a lot of math behind RSA computation and we were trying to distill as much as we could, but it's not perfect. We have added a simple example to tie everything together, but it just means that you might have to plow thru the heavy bits first.
Now, the totient it needed to compute your encryption and decryption values. You start with getting 2 primes:
n = p * q
then you compute the totient:
ϕ(n) = (p-1)(q-1)
then you compute your encryption and decryption values:
e x d = 1 mod ϕ(n)
Then your private key will be be a pair (d, n) and public key will be (e, n).
Then, given that m is message and c is cipher:
Encryption
F(m,e) = m^e mod n = c
Decryption
F(c,d) = c^d mod n = m
One other thing that I just realized was bothering me about this: Euler is pronounced "Oy-ler" not "Yew-ler". The meme of Ben Stein made no sense to me until I realized the author didn't know how to pronounce that name right.
I'm a bit annoyed by many of these crypto introductions that explain textbook RSA, which is not something anyone uses in a real world application. It is crucial for RSA to use a padding mode and that's where all the fun comes in and what decides about how secure the thing you're building is.
It's not actually our CloudFlare site, unfortunately, we're proxying Ghost Pro through our service (so we can serve `/articles/` on the same hostname).
>Considering that we need a distinct key for each individual, that exchanging keys with each person would be a significant computational burden, and that there are more cryptographic functions needed than simply exchanging keys, new methods arose.
Isn't this exactly what RSA does, exchanging a private symmetric key with asymmetric crypto? The next paragraph makes it seem like RSA does something different.
Most excellent question, kss238. The next part in the series, which breaks apart the different parts of a TLS ciphersuite, was just published: http://fly.io/articles/how-ciphersuites-work/
It should answer your question, in similar spirits to that of this article. Thank you for reading and I wish you well.
It's most likely to be Fly-specific, but you could replicate this behavior with passing appropriate to tls.Config#GetCertificate (https://golang.org/pkg/crypto/tls/#Config). You could then have something like that :
You would see what curves/ciphersuites are supported by the client and check that against what you'd be supporting (if you use LE than that's more than likely going to be ECDSA with P-256). You would then return ECDSA cert (if one exist) for supporting clients and fallback to RSA certs. :boom: :D
you can also use RSA for actual encryption (like PGP) or for signing/verifying. ECDHE is better for key exchange, and ECDSA is better for signing/verifying. Check out goodroot's link!
what encryption are you talking about? IIRC, RSA has only been used for key exchange or authentication (sign/verify) in SSL/TLS. Even in the old days up to SSL 3.0, RC4 or (3)DES was used for actual (symmetrical) encryption.
SSL and TLS before 1.3 had a key exchange mode that used RSA encryption, without any DH, DHE, ECDHE, etc [1]. The client would generate a secret, encrypt it to the server's public key (from the certificate) and send that to the server. The server would decrypt it, compute shared secret key and continue.
Being able to decrypt was used to prove server has the private key for the certificate, instead of signature.
RSA was was thus used for both key agreement and authentication.
This of course has the problem of all recorded traffic can be decrypted after you get your hands on the certificate's private key, maybe after the certificate has expired and admins think the key is worthless.
This was known to be a bad idea and was removed from TLS 1.3. Some banks complained, they were told to escrow using ECDHE instead if they had to make the traffic decryptable by someone with a key for some reason.
"RSA key exchange" = "let me think about a secret and I'll encrypt it with your public key". In other words, the RSA cryptosystem does not have a key exchange operation.
tptacek: I think this sub-thread has been mainly to explain what RSA could be used for, not that it would be a good idea. On the side note, I have been positively surprised to see how many devices support ECDHE key exchange.
Also, do you have a good resource that explains the drawbacks of RSA key exchange in more details?
Very good point! I was thinking about other potential drawbacks, but this must be the biggest! We're talking about PFS in the next article - https://fly.io/articles/how-ciphersuites-work/
For example:
>In order to generate e, we'll need to find a random prime number that has a greatest common divisor (GCD) of 1 in relation to ϕ(n).
How can a prime number have any divisor that isn't 1, let alone a gcd? Either that's mistaken, or it's unnecessary to state.
There's also no explanation of what purpose the totient value is. The author simply states it's needed, but not what value it provides.
In short, it feels like it's written for people who already know the answers, not for people trying to learn.
Imagine taking the powers of p mod n. If p and n have no common factor, then successive powers of p will take on all values less than n, in a sequence starting with 1, p, p^2, p^3, ... and eventually loop back to 1. There are exactly n values from 1...n, so the sequence loops back exactly after the nth power; in other words, p^n mod n == p, or p^(n-1) mod n == 1. This is known as Fermat's Little Theorem.
More colloquially, if you start with a number < n, and exponentiate it enough times mod n, you will get back to where you started. If you exponentiate it a fewer number of times, it will become some other number on this "circle", but you can then take that number and exponentiate it a further suitable number of times to get back to the original one. This is the RSA encryption and decryption, with the exponents being the public and private pieces of the key. The details of how those numbers are chosen involve more maths, but this is basically the principle of how RSA works.
[0]: http://www.muppetlabs.com/~breadbox/txt/rsa.html
There's a lot of math behind RSA computation and we were trying to distill as much as we could, but it's not perfect. We have added a simple example to tie everything together, but it just means that you might have to plow thru the heavy bits first.
Now, the totient it needed to compute your encryption and decryption values. You start with getting 2 primes:
then you compute the totient: then you compute your encryption and decryption values: Then your private key will be be a pair (d, n) and public key will be (e, n).Then, given that m is message and c is cipher:
> How can a prime number have any divisor that isn't 1, let alone a gcd? Either that's mistaken, or it's unnecessary to state.
A prime is a divisor of itself. What it is in effect saying is "find a random prime number that is not a divisor of ϕ(n)".
I'm not sure why it is saying that, though, because RSA does not require e to be a prime number. It just requires that gcd(e,ϕ(n)) = 1.
The article is just poorly written, as can be seen by this sentence a little further down:
>> The e value is often made up; it's an arbitrary factor of both of your primes.
I cannot even begin to figure out where that came from.
https://en.wikipedia.org/wiki/Leonhard_Euler
What they mean by "gcd of 1 in relation to" is what we call "coprime".
5 and 3 are coprime because nothing but 1 divides both at the same time.
> what purpose the totient value is
it allows you to compute the private key out of the public key (only possible if the totient is coprime with the public key)
I'm a bit annoyed by many of these crypto introductions that explain textbook RSA, which is not something anyone uses in a real world application. It is crucial for RSA to use a padding mode and that's where all the fun comes in and what decides about how secure the thing you're building is.
On FF (57.0.2) Windows 7, the message is as below:
Error 1010 Ray ID: 3cc3b2b85d0b9300 • 2017-12-12 21:15:17 UTC Access denied What happened?
The owner of this website (fly-io.ghost.io) has banned your access based on your browser's signature (3cc3b2b85d0b9300-ua48).
Not sure if the author or website owner had a beef with FF.
EDIT: never mind, now it's giving the same error on Firefox too, only Safari works. Go figure.
>Considering that we need a distinct key for each individual, that exchanging keys with each person would be a significant computational burden, and that there are more cryptographic functions needed than simply exchanging keys, new methods arose.
Isn't this exactly what RSA does, exchanging a private symmetric key with asymmetric crypto? The next paragraph makes it seem like RSA does something different.
It should answer your question, in similar spirits to that of this article. Thank you for reading and I wish you well.
Being able to decrypt was used to prove server has the private key for the certificate, instead of signature.
RSA was was thus used for both key agreement and authentication.
This of course has the problem of all recorded traffic can be decrypted after you get your hands on the certificate's private key, maybe after the certificate has expired and admins think the key is worthless.
This was known to be a bad idea and was removed from TLS 1.3. Some banks complained, they were told to escrow using ECDHE instead if they had to make the traffic decryptable by someone with a key for some reason.
1 - https://tools.ietf.org/html/rfc5246#section-8.1.1
Also, do you have a good resource that explains the drawbacks of RSA key exchange in more details?
https://github.com/mcdallas/rsa
I'll just show my implementation of Wiener's attack, which shows that RSA can be super weak if you don't choose your private key with a grain of salt.
https://gist.github.com/lou1306/df1bfa60e247b4084149139a97da...