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
    And what is $r$? It appears *ex nihilo* in the last congruence...2011-06-01
  • 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
    A triviality is to take $z = a$ but $a$ is not known as it is Alice private key. Am I missing something?2011-06-02
  • 1
    More than just "whenever $s$ and $t$ differ by a multiple of $12q$"; what you really want here is the converse: if $s$ and $t$ differ by a multiple of $12q$, *then* $12^s\equiv 12^t\pmod{p}$.2011-06-02
  • 0
    That's what I meant--I'll change the confusing wording.2011-06-02
  • 0
    Okay so qa-qz is a multiple of 12q which means a-z is a multiple of 12 which implies I only need to check 12 candidates for z?2011-06-02
  • 0
    Correct :) having only 12 cases to check is very efficient.2011-06-02