Show HN: Arithmetic on elliptic curves in Ruby

(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!).

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?

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