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

21–30 of 38 posts

Re: How RSA Works: TLS Foundations

#21

Post by baby »

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…

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

Re: How RSA Works: TLS Foundations

#22

Post by bogomipz »

matahwoosh wrote: post #20
bogomipz wrote: post #17

Earlier quoted context omitted.

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

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 : GetCertificate: func(helloInfo *tls.ClientHelloInfo) (*tls.Certificate, error) { return myGetCertificateImplementation(checkClientSupportForECDSA(helloInfo)) } You would see what curves/ciphersuites are…

Thanks, cheers.

Re: How RSA Works: TLS Foundations

#23

Post by matahwoosh »

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…

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

Re: How RSA Works: TLS Foundations

#24

Post by wolf550e »

matahwoosh wrote: post #18
tptacek wrote: post #16

Earlier quoted context omitted.

RSA is a bad idea in key exchanges as well.

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?

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

Re: How RSA Works: TLS Foundations

#25

Post by matahwoosh »

wolf550e wrote: post #24
matahwoosh wrote: post #18

Earlier quoted context omitted.

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?

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

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/

Re: How RSA Works: TLS Foundations

#26

Post by mabbo »

baby wrote: post #21
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…

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

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

Re: How RSA Works: TLS Foundations

#27

Post by blattimwind »

matahwoosh wrote: post #14
blattimwind wrote: post #13

Earlier quoted context omitted.

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.

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

Re: How RSA Works: TLS Foundations

#28

Post by userbinator »

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…

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.

Re: How RSA Works: TLS Foundations

#29

Post by matahwoosh »

blattimwind wrote: post #27
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 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.

yeah, makes sense. I wanted to make sure you were talking about RSA key exchange in particular.
Post reply on HN