DOC PREVIEW
USC CSCI 530 - 03a_pubkey

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSCI 530, Spring 2010 Copyright © William C. Cheng T1CS530Public KeyCryptographyBill Chenghttp://merlot.usc.edu/cs530-s10CSCI 530, Spring 2010 Copyright © William C. Cheng T2Public Key Cryptographyunique factorizationfor any integers b, n, y: Find x such that bx mod n = yaka asymmetric cryptographyBased on some NP-complete problemdiscrete logarithmstraveling salesman problemn cities, connectedfind shortest tour, all cities must be visitedsolution complexity is n!modular arithmetic produces foldingfactor an integer into product of prime numbers (uniquesolution)CSCI 530, Spring 2010 Copyright © William C. Cheng T3A Short Note on Primesabout 1 in 1/ln(p)about 1 in 355 2 numbers ≈ 2 1024 is product of twoprimes (and therefore valid RSA modulo)Why are public keys (and private keys) so large?What is the probability that some large number p is prime?when p ≈ 2 512 (≈ 10 150), equals about 1 in 3552 digit numbers: 25 primes (1 in 4)10 digit numbers: 1 in 23 are primes100 digit numbers: 1 in 230 are primesbut... the more digits, the more primes!because key space is sparseCSCI 530, Spring 2010 Copyright © William C. Cheng T4RSAlet n = pqRivest, Shamir, AdlemanGenerate two primes: p, qchoose e, a small number, relatively prime to (p-1)(q-1)choose d (< n) such that ed ≡ 1 mod (p-1)(q-1)Then, c = m e mod n and m = c d mod nNote: encryption is fast (because e is small) and decryptionis slowRSA public-key is <e, n> (e is called the public exponent)RSA private-key is <d, n> (d is called the private exponent)can also encrypt with d and decrypt with ei.e., c = m d mod n and m = c e mod nn is called the public moduluspick e = 3 (recall that e is relatively prime to (p-1)(q-1)) CSCI 530, Spring 2010 Copyright © William C. Cheng T5An Examplethen n = 55 (recall that n = pq)Let p = 5, q = 11, e = 3 (recall that p & q are primes)d = 27, since (3)(27) mod 40 = 1(recall that ed ≡ 1 mod (p-1)(q-1))If m = 7, then c = 7 3 mod 55 = 343 mod 55 = 13Then m should be = 13 27 mod 5513 1 mod 55 = 13, 13 2 mod 55 = 4, 13 4 mod 55 = 16,13 8 mod 55 = 36, 13 16 mod 55 = 31Computing 13 27 mod 5527 = 1+2+8+1613 27 mod 55 = (13)(4)(36)(31) mod 55 =(1872 mod 55)(31) mod 55 = 62 mod 55 = 7 (check)ed ≡ 1 mod (p-1)(q-1) CSCI 530, Spring 2010 Copyright © William C. Cheng T6Calculating the Private Exponentd is the multiplicative inverse of e modulo (p-1)(q-1)multiplicative inverse of e is like the reciprocal of e sincee ⋅ (1/e) = 1let a be an integer such that a < n has a multiplicativeinverse modulo n only if gcd(a,n)=1a has a multiplicative inverse modulo n if and only ifgcd(a,n)=1use the Extended Euclidean AlgorithmHow to compute multiplicative inverses?2 ⋅ 153 + 1191 ⋅ 119 + 343 ⋅ 34 + 172 ⋅ 17 + 0Input: two non-negative integers a and b with a ≥ bOutput: gcd(a,b)while b > 0 do:1)r ← a mod b, a ← b, b ← r1.1)return (a)2)Ex: a = 425, b = 153, gcd(a,b) = 17r-11934170a4251531193417b1531193417042515311934====q-2132 CSCI 530, Spring 2010 Copyright © William C. Cheng T7Euclidean Algorithma4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-2132if b = 0 then set d ← a0, x ← 1, y ← 0, and return (d,x,y)Input: two non-negative integers a0 and b0 with a0 ≥ b0Output: d = gcd(a0,b0) and integers x, y satisfying a0x + b0y = d1)set a ← a0, b ← b0, x2 ← 1, x1 ← 0, y2 ← 0, y1 ← 12)while b > 0 do:3)q ← a/b, r ← a - qb, x ← x2 - qx1, y ← y2 - qy13.1)a ← b, b ← r, x2 ← x1, x1 ← x, y2 ← y1, y1 ← y3.2)set d ← a, x ← x2, y ← y2, and return (d,x,y)4)Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17end of each iteration: a0x2 + b0y2 = a CSCI 530, Spring 2010 Copyright © William C. Cheng T8Extended Euclidean Algorithm [HAC 2.4]A simple way to implement the Extended Euclidean Algorithmhttp://en.wikipedia.org/wiki/Extended_Euclidean_algorithmrem[1] = a0;rem[2] = b0;x[1] = 0;x[2] = 1;y[1] = 1;y[2] = 0; for (i=3; rem[i] > 1; i++) { rem[i] = rem[i-2] % rem[i-1]; quo[i] = rem[i-2] / rem[i-1]; x[i] = -quo[i] * x[i-1] + x[i-2]; y[i] = -quo[i] * y[i-1] + y[i-2]; /* optional */}inverse = x[i]; CSCI 530, Spring 2010 Copyright © William C. Cheng T9The Table Methodrem yxquoa4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-21324251531001--Table Method:Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17rem[i] = rem[i-2] - quo[i] * rem[i-1] x[i] = x[i-2] - quo[i] * x[i-1] y[i] = y[i-2] - quo[i] * y[i-1]i12 CSCI 530, Spring 2010 Copyright © William C. Cheng T10The Table Method (Cont...)rem yxquoa4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-21324251531191001-2-Table Method:Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17rem[i] = rem[i-2] - quo[i] * rem[i-1] x[i] = x[i-2] - quo[i] * x[i-1] y[i] = y[i-2] - quo[i] * y[i-1]i132 CSCI 530, Spring 2010 Copyright © William C. Cheng T11The Table Method (Cont...)CSCI 530, Spring 2010 Copyright © William C. Cheng T12The Table Method (Cont...)rem yxquoa4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-21324251531191001-2-2-Table Method:Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17rem[i] = rem[i-2] - quo[i] * rem[i-1] x[i] = x[i-2] - quo[i] * x[i-1] y[i] = y[i-2] - quo[i] * y[i-1]i132CSCI 530, Spring 2010 Copyright © William C. Cheng T13The Table Method (Cont...)rem yxquoa4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-213242515311910101-2-2-Table Method:Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17rem[i] = rem[i-2] - quo[i] * rem[i-1] x[i] = x[i-2] - quo[i] * x[i-1] y[i] = y[i-2] - quo[i] * y[i-1]i132rem yxquoa4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-213242515311934101-101-23-21-Table Method:Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17rem[i] = rem[i-2] - quo[i] * rem[i-1] x[i] = x[i-2] - quo[i] * x[i-1] y[i] = y[i-2] - quo[i] * y[i-1]4i132 CSCI 530, Spring 2010 Copyright © William C. Cheng T14The Table Method (Cont...)rem yxquoa4251531193417b15311934170x2101-14x101-14-8y201-23-11y11-23-1125y--23-1125x-1-14-8r-11934170q-21324251531193417101-1401-23-11-213-Table Method:Ex: a0 = 425, b0 = 153, gcd(a0,b0) = 17, and 425 ⋅ 4+153 ⋅ (-11) = 17rem[i]


View Full Document

USC CSCI 530 - 03a_pubkey

Download 03a_pubkey
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 03a_pubkey and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 03a_pubkey 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?