space-backspace-space

1、1Public Key CryptographyTom HortonAlfred C. WeaverCS453 Electronic Commerce2ReferencesChap. 12 of Treese and Stewart textbookWeb articles on PGP, GPG, Phil ZimmermanBruce Schneier, “Applied Cryptography,” John Wiley & SonsAndrew Tanenbaum, “Computer Networks,” Prentice-HallJim Kurose and Keith Ross,

2、 “Computer Networking,” Addison-Wesley3Overview of PKCAlso known as using asymmetric keysA pair of keys(Can think of this as one long key in two parts)One used for encryption, the other for decryptionOne publicly accessible, the other private to one personAlgorithms / SystemsRSA (Rivest, Shamir, Ade

3、lman)DSA (Digital Signature Algorithm)PGP, OpenPGP, GPG (Gnus PGP)ssh, sftpSSL4Public Key CryptographyPlaintextOriginalPlaintextEncryptionDecryptionCiphertextEncryption withReceivers Public KeyDecryption withReceivers Private Key5Mailbox AnalogyPart of the system is public yet secureMailbox with slo

4、tPublic: everyone can access it and leave infoSecure: info not accessible to anyone exceptUsefully accessing the info requires a private keyThe recipient has something personal to get to the data and read itMatches common use (shown in slide): Sending encrypted information to someoneOther ways to us

5、e this67Public Key CryptographyKey is some large number (string of bits)Key has two parts, one public, one privatePublic key is well-knownTrusted agents verify the public keyPrivate key is a secret foreverKey is arbitrarily largeEncrypt with receivers public keyDecrypt with receivers private key8Pub

6、lic Key Cryptography1. Choose two large primes, p and q2. Compute n = (p)(q)3. Compute z = (p-1)(q-1)4. Choose d such that it is relatively prime to z (no common divisor)5. Find e such that (e)(d) modulo z = 16. Public key is (e,n)7. Private key is (d,n)9Public Key Cryptography8. To encrypt plaintex

7、t message m, compute c = me mod n9. To decrypt ciphertext message c, compute m = cd mod n.10PKC Example1. Choose two (large) primes, p and qp = 3 and q = 112. Compute n = (p)(q)n = (3)(11) = 333. Compute z = (p-1)(q-1)z = (2)(10) = 204. Choose d such that it is relatively prime to z (no common divis

8、or)choose d = 7 7 and 20 have no common divisor11PKC Example5. Find e such that (e)(d) modulo z = 1find e such that 7e mod 20 = 1one solution is e = 36. Public key is (e,n)public key = (3, 33)7. Private key is (d,n)private key is (7, 33)12PKC Example8. To encrypt plaintext message m, compute c = me

9、mod nc = m3 mod 33note: require m = 128 bitspublic keys of length = 1024 bitsIf cryptography is so strong, why is this not a completely solved problem?36Key ManagementCrypto is strong so criminals, hackers, and the government go after key managementIf the keys are not secure, the communication is no

10、t secureThe threat to modern cryptography is key managementkey distributionkey revocationkey storagekey theft37Digital SignatureSenders dataHash algorithm (SHA-1, MD5)Hash code (message digest)PKC encryptionSenders private keyDigital signatureValidate with senders public keyTimestampTimestamp38Hash

11、CodeWhat makes a good hash code?Recall why we use it: the hash code is digitally signed (rather than the message itself) for computational economythe hash code is used to prove message integrityhash(P) = hash ( D ( E ( P) ) )39CharacteristicsOne-way hash function H operates on arbitrary length messa

12、ge M and returns a fixed length hash value, h=H(M)Many functions can do thatOur goals aregiven M, easy to compute hgiven h, difficult to compute M s.t. H(M)=hgiven M, hard to find M such that H(M) = H(M)40Hash Codes (Message Digests)One example scheme:01011111 . 1101001110 . 1000100001 . 0101001001

13、. 1111010100 . 1011110000 . 1110001011 . 00File for which you wish to prove integrity (M)h = 11010110 . 10 = H(M)H = exclusive-OR41DiscussionLet the hash function H() be the n-bit wide exclusive-or of the message M.Is that a good hash function?Advantages?Disadvantages?42DiscussWhat if H(M) is a 16-b

14、it wide exclusive OR?M = “I will buy your house for $1,000,000”M base 2 = 01100101 01101100 00101010 01101010 H(M) = 10010100 01010110Premise: If I use EX-OR as hash, and digitally sign the hash value, then neither you nor I can change the contract because doing so would change the hash, and thus H(

15、D(E(P) != H(P).Is that true?43Cheating with Digital Signatures1. Change $1,000,000 to $12. Hash is only 16 bits wide.3. There are only 216 hash values.4. Start generating other variations on the message that are merely cosmetic,e.g., replace space with space-backspace-space, orreplace “.” with “.”5.

16、 If this were a contract with 16 lines, making or notmaking one change on each of 16 lines would produce216 variations of the document. 6. Not all 216 hash values are necessarily presentthisjust shows that it is relatively easy to produce a large number of variants quickly and easily and automatical

17、ly!44Cheating with Digital SignaturesSo take the original document and digitally sign it.Take a version of the altered document where H(M)=H(M) and sign that one also.Present your check for $1.Go to court to enforce the digitally signed contract M where the price is $1.45LessonsLesson #1: H(M) needs

18、 to produce a lot more than 16 bits. Target 128 or 256.Lesson #2: And while were at it, lets stir the bits when computing H(M) so that hash bits are a function of more than just a single column of bits. Want each hash bit hi to be a function of many input bits (as with DES).46Real-world crypto hash

19、functionsMD5 and SHA-1 commonly usedSupported in libraries (e.g. PHP)Wikipedia:/wiki/Cryptographic_hash_function/wiki/MD5/wiki/SHA_hash_functionsBruce Schneier, “Applied Cryptography”, pages 436-441.47ToolsGnu PGPOpenSSLMore info on this laterLanguage librariesE.g. PGPCommercial vendors or groupsE.g

20、. 48Another Bit of HistoryThe Clipper ChipPromoted by the US Government from 1993-96/wiki/Clipper_chipA encryption chipTo be installed in devices doing voice transmissionSkipjack algorithm developed by NSAGovernment agency holds private keys “in escrow”If an agency “established its authority”, it co

21、uld be given the key49Threats on encryptionDistributed computing (grid computing) on the scale of the InternetQuantum computing5051Pretty Good PrivacyPGP designed by Phillip Zimmerman for electronic mail Uses three known techniques:IDEA for encrypting email messageInternational Data Exchange Algorit

22、hm block cipher with 64-bit blockssimilar in concept but different in details from DESuses 128-bit keyspatented, but free for non-commercial use52ControversiesWas released overseasZimmerman says not by himUS Government investigated him for 3 years under the Arms Export Control ActDropped in 1996Use

23、of RSA patentsPGP eventually became a companyOpen PGPUse by non-government groupsDissidents, terrorists, etc.53PGPRSA public key encryptionpermits keys up to 2,047 bits in lengthDigital signatures use MD5 as the one-way hash functionPGP generates a random 128-bit symmetric key, used by IDEA for each

24、 email messagePGP generates its own public/private key pairs Keys are stored locally using a hashed pass phrase54Hashed Pass PhraseAccess to the private key is granted by providing the “pass phrase” (not password)Should be on the order of 100 charactersIssues with a pass phrase:whats the chance of guessing a 100 character phrase? Is it 2(100*8)?55Hashed Pass PhrasePeople dont want to type 100 characters,