Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ which is the private key.

So the public key is $(g,b,p)$ where $b=g^x$ $mod$ $p$.

To encrypt, we compute: $y_1 = g^r$ mod $p$ and $y_2 = M*b^r$ mod $p$. Then the encrypted version of $M$ is the pair $(y_1,y_2).$

I also know $s=(M-a^y)(r^{-1})$ mod $p-1$. Now we know the El Gamal signature on $M$ which is $(y,s)$.

So in conclusion, I know $(g,b,p,x,y,s)$ where $y$ is the message. I want to know how to determine $r$ from all this information. How can I do that?

share|improve this question
add comment

1 Answer

At first glance

$r = s^{-1} (M - a^y) \bmod p-1$

would appear to be what you're looking for.

If $s$ isn't invertable modulo $p-1$, then you can work around this by working with the factors of $p-1$; in this case, $p-1 = uv$ where $s$ is a multiple of $u$ and $s$ is relatively prime to $v$.

So, we can solve:

$r_v = s^{-1} (M - a^y) \bmod v$

and so we have:

$r = r_v + kv$

for some integer $k$; if you know $y_1 = g^r \bmod p$, then you can recover the correct $k$ in $O( \sqrt{u})$ time.

share|improve this answer
    
When I factored $p-1$, I get a list of factors. How would I know how to compute $uv$ from $p-1$ or better yet, which factors to choose for $u$ and $v$? –  hhel uilop Nov 21 '13 at 19:54
    
@hheluilop: There's no need to fully factor $p-1$; all you really need is $u = gcd(p-1,s)$ and $v = (p-1)/s$ –  poncho Nov 21 '13 at 19:56
add comment

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.