Cryptography Reference
In-Depth Information
RSA IS SPECIAL
We have mentioned several times that RSA is 'special' in that it allows the naive
digital signature scheme to be realised by essentially swapping the roles of private
and public keys in an RSA cryptosystem. In general, we cannot obtain a digital
signature scheme froman arbitrary public-key cryptosystem in this way. Similarly,
we cannot obtain a public-key cryptosystemby swapping the roles of the signature
and verification keys of any digital signature scheme.
RSA has a special property that facilitates this. Let the verification key of the
signer be (
n
,
e
) and the signature key be
d
. To sign data
m
, the signer first computes
h
(
m
) and then digitally signs
h
(
m
) by raising it to the power
d
modulo
n
:
h
(
m
)
d
mod
n
sig
(
m
)
=
.
The signer then sends
m
and
sig
(
m
) to the verifier. To verify this digital signature,
the verifier computes
h
(
m
) and then verifies
sig
(
m
) by raising it to the power
e
modulo
n
. The verifier now checks to see if:
h
(
m
)
=
sig
(
m
)
e
mod
n
.
If it does then the verifier accepts the digital signature.
We need to determine why this works. Firstly, observe that by one of the basic
rules of exponentiation (see Section 1.6.1):
sig
(
m
)
e
(
h
(
m
)
d
)
e
h
(
m
)
de
mod
n
=
=
.
When we multiply two numbers together it does not matter which number we
write first (for example, 2
×
3
=
3
×
2
=
6), thus:
h
(
m
)
de
h
(
m
)
ed
(
h
(
m
)
e
)
d
mod
n
=
=
.
However, we know from our study of RSA as a public-key encryption scheme
in Section 5.2.2 that raising something to the power
e
and then to the power
d
is equivalent to 'encrypting' it with a 'public' key and then 'decrypting' it with a
'private' key. We saw that for RSA this gets us back to where we started, since
decryption of an encrypted plaintext recovers the original plaintext. Thus:
(
h
(
m
)
e
)
d
=
h
(
m
) mod
n
,
which is what we hoped would happen.
So what is special about RSA? In fact there are two special features:
Similarity of processes
. The first special property is that the encryption and
decryption processes are essentially the same. Encryption and decryption both
use simple modular exponentiation.
Symmetry of exponentiation
. The second special property is that raising a
number to a power
d
and then to a power
e
has the same effect as raising
a number to a power
e
and then to a power
d
. This makes it possible to 'swap'
the roles of the encryption and decryption keys and thus convert an encryption
scheme into a digital signature scheme. Most other public-key cryptosystems
