4 ms·

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 befo

by mabbo 9y 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 9y 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)
- mabbo 9y ago
  Yes, but why? Just saying "here's the algorithm" doesn't really explain why it works.
matahwoosh 9y 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 9y 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 9y 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 http://www.muppetlabs.com/~breadbox/txt/rsa.html
tzs 9y 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 9y 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/notebooks/rsa.ipynb https://github.com/ValFadeev/ihaskell-notebooks/blob/master/... [1]: https://github.com/ValFadeev/ihaskell-notebooks/blob/master/notebooks/ecc.ipynb https://github.com/ValFadeev/ihaskell-notebooks/blob/master/...
mabbo 9y 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 https://en.wikipedia.org/wiki/Leonhard_Euler

by mabbo 9y ago

baby 9y 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)

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

matahwoosh 9y 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 9y 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 9y 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 http://www.muppetlabs.com/~breadbox/txt/rsa.html

tzs 9y 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 9y 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/notebooks/rsa.ipynb https://github.com/ValFadeev/ihaskell-notebooks/blob/master/... [1]: https://github.com/ValFadeev/ihaskell-notebooks/blob/master/notebooks/ecc.ipynb https://github.com/ValFadeev/ihaskell-notebooks/blob/master/...

mabbo 9y 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 https://en.wikipedia.org/wiki/Leonhard_Euler