### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Cryptography CS 55500

Purdue

GPA 3.68

### View Full Document

## 50

## 0

## Popular in Course

## Popular in ComputerScienence

This 194 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 55500 at Purdue University taught by Staff in Fall. Since its upload, it has received 50 views. For similar materials see /class/208087/cs-55500-purdue-university in ComputerScienence at Purdue University.

## Reviews for Cryptography

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15

Cryptography CS 555 Lecture 13 Attacks on RSA RSA and Semantic Security Department of Computer Sciences Purdue University Cristina NitaRotaru Spring 2005Lecture 13 1 News Hw3 sol will be sent to the class list today Hw3 returned next week Hw4 deadline extended till next Thursday 1 30 PM Project proposal extended till next Saturday 1159 PM sent by email to me Cristina NitaRotaruD Spring 2005Lecture 13 Midterm Everything but the watermarking lecture includes today s lecture In the class 115 mins don t be late Closed books notebooks slides etc o 67 problems 12 multiple choice 1 numbertheory problem Study also definitions and attacks Cristina NitaRotaruD Spring 2005Lecture 13 Lecture Outline Factoring Attacks on RSA g OAEP f C Cristina NitaRotaruD Spring 2005Lecture 13 Recommended Reading From Stinson Chapter 5 Cristina NitaRotaruD Spring 2005Lecture 13 RSA Description Key generation Select 2 large prime numbers of about the same size p and q Compute n pq and I q1p1 Select a random integer e 1 lt e lt I st gcde 1 1 Compute d 1lt dlt I st ed 51 mod 1 Public key e n Secret key d p and q must also remain secret Cristina NitaRotaruD Spring 2005Lecture 13 RSA Description cont Encryption Forthe message M O lt M lt n use public key e n compute C Me mod n Decryption For a message C use private key d Compute Cd mod n Me mod nd mod n M Cristina NitaRotaruD Spring 2005Lecture 13 Attacks on RSA Brute force key search Timing attacks Mathematical attacks Cristina NitaRotaruD Spring 2005Lecture 13 Brute Force An adversaryjust tries all possible keys and keeps his fingers crossed that the right key is not the last key he will try worst case I Cristina NitaRotaruD Spring 2005Lecture 13 Timing Attacks Timing Attacks on Implementations of DiffieHeIman RSA DSS and Other Systems 1996 Paul C Kocher By measuring the time required to perform decryption exponentiation with the private key as exponent an attacker can figure out the private key Possible countermeasures use constant exponentiation time add random delays blind values used in calculations 39 Cristina NitaRotaruD Spring 2005Lecture 13 10 Timing Attacks cont Is is possible in practice YES OpenSSL Security Advisory 17 March 2003 Timing based attacks on RSA keys Researchers have discovered a timing attack on RSA keys to which OpenSSL is generally vulnerable unless RSA blinding has been turned on Cristina NitaRotaruD Spring 2005Lecture 13 11 MathBased Key Recovery Attacks Three possible approaches 1 Factor n pq 2 Determine CIgtn 3 Find the private key cl directly All the above are equivalent to factoring n Cristina NitaRotaruD Spring 2005Lecture 13 12 Knowing In Implies Factorization Knowing both n and cIgtn one knows n m CIgtn p1q1 m p q 1 n p np 1 MW np pZ n p pZ nplt1gtnp pn0 p2nltIgtn1pn0 There are two solutions of p in the above equation Both p and q are solutions Cristina NitaRotaruD Spring 2005Lecture 13 13 Factoring Large Numbers Three most effective algorithms are quadratic sieve elliptic curve factoring algorithm numberfield sieve One idea many factoring algorithms use Suppose one find xzay2 mod n such that x y mod n and x y mod n Then n xyxy Neither xy or xy is divisible by n thus gcdxyn has a non trivial factor of n RSA576 Factored Dec 3 2003 10000 Cristina NitaRotaruD Spring 2005Lecture 13 14 Factoring When knowing e and d Fact if npq then x221 mod n has four solutions that are ltn x251 mod n if and only if both x251 mod p and x251 mod q Two trivial solutions 1 and n1 1 is solution to x a 1 mod p and x a 1 mod q n1 is solution to x a 1 mod p and x a 1 mod q Two other solutions solution to x a 1 mod p and x a 1 mod q solution to x a 1 mod p and x a 1 mod q Eg n3 515 then x251 mod 15 has the following solutions 1 4 11 14 Cristina NitaRotaruD Spring 2005Lecture 13 15 Factoring When knowing e and d Knowing a nontrivial solution to x221 mod n compute gcdx1n and gcdx1n Eg 4 and 11 are solution to x251 mod 15 gcd4115 5 gcd4115 3 gcd11115 3 gcd11115 5 Cristina NitaRotaruD Spring 2005Lecture 13 Factoring When knowing c and d Knowing ed such that ed a 1 mod ltIgtn write ed 1 25 r r odd choose w at random such that 1ltwltn1 ifw not relative prime to n then return gcdwn if gcdwn1 what value is w2 Sr mod n compute w W w4r until find w tr a 1 mod n Fails when we 1 mod n or w t re 1 mod n Cristina NitaRotaruD Spring 2005Lecture 13 Example Factoring n given 01 nput n2773e17d157 ed1266822 667 r667 Pick random w compute wr mod n w7 76671 no good w8 8667471 and 47121 so 471 is a nontrivial square root of 1 mod 2773 compute gcd4711 277359 gcd4711 277347 277359 47 Cristina NitaRotaruD Spring 2005Lecture 13 Decryption attacks on RSA RSA Problem Given a positive integer n that is a product of two distinct large primes p and q a positive integer e such that gcde p1q11 and an integer c find an integer m such that meac mod n widely believed that the RSA problem is computationally equivalent to integer factorization however no proof is known The security of RSA encryption s scheme depends on the hardness of the RSA problem Cristina NitaRotaruD Spring 2005Lecture 13 Summary of Key Recovery Math based Attacks on RSA Three possible approaches 1Factor n pq 2Determine CIgtn 3Find the private key d directly All are equivalent finding out d implies factoring n if factoring is hard so is finding out d Cristina NitaRotaruD Spring 2005Lecture 13 20 Other Attacks on RSA Forward Search Attack If message space is small the attacker can create a dictionary of encrypted messages public key known encrypt all possible messages and store them When the attacker sees a message on the network compares the encrypted messages so he finds out what particular message was encrypted Cristina NitaRotaruD Spring 2005Lecture 13 21 Semantic Security Cryptosystems in which an adversary can not in polynomial time distinguish ciphertexts Cristina NitaRotaruD Spring 2005Lecture 13 22 Mallcablc Nonmalleable given a ciphertext it is computationally infeasible to generate a different ciphertext such that the corresponding plaintexts are related Non malleable systems are semantically secure Cristina NitaRotaruD Spring 2005Lecture 13 23 Semantic Security of RSA RSA is malleable RSA leaks information about the plaintext RSA not semantically secure because it is deterministic OAEP tries to solve these problems Cristina NitaRotaruD Spring 2005Lecture 13 24 Quadratic Residues a is a quadratic residue modulo p if El b EZp such that b2 a a mod p otherwise a is a nonquadratic residue Qp is the set of all quadratic residues QB is the set of all nonquadratic residues If p is prime there are p12 quadratic residues in Zp lQpl IO1V2 If r IO1V2 a 1 mod p then r is a quadratic residue if1 then r is a nonquadratic residue Cristina NitaRotaruD Spring 2005Lecture 13 25 Legendre Symbol Let p be an odd prime and a an integer The Legendre symbol is defined Oifpa 3 1 ifaEQp 1ifaE p Cristina NitaRotaruD Spring 2005Lecture 13 26 Jacobi Symbol let n 2 3 be a composite odd with prime factorization e1 62 6k n 171172 39pk the Jacobi symbol is defined to be aiiiiiiiii Cristina NitaRotaruD Spring 2005Lecture 13 27 ek RSA Leaks the Jacobi Symbol C MOI mod n gcdd ltIgtn 1 3 Since d is odd then m Cristina NitaRotaruD Spring 2005Lecture 13 28 Cost of Semantic Security in Public Key Encryption In order to have semantic security some expansion is necessary ie the ciphertext must be larger than its corresponding plaintext why suppose that all plaintexts have size m what is the minimal size of ciphertexts to have an adequate level of security eg takes 2t to break the semantic security Cristina NitaRotaruD Spring 2005Lecture 13 29 A Padding Scheme for Semantically Secure Publickey Encryption Padding Scheme 1 given a publickey encryption scheme E to encrypt x generates a random r the ciphertext is y1 EKr y2 Hr x where H is a cryptographic hash function to decrypt rm one compute HDKy1 y2 requires an extra random number generation and an XOR operation for each bit Cristina NitaRotaruD Spring 2005Lecture 13 30 Example of the Padding Scheme Example of the Padding Scheme for RSA Public key ne The ciphertext for x is re mod n X Hr To decrypt a ciphertext y1 y2 compute r y1OI mod n and X y2 Hr To encrypt a 128bit message the ciphertext has 1024128 bits Cristina NitaRotaruD Spring 2005Lecture 13 31 Why is This Padding Scheme Secure This padding scheme is provany INDCPA secure when H is modelled as a random oracle ie H is a random function and EK is a trapdoor oneway permutation to learn any information about x from EKr X Hr one has to learn some information about Hr as H is a random function the only way to learn any information about Hr is to evaluate H at the point r an adversary who can learn anything about x thus knows r the adversary can thus invert EK Cristina NitaRotaruD Spring 2005Leoture 13 32 OAEP M Belare and P Rogaway Optimal asymmetric encryption Advances in Cryptology Eurocrypt 94 Springer Verlag 1994 921 1 1 Optimal Asymmetric Encryption Padding OAEP method for encoding messages Uses one trapdoor permutation functions EK and two hash functions H O1m01t and G 01O1m To encrypt xEO1m chooses random rEO1t and computes EKx rGr r Hx Gr How to decrypt given y Security intuitions Cristina NitaRotaruD Spring 2005Lecture 13 33 OAEP cont 0 OAEP EKX Gr r Hx Gr H 01m01t and G O1t01m OAEP is provany INDCPA secure when H and G are modeled as random oracles and EK is a trapdoor oneway permutation A ciphertext has size n z1024 for RSA The padding size t should be st 2t computing time is infeasible why t128 The plaintext size m can be up to 1024128896 Expansion is optimal Cristina NitaRotaruD Spring 2005Leoture 13 34 Summary Mathbased attacks 1Factor n pq 2Determine CIgtn 3Find the private key cl directly All are equivalent RSA is malleable OAEP used in practice to encrypt using RSA Cristina NitaRotaruD Spring 2005Lecture 13 35 Next Lecture o More public key protocols Rabin EIGamaI Probabilistic cryptosystems Reading Stinson 58 Rabin 61 EIGamaI Cristina NitaRotaruD Spring 2005Lecture 13 36 Cryptography CS 555 Lecture 1 Security services attacks and mechanisms Department of Computer Sciences Purdue University Cristina NitaRotaru Spring 2005Lecture1 1 Course Information Meetings TuampTh 130245 PM Professor contact info Office REC 217DCS174 Email crisncs Office hours TuTh 3 4 PM in CS174 TA Jayesh Pandey Office MATH BB Office hours W 1 30 330 Email jpandeycs Class webpage httpwwwcspurdueed uhomescrisncoursescs55520 O5 Cristina NitaRotaruD Spring 2005Lecture 1 Grading Policy Written Assignments 6 20 Final Project 25 Midterm Exam 20 Final Exam 30 Class Participation 5 Undergrads are required to attend class Cristina NitaRotaruD Spring 2005Lecture 1 Homework Homework must by TYPED Homework is due and will be returned in class at 130 Every student has 3 extra days for all the written assignments that he can use Email me and the TA with name and number of extra days used for an assignment After using your 3 extra days no late homework will be accepted You must work alone on the assignments NO CHEATING Cristina NitaRotaruD Spring 2005Lecture 1 4 Exams and Project Midterm February 24 Final check university web page Project Teams of 23 required Proposal due one week before midterm Must have a practical aspect There will be a meeting with the professor to discuss the results of the project PLEASE COME AND TALK TO ME IF YOU HAVE PROBLEMS WITH YOUR PROJECT DON T WAIT TLL THE LAST DAY Cristina NitaRotaruD Spring 2005Lecture 1 5 Course Overview 1 Concepts and principles of cryptography security services attacks and mechanisms Classical cryptographic systems shift cipher Vigenere and Vernam ciphers Jefferson wheel cipher and the Enigma machine Block ciphers DES Blowfish RC5 IDEA AES Stream ciphers SEAL RC4 65555 Cristina NitaRotaruD Spring 2005Lecture 1 Course Overview 2 Publickey encryption RSA quot ElGamal Rabin CS555 Probabilistic cryptosystems GoldwasserMicali Data integrity hash functions MD5 SHA1 HMAC Digital signatures RSA ElGamal DSA Schnorr Authentication protocols data and entity authentication One time passwords Lamport39s scheme challengeresponse schemes Kerberos Cristina NitaRotaruD Spring 2005Lecture 1 Course Overview 3 Key management twoparty key exchange and group key management protocols Verifiable encryption and applications Digital rights Zeroknowledge proofs Identitybased cryptosystems 65555 Notions of threshold cryptography Proactive security Cristina NitaRotaruD Spring 2005Lecture 1 8 Reference Material Textbooks D R Stinson Cryptography Theory and Pract1ce Second Edition firm l m m CRC Press 2002 y W Stallings Cryptography and Network Security Principles and Practice Third Edition Prentice Hall 2002 Hilly 5 R ll3939i Recommended reading l a GBYP I39ANALYSIS Handbook of Apphed Cryptography HAC gagga g g Menezes Oorschot Vanstone CRC Press 7 httpwwwcacrrnathuwaterloocahac 7 Y Cryptanalysis of Number Theoretic Ciphers S smmjw gs h39 S Wafstaff Jr CRC Press Cristina NitaRotaruD Spring 2005Lecture 1 9 Academic Integrity Purdue University Academic Integrity httpwwwpurdueeduODOSadministra tionintegrityhtm Class policy httpwwwceriaspurdueeduhomesspa fCpolicyhtm Cristina NitaRotaruD Spring 2005Lecture 1 Lecture Outline Security services Security attacks Security mechanisms Li Terminology Attacks of ciphers and cryptographic Protocols Cristina NitaRotaruD Spring 2005Lecture 1 11 Recommended Reading Stallings Chapter1 HAC Chapter1 Wagstaff Chapter1 Cristina NitaRotaruD Spring 2005Lecture 1 Let s Make the Introductions Alice Carl or Eve Cristina NitaRotaruD Spring 2005Lecture 1 13 Information Security NETWORK SECURITY SECURITY Cristina NitaRotaruD Spring 2005Lecture 1 14 Information Security Security attacks Any action that compromises the security of information Security mechanism A mechanism that is designed to detect prevent or recover from a security attack Security service A service that enhances the security of data processing systems and information transfers A security service makes use of one or more security mechanisms Cristina NitaRotaruD Spring 2005Lecture 1 15 Security Services or Goals 1 Confidentiality information is available for reading only to authorized parties Example Alice sends a message to Bob only Alice and Bob can understand the content of the message 2 Authentication Data source authentication the data is coming from an authorized party Example Alice receives a message from Bob This service ensures that the message is from Bob and not from Carl Entity authentication the entity is who it says it is Example When Alice tries to obtain access to her bank account an authentication operation is performed to ensure that Alice asks for the information Cristina NitaRotaruD Spring 2005Lecture 1 16 Security Services 2 3 Integrity detect if data was modified from the source to the destination Example Alice sends an email to Bob Carl intercepts the message and modifies it Data integrity allows for Bob to detect that the message was modified on the way from Alice to him 4 Nonrepudiation neitherthe sender northe receiver of a message are able to deny the transmission Example Alice sends Bob a contract signed The non repudiation service ensures that Alice can not claim that the signature was produced by somebody else Cristina NitaRotaruD Spring 2005Leoture 1 17 Security Services 3 5 Access control only authorized parties can use specific resources Example Alice wants to print a document she must be authorized to get that document and to use the printer 6 Availability resources available to authorized parties Example A web site might become unavailable if the server crashes or is bombarded with requests Cristina NitaRotaruD Spring 2005Lecture 1 18 Security Attacks Passive the attacker does not modify the data only monitors the communication It threatens confidentiality Example listen to the communication between Alice and Bob and if it s encrypted try to decrypt it Active the attacker is actively involved in deleting adding or modifying data It threatens all security services Example Alice sends Bob a message meet me today at 5 Carl intercepts the message and modifies it meet me tomorrow at 5 and then sends it to Bob Cristina NitaRotaruD Spring 2005Leoture 1 19 Security Attacks Examples Interruption Interception Cristina NitaRotaruD Spring 2005Lecture 1 20 Security Attacks Examples Modification Cristina NitaRotaruD Spring 2005Lecture 1 21 Security Mechanisms Cryptography protect data by performing operations on the data for example encrypt data Software access limitations to in a database in operating system protect each user from other users networking firewall Hardware use smartcards for authentication Policies define who has access to what resources Physical security control who has physical access to devices storing data Cristina NitaRotaruD Spring 2005Lecture 1 22 What Is Cryptography Cryptography the study of mathematical techniques related to aspects of information security Cryptanalysis the study of mathematical techniques for attempting to defeat information security services Cryptology the study of cryptography and cryptanalysis Cristina NitaRotaruD Spring 2005Lecture 1 23 Cryptographic Primitives Encryption Key management Hash functions Digital signatures Certificates and CAs Cristina NitaRotaruD Spring 2005Lecture 1 24 Symmetric and Public Cryptography Symmetric cryptography Parties that communicate share a secret Used mainly to encipherdecipher data Examples DES Blowfish AES RC4 How obtain the secret key in the first place Public cryptography Each party has a PAIR P S of keys P is the public key and S is the secret key Used mainly to distribute keys and create digital signatures Examples RSA EIGamaI P Cristina NitaRotaruD Spring 2005Lecture 1 25 What is a Cryptosystem Plaintext data to be hidden or protected Ciphertext the result of applying a crypto operation encrypjjnptthe data decryption plaintext quot9 ciphertext quot9 ciphertext Definition A cryptosystem is a fivetuple P C K E D s t P is a finite set of possible plaintexts C is a finite set of possible ciphertexts K the keyspace is the set of possible keys For each kEK there are encryption rule ek ekzP a C decryption rule dk dsz a P st dkekx x PWNT Cristina NitaRotaruD Spring 2005Lecture 1 26 Going Back to Cryptanalysis There are different methods of breaking a cipher depending on the type of information available to the attacker the interaction with the cipher machine Cristina NitaRotaruD Spring 2005Lecture 1 27 Breaking Ciphers Cipher rex ronly attack The cryptanalyst knows only the ciphertext Sometimes the language of the plaintext and the cipher are also kown Goal find the plaintext and the key NOTE any encryption scheme vulnerable to this type of attack is considered to be completely insecure Knownplaintext attack The cryptanalyst knows several pairs of ciphertext and corresponding plaintext The goal is to find the key used to encrypt these messages or a way to decrypt any new messages that use that key Cristina NitaRotaruD Spring 2005Lecture 1 28 Breaking Ciphers 2 Chosenplaintext attack The cryptanalyst knows a number of encrypted messages and he can also encrypt any message he chooses The goal is to deduce the key used in the other encrypted messages or decrypt any new messages using that key o It can be adaptive the choice of plaintext depends on the ciphertext received from previous requests Cristina NitaRotaruD Spring 2005Lecture 1 29 Breaking Ciphers 3 Chosenciphertext attack Similar to the chosenplaintext attack but the cryptanalyst can choose the ciphertext not the plaintext The goal is to obtain the key It can also be adaptive The choice of ciphertext may depend on the plaintext received from previou requests Cristina NitaRotaruD Spring 2005Lecture 1 30 Protocols Definition A network protocol defines rules for sendingreceiving packets the format and type of the packets actions in response of receiving a certain type of packets A cryptographic protocol also specifies what cryptographic mechanisms are used Cristina NitaRotaruD Spring 2005Lecture 1 31 Attacks on Protocols Knownkey attack This attack uses previously used keys to determine new keys used for encryption Replay attack In this type of attack an attacker records a communication session and later on replays that session Impersonation attack This attack deceives the identity of one of the legitimate parties Cristina NitaRotaruD Spring 2005Lecture 1 32 Attacks on Protocols Dictionary attack This attacks usually targets passwords The attacker uses a dictionary of plaintextciphertext encrypted with all possible keys Forward search attack This attack is similar with the dictionary attack and is used if the message space is small or predictable with the goal of decrypting messages Interleaving attack Impersonation or other deception involving selective combination of information from parallel sessions it is an attack against authentication Cristina NitaRotaruD Spring 2005Lecture 1 33 Models for Evaluating Security Unconditional security The adversary has unlimited computational resources Analysis is made by using probability theory Perfect secrecy observation of the ciphertext provides no information to an adversary Complexitytheoretic security The adversary is assumed to have polynomial computational power The analysis uses complexity theory Polynomial attacks although feasible in practice can be computationally infeasible Cristina NitaRotaruD Spring 2005Lecture 1 34 Models for Evaluating Security Provable security Proof of security relies on the difficulty of solving a wellknown and supposedly difficult problem example computation of discrete logarithms Computational security practical security Measures the amount of computational effort required to defeat a system Sometimes related to the hard problems but no proof of equivalence is known Ad hoc security heuristic security Variety of convincing arguments that every successful attack requires more resources than the ones available to an attacker Unforeseen attacks remain a threat Cristina NitaRotaruD Spring 2005Lecture 1 Summary Cryptography is an important mechanism used to defend against attacks on computers and networks Encryption schemes and protocols can be attacked in several ways classified depending on the computational power and the amount of information available to the attacker Cristina NitaRotaruD Spring 2005Lecture 1 36 Recommended Reading for Next Lecture Chapter1 from Stinson Cristina NitaRotaruD Spring 2005Lecture 1 37 Cryptography CS 555 Lecture 14 Rabin SRA Mental Poker Protocol GoldwasserMicali Department of Computer Sciences Purdue University Cristina NitaRotaru Spring 2005Lecture 14 1 Midterm Mean 766 Std 15 Final will be similar make sure you provide clean solution every stepclaim back up by theoremsdefinitions etc Cristina NitaRotaruD Spring 2005Lecture 14 2 Lecture Outline Rabin Commutative encryption SRA Mental Poker Protocol GoldwasserMicali Cristina NitaRotaruD Spring 2005Lecture 14 Recommended Reading Stinson Chapter 58 for Rabin HAC Chapter 87 probabilistic schemes Stinson Chapter 61 EIGamaI Cristina NitaRotaruD Spring 2005Lecture 14 Quadratic Residues Module A Prime Definition a is a quadratic residue modulo p if El b EZp such that b2 E a mod p otherwise when a O a is a quadratic nonresidue 0 Q is the set of all quadratic residues p is the set of all quadratic nonresidues Cristina NitaRotaruD Spring 2005Lecture 14 Quadratic Residues Module A Prime Theorem If p is prime there are p12 quadratic residues in Zp Qp p12 Theorem A element a in QIo has exactly two square roots Theorem If a IO 2 2 1 mod p p prime then a is a quadratic residue if a 1 then a is a quadratic nonresidue Cristina NitaRotaruD Spring 2005Lecture 14 Legendre Symbol Let p be an odd prime and a an integer The Legendre symbol is defined Oifpa 1 ifaEQp P o 11faEQp p 12 p a from previous theorem Cristina NitaRotaruD Spring 2005Lecture 14 Jacobi Symbol let n 2 3 be odd with prime factorization 91 92 6k n 171172 39pk the Jacobi symbol is defined to be 91 92 ek a 1 1 1 n 191 172 pk the Jacobi symbol can be computed without factoring n see the textbook for details Cristina NitaRotaruD Spring 2005Lecture 14 Euler Pseudoprime For any prime p the Legendre symbol allo39ll2 mod p o For a composite n If the Jacobi symbol E aWV2 mod n then n is called an Euler pseudoprime to the base a o For any composite n the number of pseudo evidences that n is prime for at most half of the integers in Zn Cristina NitaRotaruD Spring 2005Lecture 14 Quadratic Residues Modulo 21 Composite Definition a is a quadratic residue modulo n aEQn if El b EZn such that b2 a a mod n otherwise when a 0 a is a quadratic nonresidue Fact aEQn where npq iff aEQIo and aEQq IbeEamod nthen bZEamodpand bZEamodq If b2 a a mod p and c2 a a mod q then the solutions to xabmodpandxacmodq xabmodpandecmodq xEbmodpandxacmodq Eb mod pandecmodq satisfies x2 a a mod p Cristina NitaRotaruD Spring 2005Lecture 14 Quadratic Residues Modulo 21 Composite Cristina NitaRotaruD IQnI lQpl quI p1q14 Q 3p1q14 Jacobi symbol does not tell whether a number a is a QR 3i 3 n p q when it is 1 then either aEQIo A ae Qq or ae Qp A aEQq when it is 1 then either aEQIo A aEQq or ae Qp A ae Qq it is widely believed that determining QR modulo n is equivalent to factoring n no proof is known a Spring 2005Lecture 14 11 The Rabin Encryption Scheme Motivation The security of RSA encryption depends on the difficulty of computing the e th root modulo n ie given C it is difficult to find M st MeC mod n o It is not known that this encryption is as difficult as factoring The Rabin encryption scheme is provany secure to a passive attack if factoring is hard here secure means to recover the plaintext from a ciphertext Idea ratherthan using an odd prime as e uses 2 fxx2 mod n this is not a special case of RSA as this function is not 1to1 Cristina NitaRotaruD Spring 2005Lecture 14 12 The Rabin Encryption Scheme Public key n Privacy key p q prime st n pq Encryption compute c m2 mod n Decryption compute the square roots of c how many are there Fact when quE3 mod 4 deterministic algorithms exist to compute the square roots othenvise efficient randomized algorithms exist to compute the square roots Cristina NitaRotaruD Spring 2005Lecture 14 13 Pragmatic Considerations for the Rabin Encryption Scheme Normally one picks psqs3 mod 4 Redundancy is used to ensure that only one square root is a legitimate message Encryption very fast only one exponen a on Decryption comparable to RSA decryption Cristina NitaRotaruD Spring 2005Lecture 14 14 The Mental Poker Problem Alice and Bob want to play poker we need a way to deal 5 cards to each of Alice and Bob so that Alice s hand of 5 cards does not overlap with Bob s hand Neither Alice nor Bob can control which cards they each get Neither Alice nor Bob knows the other party s hand Both hands should be random provided one party follows the protocol First solution due to Shamir Rivest and Adelman in 1980 SRA protocol uses commutative encryption schemes Cristina NitaRotaruD Spring 2005Lecture 14 15 Commutative Encryption Definition An encryption scheme is commutative if EK1EK2M EK2EK1M Given an encryption scheme that is commutative then DK1DK2EK1EK2M M Most symmetric encryption scheme such as DES and AES are not commutative Cristina NitaRotaruD Spring 2005Lecture 14 16 PohligHellman Exponentiation Cipher Commutative encryption scheme PohligHellman Exponentiation Cipher with the same modulus p p prime encryption key is e decryption key is d where eds1 mod p1 Ee1M Me1 mod p and Dd1C CO391 mod p Ee1Ee2M M6162 Ee1Ee2M mOd p Cristina NitaRotaruD Spring 2005Lecture 14 17 The SRA encryption scheme Commutative encryption Alice and Bob share npq and they both know p and q Alice has encryption key e1 and decryption key cl1 st e1d121 mod p1q1 Ee1MMe1 mod n Bob has e2 cl2 st ezdzsl mod p1q1 Also a commutative encryption scheme Essentially RSA except that e is kept private Cristina NitaRotaruD Spring 2005Lecture 14 18 The SRA Mental Poker Protocol Setup Alice and Bob share M1 M2 M52 denote the 52 cards npq p and q Alice has e1d1 and Bob has e2d2 Protocol Cristina NitaRotaruD Alice encrypts M1 M2 M52 using her key ie computes CjMe1 mod n for 1s s52 randomly permute them and send the ciphertexts to ob Bob picks 5 cards as Alice s hand and sends them to Alice Alice decrypts them to get his hand Bob picks 5 other cards as his hand encrypts them using his key and sends them to Alice Alice decrypts the 5 ciphertexts and sends to Bob Bob decrypts what Alice sends and gets his hand Both Alice and Bob reveal their key pairs to the other party and verify that the other party was not cheating Spring 2005Lecture 14 Security Analysis of the Protocol Bob sees 52 random ciphertexts he doesn t know which ciphertext corresponds to which cards Bob can only randomly pick Alice s hand and Bob does not know what Alice s hand is Bob can only randomly pick his hand and Alice doesn t know Bob s hand as it is encrypted under Bob s key This is not a security proof Cristina NitaRotaruD Spring 2005Lecture 14 20 An Attack on the SRA Mental Poker Protocol The encryption function fxxe mod n leaks information about x l fx is QR modulo n iff x is QR modulo n xe EQRn l x6 EQRIo and x6 EQRq l x EQRIo and x EQRq l XEQRn Why this matters in the SRA mental poker protocol suppose that the cards that are QR are mostly large cards and the cards that are not QR are mostly small cards then Bob can choose large cards for him and small cards for Alice Cristina NitaRotaruD Spring 2005Lecture 14 21 Semantic Security INDCPA for Public Key Encryption The INDCPA game Challenger Adversary picks a random key pair K KI and picks random bEO 1 K 7 M0 M1 picks M0 M1 of equal length C EKMb b EOl Attacker Wins game if bb Cristina NitaRotaruD Spring 2005Lecture 14 22 Semantic Insecurity of the RSA RSA encryption is not semantically secure because it is deterministic The encryption function fxxe mod n leaks information about x l it leaks the Jacobi symbol of x so it allows an attacker to distinguish between ciphertexts X gll ltiltilltl Cristina NitaRotaruD Spring 2005Leoture 14 23 The GoldwasserMicali Probablistic Encryption Scheme First provany semantically secure public key encryption scheme security based on the hardness of determining whether a number x is a QR modulo n when the factoring of n is unknown and the Jacobi symbol is 1 Encryption is done bit by bit For each bit in the plaintext the ciphertext is one number in Zn expansion factor is 1024 when using 1024 moduli Cristina NitaRotaruD Spring 2005Lecture 14 24 The GoldwasserMicali Probablistic Encryption Scheme Key generation randomly choose two large equalsize prime number p and q pick a random integer y such that err 1 P q public key is npqy private key is pq Encryption to encrypt one bit b pick a random x in Zn and let Cx2yb that is Cx2 when b0 and Cx2y when b1 Cristina NitaRotaruD Spring 2005Lecture 14 25 The GoldwasserMicali Probablistic Encryption Scheme Consider the Jacobi symbol of the ciphertext C x 211 yxzyxzyx2111 quot 1 q n p q Consider whether the ciphertext C is QR modulo n C is QR iff the plaintext bit b is O Decryption knowing p and q st npq one can determine whether x is QR modulo n and thus retrieves the plaintext Cristina NitaRotaruD Spring 2005Lecture 14 26 Cost of Semantic Security in Public Key Encryption In order to have semantic security some expansion is necessary ie the ciphertext must be larger than its corresponding plaintext the Goldwasser Micali encryption scheme generate ciphertexts of size 1024m Cristina NitaRotaruD Spring 2005Lecture 14 27 CDH and ElGamal Prove that any algorithm that solves CDH can be used to decrypt ElGamaI ciphertexts Intuition Compute m from y 9quot 6 m Bk is equivalent to compute Bk one knows y 9quot 398 and needs to compute gka Formal Proof gt Assume that algorithm OracleCHD solves CDH and let y 6 be an ElGamal encryption and let public key 9 5 9a y 9quot mod p 6 m gakmod p y OracleCDHg 5 y and x o y391 then x is the decryption of y 6 Cristina NitaRotaruD Spring 2005Lecture 14 28 Decision DH gt ElGamal Given decision DH oracle find two messages whose EIGamaI encryptions can be distinguished For any two M0 M1 3 ga EMo 9X IVIo BX Em1 9y M1 By Suppose receive ciphertext y6 Feed lty 3 gr 6 yrm0gt when yo is EM0 this is ltgX g3 M0 gax gXr M0gt ltgx gar gxargt when yo is EM1 this is ltgX g3 gxarM1M0gt if the DDH oracle say yes we say 0 othenNise we say 1 Cristina NitaRotaruD Spring 2005Lecture 14 Next Lecture EIGamal DLP CDH and DDH Security of EIGamal Cristina NitaRotaruD Spring 2005Lecture 14 30 Cryptography CS 555 Lecture 1 Security services attacks and mechanisms Cristina NitaRotaru Fall 2005Lecture1 1 Course Information Meetings MampWe 430545 PM Professor contact info Office REC 217DCS174 Email crisncs Office hours MW 4430 amp 545630 PM in CS174 TA Jayesh Pandey Office MATH BB Office hours Th 10 12 Email jpandeycs Class webpage httpwwwcspurdueed uhomescrisncoursescs555Fall 2005 Cristina NitaRotaru Fall 2005Lecture 1 Grading Policy Written Assignments 4 20 Two Programming Projects 25 Midterm Exam 20 Final Exam 30 Class Participation 5 Cristina NitaRotaru Fall 2005Lecture 1 Class Attendance Undergrads are required to attend every lecture email me if you missed a lecture and explain what is the reason Grads you are not required to attend to class but if you miss a lecture it is your responsibility to find out what happened I am not going to repeat what was done in class in office hours Please join the mailing list I am not going to repeat information that was sent to the mailing list Cristina NitaRotaru Fall 2005Lecture 1 Homework Homework must by TYPED Homework is due and will be returned in class at 430 Bring the printed copy Every student has 3 extra days for all the written assignments pr projects that he can use Email me and the TA with name and number of extra days used for an assignment After using your 3 extra days no late homework will be accepted You must work alone on the assignments 0 CHEATING WILL NOT BE TOLERATED Cristina NitaRotaru Fall 2005Lecture 1 Exams and Project Midterm Oct 5 Final check university web page Projects Teams of 2 required There will be a meeting with the professor to discuss the results of the projects You have 2 extra days for the projects as in hw PLEASE COME AND TALK TO ME IF YOU HAVE ANY PROBLEM WITH HWS or PROJECTS DON T WAIT TLL THE LAST DAY Cristina NitaRotaru Fall 2005Lecture 1 6 Course Overview 1 Concepts and principles of cryptography security services attacks and mechanisms Classical cryptographic systems shift cipher Vigenere and Vernam ciphers Jefferson wheel cipher and the Enigma machine Block ciphers DES Blowfish RC5 IDEA AES Stream ciphers SEAL RC4 C5555 Cristina NitaRotaru Fall 2005Lecture 1 Course Overview 2 Publickey encryption RSA 65555 ElGamal Rabin Probabilistic cryptosystems GoldwasserMicali Data integrity hash functions MD5 SHA1 HMAC Digital signatures RSA ElGamal DSA Schnorr Authentication protocols data and entity authentication One time passwords Lamport39s scheme challengeresponse schemes Kerberos Cristina NitaRotaru Fall 2005Lecture 1 Course Overview 3 Key management twoparty key exchange and group key management protocols Verifiable encryption and applications Digital rights Zeroknowledge proofs Identitybased cryptosystems Notions of threshold cryptography Proactive security C 5555 Cristina NitaRotaru Fall 2005Lecture 1 9 Reference Material Textbooks D R Stinson Cryptography Theory and Pract1ce Second Edition firm W CRC Press 2002 y W Stallings Cryptography and Network Security Principles and Practice Third Edition Prentice Hall 2002 Hilly 5 R ll3939i Recommended reading l GBYPTAIIALYSIS Handbook of Apphed Cryptography HAC g gga g g Menezes Oorschot Vanstone CRC Press 7 httpwwwcacrrnathuwaterloocahac 7 i 533 p Cryptanalysis of Number Theoretic Ciphers S mm wis h39 SWafstaffJr CRC Press Cristina NitaRotaru Fall 2005Lecture 1 10 Academic Integrity Purdue University Academic Integrity httpwwwpurdueeduODOSadministra tionintegrityhtm Class policy httpwwwceriaspurdueeduhomesspa fCpolicyhtm Cristina NitaRotaru Fall 2005Lecture 1 11 Qustions Cristina NitaRotaru Fall 2005Lecture 1 Lecture Outline Security services Security attacks Security mechanisms Li Terminology Attacks of ciphers and cryptographic Protocols Cristina NitaRotaru Fall 2005Lecture 1 13 Recommended Reading Stallings Chapter1 HAC Chapter1 Wagstaff Chapter1 Cristina NitaRotaru Fall 2005Lecture 1 Let s Make the Introductions Alice Carl or Eve Cristina NitaRotaru Fall 2005Lecture 1 15 Information Security NETWORK SECURITY SECURITY Cristina NitaRotaru Fall 2005Lecture 1 16 What is Security Security means different things for different protocols or applications security goals An attacker can do many things attacker model How to achieve security security mechanisms to achieve the goals How do you know that indeed the system is secure Show that under the considered attack model security goals are achieved Cristina NitaRotaru Fall 2005Lecture 1 17 Security Service Security attacks Any action that compromises the security of information Security mechanism A mechanism that is designed to detect prevent or recover from a security attack Security service A service that enhances the security of data processing systems and information transfers A security service makes use of one or more security mechanisms Cristina NitaRotaru Fall 2005Lecture 1 18 Security Services 1 Confidentiality information is available for reading only to authorized parties Example Alice sends a message to Bob only Alice and Bob can understand the content of the message 2 Authentication Data source authentication the data is coming from an authorized party Example Alice receives a message from Bob This service ensures that the message is from Bob and not from Carl Entity authentication the entity is who it says it is Example When Alice tries to obtain access to her bank account an authentication operation is performed to ensure that Alice asks for the information Cristina NitaRotaru Fall 2005Lecture 1 19 Security Services 2 3 Integrity detect if data was modified from the source to the destination Example Alice sends an email to Bob Carl intercepts the message and modifies it Data integrity allows for Bob to detect that the message was modified on the way from Alice to him 4 Nonrepudiation neitherthe sender northe receiver of a message are able to deny the transmission Example Alice sends Bob a contract signed The non repudiation service ensures that Alice can not claim that the signature was produced by somebody else Cristina NitaRotaru Fall 2005Leoture 1 20 Security Services 3 5 Access control only authorized parties can use specific resources Example Alice wants to print a document she must be authorized to get that document and to use the printer 6 Availability resources available to authorized parties Example A web site might become unavailable if the server crashes or is bombarded with requests Cristina NitaRotaru Fall 2005Lecture 1 21 Attacker Models Actions Passive the attacker does not modify the data only monitors the communication It threatens confidentiality Example listen to the communication between Alice and Bob and if it s encrypted try to decrypt it Active the attacker is actively involved in deleting adding or modifying data It threatens all security services Example Alice sends Bob a message meet me today at 5 Carl intercepts the message and modifies it meet me tomorrow at 5 and then sends it to Bob Cristina NitaRotaru Fall 2005Lecture 1 22 Attacker Models Information Access Outsider the attacker does not belong to the system and does not have access to any internal system data Insider the attacker is part of the system for example it compromised a computer thus is has access to internal information for example can have access on cryptographic keys It is more difficult to deal with insiders Cristina NitaRotaru Fall 2005Lecture 1 23 Security Attacks Examples Interruption Interception eavesdropping Cristina NitaRotaru Fall 2005Lecture 1 24 Security Attacks Examples Modification Cristina NitaRotaru Fall 2005Lecture 1 25 What is Security Security means different things for different protocols or applications security goals An attacker can do many things attacker model How to achieve security security mechanisms to achieve the goals How do you know that indeed the system is secure Show that under the considered attack model security goals are achieved Cristina NitaRotaru Fall 2005Lecture 1 26 Security Mechanisms Cristina NitaRotaru operations on the data for example encrypt data Software access limitations to in a database in operating system protect each user from other users networking firewall Hardware use smartcards for authentication Policies define who has access to what resources Physical security control who has physical access to devices storing data Cryptography protect data by performing Fall 2005Leoture 1 27 What Is Cryptography Cryptography the study of mathematical techniques related to aspects of providing information security services construct Cryptanalysis the study of mathematical techniques for attempting to defeat information security services break Cryptology the study of cryptography and cryptanalysis Cristina NitaRotaru Fall 2005Lecture 1 28 Cryptographic Primitives Encryption Key management Hash functions Digital signatures Certificates and CAs Cristina NitaRotaru Fall 2005Lecture 1 29 Symmetric and Public Cryptography Symmetric cryptography Parties that communicate share a secret Used mainly to encipherdecipher data Examples DES Blowfish AES RC4 How obtain the secret key in the first place Public cryptography Each party has a PAIR P S of keys P is the public key and S is the secret key Used mainly to distribute keys and create digital signatures Examples RSA EIGamaI P Cristina NitaRotaru Fall 2005Lecture 1 30 What is a Cryptosystem Plaintext data to be hidden or protected Ciphertext the result of applying a crypto operation on the data d plaintext IIEEXEEI ciphertext quotifgy g ciphertext Definition A cryptosystem is a fivetuple P C K E D s t P is a finite set of possible plaintexts C is a finite set of possible ciphertexts K the keyspace is the set of possible keys For each kEK there are encryption rule ek ekzP a C decryption rule dk dsz a P st dkekx x PWNT Cristina NitaRotaru Fall 2005Lecture 1 31 How Do You Know a System is Secure Security means different things for different protocols or applications security goals An attacker can do many things attacker model How to achieve security security mechanisms to achieve the goals How do you know that indeed the system is secure Show that under the considered attack model security goals are NOT achieved break it Show that under the considered attack model security goals are achieved evaluate security Cristina NitaRotaru Fall 2005Lecture 1 32 Breaking Ciphers There are different methods of breaking a cipher depending on the type of information available to the attacker the interaction with the cipher machine the computational power available to the attacker Cristina NitaRotaru Fall 2005Lecture 1 33 Breaking Ciphcrs Ciphertextonly attack The cryptanalyst knows only the ciphertext Sometimes the language of the plaintext and the cipher are also kown The goal is to find the plaintext and the key NOTE any encryption scheme vulnerable to this type of attack is considered to be completely insecure Cristina NitaRotaru Fall 2005Lecture 1 34 Breaking Ciphers 2 Knownplaintext attack The cryptanalyst knows one or several pairs of ciphertext and the corresponding plaintext The goal is to find the key used to encrypt these messages or a way to decrypt any new messages that use that key How does the cryptanalysis get the pairs of ciphertext and plaintext Cristina NitaRotaru Fall 2005Lecture 1 Breaking Ciphers 3 Chosenplaim ext attack The cryptanalyst knows a number of encrypted messages and he can also encrypt any message he chooses The goal is to deduce the key used in the other encrypted messages or decrypt any new messages using that key It can be adaptive the choice ciphertext received from previous requests Cristina NitaRotaru Fall 2005Lecture 1 36 Breaking Ciphers 4 Chosenciphertext attack Similar to the chosenplaintext attack but the cryptanalyst can choose the ciphertext not the plaintext The goal is to obtain the key It can also be adaptive The choice of ciphertext may depend on the plaintext received from previou requests Cristina NitaRotaru Fall 2005Lecture 1 37 How Do You Know a System is Secure Security means different things for different protocols or applications security goals An attacker can do many things attacker model How to achieve security security mechanisms to achieve the goals How do you know that indeed the system is secure Show that under the considered attack model security goals are NOT achieved break it Show that under the considered attack model security goals are achieved evaluate security Cristina NitaRotaru Fall 2005Lecture 1 38 Models for Evaluating Security Unconditional informationtheoretic security The adversary has unlimited computational resources Plaintext and ciphertext modeled by their distribution Analysis is made by using probability theory For encryption systems perfect secrecy observation of the ciphertext provides no information to an adversary Cristina NitaRotaru Fall 2005Lecture 1 39 Models for Evaluating Security 2 Provable security Prove security properties based on assumptions that it is difficult to solve a wellknown and supposedly difficult problem example computation of discrete logarithms factoring Cristina NitaRotaru Fall 2005Lecture 1 4O Models for Evaluating Security 3 Computational security practical security Measures the amount of computational effort required to defeat a system using the bestknown attacks Sometimes related to the hard problems but no proof of equivalence is known Cristina NitaRotaru Fall 2005Lecture 1 41 Models for Evaluating Security 4 Ad hoc security heuristic security Variety of convincing arguments that every successful attack requires more resources than the ones available to an attacker Unforeseen attacks remain a threat THIS IS NOT A PROOF Cristina NitaRotaru Fall 2005Lecture 1 42 Summary Cryptography is an important mechanism used to defend against attacks on computers and networks When designing secure systems must define secure goals attacker model and then show security goals are achieved Cristina NitaRotaru Fall 2005Lecture 1 43 Cryptography CS 555 i H 39 gt 525 quot2quotquot g i 1 i i emsrm i ra r 7 r 7 7 7 39 i 77 7 V I Lecture 10 Attacks on RSA RSA and Semantic Security Department of Computer Sciences Purdue University Cristina NitaRotaru Fall 2005Lecture 1O 1 Lecture Outline Midterm and Hw2 Project 1 g Factoring Z 3 Attacks on RSA OAEP Cristina NitaRotaru Fall 2005Lecture 1O Midterm HWl HW2 Midterm Mean 9037 8493 68 Median 92 88 645 Std Dev 607 1146 127 Cristina NitaRotaru Fall 2005Lecture 1O Project 1 SRA Poker Mental Game implementation Requires you to use openssl library go to opensslorg and get familiarized with the code You must work in pairs You have 35 weeks more information will be sent tonight Submission Turnin is now available for project 1 on mentor submit turnin c cs555 p proj1 files lookup turnin verify turnin v o for more lookup 39man turnin39 Cristina NitaRotaru Fall 2005Lecture 1O The Mental Poker Problem Alice and Bob want to play poker we need a way to deal 5 cards to each of Alice and Bob so that Alice s hand of 5 cards does not overlap with Bob s hand Neither Alice nor Bob can control which cards they each get Neither Alice nor Bob knows the other party s hand Both hands should be random provided one party follows the protocol First solution due to Shamir Rivest and Adelman in 1980 uses commutative encryption schemes Cristina NitaRotaru Fall 2005Lecture 1O Commutative Encryption Definition An encryption scheme is commutative if EK1EK2M EK2EK1M Given an encryption scheme that is commutative then DK1DK2EK1EK2M M Most symmetric encryption scheme such as DES and AES are not commutative Cristina NitaRotaru Fall 2005Lecture 1O PohligHellman Exponentiation Cipher Commutative encryption scheme PohligHellman Exponentiation Cipher with the same modulus p p prime encryption key is e decryption key is cl where edsl mod p1 Ee1M Me1 mod p and Dd1C C l1 mod p Ee1Ee2M M6162 Ee1Ee2M mOd p Cristina NitaRotaru Fall 2005Lecture 1O The SRA encryption scheme Commutative encryption Alice and Bob share npq and they both know p and q Alice has encryption key e1 and decryption key cl1 st e1d121 mod p1q1 Ee1MMe1 mod n Bob has e2 cl2 st ezdzsl mod p1q1 Also a commutative encryption scheme Essentially RSA except that e is kept private Cristina NitaRotaru Fall 2005Lecture 1O The SRA Mental Poker Protocol Setup Alice and Bob share M1 M2 M52 denote the 52 cards Alice has K1 Bob has K2 Protocol Alice encrypts M1 M2 M52 using her key ie computes CjEK1Mi for 1s s52 randomly permute them and send the ciphertexts to Bob Bob picks 5 cards as Alice s hand and sends them to Alice Alice decrypts them to get his hand Bob picks 5 other cards as his hand encrypts them using his key and sends them to Alice Alice decrypts the 5 ciphertexts and sends to Bob Bob decrypts what Alice sends and gets his hand Cristina NitaRotaru Fall 2005Lecture 1O Project 1 SRA Poker Mental Game implementation Implement PohligHellman Exponentiation Cipher Implement SRA without any networking communication make sure it works correctly Add networking Cristina NitaRotaru Fall 2005Lecture 1O 1O RSA Description Key generation Select 2 large prime numbers of about the same size p and q Compute n pq and I q1p1 Select a random integer e 1 lt e lt I st gcde 1 1 Compute d 1lt dlt I st ed 51 mod 1 Public key e n Secret key d p and q must also remain secret Cristina NitaRotaru Fall 2005Lecture 10 11 RSA Description cont Encryption Forthe message M O lt M lt n use public key e n compute C Me mod n Decryption For a message C use private key cl Compute Cd mod n Me mod nd mod n M Cristina NitaRotaru Fall 2005Lecture 10 12 Attacks on RSA Brute force key search Timing attacks Mathematical attacks Cristina NitaRotaru Fall 2005Lecture 1O Brute Force An adversary just tries all possible keys and keeps his fingers crossed that the right key is not the last key he will try worst case Cristina NitaRotaru Fall 2005Leoture 1O Timing Attacks Timing Attacks on Implementations of DiffieHeIman RSA DSS and Other Systems 1996 Paul C Kocher By measuring the time required to perform decryption exponentiation with the private key as exponent an attacker can figure out the private key Possible countermeasures use constant exponentiation time add random delays blind values used in calculations 39 Cristina NitaRotaru Fall 2005Lecture 10 15 Timing Attacks cont Is is possible in practice YES OpenSSL Security Advisory 17 March 2003 Timing based attacks on RSA keys Researchers have discovered a timing attack on RSA keys to which OpenSSL is generally vulnerable unless RSA blinding has been turned on Cristina NitaRotaru Fall 2005Lecture 10 16 MathBased Key Recovery Attacks Three possible approaches 1 Factor n pq 2 Determine CIgtn 3 Find the private key cl directly All the above are equivalent to factoring n Cristina NitaRotaru Fall 2005Lecture 10 17 Knowing In Implies Factorization Knowing both n and cIgtn one knows n m CIgtn p1q1 m p q 1 n p np 1 MW np pZ n p pZ nplt1gtnp pn0 p2nltIgtn1pn0 There are two solutions of p in the above equation Both p and q are solutions Cristina NitaRotaru Fall 2005Lecture 1O 18 Factoring Large Numbers Three most effective algorithms are quadratic sieve elliptic curve factoring algorithm numberfield sieve One idea many factoring algorithms use Suppose one find xzay2 mod n such that x y mod n and x y mod n Then n xyxy Neither xy or xy is divisible by n thus gcdxyn has a non trivial factor of n RSA576 Factored Dec 3 2003 10000 Cristina NitaRotaru Fall 2005Lecture 1O 19 Factoring When knowing e and d Fact if npq then x221 mod n has four solutions that are ltn x251 mod n if and only if both x251 mod p and x251 mod q Two trivial solutions 1 and n1 1 is solution to x a 1 mod p and x a 1 mod q n1 is solution to x a 1 mod p and x a 1 mod q Two other solutions solution to x a 1 mod p and x a 1 mod q solution to x a 1 mod p and x a 1 mod q Eg n3 515 then x251 mod 15 has the following solutions 1 4 11 14 Cristina NitaRotaru Fall 2005Lecture 1O 20 Factoring When knowing e and d Knowing a nontrivial solution to x221 mod n compute gcdx1n and gcdx1n Eg 4 and 11 are solution to x251 mod 15 gcd4115 5 gcd4115 3 gcd11115 3 gcd11115 5 Cristina NitaRotaru Fall 2005Lecture 1O 21 Factoring When knowing c and d Knowing ed such that ed a 1 mod ltIgtn write ed 1 25 r r odd choose w at random such that 1ltwltn1 ifw not relative prime to n then return gcdwn if gcdwn1 what value is w2 Sr mod n compute w W w4r until find w tr a 1 mod n Fails when we 1 mod n or w t re 1 mod n Cristina NitaRotaru Fall 2005Lecture 1O 22 Example Factoring n given 01 nput n2773e17d157 ed1266822 667 r667 Pick random w compute wr mod n w7 76671 no good w8 8667471 and 47121 so 471 is a nontrivial square root of 1 mod 2773 compute gcd4711 277359 gcd4711 277347 277359 47 Cristina NitaRotaru Fall 2005Lecture 1O 23 Decryption attacks on RSA RSA Problem Given a positive integer n that is a product of two distinct large primes p and q a positive integer e such that gcde p1q11 and an integer c find an integer m such that meac mod n widely believed that the RSA problem is computationally equivalent to integer factorization however no proof is known The security of RSA encryption s scheme depends on the hardness of the RSA problem Cristina NitaRotaru Fall 2005Lecture 1O 24 Summary of Key Recovery Math based Attacks on RSA Three possible approaches 1Factor n pq 2Determine CIgtn 3Find the private key d directly All are equivalent finding out d implies factoring n if factoring is hard so is finding out d Cristina NitaRotaru Fall 2005Lecture 1O 25 Other Attacks on RSA Forward Search Attack If message space is small the attacker can create a dictionary of encrypted messages public key known encrypt all possible messages and store them When the attacker sees a message on the network compares the encrypted messages so he finds out what particular message was encrypted Cristina NitaRotaru Fall 2005Lecture 1O 26 Semantic Security Semantically secure cryptosystems Cryptosystems in which an adversary can not in polynomial time distinguish ciphertexts Cristina NitaRotaru Fall 2005Lecture 10 27 Mallcablc Nonmalleable given a ciphertext it is computationally infeasible to generate a different ciphertext such that the corresponding plaintexts are related Non malleable systems are semantically secure Cristina NitaRotaru Fall 2005Lecture 1O 28 Semantic Security of RSA RSA is malleable RSA leaks information about the plaintext RSA not semantically secure because it is deterministic OAEP tries to solve these problems Cristina NitaRotaru Fall 2005Lecture 10 29 Quadratic Residues Module A Prime Definition a is a quadratic residue modulo p if El b EZp such that b2 E a mod p otherwise when a O a is a quadratic nonresidue 0 Q is the set of all quadratic residues p is the set of all quadratic nonresidues Cristina NitaRotaru Fall 2005Lecture 1O 30 Quadratic Residues Module A Prime Theorem If p is prime there are p12 quadratic residues in Zp lQpl p12 Theorem A element a in QIo has exactly two square roots Theorem If a IO 2 5 1 mod p p prime then a is a quadratic residue if a 1 then a is a quadratic nonresidue Cristina NitaRotaru Fall 2005Lecture 1O 31 Legendre Symbol Let p be an odd prime and a an integer The Legendre symbol is defined Oifpa 3 1 ifaEQp 1ifaE p Cristina NitaRotaru Fall 2005Lecture 1O 32 Jacobi Symbol let n 2 3 be a composite odd with prime factorization 91 62 9k n 171172 39pk the Jacobi symbol is defined to be gtfia iif the Jacobi symbol can be computed without factoring n Cristina NitaRotaru Fall 2005Lecture 1O 33 RSA Leaks the Jacobi Symbol C MOI mod n gcdd ltIgtn 1 3 Since d is odd then m w Cristina NitaRotaru Fall 2005Lecture 1O 34 Semantic Security INDCPA for Public Key Encryption The INDCPA game Challenger Adversary picks a random key pair K KI and picks random bEO 1 K 7 M0 M1 picks M0 M1 of equal length C EKMb b EOl Attacker Wins game if bb Cristina NitaRotaru Fall 2005Lecture 1O 35 Semantic Insecurity of the RSA RSA encryption is not semantically secure because it is deterministic The encryption function fxxe mod n leaks information about x l it leaks the Jacobi symbol of x so it allows an attacker to distinguish between ciphertexts X gll ltiltilltl Cristina NitaRotaru Fall 2005Leoture 1O 36 Cost of Semantic Security in Public Key Encryption In order to have semantic security some expansion is necessary ie the ciphertext must be larger than its corresponding plaintext why suppose that all plaintexts have size m what is the minimal size of ciphertexts to have an adequate level of security eg takes 2t to break the semantic security Cristina NitaRotaru Fall 2005Lecture 1O 37 A Padding Scheme for Semantically Secure Publickey Encryption Padding Scheme 1 given a publickey encryption scheme E to encrypt x generates a random r the ciphertext is y1 EKr y2 Hr x where H is a cryptographic hash function to decrypt rm one compute HDKy1 y2 requires an extra random number generation and an XOR operation for each bit Cristina NitaRotaru Fall 2005Lecture 1O 38 Example of the Padding Scheme Example of the Padding Scheme for RSA Public key ne The ciphertext for x is re mod n X Hr To decrypt a ciphertext y1 y2 compute r y1OI mod n and X y2 Hr To encrypt a 128bit message the ciphertext has 1024128 bits Cristina NitaRotaru Fall 2005Lecture 1O 39 OAEP M Belare and P Rogaway Optimal asymmetric encryption Advances in Cryptology Eurocrypt 94 Springer Verlag 1994 921 1 1 Optimal Asymmetric Encryption Padding OAEP method for encoding messages Uses one trapdoor permutation functions EK and two hash functions H 01m01t and G 01O1m To encrypt xEO1m chooses random rEO1t and computes EKx rGr r Hx Gr How to decrypt given y Cristina NitaRotaru Fall 2005Lecture 10 4O OAEP cont 0 OAEP EKX Gr r Hx Gr H 01m01t and G O1t01m OAEP is provany INDCPA secure when H and G are modeled as random oracles and EK is a trapdoor oneway permutation A ciphertext has size n z1024 for RSA The padding size t should be st 2t computing time is infeasible why t128 The plaintext size m can be up to 1024128896 Expansion is optimal Cristina NitaRotaru Fall 2005Leoture 1O 41 The Rabin Encryption Scheme Motivation The security of RSA encryption depends on the difficulty of computing the e th root modulo n ie given C it is difficult to find M st MeC mod n o It is not known that this encryption is as difficult as factoring The Rabin encryption scheme is provany secure to a passive attack if factoring is hard here secure means to recover the plaintext from a ciphertext ldea rather than using an odd prime as e uses 2 fxx2 mod n this is not a special case of RSA as this function is not 1to1 Cristina NitaRotaru Fall 2005Lecture 10 42 The Rabin Encryption Scheme Public key n Privacy key p q prime st n pq Encryption compute c m2 mod n Decryption compute the square roots of c how many are there Fact when pquB mod 4 deterministic algorithms exist to compute the square roots otherwise efficient randomized algorithms exist to compute the square roots Cristina NitaRotaru Fall 2005Lecture 10 43 Pragmatic Considerations for the Rabin Encryption Scheme Normally one picks psqs3 mod 4 Redundancy is used to ensure that only one square root is a legitimate message Encryption very fast only one exponen a on Decryption comparable to RSA decryption Cristina NitaRotaru Fall 2005Lecture 10 44 Quadratic Residues Modulo 21 Composite Definition a is a quadratic residue modulo n aEQn if El b EZn such that b2 a a mod n otherwise when a 0 a is a quadratic nonresidue Fact aEQn where npq iff aEQIo and aEQq IbeEamodn then bZEamodpand bZEamodq If b2 a a mod p and 02 a a mod q then the solutions to xsbmodpandxscmodq xsbmodpandxscmodq xsbmodpandxscmodq Ebmodpandxscmodq satisfies x2 a a mod p Cristina NitaRotaru Fall 2005Lecture 10 45 Quadratic Residues Modulo 21 Composite Qn 3p 1gtltq1gt4 Jacobi symbol does not tell whether a number a is a QR a a a n q when it is 1 then either aEQIo A aeEQCI or aeEQIo A aEQCI when it is 1 then either aEQIo A aEQq or aeEQIo A a EQq it is widely believed that determining QR modulo n is equivalent to factoring n no proof is known Cristina NitaRotaru Fall 2005Lecture 1O 46 The GoldwasserMicali Probablistic Encryption Scheme First provany semantically secure public key encryption scheme security based on the hardness of determining whether a number x is a QR modulo n when the factoring of n is unknown and the Jacobi symbol is 1 n Encryption is done bit by bit For each bit in the plaintext the ciphertext is one number in Zn expansion factor is 1024 when using 1024 moduli Cristina NitaRotaru Fall 2005Lecture 1O 47

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.