Cryptography Reference
In-Depth Information
n
we have
g
k
g
de
−
1
gg
−
1
odd
r
and
t
1mod
n
,and
therefore
g
k/
2
is a square root of 1 modulo
n
, of which there are four: In addition
to
≥
1
. For every
g
∈
Z
≡
≡
≡
1mod
q
. Thus
p |
(
x −
1)
and
q |
(
x
+1)
(cf. Section 10.4.3). By calculating
p
= gcd(
x −
1
,n
)
one thus obtains the factorization of
n
(cf. page 212).
Possibilities for attacking the RSA algorithm other than factorization of the
modulus are either as expensive as this or rely on the special weaknesses of
individual protocols used in implementing the RSA cryptosystem, but do not rely
on the RSA algorithm itself. Based on the current state of knowledge the following
conditions lead to opportunities to attack the RSA algorithm:
±
1
there are the roots
±
x
with
x
≡
1mod
p
and
x
≡−
1.
Common modulus
The use of a common modulus for several participants leads to an obvious
weakness: Based on what we have just said, each participant can use his
or her own key components
e
and
d
to factorize the common modulus
n
=
pq
. From a knowledge of the factors
p
and
q
as well as the public key
components of other participants with the same modulus their secret keys
can be calculated.
2.
Small public exponents
Since the computational time for the RSA algorithm for a given modulus
depends directly on the size of the exponents
e
and
d
, it would appear
attractive to choose these as small as possible. For example,
3
,as
the smallest possible exponent, requires only one squaring and one
multiplication modulo
n
, so why not save valuable computing time in this
way?
Let us assume that an attacker was able to capture three encoded messages
C
1
,
C
2
,and
C
3
, each of which encodes the same plain text
M
, encoded
with the keys
3
,n
i
of three different recipients:
C
1
=
M
3
mod
n
1
,C
2
=
M
3
mod
n
2
,C
3
=
M
3
mod
n
3
.
It is highly probable that
gcd (
n
i
,n
j
)=1
for
i
=
j
, so that the attacker
can use the Chinese remainder theorem (cf. page 203) to find a value
C
for
which
C ≡ M
3
mod
n
1
n
2
n
3
.
Sinceitisalsotruethat
M
3
<n
1
n
2
n
3
, we have that
C
is actua
lly
equal
to
M
3
, and the attacker can obtain
M
directly by calculating
√
C
. Such
assaults, known as broadcast attacks, can always be carried out when the
number of cryptograms
C
i
is greater than the public exponent, and this
holds even if the plain texts to be encoded are not identical but are merely
linearly dependent on one another, that is, if relations like
M
i
=
a
+
b
3
M
j
hold (cf. [Bone]). To avoid such an attack it is therefore necessary to choose
the public exponents not too small (in no case less than
2
16
+ 1 = 65537
)
·
