Cryptography Public Key CryptosystemsPublic key encryptionAsymmetric (Public Key) EncryptionContributionsA revolution of sortsBasicsRequirements for Public KeyFirst of two usesSecond of two usesHow do you distribute the Public Key?DigressionComparisons – Preview *Some Misconceptions about Symmetric vs Asymmetric encryptionRSA (Rivest, Shamir, Adelman) AlgorithmRSA Important propertiesSlide 16RSA: computing e, n, and dSlide 18RSA: applying e, n, and dRSA -- getting parameters “right”Slide 21Slide 22Speeding up RSASlide 24Attacks on RSARSA security rests on factoringBreaking RSAElliptic Curve CryptographyApplicationsDigital SignatureKey DistributionPublic Key CertificateKey distribution -- using certificatesWe need a more formal way of describing these exchanges! Let’s talk about security protocols!BackupsWhy?Theory behind RSASpeeding up RSA (cont)CryptographyPublic Key CryptosystemsAnita JonesCS451 Information SecurityCopyright(C) Anita JonesSeptember, 2006 Public key encryptionThe two problems to be solved:Key distributionDigital signatureRevolutionary new approachBased on math functions, not simple operations on bit patternsAsymmetric (Public Key) EncryptionRalph Merkle, Martin Hellman, Whitfield Diffie (1977) Len Adleman Ronald Rivest Adi ShamirSeptember, 2006 ContributionsDiffie & Hellman showed that encryption with pairs of keys was possibleRivest, Shamir & Adleman created a cost-effective method, and then commercialized it which make it readily accessible to usersSeptember, 2006 A revolution of sortsDiffie & Hellman (1976) sought to solve 2 problems:better way to distribute keysprovide for a digital document signaturepublic key encryption is based on mathematical functions, not on substitution & permutationasymmetric – two different keysit does not displace block ciphers (symmetric keys)Why not? Because it costs too muchSeptember, 2006 BasicsEach user generates a pair of keysEach user places one key in a publicly accessible placeEach user keeps the other key secretEKR(M) = C EKU(C) = MWhere, M = plaintext (message); C = ciphertextKR = restricted (private) key KU = unrestricted (public) keySeptember, 2006 Requirements for Public KeyComputationally EASY togenerate a pair of keys (public KU, private KR)encrypt, given key KU & message Mdecrypt, given key KR & encrypted message, CComputationally INFEASIBLE todetermine private key KR, knowing public key KUrecover original message (M), given public key KU & ciphertext, C, for message MSeptember, 2006 First of two usesConfidentiality A wants to send message to BA encrypts message with B’s public keyA sends encrypted message to BB decrypts message with its private key(and by the way, B’s public key will not “decrypt” the encrypted message)September, 2006 Second of two usesAuthentication, or digital signature A wants to send message to B in a way that B can be assured that A (and no one else) sent itA encrypts message with A’s private key (sign!)A sends encrypted/signed message to BB decrypts message with A’s public keyB then knows thatonly A could have sent itdata integrity assured, once encrypted (if whole message is encrypted)How do you distribute the Public Key?September, 2006 DigressionWhat does the receiver know about a message once it is “correctly” decrypted?Plaintext is readable, i.e. understandableIf a “bit flipped”, then resulting plaintext is unintelligible; remember “avalanche” propertyBoth the cryptanalyst and a legitimate receiver know when they decrypt and read plaintextSeptember, 2006 Comparisons – Preview *Primary Source: Security in Computing, Pfleeger&Pfleeger, p. 75 Symmetric Asymmetric•1 2•Must be kept secret One secret; One public•Crypto “workhorse”; Key distribution, authenticationsecrecy & integrity of data–single characters to blocks of data, messages, files•Must be “out-of-band” Public key can be used to distribute other keys•Fast - based on addition, Slow; complex mathematics (e.g. masks, and shifts exponentiation); typically 10,000 times slower than symmetric keys•40, 128, 256, 512 512, 1024, 2048•DES, 3DES, AES, RSA, El Gamal, Merkle-Hellman, Blowfish, Twofish, IDEA Elliptic Curve•# of Keys•Protection of key•Best Uses•Key Distribution•Speed•Key Lengths•ExamplesSeptember, 2006 Some Misconceptions about Symmetric vs Asymmetric encryptionOne is superior to the otherPublic key encryption replaces symmetric encryptionPublic key encryption makes key distribution trivially easySeptember, 2006 RSA (Rivest, Shamir, Adelman) Algorithmplaintext and ciphertext are (considered) integers between 0 and n-1, some npublic KU = {e, n} and public KR = {d, n}for plaintext M and ciphertext C C = Me mod n M = Cd mod n = (Me)d mod n = Med mod n Why so prevalent? Because RSA Inc. commercialized itSeptember, 2006 RSA Important propertiesThere exists e, d, n such that Med = M mod n for all M < n Easy to calculate Me and Cd for all values of M < n Infeasible to determine d, given e and nSeptember, 2006 Modulo arithmetic – review a mod n is the remainder of a divided by nSo, values of a mod n are all between 0 and n-1 24 mod 7 = 3 5 mod 7 = 5a = b mod n means a mod n = b mod ni.e. give the same remaindera=b mod n means a = b + kn (k negative or positive)a and b are congruent mod n24 mod 7 = 10 mod 7 = 3, so 24 =10 = 3 mod 7September, 2006 RSA: computing e, n, and dselect 2 prime numbers p, q (p not = q)calculate n = p * q (n is the modulus)calculate ø(n) = (p-1) * (q-1)select e such that e is relatively prime to ø(n) and 1 < e < ø(n)determine d such that d * e = 1 mod ø(n)September, 2006 RSA: computing e, n, and dselect prime numbers p = 7, q = 17calculate n = p * q = 119calculate ø(n) = (p-1) * (q-1) = 6 * 16 = 96select e = 5 such that e is relative prime to ø(n) and e < ø(n)determine d = 77 such that d * e = 1 mod ø(n) and d < ø(n)5 * 77 = 385 = 4 * 96 + 1September, 2006 RSA: applying e, n, and dKU = {5, 119} and KR = {77, 119}let plaintext M = 19Encryption C = Me mod n C = EKU(19) = 195 mod 119 = 2,476,099 mod 119 = 66Decryption M = Cd mod n M = DKR(66) = 6677 mod 119 = <big number> mod 119