3 ms·

Show HN: Arithmetic on elliptic curves in Ruby

16 points by nmc 13y ago

mauricioc 13y ago
(I only read the very first function from the implementation, so I apologise for the overly-specific comment in advance.) Simple and fast ways of calculating modular inverses are: - Bézout's identity. That is, inverting p mod q can be done by adapting the Euclidean GCD algorithm to produce numbers x and y such that xp + yq = gcd(p, q). The adaptation is usually called the Extended Euclidean Algorithm, and it is simple: For the base case of the Euclidean algorithm, where p divides q, we can take x = 1 and y = 0. For the other cases, we can use recursion: if we have x', y' satisfying x' * p + y' * (q%p) = gcd(p, q%p) = gcd(p, q), then summing and subtracting y' * p * (q/p) (integer division here) allows q to reappear in the equation by some rearranging, since q = (q/p) * p + (q%p). This allows us to find x, y in terms of x', y'. Since p is prime in this particular case, gcd(p, q) = 1 for all relevant values of q and thus y is the modular inverse of q: xp + yq = 1 (mod p) implies yq = 1 (mod p). Perhaps it's relevant to mention that this method works even for non-prime p, just as long as gcd(p, q) = 1. - Fermat's little theorem. That is, the inverse of q (mod p) is q^(p-2) (mod p), since q^(p-2) * q = q^(p-1) = 1 (mod p) by Fermat's little theorem. You can compute q^(p-2) (mod p) in logarithmic time by doing binary exponentiation: a^b is 1 if b is zero; it equals (a^(b/2))^2 if b is even, and it equals a * (a^(b/2))^2 if b is odd (integer division again!).
- nmc 13y ago
  No apology needed, your comment is relevant. =D I should have mentioned: this is a naive implementation. Optimizations like this will come later. Thanks for the interest.
theboss 13y ago
I've seen a lot of talk about ECC on hacker news in the last few weeks and people seem really interested. My question is why? Are you guys about to roll out ECC as your crypto-solution? Nobody really encrypts large amounts of data RSA/ECC, so the benefits of ECC aren't even THAT big since at best, these are used for a key agreement. Aren't I better just using RSA/DH for my key agreement, algorithms that are safe that I fully understand, than ECC?
- ctz 13y ago
  The main benefit of EC over IF/DL based cryptosystems is that it scales much better as you move to higher security levels. Compare, for instance, the speed of RSA with a 15360-bit modulus and the speed of ECC over NIST-P521. These are thought to provide roughly the same security level.
  - theboss 13y ago
    Yeah but who is doing that here? For the most part, a lot of people here just need an HTTPS cert with RSA 2048. I guess I may be wrong and it might help with efficiency if you have 10,000 connections HTTPS request per second and you're working at a big company, but if you're just a tiny website with a TLS cert then I wouldn't waste my time learning about ECC if I were you.
- maaku 13y ago
  Probably a lot of it is bitcoin related (which uses ECDSA over the secp256k1 curve).
- espeed 13y ago
  Use elliptic curve Diffie-Hellman with forward secrecy. See... Google Security: Protecting data for the long term with forward secrecy http://googleonlinesecurity.blogspot.com/2011/11/protecting-data-for-long-term-with.html http://googleonlinesecurity.blogspot.com/2011/11/protecting-... Google Research: Fast Elliptic Curve Cryptography in OpenSSL http://research.google.com/pubs/pub37376.html http://research.google.com/pubs/pub37376.html http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/37376.pdf http://static.googleusercontent.com/external_content/untrust... SSL Labs: Deploying Forward Secrecy https://community.qualys.com/blogs/securitylabs/2013/06/25/ssl-labs-deploying-forward-secrecy https://community.qualys.com/blogs/securitylabs/2013/06/25/s... Michael Horowitz: Perfect Forward Secrecy can block the NSA from secure web pages, but no one uses it (http://blogs.computerworld.com/encryption/22366/can-nsa-see-through-encrypted-web-pages-maybe-so http://blogs.computerworld.com/encryption/22366/can-nsa-see-...)
robertk 13y ago
Exercise for the reader: Use my Ruby library for finite fields and this to implement arithmetic on elliptic curves over finite fields. https://github.com/RobertZK/FiniteFields https://github.com/RobertZK/FiniteFields
- nmc 13y ago
  That's a plan for my next week-end!

