Cryptography Reference
In-Depth Information
The RSA Public-Key Cryptosystem
We break the algorithm into two parts with the underlying assumption that
Alice wants to send a message to Bob.
(I) RSA Key Generation
1. Bob generates two large, random primes
p
=
q
of roughly the same size,
and computes both
n
=
pq
and
φ
(
n
)=(
p
−
1)(
q
−
1)
.
The integer
n
is called his (
RSA
)
modulus
.
2. He selects a random
e
such that 1
<e<φ
(
n
) and gcd(
e, φ
(
n
)) = 1.
The integer
e
is called his (
RSA
)
enciphering exponent.
Then using the
extended Euclidean algorithm (see page 471), he computes the unique
d
∈
N
∈
N
with 1
<d<φ
(
n
) such that
ed
≡
1 (mod
φ
(
n
))
.
3. Bob publishes (
n, e
) in some public database and keeps
d, p, q
, and
φ
(
n
)
private. Thus, Bob's (
RSA
)
public-key
is (
n, e
) and his (
RSA
)
private key
is
d
. The integer
d
is called his (
RSA
)
deciphering exponent
.
(II) RSA Public-Key Cipher
enciphering stage
:
In order to simplify this stage, we assume that the plaintext message
m
∈
M
is in numerical form with
m<n
. Also,
M
=
C
=
Z
/n
Z
, and we assume that
gcd(
m, n
)=1.
1. Alice obtains Bob's public key (
n, e
) from the database.
m
e
(mod
n
) using the repeated squaring
method given on page 171, and sends
c
2. She enciphers
m
by computing
c
≡
∈
C
to Bob.
deciphering stage
:
Once Bob receives
c
, he uses
d
to compute
m
c
d
(mod
n
).
≡
Example 4.5
Suppose that Bob chooses
(
p, q
) = (9221
,
7489)
.Then
n
=
69056069
and
φ
(
n
) = 69039360
.If Bob selects
e
=7
, then solving
1=7
d
+
φ
(
n
)
x
(
for
x
=
4)
, he gets
d
= 39451063
, his private key.Also,
(69056069
,
7)
is
his public key.Alice obtains Bob's public key and wishes to send the message
m
= 7289258
.She enciphers using Bob's public key to get
−
m
7
c
≡
≡
19407420 (mod
n
)
,
which she sends to Bob.He uses his private key
d
to decipher via
c
d
19407420
39451063
≡
≡
7289258
≡
m
(mod
n
)
.
Search WWH ::
Custom Search