Hashing and message authentication

Introductions

The computational security of RSA depends on a trapdoor function, meaning a function that is easy to compute in one direction but computationally infeasible in the other direction.
RSA parameters
- m: message
- e: public exponent
- d: private exponent
- n: modulus
- c: ciphertext
RSA encryption, in simplified form, is c = m^e (mod n)
RSA decryption, in simplified form, is m = c^d (mod n)
Process to choose a public and private key
- The receiver chooses two large prime numbers, p, and q. Compute their product, n = pq.
- The receiver calculates ϕ(pq) = (p - 1)(q - 1).
- The receiver chooses a number e relatively prime to ϕ(pq). In practice, e may be 2¹⁶ +1 = 65537.
- The public key is (e, n).
- The receiver calculates the modular inverse d of e modulo ϕ(n). This means de = 1 (mod ϕ(n)).
- The private key is d.
Attacking RSA
- Attacker knows n, but factoring into p and q is a known hard problem.
- Attacker does not know ϕ(n), so it cannot use knowledge of e to calculate d. The only way to get ϕ(n) is to factor n into its primes.

elliptic curves provide a better trapdoor function
curves have a form similar to y = x³ + ax + b
An elliptic curve cryptosystem can be defined by picking a prime number as a maximum, a curve equation and a public point on the curve. A private key is a number priv, and a public key is the public point dotted with itself priv times. Computing the private key from the public key in this kind of cryptosystem is called the elliptic curve discrete logarithm function. This turns out to be the Trapdoor Function we were looking for.
elliptic curves are much more efficient for the same level of security

We are using the Rust Crypto crates.