Cryptographic Algorithms

Cryprographic Algorithms are really the heart of the matter in cryptology. An algorithm, of course is a "recipe" for doing something on a computer. In cryptology, an algorithm refers to a set of mathematical transformations in order to scramble a message. This message, in classical cryptological parlance is called Plain Text or just PT. Upon being treated by the algorithm it outputs a message which now bears no resemblance to the PT. This, called the Cipher Text (CT) is completely random(ideally). Of course, Shannon's test for perfect secrecy demands that each bit of PT after transformation is either a ‘0’ or a ‘1’ with a probability of exactly 0.5. In practice, that doesn't happen.

Having a good algorithm is central to sound cryptology. Almost equally important is to have a robust KEY. A cryptographic transformation requires a KEY which is some secret information(a series of bits, really) that the algorithm uses when it treats the PT to its mathematical transforms. Ideally, any cryptographic system must use an algorithm which uses a set of fast linear transformations to yield a hard to invert (therefore, highly non-linear) cipher text, unless of course one has the key. Hence, it is so important to keep the key secure.

Examples of cryptographic algorithms are DES(data Encryption Standard), the 3DES (called Three or Triple DES) and AES (Advanced Encryption Standard, actually a flavour of the Rijndael algorithm) to name but a few. Of course, there is then RSA (Rivest,Ron-Shamir,Adi-Adleman,Len). We might as well mention ElGamal; Which compels us to say a word about how cryptographic algorithms (or cryptosystems to make our narrative broader) are classified.

Cryptosystems could use Block ciphers or Stream Ciphers. Quite intuitively, block ciphers work on chunks of bits at a time (called blocks) or they could work on the PT bit by bit in which case they become stream ciphers. Then again cryptosystems could be symmetric or asymmetric. Symmetric ciphers use the same key for encryption as well as for decryption. Obviously, this key needs to be kept private. For this reason, symmetric ciphers are also called private key crypto systems. In contrast, asymmetric cryptosystems use one key for encryption and a related but different key for decryption. One of these keys(depending upon the application) is made public. For this reason, such systems are also called public key crypto systems. RSA and ElGamal are examples of such cryptosystems, whilst DES, 3DES and AES are symmetric key(or private key) crypto systems.

In cryptography, it is always assumed that the adversary knows not only the method (the algorithm) but also the class of methods (Shannon), often considered an independent paraphrasing of the Kerckhoff’s Principle. The interested reader is referred to Shannon’s path breaking work on Communication Theory of Secrecy Systems. Usually, most applications deploy well-know cryptographic algorithms, meaning those that have been well flogged by the cryptanalytical community. Consequently, from a pragmatic point of view, it is prudent to work on the maxim, “All security lies in the Key”. Of course, most secret service agencies of the world work on the contrarian premise of security through obscurity. This of course galls the academicians.

Algorithms that have withstood cryptanalytic attacks are those that are mathematically robust. All algorithms in cryptology are based upon the intractability of some mathematical problem. The RSA problem (large integer factorization) and the Diffie Hellman problem (DH is essentially a problem of discrete logarithm) are ready examples. Ideally, the name of the game is to prove that the mathematical problem is np-complete. That, we all know is not so easy. Therefore, one would want in the minimum to be able to base the algorithmic constructs to fall in the domain of being np-hard. By the way, no cryptographic algorithm bar one is unbreakable. The sole exception is the One Time Pad or OTP for short. A one time pad uses a truly random key string each time, and every message uses a new truly random key. Of course, for reasons that are at once obvious, such systems are impossible to realize in the practical world, more so, in the electronic domain.

Often, what is used as a measure of the robustness of an algorithm is it’s brute force work factor. This assumes that the fundamental mathematics of the algorithm are solid meaning that it isn’t suspect to known cryptanalytic attacks, that it’s structure is strong, that it can withstand complexity theoretic/number theoretic attacks and of course, the mechanism of key selection yields keys that are strong and from a diverse set. Given that all of these (and several others attributes) are true, the only way to rate an algorithm (actually the cryptographic scheme) is to make fantastic assumptions about computing power in the hands of the cryptanalyst (say, the computer can operate on one instruction at a billionth of a second, that there are a billion such processors running in parallel, and that it takes precisely one clock cycle to try out a key, and so on). Then consider all possible keys available (this of course depends upon the key size supported by the algorithm). If even after these assumptions it takes over 10¹⁰ years to try out each possible key, then we say that the cryptographic scheme is “computationally secure”. Of course, this is a rule of the thumb, and not a bad one at that!

References

Menezes, van Oorshot, and Vanstone, Handbook of Applied Cryptography, CRC Press (1997)

Schneier, Bruce, Applied Cryptography, Wiley (1994), 2nd Edition

Bauer, FL, Decrypted Secrets, Methods and Maxims of Cryptology, Springer (2002), 3rd Edition

Herstein, IN, Topics in Algebra, Wiley (1975)

Maintainer: anurag.dave@hsc.com

Views: