CS计算机代考程序代写 x86 chain android algorithm Hive Cryptography

Cryptography

CSE 365 – Information Assurance

Spring 2020

Adam Doupé

Arizona State University

http://adamdoupe.com

Adam Doupé, Information Assurance

Cryptography

• Derived from the Greek words for “hidden,

secret” and “writing”

• How to keep information secret or hidden?

2

Adam Doupé, Information Assurance

Terminology

• Encryption

– Process of transforming a message such that

its meaning is concealed

• Decryption

– Process of transforming an encrypted

message back into original form

3

Adam Doupé, Information Assurance

Terminology

• Cryptosystem
– A system that describes how to encrypt or decrypt

messages

• Plaintext
– Message in its original form

• Ciphertext
– Message in its encrypted form

• Cryptographer
– Invents encryption algorithms

• Cryptanalyst
– Breaks encryption algorithms or implementations

4

Adam Doupé, Information Assurance

Security Benefits of Cryptography

• Confidentiality

• Integrity

• Authentication (as we will see)

• Non-repudiation

5

Adam Doupé, Information Assurance

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

6

Adam Doupé, Information Assurance

Caesar Cipher

“If he had anything confidential to say, he

wrote it in cipher, that is, by so changing the

order of the letters of the alphabet, that not a

word could be made out. If anyone wishes to

decipher these, and get at their meaning, he

must substitute the fourth letter of the

alphabet, namely D, for A, and so with the

others.”

– Suetonius, Life of Julius Caesar 56

7

Adam Doupé, Information Assurance

Caesar Cipher

• M = { sequences of letters }
• K = { i | i is an integer and 0 ≤ i ≤ 25 }
• E = { Ek | k K and for all letters m,

Ek(m) = (m + k) mod 26 }

• D = { Dk | k K and for all letters c,
Dk(c) = (26 + c – k) mod 26 }

• C = M

8

Adam Doupé, Information Assurance

Attacks

• Adversary is the person who wants to
break the cryptosystem

– Assume adversary knowns the algorithm
used, but not the key

• Is this a realistic assumption?

• Adversary capabilities
– ciphertext only

– known plaintext

– chosen plaintext

9

Adam Doupé, Information Assurance

Basis for Attacks

• Mathematical attacks
– Finding flaws by analyzing the underlying

mathematics of the cryptosystem

• Statistical attacks
– Make assumptions based on the underlying

language

– Examine ciphertext, correlate properties with the
assumptions

• Implementation attacks
– Implementation of cryptosystem introduces a flaw

that is not in the mathematics of the cryptosystem

10

Adam Doupé, Information Assurance

Classical Cryptography

• Sender and receiver share common key

– Keys may be the same, or trivial to derive

from one another

– Called symmetric cryptography

• Two basic types

– Substitution ciphers

– Transposition ciphers

– Combinations are called product ciphers

11

Adam Doupé, Information Assurance

Substitution Ciphers

• Change characters in plaintext to produce

ciphertext

• Ceasar cipher

– HELLO WORLD

– Change each letter to the third letter following

it (X -> A, Y -> B, Z -> C, …)

• Key is 3 or written as a letter ‘D’

– KHOOR ZRUOG

12

Adam Doupé, Information Assurance

Attacking the Caesar Cipher

• Exhaustive search

– Try all possible keys!

• Statistical analysis

– Compare to 1-gram model of English

13

Adam Doupé, Information Assurance

Attacking the Caesar Cipher

Example

LBHFUBHYQARIREOHVYQLBHEBJAPELCGB

• Compute frequency of each letter in
ciphertext

B: 0.15625 H: 0.125 L: 0.09375
E: 0.09375 Y: 0.0625 R: 0.0625
Q: 0.0625 A: 0.0625 V: 0.03125
U: 0.03125 P: 0.03125 O: 0.03125
J: 0.03125 I: 0.03125 G: 0.03125
F: 0.03125 C: 0.03125

14

Adam Doupé, Information Assurance

English Character Frequencies

15

Source: https://commons.wikimedia.org/wiki/File:English-slf.png

Adam Doupé, Information Assurance

Statistical Analysis

• For every possible key, calculate the

correlation of frequency of letters in

