How RSA Works: TLS Foundations

https://fly.io/articles/how-rsa-works-tls-foundations/?twitter

by rmdoss • 9 years ago

164 35 9 years ago

kss238• 9 years ago

Can someone explain this section some more

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.

goodroot• 9 years ago

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.

bogomipz2• 9 years ago

What is the rest of the context of the Golang code snippet in that that link?

matahwoosh7• 9 years ago

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!

blattimwind2• 9 years ago

RSA encryption has been shown time and time again to be a really bad idea, to the point that it was removed from TLS 1.3 early on.

AngeloAnolin• 9 years ago

Noticed that this page worked on Chrome, but not on FF.

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.

dguaraglia• 9 years ago

Same here.

EDIT: never mind, now it's giving the same error on Firefox too, only Safari works. Go figure.

mrkurt2• 9 years ago

This is CloudFlare helpfully preventing you from DDOSing Ghost. We're working on bypassing CF for our ghost stuff, sorry about that.

judge2020• 9 years ago

If you have extra page rules, the "disable security" tick on `https://fly.io/articles/*` may stop this kind of protection.

manigandham• 9 years ago

Try it without the "?twitter" querystring which looks to be cached: https://fly.io/articles/how-rsa-works-tls-foundations/

mabbo3• 9 years ago

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.

baby• 9 years ago

How can a prime number have any divisor that isn't 1

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)

mabbo3• 9 years ago

Yes, but why? Just saying "here's the algorithm" doesn't really explain why it works.

matahwoosh7• 9 years ago

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

userbinator• 9 years ago

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.

zaarn• 9 years ago

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.

[0] http://www.muppetlabs.com/~breadbox/txt/rsa.html

tzs• 9 years ago

>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.

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.

valfadeev• 9 years ago

I wrote up [0] and [1] a while ago as an attempt to understand RSA and Diffie-Hellman. While not perfect and certainly far removed from any real-world implementation, I still revisit these to remind myself of the basics. [0]: https://github.com/ValFadeev/ihaskell-notebooks/blob/master/... [1]: https://github.com/ValFadeev/ihaskell-notebooks/blob/master/...

mabbo3• 9 years ago

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.

https://en.wikipedia.org/wiki/Leonhard_Euler

orliesaurus• 9 years ago

interesting, these folks at fly.io sure put out a lot of content!

hannob• 9 years ago

A better title would be "How RSA does not work".

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.

sethgecko• 9 years ago

I just made a quick Python implementation (3.6+ only as it uses the secrets module)

https://github.com/mcdallas/rsa

lou1306• 9 years ago

Nice! I also did something similar during my basic crypto course.

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...

How RSA Works: TLS Foundations

Related Stories