›

Luận văn Hệ mật đường cong elliptic

pdf 34 trang yendo 6830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Hệ mật đường cong elliptic", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_he_mat_duong_cong_elliptic.pdf

Nội dung text: Luận văn Hệ mật đường cong elliptic

  1.  Luận văn Hệ mật đường cong elliptic , tháng năm
  2. Đồ án tốt nghiệp Hệ mật đường cong elliptic MỤC LỤC MỤC LỤC 1 LỜI CẢM ƠN 2 MỞ ĐẦU 3 CHƢƠNG 1 5 CƠ SỞ TOÁN HỌC 5 1.1. Phƣơng trình đồng dƣ bậc hai và thặng dƣ bậc hai 5 1.2. Nhóm 9 1.3. Trƣờng 10 1.4. Trƣờng hữu hạn 11 CHƢƠNG 2 12 ĐƢỜNG CONG ELLIPTIC 12 2.1. Mở đầu và đặt bài toán 12 2.2. Đƣờng cong elliptic trên trƣờng hữu hạn 14 2.3. Các phép toán trên đƣờng cong Elliptic 15 2.4. Đếm số điểm trên đƣờng cong elliptic trên trƣờng Fq 17 2.5. Phƣơng pháp chọn đƣờng cong Elliptic phù hợp và điểm cơ sở 18 2.5.1. Trƣờng K 18 2.5.2. Dạng của đƣờng cong elliptic 19 2.5.3. Phƣơng pháp lựa chọn 19 CHƢƠNG 3 21 HỆ MẬT ĐƢỜNG CONG ELLIPTIC 21 3.1. Mở đầu và đặt bài toán 21 3.2. Nhúng bản rõ lên đƣờng cong 22 3.3. Logarit rời rạc trên đƣờng cong Elliptic( Discrete logarithm on Elliptic) 24 3.4. Vấn đề trao đổi khoá Diffie- Hellman(D- H) trên Elliptic 24 3.5. Hệ mât mã hoá Elgamal trên đƣờng cong Elliptic 25 CHƢƠNG 4 27 MỘT VÀI ỨNG DỤNG 27 4.1. Lƣợc đồ chữ ký số trên đƣờng cong elliptic (Elliptic Curve Signature Algorithm ) - ECDSA 27 4.1.1. Lƣợc đồ ký ECDSA 27 4.1.2. Độ an toàn của sơ đồ chữ ký ECDSA 28 4.2. Một số chuẩn sử dụng hệ mật ECC 29 KẾT LUẬN 32 TÀI LIỆU THAM KHẢO 33 Phan Thị Thu Hiền - 1 - Lớp CT702
  3. Đồ án tốt nghiệp Hệ mật đường cong elliptic LỜI CẢM ƠN Em xin bày tỏ lòng biết ơn tới TS Hồ Văn Canh đã tận tình hƣớng dẫn và cung cấp những tài liệu quý báu để em hoàn thành luận văn này. Em xin chân thành cảm ơn các Thầy cô giáo khoa công nghệ thông tin trƣờng Đại Học Dân Lập Hải Phòng đã nhiệt tình giảng dạy chúng em trong 4 năm học. Tôi cũng xin chân thành cảm ơn các bạn bè đồng nghiệp đã giúp đỡ tôi trong quá trình học tập và hoàn thành tốt luận văn này! Phan Thị Thu Hiền - 2 - Lớp CT702
  4. Đồ án tốt nghiệp Hệ mật đường cong elliptic MỞ ĐẦU Ngày nay với sự phát triển mạnh mẽ của công nghệ thông tin, truyền thông nói chung và Internet nói riêng đã giúp cho việc trao đổi thông tin nhanh chóng, dễ dàng, E-mail cho phép ngƣời ta nhận hay gửi thƣ ngay trên máy tính của mình, E-business cho phép thực hiện các giao dịch trên mạn. Do vậy một vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể là sai lệch, có thể giả mạo. Điều đó có thể ảnh hƣởng tới các tổ chứa, các công ty hay cả một quốc gia. Những bí mật kinh doanh, tài chính là mục tiêu của các đối thủ cạnh tranh. Những tin tức về an ninh quốc gia là mục tiêu của các tổ chức tình báo trong và ngoài nƣớc. Để giải quyết tình hình trên an toàn thông tin đƣợc đặt ra cấp thiết. Kỹ thuật mật mã là một trong những giải pháp của an toàn truyên thông. Kỹ thuật này có từ ngàn xƣa nhƣng nó đơn giản, ngày nay khi có mạng máy tính ngƣời ta dùng mật mã hiện đại. Các nhà khoa học đã phát minh ra những hệ mật mã nhằm che dấu thông tin cũng nhƣ là làm rõ chúng để tránh sự giòm ngó của những kẻ cố tình phá hoại nhƣ các hệ mật: RSA, Elgamal mặc dù cũng rất an toàn nhƣng có độ dài khoá lớn nên trong một số lĩnh vực không thể ứng dụng đƣợc. Chính vì vậy ngƣời ta đã phát minh một hệ mật đó là hệ mật trên đƣờng cong elliptic, hệ mật này đƣợc đánh giá là hệ mật có độ bảo mật an toàn cao và hiệu quả hơn nhiều so với hệ mật công khai khác, nó đã đƣợc ứng dụng trên nhiều lĩnh vực và đƣợc sử dụng nhiều nơi trên thế giới tuy nhiên còn mới mẻ ở Việt Nam. Trong tƣơng lai gần Hệ mật trên đƣờng cong Elliptic sẽ đƣợc sử dụng một cách phổ biến và thay thế những hệ mật trƣớc nó. Phan Thị Thu Hiền - 3 - Lớp CT702
  5. Đồ án tốt nghiệp Hệ mật đường cong elliptic Vì lý do đó, em đã chọn đề tài “Hệ mật đƣờng cong elliptic” để nghiên cứu, tìm hiểu nhằm tiến tới khai thác hệ mật này phục vụ cho bảo mật thông tin trong thực tế. Luân văn này gồm 4 chƣơng . Chƣơng 1: Cơ sở toán học . Chƣơng 2: Hệ mật mã . Chƣơng 3: Đƣờng cong Elliptic . Chƣơng 4: Hệ mật đƣờng cong Elliptic . Chƣơng 5: Một vài ứng dụng Nhƣng trong báo cáo này em trình bày tóm tắt nội dung chính trong đề tài:”Hệ mật đƣờng cong elliptic”. Phan Thị Thu Hiền - 4 - Lớp CT702
  6. Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƢƠNG 1 CƠ SỞ TOÁN HỌC 1.1. Phƣơng trình đồng dƣ bậc hai và thặng dƣ bậc hai Ta xét phƣơng trình đồng dƣ bậc hai có dạng nhƣ sau: x2 ≡ a (mod n) Trong đó n là số nguyên dƣơng, a là số nguyên với gcd(a, n) ≡ 1, và x là ẩn số. Phƣơng trình đó không phải bao giờ cũng có nghiệm, khi nó có nghiệm thì ta gọi a là thặng dƣ bậc hai mod n. Ngƣợc lại thì a gọi là một bất thặng dƣ bậc hai mod n. Tập các số nguyên nguyên tố với n đƣợc phân hoạch thành hai tập con. Tập Qn các thặng dƣ bậc hai mod n, và tập các bất thặng dƣ bậc hai mod n. Tiêu chuẩn Euler Khi p là số nguyên tố, số a là thặng dƣ bậc 2 mod p nếu và chỉ nếu a(p- 1)/2 ≡ 1 (mod p) Ký hiệu Legendre Cho p là số nguyên tố, với p >2, số a ≥ 0 là số nguyên. Ta định nghĩa a nhƣ sau: p 0,khi , a 0 (mod p ) a = 1,khi , a Qp ; p 1,khi , a Qp . Chú ý: + Từ định nghĩa suy ra a là thặng dƣ bậc hai mod p khi và chỉ khi = 1 + Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0 ta có: Phan Thị Thu Hiền - 5 - Lớp CT702
  7. Đồ án tốt nghiệp Hệ mật đường cong elliptic a (p-1)/2 ≡ a (mod p) . p Legendre Symbol thoả mãn các tính chất sau: 1. chỉ phụ thuộc vào đồng dƣ của a theo mod p. ab b 2. = ; p p ab 2 a 3. b nguyên tố với p thì = ; p p 1 1 (p-1)/2 4. =1 và = (-1) . p p Định lý 1: 2 2 (p – 1)/8 1 1 p mod 8 = (-1) = p 1 p3 mod 8 Định lý: Gọi là luật thuận nghịch bình phƣơng. Cho p, q là 2 số nguyên tố lẻ, khi đó: p   neu p q 3mod 4 q q (p-1)(q-1)/4 p = (-1) . = p q p trong truong hop khac q Định lý 2 b Nếu a ≡ b mod p → = p Định lý 3 = 1 p ≡ 1 mod 8 hay p ≡ 7 mod 8 -1 p ≡ 3 mod 8 hay p ≡ 5 mod 8 Ví dụ: Cho a = 186, p= 401 (p là số nguyên) Phan Thị Thu Hiền - 6 - Lớp CT702
  8. Đồ án tốt nghiệp Hệ mật đường cong elliptic Tìm a có là thặng dƣ bậc hai không nghĩa là a Q401? Và tìm x? với x2 ≡ a mod 401 a 186 2.93 2 93 = = = . p 401 401 401 401 Theo định lý 3: Vì 401 ≡ 1 mod 8 =1 vậy 331 3 31 = = = = 401 401 401 2.400 3 401 2 Nhƣng = (-1) 4 . = = -1 (định lý 1) 401 3 3 30.400 401 29 2 Và = (-1) 4 = = = =-1. 3 31 29 Vậy = 1.(-1).(-1) = 1 Do đó a Q401 Tiếp theo ta cần tìm x: x2 ≡ 186 mod 401. Lấy n =3 rõ ràng 3 không là đồng dƣ toàn phƣơng của 186 theo mod 401 (nhƣ trên ta đã chứng minh đƣợc = -1). 4 25 S 25 Ta có p-1 = 400 = 2 . → b = n = 186 mod 401 = 286 mod 401. 3 S 1 Còn r = a 2 mod 401 = 186 mod 401 = 103. Tính a-1 mod 401 = 186-1 mod 401 = 235 (thuật toán ơclit mở rộng). Tính a-1. r2 = 1032 . 235 mod 401 = 98 vì -2 = 4-2 =2 do đó ta nâng luỹ thừa 22 = 4 = của 98 và có 984 ≡ -1 mod 401 = -1 (984 mod 401 = (982 2 2 mod 401)( 98 mod 401) mod 401 = 381 mod 401 = -1) đặt j0 = 1 tiếp 2 theo, ta có (br) /a = -1 luỹ thừa bậc 2 của nó là 1 đặt j1 =0, cứ thế j2 =1(2 = K = ) Vậy j =5 vì 1.22 +1 = 5 Căn bậc 2 của 186 là b5r mod 401 = 304 Thử lại 3042 ≡ 186 mod 401? Phan Thị Thu Hiền - 7 - Lớp CT702
  9. Đồ án tốt nghiệp Hệ mật đường cong elliptic Ta có 3042 = 92416 vậy 3042 = 186 = 92230 ≡ 0 mod 401 x= 304 Ký hiệu Jacobi Symbol Bây giờ ta mở rộng ký hiệu Legendre để đƣợc ký hiệu Jacobi đối với mọi số nguyên lẻ n ≥ 1 và mọi số nguyên a ≥ 0. a1 a2 an Giả sử a có khai triển chính tắc thành thừa số là n = p 1, p 2, , p n thì a1 a2 ak a a a a = n p1 p2 pk với a1, a2, , ak 1 P1, P2, .Pk là những số nguyên tố. Khi n = p là số nguyên tố thì giá trị của các ký hiệu Legendre và Jacobi là nhƣ nhau. Việc tính ký hiệu Legendre có thể phức tạp khi p rất lớn, trong khi việc tính ký hiệu Jacobi có thể thuận lợi hơn do có thể sử dụng các tính chất 1- 4 sau đây: m1 m2 1. Nếu m1 ≡ m2 mod n thì = . n n 2 1,khi a  1(mod8) 2. = n 1khi a  3(mod8) mm12 m1 m2 3. = . n n n 4. Nếu m và n đều là số là thì: n khi m3mod 4& n 3mod 4 m m = n n khi m1mod 4  n  1mod 4 m Bây giờ xét việc giải phƣơng trình đồng dƣ bậc hai: x2 ≡ a (mod n) (*) Phan Thị Thu Hiền - 8 - Lớp CT702
  10. Đồ án tốt nghiệp Hệ mật đường cong elliptic Trong một trƣờng hợp đặc biệt khi n = p là số nguyên tố có dạng p = 4m + 3 tức là p đồng dƣ với 3 theo mod 4, và a là một số nguyên nguyên tố với p. Theo tiêu chuẩn Euler ta biết phƣơng trình (*) có nghiệm khi và chỉ khi a(p-1)/2 ≡ 1 (mod p). Khi đó ta có: p 1 1 a 2 ≡ a (mod p), a 2(m 1) ≡ a (mod p). 1.2. Nhóm Định nghĩa: Nhóm là một tập hợp G ≠ cùng với phép toán hai ngôi * trên G. Với a, b G, a * b = G thoả mãn tính chất sau: 1. Tính kết hợp: (a * b) * c = a * (b * c) với mọi a, b, c G. 2. Phần tử đồng nhất: Tồn tại e G thoả mãn e * a = a *e = a với mọi a G (e đƣợc gọi là phần tử trung hoà). 3. Phần tử nghịch đảo: với mỗi a G, tồn tại một phần tử b G thoả mãn b * a = a * b = e (b là duy nhất và đƣợc gọi là phần tử nghịch đảo của a). Và ngƣời ta ký hiệu của a bởi a-1. - Ký hiệu là nhóm nhân và G là nhóm cộng. Trong đó nhóm cộng, phần tử trung hoà là 0 và phần tử nghịch đảo của a là –a. Trong nhóm nhân, phần tử trung hoà là 1 và phần tử nghịch đảo của a là a-1. đ ƣơc gọi là một nhóm giao hoán (nhóm Abelian) nếu b * a = a * b với a, b G. - Một nhóm có cấp hữu hạn đƣợc gọi là nhóm hữu hạn Nếu là nhóm hữu hạn thì số các phần tử của đƣợc gọi là bậc của G và ký hiệu là |G| . Nếu là nhóm nhân hữu hạn, bậc của một phần tử a G kà số nguyên dƣơng nhỏ nhất m thoả mãn am = 1. Trong nhóm có cấp hữu hạn, với mọi phần tử thuộc nhóm, m luôn tồn tại. Nhóm Cylic Phan Thị Thu Hiền - 9 - Lớp CT702
  11. Đồ án tốt nghiệp Hệ mật đường cong elliptic Là nhóm mà mọi phần tử của nó đƣợc sinh ra từ một phần tử đặc biệt g G. Phần tử này đƣợc gọi là phần tử sinh (nguyên thuỷ) tức là: Với  x G(G là nhóm với toán tử * ):  n N mà gn = x Ví dụ: (Z+, *) là nhóm Cylic có phần tử sinh là 1. 1.3. Trƣờng Giả sử F là một tập hợp khác rỗng, trên đó có hai phép toán cộng và phép nhân. Khi đó F là một trƣờng nếu và chỉ nếu: 1. (F, +) là nhóm giao hoán với phần tử đơn vị là “0”. 2. (F\{0}, .) là nhóm giao hoán với phần tử đơn vị là “1”. 3. Các phép toán cộng và nhân có tính chất phân bố: a.(b.c) = (a.b) + (a.c) Trƣờng có thể định nghĩa nhƣ là vành giao hoán với phần tử đơn vị (trừ phần tử 0) đều có phần tử nghịch đảo cùng thuộc trƣờng. p Ví dụ: Q = { p, q là số nguyên: (p, q) = 1} trên Q có 2 phép toán cộng q và nhân thông thƣờng là một trƣờng. Định nghĩa Cho F là một trƣờng. 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 có 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. 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 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ử. Đối với một trƣờng hữu hạn thì  a F luôn luôn tồn tại một số nguyên dƣơng n sao cho: n aa = 0 Định nghĩa Phan Thị Thu Hiền - 10 - Lớp CT702
  12. Đồ án tốt nghiệp Hệ mật đường cong elliptic Trƣờng K với phần tử đơn vị nhân là 1. Với p dƣơng nhỏ nhất thoả mãn 1 1   1 = 0 đƣợc gọi là đặc số của K. p (Các trƣờng hữu tỷ Q, số thực R, số thực C có đặc số là 0). Ngƣời ta chứng minh đƣợc rằng đặc số của trƣờng hữu hạn là số nguyên tố. Với p là nguyên tố thì GF (pn) có đặc số p. 1.4. 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ử. Trƣờng hữu hạn không có đặc số 0. Ta gọi p là đặc số của Fq khi đó Fq khi đó Fq chứa trƣờng nguyên tố Fp = Z/ pZ vì vậy một không gian vector( không cần thiết phải có chiều hữu hạn) trên trƣờng Fp. Lấy f ký hiệu là chiều của nó coi Fp nhƣ là một không gian vector đó. Bằng cách chọn cơ sở cho phép chúng ta lập nên một tƣơng ứng 1-1 giữa không gian vector f chiều với tập hợp tất cả bộ f phần tử trong Fp nghĩa là q là luỹ thừa của đặc số p. f Đối với mỗi lũy thừa nguyên tố q = p có tồn tại một trƣờng q phần tử và đó là trƣờng duy nhất (theo nghĩa đẳng cấu). * * Cấp của các phần tử trong F q theo nghĩa đối với phép nhân với F q là tập hợp tất cả các phần tử khác không của trƣờng Fq (q hữu hạn) Chú ý rằng đối với mọi nhóm nhân hữu hạn, cấp của bất cứ một số phần tử khác không nào cũng là ƣớc của số các phần tử trong nhóm. Cụ thể ta có định lý Định nghĩa 1 2 q-1 Giả sử phần tử g Fq nếu cấp của g là q-1 tức là {g , g , , g = 1} * = F q Phan Thị Thu Hiền - 11 - Lớp CT702
  13. Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƢƠNG 2 ĐƢỜNG CONG ELLIPTIC 2.1. Mở đầu và đặt bài toán Lý thuyết đƣờng cong Elliptic đƣợc xác định trên trƣờng số hữu hạn đã có địa chỉ ứng dụng trong lĩnh vực mật mã đáng lƣu ý. Lý do cơ bản của nó là đƣờng cong Elliptic trên trƣờng hữu hạn đã cung cấp cho chúng ta một cơ sở xây dựng thuật toán không thể dùng thuật toán vét cạn để thám mã của nhóm Abelian ngay cả khi nhóm đó có cấp không lớn lắm. Đƣờng cong elliptic là tập hợp các điểm có toạ độ (x, y) thoả mãn phƣơng trình có dạng sau đây: 2 3 2 y + a1xy + a3y = x + a2x +a4x + a6. Trên trƣờng F biểu diễn bằng phƣơng trình Weiretrass: 2 3 2 y + a1xy + a3y = x + a2x +a4x + a6 2 (*) Xét đƣờng cong E trên trƣờngnguyên tố hữu hạn Fp (p nguyên tố, p>3 ) với công thức biến đổi nhƣ sau: a2 a1X a3 X→X − , Y→ Y − 3 2 Khi đó phƣơng trình Weierstrass có dạng: X3 + aX +b. Vậy trong trƣờng Fp (*) trở thành: Y2 = X3 + aX + b Định nghĩa: Giả sử K là một trƣờng có đặc số khác 2 và khác 3 và xét đa thức X3 + aX + b(với a, b K) Khi đó đƣờng cong elliptic trên trƣờng K: Y2 = X3 + aX + b (1) là tập hợp tất cả các điểm (x, y) với x, y K sao cho (1) không có các nghiệm bội Phan Thị Thu Hiền - 12 - Lớp CT702
  14. Đồ án tốt nghiệp Hệ mật đường cong elliptic tức là 4a3 + 27b2 ≠ 0 mod p cùng với phần tử O - điểm O này đƣợc gọi là điểm vô hạn. Tức là đƣờng cong Elliptic là tập hợp S: S = { (x, y) : y2 = x3 + ax +b, x, y K }  {O} . Với a, b K cho trƣớc sao cho 4a3 + 27b2 ≠ 0 theo mod p. Nếu K là trƣờng đặc số 2 thì ta định nghĩa: S = { (x, y) : y-2 + y= x3 + ax +b } {O} (2) . Nếu K là trƣờng đặc số 3 thì ta định nghĩa: S = { (x, y) : y2 = x3 + ax +bx + c } {O} (3) * Tính chất của đường cong elliptic: Nếu hai điểm P1 (x1, y1 ) và P2 (x2, y2) với x1 ≠ x2 nằm trên đƣờng cùng một đƣờng cong elliptic E, thì đƣờng thẳng qua hai điểm P1 và P2 sẽ cắt một điểm duy nhất P3 ( x3, y3) có thể xác định thông qua P1 và P2 nằm trên đƣờng cong E. Tiếp tuyến của đƣờng cong tại điểm bất kỳ P(x, y) trên đƣờng cong E cũng cắt đƣờng cong elliptic E tại một điểm duy nhất nằm trên đƣờng E, điểm này cũng có thể xác định đƣợc thông qua P. Dựa vào những tính chất đó ngƣời ta đã nghiên cứu và phát hiện ra một khả năng mới cho kỹ thuật mã hoá nói chung và chứng thực nói riêng, kỹ thuật mã hoá dựa trên đƣờng cong elliptic. Ngƣời ta đã chỉ ra rằng các hệ mã hoá bằng đƣờng cong elliptic có độ bảo mật cao hơn nhiều so với các hệ mã hoá công khai khác nhƣ RSA, Elgamal. Độ bảo mật dựa trên độ khó phân tích số nguyên thành các thừa số nguyên tố cũng nhƣ bài toán logarit rời rạc, độ dài khoá giảm đi nhiều lần và do đó tốc độ thực hiện cũng sẽ nhanh hơn rất nhiều. Chính vì vậy ta áp dụng kỹ thuật mã hoá bằng đƣờng cong elliptic vào nhiều lĩnh vực khác nhau. Các kỹ thuật mã hoá bằng phƣơng pháp đƣờng cong elliptic đƣợc sử dụng hiệu quả nhất trong việc xây dựng các giải pháp bảo mật thông tin cho Phan Thị Thu Hiền - 13 - Lớp CT702
  15. Đồ án tốt nghiệp Hệ mật đường cong elliptic các thẻ thông minh(Smart Card), các thiết bị điện tử có khả năng tính toán và không gian bộ nhớ hạn chế. 2.2. Đƣờng cong elliptic trên trƣờng hữu hạn r Xét trƣờng hữu hạn Fq của q = p phần tử trên trƣờng hữu hạn K. Giả sử E là đƣờng cong elliptic đƣợc định nghĩa trên Fq. Nếu đặc số của trƣờng p=2 hoặc p=3 thì E đƣợc cho bởi phƣơng trình ở (2) và (3) . Dễ dàng thấy rằng một đƣờng cong nhƣ vậy có thể có nhiều nhất là 2p+1 điểm trong Fq, nghĩa là điểm vô cùng với 2q cặp (x, y) trong đó x, y Fq thoả mãn (1) (2) (3) (nếu p=2 hoặc 3), tức là với mỗi q giá trị x có thể có tồn tại * nhiều nhất 2 giá trị y thoả mãn (1). Nhƣng vì chỉ có một nửa các phần của F q 3 có căn bậc 2 ngƣời ta kỳ vọng (nếu x + ax +b là các phần tử ngẫu nhiên của trƣờng ) chỉ có khoảng một nửa số các điểm của Fq. Chính xác hơn, giả sử  đặc trƣng toàn phƣơng của Fq (lấy (0) = 0). x Ví dụ: Nếu q = p là 1 số nguyên tố thì (x) =( ) là ký hiệu Legedre p Symbol). Do đó trong tất cả mọi trƣờng hợp số các nghiệm y Fq thoả mãn phƣơng trình y2 = u là bằng 1 + (u). Vì vậy số các nghiệm ở phƣơng trình 1 và điểm vô hạn là: 1 +  (1+  (x3 + ax + b)) = q + 1 +  (1+ (x3 + ax + b)) (6) x Fq x Fq Ta hy vọng rằng  ( x3 + ax + b) bằng +1 và -1. Lấy tổng ngẫu nhiên: tung đồng xu q lần. Ngƣời ta thấy rằng (x3 + ax + b) bị chặn bởi 2 q đó chính là định lý Hasses đƣợc phát triển nhƣ sau: Định lý: Gọi N là số các điểm trên đƣờng cong elliptic đƣợc định nghĩa trên Fq. Khi đó | N−(q + 1) | ≤ 2 Phan Thị Thu Hiền - 14 - Lớp CT702
  16. Đồ án tốt nghiệp Hệ mật đường cong elliptic 2.3. Các phép toán trên đƣờng cong Elliptic Giả sử p là một số nguyên tố >3. Ngƣời ta chứng minh đƣợc rằng bằng phép biến đổi tuyến tính, ta có thể quy phƣơng trình đƣờng cong elliptic về dạng Weierstrass nhƣ sau: Y2 = X3 + aX + b 2 3 Đƣờng cong elliptic Y = X + aX + b trên Zp đƣợc định nghĩa là tập hợp tất cả các điểm (x, y) Zp Zp thoả mãn phƣơng trình: Y2 = X3 + aX + b (mod p), Cùng với một phần tử đặc biệt ký hiệu là O là phần tử trung hoà. Tập hợp đó đƣợc ký hiệu là E. 23.1. Phép cộng Giả sử P= (x1, y1) và Q (x2, y2) là hai điểm của E. Nếu x1 = x2 và y1 = - y2 thì ta định nghĩa P + Q = O Ngƣợc lại th ì P + Q = (x3, y3) E trong đó 2 x3 =  - x1 – x2 , y3 = (x1 – x3 ) –y1, Với  = (y2 – y1 ) / (x2 – x1), khi P ≠ Q( nếu x1 = x2 th ì là hệ số góc đƣờng thẳng qua P và Q) (*) 2 (3x + a) / 2 y1, khi P = Q (  là đạo hàm của đƣờng cong tại P) ( ) Vậy nếu P ≠ Q tức là x1 ≠ x2 2 y2 y1 x3 = - x1 – x2 (*) x2 x1 y2 y1 y3 = ( x1 – x3) - y1 x2 x1 N ếu P =Q Phan Thị Thu Hiền - 15 - Lớp CT702
  17. Đồ án tốt nghiệp Hệ mật đường cong elliptic 2 3x1 a x3 = – 2x2 ( ) 2y1 2 3x 1 a y3 = ( x1 – x3) - y1 2y1 2 1 R Q P R 2P P P+ Q -1 -2 Hình 2.6.1 Phép cộng trên đường cong Elliptic Chú ý rằng các điểm (x3, y3), (x3, -y3) cũng nằm trên đƣờng cong E và xét về mặt hình học, thì các điểm (x1, y1), (x2, y2), (x3, -y3) cũng nằm trên một đƣờng thẳng. Ngoài ra ta định nghĩa thêm: P + O = O + P = P. Tính chất Dễ thấy rằng tập E với phép toán cộng đó tạo thành một nhóm Abelian: Phan Thị Thu Hiền - 16 - Lớp CT702
  18. Đồ án tốt nghiệp Hệ mật đường cong elliptic  Tính đóng: Nếu P, Q E thì P + Q E.  Tính kết hợp: Nếu P, Q, R E thì P + ( Q + R ) = R + ( Q + P ).  Tồn tại phần tử trung hoà O: với mọi P E thì P + O = O + P = P (theo định nghĩa).  Tồn tại phần tử nghịch đảo: với mỗi P(x, y) E thì luôn tồn tạ phần tử -P(x, -y) E để P + (-P) = O.  Tính chất giao hoán Nếu P, Q E thì P + Q = Q + P. Ví dụ: Xét đƣờng cong elliptic y2 = x3 – 36x Lấy P =(-3, 9), Q = (-2, 8). Hãy tìm P + Q và 2P? Với x1 = -3, y1 = 9, x2 = -2 , y2 = 8. Do đó áp dụng công thức(*) ta có: (8 9) 2 x3 = +3 + 2 = 1+ 3 +2 = 6. 2 3 8 9 y3 = -9 (-3-6) = -9 + (-1)(-9) =0. 2 3 Vậy P +Q = (6, 0). Bây giờ ta tính 2P áp dụng ( ) ta có: x1= -3, y1 = 9 25 35 25 35 x3 = và do đó y3= . Vậy 2P = ( , ) 4 8 4 8 2.3.2. Phép nhân Phép nhân một số nguyên k với một điểm P thuộc đƣờng cong elliptic E là điểm Q đƣợc xác định bằng cách cộng k lần điểm P và dĩ nhiên Q E: k P = P + P + P + P ( k phép cộng điểm P). Vì vậy nếu G là một điểm thuộc đƣờng cong elliptic E thì với mỗi số nguyên dƣơng k luôn dễ dàng xác định đƣợc điểm Q = k G 2.4. Đếm số điểm trên đƣờng cong elliptic trên trƣờng Fq Việc xây dựng các hệ mật mã trên đƣờng cong elliptic bao gồm việc lựa chọn đƣờng cong E thích hợp và một điểm G trên E gọi là điểm cơ sở. Xét trƣờng K là Fq. Định lý Hasse Phan Thị Thu Hiền - 17 - Lớp CT702
  19. Đồ án tốt nghiệp Hệ mật đường cong elliptic N là số điểm của E trên trƣờng Fq (trƣờng hữu hạn q phần tử). Khi đó: |N – (q +1)| ≤ 2 q .Từ định lý Hasse suy ra #E(Fq) = q +1 – t trong đó |t| ≤ 2 q . Định nghĩa Bậc của điểm G thuộc E là số k dƣơng bé nhất sao cho kG = O; khi k = #E(Fq) thì G là điểm cơ sở của E. 2.5. Phƣơng pháp chọn đƣờng cong Elliptic phù hợp và điểm cơ sở Việc chọn một đƣờng cong elliptic thế nào ảnh hƣởng đến tốc độ, tính hiệu quả, độ dài khoá và tính an toàn của hệ mật mã trên đƣờng cong này. Dù E, K và điểm cơ sở B E cố định và công khai nhƣng việc chọn các tham số này phù hợp là bƣớc quan trọng nhất. 2.5.1. Trƣờng K Trƣớc hết chúng ta xem xét sự ảnh hƣởng của trƣờng K đến cấu trúc nhóm của E(K) và các hệ mật mã trên E (K). Một đƣờng cong elliptic trên một trƣờng hữu hạn tạo thành nhóm r Abelian đƣợc sử dụng trong mật mã học. Một ví dụ là việc chọn trƣờng F2 giúp thực hiện các phép tính nhanh và dễ dàng triển khai đƣợc trên các thiết bị r cứng. Tuy nhiên, các đƣờng cong trên trƣờng F2 có thể bị tấn công bởi MOV, trong khi các đƣờng cong trên trƣờng Fp (p là số nguyên tố lớn) lại chống lại đƣợc kiểu tấn công này. Rõ ràng, các đƣờng cong elliptic trên n trƣờng số nguyên tố Fp và trên trƣờng Fq có các tính chất giúp chúng có thể thực thi đƣợc trên các thiết bị mà vẫn đảm bảo an toàn. Một chú ý nữa là việc tính số điểm trên # E (K). Với # E (K) thích hợp có thể là điều kiện cho phép thực hiện tấn công Pohlig – Hellman. Có thể dùng thuật toán đơn định thời gian đa thức Shoof để tính trên trƣờng hữu hạn Fq với đặc số khác 2 hoặc 3. Tốc độ của thuật toán Shoof phụ thuộc vào kích r thƣớc và đặc số của trƣờng K. Ví dụ với r nhỏ, tính # E (F2 ) có thể nhanh hơn Phan Thị Thu Hiền - 18 - Lớp CT702
  20. Đồ án tốt nghiệp Hệ mật đường cong elliptic r một chút so với tính # E(Fp), trong đó p lớn hơn đáng kể so với 2 , nhƣng khi r r tăng thì tính # E (F2 ) mất nhiều thời gian hơn tính # E (Fp). 2.5.2. Dạng của đƣờng cong elliptic Trƣớc hết, chúng ta cần xem các dạng đƣờng cong elliptic. Trên trƣờng Fq có hai lớp đƣờng cong elliptic đƣợc dùng trong các hệ mã hoá là m supersinggular. Xét Fq có đặc số là 2 (g = 2 ). Khi đó: . Tập tất cả các cặp nghiệm (x, y) của phƣơng trình y2 +ax = x3 + bx + c với a, b, c Fq và a = 0 (mod q) cùng với điểm trung hoà O tạo thành một đƣờng cong elliptic dạng supersingular. . Tập tất cả các cặp nghiệm (x, y) của phƣơng trình y2 + ax = x3 + bx + c với a, b, c Fq và b = 0 (mod q) cùng với điểm trung hoà O tạo thành một đƣờng cong elliptic dạng non-supersingular. Supersingular Curve: Menezes và Vanstone đã tìm ra các ƣu điểm của các đƣờng cong elliptic supersingular cho các hệ mật mã, đặc biệt trên trƣờng r F2 . Tuy nhiên, các đƣờng cong supersingular có thể bị tấn công bằng MOV. Nonsupersingular Curve: Ƣu điểm của các đƣờng cong nonsupersingular là nó cung cấp độ bảo mật tƣơng đƣơng nhƣ các đƣờng cong supersingular nhƣng với các trƣờng nhỏ hơn. Độ dài khoá ngắn giúp chúng có thể triển khai trên các thiết bị nhƣ smart card. Hơn nữa, các đƣờng cong nonsupersingular có thể chống lại tấn công MOV, ví dụ nhóm con cylic cỡ 2160. 2.5.3. Phƣơng pháp lựa chọn Có nhiều cách chọn các đƣờng cong elliptic và điểm cơ sở B thuộc đƣờng cong đó. Một cách chọn điển hình là: Phương pháp- Phương pháp chọn ngẫu nhiên Kobliz: Sơ đồ 3.8. Phương pháp chọn ngẫu nhiên Kobliz 1. Chọn ngẫu nhiên 3 phần tử từ Fq là x, y, a 2. Tính b = y2 – (x3 + ax) Phan Thị Thu Hiền - 19 - Lớp CT702
  21. Đồ án tốt nghiệp Hệ mật đường cong elliptic 3. Kiểm tra 4a3 + 27b2 ≠ 0 để đảm bảo phƣơng trình x3 + ax + b =0 không có nghiệm kép. 4. Nếu điều kiện trên khôn thoả mãn quay lại bƣớc 1. 5. Còn lại, đặt P = (x, y) và đƣờng cong y2 = x3 + ax +b là đƣờng cong cần chọn. Tuy nhiên phƣơng pháp này có thể tạo ra các đƣờng cong không đảm bảo một số yêu cầu định trƣớc. Một kỹ thuật cải tiến là xây dựng các đƣờng cong với các tính chất cho trƣớc. Cũng có thể chọn những đƣờng cong để tạo các hệ mã hoá không phụ thuộc vào bài toán EDLP, chẳng hạn các hệ elliptic dựa trên RSA. Các hệ mật mã elliptic làm việc với các nhóm con cylic của E với phần tử sinh là điểm P. Vì vậy, việc lựa chọn P phù hợp là rất quan trọng. Để đảm bảo việc chọn điểm thích hợp ta hãy chọn đƣờng cong elliptic của chúng ta và trƣờng hữu hạn sao cho số N các điểm của đƣờng cong là một số nguyên tố. Nếu chọn đƣợc nhƣ vậy thì mọi điểm B ≠ 0 đều là phần tử sinh. Phan Thị Thu Hiền - 20 - Lớp CT702
  22. Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƢƠNG 3 HỆ MẬT ĐƢỜNG CONG ELLIPTIC 3.1. Mở đầu và đặt bài toán Năm 1976, Diffie và Hellman giới thiệu hệ mã hoá khoá công khai đầu tiên mà sự an toàn của nó dựa trên độ khó của bài toán DLP. Họ đƣa ra khái niệm hàm cửa sập một chiều (TOF). Năm 1985, Lenstra thành công trong việc sử dụng các đƣờng cong elliptic cho các số nguyên. Kết quả này mang lại khả năng áp dụng các đƣờng cong elliptic trong các hệ mật mã khoá công khai. Miller và Kobliz giới thiệu những hệ mật mã elliptic. Họ không phát minh ra các thuật toán mới nhƣng đã có đóng góp lớn là chỉ ra việc áp dụng elliptic cho các hệ khoá công khai. Miller đề xuất một giao thức trao đổi khoá tựa nhƣ Diffie – Hellman vào năm 1985 (nhanh hơn 20% so với giao thức Diffie - Hellman). Kobliz đƣa ra thuật toán mã hoá tƣơng tự nhƣ hệ Elgamal và Massey – Omura vào năm 1987. Sơ đồ đầu tiên tƣơng tự nhƣ sơ đồ RSA và 3 hàm một chiều (có cửa sập) mới dựa trên đƣờng cong Elliptic đƣợc đƣa ra năm 1991 bởi Koyama, Maurer, Okamoto và Vanstone ( thuật toán này tốc độ thực hiện nhanh gấp 6 lần so với RSA). Cùng thời điểm đó, Kaliski chứng minh rằng các hàm cửa sập một chiều đòi hỏi thời gian là hàm mũ để thực hiện phép tính nghịch đảo. Menezes, Okamoto và Vanstone đã đƣa ra một phƣơng pháp tấn công MOV để giải bài toán EDLP trong một số trƣờng hợp riêng. Ngay sau đó, Miyaji đã tìm đƣợc các điều kiện để tránh khỏi tấn công MOV và đề xuất một ứng dụng thực tế của các đƣờng cong elliptic cho các sơ đồ chữ ký và định danh trên Smart Card. Năm 1993, Demytko đƣa ra một thuật toán mới tƣơng tự nhƣ RSA cho các đƣờng cong Elliptic trên vành Zn vƣợt qua các hạn chế của các phiên bản trƣớc, và Menezes và Vanstone đã đƣa ra phƣơng pháp thực thi trên các thiết Phan Thị Thu Hiền - 21 - Lớp CT702
  23. Đồ án tốt nghiệp Hệ mật đường cong elliptic bị cứng có thể cài thiện các tính toán trên elliptic trên một trƣờng hữu hạn. Những năm 1997, 1998 việc tìm ra các hệ mật mã trên các đƣờng cong Elliptic ngày càng thu hút nhiều sự chú ý và một số thuật toán đã đƣợc đƣa thành chuẩn trong các RFC. 3.2. Nhúng bản rõ lên đƣờng cong Nhúng một bản rõ lên E là biểu diễn lại bản rõ đó nhƣ là các điểm trên E mà nhờ đó chúng ta có thể thực hiện đƣợc các tính toán trên E. Có một số phƣơng pháp thực hiện việc này. Trong đó có 2 phƣơng pháp chính là imbedding và mask. 4.2.1. Imbedding Muốn mã hoá bản rõ m trên một đƣờng cong elliptic cho trƣớc đƣợc định nghĩa trên trƣờng Fq trƣớc hết ta phải tìm cách nhúng nó lên E. Giả sử m đƣợc coi là một số nguyên dƣơng nào đó. Bản rõ m đƣợc ứng với điểm Pm trên E. Trƣớc khi thực hiện “nhúng” điểm m lên E ta cần lƣu ý: 1. Sau khi nhận đƣợc bản mã, ngƣời ta nhận đích thực phải có thể giải đƣợc bản mã một cách dễ dàng. 2. Không có một thuật toán tất định với thời gian đa thức (trong log q) để biết đƣợc một số lớn các điểm trên đƣờng cong elliptic tuỳ ý trên E cả trƣờng Fq. Tuy nhiên lại tồn tại một thuật toán xác suất mà đối với nó xác suất sai là rất bé. 3. Việc tạo ra các điểm ngẫu nhiên của E là không đủ để mã hoá một số lƣợng lớn tuỳ ý các bản rõ m. Trong lúc đó bản rõ mà ta cần nhúng lại có thể rất lớn. Do đó, một phƣơng pháp xác suất có thể cho phép nhúng (imbed) các bản rõ m đƣợc coi là một điểm trên đƣờng cong elliptic E đƣợc định nghĩa n trên trƣờng Fq với q = p đƣợc giả thiết là đủ lớn. Gọi  là một số nguyên dƣơng đủ lớn sao cho thoả mãn xác suất sai xấp  xỉ 1/2 . Giả sử khi chúng ta muốn nhúng một bản rõ m, giả sử  là một số Phan Thị Thu Hiền - 22 - Lớp CT702
  24. Đồ án tốt nghiệp Hệ mật đường cong elliptic nào đó( =20, 30 hoặc = 50 là đủ). Với m kà một số nguyên sao cho 0≤ m ≤M (M là số nguyên dƣơng lớn hơn mọi khối rõ m cần nhúng ) Trƣờng hữu hạn đã chọn sao cho q > M .Biểu diễn các số nguyên từ 1 đến M dƣới dạng: {m + j} 1≤ j ≤ Ta lập một ánh xạ 1- 1 tƣơng ứng giữa các số nguyên trên với tập hợp các phần tử của Fq. Ví dụ có thể viết một số nguyên nhƣ là một số nguyên cơ số p có độ dài r và coi r nhƣ là một phần tử của Z/pZ , là hệ số của một đa thức cấp r – 1 tƣơng ứng với một phần tử của Fq. Nghĩa là số nguyên (ar-1 , ar- r 1 j 2, .a1, a0 )p đặt tƣơng ứng với đa thức  ajX mà nóđƣợc xem nhƣ modulo i 0 đa thức bất khả quy cấp r cố định trên Fp, cho một phần tử của Fq. Do đó cho trƣớc m với j = 1, 2,3  sẽ nhận đƣợc một phần tử của Fq tƣơng ứng với m + j Đối với số x đó ta tính: Y2 = f(x) = x3 + ax + b và tìm căn bậc 2 của giá trì f(x) bằng cách sử dụng phƣơng pháp đã nêu trong ví dụ 1.1.4. 2 Nếu tìm đƣợc một số y sao cho y = f(x) thì lấy Pm = (x, y). Nếu kết quả f(x) là không bình phƣơng thì tăng x bởi 1 và tiếp tục tính toán từ đầu cho đến khi tìm đƣợc một số x sao cho f(x) là một bình phƣơng cho đến khi j nhận giá trị lớn  , có thể khôi phục lại đƣợc m từ điểm (x, y) bởi công thức: -1)/  ] Trong đ ó là một số nguyên ứng với giá trị x bởi phép tƣơng ứng 1-1 giữa các số nguyên và các phần tử của Fq. Vì f(x) là một bình phƣơng với xấp xỉ 50% của mọi x cho nên chỉ có khoảng xác suất 2- để cho phƣơng pháp này là sai. Phan Thị Thu Hiền - 23 - Lớp CT702
  25. Đồ án tốt nghiệp Hệ mật đường cong elliptic 3.3. Logarit rời rạc trên đƣờng cong Elliptic( Discrete logarithm on Elliptic) Định nghĩa: Nếu E là đƣờng cong Elliptic trên trƣờng Fq và B là một điểm trên E. Khi đó bài toán logarit rời rạc trên E (theo cơ số B) là một bài toán, cho trƣớc một điểm P E, tìm số nguyên x Z sao cho xB = P (nếu số x nhƣ vậy tồn tại) Hầu nhƣ bài toán tính logarit rời rạc trên đƣờng cong elliptic sẽ khó hơn bài toán logarit rời rạc trên trƣờng hữu hạn. Các kỹ thuật mạnh nhất đã đƣợc phát triển để sử dụng trong các trƣờng hữu hạn dƣờng nhƣ không có giá trị đối với đƣờng cong elliptic. Kết quả này đặc biệt đúng trong trƣờng hợp trƣờng có đặc số 2. Nhƣ đã đƣợc chứng tỏ bởi Odlzko rằng có một số phƣơng * r pháp đặc biệt để giải bài toán logarit rời rạc trong G 2 với chúng dễ dàng tính đƣợc logarit rời rạc và do đó phá vỡ đƣợc hệ mật mã, trừ ra trƣờng hợp số r đƣợc chon đủ lớn. Dƣờng nhƣ các hệ thống tƣơng tự sử dụng đƣờng cong r elliptic đƣợc định nghĩa trên trƣờng F2 sẽ đảm bảo an toàn kể cả trong trƣờng hợp giá trị r khá bé. 3.4. Vấn đề trao đổi khoá Diffie- Hellman(D- H) trên Elliptic Giả sử A và B muốn thống nhất một khoá chung để liên lạc có bảo mật giữa hai ngƣời bằng mật mã truyền thống. Trƣớc hết hai bên thống nhất công khai chọn một trƣờng hữu hạn Fq và một đƣờng cong elliptic trên nó khoá chung của họ sẽ đƣợc xây dựng từ một điểm ngẫu nhiên P của đƣờng cong vừa cho, họ làm cách này bằng cách chọn toạ độ x của P là ngẫu nhiên trong r Fq. Sau đó nó đƣợc chuyển đổi thành số nguyên cơ số P có r số( q = p ) mà đƣợc coi là khoá đối với hệ mã truyền thống của họ. Cụ thể nhƣ sau: Trƣớc hết A, B chọn công khai một điểm B E. B đóng vai trò nhƣ là phần tử sinh g trong trƣờng hữu hạn của hệ thống Diifie-Hellman. Chúng ta muốn có một nhóm con đƣợc sinh ra bởi B là lớn, tốt nhất là có cùng cấp nhƣ Phan Thị Thu Hiền - 24 - Lớp CT702
  26. Đồ án tốt nghiệp Hệ mật đường cong elliptic E. Bây giờ giả sử B là công khai và cố định trên E mà cấp của nó là đủ lớn (chẳng hạn hoặc là N hoặc là một nhân tử lớn của N). Để tạo ra khoá, trƣớc hết A chọn ngẫu nhiên một số nguyên a có cấp q (nó xấp xỉ nhƣ số N). Số a đƣợc giữ bí mật. Trên cơ sở đó, A tính aB E, aB là công khai. Đến lƣợt B cũng làm nhƣ vậy, anh ta chọn ngẫu nhiên số b và tính bB E, bB cũng đƣợc công khai. Khoá bí mật mà chỉ có hai ngƣời A, B mới có đó là: P =abB E. Ngƣời thứ ba bất kỳ không thể suy ra abB từ aB và r bB nếu không giải bài toán logarit rời rạc trên E của trƣờng Fp . 3.5. Hệ mât mã hoá Elgamal trên đƣờng cong Elliptic Hệ Elgamal làm việc với nhóm Cyclic hữu hạn. Năm 1978, Kobliz đã đƣa một hệ trên ECC dựa trên hệ Elgamal. Để xây dựng hệ mã hoá dựa trên đƣờng cong elliptic ta chọn đƣờng cong E(a, b) và một điểm G trên đƣờng cong làm điểm cơ sở. Mỗi ngƣời dùng A một khoá bí mật nA là một số nguyên, và sinh khoá công khai PA = nA * G. Khi đó hệ mã hoá đƣờng cong elliptic đƣợc xây dựng tƣơng tự hệ mã hoá ElGamal, trong đó thuật toán mã hoá và giải mã đƣợc xác định nhƣ sau: Thuật toán mã hoá Giả sử ngƣời dùng A muốn gửi thông điệp cần mã hoá Pm tới ngƣời dụng B, chọn một số ngẫu nhiên k và gửi thông điệp mã hoá Cm đƣợc tính nhƣ sau: Cm = {k * G, Pm + k * PB } (PB là khoá công khai của B) Thuật toán giải mã Để giải mã thông điệp Cm = { k * G, Pm + k * PB }, ngƣời dùng B thực hiện tính nhƣ sau: Pm + k * PB - nB * k * G = Pm + k * PB – k * nB * G = Pm + k * PB - k * PB = Pm Phan Thị Thu Hiền - 25 - Lớp CT702
  27. Đồ án tốt nghiệp Hệ mật đường cong elliptic Chỉ có B mới có thể giải mã vì B có nB (là khoá bí mật). Chú ý rằng ở đây Pm là một điểm thuộc đƣờng cong elliptic, quá trình mã hoá giải mã đƣợc thực hiện trên các điểm thuộc đƣờng cong E. Trong thực tế, để sử dụng đƣợc ngƣời ta phải tƣơng ứng một số với một điểm thuộc đƣờng cong elliptic. Khi đó mỗi thông điệp cần mã hoá sẽ tƣơng ứng với một dãy số. Mỗi số sẽ tƣơng ứng với một điểm trên đƣờng cong elliptic. Tính bảo mật Nếu kẻ tấn công giữa đƣờng, Oscar, có thể giải bài toán EDLP thì anh ta có thể biết đƣợc khoá bí mật từ nB của B từ các thông tin công khai G và nBG, và có thể giải mã thông điệp mà A gửi. Nhƣ vậy độan toàn (bảo mật) của thuật toán trên dựa vào độ khó của bài toán EDLP. Phan Thị Thu Hiền - 26 - Lớp CT702
  28. Đồ án tốt nghiệp Hệ mật đường cong elliptic CHƢƠNG 4 MỘT VÀI ỨNG DỤNG 4.1. Lƣợc đồ chữ ký số trên đƣờng cong elliptic (Elliptic Curve Signature Algorithm ) - ECDSA 4.1.1. Lƣợc đồ ký ECDSA Sơ đồ chữ ký ECDSA đƣợc xây dựng tƣơng tự nhƣ sơ đồ chữ ký ElGamal tuy nhiên các thuật toán ký và thuật toán kiểm thử đƣợc xây dựng dựa trên đƣờng cong Elliptic. Để 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 và công khai cho tất cả mọi ngƣời, đ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ích q của trƣờng, hoặc q = p (p>2) hoặc q= 2m. 2 2. Hai phần tử a, b thuộc Fq xác định phƣơng trình đƣờng cong Elliptic: y = 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à n > 4 q . Sinh khoá 1. Chọn số ngẫu nhiên d trong khoảng [2, n-1 ] làm khoá bí mật 2. Tính Q = dG làm khoá công khai. Thuật toán ký trên bản rõ m Ngƣời dùng A ký lên thông điệp m theo các bƣớc sau: 1. Chọn một số ngẫu nhiên k, 2 k n 1 2. Tính kG = (x1, y1). 3. Tính r = x1 mod n. Nếu r =0, quay lại bƣớc 1. Phan Thị Thu Hiền - 27 - Lớp CT702
  29. Đồ án tốt nghiệp Hệ mật đường cong elliptic 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 ). Thuật toán kiểm tra chữ ký Ngƣời dùng B kiểm tra chữ ký (r, s ) trên thông điệp m theo các bƣớc sau: 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. 4.1.2. Độ an toàn của sơ đồ chữ ký ECDSA Các hệ mã hoá đƣờng cong elliptic đầu tiên đƣợc phát minh năm 1985 bởi Neal Kobliz và Victor Miller. Tuy nhiên sơ đồ chữ ký ECDSA do Scott Vanstone đƣa ra năm 1992, đƣợc chấp nhận là chuẩn ISO vào năm 1998, là chuẩn ANSI vào năm 1999, và là chuẩn IEEE vào năm 2000. Độ an toàn của sơ đồ ký ECDSA dựa trên bài toán logarit rời rạc đƣờng cong elliptic. Cho đến nay độ an toàn của các hệ mã hoá đƣờng cong elliptic đã đƣợc chỉ ra là rất an toàn và hiệu quả. Đối với bài toán logarit rời rạc đƣờng cong elliptic thì có nhiều thuật toán giải nó. Tuy nhiên chƣa có thuật toán nào có độ phức tạp tính toán trong thời gian đa thức. Thuật toán giải bài toán logarit rời rạc đƣờng cong elliptic tốt nhất hiện nay là thuật toán Pollard’s Rho, phiên bản thiết kế theo hƣớng tính toán song song. Theo đó với nhóm đƣờng cong elliptic cấp n và có r máy tính cùng tính toán thì phải mật .n /2.r phép toán. Mặt khác ngƣời ta đã phân tích và chỉ ra rằng với hệ mã hoá dựa trên bài toán logarit rời rạc đƣờng cong elliptic có cùng độ bảo mật với hệ mã hoá dựa trên bài toán phân tích số nguyên thành các thừa số nguyên tố (nhƣ RSA) Phan Thị Thu Hiền - 28 - Lớp CT702
  30. Đồ án tốt nghiệp Hệ mật đường cong elliptic thì độ dài khoá của hệ mã hoá dựa trên đƣờng cong elliptic có chiều dài khoá ngắn hơn rất nhiều . Chẳng hạn với hệ mã hoá RSA có chiều dài khoá là 1024 bit thì hệ mã hoá bằng đƣờng cong elliptic chỉ cần độ dài khoá 163 bit sẽ có độ bảo mật tƣơng đƣơng. Và do đó việc tính toán các tiến trình đối với các hệ mã hoá đƣờng cong elliptic là nhanh hơn rất nhiều. 4.2. Một số chuẩn sử dụng hệ mật ECC Việc đƣa ra một số chuẩn chung cho các hệ thống mật mã, các giao thức, các giao diện là một việc quan trọng. Việc chuẩn hoá mạng lại 3 lợi ích chính: 1. Cho phép kết hợp phần cứng và phần mềm của nhiều nhà cung cấp khác nhau. 2. Đƣa ra chuẩn cho việc đảm bảo an toàn các hệ thống dƣới khía cạnh mật mã học. 3. Cho phép có thiết kế chuẩn cho các môi trƣờng ứng dụng khác nhau. Các đƣờng cong Elliptic đã đƣợc xem xét và nghiên cứu kỹ lƣỡng bởi các nhà toán học trong hơn 10 năm và đã đƣợc khảo sát kỹ bởi các tổ chức chuẩn hoá từ năm 1995. Điều này đảm bảo rằng tính tin cậy của nó đã đƣợc kiểm chứng. Nỗ lực để có thể chuẩn hoá các hệ mật mã khoá công khai đƣợc bắt đầu từ nhiều năm trƣớc bởi Viện nghiên cứu điện và điện tử IEEE(Institute of the Electrical and Electronics Engineers) với phiên bản P1363. Nó đƣa ra định dạng và thủ tục cho 3 hệ thống mã hoá khoá công khai khác nhau bao gồm xác thực, toàn vẹn và tin cậy. ISO/IEC SC27 cũng bắt đầu xem xét các chuẩn cho ECC. Trong ANSI X9.25 có sơ đồ chữ ký ECC là ECDSA( Elliptic Curve Digital Signature Algorithm) và trong ANSI X9.63 có các chuẩn về thoả thuận và truyền khoá. ECC cũng đã đƣợc hỗ trợ trong các chuẩn mới của Internet về Phan Thị Thu Hiền - 29 - Lớp CT702
  31. Đồ án tốt nghiệp Hệ mật đường cong elliptic bảo mật cho tầng IP(IPSEC, ISAKMP, Oakley). Trong các chuẩn liên quan đến công nghiệp có SET(Secure Electronic Transaction). ANSI X9. ECC đã đƣợc thử nghiệm trong 2 lĩnh vực bởi ANSI ASC X9(dịch vụ tài chính). ANSI X9.62, chữ ký số ECDSA, ANSI X9.63, giao thức thoả thuận khoá ECC ECKA(Elliptic Curve Key Agrement) và giao thức giao vận ECTP (Transport Protocols). ANSI TG-17 (Technical Guideline on Mathematical Background for Elliptic Curve Cryptosystems) chứa các thông tin mở rộng về mặt toán học cho ECC, bao gồm các thuật toán đếm số các điểm trên đƣờng cong Elliptic. ATM Forum. Cung cấp cơ chế bảo mật cho các mạng ATM (chế độ truyền thông không đồng bộ Asynchronous Transfer Mode). Các dịch vụ bảo mật bao gồm tính tin cậy, chính xác thực, toàn vẹn dữ liệu, điều khiển truy cập. ECC là một trong các hệ thống đƣợc hỗ trợ. Certicom. Certicom đã xuất bản các tài liệu về ECC. ECC trong X.509 mô tả cơ chế sử dụng các khoá ECC trong X.509 framework. Ví dụ nó định nghĩa các định dạng chứng chỉ và định dạng danh sách thu hồi chứng chỉ. Các chuẩn cho mã hoá ECC(SEC 1 Standards for Efficient Cryptography): ECC, các sơ đồ mã hoá khoá công khai trên ECC. Đặc biệt là các sơ đồ chữ ký điện tử, các sơ đồ mã hoá và các sơ đồ thoả thuận khóa. SEC.2 bao gồm các tham số đƣợc khuyến nghị cho mã hoá ECC, danh sách các tham số ECC đƣợc yêu cầu tƣơng ứng với các cấp độ bảo mật khác nhau. FSTC. FSTC (Financial Services Technology Consortium) liên quan đến các hệ thống thanh toán điện tử và các dịch vụ tài chính khác. Các thanh toán điện tử có thể sử dụng rất nhiều thiết bị khác nhau nhƣ máy tính cá nhân, điện thoại màn hình, máy ATM, hoặc các hệ thống kiểm toán. ECC đƣợc sử dụng để mã hoá Email truyền gửi các sec điện tử. Phan Thị Thu Hiền - 30 - Lớp CT702
  32. Đồ án tốt nghiệp Hệ mật đường cong elliptic IEEE P1363. ECC đã đƣợc đƣa ra trong chuẩn phác thảo IEEE P1363(Đặc tả các chuẩn cho mật mã khoá công khai), bao gồm mã hoá, chữ ký số, các cơ chế thoả thuận khoá. Các đƣờng cong Elliptic có thể m m định nghĩa theo modulo p hoặc trên trƣờng F2 , trƣờng có 2 phần tử. IETF.(Internet Engineering Task Force). Mô tả giao thức thoả thuận khoá là biến thể của giao thức thoả thuận khoá Diffie-Hellmal. Nó cho phép sử dụng các nhóm khác nhau, bao gồm cả nhóm đƣờng cong Elliptic. Các nhóm trên đƣờng cong Elliptic đƣợc khuyến nghị m 210 dùng là các trƣờng F2 và F2 . ISO/IEC. Bản phác thảo ISO/IEC 14888, các cơ chế dựa trên chứng chỉ, các thuật toán ký tƣơng tự nhƣ DSA. NIST. (Viện nghiên cứu chuẩn quốc tế- National Institute of Standards). NIST cũng có các đặc tả cho ECC trong MISPC. SET. Chuẩn SET(Secure Electronic Transactions) đƣợc phát triển cho các giao dịch thẻ tín dụng trên Internet. ECC đƣợc xem xét nhƣ một chuẩn SET mới cho thƣơng mại điện tử trên Internet. Những lợi ích mà ECC mang lại cho các ứng dụng quan trọng đạng đƣợc đánh giá kĩ lƣỡng. WAP. Wireless Application Protocol, cung cấp cơ chế truy cập Internet an toàn cho các thiết bị không dây nhƣ điện thoại, thiết bị không dây đầu cuối. Các đặc tả giới thiệu trong kiến trúc mạng cho phép các ứng dụng sử dụng các lựa chọn giao thức truyền khác nhau và giữa các thiết bị khác nhau. ECC cũng đƣợc hỗ trợ trong tầng bảo mật WAP WTLS(Wireless Transport Layer Security). Phan Thị Thu Hiền - 31 - Lớp CT702
  33. Đồ án tốt nghiệp Hệ mật đường cong elliptic KẾT LUẬN Công nghệ thông tin đã và đang là một trong những lĩnh vực đem lại nhiều lợi ích cho xã hội, nó không thể thiếu trong nền kinh tế hội nhập và toàn cầu hoá. An toàn và bảo mật thông tin là một trong những yếu tố quan trọng cho nhiều ứng dụng trong thực tiễn. Trong quát trình nghiên cứu các giải pháp bảo mật ngƣời ta đã phát minh hệ mã hoá công khai dựa trên đƣờng cong elliptic. Cho đến nay hệ mã hóa đƣờng cong elliptic đƣợc xem là hệ mã hoá an toàn và hiệu quả nhất. So với các hệ mã hoá công khai khác, ECC đƣợc xem là ƣu việt hơn bởi ở cùng độ bảo mật nhƣ nhau thì độ dài khoá trong ECC nhỏ hơn nhiều so với các hệ mã hoá khác. Điều này dẫn tới các hệ mã hoá ECC có khả năng thực thi nhanh hơn, hiệu quả hơn các hệ mã hóa công khai khác. Phan Thị Thu Hiền - 32 - Lớp CT702
  34. Đồ án tốt nghiệp Hệ mật đường cong elliptic TÀI LIỆU THAM KHẢO Tài liệu tiếng việt [1] Phan Đình Diệu (1999), Lý thuyết mật mã và an toàn thông tin- NXB Đại Học Quốc Gia Hà Nội. [2] Phạm Huy Điển, Hà Duy Khoái (2003), Mã hoá thông tin: Cơ sở toán học và ứng dụng- NXB Đại Học Quốc Gia. Tài liệu tiếng việt [3] Neal Kobliz: A Corse in Number Theory and Cryptography. Sprirger- Verlag: Network, Berlin Heidelberg London, Paris, Tokyo 1987 [4] Stphen B. Wicker: Error Control Systems for Digital communication and storage. Shool of electrical computer- Engineering. Georgra institute of Technology, Prentice Hall – NewJersey- 2003. [5] A.j. Menzes: Elliptic curse public key crypto system, Klwer Academic publishers, Massachusetts, USA -1993. Phan Thị Thu Hiền - 33 - Lớp CT702