Luận văn Nghiên cứu phát triển mã hóa trên đường cong elliptic dựa trên chuỗi cơ số kép tối ưu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ————————— Đặng Thị Liên NGHIÊN CỨU PHÁT TRIỂN MÃ HÓA TRÊN ĐƯỜNG CONG ELLIPTIC DỰA TRÊN CHUỖI CƠ SỐ KÉP TỐI ƯU LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2016 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ————————— Đặng Thị Liên NGHIÊN CỨU PHÁT TRIỂN MÃ HÓA TRÊN ĐƯỜNG CONG ELLIPTIC DỰA TRÊN CHUỖI CƠ SỐ KÉP TỐI ƯU Chuyên ngành: Cơ sở toán cho tin học Mã số : 60460110 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Hải Vinh Hà Nội - 2016 LỜI CẢM ƠN Được sự phân công của khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, Đại Học Quốc Gia Hà Nội, được sự đồng ý của Thầy giáo hướng dẫn TS. Nguyễn Hải Vinh, tôi đã thực hiện đề tài "Nghiên cứu phát triển mã hóa trên đường cong Elliptic dựa trên chuỗi cơ số kép tối ưu". Để hoàn thành luận văn này, tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Hải Vinh - người Thầy đã trực tiếp hướng dẫn và chỉ bảo giúp tôi hoàn thành luận văn thạc sĩ. Tôi cũng xin chân thành cảm ơn các Thầy, Cô giáo đã tận tình hướng dẫn, giảng dạy trong suốt quá trình tôi học tập và rèn luyện tại trường. Qua đây, tôi xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp - những người đã luôn bên cạnh cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận văn này. Mặc dù tôi đã cố gắng thực hiện luận văn song do kiến thức của tôi còn nhiều hạn chế nên luận văn không tránh khỏi những thiết sót nhất định. Do đó, tôi rất mong được sự góp ý của quý Thầy, Cô giáo và các bạn để luận văn của tôi được hoàn thiện hơn. Tôi xin chân thành cảm ơn!. Hưng Yên, ngày..... tháng ..... năm 2016 Học viên Đặng Thị Liên BẢNG KÍ HIỆU, CHỮ VIẾT TẮT STT Kí hiệu Dạng đầy đủ Ý nghĩa 1 DBC Double Base Chains Chuỗi cơ số kép 2 DBNS Double Base Number System Hệ biểu diễn cơ số kép 3 EC Elliptic Curve Đường cong Elliptic 4 ECC Elliptic Curve Cryptography Hệ mật mã đường cong Elliptic 5 NAF Non Adjacent Form Dạng hình thức không liền kề 6 I Field Inversions Phép nghịch đảo trường 7 S Field Squarings Phép bình phương trường 8 M Field Multiplications Phép nhân trường 9 RSA Cryptosystem proposed by Rivest, Shamir, Adleman Hệ mật mã khóa công khai RSA 10 Ds Digit set Tập các số 2 Mục lục Lời mở đầu 5 Chương 1 Cơ sở lý thuyết 7 1.1 Sơ lược về mật mã học . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Đường cong Elliptic trên trường nguyên tố hữu hạn . . . . . . . . . . . . 10 1.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Tính chất của đường cong Elliptic . . . . . . . . . . . . . . . . . . 12 1.2.3 Các phép toán trên đường cong Elliptic . . . . . . . . . . . . . . . 13 1.2.4 Chi phí của một số phép toán trên điểm . . . . . . . . . . . . . . 16 1.3 Hệ mật mã dựa trên đường cong Elliptic . . . . . . . . . . . . . . . . . . . 20 1.3.1 Quá trình mã hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.2 Quá trình giải mã . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Chương 2 Một số phương pháp và chi phí tính phép nhân vô hướng trên đường cong elliptic 24 2.1 Đặt bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Một số phương pháp và chi phí tính phép nhân vô hướng trên đường cong elliptic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.1 Phương pháp Double-and-Add . . . . . . . . . . . . . . . . . . . 24 2.2.2 Phương pháp sử dụng chuỗi hình thức không liền kề (NAF) . . . 27 2.2.3 Phương pháp sử dụng chuỗi cơ số kép tối ưu . . . . . . . . . . . . 30 Chương 3 Áp dụng tính toán thực tế 50 3.1 Tính toán trên cơ sở lý thuyết . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1.1 Chi phí của phương pháp Double-and-Add . . . . . . . . . . . . . 50 3.1.2 Chi phí của phương pháp NAF . . . . . . . . . . . . . . . . . . . 51 3.1.3 Chi phí của phương pháp sử dụng DBC trên miền Ds = {0, 1} . . 53 3 3.1.4 Chi phí của phương pháp sử dụng DBC trên miền Ds = {0, 1,−1} 54 3.2 Kết quả dựa trên cơ sở chạy chương trình . . . . . . . . . . . . . . . . . . 58 3.3 Ứng dụng mã hóa và giải mã đường cong Elliptic . . . . . . . . . . . . . . 59 3.3.1 Hệ mật mã khóa công khai ElGamal . . . . . . . . . . . . . . . . 60 3.3.2 Cài đặt chương trình sử dụng phương pháp ElGamal . . . . . . . 60 Kết luận 64 Phụ lục 65 Tài liệu tham khảo 68 4 LỜI MỞ ĐẦU Ngày nay, sự phát triển của công nghệ thông tin, truyền thông nói chung và đặc biệt là sự bùng nổ của internet nói riêng đã giúp cho việc trao đổi thông tin trở nên nhanh chóng, dễ dàng. Song song với những lợi ích của nó vẫn tồn tại một số vấn đề trong quá trình lưu trữ và truyền tải thông tin, đó là thông tin có thể bị đánh cắp, bị sai lệch hoặc có thể bị giả mạo. Điều này có thể ảnh hưởng đến các tổ chức, các công ty hay cả một quốc gia. Để giải quyết vấn đề 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 mã nhằm che dấu thông 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 . . .mặc dù cũng rất an toàn, tuy nhiên độ dài khóa 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 ra một hệ mật đó là hệ mật mã dựa trên đường cong elliptic. Hệ mật này được đánh giá có độ bảo mật an toàn cao và hiệu quả hơn một số hệ mật công khai khác do khả năng bảo mật của ECC cao với kích thước khóa nhỏ nên làm giảm thời gian tạo khóa, 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. Mục đích của luận văn là nghiên cứu phương pháp giảm thời gian tạo khóa bằng cách tập trung vào hệ thắt nút cổ chai của ECC - "phép nhân với đại lượng vô hướng" (gọi tắt là nhân vô hướng) Q = rS, với S,Q là 2 điểm trên EC, r là một số nguyên dương. Thời gian tính toán của hệ này phụ thuộc mạnh mẽ vào biểu diễn của vô hướng r, các biểu diễn thường gặp như là chuỗi nhị phân, chuỗi hình thức không liền kề, chuỗi cơ số kép, ... Yêu cầu đặt ra đối với hệ mật mã dựa trên đường cong elliptic chính là giảm bớt khó khăn trong phép tính Q = rS bởi với mỗi vô hướng r có nhiều cách để biểu diễn r nên ta có được các phương pháp tính nhân vô hướng đặc trưng cho từng biểu diễn đó. Để làm rõ vai trò của biểu diễn vô hướng r trên hệ ECC cũng như sự phát triển các phương pháp thực hiện phép nhân vô hướng nhằm giảm chi phí, thời gian tính toán của quá trình mã hóa, tôi quyết định chọn đề tài: "Nghiên cứu phát triển mã hóa trên đường cong Elliptic dựa trên chuỗi cơ số kép tối ưu". Đối tượng nghiên cứu của luận văn bao gồm cơ sở toán học hệ mật dựa trên đường cong elliptic; các phương pháp và chi phí tính nhân vô hướng, tập trung vào phương pháp sử dụng chuỗi cơ số kép tối ưu trên các miền Ds khác nhau. 5 Phạm vi nghiên cứu của luận văn:Dựa trên sách và các bài báo khoa học liên quan đến hệ mật đường cong Elliptic, mà trọng tâm là bài báo "Fast Elliptic curve cryptogra- phy using optimal double - Base Chains" của nhóm tác giả Vorapong Suppakitpalsarn, Masato Edahiro, Hiroshi Imai. Bài báo này đề xuất phương án sử dụng chuỗi cơ số kép tối ưu để tính nhân vô hướng trên miền các miền Ds = {0, 1} và Ds = {0, 1,−1} Kết quả của luận văn là nghiên cứu quá trình hoàn thiện mã hóa trên đường cong Elliptic qua các phương pháp nhân vô hướng khác nhau. So sánh, đối chiếu các phương pháp và từ đó rút ra được phương pháp nào là hiệu quả và tối ưu hơn. Ứng với mỗi phương pháp này xây dựng chương trình minh họa cho nó. Dựa vào mục đích, phạm vi, đối tượng nghiên cứu, luận văn được trình bày bao gồm 3 chương chính cùng với phần mở đầu, kết luận và phụ lục: • Chương 1: Cơ sở lý thuyết • Chương 2: Một số phương pháp và chi phí tính phép nhân vô hướng trên đường cong Elliptic • Chương 3: Áp dụng tính toán thực tế. 6 Chương 1 Cơ sở lý thuyết 1.1 Sơ lược về mật mã học Mật mã đã được con người sử dụng từ lâu đời. Các hình thức mật mã sơ khai đã được tìm thấy từ khoảng bốn nghìn năm trước trong nền văn minh Ai Cập cổ đại. Trải qua hàng nghìn năm lịch sử, mật mã đã được sử dụng rộng rãi ở khắp nơi trên thế giới từ Đông sang Tây để giữ bí mật cho việc giao lưu thông tin trong nhiều lĩnh vực hoạt động giữa con người và các quốc gia, đặc biệt trong các lĩnh vực quân sự, chính trị, ngoại giao. Mật mã trước hết là một loại hoạt động thực tiễn, nội dung chính của nó là để giữ bí mật thông tin. Ví dụ muốn gửi một văn bản từ một người gửi A đến một người nhận B, A phải tạo cho văn bản đó một bản mã mật tương ứng và thay vì gửi văn bản rõ thì A chỉ gửi cho B bản mã mật, B nhận được bản mã mật và khôi phục lại văn bản rõ để hiểu được thông tin mà A muốn gửi cho mình. Do văn bản gửi đi thường được chuyển qua các con đường công khai nên người ngoài có thể “lấy trộm” được, nhưng vì đó là bản mật mã nên không đọc hiểu được; Còn A có thể tạo ra bản mã mật và B có thể giải bản mã mật thành bản rõ để hiểu được là do hai người đã có một thoả thuận về một chìa khoá chung, chỉ với khoá chung này thì A mới tạo được bản mã mật từ bản rõ và B mới khôi phục được bản rõ từ bản mã mật. Khoá chung đó được gọi là khoá mật mã. Để thực hiện được một phép mật mã, ta còn cần có một thuật toán biến bản rõ cùng với khoá mật mã thành bản mã mật và một thuật toán ngược lại biến bản mật cùng với khoá mật mã thành bản rõ. Các thuật toán đó được gọi tương ứng là thuật toán lập mã và thuật toán giải mã. Các thuật toán này thường không nhất thiết phải giữ bí mật, mà cái luôn cần được giữ bí mật là khoá mật mã. Trong thực tiễn, có những hoạt động ngược lại với hoạt động bảo mật là khám phá bí mật từ các bản mã “lấy trộm” được, hoạt động này thường được gọi là mã thám hay phá khoá [2]. Hiện nay, người ta chia hệ mật mã thành hai loại chính: • Mật mã khóa đối xứng, hay còn gọi là mật mã khóa bí mật [3] • Mật mã khóa bất đối xứng, hay còn gọi là mật mã khóa công khai [3] Nhắc đến hệ mật mã khóa bí mật, ta thấy ưu điểm nổi trội của nó là việc dùng chung một khóa để lập mã và giải mã được thực hiện nhanh chóng và đơn giản. Mặc dù mã hóa đối xứng đã phát triển từ cổ điển đến hiện đại nhưng vẫn tồn tại hai điểm yếu chính sau: 7 • Vấn đề trao đổi khóa giữa người gửi và người nhận: Cần có thêm một kênh an toàn để trao đổi khóa sao cho khóa được giữ bí mật chỉ có người gửi và người nhận được biết. Điều này trở nên cực kì khó khăn khi khối lượng thông tin truyền tải trên khắp thế giới rất lớn. Việc thiết lập một kênh an toàn như vậy sẽ tốn kém về mặt chi phí và chậm trễ về mặt thời gian. • Tính bảo mật của khóa: Vì khóa được dùng chung cho cả người gửi và người nhận nên khi khóa bị lộ không có cơ sở quy trách nhiệm cho người nào. Để giải quyết vấn đề phân phối và thoả thuận khoá của mật mã khoá đối xứng, năm 1976 Diffie và Hellman đã đưa ra khái niệm về hệ mật mã khoá công khai và một phương pháp trao đổi công khai để tạo ra một khoá bí mật chung mà tính an toàn được bảo đảm bởi độ khó của một bài toán toán học, cụ thể là bài toán tính logarit rời rạc [1]. Hệ mật mã khoá công khai hay còn được gọi là hệ mật mã phi đối xứng sử dụng một cặp khoá, khoá mã hoá còn gọi là khoá công khai (public key) và khoá giải mã được gọi là khoá bí mật hay khóa riêng (private key). Trong hệ mật này, khoá mã hoá khác với khoá giải mã. Về mặt toán học thì từ khoá công khai rất khó tính được khoá riêng. Biết được khoá này không dễ dàng tìm được khoá kia. Khoá giải mã được giữ bí mật trong khi khoá mã hoá được công bố công khai. Một người bất kỳ có thể sử dụng khoá công khai để mã hoá tin tức, nhưng chỉ có người nào có đúng khoá giải mã mới có khả năng xem được bản rõ. Người gửi A sẽ mã hoá thông điệp bằng khóa công của người nhận và người nhận B sẽ giải mã thông điệp với khoá riêng tương ứng của mình. Có nhiều hệ thống khoá công khai được triển khai rộng rãi như hệ RSA, hệ ElGa- mal sử dụng giao thức trao đổi khoá Diffie-Hellman và nổi lên trong những năm gần đây là hệ mật mã dựa trên đường cong Elliptic. Trong số các hệ mật mã trên, hệ mã hóa công khai RSA là hệ được cộng đồng chuẩn quốc tế và công nghiệp chấp nhận rộng rãi trong việc thực thi mật mã khoá công khai. Hệ mật mã RSA, do Rivest, Shamir và Adleman [3] tìm ra, đã được công bố lần đầu tiên vào tháng 8 năm 1977 trên tạp chí Scientific American. Hệ mật mã RSA được sử dụng rộng rãi trong thực tiễn đặc biệt cho mục đích bảo mật và xác thực dữ liệu số. Tính bảo mật và an toàn của chúng được bảo đảm bằng độ phức tạp của một bài toán số học nổi tiếng là bài toán phân tích một số thành các thừa số nguyên tố [1]. Để thực hiện mã hóa và giải mã bằng phương pháp RSA [2], RSA dùng phép lũy thừa modulo của lý thuyết số và thực hiện theo các bước sau: 8 1. Chọn hai số nguyên tố lớn p và q và tính N = pq. Cần chọn p và q sao cho: M < 2i−1 < N < 2i Với i = 1024 thì N là một số nguyên dài khoảng 309 chữ số. 2. Tính n = (p− 1)(q − 1) 3. Tìm một số e sao cho e nguyên tố cùng nhau với n 4. Tìm một số d sao cho e.d ≡ 1 (mod n) (d là nghịch đảo của e trong phép modulo n ) 5. Hủy bỏ n, p và q. Chọn khóa công khaiKU là cặp (e,N), khóa riêngKR là cặp (d,N) 6. Việc mã hóa thực hiện theo công thức: C = E(M,KU ) = M e mod N 7. Việc giải mã thực hiện theo công thức: M = D(C,KR) = C d mod N Đối với phương pháp RSA, để đảm bảo an toàn, chúng ta phải chọn số N lớn (1024 bít) nên việc sinh khóa, lập mã và giải mã phức tạp, dẫn đến tốc độ thực hiện chậm. Để khắc phục nhược điểm này, 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 [3] để xây dựng mã hóa dựa trên đường cong Elliptic. Mã hóa đường cong elliptic giải quyết vấn đề của mã hóa RSA khi dùng các tham số có kích thước ngắn hơn (168 bít) tuy nhiên vẫn đảm bảo độ an toàn như RSA 1024 bít. Ưu điểm nổi bật của ECC là hệ mật mã này sử dụng khoá có độ dài nhỏ hơn so với RSA. Từ đó làm tăng tốc độ xử lý một cách đáng kể, do số phép toán dùng để mã hoá và giải mã ít hơn và yêu cầu các thiết bị có khả năng tính toán thấp hơn, nên giúp tăng tốc độ và làm giảm năng lượng cần sử dụng trong quá trình mã hoá và giải mã. Sau đây, chúng ta sẽ tìm hiểu chi tiết về lý thuyết toán học đường cong elliptic trên trường nguyên tố hữu hạn và hệ mật mã dựa trên đường cong elliptic. 9 1.2 Đường cong Elliptic trên trường nguyên tố hữu hạn 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ố [1]. 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 nhỏ hơn cấp lũy thừa. Thuật toán tốt nhất được biết đến cho tới hôm nay tốn thời gian thực hiện cấp lũy thừa. 1.2.1 Định nghĩa Gọi K là một 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 Weierstrass (theo tài liệu [4, 7]): y2z + a1xyz + a3yz 2 = x3 + a2x 2z + a4xz 2 + a6z 3 trong đó a1, a2, a3, a4, a6 ∈ K. Đường cong elliptic trên trườngK được kí hiệu là E(K). Đối với từng trường khác nhau, công thức Weierstrass có thể được biến đổi và đơn giản hóa thành các dạng khác nhau. Trong luận văn này chỉ xét đường cong elliptic trên trường nguyên tố hữu hạn nên ta có dạng thu gọn của đường cong với định nghĩa như sau: Đường cong Elliptic E trên trường nguyên tố hữu hạn Zp kí hiệu là (E(Zp)), là đường cong có các hệ số thuộc trường Zp, đường cong này có dạng: (E(Zp)) : y 2 mod p = ( x3 + ax+ b ) mod p (1.2.1) với a, b ∈ Zp , ∆ = −16 ( 4a3 + 27b2 ) 6= 0 , char(Zp) > 3 , là tập tất cả các cặp điểm (x, y) với x, y ∈ Zp thỏa mãn phương trình trên cùng với một điểm O - được gọi là điểm tại vô cực. Ví dụ trong trường Z23, chọn a = 1, b = 1, x = 9, y = 7 ta có: 72 mod 23 = (93 + 9 + 1) mod 23 49 mod 23 = 739 mod 23 = 3 10 Khác với đường cong Elliptic trong trường số thực [1], chúng ta không thể biểu diễn đường cong Elliptic E(Zp) bằng đồ thị hàm số liên tục. Bảng bên dưới liệt kê các điểm (x, y) của đường cong y2 = x3 + x+ 1 trong trường Z23 với a = 1, b = 1 như sau: Bảng 1: Danh sách các điểm của đường cong y2 mod 23 = ( x3 + x+ 1 ) mod 23 (0, 1) (6, 4) (12, 19) (0, 22) (6, 19) (13, 7) (1, 7) (7, 11) (13, 16) (1, 16) (7, 12) (17, 3) (3, 10) (9, 7) (17, 20) (3, 13) (9, 16) (18, 3) (4, 0) (11, 3) (18, 20) (5, 4) (11, 20) (19, 5) (5, 19) (12, 4) (19, 18) Cũng tương tự khái niệm đối xứng qua trục hoành của đường cong Elliptic trên trường số thực E (R), đường cong Elliptic trên trường nguyên tố hữu hạn E(Zp) cũng đối xứng theo nghĩa đối xứng modulo. Thật vậy, giả sử điểm (x, y) thuộc E(Zp) thỏa mãn (1.2.1) thì điểm (x, p− y) cũng thuộc (1.2.1) vì: (p− y)2 mod p = (p2 − 2py + y2) mod p ≡ y2 mod p Ví dụ (1, 7) đối xứng với (1, 16) vì 7 + 16 = 0 mod 23 hoặc (3, 10) đối xứng với (3, 13) vì 10 + 13 = 0 mod 23. Hình vẽ bên dưới minh họa tính đối xứng của các điểm thuộc đường cong Elliptic trên trường nguyên tố hữu hạn: 11 Hình 1: Minh họa tính đối xứng trong Z23 Các điểm đối xứng với nhau qua đường y = 11.5 . Riêng điểm (4, 0) xem như là đối xứng với chính nó. 1.2.2 Tính chất của đường cong Elliptic • Nếu hai điểm P (x1, y1) và Q(x2, y2) (với x1 6= x2) nằm trên cùng một đường cong Elliptic (E), thì đường thẳng đi qua hai điểm P và Q sẽ cắt tại một điểm duy nhất R(x3, y3) nằm trên đường cong (E) đó, và R có thể xác định thông qua P và Q. • Tiếp tuyến của đường cong tại một điểm bất kỳ P (x, y) trên đường cong (E) cũng cắt (E) tại một điểm duy nhất trên (E), điểm này cũng có thể xác định thông qua P . 12 Hình 2: Minh họa tính chất của đường cong Elliptic 1.2.3 Các phép toán trên đường cong Elliptic Dựa vào các tính chất của đường cong Elliptic, chúng ta xác định hai phép toán trên đường cong Elliptic là: phép cộng điểm và phép nhân điểm. Sau đây là công thức tính của từng phép toán. 13 Phép cộng điểm • Định nghĩa: Với 2 điểm P (xP , yP ), Q(xQ, yQ) bất kỳ, phép cộng R = P + Q được xác định bằng công thức: xR = α 2 − xP − xQ mod p yR = α(xP − xR)− yP mod p trong đó: α =  yQ − yP xQ − xP mod p nếu P 6= Q 3x2P + a 2yP mod p nếu P = Q Hình 3: Minh họa phép cộng điểm Chú ý rằng các điểm (xR; yR) , (xR;−yR)cùng nằm trên đường cong Elliptic và xét về mặt hình học thì các điểm (xP ; yP ), (xQ; yQ) và (xR; yR) 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: (E(Zp),+) tạo thành nhóm Abelian: – Tính đóng: Nếu P,Q ∈ E(Zp) thì P +Q ∈ E(Zp) 14 – Tính kết hợp: Nếu ∀P,Q,R ∈ E(Zp) thì P + (Q+R) = (P +Q) +R – Tồn tại phần tử trung hòa O: ∀P ∈ E(Zp) 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(Zp) thì luôn tồn tại phần tử −P (x, p− y) ∈ E(Zp) , là điểm đối xứng của P để P + (−P ) = O – Tính chất giao hoán: Nếu P,Q ∈ E(Zp) thì P +Q = Q+ P Phép nhân điểm • Phép nhân một số nguyên r với một điểm P ∈ (E) là điểm R ∈ (E) được xác định bằng r − 1 lần phép cộng điểm: rP = P + P + ....+ P︸ ︷︷ ︸ r Vì vậy, nếu P là một điểm thuộc đường cong Elliptic E thì với mỗi số nguyên dương r luôn dễ dàng xác định được điểm R = rP Hình 4: Minh họa phép nhân đôi điểm R = 2P Từ các tính chất và phép toán của đường cong Elliptic trên trường nguyên tố hữu hạn Zp ta thấy việc mã hóa đường cong Elliptic chính là việc thực hiện phép nhân vô 15 hướng r với một điểm P ∈ E(Zp): Q = rP ∈ E(Zp) với r là số nguyên dương lớn, Q là khóa công khai dùng trong khi tạo đường cong Elipptic. Có nhiều phương pháp để tính nhân vô hướng này, tùy vào từng biểu diễn của r thì mỗi phương pháp lại dùng các phép toán trên điểm khác nhau. Sau đây, ta tìm hiểu các thuật toán và chi phí của các phép toán trên từng thuật toán để tính phép nhân với đại lượng vô hướng. 1.2.4 Chi phí của một số phép toán trên điểm Cho P (x1, y1), Q(x2, y2) ∈ E(Zp). Các phép toán số học cơ bản trên trường nguyên tố hữu hạn Zp được ký hiệu như sau: • Phép toán nghịch đảo, ký hiệu là: I • Phép toán bình phương, ký hiệu là: S • Phép toán nhân, ký hiệu là:M Để tính chi phí của các phép toán trên điểm P và Q chúng ta dựa vào việc đếm số phép toán số học (I, S,M) trên trường nguyên tố hữu hạn của từng thuật toán. • Phép toán trên điểm P +Q, 2P Nếu P 6= Q thì chúng ta có phép toán cộng điểm P +Q. Nếu P = Q thì chúng ta có phép toán nhân đôi điểm 2P . – Phép cộng điểm: P +Q = R(x3, y3), trong đó: x3 = ( α2 − x1 − x2 ) (mod p) y3 = (α (x1 − x3)− y1) (mod p) với α = y2 − y1 x2 − x1 (mod p) = ( (y2 − y1) (x2 − x1)−1 ) (mod p ) – Phép nhân đôi điểm: 2P = R (x3, y3), trong đó: x3 = ( α2 − 2x1 ) (mod p) y3 = (α (x1 − x3)− y1) (mod p) với α = 3x21 + a 2y1 (mod p) = (( 3x21 + a ) (2y1) −1) (mod p) Từ tính chất và phân tích trên dẫn đến thuật toán sau [6]: 16 Thuật toán 1 : Cộng, nhân 2 điểm Input: P (x1, y1), Q(x2, y2) ∈ E(Zp) Output: R(x3, y3) = P +Q 1: if P = O return Q 2: if Q = O return P 3: if P = Q : 4: ∆1 ← ( (3x21 + a)(2y1) −1) (mod p) 1S + 1I + 1M 5: x3 ← ( ∆21 − 2x1 ) (mod p) 1S 6: y3 ← (∆1(x1 − x3)− y1) (mod p) 1M 7: if P = −Q : return O 8: if P 6= Q : 9: ∆1 ← ( (y2 − y1)(x2 − x1)−1 ) (mod p) 1I + 1M 10: x3 ← ( ∆21 − x1 − x2 ) (mod p) 1S 11: y3 ← (∆1(x1 − x3)− y1) (mod p) 1M 12: return (x3, y3) Tổng 2P : 1I + 2S + 2M P +Q : 1I + 1S + 2M • Phép toán trên điểm 2P +Q – Ta có: P (x1, y1),Q(x2, y2) với x1 6= x2 thì tính ∆1 = y2 − y1 x2 − x1 , và P+Q = (x3, y3) với: x3 = ∆ 2 1 − x1 − x2, y3 = ∆1(x1 − x3)− y1 Tính S = 2P +Q = P + (P +Q) = (x4, y4) Ta có: ∆2 = y3 − y1 x3 − x1 = (∆1(x1 − x3)− y1)− y1 x3 − x1 = 2y1 x1 − x3 −∆1 x4 = ∆ 2 2 − x1 − x3 = ∆22 − x1 −∆21 + x1 + x2 = ∆22 −∆21 + x2 = (∆2 −∆1)(∆2 + ∆1) + x2 y4 = (x1 − x4)∆2 − y1 – Biến đổi, từ công thức: x4 = (∆2 −∆1)(∆2 + ∆1) + x2 ta thay:  ∆2 = 2y1 x1 − x3 −∆1 x3 = ∆ 2 1 − x1 − x2 ∆1 = y2 − y1 x2 − x1 17 dẫn đến đặt d = (x2 − x1)2(2x1 + x2)− (y2 − y1)2 Dễ dàng có: d = (x2 − x1)2(2x1 + x2)−∆21(x2 − x1)2 = (x2 − x1)2(2x1 + x2 −∆21) = (x2 − x1)2(2x1 + x2 − x3 − x1 − x2) = (x2 − x1)2(x1 − x3) Định nghĩa: D = d(x2 − x1), I = D−1 , suy ra: 1 x2 − x1 = dD −1 = dI 1 x1 − x3 = (x2 − x1)2 d = (x2 − x1)3 D = (x2 − x1)3I Từ phân tích ở trên ta có được thuật toán sau [6]: Thuật toán 2: Tính 2P + Q Input: P (x1, y1), Q(x2, y2) ∈ E(Zp) Output: S(x4, y4) = 2P +Q 1: if (x1 = x2) then 2: (y1 = y2) then return 3P else return P 3: A ← ((x2 − x1)2) (mod p), B ← ((y2 − y1)2) (mod p) SS 4: d← (A (2x1 + x2)−B) (mod p) M 5: if (d = 0) then return O 6: D ← (d (x2 − x1)) (mod p) ,I ← ( D−1 ) (mod p) MI 7: ∆1 ← (dI (y2 − y1)) (mod p) MM 8: ∆2 ← (2y1A (x2 − x1) I −∆1) (mod p) MMM 9: x4 ← ((∆2 −∆1) (∆2 + ∆1) + x2) (mod p) M 10: y4 ← ((x1 − x4) ∆2 − y1) (mod p) M 11: return (x4, y4) Tổng 1I + 2S + 9M • Phép toán trên điểm 3P – Khi P = Q thì thuật toán trên không cho ta biết làm thế nào để tính 3P , dùng cách biến đổi tương tự như của thuật toán trên ta có phân tích để tính 3P như sau: 18