WIXLIB

Cryptography andThe Da Vinci CodeProf. Keith MartinInformation Security GroupRoyal HollowayUniversity of London

(OR what Sophie Neveu did NOT seem to learnwhen she studied at Royal Holloway)

"There's an easier way," Sophie said, taking the pen fromTeabing."It works for all reflectional substitution ciphers, includingthe Atbash. A little trick I learned at the Royal Holloway."Sophie wrote the first half of the alphabet from left to rightand then, beneath it, wrote the second half, right to left."Cryptanalysts call it the fold-over. Half as complicated.Twice as clean."Teabing eyed her handiwork and chuckled.: "Right you are. Gladto see those boys at the Holloway are doing their job."3

What iscryptography ?

Have you usedcryptography:on a daily basis?on a weekly basis?occasionally?

A simple scenarioAliceBob6

Risks to information Passive attacks– unauthorised access to information Active attacks– Unauthorised alteration– Unauthorised deletion– Unauthorised transmission– Falsification of origin of information– Unauthorised prevention of access toinformation7

Cryptography: the toolkitCryptography provides a mathematicaltoolkit of techniques that can be calledupon in order to implement the securityservices required for any application.8

Cryptographic primitives9

The need forconfidentiality

Sending a letter to a friend

Sending an email to a friend

Calling a friend on a mobile

The Caesar Cipher

The Caesar STUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZsliding ruler15

Caesar Cipher ExampleABCDEFGHIJ.XYZ

Caesar Cipher ExampleKey shift CACBCDEFGHIJ.XYZ

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZAB

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACEAXE

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACCEAXE

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACCEEAXE

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACECEGAXE

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACEACEGCXE

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACEAXCEGCZE

Caesar Cipher ExampleKey shift CABCDEFGHIJ.XYZCDEFGHIJKL.ZABACEAXECEGCZG

Caesar Cipher ChallengesWhat creature hops about and explodes near a naked flame?MX MW E KEWLSTTIV(key shift E)Which creature says “baa” and fights at sea?ZNOY OY G HGZZRKYNKKV(key shift G)Which animal runs very fast and keeps you warm?AL AK S OAFVUZWWLSZ(key shift S)

Simple Substitution CipherabcdefghijklmDIQ M TBZSY KVOFnopqstuv wxyzERJA U W PXH LCN Gr27

Keyspace of the Substitution CipherThe key space of the Simple Substitution Cipher isapproximately 4 x 1026, that is:400 000 000 000 000 000 000 000 000Just how big is that?There are an estimated 10 sextillion (that’s 1022) stars in ouruniverse. That means that the Simple Substitution Cipher hasabout 40 000 times the number of keys than there are stars inour universe.The key space of DES is somewhere between 1016 and 1017.That’s a much smaller number – it’s only about 100 000 timesthe number of stars in our galaxy!28

Substitution Cipher ExamplesDecrypt the following ciphertexts1B TO T OTA2XAV3VBDDQD4VBDDQD5ABXAZ O OAZ TCYE TE F CEOE UCZXT(given that the plaintext is thename of a country)29

World Cup 2010 Special ExamplesTBZHPSNRPVGYZICEBCGOQC UQFKFOXYEVENLEM30

Substitution Cipher Histogram35Number of Occurrences302520151050ACEGIKMOQSUWYA histogram showing the relative frequencies of the letters in acryptogram that was obtained by using a simple substitution cipher.31

Advanced Encryption Standardcurrent stateBytesubstitutionAESS-boxShift rowskeyKeyscheduleMixcolumnsround key new state32

A cryptosystemSenderReceiverencryption keyplaintextEncryptionalgorithmdecryption or33

The need fordata integrity

Two things that can go wrong.Accidental errorsDeliberate errors

How the Internet works (part 1)

How the Internet works (part 2)

Morse Code Example001001100000111

The ISBN number

Deliberate errors

CBC-MAC(Padded) message divided into blocksM11KKEC1M2M3Mn 2EKEK3EMACC24M1 M2 M3 ., Mn MAC42

The need forauthentication

A problem with emailCan you be surethat an emailfrom a friend isreally from yourfriend?

A need for authentication!

Types of entity authenticationThe most common methods use (a combination of): something that you have something that you are something that you know46

PasswordsChoose a BARCV8**G9Pa2

One-time password mechanismsDeviceRandomNumberGeneratorSmart se ?57Decision48

Real world applications needConfidentialityData IntegrityAuthentication.to varying degrees

So.what didSophie Neveu learnat Royal Holloway ?

Atbash CipherabcdefghijkZYX W VUTSR Q PO Nnopqrstuv wyM LKJIH GFE D CxlmzB A51

"There's an easier way," Sophie said, taking the pen fromTeabing."It works for all reflectional substitution ciphers, includingthe Atbash. A little trick I learned at the Royal Holloway."Sophie wrote the first half of the alphabet from left to rightand then, beneath it, wrote the second half, right to left."Cryptanalysts call it the fold-over. Half as complicated.Twice as clean."Teabing eyed her handiwork and chuckled.: "Right you are. Gladto see those boys at the Holloway are doing their job."52

Highly recommendedhttp://www.cryptool.org/53

Some bed-time reading F. Piper and S. Murphy, Cryptography: A Very ShortIntroduction, Oxford University Press (2002). H.X. Mel and D. Baker, Cryptography Decrypted,Addison-Wesley (2001). D.R. Stinson, Cryptography: Theory and Practice,3rd Edition, Chapman & Hall/CRC Press (2006). S. Levy, Crypto, Penguin Books (2000). S. Singh, The Code Book, Fourth Estate (1999). N. Ferguson and B. Schneier PracticalCryptography, Wiley (2003).54

Thank You

The Da Vinci Code Prof. Keith Martin Information Security Group . Morse Code Example 0010 01 1000 00 111 . The ISBN number . Deliberate errors . 42 CBC-MAC M 1 . The Code Book, Fourth Estate (1999). N. Fergu