Sunday, March 7, 2010

Introduction to Cryptography

  • cryptography is the study of
secret (crypto-) writing (-graphy)

  • concerned with developing algorithms which may be used to:
    • conceal the context of some message from all except the sender and recipient (privacy or secrecy), and/or
    • verify the correctness of a message to the recipient (authentication)
  • form the basis of many technological solutions to computer and communications security problems
  • for a good overview paper see:
W Diffie, M E Hellman, "Privacy and Authentication: An Introduction to Cryptography", in Proc. IEEE, Vol 67(3) Mar 1979, pp 397-427

Basic Concepts

cryptography
the art or science encompassing the principles and methods of transforming an intelligible message into one that is unintelligible, and then retransforming that message back to its original form
plaintext
the original intelligible message
ciphertext
the transformed message
cipher
an algorithm for transforming an intelligible message into one that is unintelligible by transposition and/or substitution methods
key
some critical information used by the cipher, known only to the sender & receiver
encipher (encode)
the process of converting plaintext to ciphertext using a cipher and a key
decipher (decode)
the process of converting ciphertext back into plaintext using a cipher and a key
cryptanalysis
the study of principles and methods of transforming an unintelligible message back into an intelligible message without knowledge of the key. Also called codebreaking
cryptology
both cryptography and cryptanalysis
code
an algorithm for transforming an intelligible message into an unintelligible one using a code-book

Concepts

Encryption C = E_(K)(P)

Decryption P = E_(K)^(-1)(C)

E_(K) is chosen from a family of transformations known as a cryptographic system.

The parameter that selects the individual transformation is called the key K, selected from a keyspace K

More formally a cryptographic system is a single parameter family of invertible transformations

E_(K) ; K in K : P -> C

with the inverse algorithm E_(K)^(-1) ; K in K : C -> P

such that the inverse is unique

Usually assume the cryptographic system is public, and only the key is secret information

Private-Key Encryption Algorithms

  • a private-key (or secret-key, or single-key) encryption algorithm is one where the sender and the recipient share a common, or closely related, key
  • all traditional encryption algorithms are private-key
  • overview of a private-key encryption system and attacker

Cryptanalytic Attacks

  • have several different types of attacks

ciphertext only

  • only have access to some enciphered messages
  • use statistical attacks only

known plaintext

  • know (or strongly suspect) some plaintext-ciphertext pairs
  • use this knowledge in attacking cipher

chosen plaintext

  • can select plaintext and obtain corresponding ciphertext
  • use knowledge of algorithm structure in attack

chosen plaintext-ciphertext

  • can select plaintext and obtain corresponding ciphertext, or select ciphertext and obtain plaintext
  • allows further knowledge of algorithm structure to be used

Unconditional and Computational Security

  • two fundamentally different ways ciphers may be secure
    unconditional security
    - no matter how much computer power is available, the cipher cannot be broken
    computational security
    - given limited computing resources (eg time needed for calculations is greater than age of universe), the cipher cannot be broken

A Brief History of Cryptography

Ancient Ciphers

  • have a history of at least 4000 years
  • ancient Egyptians enciphered some of their hieroglyphic writing on monuments
  • ancient Hebrews enciphered certain words in the scriptures
  • 2000 years ago Julius Ceasar used a simple substitution cipher, now known as the Caesar cipher
  • Roger Bacon described several methods in 1200s
  • Geoffrey Chaucer included several ciphers in his works
  • Leon Alberti devised a cipher wheel, and described the principles of frequency analysis in the 1460s
  • Blaise de Vigenère published a book on cryptology in 1585, & described the polyalphabetic substitution cipher
  • increasing use, esp in diplomacy & war over centuries

Machine Ciphers

  • Jefferson cylinder, developed in 1790s, comprised 36 disks, each with a random alphabet, order of disks was key, message was set, then another row became cipher
  • Wheatstone disc, originally invented by Wadsworth in 1817, but developed by Wheatstone in 1860's, comprised two concentric wheels used to generate a polyalphabetic cipher
  • Enigma Rotor machine, one of a very important class of cipher machines, heavily used during 2nd world war, comprised a series of rotor wheels with internal cross-connections, providing a substitution using a continuosly changing alphabet

