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!
findE
with? $\endgroup$n: 1000133 p: 372453 pe: 464079
$\endgroup$c * base
overflows since both inputs may be as large as $n$, which is about 20 bits. Hence the product becomes too large for anint
and gets truncated. Use arbitrary-precision integers to make it work. $\endgroup$