How RSA Works: TLS Foundations
fly.io
fly.io
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.
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
ϕ(n) = (p-1)(q-1)
e x d = 1 mod ϕ(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> 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.
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.
GetCertificate: func(helloInfo *tls.ClientHelloInfo) (*tls.Certificate, error) {
return myGetCertificateImplementation(checkClientSupportForECDSA(helloInfo))
}
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.
Also, do you have a good resource that explains the drawbacks of RSA key exchange in more details?
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...