Đề tài Nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường cong elliptic, ứng dụng của đường cong elliptic

1 TRƯỜNG……………………… KHOA…………………………….. LUẬN VĂN TỐT NGHIỆP NGHIÊN CỨU, TÌM HIỂU VÀ TRÌNH BÀY VỀ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG Elliptic, ỨNG DỤNG CỦA ĐƯỜNG CONG Elliptic TRONG HỆ THỐNG BỎ PHIẾU ĐIỆN TỬ VÀ HỆ THỐNG TIỀN ĐIỆN TỬ. 2 LỜI CẢM ƠN Lời đầu tiên, em xin được gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật Tiến, người thầy đã giúp đỡ em trong suốt quá trình làm khóa luận, đồng thời cũng là người thầy đã hướng dẫn em những bước đi đầu tiên để khám phá một lĩnh vực đầy bí ẩn và thách thức – lĩnh vực an toàn và bảo mật dữ liệu. Em xin được cảm ơn các thầy, các cô đã giảng dạy em trong suốt bốn năm qua. Những kiến thức mà các thầy, các cô đã dạy sẽ mãi là hành trang giúp em vững bước trong tương lai . Em cũng xin được cảm ơn tập thể lớp K50CC, một tập thể lớp đoàn kết với những người bạn không chỉ học giỏi mà còn luôn nhiệt tình giúp đỡ mọi người, những người bạn đã giúp đỡ em trong suốt bốn năm học tập trên giảng đường Đại học. Cuối cùng, em xin được gửi lời cảm ơn sâu sắc tới gia đình em, những người luôn kịp thời động viên, khích lệ em, giúp đỡ em vượt qua những khó khăn trong cuộc sống. Hà nội, tháng 05 năm 2009 Sinh viên Nguyễn Minh Hải 3 TÓM TẮT NỘI DUNG KHÓA LUẬN Khóa luận là sự nghiên cứu, tìm hiểu và trình bày về chữ ký số trên đường cong Elliptic, ứng dụng của đường cong Elliptic trong Hệ thống bỏ phiếu điện tử và Hệ thống tiền điện tử. Khóa luận được trình bày thành bốn chương với nội dung như sau: Chương 1 : Tóm tắt các khái niệm cơ bản trong số học và trong đại số học. Chương 2 : Trình bày về khái niệm đường cong Elliptic, các dạng đường cong và các phép toán trên đường cong Elliptic. Chương 3 : Trình bày một số chữ ký số trên đường cong Elliptic và phương pháp tấn công hệ mã hóa đường cong Elliptic. Chương 4 : Trình bày ứng dụng của đường cong Elliptic trong Hệ thống bỏ phiếu điện tử và Hệ thống tiền điện tử. 4 CÁC KÝ HIỆU VIẾT TẮT Tom Người gửi tin hoặc người thực hiện việc ký BĐK Ban đăng ký BKP Ban kiểm phiếu Jerry Người nhận tin hoặc người yêu cầu ký EC Đường cong Elliptic (Elliptic Curve) ECC Mã hóa đường cong Elliptic (Elliptic Curve Cryptosystem) ECDSA Thuật toán ký trên EC EDLP Bài toán Logarith rời rạc trên EC E-Voting Bỏ phiếu điện tử (Electronic Voting) gcd Ước số chung lớn nhất (Greatest Common Divisor) GF Trường hữu hạn (Galois Field) IEEE Institute of Electrical and Electronics Engineers IETF Internet Engineer Task Force IFP Bài toán ước số nguyên (Integer Factorization Problem) lcm Bội số chung nhỏ nhất (Least Common Multiple) MOV Phương pháp tấn công Menezes – Okamoto - Vanstone NIST National Institute of Standards RFC Request For Comments RIPEMD-160 Hàm băm 160 bit RSA Hệ mã hóa khóa công khai Rivest – Shamir – Adleman TOF Hàm cửa sập một chiều (Trapdoor One-way Function) 5 CÁC KÝ HIỆU TOÁN HỌC Nhóm cyclic được sinh bởi g #E Số phần tử của đường cong elliptic C Tập các bản mã có thể dK Thuật toán giải mã E Đường cong elliptic eK Thuật toán mã hóa F* Nhóm nhân trên trường F Fq Trường hữu hạn với q phần tử G Điểm cơ sở của E K Không gian các khóa O Phần tử trung hòa của E sigK Thuật toán ký số verK Thuật toán kiểm tra chữ ký Zp Vành các số nguyên dương p φ(n) Hàm phi Euler các số nguyên trong Zn nguyên tố cùng nhau với n. 6 DANH MỤC CÁC HÌNH VẼ TRONG KHÓA LUẬN Hình 1: Một ví dụ về đường cong Elliptic....................................... Error! Bookmark not defined. Hình 2: Điểm ở vô cực................................................................... Error! Bookmark not defined. Hình 3: Phép cộng trên đường cong elliptic .................................... Error! Bookmark not defined. Hình 4: Phép nhân đôi trên đường cong elliptic .............................. Error! Bookmark not defined. 7 MỤC LỤC LỜI MỞ ĐẦU ..............................................................................................................................1 Chương 1 : CÁC KHÁI NIỆM CƠ BẢN ..................................................................................11 1.1. KHÁI NIỆM TRONG SỐ HỌC ..........................................................................................11 1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất .......................................................................11 1.1.2. Quan hệ đồng dư ................................................................................................................12 1.1.3. Số nguyên tố .....................................................................................................................13 1.2. KHÁI NIỆM TRONG ĐẠI SỐ ............................................................................................15 1.2.1. Nhóm................................................................................................................................15 1.2.2. Vành ..................................................................................................................................17 1.2.3. Trường ..............................................................................................................................18 1.2.4. Không gian vector ............................................................................................................22 Chương 2. ĐƯỜNG CONG ELLIPTIC ....................................................................................23 2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG ELLIPTIC.......................................24 2.2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG R2 .................................................................24 2.2.1. Phép cộng ..........................................................................................................................25 2.2.2. Phép nhân đôi.....................................................................................................................28 2.3. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN ...................................................29 2.3.1. Đường cong elliptic trên trường Fp (p là số nguyên tố)........................................................29 2.3.2. Đường cong elliptic trên trường F2m....................................................................................30 2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine ............................................30 2.3.4. Các phép toán trên đường cong elliptic trong hệ tọa độ chiếu..............................................32 2.3.5. Chuyển đổi giữa hệ tọa độ Affine và hệ tọa độ chiếu ..........................................................33 2.3.6. Các phép toán đường cong trong hệ tọa độ chiếu ................................................................33 2.3.6. Phép nhân đường cong .......................................................................................................34 2.4 BÀI TOÁN LOGARIT RỜI RẠC TRÊN ĐƯỜNG CONG ELLIPTIC...................................36 Chương 3. CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTC....................................................37 3.1. CHỮ KÝ SỐ ........................................................................................................................37 3.1.1. Khái niệm chữ ký số.........................................................................................................37 3.1.2. Sơ đồ chữ ký số ................................................................................................................38 3.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC......................................41 3.2.1. Sơ đồ chữ ký ECDSA......................................................................................................41 3.2.2. Sơ đồ chữ ký Nyberg- Rueppel ........................................................................................43 3.2.3. Sơ đồ chữ ký mù Harn trên EC .........................................................................................44 8 3.2.4. Sơ đồ đa chữ ký mù của Harn trên EC .............................................................................47 3.3. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ ECC ................................................................49 3.3.1. Phương pháp tấn công “baby - step giant - step” ...............................................................49 3.3.2. Phương pháp tấn công MOV ............................................................................................50 Chương 4 . ỨNG DỤNG CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC ..........................53 4.1.ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ .........................................................................54 4.1.1. Quy trình bỏ phiếu điện tử ................................................................................................54 4.1.2. Sử dụng ECC trong bỏ phiếu điện tử.................................................................................55 4.2. ỨNG DỤNG TRONG HỆ THỐNG TIỀN ĐIỆN TỬ ..........................................................57 4.2.1. Tạo tiền ecash ...................................................................................................................57 4.2.2 Tiêu tiền ecash ..................................................................................................................58 4.2.3 Đổi tiền ..............................................................................................................................58 4.2.4 Kết thúc giao dịch .............................................................................................................58 KẾT LUẬN ................................................................................................................................59 TÀI LIỆU THAM KHẢO .........................................................................................................61 9 LỜI MỞ ĐẦU Mục tiêu cơ bản của mật mã học là đảm bảo tính bí mật. Nó cho phép 2 đối tác trao đổi thông tin với nhau một cách an toàn trên những kênh truyền thông công khai. Hệ mật mã khóa bí mật có thể định nghĩa như sau: Giả sử ký hiệu M là tập tất cả các bản rõ có thể. C là tập tất cả các bản mã có thể. K là tập các khóa có thể. Hệ mật mã khóa bí mật gồm 2 hàm: CMek : , MCd k : , Kk  sao cho mmed kk ))(( với mọi Mm và Kk  . Trong hệ mật mã này, người gửi (giả sử là Tom)và người nhận (Jerry) cùng thỏa thuận một khóa bí mật, bằng cách gặp mặt nhau trực tiếp hoặc nhờ một trung tâm tin cậy phân phối khóa. Nếu Tom muốn gửi cho Jerry một thông điệp Mm , cô ấy sẽ gửi bản mã )(mec k cho Jerry. Jerry sẽ khôi phục bản rõ m bằng việc dùng hàm giải mã kd . Hệ mật mã khóa bí mật phải đảm bảo rằng các hàm ke và kd phải dễ áp dụng nhưng vẫn an toàn trước kẻ tấn công, khi có bản mã c vẫn khó tính được m (hoặc khóa k). Dù hệ mật mã khóa bí mật vẫn đang được dùng trong nhiều ứng dụng, nhưng vẫn còn một số nhược điểm như vấn đề phân phối khóa, vấn đề quản lý khóa và nó không hỗ trợ việc tạo chữ ký điện tử. Ý tưởng chính của các thuật toán khóa công khai là sử dụng 2 khóa khác nhau cho 2 quá trình mã hóa và giải mã. Ý tưởng này được phát minh bởi Whitfield Diffie và Martin Hellman (1976), độc lập với Ralph Merkle (1978). Từ đó, nhiều hệ mật mã khóa công khai được đưa ra, nhưng hầu hết chúng đều hoặc không an toàn hoặc không khả thi. Các thuật toán khóa công khai đều chậm hơn rất nhiều so với các thuật toán khóa bí mật. Thuật toán RSA chậm hơn 1000 lần so với các thuật toán khóa bí mật phổ biến như DES khi triển khai trong các thiết bị phần cứng; và chậm hơn 100 lần trong các phần mềm mã hóa khi mã hóa cùng một khối lượng dữ liệu như nhau. Tuy nhiên, hệ mật mã khóa công khai có một ưu điểm nổi trội là cho phép tạo chữ ký điện tử. Khóa riêng được người sở hữu giữ bí mật và nó được sử dụng để tạo chữ ký điện tử hoặc để giải mã các thông điệp đã được mã hóa bằng khóa công khai. Khóa công khai không cần thiết phải giữ bí mật do tính chất “khó tính được khóa riêng từ khóa công khai” của cặp khóa. Vì vậy, người dùng có thể công bố khóa công khai 10 trên các kênh công cộng cho những ai muốn gửi thông tin cho họ hoặc xác minh chữ ký của họ. Trong lịch sử hơn 20 năm của mật mã khóa công khai, đã có nhiều bài toán “khó” được đưa ra xem xét để ứng dụng cho các vấn đề mật mã học. Trong đó có 2 bài toán nổi bật nhất là bài toán logarith rời rạc trên trường hữu hạn và bài toán tìm ước số nguyên tố. Năm 1985, Neal Koblitz và V.S.Miller đã độc lập nhau cùng đề xuấtviệc sử dụng các đường cong elliptic cho các hệ mã hóa khóa công khai. Họ không phát minh ra thuật toán mã hóa mới với các đường cong elliptic trên trường hữu hạn, mà họ dùng những thuật toán đã có như Diffie – Hellman, sử dụng các đường cong elliptic. Các đường cong Elliptic có thể dùng trong nhiều ứng dụng như kiểm thử số nguyên tố hoặc bài toán tìm ước số nguyên tố. Các hệ mật mã trên đường cong elliptic (ECC) được dự báo là sẽ phổ biến hơn RSA do khóa nhỏ gọn hơn nhiều (khoảng 163 bit) so với RSA (1024 bit). Vì vậy, tốc độ mã hóa nhanh hơn so với RSA. Như vậy ECC có thể được dùng trên các thiết bị cầm tay (có bộ nhớ nhỏ, và tốc độ tính toán không cao) . Việc thương mại hóa ECC đã được một số nơi thực hiện như công ty Certicom và công ty RSA đã hỗ trợ mã hóa ECC trong các bộ công cụ phát triển. Tuy nhiên, một vấn đề có thể ảnh hưởng đến sự chấp nhận ECC rộng rãi như một phần của cơ sở hạ tầng khóa công khai là các kỹ thuật thực thi đường cong elliptic, thói quen, các thuật toán, và các giao thức. ECC đòi hỏi các thủ tục toán học phức tạp trong việc khởi tạo các đường cong. Các chuyên gia công nghệ thông tin vẫn chưa hiểu thấu đáo để thiết kế các hệ thống bảo mật dựa trên mật mã học, trong khi hệ RSA thì không quá phức tạp và khó hiểu. 11 Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. KHÁI NIỆM TRONG SỐ HỌC 1.1.1. Ước chung lớn nhất và bội chung nhỏ nhất a. Khái niệm Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, thì ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a và a là bội của b. Số nguyên d được gọi là ước chung của các số nguyên a1, a2, …, an , nếu nó là ước của tất cả các số đó. Số nguyên m được gọi là bội chung của các số nguyên a1, a2, …, an , nếu nó là bội của tất cả các số đó. Một ước chung d >0 của các số nguyên a1, a2, …, an , trong đó mọi ước chung của a1, a2, …, an đều là ước của d, thì d được gọi là ước chung lớn nhất của a1, a2, …, an . Ký hiệu d = gcd (a1, a2, …, an) hay d = UCLN(a1, a2, …, an). Nếu gcd(a1, a2, …, an) = 1,thì a1, a2, …, an được gọi là nguyên tố cùng nhau. Một bội chung m >0 của các số nguyên a1, a2, …, an , trong đó mọi bội chung của a1, a2, …, an đều là bội của m, thì m được goi là bội chung nhỏ nhất của a1, a2, …, an . Ký hiệu m = lcm(a1, a2, …, an) hay m = BCNN(a1, a2, …, an). b. Ví dụ Cho a =12, b =15, gcd(12,15) = 3, lcm(12,15) = 60. Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1. c. Tính chất 1. d = gcd(a1, a2, …, an) tồn tại x1, x2,…, xn sao cho: d = a1x1+a2x2+…+anxn a1,a2,..an nguyên tố cùng nhautồn tại x1,x2,.. xn sao cho: 1 = a1x1+a2x2+…+anxn 2. d = gcd(a1, a2, …, an)  gcd(a1/d, a2/d,…, an/d) =1. 3. m = lcm(a1, a2, …, an)  gcd(m/a1, m/a2,…, m/an) =1. 4. gcd(m a1, m a2, …, m an) = m * gcd(a1, a2, …, an) (với m ≠ 0). 5. Nếu gcd(a, b) =1 thì lcm(a, b) = a * b 6. Nếu b>0, a = bq+r thì gcd(a,b) = gcd(b, r). 12 1.1.2. Quan hệ đồng dư a. Khái niệm Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với nhau theo modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư. Ký hiệu: a ≡ b (mod m). b. Ví dụ 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, được cùng số dư là 2. c. Tính chất 1. Quan hệ “đồng dư” là quan hệ tương đương trong Z: Với mọi số nguyên dương m ta có: a ≡ a (mod m) với mọi a  Z; (tính chất phản xạ). a ≡ b (mod m) thì b ≡ a (mod m); (tính chất đối xứng). a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m); (tính chất bắc cầu). 2. Tổng hay hiệu các “đồng dư ”: (a+b) (mod n)  [(a mod n) + (b mod n)] (mod n) (a- b) (mod n)  [(a mod n) - (b mod n)] (mod n) Tổng quát: Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một đồng dư thức theo cùng modulo m, tức là: Nếu ai ≡ bi (mod m) , i = 1...k, thì 1 1 (mod ) k k i i i i i i t a t b m     với ti = ± 1. 3.. Tích các “đồng dư”: (a* b) (mod n)  [(a mod n) * (b mod n)] (mod n) Tổng quát: Có thể nhân từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một đồng dư thức theo cùng modulo m, tức là: Nếu ai ≡ bi (mod m) với i=1..k, thì ta có: 1 1 (mod ) k k i i i i a b m     13 1.1.3. Số nguyên tố a. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó. b. Ví dụ 10 số nguyên tố lớn đã được tìm thấy : rank Prime Digits Who when reference 1 232582657-1 9808358 G9 2006 Mersenne 44?? 2 230402457-1 9152052 G9 2005 Mersenne 43?? 3 225964951-1 7816230 G8 2005 Mersenne 42?? 4 224036583-1 7235733 G7 2004 Mersenne 41?? 5 220996011-1 6320430 G6 2003 Mersenne 40?? 6 213466917-1 4053946 G5 2001 Mersenne 39 7 19249·213018586+1 3918990 SB10 2007 8 27653·29167433+1 2759677 SB8 2005 9 28433·27830457+1 2357207 SB7 2004 10 33661·27031232+1 2116617 SB11 2007 c. Định lý 1. Định lý: về số nguyên dương > 1. Mọi số nguyên dương n > 1 đều có thể biểu diễn được duy nhất dưới dạng: 1 2 kn n n 1 2 k. ...=P P Pn , trong đó: k, ni ( i =1,2,..,k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau. 2. Định lý Mersenne. Cho p = 2k -1, nếu p là số nguyên tố, thì k phải là số nguyên tố. 14 Chứng minh Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1< a, b < k. Như vậy : p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E (Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Niu-tơn). Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử sai, hay k là số nguyên tố. 3. Hàm Euler: Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên tố cùng nhau với n được ký hiệu  (n) và gọi là hàm Euler. Nhận xét: Nếu p là số nguyên tố, thì  (p) = p-1 Ví dụ: Tập các số nguyên không âm nhỏ hơn 7 là Z 7 = {0, 1, 2, 3, 4, 5, 6, 7}. Do 7 là số nguyên tố, nên Tập các số nguyên dương nhỏ hơn 7 và nguyên tố cùng nhau với 7 là Z 7 * ={1, 2, 3, 4, 5, 6, 7}. Khi đó /Z/ =  (p) = p-1 =8-1 = 7. Định lý hàm Euler. Nếu n là tích của hai số nguyên tố n = p.q, thì  (n) =  (p). (q) = (p-1).(q-1). 15 1.2. KHÁI NIỆM TRONG ĐẠI SỐ 1.2.1. Nhóm a. Khái niệm Nhóm là một bộ (G, *), trong đó G  , * là phép toán hai ngôi trên G thoả mãn ba tính chất sau: + Phép toán có tính kết hợp: (x*y)* z = x*(y*z) với mọi x, y, z  G. + Có phần tử phần tử trung lập e  G: x*e = e*x = x với mọi x  G. + Với mọi x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e. Cấp của nhóm G được hiểu là số phần tử của nhóm, ký hiệu là G . Cấp của nhóm có thể là  nếu G có vô hạn phần tử. Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán. Tính chất: Nếu a * b = a * c, thì b = c. Nếu a * c = b * c, thì a = b. * Tập hợp các số nguyên Z cùng với phép cộng (+) thông thường là nhóm giáo hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên. * Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép nhân (*) thông thường là nhóm giao hoán. Gọi là nhóm nhân các số hữu tỷ (số thực) khác 0. * Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán. b. Nhóm Cyclic Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong các phần tử của nó. Tức là có phần tử g  G mà với mỗi a  G, đều tồn tại số n  N để g n = g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần). Khi đó g được gọi là phần tử sin