Asymmetric key Encryption Dawn Song dawnsong cs berkeley edu 1 Review Introduction to cryptography Symmetric key encryption One time pad Block cipher DES Fiestel Networks AES 2 Today Stream ciphers Modes of operation for Block ciphers Administrative matters Modular Arithmetic 5 min break Asymmetric key encryption 3 Stream Cipher Pseudo random generator F k i ri k is secret Attacker cannot distinguish r1 r2 ri from a sequence of random numbers Encrypt using stream ciphers Alice and Bob share k Alice wishes to send n bit msg M M1 Mn Ci Mi F k i Practical one time pad 4 Block cipher Modes of Operation Block cipher has fixed block size How to encrypt arbitrary length msgs using a block cipher How to ensure the same plaintext when encrypted sent twice will result in different ciphertexts Different block cipher modes of operation Encryption scheme Randomized i e flips a coin Stateful i e depending upon state info Decryption scheme Neither randomized nor stateful Why 5 Examples of Block Cipher Modes of Operation ECB Electronic code book CBC Cipher block chaining OFB Output feedback CTR Counter mode 6 Electronic Code Book ECB Mode P2 P1 K E K P3 E C1 K E C2 C3 Disadvantages and issues to note Same plaintext always corresponds to same ciphertext Traffic analysis yields which ciphertext blocks are equal know which plaintext blocks are equal Adversary can replace blocks with other blocks 7 Cipher Block Chaining CBC Mode Cj Pj Cj 1 K C0 IV initialization vector P1 IV K P2 E K C1 Issues to note E P3 K C2 E C3 Altered ciphertext only influences two blocks 8 Output Feedback OFB Mode X1 IV initialization vector Xj Xj 1 K X1 Cj Xj 1 Pj K P1 Issues to note E C1 K P2 X2 E C2 X3 K P3 E C3 Altered ciphertext only influences single block 9 Counter Mode CTR X1 IV called initialization vector Xj X1 j 1 X1 Cj Xj K Pj K Advantages Easy to parallelize Issues to note P1 E C1 X2 K P2 E C2 X3 K P3 E C3 Altered ciphertext only influences single block 10 Administrative Matters I New TA Rusty Sears Office hours on line M W F HW1 out Computer accounts and facility support 11 Administrative Matters II In order to turn in HW1 s programming assignment you will need a named UNIX account If you do not already have one you can set it up in 273 Soda or any other instructional computer lab Log into a machine with the username newacct and password newacct You will need to provide your student ID It takes approximately one business day for new account requests to be processed Contact TAs if you have problems 12 Modular Arithmetic a b mod s O log2 s a b mod s O log2 s ab mod s how to compute a25 mod s Repeated squaring a16 a8 a1 mod s O log2 s log b 13 Modular Division How to compute 1 a mod s What does it mean ax 1 mod s Can it always be computed iff gcd a s 1 How Extended Euclidean algorithm 14 Euclidean Algorithm Compute gcd a b Lemma If a b then gcd a b gcd a mod b b Why Euclid algorithm b a Euclid a b Euclid b a mod b if b 0 or a if b 0 15 Extended Euclidean Algorithm For any positive integers a b the extended Euclidean algorithm returns integers x y such that ax by gcd a b How to use it to compute x such that ax 1 mod s gcd a s 1 thus can compute x y s t ax sy 1 Thus ax 1 mod s If u is relatively prime to s u then u has a multiplicative inverse modulo s which can be found in O log3 s 16 Asymmetric key Crypto Symmetric cryptography both parties share the same key Secret key or shared key only known to communicating parties Asymmetric cryptography each party has a public and a private key Public key known to everyone Private key only known to owner Requirements for secure communication Symmetric crypto key is secret and authentic Asymmetric crypto private key is secret and public key is authentic 17 Advantage of Public Key Crypto Consider N parties how can any pair of them establish a secret key To use symmetric key crypto requires secret and authentic channel to set up shared secret key Need O N2 keys Key management is challenging Public key crypto advantage Each party only needs to know N 1 authentic public keys 18 Asymmetric key Encryption encryption Key decryption Key Alice has public key pub key private key priv key Bob wants to send Alice message M C E pub key M M D priv key C 19 Asymmetric cryptography encryption Key decryption Key We cannot simply run operations backwards Some things are hard to reverse Often hard means not in P Cryptanalysis is always easy in NP Does P NP Multiplication Easy to multiply two large primes Hard to factor Factoring up to 663 bits 200 digits now demonstrated Intensive computing record set in May 2005 More efficient factoring methods unknown 20 Using hard problems to make crypto Gauss building on work by Fermat proved If p and q are primes and If m is not a multiple of p or q Then m p 1 q 1 1 mod pq Example p 3 q 5 pq 15 p 1 q 1 8 18 1 1 mod 15 28 256 1 mod 15 48 65536 1 mod 15 78 5764801 1 mod 15 88 16777216 1 mod 15 118 214358881 1 mod 15 138 815730721 1 mod 15 148 1475789056 1 mod 15 21
View Full Document
Unlocking...