Chương 6: Các sơ đồ chữ kí số

Trong chương này, chúng ta xem xét các sơ đồ chữ kí số (còn đượcgọi là chữ kí số ). Chữ kí viết tay thông thường trên tàI liệu thường đượcdùng để xác người kí nó. Chữ kí được dùng hàng ngày chẳng hạn như trênmột bức thư nhận tiền từ nhà băng, kí hợp đồng...
Nội dung trích xuất từ tài liệu:
Chương 6: Các sơ đồ chữ kí số Chương 6 Các sơ đồ chữ kí số6.1 giới thiệu. Trong chương này, chúng ta xem xét các sơ đồ chữ kí số (còn đượcgọi là chữ kí số ). Chữ kí viết tay thông thường trên tàI liệu thường đượcdùng để xác người kí nó. Chữ kí được dùng hàng ngày chẳng hạn như trênmột bức thư nhận tiền từ nhà băng, kí hợp đồng... Sơ đồ chữ kí là phương pháp kí một bức đIửn lưu dưới dang đIêntừ. Chẳng hạn một bức đIửn có ký hiệu được truyền trên mạng máy tinh.Chương trình này nghiên cứu vàI sơ đồ chữ kí. Ta sẽ thảo luận trên mộtvàI khác biệt cơ bản giửa các chữ kí thông thường và chữ kí số. Đầu tiên là một vấn đề kí một tàI liệu. Với chữ kí thông thường, nólà một phần vật lý của tàI liệu. Tuy nhiên, một chữ kí số không gắn theokiểu vật lý vào bức đIửn nên thuật toán được dùng phảI ”không nhìnthấy” theo cách nào đó trên bức đIửn. Thứ hai là vấn đề về kiểm tra. Chữ kí thông thường được kiểm trabằng cách so sánh nó với các chữ kí xác thực khác. ví dụ, ai đó kí một tấmséc để mua hàng, người bán phảI so sánh chữ kí trên mảnh giấy với chữkí nằm ở mặt sau của thẻ tín dụng để kiểm tra. Dĩ nhiên, đây không phảIlà phươg pháp an toàn vì nó dể dàng giả mạo. Mắt khác, các chữ kí số cóthể được kiểm tra nhờ dùng một thuật toán kiểm tra công khai. Như vậy,bất kỳ ai cũng có thể kiểm tra dược chữ kí số. Việc dùng một sơ đồ chữkí an toàn có thể sẽ ngăn chặn dược khả năng giả mạo. Sự khác biệt cơ bản khác giữa chữ kí số và chữ kí thông thườngbản copy tàI liệu được kí băng chữ kí số đồng nhất với bản gốc, còn copytàI liệu có chữ kí trên giấy thường có thể khác với bản gốc. ĐIũu này cónghĩa là phảI cẩn thận ngăn chăn một bức kí số khỏi bị dung lạI. Ví dụ,Bob kí một bức đIửn xác nhận Alice có khả năng làm đIũu đó một lần. Vìthế, bản thân bức đIửn cần chứa thông tin (chẳng hạn như ngay tháng) đểngăn nó khỏi bị dung lại. Một sơ đồ chữ kí số thường chứa hai thành phần: thuật toán kí vàthuận toán xá minh. Bob có thể kí đIửn x dùng thuật toán kí an toàn. Chữkí sig(x) nhận được có thể kiểm tra băng thuật toán xác minh công khaiver. Khi cho trước cặp (x,y), thuật toán xác minh có giá trị TRUE hayFALSE tuỳ thuộc vào chữ kí được thực như thế nào. Dưới đây là địnhnghĩa hình thức của chữ kí:Định nghĩa 6.1 Một sơ đồ chữ kí số là bộ 5( P,A, K,S,V) thoả mãn các đIũu kiệndưới đây: 1. P là tập hữu hạn các bứ đIửn có thể. 2. A là tập hữu hạn các chữ kí có thể. 3. K không gian khoá là tập hữu hạn các khoá có thể. 4. Với mỗi K thuộc K tồn tạI một thuật toán kí sigk ∈ S và là mộtthuật toán xác minh verk∈ V. Mỗi sigk : P → A và verk: P× a →{ true,false}là những hàm sao cho mỗi bức đIửn x∈ P và mối chữ kí y∈ a thoả mãnphương trình dưới đây. True nếu y=sig(x) verk False nếu y# sig(x) Với mỗi k thuộc K hàm sigk và verk là các hàm thơì than đa thức.Verk sẽ là hàm công khai sigk là mật. Không thể dể dàng tính toán để giảmạo chữ kí của Bob trên bức điện x. Nghĩa là x cho trước, chỉ có Bob mớicó thể tính được y để verk = True. Một sơ đồ chữ kí không thể an toàn vôđIêu kiện vì Oscar có thể kiểm tra tất cả các chữ số y có thể có trên bứcđIửn x nhờ dung thuât toán ver công khai cho đến khi anh ta tìm thấy mộtchữ kí đúng. Vi thế, nếu có đủ thời gian. Oscar luôn luôn có thể giả mạochữ kí của Bob. Như vậy, giống như trường hợp hệ thống mã khoá côngkhai, mục đích của chúng ta là tìm các sơ đồ chữ kí số an toan về mặt tínhtoán. Xem thấy rằng, hệ thống mã khoá công khai RSA có thể dùng làmsơ đồ chữ kí số, Xem hình 6.1. Như vậy, Bob kí bức đIửn x dùng qui tắc giảI mã RSA là dk,. Bob làngười tạo ra chữ kí vì dk = sigk là mật. Thuật toán xác minh dùng qui tắcmã RSA ek. Bất kì ai củng có xác minh chữ kí vi ek được công khai. Chú ý rằng, ai đó có thể giả mạo chữ kí của Bob trên một bức điện“ ngẩu nhiên” x bằng cách tìm x=ek(y) với y nào đó; khi đó y= sigk(x). Mộtpháp xung quanh vấn đề khó khăn này là yêu cầu bức điện chưa đủ phầndư để chữ kí giả mạo kiểu này không tương ứng với bức điện đây nghĩalà x trừ một xác suất rất bé. Có thể dùng các hàm hash trong việc kết nốivới các sơ đồ chữ kí số sẽ loại trừ được phương pháp giả mạo này (cáchàm hash được xét trong chương 7). Hình 6.1 sơ đồ chữ kí RSA Chon=pq,pvàqlàcácsốnguyêntố.Cho p=a=Znvàđịnhnghĩap={(n,p,q,a,b):=n=pq,p vàqlànguyêntố,ab ≡ 1(mod( φ (n)))}.Cácgiá trịnvàblàcôngkhai,tađịngnghĩa: sigk(x)=xamodn và verk(x,y)=true⇔x ≡ yb(modn) (x,y ∈ Zn) Cuối cùng, ta xét tóm tắt các kết hợp chữ kí và mã khoá công khai.Giả sử rằng, Alice tính toán chư kí của ta y= sigAlice(x) và sau đó mã cả xvà y bằng hàm mã khoá công khai eBob của Bob, khi đó cô ta nhận đượcz = eBob(x,y). Bản mã z sẽ được truyền tới Bob. ...