Bài giảng Mật mã ứng dụng: Mã dòng - Đại học Bách khoa Hà Nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

9
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Mật mã ứng dụng: Mã dòng" trình bày các nội dung chính sau đây: Cách tiếp cận của mật mã; Mật mã khóa đối xứng; One-Time Pad; Mã dòng RC4; Phép toán XOR;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Mật mã ứng dụng: Mã dòng - Đại học Bách khoa Hà Nội

Mật mã ứng dụng Mã dòng 1 / 34
Tài liệu • Khóa học "Computer and Network Security"của Ron Rivest • Khóa học "Crypto 1"của Dan Boneh 2 / 34
Nội dung 1 Mã hóa 2 One-time Pad 3 Mã dòng
Mã hóa Mục tiêu: Đảm bảo tính bí mật cho các thông điệp được gửi đi (hoặc lưu trữ). Nhân vật tham gia trò chơi: • Alice, Bob là người “tốt” • Eve là kẻ “nghe trộm”, “tấn công” Kênh truyền không an toàn Alice Lắng nghe Sửa đổi Bob Eve 4 / 34
Cách tiếp cận của mật mã Kênh truyền không an toàn Alice Lắng nghe Sửa đổi Bob Eve • Bob biết khóa K mà Eve không biết. • Alice có thể mã hóa thông điệp M sao cho người biết khóa K có thể giải mã. • Eve có bản mã, nhưng không biết thông tin gì về M . 5 / 34
Mật mã khóa đối xứng Alice & Bob đã có chung khóa chia sẻ Thuật toán: K ← Gen(1λ ) sinh khóa độ dài λ C ← Enc(K, M ) mã hóa thông điệp M với khóa K, kết quả là bản mã C M = Dec(K, C) giải mã C dùng khóa K để lấy được M . Thực hiện: • Ai đó (có thể là Alice hoặc Bob) tính K ← Gen(1λ ). • Đảm bảo rằng Alice & Bob cả hai đều có K (và Eve không có) (Làm thế nào !?) 6 / 34
Mật mã khóa đối xứng Trao đổi thông tin C ← Enc(K, M ) M = Dec(K, C) C ← Enc(K, M ) K K Alice Lắng nghe Bob Eve 7 / 34
Thế nào là an toàn? Mục tiêu an toàn: Không phân biệt được bản mã hay còn gọi là an toàn ngữ nghĩa • Eve không thể phân biệt được Enc(K, M1 ) với Enc(K, M2 ) kể cả khi chị ta biết (hoặc chọn) M1 và M2 có cùng độ dài. Các kiểu tấn công: • Biết bản mã • Biết một số cặp bản mã/bản rõ • Chọn bản rõ • Chọn bản mã • ... 8 / 34
Nội dung 1 Mã hóa 2 One-time Pad 3 Mã dòng
One-Time Pad hay OTP • Vernam 1977. Bằng phát minh. • Thông điệp, khóa, và bản mã có cùng độ dài (λ bit). • Khóa K cũng được gọi là pad; nó là ngẫu nhiên và chỉ biết bởi Alice & Bob. 10 / 34
Nhắc lại: Phép toán XOR XOR của hai xâu trên {0, 1}n là tổng từng bit theo mod 2. x y ⊕ 0 0 0 101100 0 1 1 ⊕ 011010 1 0 1 110110 1 1 0 11 / 34
Một tính chất quan trọng của XOR Định lý Xét Y là một biến ngẫu nhiên trên {0, 1}n , và xét X là một biến ngẫu nhiên đều trên {0, 1}n . Khi đó Z := X ⊕ Y là biến ngẫu nhiên đều trên {0, 1}n . Chứng minh. Khi n = 1, ta có: X Y Pr Y Pr X Pr 0 0 p0 /2 0 p0 0 1/2 0 1 p1 /2 1 p1 1 1/2 1 0 p0 /2 1 1 p1 /2 12 / 34
Mã hóa OTP • Enc: Biểu diễn thông điệp như xâu nhị phân và cộng theo mod 2 với khóa. m = 101100.. ⊕ k = 011010.. c = 110110.. • Dec: Giống như mã hóa, chỉ cộng với k. (mi ⊕ ki ) ⊕ ki = mi ⊕ (ki ⊕ ki ) = mi ⊕ 0 = mi 13 / 34
An toàn theo lý thuyết thông tin Định nghĩa Một hệ mã (E, D) trên ( , , ) là bí mật tuyệt đối nếu: ∀m0 , m1 ∈ , |m0 | = |m1 | và ∀c ∈ : Pr[E(k, m0 ) = c] = Pr[E(k, m1 ) = c] với k lấy ngẫu nhiên đều trong . Hệ quả là: • Cho bản mã ta không thể biết thông điệp là m0 hay m1 . • Kẻ tấn công mạnh tùy ý cũng không lấy được thông tin gì về bản rõ từ bản mã. • Tuy vậy, hệ này chỉ chống được tấn công “biết bản mã”. 14 / 34
Bổ đề OTP là bí mật tuyệt đối Chứng minh. Với mọi m, c ta có #{k ∈ thỏa mãn E(k, m) = c} Pr[E(k, m) = c] = # Vậy thì, nếu với mọi m, c #{k ∈ thỏa mãn E(k, m) = c} = const thì hệ mã là bí mật tuyệt đối. 15 / 34
Câu hỏi Xét m ∈ và c ∈ . Có bao nhiêu khóa OTP ánh xạ m thành c? • Không có khóa nào • 1 khóa • 2 khóa • Phụ thuộc vào m. 16 / 34
Tin xấu Định lý Tính bí mật tuyệt đối =⇒ | |≥| | Có nghĩa rằng, ta chỉ có hệ mã bí mật tuyệt đối khi độ dài khóa lớn hơn hoặc bằng độ dài thông điệp. Không dùng được trong thực tế!!! 17 / 34
Nhược điểm của OTP Khó khăn khi sử dụng OTP Người dùng phải . • sinh ra các khóa bí mật lớn, • chia sẻ chúng an toàn, • giữ chúng bí mật, • tránh sử dụng lại khóa: c1 ⊕ c2 = (m1 ⊕ k) ⊕ (m2 ⊕ k) = m1 ⊕ m2 từ đó bạn có thể suy ra m1 , m2 . 18 / 34
Tính xác thực của OTP Định lý. OTP có thể bị giả mạo. (Có nghĩa rằng, thay đổi các bit của bản mã sẽ làm cho các bit tương ứng của bản mã bị thay đổi) OTP không cho phép xác thực nội dung thông điệp hay cho phép chống lại việc sửa đổi thông điệp. 19 / 34
Bài tập Giả sử bạn biết mã hóa của thông điệp “attack at dawn” dùng one time pad encryption là 6c73d5240a948c86981bc294814d (bản rõ ở dạng mã ASCII 8-bit và bản mã được viết ở dạng hexa). Bản mã của thông điệp "attack at dusk"với cùng khóa OTP là gì? 20 / 34