Secure Key Exchange over an Insecure Medium with Public Key Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 138

Y 2 Y 1 QUOTIENT REMAINDER Y

2 3 0 1

2

1 2 3 1

2

1 1 3

5 2

2 0 13 3

5

0.
The solution, ext_euclid(5,13) = y1 % a = -5 % 13 = -5 . You can check
this result by verifying that (4

Halt because remainder

5) % 13 20 % 13 6 because 13 2

6.
Of course, it should come as no surprise that, to compute secure elliptic curve
parameters, you are dealing with numbers far too large to fi t within a single
32-bit integer, or even a 64-bit integer. Secure ECC involves inverting 1,024- or
2,048-bit numbers, which means you need to make use of the huge library again.
You may see a problem here, though. When you inverted the multiplication
of 5 modulo 13, you got a negative result, and the interim computation likewise
involved negative numbers, which the huge library was not equipped to handle.
Unfortunately, there's just no way around it. You need negative number support
in order to compute modular inverses that are needed to support ECC.

26 and 20 ( 26)

Adding Negative Number Support to the Huge
Number Library
You may be familiar with two's complement binary arithmetic. In two's comple-
ment binary arithmetic, the lower half of the bit space represents positive
numbers and the upper half represents negative numbers. This enables you
to take advantage of the natural wrapping behavior of digital registers to effi -
ciently perform signed operations. Given, say, a 4-bit register (to keep things
small), you'd have the following:

0000 0

0001 1

0010 2

0011 3

0100 4

0101 5

0110 6

0111 7