©2002-2004 Matt BishopPublic Key Cryptography and Cryptographic Hashes©2002-2004 Matt BishopSlide #9-2Public-Key Cryptography©2002-2004 Matt BishopSlide #9-3Public Key Cryptography• Two keys– Private key known only to individual– Public key available to anyone• Idea– Confidentiality: encipher using public key, decipher using private key– Integrity/authentication: encipher using private key, decipher using public one©2002-2004 Matt BishopSlide #9-4Requirements1. It must be computationally easy to encipher or decipher a message given the appropriate key2. It must be computationally infeasible to derive the private key from the public key3. It must be computationally infeasible to determine the private key from a chosen plaintext attack©2002-2004 Matt BishopSlide #9-5General Facts about Public Key Systems• Public Key Systems are much slower than Symmetric Key Systems– RSA 100 to 1000 times slower than DES– Generally used in conjunction with a symmetric system for bulk encryption• Public Key Systems are based on “hard problems– Factoring large numbers, discrete logarithms, elliptic curves• Only a handful of public key systems perform both encryption and signatures©2002-2004 Matt BishopModular Arithmetic• a mod b = x if for some y > 0 ay + x = b• Associativity, Commutativity, and Distributivity hold in Modular Arithmetic• Inverses also exist in modular arithmetic– a + (-a) mod n = 0– a * a-1mod n = 1©2002-2004 Matt BishopModular Arithmetic• Reducability also holds– (a + b) mod n = (a mod n + b mod n) mod n– a * b mod n = ((a mod n) * b mod n) mod n• Fermat’s Thm: if p is any prime integer and a is an integer, then ap= a mod p– Corollary: ap-1=1 mod p if a =/= 0©2002-2004 Matt BishopSlide #9-8Diffie-Hellman• The first public key cryptosystem proposed• Usually used for exchanging keys securely• Compute a common, shared key– Called a symmetric key exchange protocol• Based on discrete logarithm problem– Given integers n and g and prime number p, compute ksuch that n = gkmod p– Solutions known for small p– Solutions computationally infeasible as p grows large©2002-2004 Matt BishopSlide #9-9Algorithm• Constants: prime p, integer g ≠ 0, 1, or p–1– Known to all participants• Anne chooses private key kAnne, computes public key KAnne = gkAnnemod p• To communicate with Bob, Anne computes Kshared = KBobkAnnemod p• To communicate with Anne, Bob computes Kshared = KAnnekBobmod p– It can be shown these keys are equal©2002-2004 Matt BishopSlide #9-10Example• Assume p = 53 and g = 17• Alice chooses kAlice = 5– Then KAlice = 175mod 53 = 40• Bob chooses kBob = 7– Then KBob = 177mod 53 = 6• Shared key:– KBobkAlicemod p = 65mod 53 = 38– KAlicekBobmod p = 407mod 53 = 38©2002-2004 Matt BishopSlide #9-11RSA• by Rivest, Shamir& Adleman of MIT in 1977 • best known & widely used public-key scheme • based on exponentiation in a finite (Galois) field over integers modulo a prime – nb. exponentiation takes O((log n)3) operations (easy) • uses large integers (eg. 1024 bits)• security due to cost of factoring large numbers – nb. factorization takes O(elog n log log n) operations (hard)©2002-2004 Matt BishopSlide #9-12Background• Totient function φ(n)– Number of positive integers less than n and relatively prime to n• Relatively prime means with no factors in common with n• Example: φ(10) = 4– 1, 3, 7, 9 are relatively prime to 10• Example: φ(21) = 12– 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 are relatively prime to 21©2002-2004 Matt BishopBackground• Euler generalized Fermat’s Thm for composite numbers.• Euler’s Thm: xφ(n)=1 mod n©2002-2004 Matt BishopSlide #9-14Algorithm• Choose two large prime numbers p, q– Let n = pq; then φ(n) = (p–1)(q–1)– Choose e < n such that e is relatively prime to φ(n).– Compute d such that ed mod φ(n) = 1• Public key: (e, n); private key: d• Encipher: c = memod n• Decipher: m = cdmod n©2002-2004 Matt BishopSlide #9-15Example: Confidentiality• Take p = 7, q = 11, so n = 77 and φ(n) = 60• Alice chooses e = 17, making d = 53• Bob wants to send Alice secret message HELLO (07 04 11 11 14)– 0717mod 77 = 28– 0417mod 77 = 16– 1117mod 77 = 44– 1117mod 77 = 44– 1417mod 77 = 42• Bob sends 28 16 44 44 42©2002-2004 Matt BishopSlide #9-16Example• Alice receives 28 16 44 44 42• Alice uses private key, d = 53, to decrypt message:– 2853mod 77 = 07– 1653mod 77 = 04– 4453mod 77 = 11– 4453mod 77 = 11– 4253mod 77 = 14• Alice translates message to letters to read HELLO– No one else could read it, as only Alice knows her private key and that is needed for decryption©2002-2004 Matt BishopSlide #9-17Example: Integrity/Authentication• Take p = 7, q = 11, so n = 77 and φ(n) = 60• Alice chooses e = 17, making d = 53• Alice wants to send Bob message HELLO (07 04 11 1114) so Bob knows it is what Alice sent (no changes in transit, and authenticated)– 0753mod 77 = 35– 0453mod 77 = 09– 1153mod 77 = 44– 1153mod 77 = 44– 1453mod 77 = 49• Alice sends 35 09 44 44 49©2002-2004 Matt BishopSlide #9-18Example• Bob receives 35 09 44 44 49• Bob uses Alice’s public key, e = 17, n = 77, to decrypt message:– 3517mod 77 = 07– 0917mod 77 = 04– 4417mod 77 = 11– 4417mod 77 = 11– 4917mod 77 = 14• Bob translates message to letters to read HELLO– Alice sent it as only she knows her private key, so no one else could have enciphered it– If (enciphered) message’s blocks (letters) altered in transit, would not decrypt properly©2002-2004 Matt BishopSlide #9-19Example: Both• Alice wants to send Bob message HELLO both enciphered and authenticated (integrity-checked)– Alice’s keys: public (17, 77); private: 53– Bob’s keys: public: (37, 77); private: 13• Alice enciphers HELLO (07 04 11 11 14):– (0753mod 77)37mod 77 = 07– (0453mod 77)37mod 77 = 37– (1153mod 77)37mod 77 = 44– (1153mod 77)37mod 77 = 44– (1453mod 77)37mod 77 = 14• Alice sends 07 37 44 44 14©2002-2004 Matt BishopSlide #9-20Security Services• Confidentiality– Only the owner of the private key knows it, so text enciphered with public key cannot be read by anyone except the owner of the private key• Authentication– Only the owner of the private key knows it, so text enciphered with private key must have been generated by the owner©2002-2004 Matt BishopSlide #9-21More Security Services• Integrity–
View Full Document
Unlocking...