Cryptography Reference
In-Depth Information
curves, though, it's a necessity because you can't add a point to itself a given
number of times. Notice also that multiplication of points is meaningless; you
can add two points together, but you can only meaningfully multiply a point
by a scalar value.
Whew! I warned you elliptic curves were complex. However, that's not all.
As a programmer, you can likely still spot a problem with this defi nition: the
division operation in the defi nition of
. Whenever you divide integers, you get
fractions, and fractions create all sorts of problems for cryptographic systems,
which need absolute precision. The solution to this problem, which is probably
not a surprise to you at this point, is to defi ne everything modulo a prime number.
But — how do you divide modulo a number?
l
How Elliptic Curve Cryptography Relies on Modular
Inversions
Recall that addition modulo a number
n
is pretty straightforward: Perform
the addition normally and then compute the remainder after dividing by
n
.
Multiplication and exponentiation are the same; just perform the operation
as you normally would and compute the remainder. The distributivity of the
modulus operator enables you to implement this as multiple operations each
followed by modulo, but the end result is the same.
What about division modulo
n
? Can you divide
x
by
y
and then compute
the remainder when divided by
n
? Consider an example. 5
6
30 and 30 %
13
4). Division mod
n
ought to return 6
if you apply it to 5. In other words, you need an operation that, given 4, 5, and
13, returns 6. Clearly, normal division doesn't work at all: (5
4 (because 2 * 13
26 and 30
26
6) % 13
4, but
(4 / 5) % 13
0.8, not 6. In fact, division modulo
n
isn't particularly well defi ned.
You can't really call it division, but you do need an operation referred to as
the
modular inverse
to complete elliptic-curve operations. This is an operation
on
x
such that
x
1
x%n
1
4, you want to discover an
operation to compute a number which, when multiplied by 4 and then computed
% 13 returns 6, inverting the multiplication.
So, going back to the example of (5
6) % 13
Using the Euclidean Algorithm to compute Greatest
Common Denominators
Such an operation exists, but it's not easily expressible; it's not nearly as simple as
modulus addition or multiplication. Typically,
x
-
1
is computed via the extended
Euclidean algorithm. The
normal
(that is, non-extended) Euclidean algorithm
is an effi cient way to discover the greatest common denominator (GCD) of two
Search WWH ::
Custom Search