Assume an encrypted message is sent through use of exponential cipher.

Question

...such that modulus $p = 2741 \text{ (p is prime)}$ and $e = 11 \text{ (e = exponent)}$

Message: $1315\quad 0611 \quad 0427 \quad 0091 \quad 0520 \quad 0733$

I am required to determine the decryption exponent and determine what it says.

This is my work so far on Mathematica. I believe my solution is wrong, as the exponent I arrived at is negative. Please advise. Thanks in advance.

---

'In' =input
'Out' =output

In $ \text{mssg} = { 1315, 0611, 0427, 0091, 0520, 0733}$

Out ${1315, 611, 427, 91, 520, 733}$

In $p = 2741$

In $e = 11$

In $\text {code[x_]} := \mod[x^{e}, p]$

In $\text { cipher = code[mssg] }$

Out $\, {2622, 2659, 1544, 951, 2718, 859}$

In $\text{ ExtendedGCD }[e, p - 1]$

Out $\,(1, (-249, 1))$

Why do my exponent here shows as $-249 ?$

Answer 1

Unfortunately, The Mathematica online help page about ExtendedGCD gives limited information about this;

\begin{align} in[1]:&\; \{g, \{a, b\}\} = \operatorname{ExtendedGCD}[2, 3]\\ out[1]:&\; \{1,\{-1,1\}\} \quad \text{ //next, test the result}\\ in[2]: &\;2 a + 3 b == g\\ out[2]:&\; \texttt{True}\\ \end{align}

The extra output sub-list is for the Bezout's Identity.:

Let $a$ and $b$ be integers with greatest common divisor $d$. Then, there exist integers $x$ and $y$ such that $ax + by = d$

For your problem;

\begin{align} \gcd(e,p-1) &= u \cdot e + v \cdot (p-1), \text{ for some } u,v\in\mathbb{Z}\\ 1 &= -249 \cdot 11 + 1 \cdot 2740\\ 1 &= -2739 + 2740 \end{align}

Actually, you want the inverse of $e$ $\bmod{p-1}$ and Bezout's Identity that is very helpful to find the inverses.

If you take $\bmod 2740$ on both side - that is one of the ways to calculate the inverse -;

$$ 1 = -249 \cdot 11 + 1 \cdot 2740$$

$$ 1 \equiv -249 \cdot 11 \pmod{2740}$$

you fill find the inverse of $11 \pmod{2740}$, that is $-249 \equiv 2491 \bmod 2740$