Cryptography Reference
In-Depth Information
What is interesting is that the message
x
is first raised to the
e
th power during
encryption and the result
y
is raised to the
d
th power in the decryption, and the
result of this is again equal to the message
x
. Expressed as an equation, this process
is:
(
x
e
)
d
x
de
d
k
pr
(
y
)=
d
k
pr
(
e
k
pub
(
x
))
≡
≡
≡
x
mod
n
.
(7.3)
This is the essence of RSA. We will now prove why the RSA scheme works.
Proof.
We need to show that decryption is the inverse function of encryption,
d
k
pr
(
e
k
pub
(
x
)) =
x
.
We start with the construction rule for the public and private
key:
d
·
e
≡
1mod
Φ
(
n
)
.
By definition of the modulo operator, this is equivalent to:
d
·
e
= 1 +
t
·
Φ
(
n
)
,
where
t
is some integer. Inserting this expression in Eq. (7.3):
x
de
x
1+
t
·
Φ(
n
)
x
t
·
Φ(
n
)
x
1
(
x
Φ(
n
)
)
t
d
k
pr
(
y
)
≡
≡
≡
·
≡
·
x
mod
n
.
(7.4)
(
x
Φ(
n
)
)
t
This means we have to prove that
x
x
mod
n
. We use now Euler's The-
orem from Sect. 6.3.3, which states that if gcd(
x
,
n
)=1 then 1
≡
·
x
Φ(
n
)
≡
mod
n
.A
minor generalization immediately follows:
1
t
(
x
Φ(
n
)
)
t
1
≡
≡
mod
n
,
(7.5)
where
t
is any integer. For the proof we distinguish two cases:
First case: gcd(
x
,
n
)=1
Euler's Theorem holds here and we can insert Eq. (7.5) into (7.4):
(
x
Φ(
n
)
)
t
d
k
pr
(
y
)
≡
·
x
≡
1
·
x
≡
x
mod
n
.
q.e.d.
This part of the proof establishes that decryption is actually the inverse func-
tion of encryption for plaintext values
x
which are relatively prime to the RSA
modulus
n
. We provide now the proof for the other case.
Second case: gcd(
x
,
n
)=gcd(
x
,
p
= 1
Since
p
and
q
are primes,
x
must have one of them as a factor:
·
q
)
x
=
r
·
p
or
x
=
s
·
q
,
where
r
,
s
are integers such that
r
<
q
and
s
<
p
. Without loss of generality we
assume
x
=
r
p
, from which follows that gcd(
x
,
q
)=1. Euler's Theorem holds
in the following form:
·
(
x
Φ(
q
)
)
t
mod
q
,
where
t
is any positive integer. We now look at the term (
x
Φ(
n
)
)
t
1
t
1
≡
≡
again:
(
x
Φ(
n
)
)
t
(
x
(
q
−
1)(
p
−
1)
)
t
((
x
Φ(
q
)
)
t
)
p
−
1
1
(
p
−
1)
= 1mod
q
.
≡
≡
≡
Using the definition of the modulo operator, this is equivalent to:
