Brute forcing the secret key in Elgamal encryption

Question

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!

Answer 1

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.