





Preview text:
1. Định nghĩa về Mật m (Cipher)
Một mật m bao gồm hai thuật to n: thuật to n m h a v thuật to n giải m . Nhưng ch nh x c hơn, mật m được định nghĩa tr n một bộ ba yếu tố:
1. Kh ng gian kh a (Key Space, K): Đy l tập hợp tất cả c c kh a c thể, c n gọi l "key space".
2. Kh ng gian bản r (Message Space, M): Đy l tập hợp tất cả c c bản r (messages) c thể.
3. Kh ng gian bản m (Ciphertext Space, C): Đy l tập hợp tất cả c c bản m (ciphertexts) c thể.
Bộ ba n y về cơ bản định nghĩa m i trường m trong đ mật m hoạt động. Bản th n mật m l một cặp c c thuật to n hiệu quả: E v D.
Thuật to n m h a E: Nhận đầu v o l một kh a k v một bản r m, xuất ra bản m c.
Thuật to n giải m D: Nhận đầu v o l một kh a k v một bản m c, xuất ra bản r m.
Thuật to n E thực hiện m h a bằng c ch nhận một kh a v một bản r , sau đ xuất ra bản m . Ngược lại, thuật to n D thực
hiện giải m bằng c ch nhận một kh a v một bản m , sau đ xuất ra bản r .
2. T nh nhất qu n (Consistency) của mật m
Điều kiện duy nhất m c c thuật to n n y phải thỏa m n l t nh nhất qu n, hay c n gọi l t nh đng (correctness). Điều n y c
nghĩa l với mọi bản r m trong kh ng gian bản r v mọi kh a k trong kh ng gian kh a, nếu t i m h a th ng điệp m bằng kh a k
v sau đ giải m bằng c ng kh a k, t i sẽ nhận lại đng bản r ban đầu. Cụ thể:
Điều n y c nghĩa l nếu bạn m h a bản r m bằng kh a k v sau đ giải m kết quả đ bằng c ng kh a k, bạn phải nhận lại đng bản
r m ban đầu. Nếu kh ng, bạn sẽ kh ng thể giải m bản m th nh bản r ban đầu được.
3. Hiệu quả (Efficiency)
T i đ đặt từ "hiệu quả" trong ngoặc k p v kh i niệm n y c thể được hiểu kh c nhau đối với mỗi người.
Nếu bạn thi n về lý thuyết, hiệu quả c nghĩa l chạy trong thời gian đa thức (polynomial time) theo k ch thước của
đầu v o. C c thuật to n E v D phải chạy trong thời gian đa thức theo k ch thước của c c đầu v o của ch ng.
Nếu bạn thi n về thực tế, hiệu quả c thể c nghĩa l chạy trong một khoảng thời gian cụ thể. V dụ, thuật to n E c thể
cần phải m h a dưới một ph t cho một gigabyte dữ liệu.
4. Mật m One-Time Pad (OTP)
B y giờ, h y chuyển sang v dụ đầu ti n về một mật m an to n, đ l One-Time Pad, được thiết kế bởi Vernam v o đầu thế kỷ 20.
Định nghĩa kh ng gian của One-Time Pad: ả ấ ả ỗ ị ộ ố ị ả ố ớ ả ồ ấ ả ỗ ị ộ ỗ ị ẫ ộ ớ ả
Thuật to n m h a v giải m :
1. M h a: Bản m c được tạo ra bằng c ch thực hiện ph p XOR giữa kh a k v bản r m:
2. Giải m : Bản r m được kh i phục bằng c ch thực hiện ph p XOR giữa bản m c v kh a k: V dụ minh họa:
Giả sử bạn c bản r m = 0110111 v kh a k = 1011001. M h a: Giải m :
Trong v dụ n y, ph p XOR giữa bản m v kh a đ kh i phục lại đng bản r ban đầu.
5. T nh bảo mật ho n hảo (Perfect Secrecy)
Một mật m c bảo mật ho n hảo (perfect secrecy) nếu biết bản m m kh ng thể biết được bất kỳ th ng tin g về bản r .
Định nghĩa bảo mật ho n hảo:
Mật m E, D được gọi l c bảo mật ho n hảo nếu với mọi bản r m0, m1 trong kh ng gian bản r v bản m c trong kh ng gian bản m :
với k được chọn ngẫu nhi n theo ph n phối đều tr n kh ng gian kh a K.
Chứng minh bảo mật ho n hảo cho One-Time Pad:
Với One-Time Pad, chỉ c một kh a k duy nhất thỏa m n:
V vậy, x c suất để m h a một bản r bất kỳ th nh bản m c l như nhau cho mọi bản r : ớ ỉ ả ẻ ấ ể ế ệ ả ầ
6. Nhược điểm của One-Time Pad
Mặc d One-Time Pad c bảo mật ho n hảo, n kh ng thực tế v :
1. Kh a phải d i bằng bản r : Alice v Bob cần trao đổi một kh a d i bằng th ng điệp trước khi giao tiếp. Nếu c phương
thức an to n để trao đổi kh a, họ c thể d ng phương thức đ để trao đổi trực tiếp th ng điệp.
2. Kh a chỉ d ng một lần: Nếu sử dụng lại kh a cho hai th ng điệp kh c nhau, t nh bảo mật sẽ bị ph vỡ.
7. Định lý của Shannon về bảo mật ho n hảo
Claude Shannon chứng minh rằng một mật m c bảo mật ho n hảo th số lượng kh a phải lớn hơn hoặc bằng số lượng bản r : 8. Kết luận
Mật m One-Time Pad c bảo mật ho n hảo nhưng kh ng thực tế. Trong c c b i học tiếp theo, ch ng ta sẽ t m hiểu c ch cải
thiện mật m để vừa đảm bảo bảo mật cao vừa c thể ứng dụng thực tế.