Sơ đồ chữ ký một lần

Trường Đại Học Dân Lập Hải Phòng Khoa Công Nghệ Thông Tin ĐỀ TÀI: SƠ ĐỒ CHỮ KÝ MỘT LẦN GVHD:Trần Ngọc Thái SVTH:Trần Trung Hiếu Nguyễn Văn Tân Tài liệu Tham Khảo How to construct optimal one-time signatures Kemal Bicakci a,*, Gene Tsudik b, Brian Tung c a Informatics Institute, Middle East Technical University, Ankara 06531, Turkey b Computer Science Department, University of California, Irvine, CA 92612, USA c USC Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA 90292, USA Received 25 March 2002; received in revised form 23 April 2003; accepted 24 April 2003 Responsible Editor: S.F. Wu Tóm Tắt Chữ ký 1 lần OTS (one time signature ) cung cấp 1 sự thay thế cho chữ ký điện tử dựa trên mã hóa khóa công khai . Sự bảo mật của OTS phụ thuôc vào độ mạnh của hàm 1 chiều OWF (one Way funtion) mà không phụ thuộc vào độ khó của các vấn đề toán học . Phát triển 1 giải thuật tối ưu cho OTS ------------------------------- Các từ khóa: One-time signature; Digital signature; On-line/off-line digital signature; Hash function; Combinatorics Giới Thiệu Mạng Internet và các mạng hiện đại khác ngày càng phát triển và có tính mở cao Truyền thông qua mạng cũng có sự thay đổi về cấu trúc :từ việc chỉ chuyền các tệp text thì giờ đây là các tệp tin dữ liêu. Phức tạp . Những sự tiến triển này làm cho sự bảo toàn dữ liệu và tính riêng tư ngày càng được quan tâm ,đặc biệt là tính bảo mật và tính hiệu quả . Các phương thức chữ ký điện tử truyền thống dựa trên mã hóa công khai là không vững chắc ,có thể bị phá vỡ bởi khả năng của máy tính . OTS cung cấp 1 phương pháp có thẻ thay thế chữ ký sử dụng khóa công khai .Không giống như chữ ký dựa trên mã hóa khóa công khai ,OTS chỉ dựa trên “ hàm 1 chiều”(OWFs) .Do vậy nó không đòi hỏi việc tính toán số học phức tạp trong việc tạo chữ ký và xác minh . Trên thực tế ,sự bảo mật của chữ ký điện tử truyền thống dựa trên 2 nhân tố :toán học và các “message digest funtions” là các hàm dùng để tạo ra các digest có kích thước cố định từ dữ liệ đầu vào bất kỳ .(Hàm này phải là 1 chiều và chịu đươc xung đột) .Sử dụng OTS cho phép ta loại trừ nhân tố đầu tiên Giới Thiệu OTS đã được đề cập đến từ hơn 2 thập ký trước .Ban đầu được phát triển bởi Lamport ,sau đó là Merkle và Winternitz . Bleichenbacher chính thức khái niệm OTS sử dụng một đồ thị có hướng (DAGS) TH đơn giản nhất :Người ký lấy 1 số ngẫu nhiên r ,phục vú cho việc tạo khóa 1 lần . Người ký sau đó bí mật phân bổ 1 khóa h(r) .Với h(.) là 1 OWF .Khóa này đôi khi được xem như là 1 giá trị tin cậy và sau này được sử dụng để người xác minh xác nhận chữ ký . Một chữ ký được xây dựng bằng cách cho biết khóa bí mật .Người xác nhận ,nhận được r’ (có thể giống hoặc khác r) .Tính h(r’) .Nếu h(r’)=h(r) thì chữ ký đó là hợp lệ .Trên thực tế cho phép việc ký với 1bit có thể đoán trước được .và cung cấp chứng thực gốc .Để ký 1 bit bất kỳ ,yêu cầu 2 số ngẫu nhiên {r0 ,r1} .Theo cách này cả h(r0)và h(r1) đã được phân bổ trước .Nhưng tối đa 1 trong 2 số đó được tiết lộ như là 1 phần của chữ ký .Cặp (r0,h(r0)) được coi như là 1 chữ ký của thông điếp “0”,trong khi (r1,h(r1)) là 1 chữ ký của thông điệp “1” . Merkle mở rộng phương pháp này cho phép ký trên 1 thông điệp có độ dài bất kỳ .Việc này được bắt đầu bằng hàm chuyển thông điệp thành các digest có đọ dài cố định ,theo cách thông thường ở chữ ký mã hóa khóa công khai . Giới Thiệu Tuy nhiên thay vì biến đổi cả khối này với 1 khóa bí mật ,mỗi bit có 1 chữ ký được liên kết và chữ ký của cả thông điệp được coi như là sự ghép nối của các OTS cho mỗi ”1” bit trên thông điệp cùng với 1 vài giá trị thêm vào để chắc chắn rằng thứ tự của các bit kia không tự nó thay đổi . Cần nói rõ là giải thuật này yêu cầu các khóa công khai cho các OTS phải được phân phối trong 1 chế độ bảo mật . Trong công thưc này ,các chữ ký sẽ dài hơn .Tuy nhiên độ dài bổ xung ,từng là mối quan tâm của hơn 2 thập kỷ trước bây giờ đã không còn đáng ngại với sự phát triển về tốc độ của mạng & Modem . Trên thực tế chưa có 1 đánh giá nào về khả năng của OTS được thực hiện .Việc xây dựng OTS tối ưu là làm tăng kích thước của thông điệp(được ký) và làm giảm số lượng của các khối ngẫu nhiên được dùng để tạo OTS Kết quả đó dẫn chúng ta đến đến 1 cách xây dựng OTS tối ưu ,mà hiệu quả tương ứng với số lượng nhỏ nhất của các thao tác trong OWF được sử dụng trong cả việc tạo và xác minh chữ ký . Cấu trúc OTS của Mercle Gán thông điệp đầu vào có kích thước là b.Đặt s=(└ logb ┘+ 1) và n=b+s .Người ký tạo 1 vectơ khóa bí mật có kích thước (b+2s) của 1 dãy số ngẫu nhiên . R={R1,…,Rb,L1,0,L1,1,…,Ls,0,Ls,1} Người ký sau đó áp dụng OWF cho mỗi phần tử của vector khóa bí mật và phân phát kết quả của vectơ kết quả khóa công khai tới người cần xác minh . H(R)= Sau đó để ký 1 thông điệp m (có kích thước k bit) ,người ký đếm số lượng bit 1 trong m ,mã hóa số bit đó thành 1 xâu (s bit) và bổ xung chúng vào m . Kết quả là 1 thông điệp m0 (kích thước n bit ) .Hiện tại chữ ký SIG(m) được xây dựng như dưới đây : for(i=1;i2b Tổng quát về chữ ký 1 lần Hoặc sau khi lấy logarit cơ số 2 cả 2 vế : Với b=128,n ít nhất phải là 132 và mỗi tập con có thể nhỏ đến 64 .Từ đó C(132,164)>2128 Tổng quát về chữ ký 1 lần Chú ý là chúng ta có thể tùy ý tăng n và giảm p hoặc ngược lại miễn là thỏa mãn C(n,p)>2b Và người ký và người xác nhận thống nhất trước về giá trị của n,p