The Mathematics Of Cryptography - UMD

The Mathematics ofCryptographyAngela RobinsonNational Institute of Standards and Technology

Cryptography sightings

Cryptography sightingsSecure websites are protected using: digital signatures – authenticity, integrity certificates – verify identity encryption – privacy

EncryptionYouYour bestie

EncryptionYouEavesdropperYour bestie

EncryptionYouEavesdropperQuestion: How can you communicate so that:– Your bestie will understand your messages– Eavesdroppers cannot understand your messagesYour bestie

Julius Caesar’s choiceSECRETJulius Caesar ruled a largeempireCommunicated with hismilitary leaders by messenger

Julius Caesar’s choiceSECRETTFDSFUEncrypted his messages byshifting each letter 3 times tothe right

Julius Caesar’s choiceSECRETTFDSFUUGETGVEncrypted his messages byshifting each letter 3 times tothe right

Julius Caesar’s choiceSECRETTFDSFUUGETGVVHFUHWSend “V H F U H W” to militaryleadersIf anyone attacks themessenger, they won’t knowwhat the secret message is

Shift Cipher Arrangeletters in acircularfashion Assignnumbers0-25Caesar used shift 3Let shift be generalizedto 𝑘

Shift Cipher Arrangeletters in acircularfashionCaesar used shift 3Let shift be generalized to 𝑘𝑘 can be any number from 1 to25.What happens if wechoose shift 𝑘 26? Assignnumbers0-25

Shift CipherPlaintextABC YZPlaintext012 242524 𝑘 𝑚𝑜𝑑 2625 𝑘 𝑚𝑜𝑑 26Encrypt0 𝑘 𝑚𝑜𝑑 26 1 𝑘 𝑚𝑜𝑑 26 Encryption:– Mathematically equivalent toaddition by k modulo 26 Decryption:– Subtraction by k modulo 262 𝑘 𝑚𝑜𝑑 26

Shift Cipher – Examplek 12PlaintextWARNINGPlaintext22017138136 Encryption:– Mathematically equivalent toaddition by 12 modulo 26 Decryption:– Subtraction by 12 modulo 26

Shift Cipher – Examplek 12PlaintextWARNINGPlaintext22017138136 1234122925202518 Encryption:– Mathematically equivalent toaddition by 12 modulo 26 Decryption:– Subtraction by 12 modulo 26

Shift Cipher – Examplek 12PlaintextWARNINGPlaintext22017138136 1234122925202518812325202518mod 26 Encryption:– Mathematically equivalent toaddition by 12 modulo 26 Decryption:– Subtraction by 12 modulo 26

Shift Cipher – Examplek 12PlaintextWARNINGPlaintext22017138136 1234122925202518mod 26812325202518CiphertextIMDZUZSWARNINGIMDZUZS

Cryptanalysis of Shift CipherSome letters are morecommonly used in the Englishalphabet than others:E, A, T, O

Cryptanalysis of Shift CipherSuppose you receive a Shift Cipherciphertext:wkh sdvvzrug lv vhyhqgrqw whoo dqbrqh

Cryptanalysis of Shift Cipherwkh sdvvzrug lv vhyhqgrqw whoo dqbrqhConstruct a letter frequency chart:h 5v 4w 3q 3r 3g 3d 2b 1k 1l 1s 1y 1

Cryptanalysis of Shift Cipherwkh sdvvzrug lv vhyhqgrqw whoo dqbrqhConstruct a letter frequency chart:h 5v 4q 3r 3g 3d 2b 1k 1l 1s 1y 1

Cryptanalysis of Shift Cipherwkh sdvvzrug lv vhyhqgrqw whoo dqbrqhConstruct a letter frequency chart:h 5v 4q 3r 3g 3d 2b 1k 1l 1s 1y 1

Cryptanalysis of Shift Cipherwkh sdvvzrug lvTHEvhyhq grqw whoodqbrqh

Cryptanalysis of Shift Cipherwkh sdvvzrug lvTHE PASSWORD ISvhyhq grqw whoodqbrqh

Cryptanalysis of Shift CipherOnly 26 distinctshifts possiblewkh sdvvzrug lvTHE PASSWORD ISvhyhq grqw whooToo easyto “guess”the key!dqbrqh

Affine Cipher - encryption Instead of plain additionmodulo 26:– Multiplication first– Then addition modulo 26PlaintextMESSAGE1241818064

Affine Cipher - encryption Instead of plain additionmodulo 26:– Multiplication first– Then addition modulo 26 Try (3,10)– Multiply by 3– Add 10 modulo 26PlaintextMESSAGE1241818064