ciphertext with corresponding letters in

English

– p(x) is frequency of character x in English

– f(c) frequency of character c in ciphertext

– (i) = 0 ≤ c ≤ 25 f(c)p(c – i)

16

(i) for 0 <= i <= 25 0.053979 23 0.051841 13 0.047364 7 0.046382 20 0.045911 3 0.044305 0 0.044097 16 0.043745 24 0.042421 19 0.041392 14 0.038844 8 0.038755 1 0.038513 9 0.038090 22 0.037858 4 0.036610 11 0.034693 12 0.033309 17 0.033170 10 0.032574 15 0.032311 2 0.031901 25 0.029868 18 0.028699 5 0.026693 6 0.026650 21 17 Adam Doupé, Information Assurance Breaking the Cipher • LBHFUBHYQARIREOHVYQLBHEBJAPELCGB • 23 – IYECRYEVNXOFOBLESVNIYEBYGXMBIZD Y • 13 – YOUSHOULDNEVERBUILDYOUROWNCRY PTO • 7 – SIOMBIOFXHYPYLVOCFXSIOLIQHWLSJNI 18 Adam Doupé, Information Assurance Caesar Cipher Problems • Key is too short – Can be found by exhaustive search – Statistical frequencies not concealed well • Make the key longer! – Multiple letters in key – Idea is so smooth the statistical frequencies to make cryptanalysis harder 19 Adam Doupé, Information Assurance Vigenère Cipher • Similar idea to Caesar cipher, but use a phrase • Message – THE BOY HAS THE BALL • Key – VIG Encipher using Caesar cipher for each letter: key VIGVIGVIGVIGVIGV plain THEBOYHASTHEBALL cipher OPKWWECIYOPKWIRG 20 Adam Doupé, Information Assurance Frequency Analysis • OPKWWECIYOPKWIRG – 0.05537 22 • KLGSSAYEUKLGSENC – 0.05150 10 • YZUGGOMSIYZUGSBQ – 0.05027, 4 • STOAAIGMCSTOAMVK – 0.04530, 2 • QRMYYGEKAQRMYKTI 21 Adam Doupé, Information Assurance Vigenère terms • Period – length of the key • polyalphabetic – key has several different letters 22 Adam Doupé, Information Assurance Attacking Vigenère Cipher • Establish period; call it n • Break message into n parts, each part being enciphered using the same key letter • Solve each part, using techniques from breaking Caesar cipher – You can leverage one part from another 23 Adam Doupé, Information Assurance ADQYS MIUSB OXKKT MIBHK IZOOO EQOOG IFBAG KAUMF VVTAA CIDTW MOCIO EQOOG BMBFV ZGGWP CIEKQ HSNEW VECNE DLAAV RWKXS VNSVP HCEUT QOIOF MEGJS WTPCH AJMOC HIUIX 24 Adam Doupé, Information Assurance Establish Period • Kaskski: repetitions in the ciphertext occur when characters of the key appear over the same characters in the plaintext • Example: key VIGVIGVIGVIGVIGV plain THEBOYHASTHEBALL cipher OPKWWECIYOPKWIRG Note the key and plaintext line up over the repetitions (underlined). As distance between repetitions is 9, the period is a factor of 9 (that is, 1, 3, or 9) 25 Adam Doupé, Information Assurance ADQYS MIUSB OXKKT MIBHK IZOOO EQOOG IFBAG KAUMF VVTAA CIDTW MOCIO EQOOG BMBFV ZGGWP CIEKQ HSNEW VECNE DLAAV RWKXS VNSVP HCEUT QOIOF MEGJS WTPCH AJMOC HIUIX 26 Adam Doupé, Information Assurance Repetitions in Ciphertext Letters Start End Distance Factors MI 5 15 10 2, 5 OO 22 27 5 5 OEQOOG 24 54 30 2, 3, 5 FV 39 63 24 2, 2, 2, 3 AA 43 87 44 2, 2, 11 MOC 50 122 72 2, 2, 2, 3, 3 QO 56 105 49 7, 7 PC 69 117 48 2, 2, 2, 2, 3 NE 77 83 6 2, 3 SV 94 97 3 3 CH 118 124 6 2, 3 27 Adam Doupé, Information Assurance Estimate of Period • OEQOOG is a good starting point – Period may be 1, 2, 3, 5, 6, 10, 15, or 30 • Most of the others (7/10) have 2 in their factors • Almost as many (6/10) have 3 in their factors • Let’s try period of 2 * 3 = 6 28 Adam Doupé, Information Assurance Check our Period Guess • Index of coincidence (IC) is the probability that two randomly chosen letters from ciphertext will be the same • Precalculated for different periods: 1 0.066 3 0.047 5 0.044 2 0.052 4 0.045 10 0.041 Large 0.038 – (Note 1/26 - random) 29 Adam Doupé, Information Assurance Compute IC • IC = [n (n – 1)]–1 0≤i≤25 [Fi (Fi – 1)] – where n is length of ciphertext and Fi the (integer) number of times character i occurs in ciphertext • In our ciphertext, IC = 0.043 – Indicates a key of slightly more than 5 – A statistical measure, so it can be in error, but it agrees with the previous estimate (which was 6) 30 Adam Doupé, Information Assurance Split Ciphertext into Alphabets • AIKHOIATTOBGEEERNEOSAI – IC 0.069 • DUKKEFUAWEMGKWDWSUFWJU – IC 0.078 • QSTIQBMAMQBWQVLKVTMTMI – IC 0.078 • YBMZOAFCOOFPHEAXPQEPOX – IC 0.056 • SOIOOGVICOVCSVASHOGCC – IC 0.124 • MXBOGKVDIGZINNVVCIJHH – IC 0.043 31 Adam Doupé, Information Assurance Solve Each Alphabet • Can be done using techniques to attack Caesar Cipher • Can also use information from breaking one alphabet or knowledge of English 32 Adam Doupé, Information Assurance Frequency Analysis ABCDEFGHIJKLMNOPQRSTUVWXYZ 1 31004011301001300112000000 2 10022210013010000010404000 3 12000000201140004013021000 4 21102201000010431000000211 5 10500021200000500030020000 6 01110022311012100000030101 Letter frequencies are (H high, M medium, L low): HMMMHMMHHMMMMHHMLHHHMLLLLL Adam Doupé, Information Assurance Try Decrypting • First alphabet matches characteristics of unshifted alphabet • Third alphabet matches if I -> A

