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ử

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ử sinh hay phần tử nguyên thuỷ của nhóm G. Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g  G sao cho mọi phần tử trong G đều là một luỹ thừa nguyên nào đó của g. Nhóm (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1. 16 Cho (G, *) là Nhóm Cyclic với phần tử sinh g. và phần tử trung lập e. Nếu tồn tại số tự nhiên nhỏ nhất n mà g n = e, thì G sẽ chỉ gồm có n phần tử khác nhau: e, g, g2 , g3 , . . . , g n - 1 . Khi đó G được gọi là nhóm Cyclic hữu hạn cấp n. Nếu không tồn tại số tự nhiên n để g n = e, thì G có cấp . c. Nhóm (Zn* , phép nhân mod n) * Kí hiệu Zn = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n. Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, pt trung lập e = 0. (Zn , + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n. * Kí hiệu Zn * = x  Zn , x là nguyên tố cùng nhau với n. Tức là x phải  0. Zn * được gọi là Tập thặng dư thu gọn theo mod n, có số phần tử là (n). Zn * với phép nhân mod n lập thành một nhóm (nhóm nhân), pt trung lập e = 1. Tổng quát (Zn * , phép nhân mod n ) không phải là nhóm Cyclic. Nhóm nhân Zn*là Cyclic chỉ khi n có dạng: 2,4, pk, hay 2pk với p là nguyên tố lẻ. * Định lý Lagrange: Nếu G là nhóm cấp n và   G, thì Cấp của  là ước của n. * Hệ quả: Giả sử   *nZ có Cấp m, thì m là ước của (n). * Định lý: Nếu p là số nguyên tố thì *pZ là nhóm Cyclic. Nếu b  *nZ thì b (n)  1 (mod n). Nếu p là số nguyên tố thì (p) = p-1. Do đó với b  *pZ (tức b nguyên tố với p), thì b (p)  1 (mod n), hay bp -1  1(mod n). d. Phần tử nghịch đảo đối với phép nhân * Định nghĩa Cho a  Zn , nếu tồn tại b  Zn sao cho a b  1 (mod n), ta nói b là phần tử nghịch đảo của a trong Zn và ký hiệu a -1. Một phần tử có phần tử nghịch đảo, gọi là khả nghịch. * Định lý: UCLN (a, n) = 1  Phần tử a  Zn có phần tử nghịch đảo. Chứng minh Nếu a a-1 ≡ 1 (mod n) thì a a-1 = 1 + kn ↔ a a-1 - kn = 1 → (a, n) =1. Nếu (a, n) = 1, ta có a a-1 + kn = 1 → a a-1 = 1+kn, do đó a a-1 ≡ 1 (mod n). 17 * Hệ quả: Mọi phần tử trong Zn* đều có phần tử nghịch đảo. 1.2.2. Vành Vành là một tập R với 2 toán tử + và . với các điều kiện sau: ,R là một nhóm Abel a . (b . c) = (a . b) . c với mọi a, b, c  R. a . (b + c) = a . b + a . c và (a + b) . c = a . c + b . c với mọi a, b, c  R. Vành tuyến tính F là một vành. Một đa thức bậc n trên F có dạng:    n i n n i i xaxaaxaxf 0 10 ...)( với n là số nguyên dương, các hệ số ai  F ( ni 0 ). Cho 2 đa thức    n i i i xaxf 0 )( và    n i i i xbxg 0 )( Ta định nghĩa tổng của f(x) và g(x) là    n i i ii xbaxgxf 0 )()()( Cho 2 đa thức    n i i i xaxf 0 )( và    m j j j xbxg 0 )( Ta định nghĩa tích của f(x) và g(x) là     nm k k k xcxgxf 0 )()( với     mjni kji jik bac 0,0 Vành được tạo thành bởi tất cả các đa thức trên F với toán tử thông thường là cộng và nhân được gọi là vành đa thức trên F và ký hiệu là F[x]. Định lý (Thuật toán chia cho F[x]) Giả sử f(x) và g(x)  F[x] có bậc nguyên dương, tồn tại duy nhất đa thức q(x), r(x) F[x] thỏa mãn f(x) = g(x) . q(x) + r(x) với bậc của r(x) nhỏ hơn bậc của g(x). Nếu r(x) là đa thức 0 thì g(x) được gọi là ước của f(x). Đa thức bất định f(x) trong F[x] là tối giản nếu nó không có ước có bậc thấp hơn f(x) trong F[x]. a F là nghiệm của f(x) F[x] nếu f(a) = 0. Hệ quả Một phần tử a F là nghiệm của đa thức f(x) F[x] khi và chỉ khi x – a là ước của f(x) trong F[x]. 18 Chứng minh Vì a là nghiệm nên f(a) = 0. Vì f(x) = (x –a).g(x) + r(x) nên bậc của r(x) nhỏ hơn 1, tức là r(x) = c F. Vì vậy, c = f(a) = 0. Ngược lại, nếu f(x) = (x – a). q(x) thì f(a) = 0. Hệ quả Một đa thức khác không f(x)  F[x] bậc n có nhiều nhất n nghiệm trong F. 1.2.3. Trường Trường F là một vành với phần tử đơn vị e  0 sao cho F* = {a F | a  0 } là một nhóm nhân. Định lý Vành Zp là một trường khi và chỉ khi p là số nguyên tố Chứng minh Với a, b  Z, ta có p là số nguyên tố  p|ab tức là p|a hoặc p|b Nếu Zp là một trường thì *pZ tạo thành một nhóm nhân. Nếu p a thì a  0 mod p. Điều này nghĩa là a *pZ và tồn tại a -1. Do đó nếu p|ab và p a thì p|(ab)-1 = b. Vậy p là số nguyên tố. Ngược lại, giả sử p là số nguyên tố. Để chỉ ra rằng *pZ là một nhóm nhân ta chỉ cần chỉ ra rằng với mọi *pZx sẽ luôn tồn tại nghịch đảo x -1. Với a, b  Zp và * pZx , nếu xa xb mod p thì a b mod p  a – b  0 mod p. Vì p|x(a–b)p|x hoặc p|a – b và *pZx tức là p x. Điều này suy ra xZp = {xa | a Zp} = Zp trong đó xa = 1 với a  Zp vì luôn tồn tại phần tử 1 trong Zp. Vậy mỗi *pZx luôn có phần tử nghịch đảo. Định nghĩa F là một trường. Một tập con K của F cũng là một trường với các toán tử của F được gọi là trường con của F. Hay F là một trường mở rộng của K. Nếu K  F thì K được gọi là một trường con hợp lệ của F. Trường là tối giản nếu không có trường con hợp lệ nào. Với trường F bất kỳ, giao F0 của tất cả các trường con hợp lệ là trường tối giản. 19 Trường F được gọi là có đặc số 0 nếu F0  Q nghĩa là F chứa Q như một trường con. Trường F được gọi là có đặc số p nếu F0  Zp. Trường hữu hạn là trường chứa hữu hạn các phần tử. Mọi trường hữu hạn có một số nguyên tố là đặc số của trường. Một trường F có đặc số thì với mọi a  F, pa =   p aa  = 0 Định nghĩa Trường K với phần tử đơn vị nhân là 1. Với p thỏa mãn 01...11   p được gọi là đặc số của K. [5] (Các trường hữu tỷ Q, số thực R, số phức C có đặc số là 0 ) Với p là nguyên tố thì GF(pn) có đặc số p. Nếu H là trường con của K thì H và K có cùng đặc số. F là trường mở rộng của trường K. Ký hiệu F = K( ) nếu F là trường mở rộng nhỏ nhất của K chứa  . Nếu F là trường hữu hạn đặc số p thì nhóm nhân F* = F \ {0} là nhóm cylic và F = Zp( ) với  là phần tử sinh của nhóm F* và  được gọi là phần tử nguyên thủy của F. Với 2 toán tử nhị nguyên * và  trên các tập A và B, một ánh xạ f : A  B nếu với mọi a, b  A ta có: f(a * b) = f(a)  f(b) Giả sử A và B là 2 nhóm (hoặc 2 trường), ta gọi h: A  B là một đẳng cấu A đến B nếu h đảm bảo các tính chất của toán tử nhóm của A. Trường hữu hạn Trường hữu hạn là trường có hữu hạn các phần tử ký hiệu là Fq hoặc GF(q) với q là số các phần tử. Định lý F là trường mở rộng bậc n trên trường hữu hạn K. Nếu K có q phần tử thì F có qn phần tử. Chứng minh Giả sử { n ,...,1 }là cơ sở của F như là một không gian vector trên K. Mọi F sẽ có dạng nncc   ...11 trong đó Kci  (i = 1,…, n). Vì mỗi ci có thể là một trong q phần tử của K nên số các tổ hợp tuyến tính là qn. 20 Định lý Nếu F là một trường hữu hạn có đặc số p thì F có pn phần tử với n nguyên dương. Vì vậy, mọi trường hữu hạn là một mở rộng của trường đẳng cấu Zp với p là đặc số của F. Định lý Trường hữu hạn F = npF là một trường mở rộng của Zp bậc n và mọi phần tử của npF là một nghiệm của đa thức xx np  trên Zp. Chứng minh Đặc số của npF là p. Tập hợp F* = F \ {0} tạo thành nhóm nhân bậc pn -1. Với *F , bậc của trong nhóm chia hết cho bậc của F*, pn – 1. Vì vậy, với mọi *F , chúng ta có 11  np hay   np . Vì xx np  có nhiều nhất pn nghiệm, npF gồm tất cả các nghiệm của xx np  trên Zp. Ví dụ Trường rF2 chứa F2(hoặc Z2).Nếu viết toán tử cộng trong rF2 như là phép cộng vector và viết phép nhân k và v(k,v rF2 )là một tích vô hướng của kF2 và v rF 2 .Khi đó rF2 được xem là không gian vector trên F2 với chiều r. Ký hiệu d là chiều của không gian vector này. Có thể thực hiện ánh xạ 1 – 1 giữa các phần tử trong không gian vector d chiều và các d-tuple của các phần tử trong F2. Vì vậy,có2d phần tử trong không gian vector này.Vì d = r, rF2 là không gian vector r chiều. mqF là một mở rộng của Fq. 2 phần tử mqF , là liên hợp trên Fq nếu  và  là các nghiệm của cùng một đa thức tối giản bậc m trên Fq. 12 ,...,,, mqqq  là các liên hợp của mqF với Fq. mqF là một mở rộng của Fq. Một cơ sở của mqF (không gian vector trên Fq) của { 12 ,...,,, mqqq  } gồm mqF và các liên hợp của nó với Fq , được gọi là cơ sở trực giao của mqF trên Fq. Mọi trường mở rộng bậc hữu hạn của một trường hữu hạn có một cơ sở trực giao. Không gian chiếu 21 Xét L = Kn+1 \{0} với K là một trường. Với A = (a0, a1, …, an), B = {b0, b1, …, bn} L, định nghĩa một quan hệ A ~ B gồm A, B và gốc O = (0, 0,…,0) là cộng tuyến, nghĩa là tồn tại K thỏa mãn : ii ba  , (i = 0, 1, …, n). Quan hệ ~ là quan hệ tương đương và định nghĩa một phân hoạch của L. Tập thương số là không gian chiếu ký hiệu là Pn(K). Mặt phẳng chiếu là tập các lớp tương đương của bộ ba (X, Y, Z) với ( ),,( ZYX  ) ~ (X, Y, Z) ( K ). Mỗi lớp tương đương (X, Y, Z) được gọi là một điểm chiếu trên mặt phẳng chiếu. Nếu một điểm chiếu có Z  0, thì (x, y, 1) là một thể hiện của lớp tương đương với x = Z X , y = Z Y . Mặt phẳng chiếu có thể được định nghĩa là tập tất cả các điểm(x, y)của mặt phẳngAffine cộng với các điểm Z = 0. 22 1.2.4. Không gian vector K là một trường và V là một nhóm cộng Abel. V được gọi là không gian vector trên trường K nếu một toán tử K x V  V được định nghĩa thỏa mãn các điều kiện sau: a(u + v) = au + av (a + b)u = au + bu a(bu) = (ab)u 1u = u Các phần tử của V được gọi là các vector và các phần tử của K được gọi là các vô hướng. V là một không gian vector trên trường K và các v1, …, vm V. Vector trong V có dạng c1v1 + c2v2 + …+ cmvm với ci K (i = 1, …, m) là một tổ hợp tuyến tính của v1, …, vm. Tập hợp tất cả các tổ hợp tuyến tính gọi là span của v1, …,vmvà ký hiệu là span(v1, …, vm). v1, …, vm được gọi là span nếu của V nếu V = span(v1, …, vm). V là không gian vector trên trường K. Các vector v1, …, vm V được gọi là độc lập tuyến tính trên K nếu không có các vô hướng c1,…, cm K thỏa mãn: c1v1 + c2v2 + …+ cmvm = 0 Tập S = {u1, u2,…,un} của các vector tạo thành cơ sở của V khi và chỉ khi u1, u2,…,un là độc lập tuyến tính là span của V. Nếu S là một cơ sở của V thì mọi phần tử của V được biểu diễn duy nhất dưới dạng tổ hợp tuyến tính của các phần tử của S. Nếu không gian vector V có cơ sở là một số hữu hạn các vector thì bất kỳ cơ sở nào của V cũng sẽ có cùng số phần tử. Khi đó nó chính là chiều của V trên K. Nếu F là một trường mở rộng của trường K thì F là một không gian vector trên K. Chiều của F trên K được gọi là bậc mở rộng của F trên K. 23 Chương 2. ĐƯỜNG CONG ELLIPTIC Hệ thống mã khóa khóa công khai dựa trên việc sử dụng các bài toán khó giải quyết. Vấn đề khó ở đây chính là việc số lượng phép tính cần thiết để tìm ra một lời giải cho bài toán là rất lớn. Trong lịch sử 20 năm của ngành mã hóa bất đối xứng đã có nhiều đề xuất khác nhau cho dạng bài toán như vậy, tuy nhiên chỉ có hai trong số các đề xuất đó còn tồn tại đến ngày nay. Hai bài toán đó bao gồm : bài toán logarit rời rạc (discrete logarithm problem) và bài toán phân tích thừa số của số nguyên. Cho đến năm 1985, hai nhà khoa học Neal Koblitz và Victor S.Miller đã độc lập nghiên cứu và đưa ra đề xuất ứng dụng lý thuyết toán học đường cong elliptic (elliptic curve ) trên trường hữu hạn. Đường cong elliptic cũng như đại số hình học- được nghiên cứu rộng rãi trong vòng 150 năm trở lại đây và đã đạt được một số kết quả lý thuyết có giá trị. Đường cong elliptic được phát hiện lần đầu tiên vào thế kỷ 17 dưới dạng công thức Diophantine : y2 – x3 = c với c Z Tính bảo mật của hệ thống mã hóa sử dụng đường cong elliptic dựa trên điểm mấu chốt là độ phức tạp của bài toán logarit rời rạc trong hệ thống đại số. Trong suốt 10 năm gần đây, bài toán này nhận được sự quan tâm chú ý rộng rãi của các nhà toán học hàng đầu trên thế giới. Không giống như bài toán logarit rời rạc trên trường hữu hạn hoặc bài toán phân tích thừa số của số nguyên, bài toán logarit rời rạc trên đường cong elliptic chưa có thuật toán nào có thời gian thực hiện nhỏ hơn cấp lũy thừa. Thuật toán tốt nhất được biết đến hôm nay tốn thời gian thực hiện cấp lũy thừa. 24 2.1. CÔNG THỨC WEIERSTRASSE VÀ ĐƯỜNG CONG ELLIPTIC Gọi K là trường hữu hạn hoặc vô hạn. Một đường cong elliptic được định nghĩa trên trường K bằng công thức Weierstrasse : y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 (1) Trong đó a1 , a2 , a3 , a4 , a5 , a6 K Đường cong elliptic trên trường k được ký hiệu E(K). Số lượng các điểm nguyên trên E ký hiệu là #E(K) , có khi chỉ đơn giản là #E. Đối với từng trường khác nhau, công thức Weierstrasse có thể được biến đổi và đơn giản hóa thành các dạng khác nhau. Một đường cong elliptic là tập hợp các điểm thỏa mãn công thức trên. Hình 1: Một ví dụ về đường cong Elliptic 2.2. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG R2 Đường cong elliptic E trên trường số thực R là tập hợp các điểm (x,y) thỏa mãn công thức: y2 = x3 + a4x + a6 với a4 , a6 R (2) cùng với một điểm đặc biệt O được gọi là điểm tại vô cực (cũng là phần tử identify). Cặp giá trị (x,y ) đại diện cho một điểm trên đường cong elliptic và tạo nên mặt phẳng tọa độ hai chiều (Affine) R x R . Đường cong elliptic E trên R2 25 được gọi là định nghĩa trên R , ký hiệu là E (R). Đường cong elliptic trên số thực có thể dùng để thể hiện một nhóm (E(R), +) bao gồm tập hợp các điểm (x ,y) thuộc R x R với phép công + trên E(R). 2.2.1. Phép cộng Hình 2: Điểm ở vô cực Phép cộng điểm (ESUM) được định nghĩa trên tập E(R) của các điểm (x, y). Điểm tại vô cực 0 là điểm cộng với bất kỳ điểm nào cũng sẽ ra chính điểm đó. Như vậy,    , ,P x y E R P O O P P          3 4 6, ,P x y E R y x a a     (3) Như vậy , tương ứng với một giá trị x ta sẽ có hai giá trị tọa độ y. Điểm (x , -y ) ký hiệu là –P E(R), được gọi là điểm đối của P với : P + (-P) = (x , y) + (x ,- y) = 0 (4) Phép cộng trên E(R) được định nghĩa theo phương diện hình học . Giả sử có hai điểm phân biệt P Và Q , P, Q E(R). Phép cộng trên nhóm đường cong elliptic là P +Q = R ,R E(R). 26 Hình 3: Phép cộng trên đường cong elliptic Để tìm ra điểm R , ta nối P và Q bằng đường thẳng L. Đường thảng L sẽ cắt E tại ba điểm P , Q và -R(x , y). Điểm R (x , -y) sẽ có tung độ là giá trị đối của y. Thể hiện đường cong elliptic dưới dạng đại số , ta có: P = (x1 , y1) Q = (x2 , y2) R= P + Q = (x3 , y3) (5) Trong đó P , Q , R E (R) và : x3 = θ2 – x1 – x2 y3 = θ(x1 + x3) – y1 (6) 2 1 2 1 y y x x     nếu P ≠ Q (7) Hoặc 2 1 4 1 3 2 x a y    nếu P = Q (8) 27 Thuật toán cộng trên đường cong elliptic Input: Đường cong elliptic E(R)với các tham số a4, a6 E(R) , Điểm P = (x1, y1) E(R) và Q = (x2, y2) E(R) Output: R = P + Q, R = (x3, y3) E(R) If P = O then R ← Q và trả về giá trị R If Q = O then R ← P và trả về giá trị R If x1 = x2 then If y1 = y2 then 2 1 4 1 3 2 x a y    else if y1 = −y2 then R ← O và trả về R, else 2 1 2 1 y y x x     end if x3 = θ2 – x1 – x2 y3 = θ(x1 + x3) – y1 Trả về (x3, y3) = R 28 2.2.2. Phép nhân đôi Hình 4: Phép nhân đôi trên đường cong elliptic Xét phép nhân đôi (EDBL): nếu cộng hai điểm P, Q E(R) với P = Q thì đường thẳng L sẽ là tiếp tuyến của đường cong elliptic tại điểm P. Trường hợp này điểm –R sẽ là giao điểm còn lại của L với E. Lúc đó R = 2P. 29 2.3. ĐƯỜNG CONG ELLIPTIC TRÊN TRƯỜNG HỮU HẠN Đường cong elliptic được xây dựng trên các trường hữu hạn. Có hai trường hữu hạn thường được sử dụng: trường hữu hạn Fq với q là số nguyên tố hoặc q là 2m (m là số nguyên). Tùy thuộc vào trường hữu hạn Fq, với mỗi bậc của q, tồn tại nhiều đường cong elliptic. Do đó, với một trường hữu hạn cố định có q phần tử và q lớn, có nhiều sự lựa chọn nhóm đường cong elliptic. 2.3.1. Đường cong elliptic trên trường Fp (p là số nguyên tố) Cho p là số nguyên tố (p>3), Cho a,b Fp sao cho 4a3 + 27b2 ≠ 0 trong trường Fp . Một đường cong elliptic E(Fp) trên Fp (được định nghĩa bởi các tham số a và b) là tập hợp các cặp giá trị (x ,y) (x, y Fp) thỏa công thức: y2 = x3 + ax + b (9) cùng với một điểm 0 – gọi là điểm tại vô cực. Số lượng điểm của E(Fp) là #E(Fp) thỏa định lý Hasse: 1 2 # ( ) 1 2pp p E F p p      (10) Các phép toán của đường cong elliptic trên Fp cũng tương tự với E(R). Tập hợp các điểm trên E(Fp) tạo thành một nhóm thỏa các tính chất sau:  Tính đóng: a, b G, a + b G.  Tính kết hợp: Các phép toán trong nhóm có tính kết hợp Do đó, (a + b) + c = a + (b + c).  Phần tử trung hòa: có một giá trị 0 G sao cho a + 0 = 0 + a = a, a G.  Phần tử đối: , a G , -a G gọi là số đối của a, sao cho -a + a = a + (-a) = 0 Bậc của một điểm A trên E(Fp) là một số nguyên dương r sao cho: .... 0 r A A A    (11) 30 2.3.2. Đường cong elliptic trên trường F2m Một đường cong elliptic E(F2m) trên F2m được đĩnh nghĩa bởi các tham số a , b F2m (với b ≠ 0 ) là tập các điểm (x,y) với các x F2m , y F2m thỏa công thức: y2 + xy = x3 + ax2 + b (12) cùng với điểm 0 là điểm tại vô cực . Số lượng các điểm thuộc E(F2m) ký hiệu # E(F2m) thỏa định lý Hasse : 1 2 # ( ) 1 2pp p E F p p      (13) Trong đó q = 2m . Ngoài ra # E(F2m) là số chẵn Tập hợp các điểm thuộc E(F2m) tạo thành một nhóm thỏa các tính chất sau:  0 + 0 = 0  (x , y) + 0 = (x , y) , (x ,y) E(F2m)  (x , y) + (x, x + y) = 0 , (x ,y) E(F2m) Khi đó (x, x + y) là điểm đối của (x , y) trên E(F2m)  Việc xử lý được thực hiện trên hai hệ tọa độ khác nhau: hệ tọa độ Affine và hệ tọa độ quy chiếu. Với các hệ tọa độ khác nhau, việc tính toán trên đường cong cũng khác nhau. 2.3.3. Các phép toán trên đường cong elliptic trong hệ tọa độ Affine Hệ mã hóa đường cong elliptic dựa trên bài toán logarit rời rạc trên E(F2m) và các tính toán cơ bản trên đường cong elliptic. Phép nhân được thể hiện là một dãy các phép cộng và phép nhân đôi các điểm của đường cong elliptic. Giống như các phép tính trên đường cong elliptic trên số thực, phép cộng và phép nhân đôi được định nghĩa trên hệ tọa độ. Xét đường cong elliptic E trên F2m trong hệ tọa độ Affine. Cho P = (x1 , y1) , Q = (x2 , y2) là hai điểm trên đường cong elliptic E(F2m) . Điểm đối của P là: –P = (x1 , y1+x1) E(F2m). 31 Nếu Q ≠ -P thì P +Q = R = (x3, y3) E(F2m) 32 Thuật toán cộng điểm trong hệ tọa độ Affine Input Đường cong elliptic E(F2m) với các tham số a2 , a6 F2m Điểm P = (x1, y1) E(F2m) và Q = (x2, y2) E(F2m) Output : R = P +Q ,R = (x3, y3) E(F2m) If P = O then R ← Q và trả về giá trị R If Q = O then R ← P và trả về giá trị R If x1 = x2 then If y1 = y2 then 1 1 1 y x x    và x3 ← θ2 + θ + a2 Else If y2 = x1 + y1 then R ← O và trả về R, Else If 1 2 1 2 y y x x     End If x3 ← θ2 + θ + x1 + x2 + a2 y3 ← (x1 + x3)θ + x3 + y1 Trả về (x1, y3) =R 2.3.4. Các phép toán trên đường cong elliptic trong hệ tọa độ chiếu Đường cong E(F2m) có thể được xem là tương đương với tập hợp các điểm E’(F2m) trên mặt phẳng chiếu P2(F2m) thỏa mãn công thức: y2z + xyz = x3 +a2x2z2 +a6z3 (16) Sử dụng hệ tọa độ chiếu , thao tác tính nghịch đảo cần cho phép cộng và phép nhân đôi điểm trong hệ Affine có thể được loại bỏ. 33 2.3.5. Chuyển đổi giữa hệ tọa độ Affine và hệ tọa độ chiếu Mọi điểm (a,b) E(F2m) trong hệ tọa độ Affine có thể được xem là bộ ba (x,y,z) trong E’(F2m) trong hệ tọa độ chiếu với x = a , y =b , z= 1. Hơn nữa , một điểm (tx , ty , tz) trong hệ tọa độ chiếu với t ≠ 0 được xem như trung với điểm (x,y,z). Như vậy , chuyển đổi giữa hệ aìffine và hệ tọa độ chiếu như sau : M(a,b) = M’(a,b,1) (17) '( , , ) , ,1 ,p q p qN p q r N N r r r r             (18) 2.3.6. Các phép toán đường cong trong hệ tọa độ chiếu Phương pháp trình bày công thức của phép cộng và nhân đôi trong hệ tọa chiếu tương tự với hệ tọa độ Affine. Cho P’ = (x1: y1: z1) E’(F2m) , Q’ = (x2: y2: z2) E’(F2m) và P’ ≠ -Q’ trong đó P’ , Q’ thuộc hệ tọa độ quy chiếu. Do P’ = (x1/z1: y1/z1:1), ta có thể áp dụng công thức cộng và nhân cho điểm P(x1/z1: y1/z1) và Q(x2,y2) cho E(F2m) trong hệ Affine để tìm P’ + Q’ = R’ (x’3: y’3:1). Từ đó ta có : 2 ' 3 22 1 B B Ax a A A z     (19) ' ' '1 1 3 3 3 1 1 ( )x yBy x x A z z     Trong đó A = (x2 z1+ x1) và A = (y2 z1+ y1). Đặt z3 = A3z1 và x3 = x’3z3 , y3 = y’3z3 ,nếu P + Q = (x3: y3: z3) thì : x3 = AD, y3 = CD + A2( Bx1 + Ay1) (20) z3 = A3z1 Với C = A + B và D = A2 ( A + a2z1) + z1BC Tương tự 2P = (x3: y3: z3) với x3 = AB , y3 = x14A + B(x12 +y1z1 + A) (21) z3 = A3 34 Trong đó A = x1z1 và B = a6z14 + x14 . Điểm kết quả có thể được chuyển trở lại sang hệ Affine bằng cách nhân với z3-1 . Như vậy sẽ không có thao tác tính nghịch đảo trọng hệ tọa độ chiếu. Do đó chỉ cần 1 phép nghịch đảo sau một dãy các phép cộng và nhân đôi để chuyển sang hệ Affine. So sánh số lượng cá thao tác đối với các phép toán trên đường cong elliptic trọng hệ tọa độ Affine và hệ tọa độ chiếu Tọa độ Affine Tọa độ chiếu Thao tác ESUM EDBL ESUM EDBL Nhân 2 2 13 7 Nghịch đảo 1 1 0 0 2.3.6. Phép nhân đường cong Thuật toán nhân điểm trong hệ tọa đội Affine Input : P E(F2m) và c F2m Output : Q = c x P   0 2 , 0,1 , 1 n i i i n i c b b b     Q ← P For i= n – 1 downto 0 Gán Q ← Q + Q (Affine EDBL) If bi = 1 then Gán Q ← Q + P (Affine ESUM) End if End for Trả về Q Phép nhân được định nghĩa như một dãy các phép cộng : ... c Q c P P P P      35 Thuật toán nhân điểm trong hệ tọa độ chiếu Input : P E(F2m) và c F2m Output : Q = c x P   0 2 , 0,1 , 1 n i i i n i c b b b     Biểu diễn P trong hệ tọa độ chiếu : P’ Gán Q’ ← P’ For i = n -1 downto 0 Q’ ← Q’ + Q’ (Projective EDBL) If bi = 1 then Q’ ← Q’ + P’ (Projective ESUM) End if End for Biểu diễn Q’ trong hệ tọa độ Affine ta được Q Trả về Q 36 2.4 BÀI TOÁN LOGARIT RỜI RẠC TRÊN ĐƯỜNG CONG ELLIPTIC Bài toán logarit rời rạc trên đường cong elliptic (ECDLP): Cho E là một đường cong elliptic và P E là một điểm có bậc n . Cho điểm Q E , tìm số nguyên dương m (2 ≤ m ≤ n-2) thỏa mãn công thức Q = m x P . Hiện nay chưa có thuật toán nào được xem là hiệu quả để giải quyết bài toán này. Để giải bài toán logarit rời rạc trên đường cong elliptic, cần phải kiểm tra tất cả các giá trị m [2...n-2]. Nếu điểm P được chọn lựa cẩn thận với n rất lớn thì việc giải bài toán ECDLP xem như không khả thi. Việc giải bài toán ECDLP khó khăn hơn việc giải quyết bài toán logarit rời rạc trên trường số nguyên thông thường. 37 Chương 3. CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTC 3.1. CHỮ KÝ SỐ 3.1.1. Khái niệm chữ ký số Để chứng thực nguồn gốc hay hiệu lực của một tài liệu (ví dụ: đơn xin học, giấy báo nhập học, ... ), lâu nay người ta dùng chữ ký “tay”, ghi vào phía dưới của mỗi tài liệu. Như vậy người ký phải trực tiếp “ký tay“ vào tài liệu. Ngày nay các tài liệu được số hóa, người ta cũng có nhu cầu chứng thực nguồn gốc hay hiệu lực của các tài liệu này. Rõ ràng không thể “ký tay“ vào tài liệu, vì chúng không được in ấn trên giấy. Tài liệu “số” ( hay tài liệu “điện tử”) là một xâu các bit (0 hay 1), xâu bít có thể rất dài (nếu in trên giấy có thể hàng nghìn trang). “Chữ ký” để chứng thực một xâu bít tài liệu cũng không thể là một xâu bit nhỏ đặt phía dưới xâu bit tài liệu. Một “chữ ký” như vậy chắc chắn sẽ bị kẻ gian sao chép để đặt dưới một tài liệu khác bất hợp pháp. Những năm 80 của thế kỷ 20, các nhà khoa học đã phát minh ra “chữ ký số” để chứng thực một “tài liệu số”. Đó chính là “bản mã” của xâu bít tài liệu. Người ta tạo ra “chữ ký số” (chữ ký điện tử) trên “tài liệu số” giống như tạo ra “bản mã” của tài liệu với “khóa lập mã”. Như vậy “ký số” trên “tài liệu số” là “ký” trên từng bit tài liệu. Kẻ gian khó thể giả mạo “chữ ký số” nếu nó không biết “khóa lập mã”. Để kiểm tra một “chữ ký số” thuộc về một “tài liệu số”, người ta giải mã “chữ ký số” bằng “khóa giải mã”., và so sánh với tài liệu gốc. Ngoài ý nghĩa để chứng thực nguồn gốc hay hiệu lực của các tài liệu số hóa, mặt mạnh của “chữ ký số” hơn “chữ ký tay” là ở chỗ người ta có thể “ký” vào tài liệu từ rất xa trên mạng công khai. Hơn thế nữa, có thể “ký” bằng các thiết bị cầm tay (VD điện thoại di động) tại khắp mọi nơi (Ubikytous) và di động (Mobile),miễn là kết nối được vào mạng. Đỡ tốn bao thời gian, sức lực, chi phí, … “Ký số” thực hiện trên từng bit tài liệu, nên độ dài của “chữ ký số” ít nhất cũng bằng độ dài của tài liệu. Do đó thay vì ký trên tài liệu dài, người ta thường dùng “hàm băm” để tạo “đại diện” cho tài liệu, sau đó mới “Ký số” lên “đại diện” này. 38 Chữ ký thông thường Chữ ký số * Vấn đề ký một tài liệu: Chữ ký chỉ là một phần vật lý của tài liệu * Vấn đề về kiểm tra: Chữ ký được kiểm tra bằng cách so sánh nó với chữ ký xác thực khác. Tuy nhiên, đây không phải là một phương pháp an toàn vì nó dễ bị giả mạo * Vấn đề ký một tài liệu: Chữ ký số không gắn kiểu vật lý vào bức thông điệp nên thuật toán được dùng phải “ không nhìn thấy” theo một cách nào đó trên bức thông điệp. * Vấn đề về kiểm tra Chữ ký số có thể kiểm tra nhờ dùng một thuật toán kiểm tra công khai. Như vậy, bất kì ai cũng có thể kiểm tra được chữ ký số. Việc dùng chữ ký số an toàn có thể chặn được giả mạo 3.1.2. Sơ đồ chữ ký số Sơ đồ chữ ký là bộ năm (P, A, K, S, V ), trong đó: P là tập hữu hạn các văn bản có thể. A là tập hữu hạn các chữ ký có thể. K là tập hữu hạn các khoá có thể. S là tập các thuật toán ký. V là tập các thuật toán kiểm thử. Với mỗi khóa k  K, có thuật toán ký Sig k  S, Sig k : P A, có thuật toán kiểm tra chữ ký Ver k  V, Ver k : P  A đúng, sai, thoả mãn điều kiện sau với mọi x  P, y  A: Đúng, nếu y = Sig k (x) Ver k (x, y) = Sai, nếu y  Sig k (x) 39 Chú ý : Người ta thường dùng hệ mã hóa khóa công khai để lập “Sơ đồ chữ ký số”. Ở đây khóa bí mật a dùng làm khóa “ký”, khóa công khai b dùng làm khóa kiểm tra “chữ ký”. Ngược lại với việc mã hóa, dùng khóa công khai b để lập mã., dùng khóa bí mật a để giải mã. Điều này là hoàn toàn tự nhiên, vì “ký” cần giữ bí mật nên phải dùng khóa bí mật a để “ký”. Còn “chữ ký” là công khai cho mọi người biết, nên họ dùng khóa công khai b để kiểm tra. Ví dụ : Chữ ký số RSA (Đề xuất năm 1978) a. Sơ đồ chữ ký *Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật số nguyên tố lớn p, q, tính n = p * q, công khai n, đặt P = C = Zn Tính bí mật (n) = (p-1).(q-1). Chọn khóa công khai b < (n), nguyên tố với (n). Khóa bí mật a là phần tử nghịch đảo của b theo mod (n): a*b  1 (mod (n). Tập cặp khóa (bí mật, công khai) K = (a, b)/ a, b  Zn , a*b  1 (mod (n)). * Ký số: Chữ ký trên x  P là y = Sig k (x) = x a (mod n), y  A. (R1) * Kiểm tra chữ ký: Verk (x, y) = đúng  x  y b (mod n). (R2) b. Chú ý: - So sánh giữa sơ đồ chữ ký RSA và sơ đồ mã hóa RSA ta thấy có sự tương ứng. - Việc ký chẳng qua là mã hoá, việc kiểm thử lại chính là việc giải mã: Việc “ký số” vào x tương ứng với việc “mã hoá” tài liệu x. Kiểm thử chữ ký chính là việc giải mã “chữ ký”, để kiểm tra xem tài liệu đã giải mã có đúng là tài liệu trước khi ký không. Thuật toán và khóa kiểm thử “chữ ký” là công khai, ai cũng có thể kiểm thử chữ ký được. 40 c. Ví dụ Chữ ký trên x = 2 *Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật số nguyên tố p=3, q=5, tính n = p * q = 3*5 = 15, công khai n. Đặt P = C = Zn = Zn . Tính bí mật (n) = (p-1).(q-1) = 3 * 4 = 8. Chọn khóa công khai b = 3 < (n), nguyên tố với (n) = 8. Khóa bí mật a = 3, là phần tử nghịch đảo của b theo mod (n): a*b  1 (mod (n). * Ký số: Chữ ký trên x = 2  P là y = Sig k (x) = x a (mod n)= 2 3 (mod 15) = 8, y  A. * Kiểm tra chữ ký: Verk (x, y) = đúng  x  y b (mod n)  2  8 b (mod 15). 41 3.2. MỘT SỐ SƠ ĐỒ CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC 3.2.1. Sơ đồ chữ ký ECDSA Để thiết lập sơ đồ chữ ký ECDSA, cần xác định các tham số: lựa chọn đường cong E trên trường hữu hạn Fq với đặc số p sao cho phù hợp, điểm cơ sở G  E(Fq). Một số khuyến nghị khi lựa chọn các tham số: 1. Kích thước q của trường, hoặc q = p (p > 2) hoặc q = 2m. 2. Hai phần tử a, b thuộc Fq xác định phương trình đường cong elliptic: y2 = x3 + ax + b (p>2) hoặc y2 + xy = x3 + ax2 + b (p =2) 3. Hai phần tử xG và yG thuộc Fq xác định điểm cơ sở G = (xG, yG). 4. Bậc n của điểm G với n > 2160 và qn 4 Sinh khóa : 1. Chọn số ngẫu nhiên d trong khoảng [2, n – 1] làm khóa bí mật. 2. Tính Q = dG làm khóa công khai. Ký trên bản rõ m 1. Chọn một số ngẫu nhiên k, 12  nk 2. Tính kG = (x1, y1). 3. Tính r = x1 mod n. Nếu r = 0, quay lại bước 1. 4. Tính k-1 mod n. 5. Tính s = k-1 (m + dr) mod n. Nếu s = 0 quay lại bước 1. 6. Chữ ký trên thông điệp m là (r, s) Kiểm tra chữ ký 1. Kiểm tra r và s có là các số tự nhiên trong khoảng [2, n – 1] không. 2. Tính w = s-1 mod n 3. Tính u1 = mw mod n và u2 = rw mod n 4. Tính X = u1G + u2Q = (xX, yX) 5. Nếu X = O thì phủ nhận chữ ký. Ngược lại tính v = xX mod n. 6. Chữ ký chỉ được chấp nhận nếu v = r. 42 Chứng minh Nếu chữ ký (r, s) trên m là đúng thì s = k-1(m + dr) mod n. k  s-1 (m + dr)  s-1e + s-1 rd  wm + wrd  u1 + u2d (mod n). Vì vậy, u1G + u2Q = (u1 + u2d)G = kG, và vì vậy v = r. 43 3.2.2. Sơ đồ chữ ký Nyberg- Rueppel Giả sử E là một đường cong Elliptic trên trường Zp (p>3 và nguyên tố) sao cho E chứa một nhóm con cyclic H trong đó bài toán logarith rời rạc là “khó”. Với ** pp xP  , ** pp xZExZC  , ta định nghĩa: }:),,,{(  aaEK  với E . Các giá trị  và  là công khai, a là bí mật. Với ),,,(  aEK  chọn một số ngẫu nhiên ||HZk  .Khi đó, với ** 21 ),( pp xZZxxx  ta định nghĩa ),,(),( dckxsig K  trong đó : kyy ),( 21 pxhashyc mod)(1  packd mod exhashtruedcxverK  )(),,(  cdyy ),( 21 pyce mod1 Tất cả các sơ đồ chữ ký đều yêu cầu phải băm văn bản trước khi ký. Chuẩn P1363 của IEEE khuyến nghị dùng SHA-1, được định nghĩa bởi NIST, hoặc RIPEMD-160, được định nghĩa bởi ISO-IEC. Lý do để sử dụng các hàm băm là việc chúng giúp khó tìm được 2 văn bản có cùng giá trị băm, hàm băm giúp chữ ký trên văn bản gốc gọn nhẹ hơn rất nhiều. 44 3.2.3. Sơ đồ chữ ký mù Harn trên EC Chữ ký mù là chữ ký thực hiện trên một văn bản mà người ký hoàn toàn không biết nội dung. Điều này thực hiện được vì người trình ký đã sử dụng một phương pháp nào đó để che dấu nội dung của văn bản gốc để người ký không biết. Để người ký yên tâm, người xin cấp chữ ký phải chứng minh tính hợp lệ của nội dung đã bị che dấu. Sinh khóa Chọn các tham số cho đường cong Elliptic 1. Chọn số nguyên tố p và số nguyên n. Giả sử f(x) là một hàm đa thức trên trường GF(p) bậc n tạo thành trường hữu hạn GF(pn) và a là một nghiệm của f(x) trong GF(pn). 2. Với 2 phần tử a, b của GF(pn), xác định phương trình của E trên GF(pn) ( baxxy  32 trong trường hợp p>3) với 0274 23  ba 3. Với 2 phần tử xp và yp trong GF(pn) xác định một điểm G = (xG, yG) trên E(GF(pn)) (G  O với O là điểm gốc). 4. Giả sử điểm G có bậc q 5. Hàm chuyển c(x) : np n ZpGF )( được cho bởi:     1 0 )( n i i k pcxc npZ ,     1 0 n i i kcx  )( npGF , pci 0 Việc sinh khóa bao gồm: 1. Chọn một khóa bí mật d là số nguyên ngẫu nhiên trong [2, q – 1] 2. Tính khóa công khai Q, là một diểm trên E sao cho Q = dG. Ký mù Giả sử Jerry yêu cầu Tom ký lên một văn bản m0 mà m là đại diện của văn bản này(m = H(m0)với H là một hàm băm nào đó).Giao thức ký được thực hiện như sau: 1. Tom sinh ra cặp khóa ( Rk , ) theo cách sau: chọn ngẫu nhiên ]1,1[  qk và tính ),( kk yxGkR  . Sau đó tính r :     1 0 )( n i i kik pcxcr , trong đó     1 0 n i i kik cx  , pc ki 0 rồi gửi r và R cho Jerry 45 2. Jerry chọn các tham số làm mù ]1,1[,  qba , tính R trên E sao cho R = a R + bG = (xk, yk) và tính r = c(xk) và rarmm  1)( . Sau đó gửi m cho Tom ( m là m sau khi đã bị làm mù). 3. Tom tính )(mod)( qkrmds  , rồi gửi s cho Jerry. 4. Jerry nhận được s , xóa mù để có được chữ ký s trên m bằng cách tính bsas  Cặp (r, s) là một chữ ký ECC trên m. Chứng minh Cặp (r, s) là một chữ ký ECC Harn của thông điệp m và sơ đồ ký trên là một sơ đồ chữ ký mù trên ECC. Việc xác minh tính hợp lệ của chữ ký Harn được thực hiện như sau: 1. Tìm một điểm V trên E sao cho sG – (m + r)Q = (xv, yv). 2. Sử dụng hàm chuyển để tính c(xe) và kiểm tra ))(mod( ? qxcr v . Nếu đúng thì (r, s) được chấp nhận là chữ ký hợp lệ. Để chứng minh giao thức trên thực sự tạo ra chữ ký có tính chất “mù”, chúng ta chỉ ra rằng mỗi người ký có một cặp duy nhất (a, b) là tham số làm mù, với ]1,1[,  qba . Với smrkR ,,,, và một chữ ký hợp lệ (r, s) của m ta có: )(mod))(( 1 qrmrma  )(mod qsasb  Ta phải chứng minh: bGRaR  . Thực vậy, RQrmsGdrGdmGsG GradrarmadGsGkrdmdaGsGGkaGsasGGkabGRa    )( ))(()( 1 46 Ví dụ Xét việc tạo chữ ký mù Harn trên đường cong elliptic y2 = x3 + x + 13 trên trường nguyên tố Z31. Chọn điểm cơ sở G = (9, 10). #E(Z31) = 34 và G là phần tử bậc 34. Khi đó q = 34. Sinh chữ ký Khóa bí mật d = 11, khi đó khóa công khai Q = dG = 11G = (22, 22). Giả sử Jerry có thông điệp m0 với đại là m = 17 và cần Tom ký lên m sao cho Tom không biết nội dung m. 1. Khi nhận được yêu cầu ký từ Jerry, Tom chọn ngẫu nhiên ]1,2[  qk = 20 và tính GkR  = 20P = (26, 10), r = 26. Tom gửi r và R cho Jerry. 2. Jerry chọn các tham số làm mù ]1,1[,  qba với a = 5, b = 7. Tính R trên E với R = a R + bG = 5 R + 7G = 5G = (25, 16), r = 25. Jerry làm mù m thành m với rarmm  1)( = (17 + 25)5-1 – 26 (mod 34) = 30. Jerry gửi m = 30 cho Tom. 3. Tom tính )(mod)( qkrmds  = 11(30 + 26) + 20 (mod 34) = 24. Tom gửi s = 24 cho Jerry. 4. Jerry nhận được s , xóa mù để có được chữ ký s trên m bằng cách tính bsas  =5 x 24 + 7(mod 34)=25. Cặp (25, 25) là chữ ký của Tom trên m=17. Xác minh tính hợp lệ của chữ ký Jerry muốn chứng minh rằng anh ta có chữ ký của Tom trên m = 17 và chữ ký muốn chứng minh chữ ký đó là (25, 25). Các thao tác chứng minh diễn ra như sau: 1. Tìm một điểm V trên E sao cho sG – (m + r)Q = (xv, yv) = 25G – (17 + 25)Q = 25P – 8Q = 25G – 88G = 5G (mod 34) = (25, 16). 2. Kiểm tra r ?  xv. Nếu Jerry cung cấp một chữ ký giả (r’, s’)  (r, s) thì điều kiện kiểm tra r ?  xv không thỏa mãn nên chữ ký sẽ bị phủ nhận. 47 3.2.4. Sơ đồ đa chữ ký mù của Harn trên EC Đa chữ ký hiểu được hiểu là chữ ký được tạo thành bởi nhiều người ký. Có những văn bản cần được ký bởi một số người có thẩm quyền thay vì một người nhằm bảo đảm tính an toàn. Đa chữ ký mù những người ký không biết về nội dung văn bản ký. Sinh khóa Việc chọn các tham số cho đường cong Elliptic tương tự như sơ đồ chữ ký Harn. Chúng ta giả sử rằng có t người ký là Ui, với ti ,.1 . Việc sinh khóa được thực hiện qua các bước: 1. Mỗi người ký Ui chọn ngẫu nhiên một khóa bí mật di là một số nguyên thuộc [1, q – 1] 2. Khóa công khai của người ký Ui là điểm: Qi = diG = ( ii dd yx , ), ti ,.1 3. Khóa công khai cho tất cả người ký là: Q = Q1 +…+ Qt = dG = (xd, yd) với d = d1 + …+ dt (mod q) Ký mù trên m 1. Người ký Ui sinh một lần cặp ( ii Rk , ) bằng cách chọn ngẫu nhiên ]1,2[  qki và tính ),( ii kkii yxGkR  . Ui tính các ir , i = 1,…, t với )( iki xcr  rồi gửi ir và iR cho Ban thư ký. 2. Ban thư ký chọn các tham số làm mù ]1,1[,  qba , tìm điểm R trên E sao cho ),( kk yxbQRaR  trong đó tRRR  1 và tQQQ  1 . Ban thư ký tính ))(mod( qxcr k và rabrmm  1)( . Sau đó, gửi m và r đến cho từng người ký Ui. 3. Ui tính chữ ký )(mod)( qkrmds iii  , i=1,…, t. Sau đó gửi is tới Ban thư ký. 4. Ban thư ký tính ),()( ii eeii yxQrmGs  và kiểm tra ))(mod( ? qxcr iei  , i=1,…, t. Chữ ký mù nhóm ECC là cặp (r, s) trong đó: )(mod...1 qsss t và )(mod qass  . 48 Chứng minh Cặp (r, s) là một chữ ký do nhiều thành viên ký trên thông điệp m – nó cũng là đa chữ ký mù. Việc xác minh tính hợp lệ của đa chữ ký (r, s) của thông điệp m được thực hiện như sau: 1. Tìm một điểm trên E sao cho ),()( ee yxQrmsG  . 2. Sử dụng hàm chuyển để tính c(xe) và kiểm tra ))(mod( ? qxcr e . Nếu đúng thì (r, s) được chấp nhận. Dễ dàng để xác minh rằng RQrmsG  )( Để chứng minh rằng giao thức ký trên tạo ra chữ ký có tính chất “mù” ta phải chỉ ra rằng với mỗi người ký tồn tại duy nhất cặp (a, b) là các tham số làm mù với ]1,1[,  qba . Với các rmsrkR iiii ,,,,, và cặp chữ ký hợp lệ (r, s) của thông điệp m, chúng ta có: )(mod1 qssa  , )(mod)( qrmarmb  Ta phải chỉ ra rằng bQRaR  . Ta có: RQrmsG QrmGsaQrmQrmaQrmGsa QrmarmRRabQRa t i t i ii t        )( )()()()))(( ))()(()..( 1 1 1 49 3.3. MỘT SỐ PHƯƠNG PHÁP TẤN CÔNG HỆ ECC 3.3.1. Phương pháp tấn công “baby - step giant - step” Đây là phương pháp tấn công đầu tiên lên hệ mật mã ECC do Shanks đưa ra, và thực hiện với thời gian là hàm mũ. Nó giải bài toán DLP trong trường nguyên tố Zp được mở rộng cho bài toán EDLP. Bài toán: Tìm k sao cho kG = Q trên E(Fq) với #E(Fq) = N, giả sử k tồn tại thực sự. Thuật toán 1. Chọn số nguyên m > N 2. Tính mG 3. Với i = 0 đến i = m-1 tính (và lưu lại) iG 4. Với j = 0 đến j = m-1 tính (và lưu lại) Q – jmG 5. Sắp xếp danh sách trong bước 3 và 4 theo một thứ tự nhất định 6. So sánh các danh sách ở các bước 3 và 4 cho đến khi tìm được cặp i, j thỏa mãn iG = Q – jmG 7. Kết quả trả lại là k  i + jm (mod N) Chứng minh Vì chúng ta chọn m thỏa mãn m2 > N nên sẽ có k < m2. Đặt k0 k (mod m), mk  00 . Đặt k1 = (k – k0) / m. Ta sẽ có: k = k0 + mk1, với mk  10 Trong thuật toán trên ta thử tìm tất cả i thuộc khoảng của k0 và tất cả j trong khoảng của k1 cho đến khi tìm được i, j thoả mãn iG = Q – jmG  (i + jm)G =Qhay k = i + jm. Vì k tồn tại nên k0, k1 tồn tại. Độ phức tạp thời gian Bước 1 cần O(log N). Bước 2 và bước 3 cần O(m+1) = O( N ). Bước 4 cần O( N ). Thuật toán sắp xếp trong bước 5 được thực hiện trong O(log( N ) N ) thời gian. Bước 6 được thực hiện trong O( N ) thời gian. Bước 7 cũng được thực hiện trong O( N ) thời gian. Bỏ qua các yếu tố logarith rời rạc ( N đủ lớn để bài toán DLP là khó giải), thì thời gian thực hiện của thuật toán là hàm mũ của N . Thuật toán này quá chậm vì thời gian là hàm mũ của độ dài dữ liệu vào N. 50 3.3.2. Phương pháp tấn công MOV Phương pháp tấn công MOV (tên của 3 nhà khoa học Menezes, Okamoto, và Vanstone) làm yếu bài toán logarit rời rạc trên đường cong elliptic E(Fq) thành bài toán logarith rời rạc trên trường mqF với m nào đó. Khi đó có thể tấn công bằng tấn công chỉ số, nhất là khi m nhỏ. Chúng ta bắt đầu bằng định nghĩa cặp Weil cho các đường cong elliptic E(F). Xét đường cong elliptic E(F) và N là một số nguyên không là ước của đặc số của F. Đặt E[N] là tập hợp các điểm trên đường cong E.  1|  NN xFx . Như vậy, N là nhóm các nghiệm thứ N trong F. Vì đặc số của F không chia hết cho N, xN = 1 không có nghiệm kép, nghĩa là có N nghiệm phân biệt trong F. Định nghĩa Một cặp Weil là một ánh xạ: ][][: NxENEeN  n thỏa mãn: 1. eN là song tuyến tính với mọi biến 2. eN là không suy biến với mọi biến. Nghĩa là, nếu eN(S, T) = 1 với mọi S, thì T = O, và nếu eN (S, T) = 1 với mọi T thì S = O. 3. eN (T, T) = 1 T 4. eN(T, S) = eN(S, T)-1  S, T 5. Nếu  à một phần tử đặc biệt của F đóng vai trò là các hệ số của E, thì eN( S,  T) =  (eN(S, T))  S, T 6. Nếu  là một separable endomorphism của E thì eN( (S),  (T)) = eN(S, T)deg   S, T Bài toán Tìm k thỏa mãn kG = Q trên E(Fq) với #E(Fq) = N và giả sử k tồn tại. Sử dụng phép làm yếu bài toán logarith rời rạc trên đường cong E(Fq) thành bài toán logarith rời rạc trên mqF 51 Thuật toán Khi (d1, d2, …,dk) = N, thực hiện các bước sau, sau mỗi bước tăng i lên 1 1. Chọn một điểm ngẫu nhiên )( mqi FES  . 2. Tính bậc Mi của Si 3. Đặt di = gcd(Mi, N) và Ti = (Mi/di)Si. 4. Đặt i1 = eN(G, Ti), i2 =eN(Q, Ti). 5. Giải bài toán logarith rời rạc iki1 = i2 trong trường mqF và tìm được ki (mod di) Sử dụng các giá trị ki (mod di) để tìm k (mod N) với k ki (mod di) i . Giá trị k chính là kết quả cần tìm. Chứng minh Ở bước 1 và 2, chúng ta chọn một điểm và tính bậc của nó. Bước 3 tìm Ti . Đặt ),( iN TRe với R là một điểm tùy ý trên E( mqF ) Khi đó: 1),(),(),(),(  OReSMRedTReTRe NiiNiN d iN d , và vì 21 , mqd F  rồi giải ik ii 12   trong mqF Đặt kG = Q, và định nghĩa li thỏa mãn k  li (mod di). Ta có: eN(kG, Ti) = eN(Q, Ti)  eN(G, Ti)k = eN(Q, Ti)  iki 21   Vì 11 di nên i k ii 12   (mod di)  li ki (mod di) và k phải bằng ki (mod di). Như vậy, việc tìm ki sẽ phục vụ việc tìm k. Độ phức tạp thời gian Khi có các ki việc tìm k là dễ dàng, vì vậy thời gian chạy của thuật toán phụ thuộc vào việc tìm ki. Thời gian tìm ki phụ thuộc vào độ lớn của trường mqF . Nếu m càng lớn thì tính toán càng phức tạp. Không có một tiêu chuẩn chung để chọn m phù hợp cho tất cả các đường cong elliptic. 52 Quay trở lại bài toán tính độ phức tạp, dựa trên đặc điểm E(F mq )  21 nn ZZ  với n1, n2 thỏa mãn n1|n2. B1, B2 là các điểm trên E(F mq ) với các bậc n1 và n2. Bất kỳ điểm Si nào tìm được cũng có thể biểu diễn dưới dạng a1B1 + a2B2 với a1, a2 nào đó. Giả sử p là một số nguyên tố pe||N. Khi đó, pe|n2. Nếu p không nguyên tố cùng nhau với a2 thì pe|n2  pe|Mi với Mi là bậc của Si. Suy ra pe|di = gcd(Mi, N). Vì Si được chọn ngẫu nhiên nên a2 cho Si cũng ngẫu nhiên, do đó xác suất để p không nguyên tố cùng nhau với a2 là 1 – 1/p. Suy ra, xác suất để : pe|di1–1/p với mọi i và với mọi pe||N. Xác suất này đủ thấp để chỉ có một vài di cần cho pe|lcm (d1, d2,…, dk) đúng với mọi p. Vì vậy chúng ta không cần lặp các bước của thuật toán quá nhiều lần. MOV là thuật toán hàm mũ nhỏ đầu tiên để giải bài toán EDLP với k nhỏ. Nó dựa vào tính đẳng cấu giữa đường cong elliptic và trường hữu hạn khi gcd(#E(Fq), q) = 1. Vì vậy, tính hiệu quả của nó giới hạn trong một lớp các đường cong elliptic là lớp các đường cong supersingular vì tồn tại k  6 cho các đường cong này. Với các đường cong elliptic khác (các đường cong nonsupersingular), k quá lớn để áp dụng tấn công MOV. Miyaji chứng minh rằng phép làm yếu trên hiệu quả cho các đường cong elliptic trên trường rF2 . Còn các đường cong elliptic trên trường Fp (với p là số nguyên tố lớn) tránh được cách tấn công này. Hơn nữa, Miyaji đề xuất một cách xây dựng một đường cong elliptic để việc làm yếu EDLP về DLP là không thể. Bởi vậy, không phải mọi hệ mật mã trên đường cong elliptic đều có thể bị tấn công bởi phương pháp MOV. 53 Chương 4 . ỨNG DỤNG CHỮ KÝ SỐ TRÊN ĐƯỜNG CONG ELLIPTIC Các hệ mật trên đường cong elliptic (ECC) có thể được sử dụng hiệu quả trong các thiết bị không dây như là Cell phone , PDA , Smart card... Vì ECC có thể hoạt động trên các thiết bị nhỏ (bộ nhớ nhỏ, bộ tính toán bé, số “cổng” ít, ít năng lượng). Mà vẫn đảm bảo độ mật cao. Với ECC chỉ cần sử dụng các khóa có độ dài nhỏ, nhưng vẫn hiệu quả như các hệ mật khác có độ dài gấp nhiều lần. Ví dụ hệ mật RSA dùng khóa có độ dài 1024 bit , nhưng ECC chỉ cần khóa 160 bit đã mang lại độ mật tương tự. Mặt khác, ECC còn tính nhanh hơn gấp 4 lần. Khóa RSA 1024bit có thể thỏa đáng giao dịch ngày nay, nhưng đến cuối thập kỷ này, để bảo đảm độ mật cần thiết, phải sử dụng khóa RSA 2048 bit. Trong khi đó, để có được độ mật tương tự , ECC chỉ cần khóa 203 bit. Hơn thế nữa thời gian tính toán chỉ bằng 1/10 , chưa kể đến việc ECC sinh khóa nhanh hơn RSA. Các hoạt động kinh tế xã hội (thanh toán, rút tiền, bỏ phiếu, đấu thầu , góp ý kiến) diễn ra mọi nơi mọi lúc. Các thiết bị cầm tay có kết nối an toàn từ xa (Smart card , E-token..). Chắc chắn sẽ được sử dụng nhiều để tiết kiệm thời gian và sức lực. Khi đó không thể quên công nghệ ECC. Hai ứng dụng là phổ biến trên thế giới có thể áp dụng ECC, đó là Bỏ phiếu điện tử và Hệ thống tiền điện tử. 54 4.1.ỨNG DỤNG TRONG BỎ PHIẾU ĐIỆN TỬ Theo phương thức bỏ phiếu điện tử , mỗi lá phiếu phải có Thông tin định danh. Nó có thể là một con số x nào đó và phải khác nhau. Trên mỗi lá phiếu phải có chữ ký trên số định danh x , thì lá phiếu mới mới có giá trị để bầu cử. Nếu cử tri chuyển ngay Số định danh x cho ban kiểm phiếu ký thì lập tức họ xác định mối liên hệ giữa cử tri và x (ví dụ qua địa chỉ Internet nơi người gửi ). Đó là điều cử tri không mong muốn gây rắc rồi sau này. Để tránh tình huống này, cử tri đổi x thành y trước khi đưa cho ban kiểm phiếu ký xác nhận. Ban kiểm phiếu ký vào y, mà không biết đó là số định danh x đã che dấu (làm mù). Họ trao chữ ký trên y là z cho cử tri. Cử tri xóa mù trên z sẽ được chữ ký ban kiểm phiếu trên số định danh x, như vậy cử tri có quyền bầu cử. Để phòng tránh sự gian lận thông đồng giữa một người nào đó trong ban kiểm phiếu với cử tri. Hệ thống dùng “Đa chữ ký mù” để bảo đảm sự nhất trí cao khi cấp quyền bỏ phiếu cho cử tri. 4.1.1. Quy trình bỏ phiếu điện tử Giai đoạn chuẩn bị Các thành phần kỹ thuật của hệ thống bỏ phiếu cũng như chuẩn bị cơ cấu tổ chức. Người kiểm phiếu và nhân viên bầu cử được chỉ định. Các nhân viên bầu cử thực hiện tất cả các bước trong quá trình bỏ phiếu như điều hành hệ thống máy tính, cung cấp dữ liệu cần thiết cho hệ thống. Người kiểm tra cuộc bầu cử sẽ điều khiển toàn bộ quá trình bầu cử bằng cách chỉ đạo các nhân viên bầu cử nhờ việc kiểm tra sự hoạt động của hệ thống máy tính. Hơn nữa, BKP cũng được chỉ định. Đây là người chịu trách nhiệm về kết quả bầu cử. Cuối cùng, danh sách các cử tri cũng được thiết lập. Trong bước này, quan trọng nhất là cơ chế định danh người gửi dùng để sử dụng trong quá trình bỏ phiếu của cử tri. Giai đoạn bỏ phiếu Giai đoạn các cử tri thực hiện bỏ phiếu. Các cử tri phải có một hình thức định danh tính hợp lệ của lá phiếu. Thêm vào đó, một vài kỹ thuật (mã hoá) cần được áp dụng để bảo đảm tính toàn vẹn của lá phiếu. Giai đoạn Kiểm phiếu và thông báo kết quả BKP sẽ tính toán kết quả dựa vào các lá phiếu đã bỏ, sau đó sẽ công bố kết quả. 55 4.1.2. Sử dụng ECC trong bỏ phiếu điện tử 1 .Cấp quyền bầu cử Khi đã được kiểm traCử tri cần BĐK ký trên bí danh của mình. BĐK sẽ sử dụng sơ đồ chữ ký mù Harn để ký như sau: Sơ đồ 4.4.1. Sơ đồ ký mù của BĐK khi cấp quyền bầu cử cho cử tri 1. Cử tri gửi ID m của mình đến BĐK để xin cấp chữ ký. 2. BĐK có cặp khóa công khai/ bí mật trên đường cong elliptic là (d, Q). Khi có yêu cầu ký, BĐK chọn ngẫu nhiên ]1,2[  qk và tính ),( kk yxGkR  . Tính     1 0 )( n i i kik pcxcr , trong đó     1 0 n i i kik cx  , pc ki 0 . Gửi r và R cho cử tri. 3. Cử tri chọn các tham số làm mù ]1,1[,  qba , tính R trên E sao cho R = a R +bG = (xk, yk) và tính r = c(xk) và rarmm  1)( . Sau đó gửi m cho BĐK (m là m sau khi đã bị làm mù). 4. BĐK ký mù (ký trên văn bản đã bị làm mù): )(mod)( qkrmds  , rồi gửi s cho cử tri.Jerry nhận được s , xóa mù để có được chữ ký s trên m bằng cách tính bsas  Cặp (r, s) là một chữ ký ECC trên định danh m của cử tri. Để tăng tính an toàn và công bằng của cuộc bầu cử nhằm tránh gian lận tại giai đoạn đăng ký (cấp quyền bầu cử cho những cử tri không hợp lệ), nên thiết lập BĐK gồm t thành viên (ít nhất là 2). Khi đó, để ký lên định danh của cử tri, t thành viên này có thể dùng giao thức đa chữ ký mù 3.2.4 của Harn để thực hiện việc ký. 2. Bỏ phiếu Sau khi đã đăng ký và được cấp quyền bầu cử, cử tri sẽ tiến hành bỏ phiếu và giả sử lá phiếu của cử tri thứ i là vi. Cử tri tiến hành các bước như sau: 56 1. Nhúng nội dung của lá phiếu lên E, khi đó vi được thể hiện thành một điểm (Pm)iE. Cử tri phải mã hóa Pm bằng khóa công khai của BKP. 2. Giả sử khóa bí mật của BKP là aT thì khóa công khai sẽ là aTG. Cử tri chọn ngẫu nhiên ri và Pm được mã hóa thành một cặp điểm trên E: Vi = (C1, C2) = (riG,( Pm)i + ri(aTG) 3. Cử tri gửi điểm Vi đến BKP. 3. Kiểm phiếu Khi các lá phiếu được chuyển về BKP, nó sẽ được trộn bằng một máy trộn ngẫu nhiên, nhằm ngăn chặn các tiêu cực trong quá trình bỏ phiếu. BKP nhận được các Vi = (C1, C2). Do tính chất đồng cấu của hệ mã ECC được sử dụng, BKP không cần giải mã từng lá phiếu mà có thể tính tổng các lá phiếu đã mã hóa rồi từ đó tính được kết quả cuối cùng của cuộc bỏ phiếu. Để giải mã từng lá phiếu, BKP tính: C2 – aT(C1) = Pm + k(aTG) – aT(kG) = Pm Tuy nhiên, không giải mã từng lá phiếu, BKP vẫn tính được kết quả cuộc bầu cử theo công thức:      N i iT N i N i im CaCP 1 1 1 1 2 57 4.2. ỨNG DỤNG TRONG HỆ THỐNG TIỀN ĐIỆN TỬ Một đồng tiền điện tử C có 2 thông tin quan trọng nhất : Số Seri và giá trị của đồng tiền. Cũng như đồng tiền thông thường(bằng giấy). Hệ thống phải bảo đảm các yêu cầu sau: Ngần hàng phát hành đồng tiền C “khó” nhận biết đồng tiền này(ví dụ : Số seri) của người mua hàng đã rút ra từ tài khoản của họ. Ngân hàng thu nạp đồng tiền C cũng khó thể biết đồng tiền C đã được nhận từ người bán. Mặt khác người bán hàng khó thể biết C được rút từ tài khoản nào. Để thực hiện yêu cầu trên, hiện nay người ta dùng “Chữ ký mù” để ký lên đồng tiền C. Như vậy tiền điện tử C không lưu lại dấu vết của những ai đã “tiêu” (Spending) nó. Trên thực tế đồng tiền C không chỉ do một ngân hàng phát hành, nó có thể là đồng tiền chung của nhiều ngân hàng. Vì vậy nó phải mang dấu ấn của các ngân hàng liên quan. Trong trường hợp này Tổ chức liên ngân hàng sẽ thống nhất một “Đa chữ ký mù” để ký lên đồng tiền C. Quá trình giao dịch sẽ chia thành bốn giai đoạn: 4.2.1. Tạo tiền ecash 1. Sau khi biết được số tiền cần phải thanh toán, phần mềm tại máy khách hàng sẽ sinh ra dãy số ngẫu nhiên, dãy số này được xem như là dãy số tiền tương trưng cho số tiền cần phải rút từ ngân hàng. Một thừa số mù sẽ được đưa vào dãy số, thừa số mù này sẽ khiến cho ngân hàng không thể lưu giữ danh sách dãy số tiền và không biết được nó được tiêu xài ở đâu. 2. Dãy số đã được làm mù này sẽ được gửi đến ngân hàng mà khách hàng đã có tài khỏan trước đấy. 3. Ngân hàng sẽ kiểm tra thông tin được gửi đến. Sau đó ngân hàng sẽ ký lên thông điệp(dãy số), vì dãy số đã được làm mù nên ngân hàng sẽ không biết nó là của ai, tại thời điểm đấy tài khoản của khách hàng sẽ bị trừ một khoảng tương ứng. 4. Ngân hàng gửi dãy số sau khi được ký đến khách hàng. 5. Khách hàng sẽ giải mù những dãy số này, như vậy dãy số cộng với chữ ký của ngân hàng đến lúc này thực sự trở thành những đồng tiền số có giá trị và giá trị của chúng được bảo đảm bởi ngân hàng, và những đồng tiền số này sẽ chứa trên máy tính của người sửa dụng. 58 4.2.2 Tiêu tiền ecash 1. Khách hàng gửi một yêu cầu mua sắm tới Người bán hàng. 2. Người bán hàng gửi một yêu cầu ngược đến cyberwallet software(số tiền cần thanh toán, thông tin về sản phẩm yêu cầu). 3. Khách hàng xác nhận giao dịch và đồng ý giao dịch thì phần mềm sẽ thu nhập những đồng tiền cần thiết đủ số tiền yêu cầu . 4. Chuyển tiền đến người bán hàng 4.2.3 Đổi tiền 1. Trước khi chấp nhận thanh toán này, Người bán hàng phải kiểm tra tính hợp lệ của những đồng tiền số bằng cách gửi chúng đến ngân hàng. 2. Ngân hàng kiểm tra tính hợp lệ của những đồng tiền số và đồng thời xem nó có được tiêu lần thứ hai không bằng cách dựa vào dữ liệu lưu trữ của ngân hàng. Nếu những đồng tiền là hợp lệ, Ngân hàng sẽ phá huỷ những đồng tiền số này, đồng thời lưu dãy số này vào dữ liệu của những tiền đã sử dụng. Và chuyển một lượng tiền đến tài khoản của người bán. 4.2.4 Kết thúc giao dịch Sau khi những đồng tiền đã được kiểm tra hợp lệ, người bán hàng gửi một biên nhận đến khách hàng và giao dịch tài chính được hoàn thành . 59 KẾT LUẬN Hệ thống mã hóa khóa công cộng ra đời đã giải quyết các hạn chế của mã hóa quy ước. Mã hóa khóa công cộng sử dụng một cặp khóa, một khóa (thông thường là khóa riêng) dùng để mã hóa và một khóa (khóa riêng) dùng để giải mã. Mã hóa khóa công cộng giúp tránh bị tấn công khi trao đổi khóa do khóa để giải mã (khóa riêng) không cần phải truyền hoặc chia sẻ với người khác. Ngoài ra,mỗi người chỉ cần sở hữu một cặp khóa công cộng – khóa riêng và người gởi thông tin chỉ cần giữ khóa công cộng của người nhận do đó số lượng khóa cần phải quản lý giảm khá nhiều. Mỗi người chỉ cần lưu trữ bảo mật một khóa riêng của chính mình. Tuy nhiên, do nhu cầu mã hóa và giải mã bằng hai khóa khác nhau trong cùng một cặp khóa nên để bảo mật, kích thước khóa công khai – khóa riêng lớn hơn rất nhiều so với khóa công khai. Do đó tốc độ mã hóa khóa công cộng chậm hơn tốc độ mã hóa khóa quy ước. Tốc độ mã hóa bằng phần mềm của thuật toán DES nhanh hơn khoảng 100 lần so với mã hóa RSA với cùng mức độ bảo mật. Mã hóa khóa công khai dựa trên hai vấn đề lớn của toán học là bài toán logarit rời rạc và bài toán phân tích thừa số của số nguyên. Phương pháp RSA dựa trên bài toán phân tích thừa số của số nguyên tố và đã được đưa ra từ cuối thập niên 70. Phương pháp ECC dựa trên bài toán logarit rời rạc trên trường số của đường elliptic curve (ECDLP) chỉ mới được đưa ra từ năm 1985. Một ưu điểm của ECC là khả năng bảo mật cao với kích thước khóa nhỏ dựa vào mức độ khó giải quyết của vấn đề ECDLP. Đây chính là một tính chất rất hữu ích đối với xu hướng ngày nay là tìm ra phương pháp tăng độ bảo mật của mã hóa khóa công cộng với kích thước khóa được rút gọn. Kích thước khóa nhỏ hơn giúp thu gọn được kích thước của chứng nhận giao dịch trên mạng và giảm kích thước tham số của hệ thống mã hóa. Kích thước khóa nhỏ giúp các hệ thống bảo mật dựa trên ECC giảm thời gian tạo khóa.Thời gian tạo khóa thường rất lớn ở hệ thống RSA. Do có kích thước khóa nhỏ và khả năng phát sinh khóa rất nhanh nên ECC rất được quan tâm để áp dụng cho các ứng dụng trên môi trường giới hạn về thông lượng truyền dữ liệu, giới hạn về khả năng tính toán, khả năng lưu trữ. ECC thích hợp với các thiết bị di động kỹ thuật số như handheld, PDA, điện thoại di động và thẻ thông minh (smart card). 60 Các hệ thống ECC đã và đang được một số công ty lớn về viễn thông và bảo mật trên thế giới quan tâm phát triển. Nổi bật trong số đó là Certicom (Canada) kết hợp với Đại học Waterloo đã nghiên cứu và xem ECC như là chiến lược phát triển bảo mật chính của công ty. Certicom cung cấp dịch vụ bảo mật dựa trên ECC. Ngoài ra, một số công ty khác như Siemens (Đức), Matsushita (Nhật), Thompson (Pháp) cũng nghiên cứu phát triển ECC. Mới đây, RSA Security Laboratory – phòng thí nghiệm chính của RSA – đã bắt đầu nghiên cứu và đưa ECC vào sản phẩm của mình. Tuy nhiên, ECC vẫn có một số hạn chế nhất định. Hạn chế lớn nhất hiện nay là việc chọn sử dụng các tham số đường cong và điểm quy ước chung như thế nào để thật sự đạt được độ bảo mật cần thiết. Hầu hết các đường cong được đưa ra đều thất bại khi áp dụng vào thực tiễn. Do đó hiện nay số lượng đường cong thật sự được sử dụng không được phong phú. NIST đề xuất một số đường cong elliptic curve đã được kiểm định là an toàn để đưa vào sử dụng thực tế trong tài liệu FIPS 186-2. Ngoài ra, đối với các tham số mang giá trị nhỏ, mức độ bảo mật của ECC không bằng RSA (khi e = 3). Đối với một số trường hợp RSA vẫn là lựa chọn tốt do RSA đã chứng minh được tính ổn định trong một khoảng thời gian khá dài. ECC vẫn còn non trẻ và cần được kiểm định trong tương lai tuy nhiên ECC cung cấp khả năng ứng dụng rất lớn trong lĩnh vực mã hóa khóa công cộng trên các thiết bị di động và smart card. Tương lai ECC sẽ được nghiên cứu đưa vào thực tiễn phổ biến hơn. Kết quả chính của khóa luận là : 1. Tìm hiểu , nghiên cứu tài liệu để hệ thống lại các vấn đề sau :  Khái niệm đường cong Elliptic  Chữ ký số trên đường cong Elliptic 2. Nghiên cứu tài liệu và thực tế để hiểu biết ứng dụng của chữ ký số trên ECC vào bỏ phiếu điện tử và dùng tiền điện tử. 61 TÀI LIỆU THAM KHẢO [1] PGS.TS Trịnh Nhật Tiến, 2008. Giáo trình An toàn dữ liệu. Trường Đại học công nghệ – ĐHQGHN. [2] ThS. Trương Thị Thu Hiền, 2006. Hệ mật đường cong elliptic và ứng dụng trong bỏ phiếu điện tử. Trường Đại học công nghệ – ĐHQGHN. [3] TS. Dương Anh Đức, 2005. Mã hóa và ứng dụng. Trường Đại học khoa học tự nhiên– Đại học Quốc gia thành phố Hồ Chí Minh. [4] PGS.TS Trịnh Nhật Tiến, ThS Trương Thị Thu Hiền, 2005. Chữ ký mù bội trên đường cong elliptic và ứng dụng. Trường Đại học công nghệ – ĐHQGHN. [5] Constantin Popescu, 1999, Blind Signature and Blind Multisignature Schemes using Elliptic Curves [6] Peter Landrock, 2005, Practical Electronic Voting Schemes, ECC conference, Copenhagen [7] Thomas Coffee, 2004, Elliptic Curves and Modern Cryptosystems. [8] Joe Hurd, course notes 2005, Elliptic Curve Cryptography – A case study in formalization using a higher order logic theorem prover, Oxford University. [9] [10] [11]