đź”™ to Projects
# Cryptosystems

## đź—“ Septemberâ€”December 2018

#### Technologies Used

#### Summary

##### RSA

##### Secret Sharing

##### ECDSA

**Project Link:** https://github.com/BerkeleyBlockchain/Cryptography

Python, Pytest

This was my first semester internal project for Blockchain at Berkeleyâ€™s Education Department.

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.

`gcd(x, y)`

- 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)`

- A function that quickly calculates the GCD for use in determining if two numbers x, y are coprime
`is_prime(x)`

- (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(keypair, unencrypted)`

- 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(keypair, encrypted)`

- 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.

`lagrange_interpolation`

- Solve for the unique
`(n-1)`

-degree polynomial that is uniquely defined on`n`

points, in a mod field.

- Solve for the unique
`div_mod`

- Computes the result of dividing a number by another number in a given modulus.

`extended_GCD`

- Computes the inverse of a number in a mod field.

`generate_random_shares`

- Generate random shares that each represent a point on a polynomial.

`generate_polynomial`

- Generate a random polynomial
`f`

such that`f(0) = secret`

.

- Generate a random polynomial
`recover_secret`

- Recover the secret using the given share points, employing
`lagrange_interpolation`

- Recover the secret using the given share points, employing

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!!):