previous |
start |
next
RSA
In 1978, Rivest, Shamir and Adleman of MIT proposed a
number-theoretic way of implementing a Public Key Cryptosystem.
Their method has been widely adopted. The basic technique is:
- Choose two large prime numbers,
p
and
q
.
- compute
n = p * q
and
x = (p-1)*(q-1)
- Choose a number relatively prime to
x
and
call it e
. This means that
e
is not a prime factor of
x
or a multiple of it.
- Find
d
such that
e * d = 1 mod x
.
To use this technique, divide the plaintext (regarded as a bit
string) into blocks so that each plaintext message
P
falls into the interval
0 <= P < n
.
This can be done by dividing it into blocks of
k
bits where k
is the
largest integer for which
2k < n
is true.
To encrypt:
C = Pe (mod n)
To decrypt:
P = Cd (mod n)
The public key, used to encrypt, is thus:
(e, n)
and the private key, used to
decrypt, is (d, n)
)
previous |
start |
next