Cryptographic Algorithms
This page lists commonly used cryptographic algorithms and methods, and tries to givereferences to implementations and textbooks. Where available, comments are also made aboutthe usefulness or other aspects of the algorithms. The comments should be interpreted asthe author's subjective opinion and should not be considered authoritative in any way.
Public key algorithms use a different key for encryption and decryption, and thedecryption key cannot (practically) be derived from the encryption key. Public key methodsare important because they can be used to transmit encryption keys or other data securelyeven when the parties have no opportunity to agree on a secret key in private. All knownmethods are quite slow, and they are usually only used to encrypt session keys (randomlygenerated "normal" keys), that are then used to encrypt the bulk of the datausing a symmetric cipher (see below).
- RSA (Rivest-Shamir-Adelman) is the most commonly used publickey algorithm. Can be used both for encryption and for signing. It is generally consideredto be secure when sufficiently long keys are used (512 bits is insecure, 768 bits ismoderately secure, and 1024 bits is good). The security of RSA relies on the difficulty offactoring large integers. Dramatic advances in factoring large integers would make RSAvulnerable. RSA is currently the most important public key algorithm. It is patented inthe United States (expires year 2000), and free elsewhere.
For information on therecommended key lengths for RSA, see the articleby Bruce Schneier. At present, 512 bit keys are considered weak, 1024 bit keys areprobably secure enough for most purposes, and 2048 bit keys are likely to remain securefor decades.
One should know that RSA is very vulnerable to chosenplaintext attacks. There is also a new timingattack that can be used to break many implementations of RSA. The RSA algorithm isbelieved to be safe when used properly, but one must be very careful when using it toavoid these attacks.
Many implementations of RSA are freely available. See e.g. RSAREF , RSAEURO, SSLeay, PGP source code, Ssh source code, and the Crypto++library. See also ftp.funet.fi:/pub/crypt/cryptography/asymmetric/rsa.
For more information, see e.g.
- Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
- Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to Computer Security.Prentice-Hall, 1989.
- Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill, 1994.
- R. Rivest, A. Shamir, and L. M. Adleman: Cryptographic Communications System and Method.US Patent 4,405,829, 1983. (Available here.)
- Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhauser, 1994.
- The RSA Frequently Asked Questions document by RSA Data Security, Inc., 1995. (Available here.)
- RSA in 3 lines of perl by Adam Back <aba@atlax.ex.ac.uk>, 1995. Available here.
- Sherry Mayo's cryptography page containsa description of RSA.
- Diffie-Hellman is a commonly used public-keyalgorithm for key exchange. It is generally considered to be secure when sufficiently longkeys and proper generators are used. The security of Diffie-Hellman relies on thedifficulty of the discrete logarithm problem (which is believed to be computationallyequivalent to factoring large integers). Diffie-Hellman is claimed to be patented in theUnited States, but the patent expires April 29, 1997. There are also strong rumors thatthe patent might in fact be invalid (there is evidence of it having been published over anyear before the patent application was wiled).
Diffie-Hellman is sensitive to thechoice of the strong prime and the generator. One possible prime/generator pair issuggested in the Photuris draft. Thesize of the secret exponent is also important for its security. Conservative advice is tomake the random exponent twice as long as the intended session key.
One should note the results presented in Brian A. LaMacchia and Andrew M. Odlyzko, Computation of Discrete Logarithms in PrimeFields, Designs, Codes and Cryptography 1 (1991), 47-62. Basically, they conclude thatby doing precomputations, it is possible to compute discrete logarithms relative to aparticular prime efficiently. The work needed for the precomputation is approximatelyequal or slightly higher than the work needed for factoring a composite number of the samesize. In practice this means that if the same prime is used for a large number ofexchanges, it should be larger than 512 bits in size, preferably 1024 bits.
There is also a new timing attack that can beused to break many implementations of Diffie-Hellman.
Many implementations of Diffie-Hellman are freely available. See e.g. RSAREF, RSAEURO, SSLeay, alodes, or Crypto++.
For further information, see e.g.
- Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
- Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to Computer Security.Prentice-Hall, 1989.
- Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill, 1994.
- M. E. Hellman and R. C. Merkle: Public Key Cryptographic Apparatus and Method. US Patent4,218,582, 1980. (Beginning available here.)
- The RSA Frequently Asked Questions document by RSA Data Security, Inc., 1995. (Available here.)
Elliptic curve public key cryptosystems is an emergingfield. They have been slow to execute, but have become feasible with modern computers.They are considered to be fairly secure, but haven't yet undergone the same scrutiny asfor example RSA.
For further information, see e.g.
Several public domain implementations are available. See e.g. the eliptic package.
- DSS (Digital Signature Standard). A signature-only mechanismendorsed by the United States Government. Its design has not been made public, and manypeople have found potential problems with it (e.g., leaking hidden data the signature, andrevealing your secret key if you ever happen to sign two different messages using the samerandom number). It was recently patented by the US government, and there is also anotherpatent on it, which is licensed at an initial payment of USD 25.000 plus royalties in USand Europe.
There should be no reason whatsoever to use DSS for anything (with thepotential exclusion of US government contracts) since better methods are widely available.DSS source code is included in in the Crypto++ library.
- ElGamal public key cryptosystem. Based on the discretelogarithm problem. See e.g. Bruce Schneier: Applied Cryptography, John Wiley and Sons,1994. Elgamal source code is included in the Crypto++ library.
- LUC is a public key encryption system. A short description isin luc-algorithm.txt. It uses Lucas functions instead ofexponentiation. It's inventor Peter Smith has since then implemented four other algorithmswith Lucas functions: LUCDIF, a key negotiation method like Diffie-Hellman; LUCELG PK,equivalent to El Gamal public-key encryption; LUCELG DS, equivalent to El Gamal digitalsignature; and LUCDSA, equivalent to the US Digital Siganture Standard. LUC EncryptionTechnology Ltd (LUCENT) has obtained patents for cryptographic use of Lucas functions inUnited States and New Zealand.
Source code can be found in ftp.funet.fi:/pub/crypt/cryptography/asymmetric/lucand is included in the Crypto++ library.
Secret key algorithms use a the same key for both encryption and decryption (or theother is easily derivable from the other).
- DES is an algorithm developed in the 1970s. It was made astandard by the US government, and has also been adopted by several other governmentsworldwide. It is widely used, especially in the financial industry.
DES is a blockcipher with 64-bit block size. It uses 56-bit keys. This makes it fairly easy to breakwith modern computers or special-purpose hardware. DES is still strong enough to keep mostrandom hackers and individuals out, but it is easily breakable with special hardware bygovernment, criminal organizations, or major corporations. In large volumes, the cost ofbeaking DES keys is on the order of tens of dollars. DES is getting too weak, and shouldnot be used in new designs.
A variant of DES, Triple-DES or 3DES is based on using DES three times (normallyin an encrypt-decrypt-encrypt sequence with three different, unrelated keys). Many peopleconsider Triple-DES to be much safer than plain DES.
Implementations of DES can be found e.g. in the libdes,alodes, SSLeay, Crypto++, descore, chalmers-des, and destoolibraries.
- Blowfish is an algorithm developed by Bruce Schneier. Itis a block cipher with 64-bit block size and variable length keys (up to 448 bits). It hasgained a fair amount of acceptance in a number of applications. No attacks are knownagainst it. (Note: some implementations of blowfish contain aserious implementation bug.)
Blowfish is used in a number of popular softwarepackages, including Nautilus and PGPfone. Implementations of Blowfish can be found e.g. inthe Crypto++ library, and here.
- IDEA (International Data Encryption Algorithm) is analgorithm developed at ETH Zurich in Switzerland. It uses a 128 bit key, and it isgenerally considered to be very secure. It is currently one of the best public knownalgorithms. It is a fairly new algorithm, but it has already been around for severalyears, and no practical attacks on it have been published despite of numberous attempts toanalyze it.
IDEA is patented in the United States and in most of the Europeancountries. The patent is held by Ascom-Tech. Non-commercial use of IDEA is free.Commercial licenses can be obtained by contacting idea@ascom.ch.
Several implementations of IDEA are freely available. See e.g. SSLeay, PGP source code,and Ssh source code, idea86,Crypto++.
- RC4 is a cipher designed by RSA Data Security, Inc. It used tobe a trade secret, until someone posted source code for an algorithm in Usenet News,claiming it to be equivalent to RC4. There is very strong evidence that the postedalgorithm is indeed equivalent to RC4. The algorithm is very fast. Its security isunknown, but breaking it does not seem trivial either. Because of its speed, it may haveuses in certain applications. It can also accept keys of arbitrary length. RC4 isessentially a pseudo random number generator, and the output of the generator is xoredwith the data stream. For this reason, it is very important that the same RC4 key never beused to encrypt two different data streams.
Source code and information about RC4 canbe found here and in many cryptographic libraries, e.g. SSLeay, Crypto++, andSsh source code.
The United States government routinely approves RC4 with 40 bit keys for export. Keysthat are this small can be easily broken by governments, criminals, and amateurs.
It is interesting to know that the exportable version of SSL (Netscape's Secure SocketLayer), which uses RC4-40, was recently broken by at least two independent groups.Breaking it took about eight days; in many major universities (or companies) thecorresponding amount of computing power is available to any computer science major. Moreinformation about the incident can be found on Damien Doligez's SSL cracking page , anda collection of various articles is in a local file.
- SAFER is an algorithm developed by J. L. Massey (one of thedevelopers of IDEA). A paper describing it was publishedrecently. It is claimed to provide secure encryption with fast software implementationeven on 8-bit processors. Two variants are available, one for 64 bit keys and the otherfor 128 bit keys. An implementation is in ftp.funet.fi:/pub/crypt/cryptography/symmetric/safer.
An analysis of SAFER-K64 was presented in Crypto'95 and is in the proceedings.
- Ciphers based on a hash function. Any cryptographically strong hash function (seebelow) can be turned into a cipher. There are several possible arrangements; the generalidea is that the hash function is used as a random number generator, and the hash value isxored with the data to be encrypted. When all bytes of the hash value have been used, anew hash value is obtained by modifying the key (or whatever was hashed) somehow, andtaking a hash of that. The data to be hashed may include a key, the previous hash value, asequence number, previous plaintext, etc.
An example of a hash-based cipher is MDC/SHA;code can be found e.g. in the Crypto++ library.
- Enigma was the cipher used by the Germans in World War II.It is trivial to solve with modern computers; see the CryptBreaker's Workbench tool. This cipher is used by the unix crypt(1) program, whichshould thus not be used.
- Vigenere is a historical cipher mentioned in manytextbooks. It is easily solvable; a program forthis is freely available.
- Several other classical ciphers are described in http://rschp2.anu.edu.au:8080/cipher.html.These ciphers should not be used because they are not secure.
These and a number of other ciphers are available from ftp.funet.fi:/pub/crypt/cryptography/symmetric.
Many commonly used ciphers (e.g., IDEA, DES, BLOWFISH) are block ciphers. This meansthat they take a fixed-size block of data (usually 64 bits), an transform it to another 64bit block using a function selected by the key. The cipher basically defines a one-to-onemapping from 64-bit integers to another permutation of 64-bit integers.
If the same block is encrypted twice with the same key, the resulting ciphertext blocksare the same (this method of encryption is called Electronic Code Book mode, or ECB).This information could be useful for an attacker.
In practical applications, it is desirable to make identical plaintext blocks encryptto different ciphertext blocks. Two methods are commonly used for this:
- CFB mode: a ciphertext block is obtained by encrypting the previous ciphertextblock, and xoring the resulting value with the plaintext.
- CBC mode: a ciphertext block is obtained by first xoring the plaintext block withthe previous ciphertext block, and encrypting the resulting value.
The previous ciphertext block is usually stored in an Initialization Vector (IV). Aninitialization vector of zero is commonly used for the first block, though otherarrangements are also in use.
More information on cipher modes can be found e.g. in Bruce Schneier: AppliedCryptography, John Wiley & Sons, 1994.
- MD5 (Message Digest Algorithm 5) is a secure hash algorithmdeveloped at RSA Data Security, Inc. It can be used to hash an arbitrary length bytestring into a 128 bit value. MD5 is in wide use, and is considered reasonable secure.
However,some people have reported potential weaknesses in it, and "keyed MD5" (typicallyused for authentication by having a shared secret, and computing an authentication valueby hashing first the secret (as a key), and then the data to be hashed) has been reportedto be broken. It is also reported that one could build a special-purpose machine costing afew million dollars to find a plaintext matching given hash value in a few weeks.
MD5 is available from ftp.funet.fi:/pub/crypt/hash/mds/md5. It is also included in PGP source code, SSLeay, RSAREF, Crypto++, and Ssh sourcecode. MD5 is described e.g. in Bruce Schneier: Applied Cryptography, John Wiley &Sons, 1994.
- MD2, MD4: These are older hash algorithms from RSA Data Security. Theyhave known flaws, and their use is not recommended. Source code for MD2 is included atleast in SSLeay and RSAREFon the software page. They are also available from ftp.funet.fi:/pub/crypt/hash/mds .
- SHA (Secure Hash Algorithm) (also SHS, Secure HashStandard): This is a cryptographic hash algorithm published by the United StatesGovernment. It produces an 160 bit hash value from an arbitrary length string. Many peopleconsider it quite good. It is a fairly new algorithm.
SHA is available from ftp.funet.fi:/pub/crypt/hash/sha, and isincluded in many cryptographic libraries, such as Crypto++.
- Tiger is a new hash algorithm developed by Anderson and Biham. It is availablefrom ftp.funet.fi:/pub/crypt/hash/tiger.
- Most recent hash algorithm is RIPEMD-160, which is designed to replace MD4 andMD5. It produces a digest of 20 bytes, reportedly runs at 40 Mb/s on a 90 MHz Pentium andhas been placed in the public domain by its designers. (Source code)
Cryptographic systems need cryptographically strong random numbers that cannot beguessed by an attacker. Random numbers are typically used to generate session keys, andtheir quality is critical for the quality of the resulting systems. The random numbergenerator is easily overlooked, and becomes the weakest point of the system.
Some machines may have special purpose hardware noise generators. Noise from the leakcurrent of a diode or transistor, least significant bits of audio inputs, times betweeninterrupts, etc. are all good sources of randomness when processed with a suitable hashfunction. It is a good idea to acquire true environmental noise whenever possible.
Examples of cryptographic random number generators can be found e.g. in PGP source code, Noiz, and Ssh source code.
Disclaimer: Any opinions and evaluations presented here are speculative, and the authorcannot be held responsible for their correctness.