• Sixth alphabet matches if V -> A

• Substitute into ciphertext (bold are substitutions)

ADIYS RIUKB OCKKL MIGHK AZOTO

EIOOL IFTAG PAUEF VATAS CIITW

EOCNO EIOOL BMTFV EGGOP CNEKI

HSSEW NECSE DDAAA RWCXS ANSNP

HHEUL QONOF EEGOS WLPCM AJEOC

MIUAX

Adam Doupé, Information Assurance

Look For Clues

• AJE in last line suggests “are”, meaning second

alphabet maps A into S:

ALIYS RICKB OCKSL MIGHS AZOTO

MIOOL INTAG PACEF VATIS CIITE

EOCNO MIOOL BUTFV EGOOP CNESI

HSSEE NECSE LDAAA RECXS ANANP

HHECL QONON EEGOS ELPCM AREOC

MICAX

Adam Doupé, Information Assurance

Next Alphabet

• MICAX in last line suggests “mical” (a common

ending for an adjective), meaning fourth

alphabet maps O into A:

ALIMS RICKP OCKSL AIGHS ANOTO MICOL
INTOG PACET VATIS QIITE ECCNO MICOL
BUTTV EGOOD CNESI VSSEE NSCSE LDOAA
RECLS ANAND HHECL EONON ESGOS ELDCM
ARECC MICAL

• Can brute force the last alphabet

Adam Doupé, Information Assurance

Got It!

• QI means that U maps into I, as Q is

always followed by U:

ALIME RICKP ACKSL AUGHS ANATO MICAL

INTOS PACET HATIS QUITE ECONO MICAL
BUTTH EGOOD ONESI VESEE NSOSE LDOMA
RECLE ANAND THECL EANON ESSOS ELDOM
ARECO MICAL

Adam Doupé, Information Assurance

Transposition Ciphers

• Rearrange letters in plaintext to produce

