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