[ 9]. In equation form, the theorem
may be rendered as:
a p– 1 = 1 (mod p)
The theorem has been mathematically extended to form the basis
for public-private key cryptography,
and is exemplified in the RSA public
key algorithm. RSA is named for
Ron Rivest, Adi Shamir, and Leonard
Adleman, who invented the method in 1978 [ 4]. In this method two
very large prime numbers, p and q, are established, and their product
is referred to as the quantity n. A number e is chosen that is greater
than 1 and less than n ( 1< e < n). Furthermore, e and (p – 1)(q – 1) must
have no common prime factors, and as such, will be relatively prime.
The number e does not have to be prime, but will be odd. Once these
quantities have been determined, the basis for the process is established. The steps of the algorithm in list form are as follows [ 3, 4]:
Figure 3: Asymmetric-key encryption.
1. Choose two large prime numbers p and q.
2. Multiply p by q to obtain n.
3. Multiply p – 1 by q – 1 to obtain φ.
4. Select a random integer e such that e and φ are relatively prime.
5. Calculate d such that d ∙ e = 1 (mod φ).
The receiver makes the numbers e and n public while keeping φ and
d private [ 4].
The equations for encryption and decryption are [ 4]:
C = Pe (mod n)
The ciphertext, C , is modulus-n of the value representing the
plaintext, P, raised to the power of e.
P = Cd(mod n)
The plaintext, P, is modulus-n of the value representing the
plaintext, C, raised to the power of d.
Other methods exist in digital encryption that utilize the public and
private key concept. One of the more well-known of these is the Diffie-Hellman system. This method was proposed by Whitfield Diffie and
Martin Hellman in a 1976 paper they authored titled, “New Directions
in Cryptography.” The process facilitates secure key exchange by using
public keys to exchange private keys [ 2, 4]. These mathematical processes
are at the heart of security mechanisms in current communications systems. I will discuss the concepts of some of these mechanisms shortly.
A definite parallel can be drawn when considering the encryption of
modern digital keys and the historic
method of concealed codebooks, cipher tables, and keys, and the efforts
made to keep them out of the wrong
hands. Concealment, control, and
containment of keys (and codebooks
in the olden days) were, and still are,
major concerns of any system of data
encryption. The public and private key
systems such as RSA and Diffie-Hellman, form the basis for current
The public-private key system provides a solution to key distribution security pitfalls that exist in symmetric-key systems. The fact that
two distinct keys, held by separate parties, are used for the encryption
and decryption processes adds more built-in security to the arrangement [ 1]. Let us now examine the asymmetric-key process. As shown
in Figure 3, the sender obtains the receiver’s public key, available to
all. This key may be obtained from any accessible source including the
Internet. After encrypting the message with this key, the data or message is sent. The intended receiver is capable of decrypting the message with a second key that is not accessible in a public manner.
Mathematical “safety” is provided in a system like RSA by forcing
any would-be cipher-breaker to factor a very large number. The
larger the number, the more unlikely it is that the factoring can be
accomplished in any reasonable amount of time [ 3].
Although in this arrangement, an eavesdropper can intercept the
encrypted message, they will not be able to read it without the private key. However, there does exist the possibility that an eavesdropper can “digitally pose” as the original sender, by encrypting it with
the public key and sending the information to the receiver. While
asymmetric-key encryption can provide secrecy of communication,
when used alone it cannot guarantee the identity of the sender. This
is where methods of authentication, the process that seeks to validate
the identity of the communicating parties, come into play.
Authentication may be established by methods such as digital signatures and certificates. Digital signatures are concerned with ensuring that a message has originated from a known and trusted source.
This method is basically the asymmetric-key process in reverse. With
a digital signature, the sender encrypts the data to be sent with his or
her private key and sends the message. The receiver decrypts the message using the public key of the sender. In this way, since only the
sender holds the private, secure key, it can be presumed with a certain
level of confidence that the source of the message is indeed valid [ 1].
Digital certificates seek to reduce some of the potential hazards of
digital signatures. These could include for example, decrypted signatures
Figure 4: The digital signature, a reverse asymmetric-key encryption.