# Brute forcing the secret key in Elgamal encryption

Crypto noob here, I am attempting to do this programming challenge. I do not have the secret key that is used to decrypt the message. However, the key is small enough for a brute force approach. I am attempting to write a function that will solve for the secret key with other variables used in the process.

She tells Bob values of $p$ and $pe \equiv p^e \pmod{n}$ (p raised to power of e mod n) as her public key. Meanwhile the value e remains her secret key (there is no easy way to calculate it from $p$ and $p^e$).

I have $pe$, $p$, and $n$. Here is some code written in java.

static int findE(int n, int p, int pe) {
for(int e = 0; e < n; e++) {
if(modular_pow(p, e, n) == pe)
return e;
}
return -1;
}

static int modular_pow(int base, int exponent, int modulus) {
int c = 1;

for(int i = 0; i < exponent; i++) {
c = (c * base) % modulus;
}
return c;
}


I calculate $p^e \pmod{n}$ for all possible values, but my "findE" function always returns -1. I have tested my modular_pow function and am certain that is not the problem. Maybe I am misunderstanding the instructions. Thanks for any help!

• The code looks as if it should work (albeit quite inefficiently). Maybe you made a mistake somewhere else? What are the arguments you're calling findE with? Jul 12, 2015 at 20:42
• I just added a System.out.println() on the parameters of my function, here is the resulting output: n: 1000133 p: 372453 pe: 464079 Jul 12, 2015 at 20:50
• Ah, here's an explanation: The multiplication c * base overflows since both inputs may be as large as $n$, which is about 20 bits. Hence the product becomes too large for an int and gets truncated. Use arbitrary-precision integers to make it work. Jul 12, 2015 at 21:04
• You are right! I didn't think about that one calculation of c * base. Well done, that solved the problem. Arbitrary-precision integers did the trick. Jul 12, 2015 at 21:20
• If you know the basic elements all fit within the length of int, then you can use long instead, so that you can do the multiplication steps. Arbitrary-length integers are preferable of course, but if this is a one-time assignment, long would be sufficient and easier to handle.
– tylo
Jul 13, 2015 at 10:42

Given $p$ and $p_e \equiv p^e \pmod{n}$. You need to calculate $p_e$. Propose $e$ is small enough to brute-force. The simplest way would be to calcute $p^e \pmod{n}$ for values $e \in \{1,2, ..., n-1\}$ until you find $p_e$.

So all you need would be something like this:

static int findE(int n, int p, int pe) {
int base = p;
for(int e = 2; e < n; e++) { // also it suffices to start at e=2
p = p * base % n;
if (p == pe) return e;
}
return -1;
}


Even though you are doing to much calculation (for every value of $e$ you recalculate all values of $p^{e-1}$), right now i do not see why your code would'nt work. Update: forget all i said about modular exponentation, that was bullsh*t.

• my modular_pow function computes using modular exponentiation because n can be of around 100,000 which means I have to use a memory efficient method to perform the calculations. Jul 12, 2015 at 20:38
• Ahh I see how your way is better now! You multiply it and then use modulus for each iteration and that way it never gets extremely large. Thank you! Jul 12, 2015 at 20:47
• I simply calculate each $p^i$ for all possible $i$ continously. You calculate $p^1 = p$, $p^2 = p * p$, $p^3 = p * p * p$, ..., and each time to start again with $p$ instead with the value you calculated in the previous iteration. Since you calculated $p^{i-1}$ in the previous round, there is no need to start all over again. Jul 12, 2015 at 21:00
• Yes, much better than my way. Also, I copy-pasted your method and it still returned -1 with the arguments n: 1000133 p: 372453 pe: 464079 Jul 12, 2015 at 21:01
• "i just did a quick run in python with my code..." Python has arbitrary-length integers by default, Java doesn't, which seems to be the problem.
– tylo
Jul 13, 2015 at 10:47