Implementation of the following algorithms used to attack Discrete Logarithm Problems (which in turn drives Diffie-Hellman Cryptosystem):
- Brute Force
- Baby-step Giant-step
- Pollard’s ρ algorithm
- Pohlig-Hellman algorithm
A description of these algorithms have been provided in algorithms.pdf
- Python 3.7
The program computes the discrete log. Given g, y and n it computes x such that g^x = y (mod n).
To run any of the code first change directories to Discrete Logarithm Attacks
cd Discrete\ Logarithm\ Attacks/
The code only works for 0 < g < n, 1 < n and 0 < y < n (which are the usual limits).
To brute force find x use (for eg. with n = 97, g = 3, y = 18),
python main.py --algo Brute -n 97 -g 3 -y 18
This returns answer 45 as expected. If no solution x exists, the returned answer is -1, as for the follwoing case:
python main.py --algo Brute -n 11 -g 3 -y 6
Similarly to run BSGS change --algo to BSGS:
python main.py --algo BSGS -n 97 -g 3 -y 18
BSGS and Pollard's rho algorithm work only for prime n. They might result incorrect results for composite n. To make them check if n is prime before running the algorithm pass -v (this might blow the running time for large n and should be avoided):
python main.py --algo BSGS -n 97 -g 3 -y 18 -v
To run Pollard's rho algorithm use
python main.py --algo Pollard-rho -n 11 -g 3 -y 9 -o 5 -v
-o argument provides the order of g mod n. If -o is not provided, the answer returned might not be the smallest x satisfying the equation. For eg.
python main.py --algo Pollard-rho -n 11 -g 3 -y 4 -v
returns 9, which is a correct answer, but not the smallest correct answer, 4.
To run Pohlig Hellman algorithm the prime factorization of n-1 must be passed in the form of two list, factors and powers such that prod_i factors[i]^powers[i] = n-1. Also the algorithm only works g^(n-1) (mod n) = 1. As 10 = 2 x 5, we can run,
python main.py --algo Pohlig-Hellman -n 11 -g 3 -y 4 --factors 2 5 --powers 1 1 -v
To run the tests
python -m unittest test
This code is provided using the MIT License.
This project was a part of the course INF 385T: Applied Encryption, offered in Spring 2020 at University of Texas at Austin.