Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How RSA Works: TLS Foundations

fly.io

Post reply on HN
Print view View original

31–38 of 38 posts

Re: How RSA Works: TLS Foundations

#31

Post by zaarn »

mabbo wrote: post #15

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 mist…

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

Re: How RSA Works: TLS Foundations

#32

Post by tzs »

mabbo wrote: post #15

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 mist…

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

Re: How RSA Works: TLS Foundations

#33

Post by hannob »

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.

Re: How RSA Works: TLS Foundations

#34

Post by valfadeev »

mabbo wrote: post #15

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 mist…

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

Re: How RSA Works: TLS Foundations

#36

Post by lou1306 »

sethgecko wrote: post #35

I just made a quick Python implementation (3.6+ only as it uses the secrets module) https://github.com/mcdallas/rsa

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

Re: How RSA Works: TLS Foundations

#37

Post by someguydave »

tptacek wrote: post #16
matahwoosh wrote: post #14

Earlier quoted context omitted.

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.

RSA is a bad idea in key exchanges as well.

One can generate session RSA keys that are signed with previous keys. That eliminates the forward secrecy objection to RSA, in my opinion.

Re: How RSA Works: TLS Foundations

#38

Post by mabbo »

mabbo wrote: post #15

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 mist…

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

Post reply on HN