How do I read and solve equations in the form of $a*b = c \mod d$?

Question

I am trying to find the decryption key of a given RSA problem. I have never solved equations using modulus, and I cannot seem to wrap my head around the equation to find the decryption key.

I am trying to solve this equation:

$43 * d = 1 mod 60$

I know the basics of modulus and therefore know that $1 \mod 60$ equals 1. I then, wrongly, substitute $1 mod 60$ by $1$ and simplify the equation like this:

$43 * d = 1$

However, I know that this is wrong, as I checked the answer sheet and there were a couple of answers, one being 301. I know that 301 is divisible by 43. The reasoning in the answer says "We need to find a number d that, when multiplied by 43 and divided by 60 leaves a remainder of 1." But in my head I ask "Why would we need to do that? I can solve 1 mod 60 and it is 1."

What did I do wrong by assuming $1 \mod 60$ equals $1$ and substituting that in the formula?

Edit: I have wrongly tagged this question as cryptography as I didn't know what tag to file this under. I welcome any edit that can fix the tag!

Answer 1

The "equation" you have there should be written $43d\equiv 1\pmod{60}$. Note the symbol: three horizontal lines, not the two lines of equality. It is read as "$43d$ is congruent to $1$ modulo $60$". It means that $43d-1$ is an integer multiple of $60$. Solving this "congruence" amounts then to finding integers $d$ and $e$ with $43d-1=60e$. We can re-arrange this as $43d-60e=1$.

The extended Euclidean algorithm gives a way of solving such two-variable equations. In this example we find a solution $d=7$, $e=5$ which gives $d\equiv7\pmod{60}$ as the solution to the congruence.

Answer 2

A possible way to solve such problem is to use the euclidian algorithm.

$$60= 1(43) + 17$$ $$43 =2(17) + 9 $$

$$17 = 1(9) + 8$$

$$9 = 1(8) + 1$$

Hence we can write

\begin{align} 1 &= 9 - 1(8) \\ &=9-(17-9) \\ &=2(9) - 17 \\ &=2(43 -2(17))-17 \\ &= 2(43)-5(17) \\ &=2(43)-5(60-43) \\ &= 7(43) - 5(60) \end{align}

Now take $\pmod {60}$, we have $7 \times 43 \equiv 1 \pmod {60}$

Notice that $a \equiv 1 \pmod m$ doesn't mean $a=1$. It simply means when $a$ is divided by $m$, the remainder is $1$.

Answer 3

You work with congruences modulo $n$ as you work with equalities, with one big difference: you cannot always divide by a congruence class (it has to be a unit modulo $n$), and you cannot alway simplify – this means, explicitly, that $ab\equiv a'b$ does not necessarily imply $\equiv a'$, as the congurance is equivalent to $(a-a')b\equiv 0$, and the congruence class of $b$ can be a zero-divisor modulo $n$.

here, $43$ is a unit mod. $60$, as it it coprime to $60$. Furthermore its inverse mod. $60$ can be found from a Bézout's relation between $43$ and $60$.

Indeed the extended Euclidean algorithm yields $$7\cdot 43 -5\cdot 60 =1,$$ so the solution of your congruence equation is $\;\color{red}{d\equiv 7\mod 60}$.

Answer 4

Since $\gcd(43,60) = 1$ there exists $c,d$ that satisfy:

$43 d + 60 c = 1$

Now we apply the Euclidean algorithm. Here is how I think about it.

$\begin{bmatrix} 1\\&1\end{bmatrix}\begin{bmatrix}60\\43\end{bmatrix} =\begin{bmatrix}60\\43\end{bmatrix}$

Now what row opperations do I need to do to reduce the numbers on the right, eventually I will get to $1.$

And I just keep tacking on the additional rows.

$\begin{bmatrix} 1&0\\0&1\\1&-1\\-2&3\\-5&7\end{bmatrix}\begin{bmatrix}60\\43\end{bmatrix} =\begin{bmatrix}60\\43\\17\\9\\1\end{bmatrix}$

$7\cdot 43 = 1 + 5\cdot 60\\ d = 7$

Answer 5

Intended is $\,43d\equiv 1\pmod{\!60}\,$ meaning $\,60\mid 43d-1,\,$ which is not equivalent to $\,43d = 1.\,$
Instead, $\quad (43d\bmod 60) = 1\,$ is a correct operational reformulation of the above congruence.
Be careful not to confuse $\!\bmod\!$ the ternary equivalence relation vs. binary operation (such confusion is greatly exacerbated by the abuse of notation used in your textbook)

There are many ways to compute modular inverses and fractions. One simple way is to employ the extended Euclidean algorithm in fractional form, e.g. below we use it to compute $\,\color{#c00}{1/43}\pmod{\!60}$

$$\dfrac{0}{60}\, \overset{\large\frown}\equiv\!\! \underbrace{\color{#c00}{\dfrac{1}{43}}\ \overset{\large\frown}\equiv \color{#90f}{\dfrac{-1}{17}}\ \overset{\large\frown}\equiv\ \color{#0a0}{\dfrac{4}{-8}}} _{\,\Large \begin{align}\color{#c00}{1}\ \ -\ \ &3(\color{#90f}{ -1 }) \ \ \equiv \ \ \ \color{#0a0}{4}\\ \color{#c00}{43}\ \ -\ \ &3(\color{#90f}{17} )\ \ \ \equiv\ \color{#0a0}{-8}\ \ \ \end{align}}\!\!\!\!\overset{\large\frown}\equiv\ \dfrac{7}1\qquad\qquad $$

Thus $\ \color{#c00}{1/43}\equiv 7\pmod{\!60}.\ $See this answer for a few other useful methods.

---

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus (or, more generally, in certain special contexts such as in the above algorithm). See here for further discussion.