|
|
|
|
ENCRYPTION FAQ
|
What are public key algorithms?
Public key algorithms use different keys for encryption and decryption, and the decryption key cannot (practically) be derived from the encryption key. Public key methods are important because they can be used for transmitting encryption keys or other data securely even when the parties have no opportunity to agree on a secret key in private. All known methods are quite slow, and they are usually used only for encrypting session keys (randomly generated "normal" keys), that are then used to encrypt the bulk of the data using a symmetric cipher.
[top]
What are the types of public key algorithms?
RSA
Rivest-Shamir-Adleman is the most commonly used public key algorithm. It can be used both for encryption and for digital signatures. The security of RSA is generally considered equivalent to factoring, although this has not been proved.
RSA computation occurs with integers modulo n = p * q, for two large secret primes p, q. To encrypt a message m, it is exponentiated with a small public exponent e. For decryption, the recipient of the ciphertext c = me (mod n) computes the multiplicative reverse d = e-1 (mod (p-1)*(q-1)) (we require that e is selected suitably for it to exist) and obtains cd = m e * d = m (mod n). The private key consists of n, p, q, e, d (where p and q can be omitted); the public key contains only n and e. The problem for the attacker is that computing the reverse d of e is assumed to be no easier than factorizing n.
The key size should be greater than 1024 bits for a reasonable level of security. Keys of size, say, 2048 bits should allow security for decades.
Diffie-Hellman
DH is a widely used key exchange algorithm. In many cryptographical protocols, two parties wish to begin communicating. However, let's assume they do not initially possess any common secret and thus cannot use secret key cryptosystems. The key exchange by Diffie-Hellman protocol remedies this situation by allowing the construction of a common secret key over an insecure communication channel. It is based on a problem related to discrete logarithms, namely the Diffie-Hellman problem. This problem is considered hard, and it is in some instances as hard as the discrete logarithm problem.
The Diffie-Hellman protocol is generally considered to be secure when an appropriate mathematical group is used. In particular, the generator element used in the exponentiations should have a large period (i.e. order). Usually, Diffie-Hellman is not implemented on hardware.
ElGamal
The ElGamal is a public key cipher. This is a straightforward extension of Diffie/Hellman's original idea on shared secret generation. Essentially, it generates a shared secret and uses it as a one-time pad to encrypt one block of data. ElGamal is the predecessor of DSS and is perfectly usable today, although no widely known standard has been created for it.
DSS
Digital Signature Standard is a signature-only mechanism endorsed by the United States Government. The underlying algorithm DSA (Digital Signature Algorithm) is similar to the one used by ElGamal signature algorithm. Also, it is fairly efficient though not as efficient as RSA for signature verification. The standard defines DSS to use the SHA-1 hash function exclusively to compute message digests.
The main problem with DSS is the fixed subgroup size (the order of the generator element), which limits the security to around only 80 bits. Hardware attacks can be menacing to some implementations of DSS. However, it is widely used and accepted as a good algorithm.
Elliptic curve cryptosystems
Elliptic curve cryptosystems are just another way of implementing discrete logarithm methods. An elliptic curve is basically a set of points that satisfy the equation y2 = x3 + ax + b when considered in finite field of characteristic p (where p must be larger than 3). A slightly different equation is needed for the cases of small characteristic, p = 2 and p = 3.
The points on elliptic curves can be added together and they form a structure called a group (in fact, an abelian group). This is just a way of saying that you can do arithmetics with them as you can do with integers when using only addition and subtraction. With regard to cryptography, elliptic curves have many theoretical benefits but they also are very practical. There is no known sub-exponential algorithm for computing discrete logarithms of points of elliptic curves unlike discrete logarithms in (the multiplicative group of) a finite field, in hyperelliptic curves (of large genus) or in many other groups. One practical benefit from the non-existence of a fast discrete logarithm computation for elliptic curves is that the key size, as well as the produced digital signatures and encrypted messages, are small. Indeed, a very simple way of computing the security limit for the key size is to take a key size for a secret key cryptosystem in bits and then just multiply it by 2. This gives a rough estimation that is good at the moment for a generic instance of elliptic curves. Elliptic curves can be implemented very efficiently in hardware and software, and they compete well in speed with cryptosystems like RSA and DSS. At the moment, elliptic curves are widely known, but not very widely used in practice.
LUC
LUC is a public key cryptosystem that uses a special group based on Lucas sequences (related to Fibonacci series) as its basic building block. It can implement all the common discrete logarithm based algorithms, and in a sense LUC is a class of public key algorithms.
It is possible to view the underlying structure of the algorithm as a certain multiplicative group of a finite field of characteristic p with degree 2 (written shortly as Fp2) - and this can be used to prove that there exists a sub-exponential algorithm for computing discrete logarithms and thus attacking the LUC algorithm. Thus, it might seem that LUC is of little interest, as it is basically just another way of implementing discrete logarithm based algorithms on finite fields. However, LUC uses the specific arithmetic operations derived from Lucas sequences that might be slightly faster (by a constant factor) than what would be a more direct approach.
The fact that values used in the LUC algorithms can be represented as a pair of values gives some additional advantage against just using integers modulo p. The computations only involve numbers needing half the bits that would be required in the latter case. As the LUC group operation is easy to compute, this makes LUC algorithms competitive with RSA and DSS.
However, at present, there appears to be little reason to use LUC cryptosystems as they offer little benefit over elliptic curves or XTR.
XTR
XTR is a public key cryptosystem developed by Arjen Lenstra and Eric Verheul. The XTR is similar to LUC in that it uses a specific multiplicative group of a particular finite field (in fact, Fp6) as its underlying group.
However, XTR has novel features such as needing only approximately 1/3 of the bits for signatures and encrypted messages. This is achieved using a specific trace-representation of the elements of this group, and performing all computations using this representation.
All discrete logarithm based public key algorithms can be implemented with XTR ideas. So, in a way, XTR is a generic name for a class of public key algorithms.
Surprisingly, the algorithm is efficient and according to Lenstra and Verheul, it might be a good substitute for elliptic curves, DSS, and even RSA. It has the advantage over elliptic curves - it is based essentially on the same discrete log problem as, say, DSS, which may help cryptographers and others to accept it faster as a strong algorithm.
[top]
What are secret key algorithms?
Secret key algorithms use the same key for both encryption and decryption (or one is easily derivable from the other). This is the more straightforward approach to data encryption than public key algorithms but it is mathematically less complicated, and has been used for many centuries.
[top]
What is the difference between block ciphers and stream ciphers?
Block ciphers.
Block ciphers transform a fixed-size block of data (usually 64 bits) into another fixed-size block (possibly 64 bits long again) using a function selected by the key. If the key, input block and output block all have n bits, a block cipher basically defines a one-to-one mapping from n-bit integers to permutations of n-bit integers.
Stream ciphers.
A stream cipher consists of a state machine that outputs at each state transition one bit of information. This stream of output bits is commonly called the running key. The state machine is nothing more than a pseudo-random number generator. For example, we can build one from a block cipher by encrypting repeatedly its own output. Typically, more elaborate constructions are used for stream ciphers to obtain high-speed. The encryption can be implemented by just exclusively-oring the running key to the plaintext message.
[top]
What are the types of secret key algorithms?
DES
The Data Encryption Standard is an algorithm developed in the mid-1970s. It was turned into a standard by the US National Institute of Standards and Technology (NIST), and was also adopted by several other governments worldwide. It was, and still is, widely used, especially in the financial industry.
DES is a block cipher with 64-bit block size. It uses 56-bit keys. This makes it susceptible to exhaustive key search with modern computers and special-purpose hardware. DES is still strong enough to keep most random hackers and individuals out, but it is easily breakable with special hardware by government, criminal organizations, or major corporations. DES is getting too weak, and should not be used in new applications.
A variant of DES, Triple-DES (also 3DES) is based on using DES three times (normally in an encrypt-decrypt-encrypt sequence with three different, unrelated keys). The Triple-DES is arguably much stronger than (single) DES, however, it is rather slow compared to some new block ciphers.
Although at the time of DES's introduction its design philosophy was held secret, it did not discourage its analysis. On the contrary, some information has been published about its design, and one of the original designers, Don Coppersmith, has commented that they discovered ideas similar to differential cryptanalysis already while designing DES in 1974. However, it was just a matter of time that these fundamental ideas were re-discovered.
Blowfish
Blowfish was designed by Bruce Schneier. It is a block cipher with 64-bit block size and variable length keys (up to 448 bits). It has gained a fair amount of acceptance in a number of applications, including Nautilus and PGPfone.
Blowfish utilizes the idea of randomized S-boxes: while doing key scheduling, it generates large pseudo-random look-up tables by doing several encryptions. The tables depend on the user supplied key in a very complex way. This approach has been proven to be highly resistant against many attacks such as differential and linear cryptanalysis. Unfortunately, this also means that it is not the algorithm of choice for environments where a large memory space (something like 4096 bytes) is not available.
IDEA
IDEA (International Data Encryption Algorithm) is an algorithm developed at ETH Zurich in Switzerland by Xuejia Lai. It uses a 128 bit key, and it is generally considered to be very secure. It has been one of the best publicly known algorithms for some time. It has been around now for several years, and no practical attacks on it have been published despite of numerous attempts to analyze it.
AES,Rijndael
The AES, Rijndael, was designed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen. Rijndael follows the tradition of square ciphers (it is based on ideas similar to the Square cipher). It performs very well in hardware and software across a wide range of environments in all possible modes. It has excellent key setup time and has low memory requirements, in addition, its operations are easy to defend against power and timing attacks.
MARS
This is an interesting new design (using a special type of a Feistel network), which depends heavily on the instruction sets available on modern 32-bit processors. This is efficient on these target machines, but it may lead to implementation difficulties in cheaper architectures like smart cards.
RC4
RC4 is a cipher designed by RSA Data Security, Inc. It used to be 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 posted algorithm is indeed equivalent to RC4. The algorithm is very fast. Its security is unknown, but breaking it does not seem trivial either. Because of its speed, it may have uses in certain applications. It can also accept keys of arbitrary length. RC4 is essentially a pseudo random number generator, and the output of the generator is xored with the data stream.
RC6
RC6 is designed by Rivest, Robshaw and Yin, RSA Laboratories, and follows the ideas of RC5 - but with many improvements. For example, it attempts to avoid some of the differential attacks against RC5's data dependent rotations. However, there are some attacks that get quite far, and it is unclear whether RC6 is well enough analyzed yet.
[top]
|
Question of the Day
|
|
|
