Monday, 8 June 2015

Math and Computer & Web Security - Cryptography

A military commander wants some assurance that the information sent to field commanders does not fall into the hands of opponents. Hence, written communications which can be easily read if intercepted by an an enemy are dangerous. (Asking the messenger to memorize secret messages is not practical, and if one can believe the spy and counter-terrorism thrillers currently on TV, not secure.) Julius Caesar is often credited with one of the earlier attempts at using a cryptological system with a mathematical flavor to disguise messages. It is claimed that he used a system in which each letter of the alphabet in a "plaintext," the original message, is replaced by the next letter of the alphabet, with the last alphabet letter cycling around to be represented by the first letter of the alphabet. Thus, the phrase Caesar Cipher would be replaced by Dbftbs Djqifs. Coming across a message such as this, one is faced with the tremendous range of possible systems that might have been used to disguise the original message. It might confuse the "enemy" for a while. Within the range of what today have come to be called Caesar Ciphers, one could shift the replacement alphabet by r places, rather than 1 place (r =1) in the example above. When r = 5 the phrase Caesar Cipher becomes hfjxfw hnumjw.

However, if a decoder hits on the idea that the way the plaintext is being disguised is to shift each letter by the same number of positions, it is not very much work, with the English alphabet of 26 letters, to try them all. This simple example already shows the interesting connection between "complexity" issues and security, whether it be Internet use of cryptography or military use. In some situations slowing down one's opponent is good enough. If it takes an hour to decode a message whose information content is valueless after an hour, then the coding system has done its job. However, if a message is decoded, then the next time a similar message is intercepted, the time to recover the hidden information could go down from an hour to 3 minutes. Then I must keep finding ways to stay a step ahead of my "enemy." In this discussion I will use the words code and cipher and decode and decipher interchangeably. However, usually a cipher refers to replacing a symbol of a plaintext alphabet by another single symbol from some other alphabet or the same alphabet. By contrast, a code refers to replacing blocks of symbols in the plaintext, by another block of symbols.

There have been many developments in cryptography since the Caesar Cipher. One simple idea is not to use the same word lengths in the enciphered message as in the original. If the word "I" or "a" is left as a single letter in the "ciphertext," then it greatly simplifies the process of breaking the encryption system. Typically, the message is broken up into groups of 5 letters (disregarding spaces between words, and often punctuation) and replaced by 5 other letters. This has the effect of making the coded message look more "anonymous." If the length of the original message is not a multiple of five, then extra symbols, called nulls in the "trade," are added to fill out the needed positions.

Another simple idea is the use of a polyalphabetic cipher, where the alphabet used to encode the plaintext changes with each letter in accordance with some key. Using the key provides a way to change the alphabet used for the encoding as one matches a plaintext letter to a letter in the key. This idea was pioneered by Leone Alberti (1404-1472), who was also a pioneer of projective geometry. It is tempting to believe that such a "complex" system would be unbreakable. However, if the key length is short and there is lots of ciphertext available using the same system, then statistical methods can be used to break the cipher. If a key is used only once and is generated at random, the so-called one-time pad, then the cipher is not breakable. However, key exchange and generation of large amounts of random key present a significant problem for the volume of communications that we want to secure in modern times.

No comments:

Post a Comment