1Asymmetric-key EncryptionDawn [email protected]• Introduction to cryptography• Symmetric-key encryption• One-time pad• Block cipher– DES» Fiestel Networks– AES3Today• Stream ciphers• Modes of operation for Block ciphers• Administrative matters• Modular Arithmetic• 5-min break• Asymmetric-key encryption4Stream 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”5Block-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?6Examples of Block-Cipher Modes of Operation• ECB: Electronic code book• CBC: Cipher block chaining• OFB: Output feedback• CTR: Counter mode7Electronic Code Book (ECB) ModeEKP1C1 P2EKC2 P3EKC3 • 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 blocks8Cipher Block Chaining (CBC) Mode• Cj= { Pj⊕ Cj-1}K• C0= IV (initialization vector)• Issues to note– Altered ciphertext only influences two blocksEKP1C1 P2EKC2 IVP3EKC3 9Output Feedback (OFB) Mode• X1= IV (initialization vector)• Xj= { Xj-1}K• Cj= Xj+1⊕ Pj• Issues to note– Altered ciphertext only influences single blockEKX1C1 P1EKX2C2 P2EKX3C3 P310Counter Mode (CTR)• X1= IV called initialization vector• Xj= X1+ j - 1• Cj= { Xj}K⊕ Pj• Advantages– Easy to parallelize• Issues to note– Altered ciphertext only influences single blockEKX1C1 P1EKX2C2 P2EKX3C3 P311Administrative Matters (I)• New TA: Rusty Sears• Office hours on-line– M-W, F• HW1 out• Computer accounts and facility support12Administrative Matters (II)• In order to turn in HW1's programming assignment, you will need a namedUNIX 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 problems13Modular Arithmetic• a + b mod s– O(log2s)• a*b mod s– O(log2s)• abmod s– how to compute a25mod s ?– Repeated squaring» a16* a8* a1mod s – O((log2s) (log b))14Modular 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 algorithm15Euclidean Algorithm• Compute gcd (a,b)• Lemma If a > b, thengcd(a,b) = gcd (a mod b, b)– Why?• Euclid algorithm:– b≤ a,– Euclid (a,b) = Euclid (b, a mod b) if b ≠ 0or a if b = 016Extended 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(log3s)17Asymmetric-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 authentic18Advantage 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 keys19Asymmetric-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)20Asymmetric 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 unknown21Using 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
View Full Document
Unlocking...