2
$\begingroup$

I'm practising for a cryptography test and came across this question:

Let us assume that for a specific elliptic curve the formulas for the computation of $(x_3, y_3)=R+S$ are given by:

$X_3=\sigma^2-x_1-x_2\ (\textrm{mod}\ p)$

$Y_3=\sigma(x_1-x_3)-y_1 \ (\textrm{mod}\ p)$

$\sigma = \frac{y_2-y_1}{x_2-x_1}\qquad \textrm{if R}\neq\textrm{S}$

$\sigma = \frac{3x_1^2+5}{2y_1}\qquad \textrm{if R = S}$

The following holds: $p=17$, $P=(3, 5)$, $a=3$, $k=2$, $M=(2, 7)$. Compute Q.

I understand the provided solution up until step 5.

1.$\ Q=a\cdot P = 3\cdot P$

2.$\ P= (3, 5) \Rightarrow 3\cdot P=2\cdot P+P$

3.$\ 2\cdot P\Rightarrow(3,5)+(3,5)$

4.$\ \sigma=\frac{3x_1^2+5}{2y_1}\qquad\ \ \ (R=S)$

5.$\ \sigma =\frac{3\cdot 3^2+5}{2\cdot 5}=\frac{32}{10}=\frac{16}{5}=\frac{16\cdot7}{5\cdot 7}\textrm{ mod } 17=112\textrm{ mod }17=10\qquad\ \ \ (5^{-1}=7\textrm{ mod } 17)$

I understand that $16\cdot 7\textrm{ mod }17=10$, but where does the $7$ come from? Also, why is $5^{-1}=7\textrm{ mod } 17$ shouldn't that equal zero..?

$\endgroup$
2
$\begingroup$

I understand that $16\cdot 7\equiv 10 \bmod 17$, but where does the $7$ come from? Also, why is $5^{−1}\equiv 7 \bmod 17$ shouldn't that equal zero..?

When working with modular arithmetic, $a^{-1}$ (if it exists) is a number $b$ such that $a\cdot b\equiv 1$. So, because $5\cdot7\equiv 1\bmod{17}$, we say that $5^{-1}\equiv 7\bmod{17}$. Not sure where $0$ came from in your mind as $0$ times anything is $0$.

In step 5, where you are multiplying by $\frac{7}{7}$, the reason they are doing this is to cancel out the bottom since $5\cdot 7\equiv 1$. This step is not necessary, but it does make things simpler, I guess. You can play around with this modular arithmetic calculator to verify that $\frac{16}{5} = 16\cdot 7\equiv 10\bmod{17}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.