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

Một phƣơng pháp hiệu quả để xây dựng các

lƣợc đồ chữ ký số an toàn là sử dụng kỹ thuật

biến đổi từ một lƣợc đồ định danh có tính chất

mật mã tốt. Phƣơng pháp đƣợc giới thiệu lần

đầu bởi Amos Fiat và Adi Shamir trong [2] nên

phép biến đổi đƣợc gọi là Phép biến đổi FiatShamir,

và dần trở thành một phƣơng pháp phổ

biến, một trong những công cụ để nhận đƣợc

các lƣợc đồ chữ ký số an toàn. Ý tƣởng chính

đằng sau phép biến đổi Fiat-Shamir là ngƣời ta

 chứng minh trong một lƣợc đồ định danh chạy

chính lƣợc đồ đó để sinh một giá trị thách thức

bằng cách áp dụng một hàm băm lên thông điệp

đầu tiên, sau đó tính một giá trị phúc đáp thích

hợp. Nếu hàm băm đƣợc mô hình hóa nhƣ một

bộ tiên tri ngẫu nhiên thì thách thức đƣợc sinh

bởi hàm băm đó là ―ngẫu nhiên thực sự‖, do đó

sẽ khiến kẻ tấn công (không biết các giá trị bí

mật) khó khăn trong việc tìm kiếm một bản ghi

chấp nhận đƣợc khi muốn mạo danh ngƣời

chứng minh trong một lần thực thi trung thực

lƣợc đồ. Bằng việc đƣa cả thông điệp vào trong

đầu vào hàm băm, một bản ghi chấp nhận đƣợc

sẽ góp phần tạo nên chữ ký trên thông điệp. Ta

sẽ cụ thể hóa ý tƣởng này trong các phần sau.

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

Trang 1

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

Trang 2

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

Trang 3

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

Trang 4

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

Trang 5

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

Trang 6

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

Trang 7

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

Trang 8

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

Trang 9

pdf 9 trang minhkhanh 6120
Bạn đang xem tài liệu "Xây dựng lược đồ chữ ký số an toàn từ các lược đồ định danh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Xây dựng lược đồ chữ ký số an toàn từ các lược đồ định danh