Classical Cryptographic Techniques

  • have two basic components of classical ciphers: substitution and transposition
  • in substitution ciphers letters are replaced by other letters
  • in transposition ciphers the letters are arranged in a different order
  • these ciphers may be:
  • monoalphabetic - only one substitution/ transposition is used, or
  • polyalphabetic - where several substitutions/ transpositions are used
  • several such ciphers may be concatentated together to form a product cipher

Caesar Cipher - a monoalphabetic cipher

  • replace each letter of message by a letter a fixed distance away eg use the 3rd letter on
  • reputedly used by Julius Caesar
eg.
	L FDPH L VDZ L FRQTXHUHG

I CAME I SAW I CONQUERED
ie mapping is
	ABCDEFGHIJKLMNOPQRSTUVWXYZ

DEFGHIJKLMNOPQRSTUVWXYZABC
  • can describe this cipher as:
Encryption E_(k) : i -> i + k mod 26

Decryption D_(k) : i -> i - k mod 26

Cryptanalysis of the Caesar Cipher

  • only have 26 possible ciphers
  • could simply try each in turn - exhaustive key search
				GDUCUGQFRMPCNJYACJCRRCPQ

HEVDVHRGSNQDOKZBDKDSSDQR
Plain - IFWEWISHTOREPLACELETTERS
JGXFXJTIUPSFQMBDFMFUUFST
KHYGYKUJVQTGRNCEGNGVVGTU
Cipher - LIZHZLVKWRUHSODFHOHWWHUV
MJAIAMWLXSVITPEGIPIXXIVW
  • also can use letter frequency analysis
Single Letter              Double Letter             Triple Letter             

E TH THE
T HE AND
R IN TIO
N ER ATI
I RE FOR
O ON THA
A AN TER
S EN RES

Character Frequencies

  • in most languages letters are not equally common
  • in English e is by far the most common letter
  • have tables of single double & triple letter frequencies
  • these are different for different languages (see Appendix A in Seberry & Pieprzyk)

  • use these tables to compare with letter frequencies in ciphertext, since a monoalphabetic substitution does not change relative letter frequencies
[1] do need a moderate amount of ciphertext (100+ letters)

Modular Arithmetic monoalphabetic cipher

  • more generally could use a more complex equation to calculate the ciphertext letter for each plaintext letter
E_(a b) : i ->a.i + b mod 26

nb a must not divide 26 (ie gcd(a,26) = 1)

otherwise cipher is not reversible eg a=2

and a=0, b=1, c=2 ... , y=24, z=25

  • eg E_(5 7) : i ->5.i + 7 mod 26
Cryptanalysis:
  • use letter frequency counts to guess a couple of possible letter mappings
    • nb frequency pattern not produced just by a shift
  • use these mappings to solve 2 simultaneous equations to derive above parameters

Example - Sinkov pp 34-35

Mixed Alphabets

  • most generally we could use an arbitrary mixed (jumbled) alphabet
  • each plaintext letter is given a different random ciphertext letter, hence key is 26 letters long
Plain:   ABCDEFGHIJKLMNOPQRSTUVWXYZ

Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN
Plaintext: IFWEWISHTOREPLACELETTERS
Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA
  • now have a total of 26! ^(~) 4 ^(x) 10^(26) keys
  • with so many keys, might think this is secure
!!!WRONG!!!
  • problem is not the number of keys, rather:
1) there is lots of statistical information in message

2) can solve the problem piece by piece

(ie can get key nearly right, and nearly get message)

(near enough MUST NOT be good enough!)

Cryptanalysis

  • use frequency counts to guess letter by letter
  • also have frequencies for digraphs & trigraphs

General Monoalphabetic

  • special form of mixed alphabet
  • use key as follows:
    • write key (with repeated letters deleted)
    • then write all remaining letters in columns underneath
    • then read off by columns to get ciphertext equivalents

Example Seberry p66

	STARW

BCDEF
GHIJK
LMNOP
QUVXY
Z

Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: SBGLQZTCHMUADINVREJOXWFKPY

Plaintext: I KNOW ONLY THAT I KNOW NOTHING
Ciphertext: H UINF NIAP OCSO H UINF INOCHIT

