# ElGamal like encryption

How can I approach the following exercise: Source: An Introduction to Mathematical Cryptography by Hoffstein

This exercise describes an approach similar to ElGamal cryptosystem with a numerical example, and in order to solve it, one should do some "reverse-engineering" and find a ay how to deduce a general algorithm from the example given.

I copied the entire text so that you get some extra context of this task. I don't know in which relationship are the exponents.

The only conclusion I've managed to made is: $m ^{ a \cdot b \cdot a' \cdot b' } = m$ with $m, a$ and $b$ defined as above and $a'= 15619$ and $b'=31883$.

One can be very fast trapped to think of an obvious solution - namely that $a$ and $a'$ are inverses in $\mathbb{Z}_p$, but they are not because: $gcd(3589,32611) = 1 = 822*32611 - 7469*3589 \Rightarrow - 7469 = 25142 (\mod 32611)$ and $25142$ is not equal to $15619$.

(This also means that I was barking barking up the wrong tree saying that $aa'$ and $bb'$ are such numbers that $\exists k: m^{ k \varphi ( p + 1 )} mod p = 1$, ie $m^{(aa')(bb')} mod p =m$ => $k \varphi ( p + 1 ) = aa'bb'$, where $\varphi(n)$ is defined like in the Euler Theorem. This is wrong because we should be able to calculate a' without any knowledge about b).

• This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. – Did Dec 8 '13 at 9:38
• @Did In random guy's defense, he did state some work he did in the "The only conclusions..." part. – fgp Dec 8 '13 at 12:50
• @fgp You might want to check the timing of the modification of the question, compared to the comment. – Did Dec 8 '13 at 13:18
• @Did Oh, I didn't realize that. – fgp Dec 8 '13 at 13:23
• I don't know why this is offtopic. I can silice this to three new questions, but it wouldn't really help because people would still not read the exercise thoroughly and conclude that a and x should be inverses, which is not true with given numbers. – random guy Dec 8 '13 at 21:34

## 1 Answer

Here are a few pointers.

You have realized that the basic idea is that $m^{abxy} = m \mod p$. For that to hold, it's sufficient of course that both $m^{ax} = m \mod p$ and $m^{by} = m \mod p$. Now compare this to euler's theorem (actually, fermat's little theorem will suffice). Given a prime $p$, what are the requirements on $a$ for there to be an $x$ with $m^{ax} = m \mod p$, and how do you find $x$ from $a$?

• This would basically mean that a and x are inverses in $\mathbb{Z}_p$. However intuitive this approach, it is unfortunately not true. With given a=3589 und x=15619, we don't get back to our m. – random guy Dec 8 '13 at 21:32
• @randomguy The approach is fine, but $\mathbb{Z}_p$ is the wrong ring to look at - observe that fermats little theorem states that $a^p = a \mod p$, yet $a^0 = 1 \mod p$, even though $p = 0 \mod p$. OTOH, $p = 1 \mod (p-1)$... – fgp Dec 9 '13 at 0:23