Về một lược đồ chữ ký số kiểu ECDSA

Công nghệ thông tin & Cơ sở toán học cho tin học N. H. Hùng, T. Q. Phong, N. Q. Toàn, “Về một lược đồ chữ ký số kiểu ECDSA.” 82 VỀ MỘT LƯỢC ĐỒ CHỮ KÝ SỐ KIỂU ECDSA Nguyễn Hữu Hùng1*, Triệu Quang Phong2, Nguyễn Quốc Toàn2 Tóm tắt: Bài báo này nghiên cứu cơ sở lý thuyết xây dựng lược đồ chữ ký số dựa trên bài toán logarith rời rạc. Phân tích một số biến thể của lược đồ chữ ký số ECDSA, phương pháp chứng minh an toàn cho ECDSA. Từ đó đề xuất một lược đồ chữ ký số kiểu ElGamal nghịch và đưa ra chứng minh an toàn cùng một số nhận xét đánh giá cho lược đồ đã đề xuất. Từ khóa: Hệ mật Ellipic (ECC), Bài toán logarith rời rạc (DLP), Lược đồ chữ ký số ECDSA. 1. ĐẶT VẤN ĐỀ Dựa theo tài liệu [1], bài báo đưa ra đề xuất một lược đồ chữ ký số mà là biến thể của thuật toán chữ ký số ECDSA. Hơn nữa, cũng theo [1], lược đồ này cũng có thể được chứng minh an toàn trong mô hình nhóm tổng quát, giống như ECDSA được chứng minh an toàn trong mô hình nhóm tổng quát bởi Brown trong [2]. Liên quan đến việc xem xét về độ an toàn, bài báo còn áp dụng phương pháp chứng minh trong [4] để chứng minh lược đồ đã đề xuất là an toàn trước tấn công không sử dụng thông điệp trong mô hình bộ tiên tri ngẫu nhiên. Ngoài ra, tương tự lược đồ ECDSA-III trong [4], bài báo chỉ ra rằng lược đồ đề xuất là khắc phục được lỗi “chữ ký kép” của ECDSA, một lỗi đã được chỉ ra trong [5]. 2. CƠ SỞ LÝ THUYẾT 2.1. Mô hình chữ ký số dựa trên bài toán DLP Một lược đồ chữ ký tổng quát dựa trên bài toán logarith rời rạc được xây dựng dựa trên các thành phần sau [1]:  Một nhóm rời rạc cấp mà ở đó việc tính logarit rời rạc là khó.  Tập các khóa bí mật có thể tồn tại là . Nếu khóa bí mật của người ký là , khóa công khai tương ứng là phần tử . Phụ thuộc vào kiểu chữ ký số, ta có thể cần hoặc . Tất cả các nhóm sẽ được coi là các nhóm nhân, ngay cả trong trường hợp của các đường cong elliptic.  Một phép chiếu: là một ánh xạ .  Một hàm băm, là một hàm mà ở đó là tập tất cả các thông điệp có thể tồn tại.  Một kiểu chữ ký số mà xác định các công thức tường minh cho quá trình thực hiện chữ ký và quá trình xác minh. Kiểu chữ ký số định nghĩa các hàm sau đây: Hàm và ; hàm , trong đó với hoặc và hoặc . Lược đồ chữ ký số thực hiện như sau:  Quá trình ký: Để ký thông điệp người ta lấy một giá trị ngẫu nhiên thuộc , tính , , đến khi và . Thông điệp được ký là .  Quá trình xác minh chữ ký: Việc xác minh bằng Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 83 việc tính toán , và kiểm tra nếu và nếu . 2.2. Hàm băm của một lược đồ chữ ký số Đối với lược đồ chữ ký số, hàm băm phải là dễ tính toán, kháng va chạm, có đầu ra ngẫu nhiên đều với . Khác với hàm băm thông thường, hàm băm của một lược đồ chữ ký số còn có một số tính chất sau [1]. Định nghĩa 2.1 (Hàm băm loại I của lược đồ chữ ký số). Hàm băm của một lược đồ chữ ký số được gọi là Loại I nếu . Một ví dụ đối với hàm băm loại I của lược đồ chữ ký số ECDSA là hàm băm SHA-256. Ta luôn có . Định nghĩa 2.2 (Hàm băm loại II của lược đồ chữ ký số). Hàm băm của một lược đồ chữ ký số được gọi là Loại II nếu nó không phải là hàm băm loại I. Định nghĩa 2.3 (Kháng va chạm cộng). Hàm băm của một lược đồ chữ ký với và được gọi là kháng va chạm cộng nếu cho trước ngẫu nhiên thì khó để tìm được sao cho . Định nghĩa 2.4 (Kháng va chạm chia). Hàm băm của một lược đồ chữ ký với và được gọi là kháng va chạm chia nếu cho trước ngẫu nhiên thì khó để tìm được sao cho . Định nghĩa 2.5 (Hàm băm như một bộ tiên tri ngẫu nhiên). Hàm băm H của một lược đồ chữ ký được coi như một bộ tiên tri ngẫu nhiên nếu hiểu biết về cặp đầu vào - đầu ra không làm hạn chế đáng kể không gian ảnh có thể có cho một đầu vào khác. 2.3. Phép chiếu của lược đồ chữ ký số Phép chiếu phải là dễ tính toán bởi người ký, và người xác minh sẽ có khả năng để kiểm tra với và . Nếu các phần tử của là không phân biệt được với các phần tử của một tập lớn hơn, thì được định nghĩa trên toàn bộ tập lớn hơn đó. Phép chiếu có thể có một số tính chất sau đây. Định nghĩa 2.6 ( hầu đều, [6]). Ánh xạ được gọi là hầu đều nếu : , với là số phần tử của . Khi là đại lượng không đáng kể theo thì được gọi là hầu đều. Nói cách khác, hàm là hầu đều nếu xác suất phân bố của từng phần tử thuộc tập đầu ra là lệch không đáng kể so với phân bố đều. Định nghĩa 2.7 ( hầu khả nghịch, [1]). Ánh xạ là hầu khả nghịch nếu tồn tại một thuật toán hiệu quả để tính hàm ngược sao cho: - - Ít nhất một tỷ lệ của các tập là khác rỗng. - Các phần tử được lấy ngẫu nhiên từ các tập là không phân biệt được với các phân tử được lấy ngẫu nhiên từ . Trong [2], Brown đã chứng minh rằng phép chiếu của lược đồ chữ ký số ECDSA là hầu khả nghịch. Công nghệ thông tin & Cơ sở toán học cho tin học N. H. Hùng, T. Q. Phong, N. Q. Toàn, “Về một lược đồ chữ ký số kiểu ECDSA.” 84 Định nghĩa 2.8 ( kháng va chạm, [1]). Phép chiếu là - kháng va chạm nếu với thì việc tìm sao cho là khó. Định nghĩa 2.9 (phép chiếu như là một bộ tiên tri ngẫu nhiên, [1]). Phép chiếu là phù hợp như một bộ tiên tri ngẫu nhiên nếu hiểu biết về các cặp đầu vào-đầu ra không hạn chế đáng kể không gian ảnh có thể có cho một đầu vào khác. Một hàm hầu khả nghịch có thể là phù hợp như một bộ tiên tri ngẫu nhiên. 2.4. Một số tính chất và các kiểu chữ ký số Một kiểu chữ ký số được mô tả bởi các tập , và , với hai hàm , và một tập . Tuy nhiên, có thể sử dụng bổ sung thêm một số hàm khác như sau. Các hàm bổ sung: Gọi là tập các đầu ra có thể có đối với và là tập các đầu ra có thể có đối với . Năm hàm bổ sung có thể được định nghĩa như sau:      Đối với mỗi kiểu chữ ký số, luôn tồn tại một thuật toán hiệu quả để tính toán kết quả của các hàm . Các tính chất cơ bản của một kiểu lược đồ chữ ký [1]: Những tính chất này là các tính chất bắt buộc cho tất cả các lược đồ chữ ký dựa trên bài toán logarit rời rạc. Tính chất (m1). Với tất cả các bộ , giá trị thỏa mãn điều kiện: nếu và thì . Tính chất (m2). Với tất cả và : . Tính chất (m1) chỉ ra rằng tất cả các chữ ký được sinh bằng thuật toán ký là hợp lệ. Tính chất (m2) dẫn tới rằng số các số ngẫu nhiên (được kỳ vọng) cần cho thuật toán sinh chữ ký là nhỏ hơn . Một số tính chất khác: Tính chất (o1). Với tất cả : Phương trình là đúng. Tính chất (o2). Với tất cả : Phương trình là đúng. Tính chất (o3). Hàm là nghịch đảo của . Các tính chất bổ sung cho độ an toàn với hàm lý tưởng [1]: Tính chất (p1). Với cố định và đều sao cho , giá trị là đều trong . Tính chất này cùng với giả thiết rằng hàm là hầu đều và một chiều dẫn tới rằng tập các cặp hợp lệ có thể có cho một thông điệp là phân phối đều. Tính chất (p2). Với và cố định và giá trị ngẫu nhiên đều và Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 85 , thì là ngẫu nhiên đều trong . Lỗi có thể xảy ra nếu và nếu . Dễ dàng thấy rằng xác xuất của lỗi này là không đáng kể. Tính chất (p3). Cho trước và ngẫu nhiên, việc tìm và các thông điệp và nào đó sao cho và là khó. Các tính chất bổ sung cho độ an toàn với hàm lý tưởng [1]: Tính chất (h1). Nếu và thì và . Tính chất (h2). . Các tính chất cho độ an toàn với nhóm lý tưởng [1]: Tính chất (g1). Với tất cả các bộ phương trình đúng. Tính chất (g2). Với tất cả các bộ , nếu thì . Các tính chất (m1), (m2), (o1), (o2), (o3), (p1), (p2), (h1) và (h2) đúng đối với hai kiểu chữ ký số điển hình sau đây. Kiểu chữ ký số ElGamal: Kết quả sau đây được phát biểu trong [1]: Lấy , và . Bởi vì , tính chất (p2) có thể sai với xác suất không đáng kể. Tính chất (p3) là tương đương với sự kháng va chạm chia của hàm băm . Các tính chất (g1) và (g2) đúng với hạn chế và ; (m2) và (h2) đúng với và . Với hàm tạo chữ ký số    , , , /h r v k h v r k    , ta có:            1 1 1 , , / ; , , / ; , , , , , ; , , ; , , h h s r h r s h s h r s r s s r v k k s v r r r r r r h                                (2.1) Kết quả 2.1. Với phương trình tạo chữ ký số kiểu ElGamal    1, , ,h r v k k h v r    ta thu được các hàm như trong công thức (2.1). Chứng minh. Thật vậy, chúng ta sẽ chỉ ra quy tắc cho việc hình thành các hàm từ phương trình tạo chữ ký . Chú ý rằng và là hai hàm để tính ; và dùng để tính giá trị ; và cuối cùng đưa ra giá trị . Do đó, từ , chúng ta có: Tiếp theo chú ý rằng, trong thuật toán xác minh cho lược đồ chữ ký tổng quát, chúng ta cần để hay . Nghĩa là chúng ta cần tính và sao cho: . Mặt khác do việc tính là khó nên cần đảm bảo và vì ngược lại thì sẽ bị lộ một cách dễ dàng thông qua một cặp thông điệp-chữ ký hợp lệ bất kỳ và các giá trị thu được từ thuật toán xác minh. Do đó, và . Hơn nữa, vì là hàm tính (khác với ), Công nghệ thông tin & Cơ sở toán học cho tin học N. H. Hùng, T. Q. Phong, N. Q. Toàn, “Về một lược đồ chữ ký số kiểu ECDSA.” 86 và nên . Tương tự, vì và là các hàm tính và nên chúng ta thu được và .■ Các hàm trong kiểu chữ ký số ElGamal nghịch dưới đây đều được suy ra từ phương trình ký bằng cách tương tự như trên. Kiểu chữ ký số ElGamal nghịch: Tương tự như kiểu chữ ký số ElGamal ở trên, gọi , và . Bởi vì , tính chất (p2) có thể sai với xác suất không đáng kể. Tính chất (p3) là tương đương với sự kháng va chạm chia của . Tính chất (g1) và (g2) đúng với hạn chế là và . Tính chất (m2) và (h2) đúng với và . Các hàm được xác định như sau :               1 1 1 , , ; , , ; , , , / ( ) , , , / ; , , , , ; , , h h s r h r s h s h r s r s h r v k k h v r s r v k k s v r r r r r r h                                          (2.2) 2.5. Một số biến thể của lược đồ chữ ký số ECDSA a) Lược đồ ECDSA-II ECDSA-II [4] là một biến thể của ECDSA mà có thể được chứng minh an toàn trong mô hình bộ tiên tri ngẫu nhiên. Điểm khác biệt duy nhất của lược đồ này so với ECDSA là việc sử dụng hàm băm loại II thay vì sử dụng hàm băm loại I như ECDSA (tính . Lược đồ này đã được chứng minh an toàn trong mô hình bộ tiên tri ngẫu nhiên thông qua định lý sau đây. Định lý 2.1 (Định lý 2, [4]). Giả sử tồn tại một tấn công lên lược đồ ECDSA- II với xác suất thành công là sau truy vấn tới bộ tiên tri ngẫu nhiên , thì người ta có thể giải bài toán logarit rời rạc trên nhóm các điểm đường cong elliptic bằng cách sử dụng nhiều nhất lần lặp lại tấn công với xác suất lớn hơn . b) Lược đồ ECDSA-III ECDSA-III [4] là một biến thể khá gần với ECDSA-II. Điểm khác biệt duy nhất của lược đồ này so với ECDSA-II là việc sử dụng phép chiếu ECaddq thay vì phép chiếu ECxq như ECDSA và ECDSA-II (tính , và ). Lược đồ này cũng được chứng minh an toàn trong mô hình bộ tiên tri ngẫu nhiên thông qua định lý dưới đây. Định lý 2.2 (Định lý 3, [4]).Giả sử tồn tại một tấn công lên ECDSA-III với xác suất thành công sau truy vấn tới bộ tiên tri ngẫu nhiên , thì người ta có thể giải bài toán logarit rời rạc trên nhóm các điểm đường cong elliptic bằng cách sử dụng nhiều nhất lần lặp lại tấn công với xác suất lớn hơn . c) Các biến thể của ECDSA sử dụng kiểu chữ ký ElGamal nghịch Biến thể của ECDSA sử dụng kiểu chữ ký ElGamal nghịch có thể được tìm thấy trong [7]. Ở đây, chúng ta sẽ tổng quát hóa về các biến thể của ECDSA (cho cả Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 87 ECDSA-II, ECDSA-III, ) sử dụng kiểu chữ ký ElGmal nghịch. Kiểu ElGamal nghịch là kiểu chữ ký số mà tính thành phần thứ hai [3]. Định nghĩa 2.10 (Kiểu lược đồ I và II). Quy ước rằng lược đồ ECDSA (có thể là ECDSA gốc, ECDSA-II, ECDSA-III, ...) mà sử dụng kiểu chữ ký ElGamal là kiểu lược đồ I, thì biến thể tương ứng của nó (sử dụng kiểu chữ ký ElGamal nghịch) sẽ được gọi là kiểu lược đồ II. So sánh kiểu lược đồ I và kiểu lược đồ II: Về hiệu suất tính toán. Kiểu lược đồ I sử dụng hai phép tính nghịch đảo modulo , một cho quá trình ký và một cho quá trình xác minh. Trong khi đó, kiểu lược đồ II chỉ sử dụng một phép tính nghịch đảo modulo (cho quá trình ký). Về độ an toàn. Độ an toàn của kiểu lược đồ I và kiểu lược đồ II là tương đương. Điều này sẽ được chứng minh qua định lý sau đây. Định lý 2.3. Kiểu lược đồ I và kiểu lược đồ II có độ an toàn tương đương. Chứng minh.Trước hết chúng ta nhận xét rằng nếu và là cặp chữ ký- thông điệp hợp lệ của kiểu lược đồ I, thì và là cặp chữ ký-thông điệp hợp lệ của kiểu lược đồ II, và ngược lại. Như vậy, nếu gọi kẻ tấn công I và kẻ tấn công II lần lượt là hai thuật toán giả mạo chữ ký đối với kiểu lược đồ I và kiểu lược đồ II, thì thời gian tính của kẻ tấn công II bằng thời gian tính của kẻ tấn công I cộng thêm thời gian tính của một phép nghịch đảo modulo đối với tấn công NMA và cộng thêm thời gian tính của một đa thức phép tính nghịch đảo modulo đối với tấn công CMA. Do thời gian tính của phép nghịch đảo modulo chỉ là một đa thức theo nên ta có thời gian quy dẫn tương đương giữa kẻ tấn công II với kẻ tấn công I và ngược lại. Điều này có nghĩa là độ an toàn của hai kiểu lược đồ này là tương đương.■ 3. ĐỀ XUẤT LƯỢC ĐỒ CHỮ KÝ SỐ DỰA TRÊN ECDSA Lược đồ đề xuất ở đây được định nghĩa trên một nhóm con cấp nguyên tố của nhóm các điểm đường cong elliptic với kiểu chữ ký số ElGamal nghịch sử dụng phép chiếu ECaddq và hàm băm loại II. Chúng tôi đặt tên lược đồ này là ECDSA-IV. Thuật toán ký của ECDSA-IV (1). Chọn ngẫu nhiên một số nguyên thuộc khoảng . (2). Tính . (3). Tính , nếu , quay về bước 1. (4). Tính , trong đó là hàm băm SHA-256. (5). Tính ; nếu , thì quay về bước 1. (6). Chữ ký của người gửi đối với thông điệp là cặp số nguyên Thuật toán xác minh của ECDSA-IV (1). Xác minh rằng giá trị và thuộc khoảng . (2). Tính , trong đó là hàm băm SHA-256. (3). Tính . (4). Tính . (5). Tính . (6). Tính (7). Chữ ký đối với thông điệp được xác minh là hợp lệ chỉ nếu . Công nghệ thông tin & Cơ sở toán học cho tin học N. H. Hùng, T. Q. Phong, N. Q. Toàn, “Về một lược đồ chữ ký số kiểu ECDSA.” 88 3.1. Đánh giá về độ an toàn của lược đồ ECDSA-IV được đề xuất a) Độ an toàn của lược đồ đề xuất trước tấn công lựa chọn thông điệp thích nghi CMA trong mô hình nhóm tổng quát GGM Mô hình nhóm tổng quát đã được giới thiệu bởi Shoup và được mở rộng bởi Brown để chứng minh độ an toàn của ECDSA [2]. Kết quả dưới đây được phát biểu trong [1] là tổng quát cho kết quả trong [2]: Khẳng định 2.1 [1]. Một lược đồ chữ ký dựa trên bài toán logarit rời rạc là “không có giả mạo tồn tại dưới các tấn công lựa chọn thông điệp thích nghi trong mô hình nhóm tổng quát” nếu là đều và kháng va chạm, là hầu đều và hầu khả nghịch, và thuộc một kiểu chữ ký số có tính chất (g1) và (g2). Phép suy dẫn độ an toàn là chặt. Khẳng định 2.1 chỉ ra điều kiện để một lược đồ có thể được chứng minh an toàn trước tấn công lựa chọn thông điệp thích nghi trong mô hình nhóm tổng quát. Trong phần này, ta sẽ kiểm tra lược đồ đề xuất ECDSA-IV cũng thỏa mãn đủ các điều kiện được nêu ra theo kết quả này, và do đó lược đồ này cũng là an toàn trước tấn công lựa chọn thông điệp thích nghi trong mô hình nhóm tổng quát. Ta phát biểu và chứng minh mệnh đề sau: Mệnh đề 2.1: Lược đồ chữ ký số đề xuất ECDSA-IV là an toàn trước tấn công lựa chọn thông điệp thích nghi CMA trong mô hình nhóm tổng quát GGM. Chứng minh: Thật vậy, đầu tiên chúng ta sẽ chỉ ra phép chiếu ECaddq , với là điểm thuộc nhóm con cấp của , được sử dụng trong lược đồ ECDSA-IV là hầu khả nghịch. Chúng ta sẽ chỉ ra thuật toán tìm ảnh ngược của như sau, kèm theo lưu ý rằng trong thực tế với (theo [2]). Với , chọn một số nguyên ngẫu nhiên sao cho (1) và (2) biểu diễn bit của cũng là biểu diễn bit của một phần tử trong trường . Theo Định lý Hasse, số điểm của là với . Mặt khác với bất kỳ, đường thẳng cắt tại nhiều nhiều nhất tại 3 điểm. Do đó nếu lấy ngẫu nhiên, thì với xác suất ít nhất là , chúng ta có đường thẳng sẽ cắt đường cong . Như vậy, với cho trước, thay vào phương trình đường cong và sau đó giải phương trình bậc ba để tìm tọa độ giao điểm của và đường cong. Chọn ngẫu nhiên trong số các giao điểm tìm được (để đảm bảo yêu cầu thứ 3 của tính hầu khả nghịch). Hơn nữa, theo đề xuất với , nên ít nhất số điểm nhận được theo cách này thuộc nhóm . Do đó thuật toán này hiệu quả và thành công với xác suất . Vì vậy là hầu khả nghịch. Tiếp theo, dễ thấy phép chiếu này cũng là hầu đều. Hàm băm sử dụng cho lược đồ này được xem là an toàn (giống như trường hợp của ECDSA). Ngoài ra, kiểu chữ ký số được sử dụng trong lược đồ này là ElGamal nghịch. Điều cuối cùng ta cần chỉ ra là ECDSA-IV thỏa mãn tính chất (g1) và (g2). Thật vậy, với chú ý đây là lược đồ kiểu ElGamal nghịch nên theo công thức (2.2) ta có:  Thỏa mãn tính chất (g1): Với tất cả , ta có:  Thỏa mãn tính chất (g2): Với tất cả , nếu Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 45, 10 - 2016 89 thì do nên suy ra .■ Như vậy, ta đã chỉ ra rằng lược đồ đề xuất ECDSA-IV thỏa mãn tất cả các yêu cầu trong Khẳng định 2.1. Do đó, chúng ta thu được kết quả rằng: Lược đồ chữ ký số đề xuất ECDSA-IV là an toàn chống tấn công CMA trong mô hình nhóm tổng quát. b) Độ an toàn của lược đồ đề xuất trước tấn công không sử dụng thông điệp NMA trong mô hình bộ tiên tri ngẫu nhiên ROM Việc chứng minh độ an toàn của lược đồ đề xuất là tương tự với lược đồ ECDSA-III [4] bằng cách sử dụng Bổ đề forking cải tiến được phát biểu trong [4]. Trong [4], bổ đề này sử dụng để chứng minh cho các lược đồ chữ ký kiểu ElGamal tin cậy (Trusted ElGamal Type Signature Scheme- TEGTSS). Tuy nhiên, trong [4] các tác giả đã áp dụng bổ đề này cho phiên bản trên đường cong elliptic của TEGTSS, và được gọi là ECTEGTSS. Chúng ta đưa ra khẳng định sau. Khẳng định 2.2. Lược đồ chữ ký số đề xuất ECDSA-IV là một kiểu ECTEGTSS và tương đương với kiểu TEGTSS-II. Chứng minh: Do giới hạn số trang nên phần chứng minh của Khẳng định này sẽ được đăng ở bài báo tiếp theo.■ Mặt khác theo [4] phép chiếu là 4-kháng va chạm nên ta cũng thu được một kết quả tương tự như cho ECDSA-III đối với lược đồ đề xuất như sau. Mệnh đề 2.2. Giả sử tồn tại kẻ tấn công lên lược đồ ECDSA-IV với xác suất thành công là sử dụng truy vấn tới bộ tiên tri ngẫu nhiên , thì người ta có thể giải bài toán logarit rời rạc trong nhóm các điểm của đường cong elliptic bằng cách sử dụng ít hơn lần lặp của với xác suất lớn hơn . Chứng minh: Do giới hạn số trang nên phần chứng minh của Khẳng định này sẽ được đăng ở bài báo tiếp theo.■ Nhận xét: Một trong những điểm yếu của ECDSA không được xem xét trong [2], mà được chỉ ra trong [5] là lỗi “chữ ký kép”. Nguyên nhân là do phép chiếu được sử dụng trong ECDSA biến một điểm trên đường cong thành hoành độ của nó, cho nên . Vì vậy, trong ECDSA tất cả các giá trị (được sinh ra trong thuật toán ký) có thể là các thành phần của một chữ ký kép tầm thường. Dễ dàng thấy rằng lược đồ ECDSA-IV khắc phục được lỗi chữ ký kép vì phép chiếu của nó không có tính chất . 4. KẾT LUẬN Bài báo này đã nghiên cứu, đề xuất một lược đồ chữ ký số dựa vào ECDSA theo kiểu ElGamal nghịch. Đưa ra khẳng định và chứng minh về độ an toàn tương đương với ECDSA. Lược đồ còn được chứng minh là an toàn trong mô hình bộ Công nghệ thông tin & Cơ sở toán học cho tin học N. H. Hùng, T. Q. Phong, N. Q. Toàn, “Về một lược đồ chữ ký số kiểu ECDSA.” 90 tiên tri ngẫu nhiên, hơn nữa quá trình kiểm tra chữ ký không phải thực hiện phép tính nghịch đảo như ECDSA. Trong bài báo tiếp theo, chúng tôi sẽ đưa ra chứng minh chi tiết cho Khẳng định 2.2 và Mệnh đề 2.2, đồng thời phân tích kỹ hơn về lỗi chữ ký số kép của lược đồ ECDSA-IV và một số kiểu lược đồ chữ ký số khác. TÀI LIỆU THAM KHẢO [1]. L. Granboulan, “PECDSA. How to build a DL-based digital signature scheme with the best proven security”, 2002. [2]. D. R. L. Brown, “Generic groups, collision resistanceand ECDSA”, 2002. [3]. G. Sarath et al, “A Survey on Elliptic Curve Digital Signature Algorithm and Its Variants”. CSCP .pp.121-136, 2014. [4]. J. Malone-Lee and N. P. Smart, “Modifications of ECDSA”, SAC’02. [5]. J. Stern, D. Pointcheval, J. M. Lee, N. P. Smart, “Flaws in Applying Proof Methodologies to Signature Schemes”, CRYPTO, 2002. [6]. M. Bellare, O. Goldreich, and E. Petrank, “Uniform generation of NP- witnesses using an NP-oracle”, Infor. and Computation, 163(2), 1998, 510– 526. [7]. Hu Junru, “The Improved Elliptic Curve Digital Signature Algorithm”, 2011 Int. Conf. on Electronic & Mechanical Engineering and Inf. Technology, 2011. ABSTRACT ON THE DIGITAL SIGNATURE SCHEME BASED ON ECDSA This paper studies the basis theory to construct a digital signature scheme based on discrete logarithmic problem. Analysis some variations of ECDSA digital signature scheme, security proof method for ECDSA. From which, proposed a digital signature scheme based on ECDSA, analogue inverse ElGamal type.This scheme also was security proof in Random Oracle Model. Keywords: Elliptic Cryptographic System (ECC), Discrete Logarithm Problem (DLP), Elliptic Curve Digital Signature Algorithm (ECDSA). Nhận bài ngày 01 tháng 9 năm 2016 Hoàn thiện ngày 22 tháng 9 năm 2016 Chấp nhận đăng ngày 26 tháng 10 năm 2016 Địa chỉ: 1Cục Chứng thực số và Bảo mật thông tin, Ban Cơ yếu Chính phủ; 2Viện KH-CN mật mã, Ban Cơ yếu Chính phủ. *Email: nhhung_CYCP@yahoo.com