Xây dựng lược đồ chữ ký số an toàn từ các lược đồ định danh

 vấn băm duy 
chữ ký nhận đƣợc từ hai Phép xây dựng có thể nhất này là truy vấn băm đặc biệt. Ký hiệu là 
chuyển đổi lẫn nhau nên suy ra lƣợc đồ chữ ký biên trên đa thức cho số lƣợng các truy vấn băm 
số nhận đƣợc từ Phép xây dựng 2 cũng đạt đƣợc thực hiện bởi . 
đƣợc tính chất an toàn nhƣ lƣợc đồ chữ ký số Tiếp theo ta mô tả kẻ tấn công PPT lên 
nhận đƣợc từ Phép xây dựng 1. lƣợc đồ . Kẻ tấn công đƣợc cho đầu vào là 
B. Điều kiện cần và đủ cho độ an toàn của lược khóa công khai , đƣợc phép truy cập đến bộ 
đồ chữ ký số xây dựng từ các lược đồ định danh tiên tri , và có tƣơng tác với ngƣời 
 Ký hiệu ( ) là một lƣợc đồ định xác minh . Hoạt động đầu tiên thực hiện là 
danh và là lƣợc đồ chữ ký số nhận đƣợc qua đoán một chỉ số ngẫu nhiên * +. Chỉ 
việc áp dụng Phép biến đổi Fiat-Shamir lên . số này đóng vai trò là phỏng đoán cho chỉ số 
Một câu hỏi tự nhiên là, để lƣợc đồ chữ ký số của truy vấn băm đặc biệt (nếu có) sẽ đƣợc thực 
an toàn dƣới các tấn công sử dụng thông điệp hiện bởi . Sau đó, kẻ tấn công chạy 
đƣợc lựa chọn thích nghi thì lƣợc đồ định danh ( ), và trả lời các truy vấn của nhƣ sau: 
 phải thỏa mãn các điều kiện gì. Định lý dƣới Truy vấn băm ( ): Có hai trƣờng hợp: 
đây sẽ trả lời cho câu hỏi đó. Nếu đây là truy vấn thứ đến , thì sẽ 
 Định lý 1 ([3, Định lý 8.1]). Cho đƣa ra phỏng đoán truy vấn này chính là truy 
( ) là một lược đồ định danh mà an vấn băm đặc biệt. gửi tới ngƣời xác 
toàn kháng lại các tấn công bị động. Khi đó, 
 minh trung thực mà nó đƣợc phép tƣơng 
nếu hàm băm được mô hình hóa như một bộ 
tiên tri ngẫu nhiên thì lược đồ chữ ký số tác, và nhận giá trị trả về là một thách thức . 
nhận được từ việc áp dụng phép biến đổi Fiat- Sau đó gửi cho nhƣ là câu phúc đáp 
Shamir lên là không thể bị giả mạo tồn tại ứng với truy vấn băm này. Ta gọi truy vấn 
dưới các tấn công sử dụng thông điệp được lựa băm trong trƣờng hợp này là truy vấn đã 
chọn thích nghi. phỏng đoán. 
 Chứng minh. Ý tƣởng chứng minh là, ta sẽ Nếu đây không phải là truy vấn thứ thì 
sử dụng một kẻ tấn công của lƣợc đồ chữ ký chọn ngẫu nhiên một giá trị và gửi 
số để xây dựng một kẻ tấn công tấn công 
 về để phúc đáp truy vấn này. 
vào lƣợc đồ định danh. Kẻ tấn công đƣợc cho 
khóa công khai cũng nhƣ đƣợc phép truy cập Rõ ràng, trong cả hai trƣờng hợp giá trị trả về 
đến bộ tiên tri , và tƣơng tác với một mà nhận đƣợc đều có phân bố đều trong . 
ngƣời xác minh trung thực . Chú ý rằng, nhƣ Truy vấn ký ( ): truy vấn tới bộ 
những lập luận đã trình bày phía dƣới Định tiên tri và nhận đƣợc bản ghi 
nghĩa 2, để không mất tính tổng quát, ta có thể ( ). Nếu giá trị băm ( ) đã đƣợc xác 
giả thiết cho phép đƣợc truy cập đến bộ tiên định trƣớc đó thì bỏ dở. Ngƣợc lại, gửi trả 
tri ngay cả trong quá trình tƣơng tác về chữ ký ( ) cho (cùng với giá trị băm 
với . ( ) ). 
 Bây giờ, giả sử là một kẻ tấn công PPT Nếu đƣa ra một chữ ký hợp lệ ( ̂ ̂) trên 