16 points by nmc 13y ago

(I only read the very first function from the implementation, so I apologise for the overly-specific comment in advance.) Simple and fast ways of calculating modular inverses are: - Bézout's identity. That is, inverting p mod q can be done by adapting the Euclidean GCD algorithm to produce numbers x and y such that xp + yq = gcd(p, q). The adaptation is usually called the Extended Euclidean Algorithm, and it is simple: For the base case of the Euclidean algorithm, where p divides q, we can take x = 1 and y = 0. For the other cases, we can use recursion: if we have x', y' satisfying x' * p + y' * (q%p) = gcd(p, q%p) = gcd(p, q), then summing and subtracting y' * p * (q/p) (integer division here) allows q to reappear in the equation by some rearranging, since q = (q/p) * p + (q%p). This allows us to find x, y in terms of x', y'. Since p is prime in this particular case, gcd(p, q) = 1 for all relevant values of q and thus y is the modular inverse of q: xp + yq = 1 (mod p) implies yq = 1 (mod p). Perhaps it's relevant to mention that this method works even for non-prime p, just as long as gcd(p, q) = 1. - Fermat's little theorem. That is, the inverse of q (mod p) is q^(p-2) (mod p), since q^(p-2) * q = q^(p-1) = 1 (mod p) by Fermat's little theorem. You can compute q^(p-2) (mod p) in logarithmic time by doing binary exponentiation: a^b is 1 if b is zero; it equals (a^(b/2))^2 if b is even, and it equals a * (a^(b/2))^2 if b is odd (integer division again!).

nmc 13y ago
No apology needed, your comment is relevant. =D I should have mentioned: this is a naive implementation. Optimizations like this will come later. Thanks for the interest.

theboss 13y ago

I've seen a lot of talk about ECC on hacker news in the last few weeks and people seem really interested. My question is why? Are you guys about to roll out ECC as your crypto-solution? Nobody really encrypts large amounts of data RSA/ECC, so the benefits of ECC aren't even THAT big since at best, these are used for a key agreement. Aren't I better just using RSA/DH for my key agreement, algorithms that are safe that I fully understand, than ECC?

ctz 13y ago
The main benefit of EC over IF/DL based cryptosystems is that it scales much better as you move to higher security levels. Compare, for instance, the speed of RSA with a 15360-bit modulus and the speed of ECC over NIST-P521. These are thought to provide roughly the same security level.
- theboss 13y ago
  Yeah but who is doing that here? For the most part, a lot of people here just need an HTTPS cert with RSA 2048. I guess I may be wrong and it might help with efficiency if you have 10,000 connections HTTPS request per second and you're working at a big company, but if you're just a tiny website with a TLS cert then I wouldn't waste my time learning about ECC if I were you.
maaku 13y ago
Probably a lot of it is bitcoin related (which uses ECDSA over the secp256k1 curve).
espeed 13y ago
Use elliptic curve Diffie-Hellman with forward secrecy. See... Google Security: Protecting data for the long term with forward secrecy http://googleonlinesecurity.blogspot.com/2011/11/protecting-data-for-long-term-with.html http://googleonlinesecurity.blogspot.com/2011/11/protecting-... Google Research: Fast Elliptic Curve Cryptography in OpenSSL http://research.google.com/pubs/pub37376.html http://research.google.com/pubs/pub37376.html http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/37376.pdf http://static.googleusercontent.com/external_content/untrust... SSL Labs: Deploying Forward Secrecy https://community.qualys.com/blogs/securitylabs/2013/06/25/ssl-labs-deploying-forward-secrecy https://community.qualys.com/blogs/securitylabs/2013/06/25/s... Michael Horowitz: Perfect Forward Secrecy can block the NSA from secure web pages, but no one uses it (http://blogs.computerworld.com/encryption/22366/can-nsa-see-through-encrypted-web-pages-maybe-so http://blogs.computerworld.com/encryption/22366/can-nsa-see-...)

robertk 13y ago

Exercise for the reader: Use my Ruby library for finite fields and this to implement arithmetic on elliptic curves over finite fields. https://github.com/RobertZK/FiniteFields https://github.com/RobertZK/FiniteFields

nmc 13y ago
That's a plan for my next week-end!