Polyalphabetic Substitution

  • in general use more than one substitution alphabet
  • makes cryptanalysis harder since have more alphabets to guess
  • and because flattens frequency distribution
  • (since same plaintext letter gets replaced by several ciphertext letter, depending on which alphabet is used)

Vigenère Cipher

  • basically multiple caesar ciphers
  • key is multiple letters long K = k_(1) k_(2) ... k_(d)
  • ith letter specifies ith alphabet to use
  • use each alphabet in turn, repeating from start after d letters in message
Plaintext	THISPROCESSCANALSOBEEXPRESSED

Keyword CIPHERCIPHERCIPHERCIPHERCIPHE
Plaintext VPXZTIQKTZWTCVPSWFDMTETIGAHLH
  • can use a Saint-Cyr Slide for easier encryption

  • based on a Vigenère Tableau

   ABCDEFGHIJKLMNOPQRSTUVWXYZ


A ABCDEFGHIJKLMNOPQRSTUVWXYZ
B BCDEFGHIJKLMNOPQRSTUVWXYZA
C CDEFGHIJKLMNOPQRSTUVWXYZAB
D DEFGHIJKLMNOPQRSTUVWXYZABC
E EFGHIJKLMNOPQRSTUVWXYZABCD
F FGHIJKLMNOPQRSTUVWXYZABCDE
G GHIJKLMNOPQRSTUVWXYZABCDEF
H HIJKLMNOPQRSTUVWXYZABCDEFG
I IJKLMNOPQRSTUVWXYZABCDEFGH
J JKLMNOPQRSTUVWXYZABCDEFGHI
K KLMNOPQRSTUVWXYZABCDEFGHIJ
L LMNOPQRSTUVWXYZABCDEFGHIJK
M MNOPQRSTUVWXYZABCDEFGHIJKL
N NOPQRSTUVWXYZABCDEFGHIJKLM
O OPQRSTUVWXYZABCDEFGHIJKLMN
P PQRSTUVWXYZABCDEFGHIJKLMNO
Q QRSTUVWXYZABCDEFGHIJKLMNOP
R RSTUVWXYZABCDEFGHIJKLMNOPQ
S STUVWXYZABCDEFGHIJKLMNOPQR
T TUVWXYZABCDEFGHIJKLMNOPQRS
U UVWXYZABCDEFGHIJKLMNOPQRST
V VWXYZABCDEFGHIJKLMNOPQRSTU
W WXYZABCDEFGHIJKLMNOPQRSTUV
X XYZABCDEFGHIJKLMNOPQRSTUVW
Y YZABCDEFGHIJKLMNOPQRSTUVWX
Z ZABCDEFGHIJKLMNOPQRSTUVWXY
  • can describe this cipher as:
given K = k_(1) k_(2) ... k_(d)

then f_(i) (a) = a + k_(i) (mod n)

Beauford Cipher

  • similar to Vigenère but with alphabet written backwards
  • can be descibed by
given K = k_(1) k_(2) ... k_(d)

then f_(i) (a) = (k_(i) - a) (mod n)

and its inverse is

f_(i) ^(-1)(a) = (k_(i) - c) (mod n)

Example - Seberry p71

Key = d

Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DCBAZYXWVUTSRQPONMLKJIHGFE

Variant-Beauford Cipher

  • just the inverse of the Vigenère (decrypts it)
given K = k_(1) k_(2) ... k_(d)

then f_(i) (a) = a - k_(i) (mod n)

Language Redundancy & Unicity Distance

  • human languages are highly redundant
    • eg th lrd s m shphrd shll nt wnt
  • Claude Shannon derived several important results about the information content of languages in 1949
  • entropy of a message H(X) is related to the number of bits of information needed to encode a message X [2]
    • cannot exceed log_(2)n bits for n possible messages
  • the rate of langauge for messages of length k denotes the average number of bits in each character
D = F(H(M),k)
  • rate of English is about 3.2 bits/letter
  • distinguish information context and redundancy
  • Shannon defined the unicity distance of a cipher to give a quantatative measure of:
    • the security of a cipher (must not be too small)
    • the amount of ciphertext N needed to break it
N = F(H(K),D)

where H(K) is entropy (amount of info) of the key,