ciphertext

• Properties

– Same 1-gram frequencies as English

– Different n-gram frequencies

– IC ~ .066

Adam Doupé, Information Assurance

Simple Transposition Cipher

• Break message into blocks of keylength

• Key is transposition of block

– Example: key(3, 0, 2, 1)

– Message: ASUI SAWE SOME

– Encrypt: SIUA AEWS OEMS

Adam Doupé, Information Assurance

Attacking the Simple Transposition

Cipher

• Brute force

– Key sizes ~< 13 (13! = 6,227,020,800) • English Analysis – Likely bigrams and trigrams – See more of this in Rail-Fence Adam Doupé, Information Assurance Rail-Fence Cipher • Rearrange letters in plaintext to produce ciphertext – Plaintext is HELLO WORLD – Rearrange as HLOOL ELWRD – Ciphertext is HLOOL ELWRD Adam Doupé, Information Assurance How to decide which ciphertext is which algorithm? • Caesar easy to test • Index of Coincidence • Correlation • 1-gram, Bigram and n-gram frequencies • Exploiting common English patterns – Q is always followed by a U – E most common letter… Adam Doupé, Information Assurance Real World Examples • Use XOR instead of shifts – Why? • Everyone implements their own Crypto – Don’t! – Side-Channel Attacks – Timing Attacks Adam Doupé, Information Assurance Def Con Quals 2011 • Binary L33tness 300 • Tar archive with .dex file and .jpgs • https://market.android.com/details?id=com .closecrowd.lokpixlite&hl=en • Encryption was XOR 8-byte key • Find out the key! https://market.android.com/details?id=com.closecrowd.lokpixlite&hl=en Adam Doupé, Information Assurance Modern Symmetric Encryption • Product Ciphers – Combination of substitution and transposition • Complicated and long history • Active area of development • What properties do you want? 50 Adam Doupé, Information Assurance Data Encryption Standard (DES) • Proposed by IBM as a standard for encrypting sensitive, unclassified government information • Standardized in 1976/1977 (after tweaks from the submission after consultation with the NSA) • 64 bit data block size • 56 bit key 51 Adam Doupé, Information Assurance 52 Adam Doupé, Information Assurance 53 Adam Doupé, Information Assurance S1 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0y y yy1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 1y y yy0 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 1y y yy1 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 0y y yy1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 1y y yy0 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 1y y yy1 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 0y y yy1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 1y y yy0 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1y y yy1 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 0y y yy1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 1y y yy0 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 1y y yy1 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 0y y yy1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 1y y yy0 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 1y y yy1 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 0y y yy1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 1y y yy0 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 1y y yy1 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 0y y yy1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1y y yy0 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 1y y yy1 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 x0000x x0001x x0010x x0011x x0100x x0101x x0110x x0111x x1000x x1001x x1010x x1011x x1100x x1101x x1110x x1111x 0y y yy0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 0y y yy1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 1y y yy0 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 1y y yy1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 54 Adam Doupé, Information Assurance The Fall of DES • Key size too small – 256 or 72,057,594,037,927,936 – 1998 the EFF built a custom DES-cracker for ~$250,000, broke key in 2 days – 2009 COPACOBANA machine built out of 120 FPGAs for ~$10,000 (off the shelf components) • Differential cryptanalysis (discovered in late 1980s) – Prior version was vulnerable • Linear cryptanalysis (1993) • Withdrawn as a standard 55 Adam Doupé, Information Assurance Symmetric Encryption in Practice • Basic algorithm will only encrypt data of blocksize – What size of messages do we want to send? • Different modes – Electronic Code Book (ECB) – Cipher Block Chaining (CBC) 56 DES Key (56 bits) Data (64 bits) Ciphertext (64 bits) Adam Doupé, Information Assurance Electronic Code Book (ECB) 57 DES K (56 bits) Plaintext Block Block Block Block Block Block DES DES DES DES DES K K K K K Ciphert ext Ciphert ext Ciphert ext Ciphert ext Ciphert ext Ciphert ext Ciphertext Adam Doupé, Information Assurance 58 image source from: https://blog.filippo.io/the-ecb-penguin/ https://commons.wikimedia.org/wiki/File:Tux.svg Original ECB encrypted https://blog.filippo.io/the-ecb-penguin/ https://commons.wikimedia.org/wiki/File:Tux.svg Adam Doupé, Information Assurance Cipher Block Chaining (CBC) Block Block Block Block Block IV DES ⊕ K (56 bits) Ciphert ext Ciphertext DES ⊕ K Ciphert ext DES ⊕ K Ciphert ext DES ⊕ K Ciphert ext DES ⊕ K Ciphert ext Adam Doupé, Information Assurance Advanced Encryption Standard (AES) • Originally called Rijndael • Standardized in 2001 – After five year process involving 15 competing designs • 128 bit block size • 128, 192, or 256 bit key size • “The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.” • Intel extended x86 to include this in hardware 60 Adam Doupé, Information Assurance One-time pad • Requires key to be the same size as the message being sent • XOR key with message • Never reuse key • One-time pad is provably secure if… – Key is truly random – Key is as long as the plaintext – Key is never reused in whole or in part – Key is kept completely secret 61 Adam Doupé, Information Assurance Main Drawbacks of Symmetric Cryptosystems • Alice and Bob want to securely communicate • How to securely transfer keys? 62 Adam Doupé, Information Assurance Asymmetric Cryptosystems • Goal – How to encrypt information without requiring a secure, shared, secret key? • Every party has two keys – Public Key (P) • PA , PB – Secret Key (S) • SA, SB • Also called Public-key Cryptography 63 Adam Doupé, Information Assurance 64 Idea and upper photo from https://blog.vrypan.net/2013/08/28/public-key-cryptography-for- non-geeks/ Key icons Created by Abdo from Noun Project https://thenounproject.com/abdulla_31/collection/keyes/?oq=key &cidx=1 PA SA https://blog.vrypan.net/2013/08/28/public-key-cryptography-for-non-geeks/ https://thenounproject.com/abdulla_31/collection/keyes/?oq=key&cidx=1 Adam Doupé, Information Assurance Public-Key Properties • Allows – Confidentiality – Nonrepudiation • Requires – Easy to generate P and S, hard to generate S given P – Each party to key S private • Both parties know PA and PB – Including the adversary, Eve (eavesdropper) – Everyone should know PA and PB 65 Adam Doupé, Information Assurance Encryption • Alice wants to send message M to Bob • Alice: PB(M) -> C

