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