and is D the rate of the language used (eg 3.2)

  • for polynomial based monoalphabetic substitution ciphers have:
N = F(H(K),D) = F(log_(2)26,3.2) = 1.5

hence only need 2 letters to break

  • for general monoalphabetic substitution ciphers have
N = F(H(K),D) = F(log_(2)n!,D) = F(log_(2)26!,3.2) = F(26 log_(2)F(26,e),3.2) = 27.6

hence only need 27 or 28 letters to break

  • for polyalphabetic substitution ciphers, if have s possible keys for each simple subs, and d keys used, then
N = F(H(K),D) = F(log_(2)s^(d),D) = F(d log_(2)26,3.2) = 1.5d

hence need 1.5 times the number of separate substitutions used letters to break the cipher

  • but first need to determine just how many alphabets were used
    • Kasiski method
    • index of coincidence


Kasiski Method

  • use repetitions in ciphertext to give clues as to period, looking for same plaintext an exact period apart, leading to same ciphertext

Example - Seberry p71

Plaintext:   TOBEORNOTTOBE

Key: NOWNOWNOWNOWN
Ciphertext: GCXRCNACPGCXR

Since repeats are 9 chars apart, guess period is 3 or 9.

Index of Coincidence

  • Index of Coincidence (IC) was introduced in 1920s by William Friedman
  • measures variation of frequencies of letters in ciphertext
    • period = 1 => simple subs => variation is high, IC high
    • period > 1 => poly subs => variation is reduced, IC low

see Seberry Table 3.2 p72 and Table 3.3 p74

d           IC             

1 0.0660
2 0.0520
3 0.0473
4 0.0450
5 0.0436
6 0.0427
7 0.0420
8 0.0415
9 0.0411
10 0.0408
11 0.0405
12 0.0403
13 0.0402
14 0.0400
15 0.0399
... ...
Inf 0.0380

	Table 3.3 - Period and IC for English

  • first define a measure of roughness (MR) giving variation of frequencies of individual characters relative to a uniform distribution
		MR = Isu(i=o,n-1,(p_(i) - F(1,n))^(2))

where p_(i) is probability an arbitrary character in ciphertext is the ith character a_(i) in the alphabet
			 Isu(i=o,n-1,p_(i)) = 1

  • for English letters can derive
		MR = Isu(i=o,n-1,p_(i)^(2)) - 0.038

or
		MR + 0.038 = Isu(i=o,n-1,p_(i)^(2))

is prob two arbitrary letters in ciphertext are the same
  • can compute MR for plaintext using characteristic letter frequencies