• Bob: SB(C) -> M

– What does Bob know for certain at this point?

• Eve: PA(C) -> Nothing, PB(C) -> Nothing

– What does Eve know at this point?

66

Adam Doupé, Information Assurance

Nonrepudiation

• Alice wants to make a statement M that

everyone knows is from Alice

• Alice: SA(M) -> C

• Bob: PA(C) -> M

– What does Bob know for certain at this point?

• Eve: PA(C) -> M

– What does Even know at this point?

67

Adam Doupé, Information Assurance

Confidential and Nonrepudiation

• Alice wants to send a message M to Bob

so that he knows it’s from Alice

• Alice: PB(SA(M)) -> C

• Bob: SB(PA(C)) -> M

– What does Bob know for certain at this point?

• Eve: PA(C) -> Nothing, PB(C) -> Nothing

– What does Eve know at this point?

68

Adam Doupé, Information Assurance

William Stanley Jevons, The Principles of Science (1874)

69

Adam Doupé, Information Assurance

History of Public-Key Cryptography

• Public
– 1976 Whitfield Diffie and Martin Hellman

published a way to exchange keys

– 1977 Ron Rivest, Adi Shamir, and Leonard
Adelman created RSA, a general public-key
cryptosystem

• Classified
– 1970 James Ellis, British Cryptographer at GCHQ

conceived of “non-secret encryption”

– 1973 Clifford Cocks (James’ colleague)
implemented RSA

70

Adam Doupé, Information Assurance

Diffie-Hellman Key Exchange

71

By Lorddota – Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=62609302

Alice and Bob agree to p = 23 and g = 9

Alice’s as = 4, Bob’s bs = 3

Alice Sends Bob A

A = 94 mod 23 = 6

Bob sends Alice B

B = 93 mod 23 = 16

Alice computes s with as
s = 164 mod 23 = 9

