Cryptography Reference
In-Depth Information
sign_x = sadd (u_l, sign_u, v_l, sign_v, x_l);
err = mul_l (m_l, mi_l, m_l);
if (E_CLINT_OK == error)
{
error = err;
}
smod (x_l, sign_x, m_l, x_l);
}
return error;
}
10.4.4 Cryptography with Quadratic Residues
We come now to the promised examples for the cryptographic application of
quadratic residues and their roots. To this end we consider first the encryption
procedure of Rabin and then the identification schema of Fiat and Shamir.
4
The encryption procedure published in 1979 by Michael Rabin (see [Rabi])
depends on the difficulty of calculating square roots in
Z
pq
. Its most important
property is the
provable
equivalence of this calculation to the factorization
problem (see also [Kran], Section 5.6). Since for encryption the procedure
requires only a squaring modulo
n
, it is simple to implement, as the following
demonstrates.
Rabin key generation
1.
Ms.
A
generates two large primes
p ≈ q
and computes
n
=
p · q
.
2.
Ms.
A
publishes
n
as a public key and uses the pair
p, q
as private key.
With the public key
n
A
a correspondent Mr.
B
can encode a message
M ∈
Z
n
in the following way and send it to Ms.
A
.
Rabin encryption
1.
Mr.
B
computes
C
:=
M
2
mod
n
A
with the function
msqr_l()
on page 77
and sends the encrypted text
C
to
A
.
2.
To decode the message,
A
computes from
C
the four square roots
M
i
modulo
n
A
,
i
=1
,...,
4
, with the aid of the function
root_l()
(cf. page
205), which here is modified so that not only the smallest but all four square
roots are output.
5
One of these roots is the plain text
M
.
4
For the fundamental concepts of asymmetric cryptography, see Chapter 17.
5
We may assume that
gcd (
M, n
A
)=1
and that therefore there really exist four distinct roots
of
C
. Otherwise, the sender
B
could factor the modulus
n
A
of the receiver
A
by calculating
gcd (
M, n
A
)
. This, of course, is not the way a public key system should operate.
