Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
And what is $r$? It appears ex nihilo in the last congruence... –  Arturo Magidin Jun 1 '11 at 20:47
    
$r$ is actually $q$. Sorry, I made a typo –  Jernej Jun 1 '11 at 22:10

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
A triviality is to take $z = a$ but $a$ is not known as it is Alice private key. Am I missing something? –  Jernej Jun 2 '11 at 0:37
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}$. –  Arturo Magidin Jun 2 '11 at 3:04
    
That's what I meant--I'll change the confusing wording. –  Elliott Jun 2 '11 at 3:08
    
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? –  Jernej Jun 2 '11 at 10:39
    
Correct :) having only 12 cases to check is very efficient. –  Elliott Jun 2 '11 at 19:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.