Tóm tắt luận văn Nghiên cứu hệ mật đường cong elliptic và ứng dụng

1 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- Hoàng Thị Xuân NGHIÊN CỨU HỆ MẬT ĐƯỜNG CONG ELLIPTIC VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KỸ THUẬT HÀ NỘI - 2013 2 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: GS. Nguyễn Bình Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 3 MỞ ĐẦU Lý do chọn đề tài Sự phát triển 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. Do vậy một số vấn đề phát sinh là thông tin có thể bị trộm cắp, có thể sai lệch, có thể giả mạo. Điều đó có thể ảnh hưởng đến các tốc chức, các công ty hay cả một quốc gia. Để 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. Các nhà khoa học đã phát minh ra những hệ mật ma nhằm che dấu thong tin cũng như là làm rõ chúng để tránh kẻ cố tình phá hoạt các hệ mật: RSA, Elgamal … Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của Luận văn: - Cơ sở toán học hệ mật dựa trên các đường cong Elliptic. - Các tấn công và độ phức tạp của các tấn công trên hệ mật Elliptic. - Giao thức bảo mật mạng sử dụng hệ mật Elliptic. Phạm vi nghiên cứu của Luận văn: - Luận văn tập trung tìm hiểu về các đánh giá tấn công hệ mật đường cong Elliptic, tìm hiểu một số hệ mật trên các đường cong Elliptic. - Dựa trên các cơ sở lý thuyết và tìm hiểu, xây dựng ứng dụng bảo mật mạng riêng ảo sử dụng hệ mật Elliptic. Mục đích nghiên cứu - Làm rõ các phương pháp tấn công trong hệ mật đường cong Elliptic. - Ứng dụng trong một bài toán bảo mật mạng cụ thể. Bố cục luận văn: Luân văn này gồm 03 chương cùng với phần mở đầu, kết luận và các danh mục: Chương 1: Tổng quan về hệ mật đường cong Elliptic Chương 2: Mật mã đường cong Elliptic Chương 3:Ứng dụng trong bài toán bảo mật mạng riêng ảo CHƯƠNG I – TỔNG QUAN VỀ HỆ MẬT ĐƯỜNG CONG ELLIPTIC 1.1 Cơ sở toán học hệ mật đường cong Elliptic 1.1.1 Các định nghĩa Định nghĩa 1. 4 Một đường cong Elliptic dạng Weierstrass đầy đủ là tập tất cả các điểm với 3 tọa độ x, y, z thỏa mãn phương trình: Với (1.1) y2 z a xyz  ayz 3  x 3  a x 2 z  a xz 2  a z 3 1 1a1, a 2, a 3, a 4, a 6  2 4 6 Phương trình đường cong Elliptic dạng Weierstrass rút gọn sẽ được biểu diễn bởi phương trình: (1.2) 23 với E:; y x  Ax  B AB,  p Định nghĩa 2: Biệt thức của đường cong E được xác định bởi công thức: (1.3) 16 4AB32  27  Định nghĩa 3: Gọi 32. Một điểm được gọi là điểm không kì dị nếu f( x , y ) x  Ax  B  P y( x , y ) E có ít nhất một trong hai đạo hàm df hoặc df khác 0. Điều này có nghĩa là nếu cả hai đạo dx dy hàm này bằng 0 thì điểm P sẽ được coi là điểm kì dị. Định nghĩa 4: Đường cong Elliptic E được coi là đường cong không kì dị nếu tất cả các điểm của nó là không kì dị. Ngược lại, nếu có ít nhất một điểm kì dị thì đường cong được coi là đường cong kì dị. Định nghĩa 5: Đại lượng j – bất biến của đường cong E khi là: 0 (1.4) 4A3 j j( E ) 1728 4AB32 27 Định nghĩa 6: Hai đường cong E và E’ xác định bởi phương trình Weierstrass rút gọn với các biến số tương ứng là (x, y) và (x’, y’) được gọi là đẳng cấu trên trường nếu và chỉ nếu tồn tại các hằng số và * sao cho khi thực hiện đổi biến 2 thì E 3 2 r,, s t u x u x'  r ; y  u y '  su x '  t biến thành E’. Có hai giá trị đặc biệt của j – bất biến là:  j = 0: Khi đó đường cong Elliptic có dạng 23 . y x B  j = 1728: Đường cong Elliptic có dạng 23 . y x Ax Định nghĩa 7: Nếu hai đường cong Elliptic khác nhau được xác định trên một trường có cùng một j – bất biến thì ta gọi chúng là “xoắn đôi” (twist) của nhau. Đường cong xoắn đôi với đường cong với j – bất biến là j có dạng: (1.5) 32jj y23 x  x ; j  0,1728 1728jj 1728 Định nghĩa 8: Một đường cong Elliptic E định nghĩa trên được gọi là đường cong siêu kì dị nếu p không có điểm bậc p. 5 Định nghĩa 9: Đường cong Elliptic E định nghĩa trên thỏa mãn được gọi là các đường p # Ep p   cong bất quy tắc. 1.1.2 Hệ mật dựa trên đường cong Elliptic Tập hợp tất cả các điểm với thỏa mãn phương trình của đường cong E xy,  xy,  p và với một điểm  ở vô cực cùng với một phép toán cộng sẽ tạo thành một nhóm, gọi là nhóm các điểm trên đường cong Elliptic trong , ký hiệu là . p E p   Phép cộng điểm: Cho hai điểm và phân biệt trên đường cong Elliptic P1 P2 E. Tổng của và , ký hiệu là , được định nghĩa như sau: P1 P2 P3 Kẻ một đường thẳng đi qua và . Đường thẳng này sẽ cắt E tại một điểm thứ 3, P1 P2 được ký hiệu là . Tiếp tục kẻ đường thẳng đi qua và vuông góc với trục , đường ' ' x P3 P3 thẳng này sẽ cắt E tại điểm thứ hai chính là điểm . P3  Phép nhân đôi một điểm: Cho là một điểm trên E . Nhân đôi điểm , ký P1 P1 hiệu là , được định nghĩa như sau: Kẻ qua một tiếp tuyến của E , tiếp P1 P 12 P 1 P1 tuyến này cắt E tại điểm thứ hai, ký hiệu là R . Kẻ đường thẳng đi qua R và vuông góc với trục , đường thẳng này cắt E tại điểm thứ hai chính là . x 2P1 Cho E là một đường cong Elliptic xác định bởi phương trình 23 . Gọi y x   x  B và là các điểm trên E với . Khi đó với P ( x , y ) P2 ( x 2 , y 2 ) PP12,  P1 P 2  P 3  ( x 3 , y 3 ) 111 được tính như sau: xy33, (1) (Công thức cộng điểm) Nếu , thì xx12 , , với . 2 x3 m  x 1  x 2 y m x  x  y yy 3 1 3 1m  21 xx21 (2) Nếu nhưng , thì . xx12 yy12 PP12   (3) (Công thức nhân đôi điểm) Nếu và , thì PP12 y1  0 , với 2 2 3xA x3 m  x 1  x 2 y m x  x  y 1 3 1 3 1m  2y1 (4) Nếu và , thì . PP12 y1  0 PP12   (5) . P1  P 1;  P 1  E Phép cộng điểm trên đường cong Elliptic thỏa mãn các tính chất sau: E (1) Tính giao hoán: với mọi trên . E P1 P 2  P 2  P 1 PP12, (2) Tồn tại phần tử đơn vị: PP   với mọi P trên E . (3) Tồn tại phần tử nghịch đảo: Với điểm P cho trước trên E , tồn tại một điểm P' E trên sao cho PP'   . Điểm P' thường được kí hiệu là P . (4) Tính kết hợp: . (P1 P 2 )  P 3  P 1  P 2  P 3  P 1 , P 2 , P 3  E 6 1.1.2.1 Các tự đồng cấu Một tự đồng cấu E nghĩa là một đồng cấu được cho bởi các hàm hữu  :EE ( ) ( ) tỉ. Nói cách khác, , và có các hàm hữu tỉ (thương của các đa chức) P1 P 2   P 1    P 2  , với các hệ số trong sao cho R1  x, y R2  x, y  x, y  R12 x , y , R x , y  x , y  E   Một tự đồng cấu được gọi là tự đồng cấu tách được nếu đạo hàm '  xy,0  R1  x, y không đồng nhất bằng không. 1.1.2.2 Các điểm n – xoắn Các điểm xoắn, chính là các điểm có bậc hữu hạn, đóng một vai trò quan trọng trong nghiên cứu các đường cong Elliptic. Cho E là một đường cong Ellip được xác định trên một trường . Giả sử n là một số nguyên dương. Theo [6] tập các điểm n-xoắn được định nghĩa bởi: (1.7) E n  P  E  | nP   1.1.2.3 Đa thức chia Đa thức chia thứ - m của đường cong Elliptic E , , được xác định bởi  m  [x , y , A , B ] dãy các công thức toán học truy hồi sau đây: 00,  1  1,  2  2y 4 2 2  3 3x  6 Ax  12 Bx  A 6 4 3 2 2 2 3  4 4y ( x  5 Ax  20 Bx  5 A x  4 ABx  8 B  A ) Với 33m  2 2m 1  m  2  m  m  1  m  1 Với . m  2 1 22 2m2y   m  m 2  m  1  m  2  m  1  Cho là một điểm trên đường cong Elliptic 3 (trên một trường P  x, y y x A x  B nào đó có đặc số khác 2), và là một số nguyên dương. Khi đó: n (1.8) x  x, y nP  nn,  2 x 3 n    n xy,  1.1.3 Cặp Weil Cho E là một đường cong Elliptic trên một trường và cho là một số nguyên không n chia hết cho đặc số của . Khi đó . Đặt: En  nn (1.9) n n xx |1   Là nhóm của các căn bậc của phần tử đơn vị trong . Vì đặc số của không chia n hết cho , nên phương trình n không có nghiệm bội, do đó nó có nghiệm trong . Do n x 1 n 7 vậy, là một nhóm cyclic bậc . Một phần tử sinh của được gọi là một căn nguyên n  n n thủy bậc . Điều này tương đương với việc nói rằng k khi và chỉ khi chia hết cho . n  1 n k Định lý [6 – Theorem 3.9]: Cho E là một đường cong Elliptic xác định trên một trường và cho là một số n nguyên dương. Giả sử rằng đặc số của trường không chia hết cho . Khi đó một phép n ghép cặp: (1.10) enn: E n E n  1.2 Đường cong Elliptic 1.2.1 Đặt vấn đề bài toán Đường cong elliptic là tập hợp các điểm có toạ độ thoả mãn phương trình có xy,  dạng sau đây: 2 3 2 y a1 xy  a 3 y  x  a 2 x  a 4 x  a 6 Trên trường F biểu diễn bằng phương trình Weiretrass: (1.11) 32 ya1 xy  a 3 y  x  a 2 x  a 4 x  a 6 Xét đường cong E trên trường nguyên tố hữu hạn ( nguyên tố, >3 ) với công p p Fp thức biến đổi như sau: 23 (1.12)    ab   Hình 1: Một ví dụ về đường cong Elliptic Định nghĩa: Giả sử  là một trường có đặc số khác 2 và khác 3 và xét đa thức 3 (với a,  ab   b   ). Khi đó đường cong elliptic trên trường : 23 là tập hợp tất cả các    ab   điểm (x, y) với x, y   sao cho (1.12) không có các nghiệm bội tức là 4a32 27 b 0mod p cùng với phần tử O - điểm O này được gọi là điểm vô hạn. Tính chất của đường cong elliptic: 8 Nếu hai điểm và với nằm trên đường cùng một đường 1(x 1 y 1 ) 2(x 2 y 2 ) xx12 cong elliptic  , thì đường thẳng qua hai điểm và sẽ cắt một điểm duy nhất  1 2 3x 3 , y 3  có thể xác định thông qua và nằm trên đường cong  . 1 2 Tiếp tuyến của đường cong tại điểm bất kỳ trên đường cong  cũng cắt đường P x, y cong elliptic  tại một điểm duy nhất nằm trên đường  , điểm này cũng có thể xác định được thông qua P. 1.2.2 Đường cong elliptic trên trường hữu hạn Xét trường hữu hạn của r phần tử trên trường hữu hạn . Giả sử E là đường q = p Fq cong elliptic được định nghĩa trên . Nếu đặc số của trường hoặc thì E được p  2 p  3 Fq cho bởi phương trình ở (1.13) và (1.14) . Định lý: Gọi N là số các điểm trên đường cong elliptic được định nghĩa trên . Khi Fq đó N q  1  2 q 1.2.3 Các phép toán trên đường cong Elliptic 1.2.3.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   x 1 – x 2 , y 3   x 1 – x 3 – y 1 Với: y2 – y 1  x 2 – x 1  Khi P ≠ Q( nếu x1 = x2 th ì là hệ số góc đường    thẳng qua P và Q) (1.17)      2 Khi P = Q ( là đạo hàm của đường cong tại P) (1.18) 3x a 2 y    1 9 2 1 R Q P R 2P P P+ Q -1 -2 Hình 2: Phép cộng trên đường cong Elliptic 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:  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 thì luôn tồn tại phần tử Px , y E để P + (-P) = O. Px , - y E  Tính chất giao hoán: Nếu P, Q  E thì P + Q = Q + P. 1.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 ( k phép cộng điểm P). Q E : k  P  P  P  P  P 10 Hình 3: Ví dụ phép nhân đôi trên đường cong Elliptic 1.2.4 Đếm số điểm trên đường cong Elliptic trên trường Fq 1.2.4.1 Định lý Hasse N là số điểm của E trên trường Fq (trường hữu hạn q phần tử). Khi đó: . Từ định lý Hasse suy ra trong đó N – q  1 2 q   #E q   q 1 – t . t  2 q 1.2.4.2 Đị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. 1.2.5 Phương pháp chọn đường cong Elliptic phù hợp và điểm cơ sở 1.2.5.1 Trường Một đường cong elliptic trên một trường hữu hạn tạo thành nhóm Abelian được sử dụng trong mật mã học. Một ví dụ là việc chọn trường giúp thực hiện các phép tính nhanh r F2 và dễ dàng triển khai được trên các thiết bị cứng. Tuy nhiên, các đường cong trên trường r F2 có thể bị tấn công bởi MOV, trong khi các đường cong trên trường (p là số nguyên tố lớn) Fp lại chống lại được kiểu tấn công này. Một chú ý nữa là việc tính số điểm trên # . Tốc E() độ của thuật toán Shoof phụ thuộc vào kích thước và đặc số của trường K. 1.2.5.2 Dạng của đườ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à supersingular. Xét Fq có đặc số là . Khi đó: 2  g  2m  11  Tập tất cả các cặp nghiệm (x, y) của phương trình với a, b, y23 ax  x  bx  c 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 supersin gular.  Tập tất cả các cặp nghiệm (x, y) của phương trình với a, b, y23 ax  x  bx  c 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. 1.2.5.3 Phương pháp lựa chọn Phương pháp- 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) (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ông 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. 1.2.6 Đánh giá các tấn công hệ mật đường cong Elliptic 1.2.6.1 Phương pháp Pohlig - Hellman Cho là các phần tử trong nhóm hữu hạn G bậc N. Ta muốn tìm một số nguyên k PQ, với . Giả sử biết phân tích ra thừa số nguyên tố của N là: kP Q Nn ei i i Phương pháp Pohlig – Hellman thực hiện tốt nếu tất cả các ước nguyên tố của N là nhỏ. Nếu ước nguyên tố lớn nhất xấp xỉ lớn của N thì phương pháp Pohlig – Hellman rất khó áp dụng. Vì lý do này, các hệ mật dựa trên logarith rời rạc, nói chung thường chọn bậc của nhóm có chứa một thừa số nguyên tố lớn. 1.2.6.2 Tấn công MOV Thuật toán 1: Tấn công MOV Input: , , , ord() P N gcd(N , p )  1Q kP P, Q E (p ) Output: kN(mod ) (1). Chọn một điểm ngẫu nhiên TE () pm (2). Tính bậc M của T 12 (3). Đặt , đặt . Khi đó có bậc chia hết cho , d N d gcd( M , N ) T1  ( M / d ) T T1 vậy T1  E N (4). Tính và . Khi đó cả , đều thuộc vào  1 e N( P , T 1 )  2 e N( P , T 2 )  1  2   * d pm (5). Giải bài toán log rời rạc trong . Kết quả cho ta . k 21 * kd(mod ) pm (6). Lặp lại với các điểm ngẫu nhiên T đến khi bội chung nhỏ nhất của các số d khác nhau thu được là N. Khi đó ta xác định được kN(mod ) 1.2.6.3 Phương pháp Xedni Thuật toán tính chỉ số ngược đầu tiên là nâng các điểm , sau đó chọn một P1, P 2 ,..., P n đường cong Elliptic chứa các điểm đã nâng và hy vọng rằng chúng phụ thuộc tuyến EQ  tính. Nghĩa là thỏa mãn quan hệ r . Tuy nhiên, xác suất để chúng phụ thuộc tuyến nii P 0 i1 tính là nhỏ. 1.2.6.4 Các tấn công dựa trên giả thuyết Diffie – Hellman Cho G là một nhóm Abel bậc nguyên tố và là phần tử sinh của G. Bài toán p g logarith rời rạc DLP trong G là bài toán tìm số khi biết và trong G. Nhiều hệ a g g a p mật được thiết kế dựa trên bài toán DLP, tuy nhiên hầu hết chúng có độ an toàn tương đương với một biến thể yếu hơn của bài toán DLP. Hai biến thể yếu hơn quan trọng nhất là bài toán DH – Tính toán CDH và bài toán DH – Quyết định DDH. CDH: Cho . Tính ? ab  g,, gab g  g DDH: Cho . Xác định xem trong hay không? abc c ab  g, g , g , g  p 1.2.6.5 Các tấn công cài đặt Kiểu tấn công cài đặt thứ nhất là dựa trên điểm không hợp lệ của đường cong Elliptic. Nếu trong quá trình nhận và xử lý một điểm trên đường cong mà không thực hiện việc kiểm tra xem nó có thực sự nằm trên đường cong đã cho hay không thì lược đồ có thể bị tấn công. Dạng tấn công thứ hai là kiểu tấn công phân tích năng lượng để khám phá khóa bí mật.. Hiệu quả của các kiểu tấn công này phụ thuộc vào cách cài đặt cụ thể. 1.2.6.6 Nhận xét Tổng hợp các phương pháp trên ta có bảng như sau: 13 Bảng 1: So sánh các phương pháp tấn công hệ mật Elliptic STT Phương Độ phức tạp của thuật toán Yêu cầu Ghi chú pháp trong nhóm có bậc là N bộ nhớ 1 Pohlig - Nhỏ Hiệu quả nếu N chỉ có OK với K là ước nguyên tố Hellman lớn nhất của N các ước nguyên tố nhỏ. 2 MOV Nhỏ Hiệu quả nếu nhỏ ~ m DLP *  pm  3 Xedni - Không áp dụng được ON() trong thực tế 4 Tấn công với d là ước của Yêu cầu giả thuyết O( d .log p ) dựa vào p mạnh, cần bộ nhớ lớn O 3 d một số giả p d p  thuyết DH 5 Tấn công Phụ thuộc vào cách cài đặt cụ Nhỏ Thời gian đa thức theo cài đặt thể Conron. Kết luận chương Các kết quả mà chương 1 đạt được bao gồm: (1) Đã nghiên cứu tổng quan về hệ mật Elliptic trên trường hữu hạn, nghiên cứu về các vấn đề như đa thức chia, nhóm con xoắn, các tự đồng cấu, Weil pairing. (2) Nghiên cứu, xem xét và đánh giá về độ phức tạp tính toán, yêu cầu bộ nhớ và khả năng áp dụng trong thực tế của các tấn công đối với hệ mật Elliptic. CHƯƠNG 2 – MẬT MÃ ĐƯỜNG CONG ELLIPTIC 2.1 Mật mã đường cong Elliptic 2.1.1 Thiết lập cơ sở Alice muốn gửi một văn bản, thường được gọi là bản rõ (Plaintext), tới Bob. Cô ấy mã hóa văn bản để thu được bản mã (Ciphertext). Để mã hóa văn bản, Alice sử dụng một khóa mã hóa (Encryption key). Bob sử dụng một khóa giải mã (Decryption key) để giải mã bản mã nhận được. Có hai cách mã hóa cơ bản. Trong mật mã đối xứng (Symmetric Encryption), khóa mã hóa và khóa giải mã là như nhau, Một dạng khác của mã hóa là mật mã khóa công khai (Public Key Encryption), hoặc mật mã không đối xứng (Asymmetric Encryption). 14 Hình 4: Mô phỏng mã hóa công khai 2.1.2 Nhúng bản rõ lên đường cong Nhúng 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, nhờ đó 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à “nhúng” (Imbeding) và “mặt nạ” (Mask). 2.1.3. Logarith rời rạc trên đường cong Elliptic Định nghĩa: 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 , tìm số nguyên P E xZ sao cho xB = P (nếu số x như vậy tồn tại) 2.1.4 Trao đổi khóa Diffie – Hellman Alice và Bob muốn thống nhất một khóa chung mà họ có thể sử dụng cho việc trao đổi dữ liệu thông qua một sơ đồ mã đối xứng. Alice và Bob thống nhất một đường cong elliptic E trên trường hữu hạn Fq sao cho bài toán logarithm rời rạc là khó trong E(Fq). Thông tin duy nhất mà kẻ trộm Eve thấy chỉ là đường cong E, trường hữu hạn Fq, và các điểm P, aP và bP. Do đó cô ta cần phải giải quyết các bài toán sau: 2.1.4.1 Bài toán Diffie – Hellman Cho trước P, aP và bP trong E(Fq), tính abP? Nếu Eve có thể giải bài toán log rời rạc trong E(Fq), khi đó cô ta có thể sử dụng P và aP để tìm a. Khi đó cô ta có thể tính a(bP) để nhận được abP. Tuy nhiên, liệu có thể có cách nào để tính abP mà không phải giải bài toán log rời rạc đầu tiên. 2.1.4.2 Bài toán quyết định Diffie – Hellman Cho trước P, aP và bP trong E(Fq) và cho trước một điểm Q ∈ E(Fq). Khi đấy có xác định được Q = abP hay không? 15 Cho E là đường cong trên Fq, vớ