Affine Cipher - encryption Instead of plain additionmodulo 26:– Multiplication first– Then addition modulo 26 Try (3,10)– Multiply by 3– Add 10 modulo 26Plaintextx3MESSAGE12418180643612545401812

Affine Cipher - encryption Instead of plain additionmodulo 26:– Multiplication first– Then addition modulo 26 Try (3,10)– Multiply by 3– Add 10 modulo 26PlaintextMESSAGE1241818064x33612545401812 1046226464102822mod 262022121210222

Affine Cipher - encryption Instead of plain additionmodulo 26:– Multiplication first– Then addition modulo 26 Try (3,10)– Multiply by 3– Add 10 modulo 26PlaintextMESSAGE1241818064x33612545401812 1046226464102822mod 262022121210222UWMMKCW

Affine Cipher - decryption Ciphertext𝐶 𝑎 𝑀 𝑏 𝑚𝑜𝑑 26Need a way to “reverse” thesemathematical steps:1. Multiplication first2. Then addition modulo 26

Affine Cipher - decryption Ciphertext𝐶 𝑎 𝑀 𝑏 𝑚𝑜𝑑 26Need a way to “reverse” thesemathematical steps:1. Multiplication first2. Then addition modulo 26Want to isolate “M”

Affine Cipher - decryption Ciphertext𝐶 𝑎 𝑀 𝑏 𝑚𝑜𝑑 26Need a way to “reverse” thesemathematical steps:1. Multiplication first2. Then addition modulo 26Want to isolate “M”1. Subtract 𝑏2. Divide by 𝑎Multiply by the multiplicative inverse of𝑎 𝑚𝑜𝑑 26

Modular multiplicative inverseDefinition A multiplicative inverse of aninteger 𝑎 mod 26 is an integer𝑥 so that:𝑎𝑥 1𝑚𝑜𝑑 26.

Modular multiplicative inverseDefinitionExample: A multiplicative inverse of aninteger 𝑎 mod 26 is an integer𝑥 so that: Let a 3.3 1 3 𝑚𝑜𝑑 263 2 6 𝑚𝑜𝑑 263 3 9 𝑚𝑜𝑑 26𝑎𝑥 1𝑚𝑜𝑑 26. 3 9 27 1 𝑚𝑜𝑑 26

Modular multiplicative inverseDefinitionExample: A multiplicative inverse of aninteger 𝑎 mod 26 is an integer𝑥 so that: Let a 3.𝑎𝑥 1𝑚𝑜𝑑 26.3 1 3 𝑚𝑜𝑑 263 2 6 𝑚𝑜𝑑 263 3 9 𝑚𝑜𝑑26 3 9 27 1 𝑚𝑜𝑑 26

Modular multiplicative inverseDefinitionExample: A multiplicative inverse of aninteger 𝑎 mod 26 is an integer𝑥 so that: Let a 3.𝑎𝑥 1𝑚𝑜𝑑 26.3 1 3 𝑚𝑜𝑑 263 2 6 𝑚𝑜𝑑 263 3 9 𝑚𝑜𝑑26 3 9 27 1 𝑚𝑜𝑑 26The direct way to compute a modularmultiplicative inverse is using the ExtendedEuclidean Algorithm!

Euclidean AlgorithmEuclid’s Division Theorem:For any integers 𝑛, 𝑑 there are unique integers𝑞, 𝑟 such that𝑛 𝑑 𝑞 𝑟 and 0 𝑟 𝑑.Not every integer has ainverse modulo 26!Affine cipher keys must have amultiplicative inverse forsuccessful decryption!

Euclidean AlgorithmEuclid’s Division Theorem:For any integers 𝑛, 𝑑 there are unique integers𝑞, 𝑟 such that𝑛 𝑑 𝑞 𝑟 and 0 𝑟 𝑑.Suppose we want to find the greatestcommon divisor of integers 𝑎, 𝑏. DivisionTheorem states:There are unique integers 𝑞, 𝑟 such that𝑎 𝑏 𝑞 𝑟.

Euclidean AlgorithmEuclid’s Division Theorem:For any integers 𝑛, 𝑑 there are unique integers𝑞, 𝑟 such that𝑛 𝑑 𝑞 𝑟 and 0 𝑟 𝑑.Suppose we want to find the greatestcommon divisor of integers 𝑎, 𝑏. DivisionTheorem states:If 𝑑 divides 𝑎,and 𝑑 divides 𝑏,then 𝑑 must divide rThere are unique integers 𝑞, 𝑟 such that𝑎 𝑏 𝑞 𝑟.

