1
$\begingroup$

I am trying to solve an exercise from a cryptography textbook and I am stuck with these specific subquestion - any kind of suggestion is welcome!

Let $\alpha = 12$ be a generator of the group $(\mathbb{Z}_p)^{*}$ where $p = 12q+1$ is a prime and $q$ is a very large prime. Assume Alice private key is $a$.

Show that it is possible to efficiently (without use of the discrete logarithm on $q$) find an integer $z$ such that $ 12^{qz} \equiv y_A^q \pmod{p}$ where $y_A = \alpha^a$

  • 0
    $r$ is actually $q$. Sorry, I made a typo2011-06-01

1 Answers 1

2

You're trying to find an integer $z$ such that $12^{qz} \equiv 12^{qa}$ mod $p$. What does it take for $12^{qz}$ to be equivalent to $12^{qa}$ (mod $p$)?

Recall Euler's theorem: since $\alpha$ and $p$ are relatively prime, $\alpha^{\varphi(p)} \equiv 1$ (mod p). But we have $\varphi(p) = p - 1 = 12q$ because $p$ is prime; thus $\alpha^{12q} \equiv 1$ (mod p).

This means that if $s$ and $t$ differ by a multiple of $12q$, then $12^s \equiv 12^t$ (mod $p$). What does this tell you about $12^{qa}$ vs $12^{qz}$?

I can give further hints if you need them.

  • 0
    Correct :) having only 12 cases to check is very efficient.2011-06-02