## Introduction This is my approach to solving the Broken_DLOG Challenge given by the ingonyama team. Here is the [Challenge Link](https://github.com/ingonyama-zk/Challenges/blob/main/Broken_Dlog.md). Github Link of the [Solution](https://github.com/Sahilgill24/Broken_DLOG). ***Currently I have set the repository to public, please mention if this is a concern.*** My Answer ```python x = 129741816436586536192511069033522723797805991085207391260653840826086090109 r = 996179739629170 ``` --- ## Approach This was the given equation, which was key to solving the challenge as here $r$ is a 50-bit number it lies between $\ [0,2^{50} ]$. $$ g^r \equiv a\pmod{p} $$ I used the **Baby-Step Giant-Step (BSGS)** algorithm to solve for r, since we know that $r$ lies in the range $\ [0,2^{50} ]$ . More details mentioned in the next section. Once we obtain $r$ using BSGS, we proceed to solve the second equation which could be solved directly using euclid's Algorithm: $$ t \equiv r + c \cdot x \pmod{p-1} $$ Note: Since p is a prime, so the totient function directly becomes $p-1$. However, we observe that $c$ and $p-1$ are not co-prime, i.e.: $$ \gcd(c, p-1) > 1 $$ Specifically, $\gcd(c, p-1) = 2$. This implies that a modular inverse of $c$ modulo $p-1$ does not exist directly. So we normalize the values as follows: $$ d = \gcd(t-r,p-1) $$ $$ (t -r)/d \equiv (c/d) \cdot x \pmod{(p-1)/d} $$ Now simply multiplying with the inverse of $(c/d)$ modulo ${(p-1)/d}$ , with the normalized $(t -r)/d$ to get the value of $x$. --- ## Broken DLOG I first implemented in Python to get familiar with the Algorithm, then moved on to C++ and now am currently implementing in CUDA which is not complete. Here $m$ is basically the power we subject our generator to while searching for matching values in the look up table. * Store all these values in a lookup table, after hashing them. $$ g^k \quad \forall k \in [0, m] $$ * Look in the table and if any match is found $$ g^{-mk} \quad \forall k \in [0, m] $$ * Matching resolution $$ g ^ n\pmod{p}= g ^ {-jk} \pmod{p} $$ * we get our $r$ as $n+ jk$. typically $m$ is taken as the root of the prime $p$, but we have a better restriction of 50-bits. so we set our $m$ as $2 ^ {25}$. #### Python - For $m = 2^{20}$: - Time: ~18 seconds - Memory: ~600 MB RAM - For $m = 2^{23}$: - Time: ~2 minutes 35 seconds - Memory: ~5 GB RAM Using basic Extrapolation (8x) we can deduce it as : - For $m = 2^{25}$: - Estimated Time: ~10 minutes - Estimated Memory: ~20 GB RAM This implies that, on a device with sufficient RAM (e.g. 32 GB), it is theoretically possible to solve this on CPU using a simple Python implementation without any parallelization or special hardware acceleration. #### C++ - For $m = 2^{20}$: - Time: ~10 seconds - Memory: ~977 MB RAM - After hash table is built: ~62 MB RAM (though this may involve some collisions with standard hasher) and time increased to 12 seconds. - For $m = 2^{23}$, memory usage increases significantly: - Time: ~1 minutes 58 seconds - Memory: ~520 MB RAM (with SHA256 hashes in unordered map) - For $m = 2^{25}$, which is complete for solving the equation: - Time: ~16 minutes 40 seconds - Memory: ~4.5 GB RAM (with SHA256 hashes in unordered map) #### CUDA (Currently writing the CUDA implementation for this, the algorithm is the easy part using the BigNUM is a challenge as I was not too familiar with CUDA before this, but it would also need a gpu with considerable ram to be able to complete the task) #### Algorithms I could have used other algorithms such as Pollard-rho and Pollig-Hellman as they are very space-efficient $O(1)$ than BSGS $O(m)$ but their Probablistic nature makes them bad for this implementation, as we know the discrete log lies in a certain range to get a sure shot result BSGS would be our best algorithm. ## Resources The resources I used for building my approach: * https://www.youtube.com/watch?v=007MVsELvQw * https://www.mat.uniroma2.it/~geatti/HCMC2023/Lecture4.pdf * https://fortenf.org/e/crypto/2017/12/03/survey-of-discrete-log-algos.html ## Contact Email: gursahilgill24@gmail.com x: [Sahilgill24](https://x.com/Sahilgill24) Discord: gills0924 (already present in the Ingonyama Discord channel ## PS Be sure to input the correct strings for the numbers, I was inputting the wrong $g$ and it took me alot of time, because of it :( .