Classical Cryptography - University of Nebraska-Lincoln

Classical Cryptography - University of Nebraska-Lincoln

Introduction to Security Attacks Interception Interruption Modification Fabrication Interception (eavesdropping) Unauthorized party gains access to service or data Example: Wiretapping to capture data into a network and coping of files

Interruption (denial of service) Services or data become unavailable Examples: Destruction of a piece of hardware, cutting of cable and disabling of a file management system Modification Unauthorized party changes the data or tampers with the service

Examples: Changing values in a file, altering a program so that it performs differently and changing the contents of messages that are sent over the network Fabrication Unauthorized party generates additional data or activity Examples Hacker gaining access to a persons email and sending messages, and adding records to a file Cryptography

Given credit where it is due Most slides are from B. A. Miller at Mount Allison University Some slides are from Scott Shenker and Ion Stoica at University of California, Berkeley I modified and added some slides What is cryptography? kryptos hidden grafo write Keeping messages secret Usually

by making the message unintelligible to anyone that intercepts it The Problem Private Message Bob Alice Eavesdropping Eve The Solution Private Message Private Message

Encryption Decryption Scrambled Message Bob Alice Eavesdropping Eve What do we need? Bob and Alice want to be able to encrypt/decrypt easily But no one else should be able to decrypt How do we do this?

Keys! Using Keys Nonsense Encryption Plaintext Ciphertext Decryption Plaintext The Shift Cipher We shift each letter over by a certain

amount Plaintext five red balloons Key = 3 f+3=I i+3=L v+3=Y Encryption ILYH UHG EDOORRQV Ciphertext The Shift Cipher cont. To decrypt, we just subtract the key

ILYH UHG EDOORRQV Ciphertext Key = 3 I-3=f L-3=i Y-3=v five red balloons Decryption Plaintext Whats wrong with the shift cipher? Not enough keys! If we shift a letter 26 times, we get the same letter back

A shift of 27 is the same as a shift of 1, etc. So we only have 25 keys (1 to 25) Eve just tries every key until she finds the right one The Substitution Cipher Rather than having a fixed shift, change every plaintext letter to an arbitrary ciphertext letter

Plaintext a b c d e z Ciphertext G X N S D

Q The Substitution Cipher cont. Key = a G n B b X o

Y c N p Z d S q P

e D r H f A s W g F

t I h V u J i L v

R j M w U k C x K l

O y T m E z Q five red balloons f =A i =L

v =R Plaintext Encryption ALRD HDS XGOOYYBW Ciphertext The Substitution Cipher cont. To decrypt we just look up the ciphertext letter in the table and then write down the matching plaintext letter How many keys do we have now?

A key is just a permutation of the letters of the alphabet There are 26! permutations 403291461126605635584000000 Whats wrong with this substitution Cipher? Frequency Analysis In English (or any language) certain letters are used more often than others

If we look at a ciphertext, certain ciphertext letters are going to appear more often than others It would be a good guess that the letters that occur most often in the ciphertext are actually the most common English letters Letter Frequency This is the letter frequency for

English The most common letter is e by a large margin, followed by t, a, and o J, q, x, and z hardly occur at all Frequency Analysis in Practice Suppose this is our ciphertext dq lqwurgxfwlrq wr frpsxwlqj surylglqj d eurdg vxuyhb ri wkh glvflsolqh dqg dq lqwurgxfwlrq wr surjudpplqj. vxuyhb wrslfv zloo eh fkrvhq iurp: ruljlqv ri frpsxwhuv,

gdwd uhsuhvhqwdwlrq dqg vwrudjh, errohdq dojheud, gljlwdo orjlf jdwhv, frpsxwhu dufklwhfwxuh, dvvhpeohuv dqg frpslohuv, rshudwlqj vbvwhpv, qhwzrunv dqg wkh lqwhuqhw, wkhrulhv ri frpsxwdwlrq, dqg duwlilfldo lqwhooljhqfh. 0.12 Relative Frequency 0.1 0.08 0.06 0.04 0.02

0 a b c d e f g h i j k l m n o p q r s t u v w x y z Letter Ciphertext distribution English distribution In our ciphertext we have one letter that occurs more often than any other (h), and 6 that occur a good deal more than any others (d, l, q, r, u, and w) There is a good chance that h corresponds to e, and d, l, q, r, u, and w correspond to the 6 next most common English letters Frequency Analysis cont. If we replace e with h and the 6 next most common letters with their matches, the ciphertext