Xây dựng lược đồ chữ ký số an toàn từ các lược đồ định danh
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 25 
Võ Tùng Linh
Tóm tắt— Trong tài liệu [3], khi trình bày về 
phương pháp xây dựng lược đồ chữ ký số dựa trên 
các lược đồ định danh chính tắc nhờ phép biến đổi 
Fiat-Shamir, tác giả đã chỉ ra “điều kiện đủ” để 
nhận được một lược đồ chữ ký số an toàn dưới tấn 
công sử dụng thông điệp được lựa chọn thích nghi 
là lược đồ định danh chính tắc phải an toàn dưới 
tấn công bị động. Tuy nhiên, tác giả của [3] chưa chỉ 
ra “điều kiện cần” đối với các lược đồ định danh 
chính tắc nhằm đảm bảo tính an toàn cho lược đồ 
chữ ký số được xây dựng. Do đó, trong bài báo này, 
chúng tôi hoàn thiện kết quả của [3] bằng việc chỉ 
ra điều kiện đủ đó cũng chính là điều kiện cần. 
Abstract— In [3], the author shows that, in order 
to the digital signature scheme Π' resulting from the 
Fiat-Shamir transform applied to a canonical 
identification scheme Π is existentially unforgeable 
under chosen-message attack then a “sufficient” 
condition is that the scheme Π has to be secure 
against a passive attack. However, the author of [3] 
has not shown the “necessary” conditions for the 
canonical identification schemes to ensure security 
of the digital signature scheme Π'. In this paper, we 
complete this result by showing that sufficient 
condition is also necessary. 
Từ khóa: Lược đồ định danh; lược đồ chữ ký 
số; phép biến đổi Fiat-Shamir. 
Keywords: Identification scheme; signature 
scheme; Fiat-Shamir transform. 
I. GIỚI THIỆU 
Một phƣơng pháp hiệu quả để xây dựng các 
lƣợc đồ chữ ký số an toàn là sử dụng kỹ thuật 
biến đổi từ một lƣợc đồ định danh có tính chất 
mật mã tốt. Phƣơng pháp đƣợc giới thiệu lần 
đầu bởi Amos Fiat và Adi Shamir trong [2] nên 
phép biến đổi đƣợc gọi là Phép biến đổi Fiat-
Shamir, và dần trở thành một phƣơng pháp phổ 
biến, một trong những công cụ để nhận đƣợc 
các lƣợc đồ chữ ký số an toàn. Ý tƣởng chính 
đằng sau phép biến đổi Fiat-Shamir là ngƣời ta 
Bài báo đƣợc nhận ngày 1/12/2018. Bài báo đƣợc nhận 
xét bởi phản biện thứ nhất vào ngày 11/12/2018 và đƣợc chấp 
nhận đăng vào ngày 18/12/2018. Bài báo đƣợc nhận xét bởi 
phản biện thứ hai vào ngày 14/12/2018 và đƣợc chấp nhận 
đăng vào ngày 28/12/2018. 
chứng minh trong một lƣợc đồ định danh chạy 
chính lƣợc đồ đó để sinh một giá trị thách thức 
bằng cách áp dụng một hàm băm lên thông điệp 
đầu tiên, sau đó tính một giá trị phúc đáp thích 
hợp. Nếu hàm băm đƣợc mô hình hóa nhƣ một 
bộ tiên tri ngẫu nhiên thì thách thức đƣợc sinh 
bởi hàm băm đó là ―ngẫu nhiên thực sự‖, do đó 
sẽ khiến kẻ tấn công (không biết các giá trị bí 
mật) khó khăn trong việc tìm kiếm một bản ghi 
chấp nhận đƣợc khi muốn mạo danh ngƣời 
chứng minh trong một lần thực thi trung thực 
lƣợc đồ. Bằng việc đƣa cả thông điệp vào trong 
đầu vào hàm băm, một bản ghi chấp nhận đƣợc 
sẽ góp phần tạo nên chữ ký trên thông điệp. Ta 
sẽ cụ thể hóa ý tƣởng này trong các phần sau. 
Với việc xây dựng lƣợc đồ chữ ký số từ lƣợc 
đồ định danh sử dụng phép biến đổi Fiat-
Shamir, câu hỏi đặt ra là: ―Lƣợc đồ định danh 
cần thỏa mãn những điều kiện (tối thiểu) nào để 
đảm bảo tính an toàn cho lƣợc đồ chữ ký số 
đƣợc xây dựng‖. Trong bài báo này, theo các 
kết quả nghiên cứu chính từ các tài liệu [1, 3] 
chúng tôi sẽ chỉ ra một cách chi tiết về các điều 
kiện cần thiết đối với lƣợc đồ định danh sao cho 
đảm bảo đƣợc tính an toàn của lƣợc đồ chữ ký 
số xây dựng lên từ nó chống lại các tấn công lựa 
chọn thông điệp. 
Đóng góp của nhóm tác giả: Trong tài liệu 
[3], tác giả đã chỉ ra rằng, để lƣợc đồ chữ ký số 
 nhận đƣợc từ lƣợc đồ định danh qua phép 
