Cryptography Reference
In-Depth Information
Z
21
are drawn
in the circle. Each quarter of the square comprises 3 elements. The upper right
quarter represents
QR
21
The example is illustrated in Figure 3.3. The elements of
QR
21
.
QNR
21
and the lower left quarter represents
Z
21
comprises all elements of
that are not elements of
QR
21
(i.e.,
QNR
21
=
{
2
,
5
,
8
,
10
,
11
,
13
,
17
,
19
,
20
}
).
' 0'
'
0
9
3
8
4
'
2
1
0
'
0'
3
5
6
7
:
3
9
3
,
QR
21
,and
QR
21
.
The elements of
Z
21
Figure 3.3
Consequently, in this example the QRP is to decide whether a particular
element of
J
21
is an element of
QR
21
or
QR
21
. It goes without saying that the
factorization of 21 must not be known. Many public key cryptosystems take their
security from the intractability of the QRP.
3.3.8
Blum Integers
Many (public key) cryptosystems use Blum integers as formally introduced in
Definition 3.33.
28
Definition 3.33 (Blum integer)
A composite number
n
is a
Blum integer
if
n
=
pq
where
p
and
q
are distinct prime numbers satisfying
p
≡
q
≡
3(mod4)
.
28
One example is the Rabin asymmetric encryption system addressed in Section 14.2.2.