Am i able to calculate ($a^{bc}$ mod d) with ($a^{b}$ mod d) and ($a^{c}$ mod d) without knowing a power?

Question

So I am trying to calculate ($a^{bc}$ mod d) with the values I have:

($a^{b}$ mod d) and ($a^{c}$ mod d)

In a scenario where I do not know what is c, but I know the integer values of ($a^{b}$ mod d), ($a^{c}$ mod d), a, d and b,

is there a way to calculate $a^{bc}$?

Thanks all!

Answer 1

This is Diffie-Hellman Problem on composite modulus - assuming $d$ is a composite number.

Diffie-Hellman Problem

Let $g$ be a generator of some group, in general, it is the multiplicative group of a finite field or an elliptic curve group.

Formally Diffie-Hellman Problem can be stated as:

Given an element $g$ and the values of $g^x$ and $g^y$, what is the value of $g^{xy}$?

In Diffie-Hellman key exchange, $x$ and $y$ are chosen randomly.

---

If the group order is not a prime and if you know the factors of $d$;

• you can calculate the discrete log for each prime factor of $d$ (assuming distinct) then you can use CRT. This requires that you know the factorization of the $d$. If the factors are not distinct, you will need the special case of CRT.

• you can use Pohlig-Hellam Algorithm which is works best if the prime factors are small.

  If $d = \prod_i p_i^{e_i}$ then it has comlexity $$\mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right)$$ compare it to the other generic discrete log agorithms with $\mathcal O(\sqrt{d})$-complexity.

If any factors of the $d$ are larger than 180-bit, you cannot calculate it with the current technology since the collective power of BitCoin miners can reach $\approx 2^{92}$ double SHA256 calculations in a year as of 2020.

As a result, your success will depend on the value and factors of $d$.