Not all of the encryption algorithms in existence were presented for consideration for the AES. Some were reserved for copyright reasons. And there were also algorithms that were submitted but not selected for the original 15. These algorithms have not disappeared. It is likely that they will be encountered form time to time. Among them are:
You can obtain more information about these algorithms at the following web sites:
The algorithm which were considered for the first round of the AES selection process, as well as some of their proponents are listed next:
The DES and AES are examples of private key algorithms. The keys are kept secret, and the key is the same on both ends of the link. A completely different type of cryptographic algorithm, the public key algorithm, was introduced by Whitfield Diffie and M.E. Hellman in 1976.[*] (See the section "Cryptographic Keys: Private and Public" earlier in this chapter for an introduction.) Two examples of public key cryptography (PKC) are the Merkle and Hellman trap-door knapsack encryption method[
] (which was broken in 1982) and the RSA algorithm introduced by Ronald Rivest, Adi Shamir, and Leonard Adleman.[
]
[
] Merkle and M.E. Hellman, "Hidden Information and Signatures in Trapdoor Knapsacks," [] Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," The very first public key algorithm, proposed by Diffie and Hellman, cannot be used for encrypting messages or files by itself, but can be used to exchange keys used with other cryptosystems, and also for identification and related purposes. Drs. W. Diffie and M.E. Hellman disclosed this method in a 1976 paper entitled "New Directions in Cryptography." The security of the Diffie-Hellman public key system is based on the mathematical difficulty of the discrete logarithm problem. For this scheme to be secure, the keys have to be long.
One particular implementation of the Diffie-Hellman algorithm, included by Sun Microsystems as part of its widely used Network File System (NFS) protocol, used keys of 192 bits. In 1989, at AT&T's Bell Laboratories, Andrew Odlyzko and Brian LaMacchia broke this particular discrete logarithm problem. With their solution, it's possible to calculate the secret key using only a few minutes of computer time (although the program that implements the calculation took months of time by cryptography experts to develop). One important result of the work of Odlyzko and LaMacchia is that for secure operations, it shows that you have to use public key algorithms with long keys. This increases the computational burden on the machines used to encoded and decode the messages.
7.4.3. The RSA Algorithm
Typically, private key algorithms such as DES can't protect against fraud by the sender or the receiver of a message. (The reason being that the key used to encrypt the DES message could have been stolen and used to encrypt a message by a false entity.) The RSA algorithm, on the other hand (as well as some other public key algorithms), provides authentication (a way of ensuring that a message was sent by a certain user), as well as encryption. Named for its developers, Rivest, Shamir, and Adleman, who invented the algorithm at MIT in 1978, the algorithm uses two keys: a private key and a public key. With RSA, there is no distinction between the function of a user's public and private keys. A key can be used as either the public or the private key.
The keys for the RSA algorithm are generated mathematicallyin part, by combining prime numbers. Most big numbers can be built by multiplying smaller ones together. Once you do this, the smaller numbers will be mathematically related, and knowing one can help you determine the other. This is the situation you are looking for with private/public key pairs. But once the numbers get really huge, knowing one of the factors does not mean it is easy to find its companion. There are many false choices, and only the right one will help decrypt the message. The security of the RSA algorithm, and others like it, depends on the use of very large numbers. (Most versions of the RSA use 154-digit or 512-bit keys.) It is hard, sometimes impossible, to reliably factor extremely large numbers, such as those that are hundreds of digits long. Some research efforts have succeeded in cracking very large numbers, but it's still highly unlikely that an intruder will choose number-cracking as a cost-effective way to break into a system.
Rivest, Shamir, and Adleman licensed the patent on the algorithm from MIT, and in 1982 began offering the algorithm as a commercial product. A number of government and corporate users now use the RSA algorithm; these include Lotus Development (in its Notes groupware product), the U.S. Navy, the Department of Labor, and a number of other federal agencies and universities. Although the RSA algorithm is patented inside the United States, it cannot be patented abroad (because the algorithm was published before it was patented), so it is in fairly wide use outside this country.
7.4.4. Digital Signatures and Certificates
In addition to providing encryption and message authentication, some encryption systems also use an authentication tool called a digital signature to verify the origin of the message and the identity of the sender and to resolve any authentication issues between sender and receiver. A digital signature is distinct for each specific transaction. It is unforgeable and can potentially be used as a valid signature in legal contracts. Public key encryption systems such as the RSA can produce digital signatures quite readily. When a message is encrypted at the sender's end, the sender's key digitally signs the message. When the message is decrypted at the recipient's end, the receiver's key is used to validates the digital signature. If any alteration in either signature or message occurs, the signature won't verify any more.
An algorithm that provides both encryption and a digital signature might work like this. Suppose Joe is sending a message to Claudia:
Joe encrypts the message with his private key (to sign it).
Joe now applies Claudia's public key to the message (to keep it a secret from anyone but Claudia).
Now, suppose Claudia has received a message, supposedly from Joe:
Claudia decrypts the message with her private key (to validate the signature that is part of the message).
Claudia now applies Joe's public key to the message to verify that he sent the message. (It won't validate unless Joe's private key was used to encode it.)
There has been discussion about expanding the use of digital signatures so they can be used as digital pseudonyms. This would be a way of preventing attackers (people trying to intercept a message) from figuring out a sender's identity via cross-matching or other techniques.
7.4.4.1. Certificates
In cryptography, a public key certificate (or identity certificate) is a short document that can be used to verify that a public key belongs to an individual. The certificate uses a digital signature to bind together a public key with information such as the name of a person, an organization, or address information.
A certificate usually follows the ITU-T X.509 standard, which includes the following:
The public key being signed.
A name, which can refer to a person, a computer, or an organization.
A validity period during which the certificate should be considered to be reliable.
The Internet address (URL) of a revocation center that can be consulted to determine if the certificate has been declared to be invalid.
Certificates make it possible to use public-key cryptography on a large scale. To securely exchange secret keys between network users becomes impractical as the number of users increases beyond a few (the key distribution problem). The system used to exchange keys as networks scale in size is called the Public Key Infrastructure (PKI). If user Beatrice wants others to be able to send her encrypted messages, she publishes her public key. Anyone who obtains it can then send her a secure message.
7.4.4.2. Certificate Authorities
Unfortunately, user Mark can outwit Beatrice by publishing a public key for which he, not Beatrice, has the associated private key. Mark then claims that the public key belongs to Beatrice and intercepts some of the messages intended for her. Beatrice can counter this, however, by building her public key into a certificate requesting that a third party digitally sign it. Anybody who trusts the third party can then check the certificate to see whether the embedded public key is truly Beatrice's.
In this PKI, the third party is a Certificate Authority (CA). The CA is must be trusted by all participants, that is, each user must decide whether to trust the CA when the CA asserts that a particular public key belongs to a particular user.
There are many commercial CAs that charge for their services. Institutions and governments may have their own CAs. You can find free CAs on the Internet. In a large network, users may not be familiar with each other's certificate authority. In this case, appeal is made to a higher level Certificate Authority, sometimes called CA2. This can be accomplished by including the public key of the local CA, signed by a higher level CA, which is likely to be recognized by the message recipient. This leads to a hierarchy of certificates, with the root certificate at the top. The root certificate represents a CA that is so central and well known that no additional third-party authentication is needed.
If it is discovered or suspected that a given private key has been compromised, or if the relationship between a certificate and a private key is no longer valid (by a person changing jobs, for instance), it is possible to revoke a certificate. This is done by placing it onto a certificate revocation list (CRL), which is stored at the revocation center, and which should be scanned when two computers need to trust each other.
A final note about certificates is that they are built on varying levels of trust. The level of trust dictates how sure you can be that the individual who owns the digital certificate is real, or is who she claims to be. Validation checking can encompass checking the corporate registry and legal status of a company, verifying whether or not they truly own the domain for which they wish to obtain a certificate. You should also check the ID of the person making the request; make sure he is an authorized representative of the requesting organization.
7.4.5. Government Algorithms
NSA has always had secret algorithms that it guards very closely. Some of these are now available to members of the Commercial Communications Security Endorsement Program (CCEP) for inclusion in so-called "high-grade" cryptographic products. Founded in 1984, CCEP is a business relationship designed to combine government cryptographic knowledge with corporate product development expertise. Through CCEP, several dozen companies have developed cryptographic products.
NSA and NIST have also joined forces to create a joint committee that's developing a set of new algorithms for use with sensitive, unclassified information. Several algorithms are known to be under consideration:
A DES-like algorithm used to protect confidentiality.
A public key algorithm used to distribute keys for the confidentiality algorithm.
An algorithm used to provide a digital signature for messages. This algorithm would perform a one-way hash of the message.
A second algorithm used to provide a digital signature for messages. This algorithm would sign the hash in digital fashion.
