CSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerCSE 543 - Computer SecurityLecture 5 - Cryptography II September 19, 2006URL: http://www.cse.psu.edu/~tjaeger/cse543-f06/1CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerRSA (Rivest, Shamir, Adelman)•A dominant public key algorithm –The algorithm itself is conceptually simple–Why it is secure is very deep (number theory)–Use properties of exponentiation modulo a product of large primes"A method for obtaining Digital Signatures and Public Key Cryptosystems“, Communications of the ACM, Feb., 1978 21(2) pages 120-126.2CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerRSA Key Generation•Pick two large primes p and q•Calculate n = pq•Pick e such that it is relatively prime to phi(n) = (q-1)(p-1) –“Euler’s Totient Function”•d ~= e-1 mod phi(n) " " or" de mod phi(n) = 11. p=3, q=112. n = 3*11 = 333. phi(n) = (2*10) = 204. e = 7 | GCD(20,7) = 1 “Euclid’s Algorithm”5. d = 7-1 mod 20 d = 7 mod 20 = 1 d = 33CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerRSA Encryption/Decryption•Public key k+ is {e,n} and private key k- is {d,n}•Encryption and DecryptionE(k+,P) : ciphertext = plaintexte mod nD(k-,C) : plaintext = ciphertextd mod n•Example–Public key (7,33), Private Key (3,33)–Data “4” (encoding of actual data)–E({7,33},4) = 47 mod 33 = 16384 mod 33 = 16–D({3,33},16) = 163 mod 33 = 4096 mod 33 = 44CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerEncryption using private key …•Encryption and DecryptionE(k-,P) : ciphertext = plaintextd mod nD(k+,C) : plaintext = ciphertexte mod n•E.g.,–E({3,45},4) = 43 mod 33 = 64 mod 33 = 31–D({7,45},19) = 317 mod 33 = 27,512,614,111 mod 33 = 4•Q: Why encrypt with private key?5CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerApplied Cryptography•How do we use these (and other) constructs to achieve security goals?–What are the goals?6CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerMeet Alice and Bob ….•Alice and Bob are the canonical players in the cryptographic world. –They represent the end points of some interaction–Used to illustrate/define a security protocol•Other players occasionally join …–Trent - trusted third party–Mallory - malicious entity–Eve - eavesdropper–Ivan - an issuer (of some object)7CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerSome notation …•You will generally see protocols defined in terms of exchanges containing some notation like–All players are identified by their first initial •E.g., Alice=A, Bob=B–d is some data –pwA is the password for A–kAB is a symmetric key known to A and B–A+,A- is a public/private key pair for entity A–E(k,d) is encryption of data d with key k–H(d) is the hash of data d–Sig(A-,d) is the signature (using A’s private key) of data d–“+” is used to refer to concatenation8CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerSome interesting things you want to do …•… when communicating.–Ensure the authenticity of a user–Ensure the integrity of the data •Also called data authenticity–Keep data confidential–Guarantee non-repudation9CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerBasic (User) AuthenticationAliceBob•Bob wants to authenticate Alice’s identity–(is who she says she is)[pwA]1[Y/N]210CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerHash User AuthenticationAliceBob•Bob wants to authenticate Alice’s identity–(is who she says she is)[h(pwA)]1[Y/N]211CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerChallenge/Response User AuthenticationAliceBob•Bob wants to authenticate Alice’s identity–(is who she says she is)[h(c+pwA)]21[c][Y/N]312CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerUser Authentication vs. Data Integrity•User authentication proves a property about the communicating parties–E.g., I know a password•Data integrity ensures that the data transmitted...–Can be verified to be from an authenticated user–Can be verified to determine whether it has been modified•Now, lets talk about the latter, data integrity13CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerSimple Data Integrity?AliceBob•Alice wants to ensure any modification of the data in flight is detectable by Bob (integrity)[d,h(d)]114CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerHMAC IntegrityAliceBob•Alice wants to ensure any modification of the data in flight is detectable by Bob (integrity)[d,h(d+pwA)]115CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerSignature IntegrityAliceBob•Alice wants to ensure any modification of the data in flight is detectable by Bob (integrity)[d, Sig(A-,d)]116CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall 2006 - Professor JaegerData Integrity vs. Non-repudiation•If the integrity of the data is preserved, is it provably from that source?–Hash integrity says what about non-repudiation?–Signature integrity says what about non-repudiation?17CSE543 Computer (and Network) Security - Fall 2005 - Professor McDanielCSE543 Computer (and Network) Security - Fall
View Full Document