Cryptography in Information Security

From Computing and Software Wiki

Revision as of 05:51, 6 March 2009 (view source) Katmehm (Talk) ← Older edit		Revision as of 22:47, 22 March 2009 (view source) Katmehm (Talk) Newer edit →
Line 6:		Line 6:
	5. Research Issues		5. Research Issues
	----		----
		+
		+	1] Terminology:
		+	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 e: M K C
		+	– D set of decryption functions d: C K M
		+
		+	Contents
		+	• Classical Cryptography
		+	– Cæsar cipher
		+	– Vigènere cipher
		+	– DES
		+	• Public Key Cryptography
		+	– Diffie-Hellman
		+	– RSA
		+	• Cryptographic Checksums
		+	– HMAC
		+
		+	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.
		+
		+	Three types of attacks:
		+	– ciphertext only: adversary has only ciphertext; goal is to
		+	find plaintext, possibly key
		+	– known plaintext: adversary has ciphertext,
		+	corresponding plaintext; goal is to find key
		+	– chosen plaintext: adversary may supply plaintexts and
		+	obtain corresponding ciphertext; goal is to find key
		+
		+	Basis of Attacks:
		+	A good cryptosystem protects against all three types of attacks.
		+	Attacks use both mathematics and statistics. The statistical methods make assumptions about the statistics
		+	of the plaintext language and examine the ciphertext to correlate its properties with those assumptions.
		+	Those assumptions are collectively called a model of the language. Figure 9-1 presents a character-based,
		+	or 1-gram, model of English text; others are 2-gram models (reflecting frequencies of pairs of letters),
		+	Markov models, and word models. In what follows, we use the 1-gram model and assume that the characters are chosen independently of one another.
		+
		+
		+
		+	Table of character frequencies in the English language, from
		+	Denning [269], Figure 2.3, p. 65
		+
		+	Classical Cryptography:
		+	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.
		+
		+	Ceasar 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.
		+
		+	Transposition ciphers
		+	A transposition cipher rearranges the characters in the plaintext to form the ciphertext. The letters are not changed.
		+
		+	EXAMPLE: The rail fence cipher is composed by writing the plaintext in two rows, proceeding
		+	down, then across, and reading the ciphertext across, then down. For example, the plaintext
		+	"HELLO, WORLD" would be written as:
		+	HLOOL
		+	ELWRD
		+	resulting in the ciphertext "HLOOLELWRD."
		+
		+	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.  http://en.wikipedia.org/wiki/Substitution_cipher
		+
		+	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
		+
		+
		+	http://en.wikipedia.org/wiki/Cryptography
		+	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

---

Revision as of 22:47, 22 March 2009

 What Is Cryptography?

1. Classical Cryptosystems 2. Public Key Cryptography 3. Cryptographic Checksums 4. Summary 5. Research Issues

---

1] Terminology: 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 e: M K C – D set of decryption functions d: C K M

Contents • Classical Cryptography – Cæsar cipher – Vigènere cipher – DES • Public Key Cryptography – Diffie-Hellman – RSA • Cryptographic Checksums – HMAC

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.

Three types of attacks: – ciphertext only: adversary has only ciphertext; goal is to find plaintext, possibly key – known plaintext: adversary has ciphertext, corresponding plaintext; goal is to find key – chosen plaintext: adversary may supply plaintexts and obtain corresponding ciphertext; goal is to find key

Basis of Attacks: A good cryptosystem protects against all three types of attacks. Attacks use both mathematics and statistics. The statistical methods make assumptions about the statistics of the plaintext language and examine the ciphertext to correlate its properties with those assumptions. Those assumptions are collectively called a model of the language. Figure 9-1 presents a character-based, or 1-gram, model of English text; others are 2-gram models (reflecting frequencies of pairs of letters), Markov models, and word models. In what follows, we use the 1-gram model and assume that the characters are chosen independently of one another.

Table of character frequencies in the English language, from Denning [269], Figure 2.3, p. 65

Classical Cryptography: 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.

Ceasar 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.

Transposition ciphers

A transposition cipher rearranges the characters in the plaintext to form the ciphertext. The letters are not changed.

EXAMPLE: The rail fence cipher is composed by writing the plaintext in two rows, proceeding down, then across, and reading the ciphertext across, then down. For example, the plaintext "HELLO, WORLD" would be written as: HLOOL ELWRD resulting in the ciphertext "HLOOLELWRD."

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. http://en.wikipedia.org/wiki/Substitution_cipher

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

http://en.wikipedia.org/wiki/Cryptography 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