Cryptography Reference
In-Depth Information
The RSA Method
Creating keys
:
•
Choose two large prime numbers,
p
and
q
(e.g., 512 bits long).
•
Compose
n
=
pq
, where
n
is
N
bits long.
•
Choose an
e>
1 that is relatively prime to (
p
−
1)(
q
−
1).
•
Use
de
=
1 mod (
p
−
1)(
q
−
1) to calculate a
d
.
•
n
and
e
form the public key,
d
forms the private key.
Encryption
:
•
Decompose the plaintext into blocks of
N
−
1 bits each (the last block may
have to be padded).
•
For each block with value
m<n
, calculate remainder
c
from
m
e
after division
by
n.c
, this is the ciphertext block, and it is
N
bits long.
Decryption
:
•
Decompose the ciphertext into
N
-bit blocks.
•
For each block with value
c<n
, the remainder from
cd
after division by
n
is the corresponding plaintext.
Figure 4.17:
The RSA method.
d
is the private key that we will never ever show to anybody. We can basically
forget about
p
and
q
now. We will publish their product,
n
=
pq
, together with
the exponent,
e
, as our public key.
As a result, we have created the key. The encryption looks like this:
1. If key
n
=
pq
is exactly
N
bits long, then we divide the text into blocks
−
1 bits each (we may have to pad; see Section 5.1.2).
2. We take each block with numerical value
m
and calculate the remainder,
m
e
, from division by
n
. This produces the ciphertext block, but has length
N
(we can pad it to bring the ciphertext block and the plaintext block
to the same length, if need be).
of
N
