《椭圆曲线密码技术备课讲稿》由会员分享，可在线阅读，更多相关《椭圆曲线密码技术备课讲稿（55页珍藏版）》请在金锄头文库上搜索。
1、橢圓曲線密碼技術,交通大學 資訊工程系 陳榮傑 http:/www.cs.nctu.edu.tw/rjchen/ECC2012S/,Outline,1 Discrete Logarithm Problem 2 Algorithms for Discrete Logarithm 3 Cryptosystems Based on DLP 4 Elliptic Curves 5 Elliptic Curve DLP 6 Signature Scheme: ECDSA 7 How to find secure ECs? 8 Hyperelliptic Curves 9 ID-based Cryptos
2、ystems 10 Pairing-based Cryptography,Let G is a finite cyclic group of size n generated by generator g, i.e. G = = g i | i = 1, 2, , n or g i | i = 0, 1, , n-1 Given g and i, it is easy to compute gi by repeated squaring Discrete logarithm problem Given , find x such that We denote,1 Discrete Logari
3、thm Problem,Example 1G = Z19*= 1, 2, , 18n=18, generator g = 2 then log214 = 7 log26 = 14,Example 3Let p =10535462803950169753046165829339587319488718149259134893426087342587178835751858673003862877377055779373829258737624519904504306613508596826974102562682711472830348975632143002371663691740666159
4、07176472549470083113107138189921280884003892629359 NB: p = 158(2800 + 25) + 1 and has 807 bits. Find x in Z, such that 2x = 3 mod p,2 Algorithms for Discrete Logarithm,trivial algorithm Shanks algorithm (Baby-step giant-step) Pollard rho discrete log algorithm Pohlig-Hellman algorithm The index calc
5、ulus method*,The index calculus method,The index calculus method (Suitable only for G=Zp*),Example log59451 mod 10007=? Choose B=2, 3, 5, 7. Of course log55=1. Use lucky exponents 4063, 5136, and 9865 54063 mod 10007 = 42 = 2 * 3 * 7 55136 mod 10007 = 54 = 2 * 33 59865 mod 10007 = 189 = 33 * 7 And w
6、e have three congruences: log52 + log53 + log57 = 4063 mod 10006 log52 + 3 log53 = 5136 mod 10006 3 log53 + log57 = 9865 mod 10006,There happens to be a unique solution modulo 10006 log52=6578, log53=6190, and log57=1301 Choose random exponent s = 7736 and try to calculate ags = 9451*57736 mod 10007
7、 = 8400 Since 8400 = 24*3*52*7 factors over B, we obtain log59451 = (4 log52 + log53 + 2 log55 + log57 s) mod 10006 = (4*6578 + 6190 + 2*1 +1301 7736) mod 10006 = 6057 mod 10006,Complexity of Index Calculus,For factoring and the discrete logarithm problem in finite fields Fq* there are index calculu
8、s algorithm (implemented with Number Field Sieve technique) These have subexponential complexity O(exp(c(lnN)1/3(lnlnN)2/3),3 Cryptosystems based on DL,Key Distribution Diffie-Hellman, 1976 Encryption Massey-Omura cryptosystem, 1983 Digital Signature ElGamal, 1985,Diffie-Hellman Key Exchange Algo,Gl
9、obal Public Elements q : prime number : q and is a primitive root of q User A Key Generation Select private XA : XA q Calculate public YA : YA= XA mod q User B Key Generation Select private XB : XB q Calculate public YB : YB= XB mod q Generation of Secret Key by User A K = (YB)XA mod q Generation of
10、 Secret Key by User B K = (YA)XB mod q,User A,User B,Generate random XA q ; Calculate YA = XA mod q Calculate K = (YB)XA mod q,Generate random XB q ; Calculate YB = XB mod q Calculate K = (YA)XB mod q,YA,YB,Diffie-Hellman Key Exchange,Massey-Omura for message transmission,Parameters q : prime number
11、 e : a random private integer 0 e q and gcd ( e, q-1) = 1 d : an inverse of e d = e-1 mod q-1 , i.e., de1 mod q-1 M : a message to be encrypted and decrypted User A wants to send a message M to User B User A : eA and dA are both private User B : eB and dB are both private,User A,User B,1.Encryption(
12、1) C1 = M eA mod q 3.Encryption(3) C3 = C2dA = (M eAeB)dA = M eB mod q,2.Encryption(2) C2 = C1eB = M eAeB mod q 4. Decryption M = C3dB = M eBdB mod q,Massey-Omura for message transmission,C1,C2,C3,ElGamal signature scheme,1985 ElGamal Parameters p : a large prime : a primitive number in GF(p) x : a
13、private key, x 1, p-1 y : a public key , y = x (mod p) m : a message to be signed , m 1, p-1 k : a random integer that is privately selected, k 0, p-2 Signature r = k mod p m = ks + rx mod (p) ,where GCD( k, (p) ) = 1 ( m , (r,s) ) is sent to the verifier Verification m = rs yr mod p The signature (
14、r,s) is accepted when the equality holds true.,ElGamal encryption scheme,Parameters p : a large prime : a primitive number in GF(p) a : a private key, a 1, p-1 : a public key , = a (mod p) m : a message to be signed , m 1, p-1 k : a random integer that is privately selected, k 0, p-2 K = (p, , a, )
15、: public key + private key Encryption eK(m, k)=(y1, y2) where y1 = k mod p and y2=mk mod p Decryption m = dK(y1, y2) = y2(y1a)-1 mod p,(xP+Q, yP+Q),(xP+Q, yP+Q),4 Elliptic Curves,Over Fields of Characteristic p3 Curve form E: Y2 = X3 + aX + b where a, b Fq, q = pn 4a3+27b20 Group operation given P1(
16、x1,y1) and P2(x2,y2) compute P3(x3,y3) = P1+P2,Example:,P,-P,Q,P+Q,Example of EC over GF(p),Addition (P1P2) Doubling (P1=P2),Computational Cost I + 3 M,Computational Cost I + 4 M,Over Fields of Characteristic 2 Curve form E: Y2 + XY = X3 + aX2 + b where a, b Fq, b0, q = 2n Group operation given P1(x1,y1) and P2(x2,y2) compute P3(x3,y3) = P1+P2,Example of EC over GF(2m),Additio
