Cryptography Reference
In-Depth Information
Making ECC Work with Whole Integers: Elliptic-Curve
Cryptography over F
p
Now that modular inversions have been defi ned, you can return to the subject
of ECC. ECC over a
prime fi nite fi eld
(denoted F
p
) is just like “regular” ECC, but
everything is performed modulo a prime number
p
. The point-addition and
point-doubling algorithms become:
x
3
(
l
x
1
x
2
)%p
y
3
(
l
(x
1
x
3
)
y
1
)%p
x
1
)
1
%p
l
(y
2
y
1
) * (x
2
and
2
x
3
(
l
2x
1
)%p
y
3
l
(x
1
x
3
)
y
1
)%p
a) * (2y
1
)
1
%p
Point multiplication (by a scalar) is still defi ned in terms of “double-and-add.”
There's just one more defi nitional issue must be addressed here. Recall that
the general form of double-and-add is the following:
sum = 0
double = multiplicand
while ( bits in multilpier )
{
if ( bit set in multiplier )
{
sum += double;
}
double *= 2;
}
(3x
1
2
l
You have
sum += double
and
double *= 2
defi ned for ECC points, but what
about
sum = 0
? You need a “point” which is zero. You can't just use the point
(0, 0). Unless
b
0, (0, 0) is just another point.
ECC sort of sidesteps this by defi ning a non-existent
point at infi nity
, which
you just have to keep track of. A point is either the point at infi nity (for example,
0), or it's something else, in which case it has a legitimate
x
and
y
coordinate.
0 it's not
on
the curve, and if b
Reimplementing Diffi e-Hellman to Use ECC Primitives
So what does all of this
elliptic-curve
stuff have to do with public-key cryptogra-
phy? Recall that RSA and
classic
Diffi e-Hellman get their security and feasibility
from the fact that exponentiation modulo a number is solvable. There's an O(
n
)
algorithm to raise a number to an
n
-bit power modulo a given prime, but there's
no known feasible inverse operation. There's no (known) algorithm to compute
Search WWH ::
Custom Search