How does eve find the message m that Bob encrypted?

Question

The following is given:

$p=13$, $g=7$, $A=5$, $(c1,c2)=(10,8)$

I know $A=g^a \to a=3$ the message $m$ should be $c2*c1^{-a}$, which is $8\times 10^{-3} \mod 13$ but I don't know how to calculate the inverse part.

Answer 1

So what I get from your first computation is the following: you have looked for $a$ such that $A = g^a \mod 13$ and have found that $a = 3$. In your second step, you want to compute $$c_2\cdot c_1^{-a} = 8 \cdot 10^{-3} \mod 13.$$

Since $\text{gcd}(10,13) = 1$, we have that $10$ has a multiplicative inverse modulo $13$. This means that there is some $x$ such that $$10\cdot x \equiv 1 \mod 13$$ and we denote $x = 10^{-1}$. Therefore, your question becomes: 'find $x$ which satisfies this equation'.

Okey, so we have the following equations: $$\begin{align} 13 &= 1 \cdot 10 + 3\\ 10 &= 3 \cdot 3 + 1\\ 3 &= 3 \cdot 1 \end{align}$$ this is Euclids division algorithm. From it , you can see that (starting from the second equation): $$\begin{align} 1 &= 10 - 3 \cdot 3\\ &= 10 - 3\cdot (13 - 1\cdot 10)\\ &= 4 \cdot 10 - 3 \cdot 13 \end{align}$$ and if we look at this modulo $13$, we see that $$1 = 4 \cdot 13 - 3 \cdot 13 \equiv 4 \cdot 10 \mod 13.$$ Therefore, we have shown that $10^{-1} \equiv 4 \mod 13$. Note that $10^{-3} \equiv 4^3 = 64 \equiv 12 \equiv -1 \mod 13$.

Using all of this, we find that $$c_2 \cdot c_1^{-a} = 8\cdot 10^{-3} \equiv 8 \cdot (-1) \equiv -8 \equiv 5 \mod 13.$$

I hope this helps :)

Answer 2

To find $10^{-3}\mod 13$ we first note that it is equal to $\left(10^{-1}\right)^3\mod 13$.

We can find $10^{-1}\mod 13$ by the definition of inverses - we want to find an $x$ such that $x\times 10\equiv 1\mod 13$ where $x$ can also be denoted by $10^{-1}$

I used WolframAlpha to find $10^{-1}=4\mod 13$, however you can do this by trying all values of $x$ from $2$ to $12$ until you find the desired value (there are far better methods for doing this btw, but beyond the scope of this answer). We note that $10$ will have an inverse modulo $13$ as $13$ is prime.

Therefore, \begin{align}10^{-3}\mod 13&\equiv\left(10^{-1}\right)^3\mod 13\\ &\equiv 4^3\mod 13\\ &\equiv 64\mod 13\\ &\equiv 12\end{align}

Answer 3

To compute the inverse of $10$ modulo $13$, jsut apply the extended Euclidean algorithm:

Write first the two trivial equations. In the steps of Euclid $\gcd(13,10) = \gcd(10,3) = \gcd(3, 1) = 1$ follow the steps by doing the same subtractions on the equations on the right, as you do to get the numbers: if $a > b$: $\gcd(a,b) =\gcd(b, a \pmod{b})$, by substracting $a / b$ (rounded down to an integer) times $b$ from $a$: $$\begin{align} & 13 = 1 \cdot 13 + 0\cdot 10\\ & 10 = 0\cdot 13 + 1\cdot 10 \\ & 3 = 1\cdot 13 + (-1)\cdot 10 & \text{from: eq (1) - eq (2)} \\ & 1 = -3 \cdot 13 + 4 \cdot 10 & \text{from: eq (2) - 3eq(3)}\\ \end{align}$$

The last equation taken modulo $13$ just says $1 \equiv 4\cdot 10\pmod{13}$

so $4$ and $10$ are inverses.