Bob computes s with bs
s = 63 mod 23 = 9

Adam Doupé, Information Assurance

RSA Key Generation

1. Choose two distinct prime numbers p and q

2. Compute n = p * q
– Given n, hard to factor p and q

– For any a, n, and e, with 0 < a < n and e > 1, calculating
ae mod n = c is easy

– Given c, e, and n, hard to calculate a

3. Compute m = (p – 1)(q – 1)

4. Choose an e such that 1 < e < m 5. Compute d = e-1 mod m – Can do this easily because e * d = 1 mod m 6. P = (n, e) 7. S = (n, d) 72 Adam Doupé, Information Assurance RSA Encryption • Alice send a message M to Bob – Must have PB = (nb, eb) • Turn M into an integer m, 0 <= m < nb • Alice: me mod n -> c

• Bob: cd mod n -> m

• Eve: c, Pb and Pa

73

Adam Doupé, Information Assurance

RSA Properties

• Allows us to send numbers less than n

• How to turn this into an actual

cryptosystem?

– Apply encryption to each letter?

– Use RSA to transmit an AES key with AES

encrypted data

• RSAE(k), AESk(M)

74

Adam Doupé, Information Assurance

Message Integrity

• What if an attacker flips a bit

– Or a bit is corrupted?

• How can the receiver know?

75

Adam Doupé, Information Assurance

Cryptographic Hash Functions

• Function that maps arbitrary size data to a

fixed size bit string

• One-way function

– Easy to compute, hard to go back

– Is it a 1-1 mapping?

• Deterministic

• Small change in input bit should

completely change the output

76

Adam Doupé, Information Assurance

Hash Functions Uses

• Public-Key Cryptography is fairly expensive

• Alice wants to make a statement M that
everyone knows is from Alice

• Alice: SA(hash(M)) -> SigM, M

• Bob: hash(M) =? PA(SigM)

– What does Bob know for certain at this point?

• What if Eve alters M to be M’?

– Bob: hash(M’) =? PA(SigM) -> hash(M’) =?
hash(M)

77

Adam Doupé, Information Assurance

Hash Function Uses

• File or Message integrity

• Password verification

• Proof-of-work

• File or data identifier

78

Adam Doupé, Information Assurance

Hash Function Properties

• Pre-image resistance

– Given a hash value h, it should be difficult to find
m, hash(m) = h

• Second pre-image resistance

– Given input m1 it should be difficult to find m2
such that hash(m1) = hash(m2)

• Collision resistance

– It should be difficult to find two messages m1 and
m2 such that hash(m1) = hash(m2)

79

Adam Doupé, Information Assurance

Public-Key Cryptosystem

Weaknesses

• How to trust the public keys?

• Eve replaces all the public keys with their

own

• Alice: PE(M1) -> C1

• Eve: SE(C1) -> M, PB(M2) -> C2

• Bob: SB(C2) -> M2

83

Adam Doupé, Information Assurance

How to trust public keys?

• Delegate/Centralization

– Public-Key Infrastructure

• Decentralization

– Web of trust

84

Adam Doupé, Information Assurance

Public-Key Infrastructure (PKI)

• Certificate Authority

– Responsible for verifying identify

– Can delegate to other trusted Cas, creating a

hierarchy

• Security goals

– Issuing certificates

– Revocation

85

Adam Doupé, Information Assurance

The Modern Web

• HTTPS (which uses TLS/SSL) uses a PKI

• Root CAs

– Must be distributed in OS and Software

• Different types of certificates (validation

levels)

– Domain Validated (DV) certificate

– Organization Validation (OV) certificate

– Extended Validation (EV) certificate

86

Adam Doupé, Information Assurance

Visual Indicators of Status

87

Adam Doupé, Information Assurance

Web of Trust

• Let end-users decide who to trust and to

verify identity

• Propagate trust

88

Adam Doupé, Information Assurance

Cryptography Research

• Breaking Crypto
– Theory

– Implementations

– https://cryptopals.com/

• Securing Crypto
– New Theory

– New Implementations

• New types of crypto
– Homomorphic encryption

– Secure Multi-party computation

– …

• Applied Crypto

89

https://cryptopals.com/