Cryptography in Information Security

From Computing and Software Wiki

Revision as of 03:50, 3 April 2009

Introduction

The word cryptography comes from two Greek words meaning "secret writing" and is the art and science of concealing meaning. Cryptanalysis is the breaking of codes. The basic component of cryptography is a cryptosystem. Quintuple (E, D, M, K, C) – M set of plaintexts – K set of keys – C set of ciphertexts – E set of encryption functions – D set of decryption functions

The goal of cryptography is to keep enciphered information secret. An adversary wishes to break a ciphertext. Standard cryptographic practice is to assume that one knows the algorithm used to encipher the plaintext, but not the specific cryptographic key (in other words, she knows D and E). One may use three types of attacks.

Classical Cryptosystems

Classical cryptosystems (also called single-key or symmetric cryptosystems) are cryptosystems that use the same key for encipherment and decipherment. So the sender, receiver share common key

Keys may be the same, or trivial to derive from one another. The are sometime called symmetric cryptography.

Cæsar cipher

The action of a Caesar cipher is to replace each plaintext letter with one a fixed number of places down the alphabet. This example is with a shift of three, so that a B in the plaintext becomes E in the ciphertext

EXAMPLE: The Caesar cipher is the widely known cipher in which letters are shifted. For example, if the key is 3, the letter A becomes D, B becomes E, and so forth, ending with Z becoming C. So the word "HELLO" is enciphered as "KHOOR." Informally, this cipher is a cryptosystem with: M = { all sequences of Roman letters } K = { i | i an integer such that 0 ≤ I ≤ 25 } E = { Ek | k≤ K and for all m M, Ek(m) = (m + k) mod 26 }

Representing each letter by its position in the alphabet (with A in position 0), "HELLO" is 7 4 11 11 14; if k = 3, the ciphertext is 10 7 14 14 17, or "KHOOR." D = { Dk | k K and for all c C, Dk(c) = (26 + c – k) mod 26 } Each Dk simply inverts the corresponding Ek. C = M because E is clearly a set of onto functions.

Vigènere cipher

A longer key might obscure the statistics. The Vigenère cipher chooses a sequence of keys, represented by a string. The key letters are applied to successive plaintext characters, and when the end of the key is reached, the key starts over. The length of the key is called the period of the cipher. Because this requires several different key letters, this type of cipher is called polyalphabetic.

EXAMPLE: The first line of a limerick is enciphered using the key "BENCH," as follows. Key B ENCHBENC HBENC HBENCH BENCHBENCH Plaintext A LIMERICK PACKS LAUGHS ANATOMICAL Ciphertext B PVOLSMPM WBGXU SBYTJZ BRNVVNMPCS

For many years, the Vigenère cipher was considered unbreakable. Then a Prussian cavalry officer named Kasiski noticed that repetitions occur when characters of the key appear over the same characters in the ciphertext. The number of characters between the repetitions is a multiple of the period.

One Time Pad The one-time pad is a variant of the Vigenère cipher. The technique is the same. The key string is chosen at random, and is at least as long as the message, so it does not repeat.

DES

The Data Encryption Standard (DES) was designed to encipher sensitive but nonclassified data. It is bit-oriented, unlike the other ciphers we have seen. It uses both transposition and substitution and for that reason is sometimes referred to as a product cipher. Its input, output, and key are each 64 bits long. The sets of 64 bits are referred to as blocks

Public Key Cryptography

Diffie-Hellman

RSA

Cryptographic Checksums

HMAC

Summary

Research Issues

Classical Cryptography:

Mathematically, the key to a transposition cipher is a permutation function. Because the permutation does not alter the frequency of plaintext characters, a transposition cipher can be detected by comparing character frequencies with a model of the language. If, for example, character frequencies for 1-grams match those of a model of English, but 2-gram frequencies do not match the model, then the text is probably a transposition cipher. Attacking a transposition cipher requires rearrangement of the letters of the ciphertext. This process, called anagramming, uses tables of n-gram frequencies to identify common n-grams. The cryptanalyst arranges the letters in such a way that the characters in the ciphertext form some n-grams with highest frequency. This process is repeated, using different n-grams, until the transposition pattern is found.

EXAMPLE: Consider the ciphertext "HLOOLELWRD." According to a Konheim's digram table [590], the digram "HE" occurs with frequency 0.0305 [1] in English. Of the other possible digrams beginning with "H," the frequency of "HO" is the next highest, at 0.0043, and the digrams "HL," "HW," "HR," and "HD" have frequencies of less than 0.0010. Furthermore, the frequency of "WH" is 0.0026, and the digrams "EH," "LH," "OH," "RH," and "DH" occur with frequencies of 0.0002 or less. This suggests that "E" follows "H." We arrange the letters so that each letter in the first block of five letters (from "H" up to but not including the "E") is adjacent to the corresponding letter in the second block of five letters, as follows. HE LL OW OR LD Reading the letters across and down produces "HELLOWORLD." Note that the shape of the arrangement is different from that in the previous example. However, the two arrangements are equivalent, leading to the correct solution. [1] This means that in Konheim's sample, 3.05% of the digrams were "HE."

Substitution ciphers

A substitution cipher changes characters in the plaintext to produce the ciphertext. [[1]]

EXAMPLE: The Caesar cipher discussed earlier had a key of 3, altering each letter in the plaintext by mapping it into the letter three characters later in the alphabet (and circling back to the beginning of the alphabet if needed). This is a substitution cipher.

Combinations are called product ciphers

[2] http://en.wikipedia.org/wiki/Caesar_cipher http://en.wikipedia.org/wiki/Encrypt http://en.wikipedia.org/wiki/Plaintext http://en.wikipedia.org/wiki/Cipher http://en.wikipedia.org/wiki/Julius_Caesar