Cryptography Reference
In-Depth Information
KeyGen
(
κ
): (Assume
κ
even.) Generate two distinct primes
p
and
q
uniformly at random in
the range 2
κ/
2
−
1
<p,q<
2
κ/
2
.Set
N
pq
so that 2
κ
−
2
<N<
2
κ
is represented by
κ
bits
(see Exercise
24.1.1
to ensure that
N
has leading bit 1).
Choose a random
κ
-bit integer
e
coprime to (
p
−
1) and (
q
−
1) (or choose
e
=
2
16
=
+
1
=
65537 and insist
p,q
≡
1 (mod
e
)). Define
d
=
e
−
1
(mod
λ
(
N
)) where
λ
(
N
)
=
lcm(
p
−
1
,q
−
1) is the
Carmichael lambda function
. Output the public key
pk
=
(
N,e
) and the private key
sk
=
(
N,d
).
R
enam
ing
p
and
q
,
if necessary, we may assume that
p<q
.Then
p<q<
2
p
and so
√
N/
2
<p<
√
N
.
In textbooks, the message space and ciphertext space are usually taken to be
C
κ
=
M
κ
=
(
Z
/N
Z
)
∗
, but it fits Definition
1.3.1
better (and is good training) to define them to
be
C
κ
={
0
,
1
}
κ
and
M
κ
={
0
,
1
}
κ
−
2
κ
−
1
.
or
{
0
,
1
}
Encrypt
(
m
,
(
N,e
)): Assume that
m
∈
M
κ
.
m
e
(mod
N
) (see later for padding schemes).
Return the ciphertext
c
.
Compute
c
=
c
d
(mod
N
) and output either
m
,or
⊥
if
m
Decrypt
(
c
,
(
N,d
)): Compute
m
=
∈
M
κ
.
Sign
(
m
,
(
N,d
)): Compute
s
=
m
d
(mod
N
).
Verify
(
m
,
s
,
(
N,e
)): Check whether
m
≡
s
e
(mod
N
).
Box 24.1
Textbook RSA public key encryption and signature schemes
24.1.1 Efficient implementation of RSA
As we have seen in Section
12.2
,
κ/
2-bit probable primes can be found in expected time
of
O
(
κ
5
) bit operations (or
O
(
κ
4
+
o
(1)
) using fast arithmetic). One can make this provable
using the AKS method, with asymptotic complexity
O
(
κ
5
+
o
(1)
) bit operations using fast
arithmetic. In any case, RSA key generation is polynomial-time. A more serious challenge
is to ensure that encryption and decryption (equivalently, signing and verification) are as
fast as possible.
Encryption and decryption are exponentiation modulo
N
and thus require
O
(log(
N
)
M
(log(
N
))) bit operations, which is polynomial-time. For current RSA key
sizes, Karatsuba multiplication is most appropriate; hence, one should assume that
M
(log(
N
))
log(
N
)
1
.
58
. Many of the techniques mentioned in earlier chapters to speed
up exponentiation can be used in RSA, particularly sliding window methods. Since
e
and
d
are fixed, one can also precompute addition chains to minimise the cost of exponentiation.
In practice, the following two improvements are almost always used.
=
Small public exponents
e
(also called
low-exponent RSA
). Traditionally,
e
=
3was
2
16
proposed, but these days
e
1 is most common. Encryption requires
only 16 modular squarings and a modular multiplication.
=
65537
=
+