biến đổi Fiat-Shamir không 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 thì một ―điều kiện đủ‖ là lƣợc 
đồ phải an toàn dƣới các tấn công bị động. 
Trong bài báo này, với Mệnh đề 1, chúng tôi 
hoàn thiện kết quả này bằng cách chỉ ra điều 
kiện đó cũng chính là một ―điều kiện cần‖ để 
đảm bảo cho lƣợc đồ chữ ký số an toàn. Mặc 
dù kết luận tƣơng tự đã đƣợc chỉ ra trong [1], 
tuy nhiên ở đây kỹ thuật chứng minh chúng tôi 
sử dụng là thống nhất với cách trình bày của tài 
liệu [3], khác với kỹ thuật sử dụng trong [1]. 
Xây dựng lƣợc đồ chữ ký số an toàn từ các 
lƣợc đồ định danh 
Journal of Science and Technology on Information Security 
26 Số 2.CS (08) 2018 
Bố cục của bài báo: Mục II chúng tôi trình 
bày định nghĩa các lƣợc đồ định danh cùng với 
độ an toàn hình thức của chúng dƣới các tấn 
công bị động. Mục III trình bày về phƣơng pháp 
xây dựng lƣợc đồ chữ ký số từ các lƣợc đồ định 
danh chính tắc qua phép biến đổi Fiat-Shamir 
cùng với kết quả chính về điều kiện cần và đủ 
để lƣợc đồ chữ ký số thu đƣợc là an toàn. Cuối 
cùng là Mục Kết luận. 
II. ĐỊNH NGHĨA LƢỢC ĐỒ ĐỊNH DANH 
VÀ ĐỘ AN TOÀN 
Trƣớc khi định nghĩa lƣợc đồ định danh là 
gì, ta xét một kịch bản mà trong đó ngƣời tham 
gia (gọi là người chứng minh) muốn thuyết 
phục ngƣời tham gia khác, ký hiệu (gọi là 
người xác minh), rằng anh ta chính là nhƣ đã 
khẳng định. Cụ thể hơn, ta có thể thấy tình 
huống này nảy sinh trong các trƣờng hợp chẳng 
hạn nhƣ và chƣa bao giờ gặp nhau trƣớc đó, 
hoặc và liên lạc qua một kênh truyền thông 
(nhƣng không mặt-đối-mặt với nhau) và 
muốn đảm bảo rằng mình đang liên lạc với 
chứ không phải là một kẻ mạo danh nào đó. Để 
cho sự đảm bảo này có ý nghĩa thì rõ ràng phải 
có một số thông tin để phân biệt với những 
ngƣời khác, nếu không thì bất kỳ ai cũng có thể 
giả mạo là . Một giải pháp để có thể thuyết 
phục những ngƣời xác minh tiềm năng là, 
thiết lập một khóa công khai mà tất cả những 
ngƣời xác minh (tiềm năng) đều đƣợc biết, sau 
đó sử dụng một khóa bí mật tƣơng ứng với khóa 
công khai này, chạy một trƣờng hợp cụ thể 
của lƣợc đồ mà đƣợc gọi là lược đồ định danh 
để thuyết phục ngƣời xác minh tin rằng mình 
chính là ngƣời mà đƣợc đại diện bởi khóa công 
khai . 
Định nghĩa 1 ([3, Định nghĩa 8. ...  luận đã trình bày phía dƣới Định 
nghĩa 2, để không mất tính tổng quát, ta có thể 
giả thiết cho phép đƣợc truy cập đến bộ tiên 
tri ngay cả trong quá trình tƣơng tác 
với . 
Bây giờ, giả sử là một kẻ tấn công PPT 
đối với lƣợc đồ . Ta sẽ đƣa ra một vài giả 
thiết đơn giản mà không làm mất đi tính tổng 
quát. Trƣớc tiên, ta giả thiết chỉ thực hiện 
truy vấn đối với giá trị băm đã cho chỉ duy nhất 
một lần. Để đơn giản, khi đƣợc cho một chữ 
ký ( ) trên thông điệp thì đồng thời 
cũng đƣợc cho giá trị ( ), do đó ta giả thiết 
 không bao giờ truy vấn ( ) sau khi đã 
nhận đƣợc chữ ký ( ) trên . Ta cũng yêu 
cầu, nếu đƣa ra chữ ký giả mạo ( ) trên 
thông điệp , thì đã yêu cầu trƣớc đó một 
truy vấn băm ( ). Ta gọi truy vấn băm duy 
nhất này là truy vấn băm đặc biệt. Ký hiệu là 
biên trên đa thức cho số lƣợng các truy vấn băm 
đƣợc thực hiện bởi . 
Tiếp theo ta mô tả kẻ tấn công PPT lên 
lƣợc đồ . Kẻ tấn công đƣợc cho đầu vào là 
khóa công khai , đƣợc phép truy cập đến bộ 
tiên tri , và có tƣơng tác với ngƣời 
xác minh . Hoạt động đầu tiên thực hiện là 
đoán một chỉ số ngẫu nhiên * +. Chỉ 
số này đóng vai trò là phỏng đoán cho chỉ số 
của truy vấn băm đặc biệt (nếu có) sẽ đƣợc thực 
hiện bởi . Sau đó, kẻ tấn công chạy 
 ( ), và trả lời các truy vấn của nhƣ sau: 
Truy vấn băm ( ): Có hai trƣờng hợp: 
 Nếu đây là truy vấn thứ đến , thì sẽ 
đƣa ra phỏng đoán truy vấn này chính là truy 
vấn băm đặc biệt. gửi tới ngƣời xác 
minh trung thực mà nó đƣợc phép tƣơng 
tác, và nhận giá trị trả về là một thách thức . 
Sau đó gửi cho nhƣ là câu phúc đáp 
ứng với truy vấn băm này. Ta gọi truy vấn 
băm trong trƣờng hợp này là truy vấn đã 
phỏng đoán. 
 Nếu đây không phải là truy vấn thứ thì 
chọn ngẫu nhiên một giá trị và gửi 
về để phúc đáp truy vấn này. 
Rõ ràng, trong cả hai trƣờng hợp giá trị trả về 
mà nhận đƣợc đều có phân bố đều trong . 
Truy vấn ký ( ): truy vấn tới bộ 
tiên tri và nhận đƣợc bản ghi 
( ). Nếu giá trị băm ( ) đã đƣợc xác 
định trƣớc đó thì bỏ dở. Ngƣợc lại, gửi trả 
về chữ ký ( ) cho (cùng với giá trị băm 
 ( ) ). 
Nếu đƣa ra một chữ ký hợp lệ ( ̂ ̂) trên 
thông điệp ̂ , thì kiểm tra xem truy vấn đã 
phỏng đoán ( ) có bằng truy vấn đặc biệt 
 ( ̂ ̂) hay không. Nếu chúng không bằng 
nhau, thì kết luận bỏ dở. Ngƣợc lại, gửi ̂ 
tới ngƣời xác minh . 
Chú ý rằng, với điều kiện không bỏ dở 
trong khi thực thi và phỏng đoán của nó về truy 
Journal of Science and Technology on Information Security 
30 Số 2.CS (08) 2018 
vấn đặc biệt là đúng, thì thành công trong 
việc giả mạo ngƣời chứng minh trung thực. Lý 
do là bởi vì: 
 Khi truy vấn đã phỏng đoán bằng với truy 
vấn đặc biệt, tức là đã gửi ̂ tới ngƣời xác 
minh, và nhận về thách thức ( ̂ ̂). 
 ( ̂ ̂) là một chữ ký hợp lệ trên ̂ nếu 
( ̂ ̂) chính xác là một bản ghi chấp nhận. 
 bỏ dở nếu, trong quá trình trả lời một truy 
vấn ký cho thông điệp , nhận đƣợc bản ghi 
( ) mà với nó truy vấn băm ( ) đã 
đƣợc thực hiện bởi . Vì lƣợc đồ định danh 
đƣợc giả thiết là chính tắc (và vì thế thông điệp 
đầu tiên là không suy biến) nên xác suất để xảy 
ra trƣờng hợp này là không đáng kể. 
Giả sử không bỏ dở trong quá trình thực 
thi, thì nó là một sự giả lập hoàn hảo cho . 
Hơn nữa, phỏng đoán của về truy vấn đặc 
biệt là đúng với xác suất (và biến cố này 
độc lập với biến cố đƣa ra một chữ ký giả 
mạo hợp lệ). Nếu thành công trong việc đƣa 
ra một chữ ký hợp lệ với xác suất thì thành 
công trong việc giả mạo với xác suất 
( ( )) với ( ) là một hàm nào đó mà 
không đáng kể theo . Do lƣợc đồ định danh 
là an toàn bị động, nên suy ra ta nhận đƣợc 
khẳng định cần chứng minh. 
Định lý 1 đã cung cấp cho ta một ―điều kiện 
đủ‖ để nhận đƣợc một lƣợc đồ chữ ký số không 
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 từ việc áp 
dụng phép biến đổi Fiat-Shamir lên các lƣợc đồ 
định danh, đó là ―lƣợc đồ định danh phải an 
toàn kháng lại các tấn công bị động và hàm băm 
 phải đƣợc mô hình hóa nhƣ một bộ tiên tri 
ngẫu nhiên‖. 
Tuy nhiên, không chỉ có vậy, với mệnh đề 
dƣới đây, chúng tôi chỉ ra ―điều kiện đủ‖ đƣa ra 
ở Định lý 1 cũng chính là ―điều kiện cần‖. 
Mệnh đề 1. Cho ( ) là một lược 
đồ định danh. Giả sử hàm băm được mô hình 
hóa như một bộ tiên tri ngẫu nhiên. Khi đó, nếu 
lược đồ chữ ký số nhận được từ việc áp dụng 
phép biến đổi Fiat-Shamir lên lược đồ là 
không 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 thì 
lược đồ là an toàn tức là kháng lại được các 
tấn công bị động. 
Chứng minh. Ta sẽ sử dụng phƣơng pháp 
phản chứng để chỉ ra điều cần chứng minh. Giả 
sử ngƣợc lại rằng lƣợc đồ chữ ký số là không 
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 
lƣợc đồ định danh không an toàn dƣới các tấn 
công bị động. Khi đó, tồn tại một kẻ tấn công 
mà dựa vào khóa công khai có thể mạo danh 
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 
hữu hạn (đa thức) đến bộ tiên tri để nhận 
đƣợc các bản ghi chấp nhận. Mục tiêu của ta là 
xây dựng một kẻ tấn công đƣợc phép truy 
cập đến bộ tiên tri ký mà sử dụng nhƣ 
một thủ tục con để giả mạo thành công chữ ký 
của lƣợc đồ với xác suất đáng kể. 
Kẻ tấn công đƣợc xây dựng một cách đơn 
giản nhƣ sau: Để đƣa ra một chữ ký giả mạo 
trên thông điệp , trƣớc tiên chạy để sinh 
ra một thông điệp . tính giá trị ( ) 
và gửi trả về nhƣ là giá trị thách thức của . 
Do đƣợc mô hình hóa nhƣ một bộ tiên tri 
ngẫu nhiên nên giá trị thách thức mà nhận 
đƣợc cũng đƣợc phân bố đều trong nhƣ mọi 
giá trị thách thức khác do ngƣời xác minh chọn 
ngẫu nhiên đều từ . Có thể lặp lại hoạt động 
của một số hữu hạn (đa thức) lần cho đến 
khi đƣa ra một câu phúc đáp tƣơng ứng với 
thông điệp . Theo giả thiết thì ( ) sẽ là 
bản ghi chấp nhận vƣợt qua đƣợc bƣớc kiểm tra 
của ngƣời xác minh với xác suất đáng kể. 
Cuối cùng, đƣa ra ( ) nhƣ là chữ ký giả 
mạo trên thông điệp . Rõ ràng, ngoại trừ với 
một xác suất nhỏ không đáng kể nhƣ sẽ chỉ ra 
dƣới đây, ( ) là một chữ ký hợp lệ trên thông 
điệp nhận đƣợc từ bản ghi chấp nhận 
( ). Nhƣ vậy đã tạo ra đƣợc chữ ký 
hợp lệ ( ) trên thông điệp với xác suất 
đáng kể mà không cần biết khóa bí mật. 
Cần lƣu ý rằng, trong quá trình tấn công để 
mạo danh , trƣớc khi đƣa ra phúc đáp tƣơng 
ứng với thách thức và thông điệp , kẻ tấn 
công có thể thực hiện một số lƣợng hữu hạn 
(đa thức) các truy vấn đến bộ tiên tri . 
Do đó ở đây ta cần mô tả chính xác cách mà 
giả lập việc truy vấn của đến bộ tiên tri 
 . Cụ thể thực hiện nhƣ sau: Đối với 
truy vấn thứ của đến , sẽ sinh 
ngẫu nhiên một thông điệp , sau đó thực hiện 
truy vấn ký trên đến bộ tiên tri ký. Kết quả 
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 31 
của việc truy vấn ký là sẽ nhận đƣợc chữ ký 
( ) trên thông điệp . Khi đó, nếu , 
hoặc đã xuất hiện trong các truy vấn trƣớc 
đó, hoặc ( ) ( ) thì bỏ dở. 
Ngƣợc lại, sẽ gửi trả về cho bản ghi chấp 
nhận ( ) với ( ) nhƣ là 
phúc đáp của lời truy vấn thứ tới bộ tiên tri 
 . Và sẽ sử dụng các bản ghi này 
trong nỗ lực mạo danh ngƣời chứng minh . 
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 
mô hình hóa nhƣ một bộ tiên tri ngẫu nhiên nên 
từ cách xây dựng , ta thấy xác suất để bỏ 
dở các hoạt động là không đáng kể. Do đó suy 
ra, xác suất của đƣa ra một chữ ký hợp lệ 
trên một thông điệp mà không cần đến khóa 
bí mật sẽ xấp xỉ xác suất thành công của kẻ 
tấn công trừ đi một lƣợng không đáng kể. 
Ta mô tả kẻ tấn công đƣợc xây dựng từ 
kẻ tấn công dƣới dạng thuật toán nhƣ sau: 
Kẻ tấn công : 
Kẻ tấn công đƣợc cho khóa công khai và 
đƣợc phép truy cập đến bộ tiên tri ký . 
1. Sinh ngẫu nhiên một thông điệp . 
2. Chạy ( ) và thực hiện nhƣ sau: 
 Tính ( ) và gửi về cho 
nhƣ là giá trị thách thức của ngƣời xác 
minh . 
 Khi thực hiện truy vấn thứ đến bộ 
tiên tri , thì trả lời nhƣ sau: 
- sinh ngẫu nhiên một thông điệp 
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ệ 
( ) trên . 
- Nếu , hoặc đã xuất hiện 
trong các truy vấn trƣớc đó, hoặc 
 ( ) ( ) thì bỏ dở. 
Ngƣợc lại, gửi cho bản ghi chấp 
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 . 
Tất cả các lập luận trên cho thấy, sử dụng kẻ 
tấn công đối với lƣợc đồ định danh nhƣ 
một thủ tục con, ta đã xây dựng đƣợc một kẻ tấn 
công mà có thể giả mạo chữ ký của lƣợc đồ 
chữ ký số với xác suất đáng kể. Điều này trái 
với giả thiết lƣợc đồ chữ ký số 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. Do vậy 
suy ra, lƣợc đồ định danh phải an toàn kháng 
lại các tấn công bị động. 
C. Điều kiện đủ cho tính an toàn bị động của 
các lược đồ định danh 
Trong mục trƣớc, với Định lý 1 và Mệnh đề 
1, ta đã chỉ ra lƣợc đồ chữ ký số nhận đƣợc 
qua việc áp dụng Phép biến đổi Fiat-Shamir lên 
lƣợc đồ định danh 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 nếu và chỉ nếu là an toàn 
bị động. Trong mục này, chúng tôi trình bày hai 
tiêu chuẩn mà là điều kiện đủ để một lƣợc đồ 
định danh đạt đƣợc độ an toàn bị động. Đó là 
tiêu chuẩn không lộ tri thức cho người xác minh 
trung thực (HVKZ) và tiêu chuẩn mạnh đặc biệt. 
Cụ thể các tiêu chuẩn này đƣợc định nghĩa 
chính thức nhƣ dƣới đây. 
Định nghĩa 4 ([3, Định nghĩa 8.3]). Một 
lược đồ định danh là không lộ tri thức cho 
người xác minh trung thực (HVZK) nếu tồn tại 
một thuật toán PPT sao cho các phân bố 
sau đây là không thể phân biệt được về mặt tính 
toán: 
{( ) ( ) ( ( ))} 
và 
{( ) ( ) ( )} 
Nếu các phân bố trên là đồng nhất, ta nói là 
không lộ tri thức cho người xác minh trung thực 
hoàn hảo. 
Định nghĩa 5 ([3, Định nghĩa 8.4]). Một 
lược đồ định danh thỏa mãn tính chất mạnh 
đặ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 : 
 [
( ) ( )
( ) ( )
 và
( ) ( )
đều là các bản ghi chấp nhận
] 
Journal of Science and Technology on Information Security 
32 Số 2.CS (08) 2018 
Định lý sau đây chỉ ra hai tiêu chuẩn trên là 
điều kiện đủ đảm bảo cho độ an toàn bị động 
của các lƣợc đồ định danh. 
Định lý 2 ([3, Định lý 8.2]). Giả sử lược đồ 
định danh là không lộ tri thức cho người xác 
minh trung thực và thỏa mãn tính chất mạnh 
đặc biệt. Khi đó với mọi kẻ tấn công 
( ) ta có: 
 [
( ) ( )
 ( )( )
 〈 ( ) ( ) 〉]
 | |
 ( ) 
với hàm không đáng kể ( ) nào đó. Cụ thể hơn, 
nếu | | ( ( )) thì là an toàn kháng 
lại các tấn công bị động. 
Chứng minh. Chi tiết xem trong tài liệu đã 
dẫn. 
Từ các Định lý 1 và Định lý 2 ta có hệ quả 
sau đây. 
Hệ quả 1. Cho ( ) là một lược 
đồ định danh thỏa mãn các tiêu chuẩn như 
trong Định lý 2. Khi đó 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ố 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ó. 
Đồng thời, trong bài báo, đã đƣa ra Nhận 
xét 1 để chỉ ra sự tƣơng đồng giữa Phép 
biến đổi Fiat-Shamir và biến thể của nó. 
Hướng nghiên cứu tiếp theo: Việc xây 
dựng các lƣợc đồ chữ ký số từ các lƣợc đồ định 
danh là một trong số những phƣơng pháp quan 
trọng, bao hàm nhiều khía cạnh tinh tế của mật 
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ề các lƣợc đồ định danh cụ thể với các tính 
chất an toàn tốt, tiêu biểu là lƣợc đồ Fiat-
Shamir, lƣợc đồ Schnorr, lƣợc đồ Guillou-
Quisquater,. Ngoài ra, việc so sánh các tính 
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 
đổi Fiat-Shamir với các lƣợc đồ chữ ký số 
không đƣợc xây dựng dựa trên phép biến đổi 
này, (chẳng hạn nhƣ lƣợc đồ RSA, ECDSA) 
cũng chƣa đƣợc đề cập đến trong bài báo. Do đó 
các vấn đề này cần đƣợc tiếp tục nghiên cứu sâu 
hơn nữa. 
Nghiên cứu Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 2.CS (08) 2018 33 
TÀI LIỆU THAM KHẢO 
[1]. Michel Abdalla, Jee Hea An, Mihir Bellare, and 
Chanathip Namprempre. ―From identification to 
signatures via the Fiat-Shamir transform: 
Necessary and sufficient conditions for security 
and forward-security‖. IEEE Transactions on 
Information Theory, 54(8): pp.3631-3646, 2008. 
[2]. Amos Fiat and Adi Shamir. ―How to prove 
yourself: Practical solutions to identification and 
signature problems‖. In Advances in Cryptology 
- CRYPTO’86, pp. 186-194, Springer, 1986. 
[3]. Jonathan Katz. ―Digital signatures‖. Springer 
Science & Business Media, 2010. 
SƠ LƢỢC VỀ TÁC GIẢ 
ThS. Võ Tùng Linh 
Đơn vị công tác: Viện Khoa học – 
Công nghệ mật mã, Ban Cơ yếu 
Chính phủ. 
Email: vtlinh@gmail.com 
Quá trình đào tạo: nhận bằng Cử 
nhân toán học năm 2005 và bằng 
Thạc sỹ toán học năm 2014. 
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. 

File đính kèm:

  • pdfxay_dung_luoc_do_chu_ky_so_an_toan_tu_cac_luoc_do_dinh_danh.pdf