becomes an intro???tion to ?o?p?tin? pro?i?in? a ?roa? ??r?e? o? t?e ?i??ip?ine an? an intro???tion to pro?ra??in?. ??r? e? topi?? ?i?? ?e ??o?en ?ro?: ori?in? o? ?o?p?ter?, ? ata repre?entation an? ?tora?e, ?oo?ean a??e?ra, ?i? ita? ?o?i? ?ate?, ?o?p?ter ar??ite?t?re, a??e???er? an? ?o?pi?er?, operatin? ???te??, net?or?? an? t?e internet, t?eorie? o? ?o?p?tation, an? arti?i?ia? inte??i?en?e. Classical to Modern Cryptography Classical cryptography Encryption/decryption

done by hand Modern cryptography Computers to encrypt and decrypt Same principles, but automation allows ciphers to become much more complex The Enigma Machine German encryption and decryption machine used in WWII

Essentially a complex, automated substitution cipher How did Enigma work? Rotors have different wiring connecting input to output Rotors move after each keypress

The key is the initial position of the three rotors Breaking the Enigma Britain set up its cryptanalysis team in Bletchley Park They consistently broke German codes throughout the war Important location in the history of computing

Alan Turing: British Cryptanalyst COLOSSUS: used by British codebreakers for Cryptanalysis Cryptography in the Computer Age Working with binary instead of letters We can do things many, many times Think of an Enigma machine that has 2128 pairs of symbols on each rotor, and 20 rotors

Other than that, the basic principles are the same as classical cryptography Modern Ciphers We design one relatively simple scrambling method (called a round) and repeat it many times Think of each round as a rotor on the Enigma One round may be easy to break, but when you put them all together it becomes very hard Almost all ciphers follow one of two structures

SPN (Substitution Permutation Network) Feistel Network (basis for DES) These describe the basic structure of a round Modern Ciphers in Practice Follow SPN/Feistel structure in general, but with added twists for security There are two important ciphers in the history of modern cryptography DES

(Data Encryption Standard) AES (Advanced Encryption Standard) DES U.S. Government recognized the need to have a standardized cipher for secret documents DES was developed by IBM in 1976 Analysis of DES was the beginning of modern cryptographic research Breaking DES The key length of DES was too short If a key is 56 bits long, that means there are

256 possible keys DES Cracker machines were designed to simply try all possible keys Increase key length to 128 bit Triple DES Breaking DES cont. DES was further weakened by the discovery of differential cryptanalysis Biham and Shamir in 1990; The most significant advance in cryptanalysis since frequency analysis

Ideally a ciphertext should be completely random, there should be no connection to its matching plaintext Differential analysis exploits the fact that this is never actually the case; Uses patterns between plaintext and ciphertext to discover the key Developing the AES With DES effectively broken, a new standard was needed In 2001, the Rijndael cipher was selected to

become the Advanced Encryption Standard The Problem of Symmetric Key Cryptography Up until now weve been talking about symmetric key cryptography Alice and Bob are using the same key to encrypt/decrypt Problem: How does Bob get the key to Alice when Eve is eavesdropping?

Up until 1976 the only solution was to physically give Alice the key in a secure environment Public Key Cryptography Diffie and Hellman published a paper in 1976 providing a solution We use one key for encryption (the public key) and a different key for decryption (the private key) Everyone knows Alices public key, so they can encrypt messages and send them to her

But only Alice has the key to decrypt those messages No one can figure out Alices private key even if they know her public key Using Public Keys Nonsense Encryption Plaintext Ciphertext Decryption

Plaintext Public Key Cryptography in Practice The problem is that public key algorithms are too slow to encrypt large messages Instead Bob uses a public key algorithm to send Alice the symmetric key, and then uses a symmetric key algorithm to send the message The best of both worlds! Security

of public key cryptography Speed of symmetric key cryptography Sending a Message Whats your public key? Bob picks a symmetric key and encrypts it using Alices public key Alice decrypts the symmetric key using her private key Then sends the key to Alice Bob encrypts his message using

the symmetric key Then sends the message to Alice hi Alice decrypts the message using the symmetric key The RSA Public Key Cipher The most popular public key cipher is RSA, developed in 1977

Named after its creators: Rivest, Shamir, and Adleman Uses the idea that it is really hard to factor large numbers Create public and private keys using two large prime numbers Then forget about the prime numbers and just tell people their product Anyone can encrypt using the product, but they cant decrypt unless they know the factors If Eve could factor the large number efficiently she could get the private key, but there is no known way to do this Public-Key Cryptography: RSA (Rivest,

Shamir, and Adleman) Sender uses a public key - Advertised to everyone Receiver uses a private key Plaintext Plaintext Encrypt with public key Internet Decrypt with

private key Ciphertext 42 Generating Public and Private Keys Choose two large prime numbers p and q (~ 256 bit long) and multiply them: n = p*q Chose encryption key e such that e and (p-1)*(q-1) are relatively prime Compute decryption key d, where