đối với lƣợc đồ . Ta sẽ đƣa ra một vài giả thông điệp ̂, thì kiểm tra xem truy vấn đã 
thiết đơn giản mà không làm mất đi tính tổng phỏng đoán ( ) có bằng truy vấn đặc biệt 
quát. Trƣớc tiên, ta giả thiết chỉ thực hiện ( ̂ ̂) hay không. Nếu chúng không bằng 
truy vấn đối với giá trị băm đã cho chỉ duy nhất nhau, thì kết luận bỏ dở. Ngƣợc lại, gửi ̂ 
một lần. Để đơn giản, khi đƣợc cho một chữ 
 tới ngƣời xác minh . 
ký ( ) trên thông điệp thì đồng thời 
cũng đƣợc cho giá trị ( ), do đó ta giả thiết Chú ý rằng, với điều kiện không bỏ dở 
 không bao giờ truy vấn ( ) sau khi đã trong khi thực thi và phỏng đoán của nó về truy 
 Số 2.CS (08) 2018 29 
Journal of Science and Technology on Information Security 
vấn đặc biệt là đúng, thì thành công trong Chứng minh. Ta sẽ sử dụng phƣơng pháp 
việc giả mạo ngƣời chứng minh trung thực. Lý phản chứng để chỉ ra điều cần chứng minh. Giả 
do là bởi vì: sử ngƣợc lại rằng lƣợc đồ chữ ký số là không 
 Khi truy vấn đã phỏng đoán bằng với truy thể bị giả mạo tồn tại dƣới tấn công sử dụng 
 thông điệp đƣợc lựa chọn thích nghi, nhƣng 
 vấn đặc biệt, tức là đã gửi ̂ tới ngƣời xác 
 lƣợc đồ định danh không an toàn dƣới các tấn 
 minh, và nhận về thách thức ( ̂ ̂). công bị động. Khi đó, tồn tại một kẻ tấn công 
 ( ̂ ̂) là một chữ ký hợp lệ trên ̂ nếu mà dựa vào khóa công khai có thể mạo danh 
 ( ̂ ̂) chính xác là một bản ghi chấp nhận. ngƣời chứng minh với xác suất đáng kể. Tất 
 nhiên ở đây đƣợc phép truy vấn một số lƣợng 
 bỏ dở nếu, trong quá trình trả lời một truy hữu hạn (đa thức) đến bộ tiên tri để nhận 
vấn ký cho thông điệp , nhận đƣợc bản ghi đƣợc các bản ghi chấp nhận. Mục tiêu của ta là 
( ) mà với nó truy vấn băm ( ) đã xây dựng một kẻ tấn công đƣợc phép truy 
đƣợc thực hiện bởi . Vì lƣợc đồ định danh cập đến bộ tiên tri ký mà sử dụng nhƣ 
đƣợc giả thiết là chính tắc (và vì thế thông điệp một thủ tục con để giả mạo thành công chữ ký 
đầu tiên là không suy biến) nên xác suất để xảy của lƣợc đồ với xác suất đáng kể. 
ra trƣờng hợp này là không đáng kể. 
 Kẻ tấn công đƣợc xây dựng một cách đơn 
 Giả sử không bỏ dở trong quá trình thực giản nhƣ sau: Để đƣa ra một chữ ký giả mạo 
thi, thì nó là một sự giả lập hoàn hảo cho . trên thông điệp , trƣớc tiên chạy để sinh 
Hơn nữa, phỏng đoán của về truy vấn đặc ra một thông điệp . tính giá trị ( ) 
biệt là đúng với xác suất (và biến cố này và gửi trả về nhƣ là giá trị thách thức của . 
độc lập với biến cố đƣa ra một chữ ký giả Do đƣợc mô hình hóa nhƣ một bộ tiên tri 
mạo hợp lệ). Nếu thành công trong việc đƣa ngẫu nhiên nên giá trị thách thức mà nhận 
ra một chữ ký hợp lệ với xác suất thì thành đƣợc cũng đƣợc phân bố đều trong nhƣ mọi 
công trong việc giả mạo với xác suất giá trị thách thức khác do ngƣời xác minh chọn 
( ( )) với ( ) là một hàm nào đó mà ngẫu nhiên đều từ . Có thể lặp lại hoạt động 
không đáng kể theo . Do lƣợc đồ định danh của một số hữu hạn (đa thức) lần cho đến 
là an toàn bị động, nên suy ra ta nhận đƣợc khi đƣa ra một câu phúc đáp tƣơng ứng với 
khẳng định cần chứng minh. thông điệp . Theo giả thiết thì ( ) sẽ là 
 Định lý 1 đã cung cấp cho ta một ―điều kiện bản ghi chấp nhận vƣợt qua đƣợc bƣớc kiểm tra 
