1、ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Electronic Payment Systems 20-763 Lecture 5: ePayment Security II,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Outline,Public-key Cryptography One-way trapdoor functions RSA Protocol Fail
2、ure Discrete Logarithms Diffie-Hellman El Gamal Elliptic Curve Cryptosystems,Public Key Encryption,Encryption,“The quick brown fox jumps over the lazy dog”,“Py75c%bn&*)9|fDebDFaq#xzjFrg5=&nmdFg$5knvMdrkvegMs”,“The quick brown fox jumps over the lazy dog”,Decryption,Clear-text Input,Clear-text Output
3、,Cipher-text,Different but mathematically linked keys,Recipients public key,Recipients private key,public,SOURCE: ALBERTO PACE,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,One-Way Trapdoor Function,A function that is easy to compute Computationally difficult to inve
4、rt without knowing the secret (the “trapdoor”) Easy to invert with the secret Example: f x (y) = x y Given f x (y), it is difficult to find either x or y Given f x (y) and x (the secret), it is easy to find y: y = x y / x ANY one-way trapdoor function can be used in public-key cryptography.,ELECTRON
5、IC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Trapdoor Functions for Cryptogrpahy,Alice wants to send message m to Bob Bobs public key e is a parameter to the trapdoor function fe(x) The inverse fe -1(y) is easy to compute knowing Bobs private key d but difficult without d A
6、lice computes fe(m), sends it to Bob Bob computes fe -1(fe(m) = m (easy if d is known) Eavesdropper Eve cant compute m = fe -1(fe(m) without the trapdoor d to find the inverse fe -1 Symmetric encryption satisfies the trapdoor criteria except that e and d are the same, so neither can be made public,E
7、LECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Rivest-Shamir-Adelman (RSA),It is easy to multiply two numbers but apparently hard to factor a number into a product of two others. Given p, q, it is easy to compute n = p q Example: p = 5453089; q = 3918067Easy to find n
8、= 21365568058963 Given n, hard to find two numbers p, q with p q = n Now suppose n = 7859112349338149 What are p and q such that p q = n ? Multiplication is a one-way function RSA exploits this fact in public-key encryption,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAM
9、OS,RSA Encryption,Select two large prime numbers p, q (e.g. 1024 bits) Let n = p q Choose a small odd integer e that does not divide m = (p - 1)(q - 1). Then x(p-1)(q-1) = 1 (mod n) Compute d = e-1(mod m) That is, d e gives remainder 1 when divided by m Then xe d = x (mod n) (by Fermats “Little” The
10、orem) Public key is the pair (e, n) Private key is the pair (d, n) d cannot be calculated quickly from (e, n) Still need p and q, which involves factoring n,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,RSA Encryption,Message M is a numberTo encrypt message M using k
11、ey (e, n): Compute E(M) = M e (mod n)To decrypt message E(M) using key (d, n): Compute D(E(M) = E(M) d (mod n) Note that D(E(M) = E(D(M) = (M e)d (mod n) = M ed (mod n) = M because e d = 1 (mod m) and m = (p-1)(q-1) DEMO,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,
12、Protocol Failure,A “secure” cryptosystem is not secure if used carelessly Protocols must be followed carefully or a “protocol failure” occurs Example: “common modulus” failure Bob and Carol have the same public-key modulus n with encryption exponents eBOB and eCAROL having no common factor Alice sen
13、ds the same plaintext M to both Bob and Carol Bob gets yBOB = MeBOB mod n Carol gets yCAROL = MeCAROL mod n If Eve intercepts both, she can read the message WARNING: NEVER SEND THE SAME MESSAGE TWICE!,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Protocol Failure,Eve
14、 computes: c1 = eBOB-1 (mod eCAROL ) c2 = (c1 eBOB) - 1 )/ eCAROL M = yBOBc1 ( yCAROLc2 )-1 (mod n) = (MeBOB)c1 (MeCAROL)c2)-1 (mod n) = (MeBOB)c1 (MeCAROL)(c1(eBOB)-1)/eCAROL)-1 (mod n) = (MeBOB)c1 (M(c1eBOB-1)-1 (mod n) = M (Mc1(eBOB)-1) (M( c1(eBOB)-1)-1 (mod n) = M mod n So Eve recovers the orig
15、inal message!,KNOWN QUANTITIES:neBOBeCAROLyBOByCAROL,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Discrete Logarithms,If ab = c, we say that logac = b Example: 232 = 4294927296 so log2(4294927296) = 32 Computing ab and logac are both easy for real numbersIn a finite
16、 field, it is easy to calculate c = ab mod p but given c, a and p it is very difficult to find b This is the “discrete logarithm” problem Analogy: Given x it is easy to find two real numbers y, z such that x = yz Given an integer n it is hard to find two integers p, q such that n = pq,ELECTRONIC PAY
17、MENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Diffie-Hellman Key Exchange,Object: allow Alice and Bob to exchange a secret key Protocol has two public parameters: a prime p and a number g p such that given 0 n p there is some k such that gk = n (g is called a generator) Alice and
18、Bob generate random private values a, b between 1 and p-2 Alices public value is ga (mod p); Bobs is gb (mod p) Alice and Bob share their public values Alice computes (gb)a (mod p) = gba (mod p) Bob computes (ga)b (mod p) = gab = gba (mod p) Let key = gab. Now both Alice and Bob have it. No one else
19、 can compute it - they dont know a or b,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,El Gamal Encryption,Based on the discrete logarithm Bobs public key is (p, q, r) Bobs private key is s such that r = qs mod pAlice sends Bob the message m by picking a random secret
20、 number k and sending (a, b) = (qk mod p, mrk mod p) Bob computes b (as )-1 mod p = mrk (qks)-1 = mqks (qks)-1 = m (Bob knows s; nobody else can do this),Relative Time in Seconds Required for RSA Modular Exponentiation y = xe mod n,SOURCE: ANDREAS STEFFEN, ZHW,Elliptic Curves,y2 = x3 + ax + b,4a3 +
21、27b2 0,General form:,Condition for distinct single roots:,Example:y2 = x3 4x= x(x 2)(x +2),SOURCE: ANDREAS STEFFEN, ZHW,ONLINE TUTORIAL,Closure: a b is also an element of G Associativity: a (b c) = (a b) c Identity Element: For some e in G, for all a, a e = e a = a Inverse Element: Every a has an in
22、verse a : a a = a a = e Commutativity: a b = b a (Abelian Group),A set G and an operation defined on pairs of elements of set G such that for all elements a, b and c in G we have:,Examples:,Addition: e = 0 , a = -a Multiplication: e = 1 , a = a-1,SOURCE: ANDREAS STEFFEN, ZHW,The Group ,The Points P(
23、x,y) on an Elliptic Curve form a Group,R = P Q,Group set: All points P(x,y) lying on an elliptic curve,Group operation: Point addition,SOURCE: ANDREAS STEFFEN, ZHW,Identity and Inverse Elements,Inverse element: P(x,-y) = P(x,y) is mirrored on x-axis,Point addition with inverse element: P P = O resul
24、ts in the identity element O(x,) at infinity,O,Identity element: P O = P,SOURCE: ANDREAS STEFFEN, ZHW,Point Doubling Adding a point to itself,R = P P,Point Doubling: Form the tangent in Point P(x,y),SOURCE: ANDREAS STEFFEN, ZHW,Point Iteration Adding a point k-1 times to itself,Pk = P P . P,Point It
25、eration:,SOURCE: ANDREAS STEFFEN, ZHW,Calculation of Point Addition,R (xR, -yR),R(xR, yR),P(xP , yP),Q (xQ , yQ),g,Intersection with curve: (s x+y0)2 = x3 +ax+b,Line g: y = s x+y0 with,Coordinates of point R:,SOURCE: ANDREAS STEFFEN, ZHW,Elliptic Curves Over Finite Fields,Elliptic curves can be defi
26、ned in a finite or Galois field GFp (mod p),y2 = x3 + ax + b mod p,where the field size p is a prime number and0,1, ., p-1 is an abelian group under addition mod pand 1, ., p-1 is an abelian group under multiplication mod p.,SOURCE: ANDREAS STEFFEN, ZHW,Which points P(x,y) with x and y in GF11 satis
27、fy the elliptic curve equation: y2 = x3 + x + 6 mod 11 In Mathematica, compute PositionTableMody2 (x3 + x + 6), 11, x, 1, 10, y, 1, 10, 0,Points on an Elliptic Curve Over a Finite Field,SOURCE: ANDREAS STEFFEN, ZHW,Solution: Points on the Elliptic Curve,There are 12 points lying on the elliptic curv
28、e.Together with the point O at infinity, the points on the elliptic curve form a group with n=13 elements.n is called the order of the elliptic curve group and depends on the choice of the curve parameters a and b.,SOURCE: ANDREAS STEFFEN, ZHW,Elliptic Curve Discrete Logarithm Problem (ECDLP),Given
29、an elliptic curvey2 = x3 + ax + b mod p and a basis point P, we can computeQ = Pk through k-1 iterative point additions. Fast algorithms for this task exist.The order of P is the smallest k for which Pk = O (the identity element) Question: Is it possible to compute k when points Q and P are known? A
30、nswer: This is a hard problem called the Elliptic Curve Discrete Logarithm Problem.,SOURCE: ANDREAS STEFFEN, ZHW,Defining An Elliptic Curve Cryptosystem,version is currently v1 fieldID the finite field over which curve is defined curve coefficients a and b of the elliptic curve base the base point P
31、 order the order of the base point, a LARGE prime number,SOURCE: ANDREAS STEFFEN, ZHW,Must specify the following parameters:,Secret Key Exchange: Diffie-Hellman v. ECC,SOURCE: ANDREAS STEFFEN, ZHW,Elliptic Curves for El Gamal,Multiplication in the elliptic group corresponds to exponentiation of real
32、 numbers Solving y = k x (mod p) for k in the elliptic group is similar to solving c = ab (mod p) for b in El Gamal (discrete logarithm) Select a generator g (an elements whose successive powers generate all group elements) Bobs private key is s; Bobs public key is (g, s g) A plaintext message m is
33、transformed to a point x in the group Alice encrypts x by picking a random value k and sending (k g, x + k s g) Bob decrypts by computing (x + k s g) - (k g) s = x,Alice sent him these,Bob knows s (his private key),g and sg are public; Alice knows x and k,Cant find s from g and sg,Table of Equivalen
34、t Cryptographic “Strength”,SOURCE: ANDREAS STEFFEN, ZHW,Key Lengths,Elliptic curve cryptography standards: PKCS#13 FIPS 186-2 ECC Cipher Suites for TLS ANSI X9.63, X9.63, Public Key Cryptography for the Financial Services Industry,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL
35、I. SHAMOS,Security of ECC versus RSA,GRAPHIC: RICHARD SOUTHERN,ECC Advantages1. The elliptic curve logarithm problem is harder than the discrete logarithm problem.2. Key size in ECC is much smaller for a given security level.3. ECC is complicated; fewer people understand it.4. ECC is not patented.,E
36、LECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Major Ideas,Any one-way trapdoor function can be used as the basis of a public-key cryptosystem Public-key encryption is slow because of the need to work with huge numbers (2000 bits) Cryptosystems can be insecure if not u
37、sed properly Elliptic curve cryptography allows high security with small key sizes,ELECTRONIC PAYMENT SYSTEMS 20-763 SPRING 2004 COPYRIGHT 2004 MICHAEL I. SHAMOS,Q,A,&,Calculation of Point Doubling,Intersection with curve: (s x+y0)2 = x3 +ax+b,Coordinates of point R:,R (xR, -yR),R (xR, yR),P(xP , yP
38、),g,Tangent g: y = s x+y0,SOURCE: ANDREAS STEFFEN, ZHW,Task 1 - Multiplication c = ab in GF11,Compile a multiplication table for c = a b mod 11 Determine the solutions of the equation x2 = 5 mod 11 You have about 10 minutes for this task,SOURCE: ANDREAS STEFFEN, ZHW,Solution 1 - Multiplication c = ab in GF11,x2 = 5 mod 11 ?,x1 = 4, x2 = 7,SOURCE: ANDREAS STEFFEN, ZHW,Task 3 Iterate a Point on the Elliptic Curve,SOURCE: ANDREAS STEFFEN, ZHW,Solution 3 Iterate a Point on the Elliptic Curve,SOURCE: ANDREAS STEFFEN, ZHW,
