Transcription
Outline12CSc 466/566Computer Security347 : Cryptography — Public KeyVersion: 2012/02/15 16:15:24Department of Computer ScienceUniversity of Arizona5collberg@gmail.comCopyright c 2012 Christian CollbergChristian Collberg61/83History of Public Key ecurityDiffie-Hellman Key ExchangeDiffie-Hellman Key ion2/83Public-key AlgorithmsDefinition (Public-key Algorithms)RSA Conference 2011-Opening-Giants Among Us:Public-key cryptographic algorithms use different keys forencryption and decryption.http://www.youtube.com/watch?v mvOsb9vNIWM&feature relatedRivest, Shamir, Adleman - The RSA Algorithm Explained:http://www.youtube.com/watch?v b57zGAkNKIcBob’s public key: PBBruce Schneier - Who are Alice & Bob?:Bob’s secret key: SBhttp://www.youtube.com/watch?v BuUSi QvFLY&feature relatedAdventures of Alice & Bob - Alice Gets Lost:EPB (M) Chttp://www.youtube.com/watch?v nULAC g22So http://www.youtube.com/watch?v nJB7a79ahGMDSB (C ) MDSB (EPB (M)) MIntroduction3/83Introduction4/83
Public Key ProtocolPublic Key Encryption Protocol. . .Key-management is the main problem with symmetricalgorithms – Bob and Alice have to somehow agree on a keyto use.BobAliceIn public key cryptosystems there are two keys, a public oneused for encryption and and private one for decryption.plaintext1Alice and Bob agree on a public key cryptosystem.2Bob sends Alice his public key, or Alice gets it from a publicdatabase.3Alice encrypts her plaintext using Bob’s public key and sendsit to Bob.4Bob decrypts the message using his private key.IntroductionPB5/83Public Key Encryption: Key DistributionAliceSA , PAPA , PCPA , PBPB , PC PA , PDCarolSC , PCEvedecryptplaintextSBIntroduction6/83In practice, public key cryptosystems are not used to encryptmessages – they are simply too slow.BobSB , PBInstead, public key cryptosystems are used to encryptkeys for symmetric cryptosystems . These are calledsession keys , and are discarded once the communicationsession is over.PB , PD1Bob sends Alice his public key.2Alice generates a session key K , encrypts it with Bob’s publickey, and sends it to Bob.3Bob decrypts the message using his private key to get thesession key K .4Both Alice and Bob communicate by encrypting theirmessages using K .SD , PDAdvantages : n key pairs to communicate between n parties.Disadvantages : Ciphers (RSA,. . . ) are slow; keys are largeIntroductionciphertextA Hybrid ProtocolDavePC , PDencrypt7/83Introduction8/83
Hybrid Encryption Protocol. . .Outline12BobAlice34KencryptEPB (K )PBdecryptKSB5MencryptKEK mExampleCorrectnessSecurityDiffie-Hellman Key ExchangeDiffie-Hellman Key SA: AlgorithmBob (Key generation):Generate two large random primes p and q.Compute n pq.Select a small odd integer e relatively prime with φ(n).4 Compute φ(n) (p 1)(q 1).5 Compute d e 1 mod φ(n).123RSA is the best know public-key cryptosystem. Its security isbased on the (believed) difficulty of factoring large numbers.Plaintexts and ciphertexts are large numbers (1000s of bits).PB (e, n) is Bob’s RSA public key.SB (d, n) is Bob’ RSA private key.Encryption and decryption is done using modularexponentiation.Alice (encrypt and send a message M to Bob):12Get Bob’s public key PB (e, n).Compute C M e mod n.Bob (decrypt a message C received from Alice):1RSA11/83RSACompute M C d mod n.12/83
RSA: Algorithm NotesRSA Example: Key GenerationsHow should we choose e?It doesn’t matter for security; everybody could use the same e.It matters for performance: 3, 17, or 65537 are good choices.n is referred to as the modulus , since it’s the n of mod n.1Select two primes: p 47 and q 71.2Compute n pq 3337.3Compute φ(n) (p 1)(q 1) 3220.4Select e 79.5ComputeYou can only encrypt messages M n. Thus, to encryptlarger messages you need to break them into pieces, each n.dThrow away p, q, and φ(n) after the key generation stage. 79 1 mod 3220Encrypting and decrypting requires a single modularexponentiation. 1019RSA13/83RSA Example: Encryption126P (79, 3337) is the RSA public key.7S (1019, 3337) is the RSA private key.RSA14/83RSA Example: DecryptionEncrypt M 6882326879666683.Break up M into 3-digit blocks:m h688, 232, 687, 966, 668, 003i3 e 1 mod φ(n)1Note the padding at the end.Encrypt each block:Decrypt each block:m1 c1d mod n 15701019 mod 3337c1 m1e mod n 688 68879 mod 3337 1570We get:c h1570, 2756, 2091, 2276, 2423, 158iRSA15/83RSA16/83
In-Class Exercise: Goodrich & Tamassia R-8.18In-Class Exercise: Goodrich & Tamassia R-8.20Alice is telling Bob that he should use a pair of the form(3, n)Show the result of encrypting M 4 using the public key(e, n) (3, 77) in the RSA cryptosystem.or(16385, n)as his RSA public key if he wants people to encrypt messagesfor him from their cell phones.As usual, n pq, for two large primes, p and q.What is the justification for Alice’s advice?RSA17/83In-Class Exercise: Stallings pp. 270-271RSA18/83RSA CorrectnessWe haveC M e mod nM C d mod n.1Generate an RSA key-pair using p 17, q 11, e 7.2Encrypt M 88.3Decrypt the result from 2.To show correctness we have to show that decryption of theciphertext actually gets the plaintext back, i.e that, for allM nC d mod n (M e )d mod n M ed mod n MRSA19/83RSA20/83
RSA Correctness: Case 1RSA Correctness: Case 1. . .From the key generation step we haved e 1 mod φ(n)from which we can conclude thatM φ(n) mod n 1 follows from Euler’s theorem.ed mod φ(n) 1edTheorem (Euler) kφ(n) 1Let x be any positive integer that’s relatively prime to the integern 0, thenx φ(n) mod n 1Case 1, M is relatively prime to n:C d mod n M ed mod n M kφ(n) 1 mod n M · (M φ(n) )k mod n M · 1k mod n M mod n MRSA21/83RSA Correctness: Case 2RSA22/83RSA Correctness: Case 2. . .We have thatφ(n) φ(pq) φ(p)φ(q)By Euler’s theorem we have thatAssume that M is not relatively prime to n, i.e. M has somefactor in common with n, since M n.There are two cases:12M kφ(n) mod q M kφ(p)φ(q) mod q (M kφ(p) )φ(q) mod q 1M is relatively prime with q and M ip, orM is relatively prime with p and M iq.Thus, for some integer hWe consider only the first case, the second is similar.M kφ(n) 1 hqMultiply both sides by MM · M kφ(n) M(1 hq)M kφ(n) 1 M MhqRSA23/83RSA24/83
RSA Correctness: Case 2. . .RSA SecurityWe can now prove Case 2, for M ip:dC mod n M MedSummary:Compute n pq, p and q prime.Select a small odd integer e relatively prime with φ(n).Compute φ(n) (p 1)(q 1).4 Compute d e 1 mod φ(n).5 PB (e, n) is Bob’s RSA public key.6 SB (d, n) is Bob’ RSA private key.mod nkφ(n) 1123mod n (M Mhq) mod n (M (ip)hq) mod n (M (ih)pq) mod nSince Alice knows Bob’s PB , she knows e and n. (M (ih)n) mod nIf she can compute d from e and n, she has Bob’s private key. (M mod n) ((ih)n mod n)If she knew φ(n) (p 1)(q 1) she could computed e 1 mod φ(n) using Euclid’s algorithm. M mod n MRSAIf she could factor n, she’d get p and q!25/83Security of Cryptosystems by Failed Cryptanalysis1Propose a cryptographic scheme.2If an attack is found, patch the scheme. GOTO 2.3If enough time has passed The scheme is secure!RSA26/83RSA Security. . .If we can factor n, we can find p and q and the scheme isbroken.As far as we know, factoring is hard.How long is enough?12RSAWe need n to be large enough, 2,048 bits.It took 5 years to break the Merkle-Hellman cryptosystem.It took 10 years to break the Chor-Rivest cryptosystem.27/83RSA28/83
RSA Factoring ChallengeRSA Factoring Challenge. . . Name :RSA 576Digits :174188198812 92 0 60 7 96 3 83 8 69 7 23 9 46 1 65 0 43 9 8 07 1 63 5 63 3 79 4 17 3 82 7 00 7 63 3 56 4 22988859715 23 4 66 5 48 5 31 9 06 0 60 6 50 4 74 3 04 5 3 17 3 88 0 11 3 03 3 96 7 16 1 99 6 92 3 21 2 057340318795 50 6 56 9 96 22 1 30 5 16 87 5 93 0 76 5 02 57 0 59 The factoring research team of F. Bahr, M. Boehm, J. Franke,T. Kleinjung continued its productivity with a successfulfactorization of the challenge number RSA-640, reported onNovember 2, 2005.The factors are:On December 3, 2003, a team of researchers in Germany andseveral other countries reported a successful factorization ofthe challenge number RSA-576.The factors are 1900871281 66 4 82 2 11 3 12 6 85 15 7 39 3 54 1 39 7 54 7 18 9 67 8 99 685154936666 38 5 39 0 88 0 27 10 3 80 2 10 4 49 8 95 7 19 1 26 14 6 55 7 147277214610 7 43 5 30 2 53 6 22 30 7 19 7 30 4 82 24 6 32 9 14 6 9530209711645 9 85 2 17 11 3 05 2 07 11 2 56 3 63 5 90 39 7 52 7 RSARSA Factoring Challenge. . .RSA Name :RSA 1536Digits :463184769970 32 1 17 4 14 7 43 0 68 3 56 2 0 20 0 16 4 40 3 01 8 54 9 33 8 66 3 4 1 0 1 71 4 71 7 85 7 74 9 10 6 5 1696711161 24 9 85 9 33 7 68 4 30 5 43 5 7 44 5 85 6 16 0 61 5 44 5 71 7 94 0 5 2 2 2 97 1 77 3 25 2 46 6 09 6 0 6469460712 49 6 23 7 20 4 42 0 22 2 69 7 5 67 5 66 8 73 7 84 2 75 6 23 8 95 0 8 7 6 4 67 8 44 0 93 3 28 5 15 7 4 9657884341 50 8 84 7 55 2 82 9 81 8 67 2 6 45 1 33 9 86 3 36 4 93 1 90 8 08 4 6 7 1 9 90 4 31 8 74 3 81 2 83 3 6 3502795470 28 2 65 3 29 7 80 2 93 4 91 6 1 55 8 11 8 81 0 49 8 44 9 08 3 19 5 4 5 0 0 98 4 83 9 37 7 52 2 72 5 7 0525785919 44 9 93 8 70 0 73 6 95 7 55 6 8 84 3 69 3 38 1 27 7 96 1 30 8 92 3 0 3 9 2 56 9 69 5 25 3 26 1 62 0 8 23676490316 03 6 55 1 37 14 4 79 1 39 3 23 47 1 69 5 66 9 88 06 9Name :RSA 768Digits :232123018668 45 3 01 1 77 5 51 3 04 9 49 5 8 38 4 96 2 72 0 77 2 85 3 56 9 59 5 33 4 7 92 1 97 3 22 4 52 1 51 7 2640050726 36 5 75 1 87 4 52 0 21 9 97 8 6 46 9 38 9 95 6 47 4 94 2 77 4 06 3 84 5 9 25 1 92 5 57 3 26 3 03 4 5373154826 85 0 79 1 70 2 61 2 21 4 29 1 3 46 1 67 0 42 9 21 4 31 1 60 2 22 1 2 4 0 4 79 2 74 7 37 7 94 0 80 6 6 5351419597459 85 69 0 21 43 41 3Name :RSA 2048Digits :617251959084 75 6 57 8 93 4 94 0 27 1 83 2 4 00 4 83 9 85 7 14 2 92 8 21 2 62 0 4 0 3 2 02 7 77 7 13 7 83 6 04 3 6 6202070759 55 5 62 6 40 1 85 2 58 8 07 8 4 40 6 91 8 29 0 64 1 24 9 51 5 08 2 1 8 9 2 98 5 59 1 49 1 76 1 84 5 0 2808489120 07 2 84 4 99 2 68 7 39 2 80 7 2 87 7 76 7 35 9 71 4 18 3 47 2 70 2 6 1 8 9 63 7 50 1 49 7 18 2 46 9 1 1650776133 79 8 59 0 95 7 00 0 97 3 30 4 5 97 4 88 0 84 2 84 0 17 9 74 2 91 0 0 6 4 2 45 8 69 1 81 7 19 5 11 8 7 4612151517 26 5 46 3 22 8 22 1 68 6 99 8 7 54 9 18 2 42 2 43 3 63 7 25 9 08 5 1 4 1 8 65 4 62 0 43 5 76 7 98 4 2 3387184774 44 7 92 0 73 9 93 4 23 6 58 4 8 23 8 24 2 81 1 98 1 63 8 15 0 10 6 7 4 8 1 04 5 16 6 03 7 73 0 60 5 6 2016196762 56 1 33 8 44 1 43 6 03 8 33 9 0 44 1 49 5 26 3 44 3 21 9 01 1 46 5 7 5 4 4 45 4 17 8 42 4 02 0 92 4 6 1651572335 07 7 87 0 77 4 98 1 71 2 57 7 2 46 7 96 2 92 6 38 6 35 6 37 3 28 9 9 1 2 1 54 8 31 4 38 1 67 8 99 8 8 50404453640 2 35 2 73 8 19 5 13 7 86 3 65 6 43 9 12 1 20 1 03 9 71 2 28 2 21 2 0 7 2 03 5 7Name :RSA 896Digits :270412023436 98 6 65 9 54 3 85 5 53 1 36 5 3 32 5 75 9 48 1 79 8 11 6 99 8 44 3 2 7 9 8 28 4 54 5 56 2 64 3 38 7 6 4455652484 26 1 98 0 98 8 70 4 23 1 61 8 4 18 7 92 6 14 2 02 4 71 8 88 6 94 9 2 5 6 0 93 1 77 6 37 5 03 3 42 1 1 3098239748 51 5 09 4 49 0 91 0 69 1 02 6 9 86 1 03 1 86 2 70 4 11 4 88 0 86 6 9 7 0 5 64 9 02 9 03 6 53 6 58 8 6 74337317208 1 31 0 41 0 51 9 08 6 4 25 4 79 3 28 2 60 1 39 1 25 7 62 4 03 3 94 6 37 3 26 9 39 1Name :RSA 1024Digits :309135066410 86 5 99 5 22 3 34 9 60 3 21 6 2 78 8 05 9 69 9 38 8 81 4 75 6 05 6 6 7 0 2 75 2 44 8 51 4 38 5 15 2 6 5106048595 33 8 33 9 40 2 87 1 50 5 71 9 0 94 4 17 9 82 0 72 8 21 6 44 7 15 5 1 3 7 3 68 0 41 9 70 3 96 4 19 1 7 4304649658 92 7 42 5 62 3 93 4 10 2 08 6 4 38 3 20 2 11 0 37 2 95 8 72 5 76 2 3 5 8 5 09 6 43 1 10 5 64 0 73 5 0 1508187510 67 6 59 4 62 9 20 5 56 3 68 5 5 29 4 75 2 13 5 00 8 52 8 79 4 16 3 7 7 3 2 85 3 39 0 61 0 97 5 05 4 4 334999811150 05 69 7 72 36 8 90 92 75 6 3RSA30/83RSA Factoring Challenge. . .Name :RSA 704Digits :212740375634 79 5 61 7 12 8 28 0 46 7 96 0 97 4 29 5 7 31 4 25 9 31 8 88 8 92 3 12 8 90 8 49 3 62 3 2 63 8 97276503402 82 6 62 7 68 9 19 9 64 1 96 2 51 1 78 4 3 99 5 89 4 33 0 50 2 12 7 58 5 37 0 11 8 96 8 0 98 2 86733173273 10 8 93 0 90 0 5 52 5 05 1 16 8 77 0 6 32 9 90 7 23 9 63 8 07 8 6 71 0 08 6 09 6 96 2 5 37 9 34 6 50 5 63 7 96 3 5 9 The effort took approximately 30 2.2GHz-Opteron-CPU yearsaccording to the submitters, over five months of calendar time.29/83 1634733645 80 9 25 3 84 8 44 3 13 3 88 3 86 50 9 08 5 98 4 17 8 36 7 00 3 309231218111 08 5 23 8 93 3 31 00 1 04 5 08 1 51 2 12 11 8 16 7 51 1 57 939807508642 4 06 4 93 7 39 7 12 55 0 05 5 03 8 64 91 1 99 0 64 3 6234252670840 6 38 5 18 95 7 59 4 63 88 9 57 2 61 7 68 58 3 31 7 Name :RSA 640Digits :193310741824 04 9 00 4 37 2 13 5 07 5 00 3 58 8 85 6 79 3 0 03 7 34 6 02 2 84 2 72 7 54 5 72 0 16 1 94 8 82320644051 80 8 15 0 45 5 63 4 68 2 96 7 17 2 32 8 67 8 2 43 7 91 6 27 2 83 8 03 3 41 5 47 1 07 3 10 8 501919548529 0 07 3 37 7 2 48 2 27 8 35 2 57 4 23 8 64 5 40 1 46 9 17 3 66 0 24 7 76 5 23 4 66 0 9http://www.rsa.com/rsalabs/node.asp?id 2093 31/83RSA32/83
RSA Security: How to use RSAOutline12Two plaintexts M1 and M2 are encrypted into ciphertexts C1and C2 .3But, RSA is deterministic!4If C1 C2 then we know that M1 M2 !Also, side-channel attacks are possible against RSA, forexample by measuring the time taken to encrypt.56RSA33/83Software – ffie-Hellman Key ExchangeDiffie-Hellman Key ey generation: Bob gpg --gen-keygpg is a public domain implementation of pgp.Please select what kind of key you want:(1) RSA and RSA (default)(2) DSA and Elgamal(3) DSA (sign only)(4) RSA (sign only)Your selection? 1What keysize do you want? (2048)Key is valid for? (0)Key does not expire at allReal name: BobbyEmail address: bobby@gmail.comComment: recipientYou need a Passphrase to protect your secret key.Enter passphrase: Bob rocksRepeat passphrase: Bob rocksSupported algorithms:Pubkey: RSA, RSA-E, RSA-S, ELG-E, DSACipher: 3DES, CAST5, BLOWFISH, AES, AES192,AES256, TWOFISH, CAMELLIA128,CAMELLIA192, CAMELLIA256Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384,SHA512, SHA224Compression: Uncompressed, ZIP, ZLIB, BZIP2http://www.gnupg.orgGPG.35/83GPG36/83
Key generation: AliceExporting the Key gpg --gen-keyPlease select what kind of key you want:(1) RSA and RSA (default)(2) DSA and Elgamal(3) DSA (sign only)(4) RSA (sign only)Your selection? 1What keysize do you want? (2048)Key is valid for? (0)Key does not expire at allReal name: AliceEmail address: alice@gmail.comComment: senderYou need a Passphrase to protect your secret key.Enter passphrase: Alice is cuteRepeat passphrase: Alice is cuteGPG gpg --armor --export Bobby-----BEGIN GPG PUBLIC KEY BLOCK----Version: GnuPG v1.4.11 t9j1kVnDPLCrongyRdSko0AwG7OYAyHWa7/USeGwjZ UaBA FZ78-----END GPG PUBLIC KEY BLOCK-----37/83EncryptionGPG38/83DecryptionWe can encrypt a message using Bobby’s key: cat messageAttack at dawn gpg --recipient bobby --armor --encrypt message cat message.asc-----BEGIN PGP MESSAGE----Version: GnuPG v1.4.11 (Darwin)Bobby can now decrypt the message using his private key: gpg --decrypt message.ascYou need a passphrase to unlock the secret key foruser: "Bobby (recipient) bobby@gmail.com "2048-bit RSA key, ID D95291EF, created 2012-02-12(main key ID g7FcrIqx gXVVUXNN86tZtERF42elwU6QwamDzfcOHqp 3zeor4Y5xN kCtgT7TdtrK3fTa8UN CYQvU2QRnaNtFhYwBMonFqhefNzDqeZb jxjSY7ZeIR2uwxdLYydtW4m B JA-----END PGP MESSAGE----GPGEnter passphrase: Bob rocksgpg: encrypted with 2048-bit RSA key, ID D95291EF, created 2012-02-12"Bobby (recipient) bobby@gmail.com "Attack at dawn39/83GPG40/83
The keyringThe keyring. . . gpg ----------------------------pub2048R/9974031B 2012-02-12uidBobby (recipient) bobby@gmail.com sub2048R/D95291EF 2012-02-12 gpg 1B 2012-02-12uidBobby (recipient) bobby@gmail.com ssb2048R/D95291EF 2012-02-12pubuidsubsecuidssb2048R/4EC8A0CB 2012-02-12Alice (sender) alice@gmail.com 2048R/B901E082 2012-02-12GPG41/83Sign and Encrypt2048R/4EC8A0CB 2012-02-12Alice (sender) alice@gmail.com 2048R/B901E082 2012-02-12GPG42/83Check Signature and DecryptBob can sign his message before sending it to Alice:Alice can now decrypt the message and check the signature: gpg -se --recipient alice --armor message gpg --decrypt message.ascYou need a passphrase to unlock the secret key foruser: "Bobby (recipient) bobby@gmail.com "2048-bit RSA key, ID 9974031B, created 2012-02-12You need a passphrase to unlock the secret key foruser: "Alice (sender) alice@gmail.com "2048-bit RSA key, ID B901E082,created 2012-02-12 (main key ID 4EC8A0CB)Enter passphrase: Bob rocksEnter passphrase: Alice is cute cat message.asc-----BEGIN PGP MESSAGE----Version: GnuPG v1.4.11 (Darwin)GPGhQEMA7osp1S5AeCCAQgAsSqSs 46oQpIgPbcdYZqIt8e/8wPU6xlMZUStzxBKLB Rj/Zg35ZVioYL oiv8-----END PGP MESSAGE-----gpg: encrypted with 2048-bit RSA key, ID B901E082, created 2012-02-12"Alice (sender) alice@gmail.com "Attack at dawngpg: Signature made Sat Feb 11 23:10:59 2012 MSTusing RSA key ID 9974031Bgpg: Good signature from "Bobby (recipient) bobby@gmail.com "43/83GPG44/83
Symmetric Encryption OnlyDeleting Keys gpg --cipher-algo AES --armor --symmetric messageEnter passphrase: sultanaRepeat passphrase: sultana cat message.asc-----BEGIN PGP MESSAGE----Version: GnuPG v1.4.11 (Darwin) gpg --delete-secret-keys bobbysec 2048R/9974031B 2012-02-12 Bobby (recipient) bobby@gmail.com Delete this key from the keyring? (y/N) yThis is a secret key! - really delete? (y/N) bsyohrOXeQLFlcfwtWcg dZvlMS6D7OE3wZCeW2LX50kYcU17MUc8wnJLDAzAdRqPAgDma sP4 UtI4-----END PGP MESSAGE----- gpg --delete-keys bobbypub 2048R/9974031B 2012-02-12 Bobby (recipient) bobby@gmail.com gpg message.ascgpg: AES encrypted dataEnter passphrase: sultanagpg: encrypted with 1 passphraseDelete this key from the keyring? (y/N) y cat messageAttack at dawnGPG45/83Generating PrimesGPG46/83Generating Random NumbersGenerate a prime number of the given number of bits:Generate 100 (base64 encoded) random bytes: gpg --gen-prime 1 16C4B7 gpg --gen-prime 1 DCBC607AC5GPG gpg --armour --gen-random 0 100e0zAVl6jbe/Dma9VF20lMgZxE1RA4S8TwNwu6KP8 zJuSur5sKC8omfPus2QtYJJNOgVbpJ7X9L4t1iNJtnw 47/83GPG48/83
Print Message DigestsGoal: Read a message encrypted with gpg gpg --print-mds messageMD5 36 D1 A5 12 17 CD 34 FC 04 F5 6C C4 91 39 C7 59SHA1 6DA4 473A 00CE 7AB6 7B6F 884D 1E75 6633 C21A 56DBRMD160 D1DE 4194 C0CD 3AED 30F3 38CD 68F3 800F CCF0 3B87SHA224 B4E94780 1AA1A9C3 418F72D8 651BA995 83284003EBEE183A 589702EESHA256 B83EF405 07696578 9D4BBDA7 D7932700 5F2AE6CBA2696FDE 69694D12 AFE70E4ASHA384 7AC39A0C 945844F1 1316BB46 C9FC7EEA E892A1782D20E4CA E7BE686C 1A091C8C F1BBDFD1 3D42BEA288AF5A4F E3705474SHA512 9CA1EB88 F064CB0D 536254B2 5755919F 4556427696CA27A0 389E4817 53F81DC2 3222488D 7D11F3DDC066B9E8 027F3870 395A2561 157DDC38 BD679D37C2E361CCGPGDecrypt the message itself (OR)2Determine symmetric key used to encrypt the message byother means (OR)3Get recipient to help decrypt message (OR)4Obtain private key of s-fig7.html49/83Goal: Read a message encrypted with gpg. . .GPG50/83Goal: Read a message encrypted with gpg. . .Determine symmetric key by other means:1 Fool sender into encrypting message using public key whoseprivate key is known (OR)Decrypt the message itself:1 Break asymmetric encryption (OR)121Convince sender that fake key (with known private key) is thekey of the intended recipient2 Convince sender to encrypt with more than one key—the realkey of the recipient and a key whose private key is known.3 Have the message encrypted with a different public key in thebackground, unbeknownst to the sender.1Brute force break asymmetric encryption (OR)Mathematically break asymmetric encryption (OR)1 Break RSA (OR)2 Factor RSA modulus/calculate Elgamal discrete log3Cryptanalyze asymmetric encryption (OR)1 General cryptanalysis of RSA/Elgamal (OR)2 Exploit weakness in RSA/Elgamal (OR)3 Timing attack on RSA/Elgamal2234Break symmetric-key encryption5Brute force break symmetric-key encryption2 Cryptanalysis of symmetric-key encryption1Determine state of randseed during encryption (OR)Implant virus that alters the state of randseed. (OR)3 Implant software that affects the choice of symmetric key.126GPGHave the recipient sign the encrypted publc key (OR)Monitor the sender’s computer memory (OR)Monitor the receiver’s computer memory (OR)Determine key from pseudo-random number generator (OR)51/83GPGImplant virus that that exposes public key.52/83
Goal: Read a message encrypted with gpg. . .Goal: Read a message encrypted with gpg. . .Get recipient to help decrypt message:GPGObtain private key of recipient:53/83Goal: Read a message encrypted with PGPGPGGoal: Read a message encrypted with PGP. . .What immediately becomes apparent from the attacktree is that breaking the RSA or IDEA encryptionalgorithms are not the most profitable attacks againstPGP. There are many ways to read someone’sPGP-encrypted messages without breaking thecryptography. You can capture their screen when theydecrypt and read the messages (using a Trojan horse likeBack Orifice, a TEMPEST receiver, or a secret camera),grab their private key after they enter a passphrase (BackOrifice again, or a dedicated computer virus), recovertheir passphrase (a keyboard sniffer, TEMPEST receiver,or Back Orifice), or simply try to brute force theirpassphrase (I can assure you that it will have much lessentropy than the 128-bit IDEA keys that it generates).GPG54/83In the scheme of things, the choice of algorithm and thekey length is probably the least important thing thataffects PGP’s overall security. PGP not only has to besecure, but it has to be used in an environment thatleverages that security without creating any cktrees-fig7.html55/83GPG56/83
ectnessSecurityDiffie-Hellman Key ExchangeDiffie-Hellman Key ExchangeExampleCorrectnessSecuritySummaryThe Elgamal cryptosystem relies on the inherent difficulty ofcalculating discrete logarithms.It is a probabilistic scheme:a particular plaintext can be encrypted into multiple differentciphertexts; ciphertexts become twice the length of the plaintext.Elgamal57/83Elgamal: AlgorithmElgamal58/83Elgamal: Algorithm NotesBob (Key generation):Pick a prime p.Find a generator g for Zp .3 Pick a random number x between 1 and p 2.4 Compute y g x mod p.PB (p, g , y ) is Bob’s RSA public key.SB x is Bob’ RSA private key.12Alice must choose a different random number k for everymessage, or she’ll leak information.Bob doesn’t need to know the random value k to decrypt.Each message has p 1 possible different encryptions.Alice (encrypt and send a message M to Bob):The division in the decryption can be avoided by use ofLagrange’s theorem :Get Bob’s public key PB (p, g , y ).2 Pick a random number k between 1 and p 2.3 Compute the ciphertext C (a, b):1ab M b · (ax ) 1 mod pg k mod pMy k mod p b · ap 1 x mod pBob (decrypt a message C (a, b) received from Alice):1ElgamalCompute M b(ax ) 1 mod p.59/83Elgamal60/83
Elgamal: Finding the generatorElgamal Example: Key generationComputing the generator is, in general, hard.1Pick a prime p 13.We can make it easier by choosing a prime number with theproperty that we can factor p 1.2Find a generator g 2 for Z13 (see next slide).3Pick a random number x 7.Then we can test that, for each prime factor pi of p 1:4Computey g x mod p 27 mod 13 11.g (p 1)/pi mod p 6 1If g is not a generator, then one of these powers will 6 1.Elgamal61/83Powers of Integers, Modulo 348765910212PB (p, g , y ) (13, 2, 11) is Bob’s public key.6SB x 7 is Bob’ private key.Elgamal62/83Elgamal Example: Encryption2 is a primitive root modulo 13 because for each integeri Z13 {1, 2, 3, . . . , 12} there’s an integer k, such thati 2k mod 12a101103912441293101a11179108112534612Encrypt the plaintext message M 3.Alice gets Bob’s public key PB (p, g , y ) (13, 2, 11).To encrypt:a1211111111111112Pick a random number k 5:Compute:ab g k mod p 25 mod 13 6My k mod p 3 · 115 mod 13 8The ciphertext C (a, b) (6, 8).63/83Elgamal64/83
Elgamal Example: DecryptionIn-Class ExerciseBob’s private key is SB x 7.Pick the prime p 13.Bob receives the ciphertext C (a, b) (6, 8) from Alice.Find the generator g 2 for Z13 .Bob computes the plaintext M:Pick a random number x 9.ComputeM b · (ax ) 1 mod py g x mod p 29 mod 13 5 b · ap 1 x mod pPB (p, g , y ) (13, 2, 5) is Bob’s public key. 8 · 613 1 7 mod 13SB x 9 is Bob’ private key. 8 · 65 mod 13 3Elgamal65/83Elgamal Correctness1Encrypt the message M 11 using the random numberk 10.2Decrypt the ciphertext from 1.Elgamal66/83Elgamal SecurityShow that M b · (ax ) 1 mod p decrypts.We have thata g k mod pb My k mod py g x mod pThe security of the scheme depends on the hardness of solvingthe discrete logarithm problem.We getGenerally believed to be hard.b · (ax ) 1 mod p (My k ) · ((g k )x ) 1 mod p (My k ) · (g kx ) 1 mod p (M((g x )k ) · (g kx ) 1 mod p Mg kx · (g kx ) 1 mod p Mg kx · g kx mod p M mod pElgamal M67/83Elgamal68/83
Outline123456Key ityDiffie-Hellman Key ExchangeDiffie-Hellman Key llman Key ExchangeA key exchange protocol (or key agreement protocol ) is away for parties to share a secret (such as a symmetric key)over an insecure channel.With an active adversary (who can modify messages) wecan’t reliably share a secret.With a passive adversary (who can only eavesdrop onmessages) we can share a secret.A passive adversary is said to be honest but curious .69/83Diffie-Hellman Key ExchangeDiffie-Hellman Key ExchangeDiffie-Hellman: Algorithm1All parties (set-up):1222Pick a random x Zp , x 0.ComputeX g x mod p.3Send X to Bob.Based on modular exponentiation .The secret K1 K2 shared by Alice and Bob at the end of theprotocol would typically be a shared symmetric key.34571/83Pick p, a prime number.Pick g , a generator for Zp .Alice :1A classic key exchange protocol.Diffie-Hellman Key Exchange70/83Bob :12Pick a random y Zp , x 0.ComputeY g y mod p.3Send Y to AliceAlice computes the secret: K1 Y x mod p.Bob computes the secret: K2 X y mod p.Diffie-Hellman Key Exchange72/83
ExampleIn-Class Exercise1Pick p 13, a prime number.2Pick g 2, a generator for Z13 .Alice :3Let p 19.Let g 10.Pick a random x 3.2 Compute X g x mod p 23 mod 13 8.14Let Bob’s secret y 15.Bob :125Let Alice’s secret x 7.Pick a random y 7.Compute Y g y mod p 27 mod 13 11.Alice computes: K1 6Bob computes: K2 7 K1 K2 5.YxXymod p mod p 11387mod 13 5.1Compute K1 .2Compute K2 .mod 13 5.Diffie-Hellman Key Exchange73/83Diffie-Hellman CorrectnessDiffie-Hellman Key Exchange74/83Diffie-Hellman Correctness. . .Alice hasAlice has computedK1 Y x mod pX (g y )x mod p g x mod p (g x )y mod pK1 Y x mod p. X y mod pBob has computedYBob has g y mod pK2 X y mod pK2 X y mod p. (g x )y mod p X y mod p K1 K2 .Diffie-Hellman Key Exchange75/83Diffie-Hellman Key Exchange76/83
Diffie-Hellman SecurityDiffie-Hellman: Man-In-The-Middle attack1The security of the scheme depends on the hardness of solvingthe discrete logarithm problem.Alice :12Eve :Intercept X g x mod p from Alice.Pick a number t in Zp .3 Send T g t mod p to Bob.Generally believed to be hard.Diffie-Hellman Property :12Givenp, X g x , Y g y3Bob :1computing4K g xy mod pSend Y g y mod p to AliceEve :Intercept Y g y mod p from Bob.Pick a number s in Zp .3 Send S g s mod p to Alice.12is thought to be hard.Diffie-Hellman Key ExchangeSend X g X mod p to Bob.77/83Diffie-Hellman: Man-In-The-Middle attack. . .Diffie-Hellman Key Exchange78/83Diffie-Hellman: Man-In-The-Middle attack. . .78Alice : Send C EK1 (M) to BobEve :Intercept C .Decrypt:M DK1 (C )Re-encrypt:C ′ EK2 (M)4 Send C ′ to Bob15Alice and Eve :1623Compute K1 g xS mod pBob and Eve :1Compute K2 g yT mod p910Bob : Send C EK2 (M) to AliceEve :Intercept C .Decrypt:M DK2 (C )3 Re-encrypt:C ′ EK1 (M)4 Send C ′ to A
You can only encrypt messages M n. Thus, to encrypt larger messages you need to break them into pieces, each n. Throw away p, q, and φ(n) after the key generation stage. Encrypting and decrypting requires a single modular exponentiation. RSA 13/83 RSA Example: Key Generations 1 Select two primes: p 47 and q 71. 2 Compute n pq 3337.