đủ‖ để nhận đƣợc một lƣợc đồ chữ ký số không của ngƣời xác minh với xác suất đáng kể. 
thể bị giả mạo tồn tại dƣới tấn công sử dụng Cuối cùng, đƣa ra ( ) nhƣ là chữ ký giả 
thông điệp đƣợc lựa chọn thích nghi từ việc áp mạo trên thông điệp . Rõ ràng, ngoại trừ với 
dụng phép biến đổi Fiat-Shamir lên các lƣợc đồ một xác suất nhỏ không đáng kể nhƣ sẽ chỉ ra 
định danh, đó là ―lƣợc đồ định danh phải an dƣới đây, ( ) là một chữ ký hợp lệ trên thông 
toàn kháng lại các tấn công bị động và hàm băm điệp nhận đƣợc từ bản ghi chấp nhận 
 phải đƣợc mô hình hóa nhƣ một bộ tiên tri ( ). Nhƣ vậy đã tạo ra đƣợc chữ ký 
ngẫu nhiên‖. hợp lệ ( ) trên thông điệp với xác suất 
 Tuy nhiên, không chỉ có vậy, với mệnh đề đáng kể mà không cần biết khóa bí mật. 
dƣới đây, chúng tôi chỉ ra ―điều kiện đủ‖ đƣa ra Cần lƣu ý rằng, trong quá trình tấn công để 
ở Định lý 1 cũng chính là ―điều kiện cần‖. mạo danh , trƣớc khi đƣa ra phúc đáp tƣơng 
 Mệnh đề 1. Cho ( ) là một lược ứng với thách thức và thông điệp , kẻ tấn 
đồ định danh. Giả sử hàm băm được mô hình công có thể thực hiện một số lƣợng hữu hạn 
hóa như một bộ tiên tri ngẫu nhiên. Khi đó, nếu (đa thức) các truy vấn đến bộ tiên tri . 
lược đồ chữ ký số nhận được từ việc áp dụng Do đó ở đây ta cần mô tả chính xác cách mà 
phép biến đổi Fiat-Shamir lên lược đồ là giả lập việc truy vấn của đến bộ tiên tri 
không thể bị giả mạo tồn tại dưới tấn công sử . Cụ thể thực hiện nhƣ sau: Đối với 
dụng thông điệp được lựa chọn thích nghi thì truy vấn thứ của đến , sẽ sinh 
lược đồ là an toàn tức là kháng lại được các ngẫu nhiên một thông điệp , sau đó thực hiện 
tấn công bị động. truy vấn ký trên đến bộ tiên tri ký. Kết quả 
30 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
của việc truy vấn ký là sẽ nhận đƣợc chữ ký Tất cả các lập luận trên cho thấy, sử dụng kẻ 
( ) trên thông điệp . Khi đó, nếu , tấn công đối với lƣợc đồ định danh nhƣ 
hoặc đã xuất hiện trong các truy vấn trƣớc một thủ tục con, ta đã xây dựng đƣợc một kẻ tấn 
đó, hoặc ( ) ( ) thì bỏ dở. công mà có thể giả mạo chữ ký của lƣợc đồ 
Ngƣợc lại, sẽ gửi trả về cho bản ghi chấp chữ ký số với xác suất đáng kể. Điều này trái 
nhận ( ) với ( ) nhƣ là với giả thiết lƣợc đồ chữ ký số là không thể 
phúc đáp của lời truy vấn thứ tới bộ tiên tri bị giả mạo tồn tại dƣới các tấn công sử dụng 
 . Và sẽ sử dụng các bản ghi này thông điệp đƣợc lựa chọn thích nghi. Do vậy 
trong nỗ lực mạo danh ngƣời chứng minh . suy ra, lƣợc đồ định danh phải an toàn kháng 
 lại các tấn công bị động. 
 Rõ ràng, do các thông điệp đƣợc chọn 
