The goal of the project was to learn about and implement the most common cryptographic schemes, which included RSA,
Shamir’s secret sharing, and ECDSA.
Here’s a basic outline of what we implemented.
A function that quickly calculates the GCD for use in determining if two numbers x, y are coprime gcd(x, y) == 1
Used Euclid’s “extended GCD” algorithm to quickly find an inverse in a mod field.
gcd(x, y) = gcd(y, x mod y)
(Efficiently) checks whether or not a (very large) number is prime. RSA operates on the order of 512-bit prime
numbers, so efficiency was really important here.
Implemented the Miller-Rabin primality test.
Created a list of small primes to check through before running Miller-Rabin to save time in a lot of cases.
Encrypt a message with a public/private key pair.
This amounts to modular exponentiation: E(x) = x^e mod pq
I implemented Chinese Remainder Theorem for quick modular exponentiation.
Decrypt an encrypted message with a corresponding key pair.
This amounts to another round of modular exponentiation, using d = e^-1 mod (p-1)(q-1): D(y) = y^d mod pq
Below is an example of how you could use the script:
A secret-sharing scheme tries to split up some secret s among n individuals, where k individuals need
to come together to access s. Any fewer will result in a garbage answer and force a brute-force computation
to try finding the secret.
To do this, we use the property that an (k-1)-degree polynomial is defined uniquely on k points. We generate
a random polynomial f(x) that satisfies f(0) = s. If we evaluate the polynomial at 0, then we get the secret.
This polynomial will be degree (k-1), and each share will be a point (i, f(i)) on the polynomial. Hand out
n unique shares to the n individuals. k individuals can come together to recreate the polynomial f(x)
by using Lagrange interpolation. Otherwise, the polynomial cannot be uniquely determined, so f(0) of the
“recovered” polynomial could be any value.
Below is an outline of what we implemented.
Solve for the unique (n-1)-degree polynomial that is uniquely defined on n points, in a mod field.
Computes the result of dividing a number by another number in a given modulus.
Computes the inverse of a number in a mod field.
Generate random shares that each represent a point on a polynomial.
Generate a random polynomial f such that f(0) = secret.
Recover the secret using the given share points, employing lagrange_interpolation
ECDSA stands for Elliptic Cryptography Digital Signature Algorithm. We implemented a basic elliptic curve
cryptography scheme, which is used in Bitcoin to generate public keys.
Take a look at what a Bitcoin address generation script looks like (don’t use this private key!!):