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.
Search WWH ::




Custom Search