4

I've a programming background and am just about to get into a project where Elliptic Curve Cryptography (ECC) is used. Although our libraries deal with the details I still like to do background reading so started with the ECC chapter of Understanding Cryptography. Everything was fine until I came upon this example of point doubling over $Z_{17}$:

enter image description here

I can't figure out how he gets $s$. For example the $(2\cdot1)^{-1}(3\cdot5^2+2)$ why does that evaluate to $2^{-1} \cdot 9$? From looking at it I would have thought $(3\cdot5^2+2)$ evaluates to $77$ so giving $2^{-1}\cdot77$ or $77\div2$ for the whole expression. Obviously the math doesn't work in the way I expect, is it something to do with the dot product not being normal multiplication? Or something else?

p.s. Sorry about formatting, I'm looking up how to do the Tex for the site now.

Peanut
  • 205
  • Are you familiar at all with modular arithmetic? $77=9$ in $\mathbb{Z}_{17}$. – fretty Jun 27 '13 at 14:21
  • 1
    Yes, to be precise, the author should have written $(2\cdot 1)^{-1}(3\cdot 5^2+2)\equiv 2^{-1}\cdot 9 \bmod 17$, and not just $=$. – Álvaro Lozano-Robledo Jun 27 '13 at 14:23
  • @ÁlvaroLozano-Robledo Thanks, can't believe it's that simple for that bit... So you have to apply the modulus operator the whole way through? So that bit is equivalent to $9\cdot9$ because $9/2$ is 4.5 and $89\mod17$ is 4 and you truncate in $Z$? Just not seeing how $9\cdot9 = 13\mod17$ – Peanut Jun 27 '13 at 14:35
  • 1
    $9\cdot 9 = 81 = 13 + 68 = 13 + 4\cdot 17 \equiv 13 \bmod 17$. – Álvaro Lozano-Robledo Jun 27 '13 at 14:39
  • @ÁlvaroLozano-Robledo I'm an idiot. Had it in my head $9\cdot9$ was 89 otherwise I'd have got that bit. Thanks. Post those two comments or a similar explanation as an answer and I'll accept. Thanks again. – Peanut Jun 27 '13 at 14:41
  • or $9\cdot 9\equiv (-8)\cdot (-8)\equiv 64\equiv 16\cdot 4\equiv -4\equiv 13\bmod 17$. – Álvaro Lozano-Robledo Jun 27 '13 at 14:42
  • why s is so when we double a point, i can't figure it out – curious Dec 03 '13 at 11:41
  • 2
    I asked nearly this identical question on Crypto https://crypto.stackexchange.com/questions/64456, and the answer there may also be worth looking at. – Brian M. Hunt Dec 01 '18 at 13:44

1 Answers1

6

All arithmetic is done modulo $17$, so $$(2\cdot 1)^{-1}(3\cdot 5^2+2)\equiv 2^{-1}\cdot 9\bmod 17$$ is a congruence, not an equality in $\mathbb{Q}$.

Moreover, $9\cdot 9\equiv 13 \bmod 17$ because $$9\cdot 9 = 81 = 13 + 68 = 13 + 4\cdot 17 \equiv 13 \bmod 17,$$ or, equivalently, $$9\cdot 9\equiv (-8)\cdot (-8)\equiv 64\equiv 16\cdot 4\equiv -4\equiv 13\bmod 17.$$

Álvaro Lozano-Robledo
  • 15,390