eg MR for English is 0.028 (0.066 - 0.038)
  • can also compute MR for a flat distribution as 0
  • since probabilities and period are unknown, cannot compute MR, however can estimate from ciphertext
  • now the number of pairs of letters that can be chosen from ciphertext of length N is
		Bbc[(S(N,2)) = F(1,2) N (N-1)

  • if F_(i) is the freq of the ith letter of English in the ciphertext, then the number of pairs containing just the ith letter is
		F(F_(i)(F_(i)-1),2)		and	Isu(i=o,n-1,F_(i)) = 1

  • now define the Index of Coincidence (IC) as the prob that two letters at random from the ciphertext are indeed the same
	IC = 	Isu(i=o,n-1,F(F_(i)(F_(i)-1),N(N-1)))

and use the IC estimate in
		MR + 0.038 = IC

  • since usually use IC in crypto work, expect that
		0.038 < IC < 0.066

  • for a cipher of period d the expected value of the IC is
		Exp(IC) = F(1,d) F(N-d,N-1)(0.066) + Bbc[(S(d-1,d))F(N,N-1)(0.038)

and we can use these values to estimate d from the ciphertext

Example program to compute IC - Seberry Fig3.4 p74

Solving Polyalphabetic Ciphers

  • use Kasiski method & IC to estimate period d
  • then separate ciphertext into d sections, and solve each as a monoalphabetic cipher

Example - Seberry pp73-77

Krypto program

  • this is a program to help solve simple substitution and transposition ciphers
  • invoke using
krypto [file]
  • has the following commands available
       Command                                    Meaning                           

? this message.
! execute a shell command.
f [ [n]] print [the n most] frequent strings of length seqlen.
g [

] print the frequency distribution graph of letters.
i [

] calculate the index of coincidence of the text.
l [ ] list only the modified string. [b=blklength, B=blks/line]
p print current code.
q exit.
s substitute ch2 for ch1.
S [-] -[gvbB] {keys} Perform the substitution specified by the key.
T [-] |key Transpose text by perm or keyword. e.g. T 4,5,2,3,1
t [/regexp] look for transpositions of period n; [print only /regexp].
B [-] |key apply the specifed rectangular encryption to the text.
b [/regexp] look for block decryptions of size n; [print only
/regexp].
u undo previous modification.
z reset the code to its initial state.
r enter code from file.
w write code to file.
e edit code.

  • see man entry for more details

Transposition Ciphers

  • transposition or permutation ciphers hide the message contents by rearranging the order of the letters

Scytale cipher

  • an early Greek transposition cipher
  • a strip of paper was wound round a staff
  • message written along staff in rows, then paper removed
  • leaving a strip of seemingly random letters
  • not very secure as key was width of paper & staff

For information on lots of simple substitution and permutation ciphers see:

  • A. Sinkov "Elementary Cryptanalysis", New Mathematical Library, Random House, 1968* other simple transposition ciphers include:

Reverse cipher

  • write the message backwards
Plain:	I CAME I SAW I CONQUERED

Cipher: DEREU QNOCI WASIE MACI

Rail Fence cipher

  • write message with letters on alternate rows
  • read off cipher row by row
Plain:	I A E S W C N U R D

C M I A I O Q E E
Cipher: IAESW CNURD CMIAI OQEE

Geometric Figure

  • write message following one pattern and read out with another

Row Transposition ciphers

  • in general write message in a number of columns and then use some rule to read off from these columns
  • key could be a series of number being the order to: read off the cipher; or write in the plaintext
Plain:	THESIMPLESTPOSSIBLETRANSPOSITIONSXX

Key (R): 2 5 4 1 3
Key (W): 4 1 5 3 2

T H E S I S T I E H
M P L E S E M S L P
T P O S S S T S O P
I B L E T E I T L B
R A N S P S R P N A
O S I T I T O I I S
O N S X X X O X S N
Cipher: STIEH EMSLP STSOP EITLB SRPNA TOIIS XOXSN

Example - Davies p26 Fig 2.14

  • or can use a word, with letter order giving sequence: to write in the plaintext; or read off the cipher
Plain:	ACONVENIENTWAYTOEXPRESSTHEPERMUTATION

Key (W): C O M P U T E R
Key (W): 1 4 3 5 8 7 2 6

A N O V I N C E
E W T A O T N Y
H E P R T U E M
A O I N Z Z T Z

Cipher: ANOVI NCEEW TAOTN YHEPR TUEMA OINZZ TZ

Example - Davies p26 Fig 2.15

  • key idea for row transposition ciphers is that message is in groups that have the letters reordered in each
  • Exercise using key sorcery (to read out) encipher:
Key(R):	sorcery => 6 3 4 1 2 5 7

laser beams can be modulated to carry more intelligence than radio waves
gives
erasb lecam snabd umole atoed ctamo ryrre elntl iicee ntgha dnria oesav w

  • decryption consists of:
    • writing the message out in columns
    • reading off the message by reordering columns
    • (use T command in krypto, uses read out keys)
  • hint - its not a good idea to leave message in groups matching the size of your key!!!

Cryptanalysis of Row Transposition ciphers

  • a frequency count will show a normal language profile
  • hence know have letters rearranged
  • basic idea is to guess period, then look at all possible permutations in period, and search for common patterns (eg t command in krypto)
  • use lists of common pairs & triples & other features

Example - Seberry p67-8 [3]

  • to determine the complexity of this cipher, we can calculate its unicity distance
    • given blocks of period d, there are d! keys, hence
N = F(H(K),D) = F(log_(2)d!,D) = F(d log_(2)(d/e),3.2)

Seberry Table 3.1 p69


Block (Columnar) Transposition ciphers

  • another group of ciphers are block (columnar) transposition ciphers where the message is written in rows, but read off by columns in order given by key (use B command in krypto)
  • for ease of recovery may insist matrix is filled
Key(R):       s o r c e r y        s o r c e r y

Key(R): 6 3 4 1 2 5 7 6 3 4 1 2 5 7

l a s e r b e l a s e r b e
a m s c a n b a m s c a n b
e m o d u l a e m o d u l a
t e d t o c a t e d t o c a
r r y m o r e r r y m o r e
i n t e l l i i n t e l l i
g e n c e t h g e n c e t h
a n r a d i o a n r a d i o
w a v e s w a v e s q r

  • giving ciphertext (by reading off cols 4, 5, 2, 3, 6, 1, 7)
ecdtm ecaer auool edsam merne nasso dytnr vbnlc rltiq laetr igawe baaei hor
  • decryption consists of:
    • calculating how many rows there are (by dividing message length by key length)
    • then write out message down columns in order given by key

Example - Sinkov p148

  • exercise - Sinkov p148 #74

Sinkov p148

Cryptanalysis of Block Transposition ciphers

  • again know must be a transposition, and guess is perhaps a block transposition
  • guess size of matrix by looking at factors of message length, and write out by columns
  • then look for ways of reordering pairs of columns to give common pairs or triples (very much trial & error)
  • (nb use b command in krypto to try possibilities)

Example - Sinkov p 149-151

Nihilist ciphers

  • a more complex transposition cipher using both row and column transpositions is the nihilist cipher
  • write message in rows in order controlled by the key (as for a row cipher)
  • then read off by rows, but in order controlled by the key, this time written down the side
  • uses a period of size the square of the key length
Plaintext:    NOWISTHETIMEFORALLGOODMEN


Key (W): L E M O N
2 1 3 5 4
L 2 O N W S I
E 1 H T E I T
M 3 E M F R O
0 5 L A L O G
N 4 D O M N E

Nihilist Cipher: HTEIT ONWSI EMFRO DOMNE LALOG

Diagonal Cipher: ONHET WSEML DAFII TRLOM OOGNE

Example - Davis Fig2.16 p27
  • attacking this cipher depends on column and row rearrangement, with much trial and error
  • for more complexity can vary readout algorithm
    • diagonal cipher reads out on fwd diag (/) in alternate directions (up diag, down diag etc), ie a zig-zag read out

Product ciphers

  • can see that in general ciphers based on just substitutions or just transpositions are not secure
  • what about using several ciphers in order
    • two substitutions are really only one more complex substitution
    • two transpositions are really only one more complex transposition
    • but a substitution followed by a transposition makes a new much harder cipher
  • product ciphers consist substitution-transposition combinations chained together
  • in general are far too hard to do by hand, however one famous product cipher, the 'ADFGVX' cipher was used in WW1 (see Kahn pp339-350)
  • instead there use had to wait for the invention of the cipher machine, particularly the rotor machines (eg Enigma, Hagalin) mentioned briefly earlier

ADFGVX Product Cipher

  • named since only letters ADFGVX are used
  • chosen since have very distinct morse codes
  • uses a fixed substitution table to map each plaintext letter to a letter pair (row-col index)
  • then uses a keyed block transposition
	

Substitution Table

\\    A     D     F     G     V     X    

A K Z W R 1 F
D 9 B 6 C L 5
F Q 7 J P G X
G E V Y 3 A N
V 8 O D H 0 2
X U 4 I S T M

	Plaintext:	PRODUCTCIPHERS


Intermediate Text:
FG AG VD VF XA DG XV
DG XF FG VG GA AG XG

Keyed Block Columnlar Transposition Matrix

D     E     U     T     S     C     H        Key                    

2 3 7 6 5 1 4 Sorted Order
F G A G V D V
F X A D G X V
D G X F F G V
G G A A G X G

	Ciphertext:	DXGX FFDG GXGG VVVG VGFG CDFA AAXA

2 comments:

  1. good post.
    Now, vigener encryption can be help by a program.
    Look at mobile5ecurity.co.cc for the example.

    ReplyDelete
  2. Superb detail about cryptography is shared above. I really appreciate and would like to thank you hundred times for this complete detail. I think no other blog has shared all about this process like the way you did.
    electronic signatures

    ReplyDelete