Note: The following discussion concerns five algorithms, sometimes used in cryptographic systems. These algorithms are used in a number of Internet security related systems. The information in this article was developed from from Internet and other sources by Thomas Jerry Scott for use in his Computer Security classes.

Crypto Algorithms Table of Contents

  1. DES -- the 56 Bit Symmetric Version

  2. IDEA -- the 128 Bit Symmetric Block Algorithm from Europe

  3. RC4 -- a Variable Length Symmetric Stream Algorithm from RSA Data Security

  4. RSA -- the most commonly used Public Key Algorithm

  5. Diffie-Hellman -- the first Public Key Algorithm

  6. Return to the Main Menu

Return to the Beginning of This Document

DES: -- the 56 Bit Symmetric Algorithm

The Digital Encryption Standard was developed by IBM and the National Security Agency (NSA) of the USA in the 50s and forms the basis not only for the Unix password program, but also for the Automatic Teller Machines PIN authentication.

DES uses a key of only 56 bits, and thus it is now susceptible to "brute force" attacks (ie try every possible key and see which decrypts the message), but at a substantial (for a private individual) cost.

Although many rumours have circulated that it was designed to be weak, the evidence apparently is that it was designed as strong as possible, even being designed to resist techniques which were not known in the unclassified world at the time. However the design criteria have never been released.

DES has never been a federal standard, but a variant called Triple-DES or 3DES, is. With 3DES, you have various options. one of which is called the EDE version, which uses two different DES keys.

Suppose we have a Message called M, and two DES keys, called P and Q.

We will use the notation "EP(X)" to mean that message X is DES encrypted with Key P, the notation "DQ(Y)" to mean that the message Y is decrypted with DES key Q.

Using this notation, the steps to encrypt a message using two key, EDE 3DES are as follows,

  1. Step 1: Encrypt message X with key P, giving the result EP(X).

  2. Step 2: Decrypt result of Step 1 with key Q, giving the result DQ(EP(X)).

  3. Step 3: Encrypt result of Step 2 with key P, giving the result EP(DQ(EP(X))).

At this point, the message is ready to be sent across the network.

To decrypt the message, the receiver does the following three steps.

  1. Step 1: Receiver decrypts received message with key P. Since he received


    when he applies DP to the mesage, the result is now DQ(EP(X)).

  2. Step 2: Receiver encrypts result from his Step 1 with key Q. Since EQ undoes the action of DQ, the resulting EQ ( DQ(EP(X)), yields EP(X).

  3. Step 3: The Receiver now decrypts the result of Step 2 with Key P.

    Since the result of Step 2 is EP(X), applying DP to this -- DP (EP(X)) yields X, the original message back.

Other variants of 3DES use three keys.

Return to the Beginning of This Document

IDEA: The 128 Bit Symmetric Block Algorithm

IDEA is a cryptosystem which was developed by Dr. X. Lai and Prof. J. Massey in Switzerland in the early 1990s to replace the DES standard. It is a symmetric algorithm that uses the block method of encryption, encrypting 8 bytes at a time, just like DES, but with a key of 128 bits.

This 128-bit key length makes it impossible to break by simply trying every key, and no other means of attack is known. Since it is relatively new, it has not had as much study as has DES. IDEA is fast, and has also been implimented in hardware.

IDEA was chosen by Phil Zimmermann for PGP after his own attempt at a cypher had been shown to be weak, and apparently because of worries he had about the security and key length of DES.

IDEA is patented in Europe, in the USA and in Japan(pending). PGP has a license to use it for non-commercial use only.

Return to the Beginning of This Document

RC4: A Stream or Character by Character Symmetric Algorithm

RC4 is a cypher invented by Ron Rivest, who is a co-inventor of the RSA cypher. RC4 is claimed as a proprietary system by RSADSI, and was originally considered to be a trade secret of RSADSI. RC4 is used in a number of commercial systems like Lotus Notes and secure Netscape.

In early 1995 a routine was published anonymously on the Newsgroups claiming to be RC4. It was tested against a valid copy of RC4, and the tests seemed to indicate that it acted identically to the the real RC4. To the extent that this alleged RC4 is identical to the real one, it is no longer a trade secret, and is no longer proprietary.

RC4 is a cypher with a key size of up to 2048 bits (256 bytes), which, on the brief examination given it over the past year or so seems to be a relatively fast and strong cypher. It is a " stream " cypher, creating a stream of random bytes and XORing those bytes with the text. Using it with the same key on two different messages makes it very weak. It is thus useful in situations in which a new key can be chosen for each message.

The source (in C for Unix) for the alleged RC4 can be obtained from various Internet sources.

Return to the Beginning of This Document

RSA: The Most Widely Used Public Key Algorithm

RSA is a cypher based on the concept of a trapdoor function. This is a function which is easily calculated, but whose inverse is extremely difficult to calculate. The RSA trapdoor function is factoring large whole numbers.

Take two prime numbers, p and q, (ie numbers which cannot be divided evenly by any other number), and multiply them together to get their product N. This is very easily done. However, if we only know N, then it is extremely difficult to determine what the factors p and q are if N is sufficienlty large. Typically in crypography, N takes a value of greater than 500 bits (150 digits).

The message is written as a series of numbers each of which is smaller than N but has approximately the same length as N. Each of these message numbers M are then multiplied by themselves e times. (In PGP ,e is often taken to have the value 17).

Then the result of that set of multiplications is divided by N, and only the remainder of that division is kept and is the encrypted message.

To decrypt the message, the recipient uses another specially chosen number d, which is typically a very large number (of the order of half the length of N).

This number is chosen so that if we now multiply the encrypted message with itself d times, divide by N, and keep only the remainder, then we get the original message back.

The only way known to find d is to know p and q. e and N are the public key, which is published, while d is the private key, which must be kept secret. e and d are symmetric in that using either as the encryption key, the other can be used as the decryption key. This is what makes signing possible.

RSA is patented in the USA by MIT, who granted exclusive rights to license the product to RSA Data Security, Inc.(RSADSI). The patent expired in 1999, so patent protection is no longer available to RSA. Elsewhere in the world RSA is free from proprietary restrictions to the best of my knowledge except for copyright on code written by RSADSI themselves.

Return to the Beginning of This Document

Diffie-Hellman: The Original Public Key Algorithm

Diffie-Hellman was the first public key cryptographic technique published. It is primarily used for public key exchange for use of some other private key type crypto system. The basis for the technique is the difficulty of calculating logs in modular arithmetic.

Say A and B wish to establish a key. A sends B the number g, the modulus m and the number h1 = g^e1 mod(m), where e1 is a large number (<m). B then sends back to A the number h2 = g^e2 mod(m). They each then use the number k = g^(e1*e2)= h1^e2=h2^e1 mod(m) as the private key.

Any enemy must be able to calculate either e1 from g,m,h1 or e2 from g,m,h2. This is believed to be very very hard for large enough values of g,m.

DH can also be used in a public key crypto system. To use it in this way, the recipient publishes g,m, h1 and the sender chooses a random exponent e2 and sends h2 along with the message encrypted using the private key crypto system and the key k.

This Diffie-Hellman system does not have the feature that one can easily sign messages, as with RSA. It has the political advantage that the patent expires in 1997. It also depends for its security on both recipient and sender choosing exponents e1 and e2 in a strong way.

Return to the Beginning of This Document