Mật mã cổ điển- Chương 6

Tham khảo tài liệu mật mã cổ điển- chương 6, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Mật mã cổ điển- Chương 6 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 được gọi là chữ kí số ). Chữ kí viếttay thông thường trên tàI liệu thường được dùng đểxác người kí nó. Chữ kí được dùng hàng ngày chẳnghạn như trên mộ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ửnlưu dưới dang đIên từ. 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ươngtrình này nghiên cứu vàI sơ đồ chữ kí. Ta sẽ thảoluận trên một và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ớichữ kí thông thường, nó là một phần vật lý của tàIliệ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ùngphảI ”không nhìn thấy” theo cách nào đó trên bứcđIửn. Thứ hai là vấn đề về kiểm tra. Chữ kí thôngthường được kiểm tra bằng cách so sánh nó với cácchữ kí xác thực khác. ví dụ, ai đó kí một tấm sécđể mua hàng, người bán phảI so sánh chữ kí trênmả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ảI là phươg phápan 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ánkiể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ường bản copy tàI liệu được kí băng chữkí số đồng nhất với bản gốc, còn copy tà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ộtbứ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ộtlầ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ị dunglại. Một sơ đồ chữ kí số thường chứa hai thànhphầ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ánxác minh công khai ver. Khi cho trước cặp (x,y),thuật toán xác minh có giá trị TRUE hay FALSE tuỳthuộc vào chữ kí được thực như thế nào. Dưới đâylà định ngh ĩ 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ện dướ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ột thuật toán xác minh verk∈ V. Mỗisigk : P → A và verk: P× a →{ true,false} là những hàmsao cho mỗi bức đIửn x∈ P và mối chữ kí y∈ a thoảmãn phươ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áchàm thơì than đa thức. Verk sẽ là hàm công khaisigk là mật. Không thể dể dàng tính toán để giả mạochữ kí của Bob trên bức điện x. Ngh ĩ a là x chotrước, chỉ có Bob mới có thể tính được y để verk =True. Một sơ đồ chữ kí không thể an toàn vô đIêukiện vì Oscar có thể kiểm tra tất cả các chữ số ycó thể có trên bức đIửn x nhờ dung thuât toán vercông khai cho đến khi anh ta tìm thấy một chữ kíđúng. Vi thế, nếu có đủ thời gian. Oscar luôn luôncó thể giả mạo chữ kí của Bob. Như vậy, giống nhưtrường hợp hệ thống mã khoá công khai, mục đích củachúng ta là tìm các sơ đồ chữ kí số an toan về mặttính toán. Xem thấy rằng, hệ thống mã khoá công khai RSAcó thể dùng làm sơ đồ chữ kí số, Xem hình 6.1. Như vậy, Bob kí bức đIửn x dùng qui tắc giảImã 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ắc mã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ủaBob trên một bức điện “ ngẩu nhiên” x bằng cáchtì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ần dư để chữ kí giả mạo kiểu nàykhông tương ứng với bức điện đây ngh ĩ a là x trừmột xác suất rất bé. Có thể dùng các hàm hash trongviệc kết nối với các sơ đồ chữ kí số sẽ loại trừđược phương pháp giả mạo này (các hàm hash được xéttrong chương 7). Hình 6.1 sơ đồ chữ kí RSA Cho n= pq, p và q là các số nguyên tố. Cho p =a= Zn và định nghĩa p= {(n,p,q,a,b):=n=pq,p và q là nguyên tố, ab ≡ 1(mod( φ (n))) }. Các giá trị n và b là công khai, ta địng nghĩa : sigk(x)= xa mod n và verk (x,y)= true ⇔ x ≡ yb (mod n) (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ánchư kí của ta y= sigAlice(x) và sau đó mã cả x và ybằng hàm mã khoá công khai eBob của Bob, khi đó côta nhận được z = eBob(x,y). Bản mã z sẽ đượctruyền tới Bob. Khi Bob nhận được z, anh ta sẽtrước hết sẽ giảI mã hàm dBob để nhận được (x,y).Sau đó anh ta dung hàm xác minh công khai của Aliceđể kiểm tra xem verAlice(x,y) có bằng True hay không. Song nếu đầu tiên Alice mã x rồi sau đó mớikí tên bản mã nhận được thì sao?. Khi đó cô tính : y= sigAlice(eBob(x)).Alice sẽ truyền cặp (z,y) tới Bob. Bob sẽ giải mãz, nhận x và sau đó xác minh chữ kí y trên x nhờdùng verAlice. Một vấn đề tiểm ẩn trong biện pháp nàylà nếu Oscar nhận được cặp (x,y) kiểu này, được tacó thay chữ kí y của Alice bằng chữ kí của mình. y, = sigOscar(eBob(x)).(chú ý rằng,Oscar có thể kí bản mã eBob(x) ngay cảkhi anh ta không biết bản rõ x). Khi đó nếu Oscartruyền(x, y’ ) đến Bob thì chữ kí Oscar được Bobxác minh bằng verOscar và Bob có thể suy ra rằng, bảnrõ x xuất phát từ Oscar. Do khó khăn này, hầu hếtngười sử dụng được khuyến nghị nếu kí trước khi mã.6.2 sơ đồ chữ kí ELGAMAL Sau đây ta sẽ mô tả sơ đồ chữ kí Elgamal đãtừng dưới thiệu trong bài báo năm 1985. Bản cả ti ...