Euclidean AlgorithmEuclid’s Division Theorem:For any integers 𝑛, 𝑑 there are unique integers𝑞, 𝑟 such that𝑛 𝑑 𝑞 𝑟 and 0 𝑟 𝑑.Suppose we want to find the greatestcommon divisor of integers 𝑎, 𝑏. DivisionTheorem states:If 𝑑 divides 𝑎,and 𝑑 divides 𝑏,then 𝑑 must divide rthere are unique integers 𝑞, 𝑟 such that𝑎 𝑏 𝑞 𝑟.

Euclidean AlgorithmCompute gcd(119,42):119 42*2 3542 35*1 735 7*5 0The last nonzero remainder is the gcd!Then 119 and 42 are not relatively prime.If 𝑑 divides 𝑎,and 𝑑 divides 𝑏,then 𝑑 must divide r

Euclidean AlgorithmCompute gcd(119,42):119 42*2 3542 35*1 735 7*5 0The last nonzero remainder is the gcd! Then119 and 42 are not relatively prime.If 𝑑 divides 𝑎,and 𝑑 divides 𝑏,then 𝑑 must divide rIf gcd(𝑎, 𝑏) 1, then 𝑎 has a multiplicativeinverse mod 𝑏.

Affine Cipher - cryptanalysisHow many keys? Keys (a,b) a must be relatively prime to 26 b an integer in {0,1,2, ,25}Letter frequency analysis? This attack still applies Still not secure

Affine Cipher - cryptanalysis114How many keys?215316 Keys (𝑎, 𝑏) 𝑎 must be relatively prime to 26 𝑏 an integer in {0,1,2, ,25}417518619720821922102311241225Letter frequency analysis? This attack still applies Still not secure13

Affine Cipher - cryptanalysis12 choices for a26 choices for bHow many keys?12 26 312 choicesfor (a,b) Keys (𝑎, 𝑏) 𝑎 must be relatively prime to 26 𝑏 an integer in {0,1,2, ,25}Letter frequency analysis? This attack still applies Still not secure11421531641751861972082192210231124122513

Preventing letter frequency attacksThe problem with Shift Ciphers and Affine Cipher is that plaintextletters consistently map to the same ciphertext letters:WARNINGIMDZUZSMESSAGEUWMMKCWMust encrypt so that, for example, plaintext A’s map to different lettersin ciphertext.

One time padSuppose secret key k is a long string of random letters:F DO JCE T MQ Z P I I Y 5 3 14 9 2 4 19 12 16 25 15 8 8 24Alice encrypts her message: MESSAGE by adding the first 7 letters ofthe secret key as follows KEYmod 26MESSAGE1241818064531492419

One time padSuppose secret key k is a long string of random letters:F DO JCE T MQ Z P I I Y 5 3 14 9 2 4 19 12 16 25 15 8 8 24Alice encrypts her message: MESSAGE by adding the first 7 letters ofthe secret key as followsMESSAGE1241818064 KEY531492419mod 261773227210231776121023RHGBCKX

One time padOne-time pad secret key is a long string of random letters:F DO JCE T MQ Z P I I Y 5 3 14 9 2 4 19 12 16 25 15 8 8 24Affine cipher secret key is a pair of integers (𝑎, 𝑏)Shift cipher secret key is one integer 𝑘

Security vs efficencyOne-time padsecret key is a long string of random letters, length 𝑛26𝑛 possible keysAffine ciphersecret key is a pair of integers (𝑎, 𝑏)312 possible keysShift ciphersecret key is one integer 𝑘25 possible keys

Goals of cryptographyKey ExchangeAliceEveBobNotice that in the Shift Cipher and Affine cipher, the same key is used to encrypt anddecrypt.Then Alice and Bob must share a key before they can communicate privately.

Goals of cryptographyKey ExchangeAliceEveQuestion: How can Alice and Bob communicate so that- they both learn a shared secret key- the eavesdropper does not learn the key?Bob

Goals of cryptographyPublic key encryptionAliceBob’spublickeyEveQuestion: How can Alice and Bob communicate so that- Bob can understand Alice’s messages- eavesdroppers cannot understand Alice’s messages- Alice and Bob DON’T need to share the same secret key ?Bob

Thank you!angela.robinson@nist.gov

Cryptography Angela Robinson National Institute of Standards and Technology. Cryptography sightings. Cryptography sightings Secure websites are protected using: digital signatures –authenticity, integrity . mathematical s