ngẫu nhiên, và theo giả thiết hàm băm đƣợc C. Điều kiện đủ cho tính an toàn bị động của 
mô hình hóa nhƣ một bộ tiên tri ngẫu nhiên nên các lược đồ định danh 
từ cách xây dựng , ta thấy xác suất để bỏ Trong mục trƣớc, với Định lý 1 và Mệnh đề 
dở các hoạt động là không đáng kể. Do đó suy 1, ta đã chỉ ra lƣợc đồ chữ ký số nhận đƣợc 
ra, xác suất của đƣa ra một chữ ký hợp lệ qua việc áp dụng Phép biến đổi Fiat-Shamir lên 
trên một thông điệp mà không cần đến khóa lƣợc đồ định danh là không thể bị giả mạo tồn 
bí mật sẽ xấp xỉ xác suất thành công của kẻ tại dƣới các tấn công sử dụng thông điệp đƣợc 
tấn công trừ đi một lƣợng không đáng kể. lựa chọn thích nghi nếu và chỉ nếu là an toàn 
 Ta mô tả kẻ tấn công đƣợc xây dựng từ bị động. Trong mục này, chúng tôi trình bày hai 
kẻ tấn công dƣới dạng thuật toán nhƣ sau: tiêu chuẩn mà là điều kiện đủ để một lƣợc đồ 
 định danh đạt đƣợc độ an toàn bị động. Đó là 
Kẻ tấn công : tiêu chuẩn không lộ tri thức cho người xác minh 
Kẻ tấn công đƣợc cho khóa công khai và trung thực (HVKZ) và tiêu chuẩn mạnh đặc biệt. 
đƣợc phép truy cập đến bộ tiên tri ký . Cụ thể các tiêu chuẩn này đƣợc định nghĩa 
 1. Sinh ngẫu nhiên một thông điệp . chính thức nhƣ dƣới đây. 
 2. Chạy ( ) và thực hiện nhƣ sau: Định nghĩa 4 ([3, Định nghĩa 8.3]). Một 
 lược đồ định danh là không lộ tri thức cho 
 Tính ( ) và gửi về cho 
 người xác minh trung thực (HVZK) nếu tồn tại 
 nhƣ là giá trị thách thức của ngƣời xác 
 một thuật toán PPT sao cho các phân bố 
 minh . sau đây là không thể phân biệt được về mặt tính 
 Khi thực hiện truy vấn thứ đến bộ toán: 
 tiên tri , thì trả lời nhƣ sau: {( ) ( ) ( ( ))} 
 - sinh ngẫu nhiên một thông điệp và 
 và thực hiện truy vấn ký trên đến bộ 
 {( ) ( ) ( )} 
 tiên tri ký , nhận về chữ ký hợp lệ 
 Nếu các phân bố trên là đồng nhất, ta nói là 
 ( ) trên . không lộ tri thức cho người xác minh trung thực 
 - Nếu , hoặc đã xuất hiện hoàn hảo. 
 trong các truy vấn trƣớc đó, hoặc Định nghĩa 5 ([3, Định nghĩa 8.4]). Một 
 ( ) ( ) thì bỏ dở. lược đồ định danh thỏa mãn tính chất mạnh 
 Ngƣợc lại, gửi cho bản ghi chấp đặc biệt nếu xác suất sau đây là không đáng kể 
 đối với mọi thuật toán PPT : 
 nhận ( ) với ( ). 
 3. Sau khi đƣa ra bản ghi chấp nhận 
 ( ) ( )
 ( ) thì đƣa ra ( ) nhƣ là chữ [
 ( ) ( )
 ký trên thông điệp . 
 và
 ( ) ( ) ] 
 đều là các bản ghi chấp nhận
 Số 2.CS (08) 2018 31 
Journal of Science and Technology on Information Security 
 Định lý sau đây chỉ ra hai tiêu chuẩn trên là Đồng thời, trong bài báo, đã đƣa ra Nhận 
điều kiện đủ đảm bảo cho độ an toàn bị động xét 1 để chỉ ra sự tƣơng đồng giữa Phép 
của các lƣợc đồ định danh. biến đổi Fiat-Shamir và biến thể của nó. 
 Định lý 2 ([3, Định lý 8.2]). Giả sử lược đồ 
 Hướng nghiên cứu tiếp theo: Việc xây 
định danh là không lộ tri thức cho người xác dựng các lƣợc đồ chữ ký số từ các lƣợc đồ định 
minh trung thực và thỏa mãn tính chất mạnh danh là một trong số những phƣơng pháp quan 
đặc biệt. Khi đó với mọi kẻ tấn công trọng, bao hàm nhiều khía cạnh tinh tế của mật 
( ) ta có: mã hiện đại. Trong khuôn khổ một bài báo 
 ( ) ( ) chúng tôi chƣa đủ khả năng cũng nhƣ thời gian 
 [ ( )
 ( ) để trình bày một cách đầy đủ, chi tiết, sâu sắc về 
 tất cả các khía cạnh mật mã của phƣơng pháp 
 〈 ( ) ( ) 〉] xây dựng này, chẳng hạn nhƣ về các điều kiện 
 cho lƣợc đồ định danh để có các lƣợc đồ chữ ký 
 | | ( ) số đạt tính chất an toàn về phía trƣớc cũng nhƣ 
