Cryptography Reference
In-Depth Information
QR
n
has precisely
four square roots modulo
n
, exactly one of which is again an element of
QR
n
.This
unique square root of
x
is called the
principal square root
of
x
modulo
n
.Ifwe
revisit the example introduced earlier, then it is easy to see that
n
=21=3
If
n
is a Blum integer, then it can be shown that
x
∈
·
7 is a
Z
21
,
J
21
,
QR
21
,and
QR
21
are specified
earlier. If we set
x
=4, then we can determine the four square roots 2, 5, 16, and
19. Obviously, 16 is the principal square root of 4 modulo 21 (because it is again an
element of
QR
21
).
If
n
is a Blum integer, then the function
f
:
QR
n
→
Blum integer (i.e., 3
≡
7
≡
3(mod4)).
QR
n
defined by
f
(
x
)=
x
2
(mod
n
) represents a trapdoor permutation. The trapdoor information
is the factorization of
n
; thus, knowing the prime factors of
n
, one can efficiently
compute the inverse function
f
−
1
:
f
−
1
(
x
)=
x
((
p−
1)(
q−
1)+4)
/
8
(mod
n
)
This trapdoor permutation is used, for example, by the Rabin asymmetric
encryption system (see Section 14.2.2).
3.4
ELLIPTIC CURVES
Elliptic curve cryptography
(ECC) is a hot topic in contemporary cryptography. We
elaborate on ECC in Section 7.6. The algebraic structures emplyoyed by ECC are
groups of points on elliptic curves defined over a finite field
F
n
. In applications,
n
is typically an odd prime or a power of 2 (i.e., 2
m
for some
m
). To keep
things as simple as possible, we restrict our explanations to elliptic curves over
Z
p
=
where
p
is an odd prime number. Furthermore, we don't
look at the general case. We restrict ourselves to a simple case in which an elliptic
curve over
{
0
,
1
,...,p
−
1
}
Z
p
can then be defined as
y
2
x
3
+
ax
+
b
(mod
p
)
≡
(3.7)
∈
Z
p
and 4
a
3
+27
b
2
with
a, b
≡
0(mod
p
). For any given
a
and
b
in
Z
p
, (3.7) has
pairs of solutions
x, y
in
Z
p
that can be expressed as follows:
E
(
Z
p
)=
{
(
x, y
)
|
x, y
∈
Z
p
and
y
2
x
3
+
ax
+
b
(mod
p
)and
4
a
3
+27
b
2
≡
≡
0(mod
p
)
}
