My solutions to the assignments for my course "Algorithms for Numbers and Public-Key Cryptography".
Exercise 1 includes:
- Euclid’s Algorithm;
- Multiplicative inverse;
- Chinese Remainder Theorem;
- Jacobi symbol;
- Square roots and quadratic equations.
Exercise 2 includes:
- Addition algorithm for positive integers;
- Application: Fibonacci Sequence;
- Multiplication algorithm for positive integers;
- Factorial;
- Modular Exponentiation.
Exercise 3 includes:
- Fermat test;
- Miller-Rabin primality test;
- RSA.
Exercise 4 includes:
- Coppersmith Attack on partially known message encryption with RSA
- Finding small root of a modular polynomial equation of degree 2;
- Polynomials of degree 3;
- Application to breaking RSA encryption with small exponent e.
Exercise 5 includes:
- Fault attacks against RSA signatures
- Signature generation algorithm using the Chinese Remainder Theorem;
- Recovering the factorization of N from s, following the Bellcore attack.
Exercise 6 includes:
- DGHV Somewhat Homormorphic Encryption Scheme.