encryption method is presented with the novel property
that publicly revealing an encryption key does not thereby
reveal the corresponding decryption key. This has two important
Couriers or other secure means are not needed to transmit
A message can be 'signed' using a privately held decryption
key. Anyone can verify this signature using the corresponding
publicly revealed encryption key...
Shamir, Adleman; A method for obtaining digital signatures
and public-key cryptosystems; Communications of the ACM;
The security of the standard Public Key
Cryptography (PKC) algorithm RSA is founded on the mathematical
difficulty of finding two prime
Historically, most encryption systems depended on a secret key
that two or more parties used to decrypt information encrypted
by a commonly agreed method. The main idea of PKC is the use of
two unique keys for each participant, with a bi-directional encryption
mechanism that can use either key to decrypt information encrypted
with the other key, as described below:
- Public key. One of the keys
allocated to each person is called the "public key",
and is published in an open directory somewhere where anyone
can easily look it up,
for example by email address.
- Private key. Each person keeps their other key
secret, which is then called their "private key".
If John wants to send an encrypted email to Mary, he encrypts
his message with Mary's public key, and then sends it to her. He
doesn't need to be worried about interception or eavesdropping
since the only person that can read the message is Mary, because
she is the only one that has the corresponding private key that
can decrypt it. This powerful architecture has three profound consequences:
- Geography. The sender and the recipient no longer need
to meet or use some other potentially insecure method to exchange
a common secret key. Since everyone has their own set of keys,
then anyone can securely communicate with anyone else by first
looking up their public key and using that to encrypt the message,
secure communication even across great distances
over a network (like the Internet).
- Digital signatures. A
sender can digitally sign their message by encrypting their name
(or some other meaningful document) with their secret key and
then attaching it to a message. The recipient can verify that
the message came from the sender by decrypting their signature
with their public key. If the decryption works and produces a
readable signature, then the message came from the sender because
only they could have encrypted the signature with their private
key in the first place.
- Security. The disclosure of a key doesn't compromise
all of the communications on a network, since disclosure of public
keys is intended, and only messages sent to one person are affected
by the disclosure of a private key.
Details. The algorithms on which
both RSA's and Cock's algorithms are based uses a mathematical
expression built on the multiplication of two large prime numbers
(a number that is the product of only 1 and itself). For example,
the following numbers are the product of two prime numbers:
While RSA's and Cock's algorithm are similar, RSA's is described
in the following because it is the more general case and was published
first. Essentially, the public key is the product of two randomly
selected large prime numbers, and the secret key is the two primes
themselves. The algorithm encrypts data using the product, and
decrypts it with the two primes, and vice versa. A mathematical
description of the encryption and decryption expressions is shown
Encryption: C = M^e ( modulo n )
Decryption: M = C^d ( modulo n )
M = the plain-text message expressed as an integer number.
C = the encrypted message expressed as an integer number.
n = the product of two randomly selected, large primes p and q.
d = a large, random integer relatively prime to (p-1)*(q-1).
e = the multiplicative inverse of d, that is:
( e * d ) = 1 ( modulo
( p - 1 ) * ( q - 1 ) )
The public key is the pair of numbers ( n, e ).
The private key is the pair of numbers ( n, d ).
This algorithm is secure because of the great mathematical difficulty
of finding the two prime factors of a large number, and of finding
the private key d from the public key n. This is difficult because
the only known method of finding the two prime factors of a large
number is to check all the possibilities one by one, which isn't
practical because there are so many prime numbers. For example,
a 128 bit public key would be a number between 1 and
Now, first Euclid proved that there are an infinite number of
primes. Then, the work of Legendre, Gauss, Littlewood, Te Riele,
Tchebycheff, Sylvester, Hadamard, de la Vallée Poussin,
Atle Selberg, Paul Erdös, Hardy, Wright, and von Koch showed that
the number of prime numbers between one and n is approximately
n / ln(n). Therefore, there are about:
2^128 / ln( 2^128 ) =
different prime numbers in a 128 bit key. That means that even
with enough computing power to check one trillion of these numbers
a second, it would take more than 121,617,874,031,562,000 years
to check them all. That's about 10 million times longer than the
universe has existed so far.
Therefore, unless someone makes a very large and unexpected mathematical
breakthrough, it's practically impossible to find out the private
key from a public key with RSA encryption, making it one of the
most secure methods ever invented. However, please note that like
almost all encryption systems, the RSA algorithm is still vulnerable
attacks, when a third party can repeatedly choose (or otherwise
knows) some of the text to be encrypted and can examine the result.
In addition, the promised development of quantum computers over
the next several decades that can effectively perform many calculations
simultaneously may be able
to break the RSA algorithm relatively quickly.