d = e-1 mod ((p-1)*(q-1)) (equivalent to d*e = 1 mod ((p-1)*(q-1))) Public key consists of pair (n, e) Private key consists of pair (n, d) 43 RSA Encryption and Decryption Encryption of message block m: - c = me mod n Decryption of ciphertext c: - m = cd mod n 44

Example (1/2) Choose p = 7 and q = 11 n = p*q = 77 Compute encryption key e: (p-1)*(q-1) = 6*10 = 60 chose e = 13 (13 and 60 are relatively prime numbers) Compute decryption key d such that 13*d = 1 mod 60 d = 37 (37*13 = 481) 45 Example (2/2)

n = 77; e = 13; d = 37 Send message block m = 7 Encryption: c = me mod n = 713 mod 77 = 35 Decryption: m = cd mod n = 3537 mod 77 = 7 46 Properties

Confidentiality A receiver B computes n, e, d, and sends out (n, e) - Everyone who wants to send a message to B uses (n, e) to encrypt it How difficult is to recover d ? (Someone that can do this can decrypt any message sent to B!) Recall that d = e-1 mod ((p-1)*(q-1)) So to find d, you need to find primes factors p and q - This is provable very difficult

47 RSA Factoring Challenge In mathematics, the RSA numbers are a set of large semiprimes (numbers with exactly two prime factors) that are part of the RSA Factoring Challenge. RSA-768 has 232 decimal digits and was factored on December 12, 2009. Its the largest factored RSA number to date. RSA-2048 may not be factorizable for many years to

come, unless considerable advances are made in integer factorization or computational power in the near future. 48 RSA Factoring Challenge Suppose, for example, that in the year 2020 a factorization of RSA-1024 is announced that requires 6 months of effort on 100,000 workstations. In this hypothetical situation, would all 1024-bit RSA keys need to be replaced? - The answer is no. If the data being protected needs security for significantly less than six months, and its value is considerably less than the cost of running 100,000 workstations for that period, then 1024-bit keys may continue to be used.

49 Are we all secure now? Unfortunately not, there are still many problems that need to be dealt with How does Bob know that hes really talking to Alice? How does Alice know that the message she receives hasnt been tampered with? How does Alice know the message was sent by Bob?

Recently Viewed Presentations

  • Katalyzované reakce

    Katalyzované reakce

    Katalyzované reakce Kinetika katalyzovaných reakcí, vliv vnitřní difuze na selektivitu Heterogenní katalýza Chemisorpce Reakce látky s aktivním místem na povrchu katalyzátoru Adsorpční izoterma Závislost rovnovážného množství adsorbované látky na složení směsi Langmuirova izoterma adsorpce v jediné vrstvě stupeň pokrytí povrchu...
  • Programming Languages & Software Engineering

    Programming Languages & Software Engineering

    Lauren Milne. Spring 2015. Announcements Homework 3 due on Wednesday at 11pm. Catie back Monday. Spring 2015. CSE 373 Data structures and Algorithms. Amortized Analysis. In amortized analysis, the time required to perform a sequenceof data structure operations is averaged...
  • Workshop on Health Examination Surveys

    Workshop on Health Examination Surveys

    Health examination survey (HES) HES is a population survey with physical examinations, laboratory tests, physical functioning tests, etc. ; and a questionnaire Background of the Workshop Some crucial population level health information can be obtained only by HES Successful examples...


    Figure4-1A laser beam is used to determine the search area for the position of a shooter who has fired a bullet through a window and wounded a victim. The bullet path is determined by lining up the victim's bullet wound...
  • Learning Module 01 - University of Texas at Dallas

    Learning Module 01 - University of Texas at Dallas

    Which sound is a voiced labiodental fricative? Which sound is a voiceless velar stop? Which sound is a voiced affricate? Which consonants are interdentals? Which sound is in the middle of "rattle?" Exercise 01
  • Language Variation at a Region in China and

    Language Variation at a Region in China and

    The goal being a better understanding of the structure of language and of how languages function in communication (Wardaugh, 2007). ... which explains SES status factor in individuals' choice of lexical items. ... Robins, C., & Lewis, J. (1968). A...
  • Today: 1.Vocabulary lists- review with Dr. Weast- foods,

    Today: 1.Vocabulary lists- review with Dr. Weast- foods,

    Today: Vocabulary lists- review with Dr. Weast- foods, countries Deaf Awareness Week- hang posters around campus - shhh! Deaf for a Day information- teacher signature forms, and signs- handout (I have already emailed all teachers).

    In 1095, Pope Urban II launched the First Crusade, calling forth knights and peasants from across Western Europe to march against Muslim Turks in the Byzantine Empire and ultimately "re-conquer" the holy city of Jerusalem.