với hàm không đáng kể ( ) nào đó. Cụ thể hơn, về các lƣợc đồ định danh cụ thể với các tính 
nếu | | ( ( )) thì là an toàn kháng chất an toàn tốt, tiêu biểu là lƣợc đồ Fiat-
lại các tấn công bị động. Shamir, lƣợc đồ Schnorr, lƣợc đồ Guillou-
 Chứng minh. Chi tiết xem trong tài liệu đã Quisquater,. Ngoài ra, việc so sánh các tính 
dẫn. chất an toàn giữa các lƣợc đồ chữ ký số nhận 
 đƣợc từ các lƣợc đồ định danh qua phép biến 
 Từ các Định lý 1 và Định lý 2 ta có hệ quả đổi Fiat-Shamir với các lƣợc đồ chữ ký số 
sau đây. không đƣợc xây dựng dựa trên phép biến đổi 
 Hệ quả 1. Cho ( ) là một lược này, (chẳng hạn nhƣ lƣợc đồ RSA, ECDSA) 
đồ định danh thỏa mãn các tiêu chuẩn như cũng chƣa đƣợc đề cập đến trong bài báo. Do đó 
trong Định lý 2. Khi đó nếu hàm băm được các vấn đề này cần đƣợc tiếp tục nghiên cứu sâu 
mô hình hóa như một bộ tiên tri ngẫu nhiên thì hơn nữa. 
lược đồ chữ ký số nhận được từ việc áp dụng 
phép biến đổi Fiat-Shamir lên là không thể bị 
giả mạo tồn tại dưới các tấn công sử dụng 
thông điệp được lựa chọn thích nghi. 
 Chứng minh. Khẳng định này là hiển nhiên 
từ các Định lý 1 và 2. 
 IV. KẾT LUẬN 
 Trong bài báo này chúng tôi đã trình bày 
nội dung cơ bản về phƣơng pháp xây dựng lƣợc 
đồ chữ ký số từ các lƣợc đồ định danh với việc 
sử dụng phép biến đổi Fiat-Shamir. Ngoài các 
định nghĩa và kết quả đƣợc trích dẫn từ tài liệu 
tham khảo [2], đóng góp của chúng tôi qua bài 
báo gồm có: 
 Phát biểu và chứng minh Mệnh đề 1 về 
 điều kiện cần của lƣợc đồ định danh để đảm 
 bảo cho lƣợc đồ chữ ký xây dựng từ nó là 
 an toàn. 
 Chúng tôi đƣa ra Hệ quả 1 nhƣ là một sự 
 tổng kết về một số ―điều kiện đủ‖ cho các 
 lƣợc đồ định danh để đảm bảo tính an toàn 
 cho lƣợc đồ chữ ký số đƣợc xây dựng từ nó. 
32 Số 2.CS (08) 2018 
 Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 TÀI LIỆU THAM KHẢO SƠ LƢỢC VỀ TÁC GIẢ 
[1]. Michel Abdalla, Jee Hea An, Mihir Bellare, and ThS. Võ Tùng Linh 
 Chanathip Namprempre. ―From identification to Đơn vị công tác: Viện Khoa học – 
 signatures via the Fiat-Shamir transform: Công nghệ mật mã, Ban Cơ yếu 
 Necessary and sufficient conditions for security Chính phủ. 
 and forward-security‖. IEEE Transactions on 
 Email: vtlinh@gmail.com 
 Information Theory, 54(8): pp.3631-3646, 2008. 
 Quá trình đào tạo: nhận bằng Cử 
[2]. Amos Fiat and Adi Shamir. ―How to prove 
 nhân toán học năm 2005 và bằng 
 yourself: Practical solutions to identification and 
 Thạc sỹ toán học năm 2014. 
 signature problems‖. In Advances in Cryptology 
 - CRYPTO’86, pp. 186-194, Springer, 1986. Lĩnh vực nghiên cứu hiện nay: mật mã khóa công 
 khai, mật mã đƣờng cong elliptic. 
[3]. Jonathan Katz. ―Digital signatures‖. Springer 
 Science & Business Media, 2010. 
 Số 2.CS (08) 2018 33