1. Đnh nghĩa v Mt m (Cipher)
Mt mt m bao gm hai thut to n: thut to n m h a v thut to n gii m . Nhưng ch nh x c hơn, mt m đưc đnh nghĩa tr
n mt b ba yếu t:
1. Kh ng gian kh a (Key Space, K): Đy l tp hp tt c c c kh a c th, c n gi l "key space".
2. Kh ng gian bn r (Message Space, M): Đy l tp hp tt c c c bn r (messages) c th.
3. Kh ng gian bn m (Ciphertext Space, C): Đy l tp hp tt c c c bn m (ciphertexts) c th.
B ba n y v cơ bn đnh nghĩa m i trưng m trong đ mt m hot đng. Bn th n mt m l mt cp c c thut to n hiu
qu: E v D.
Thut to n m h a E: Nhn đu v o l mt kh a k v mt bn r m, xut ra bn m c.
Thut to n gii m D: Nhn đu v o l mt kh a k v mt bn m c, xut ra bn r m.
Thut to n E thc hin m h a bng c ch nhn mt kh a v mt bn r , sau đ xut ra bn m . Ngưc li, thut to n D thc
hin gii m bng c ch nhn mt kh a v mt bn m , sau đ xut ra bn r .
2. T nh nht qu n (Consistency) ca mt m
Điu kin duy nht m c c thut to n n y phi tha m n l t nh nht qu n, hay c n gi l t nh đng (correctness). Điu n y c
nghĩa l vi mi bn r m trong kh ng gian bn r v mi kh a k trong kh ng gian kh a, nếu t i m h a th ng đip m bng kh a k
v sau đ gii m bng c ng kh a k, t i s nhn li đng bn r ban đu.
C th:
Điu n y c nghĩa l nếu bn m h a bn r m bng kh a k v sau đ gii m kết qu đ bng c ng kh a k, bn phi nhn li đng bn
r m ban đu. Nếu kh ng, bn s kh ng th gii m bn m th nh bn r ban đu đưc.
3. Hiu qu (Eciency)
T i đ đt t "hiu qu" trong ngoc k p v kh i nim n y c th đưc hiu kh c nhau đi vi mi ngưi.
Nếu bn thi n v lý thuyết, hiu qu c nghĩa l chy trong thi gian đa thc (polynomial me) theo k ch thưc ca
đu v o. C c thut to n E v D phi chy trong thi gian đa thc theo k ch thưc ca c c đu v o ca ch ng.
Nếu bn thi n v thc tế, hiu qu c th c nghĩa l chy trong mt khong thi gian c th. V d, thut to n E c th
cn phi m h a dưi mt ph t cho mt gigabyte d liu.
4. Mt m One-Time Pad (OTP)
B y gi, h y chuyn sang v d đu  n v mt mt m an to n, đ l One-Time Pad, đưc thiết kế bi Vernam v o đu thế kỷ
20.
Đnh nghĩa kh ng gian ca One-Time Pad:
Thut to n m h a v gii m :
1. M h a: Bn m c đưc to ra bng c ch thc hin ph p XOR gia kh a k v bn r m:
2. Gii m : Bn r m đưc kh i phc bng c ch thc hin ph p XOR gia bn m c v kh a k:
V d minh ha:
Gi s bn c bn r m = 0110111 v kh a k = 1011001.
M h a:
Gii m :
Trong v d n y, ph p XOR gia bn m v kh a đ kh i phc li đng bn r ban đu.
5. T nh bo mt ho n ho (Perfect Secrecy)
Mt mt m c bo mt ho n ho (perfect secrecy) nếu biết bn m m kh ng th biết đưc bt kỳ th ng n g v bn r .
Đnh nghĩa bo mt ho n ho:
Mt m E, D đưc gi l c bo mt ho n ho nếu vi mi bn r m0, m1 trong kh ng gian bn r v bn m c trong kh ng gian
bn m :
vi k đưc chn ngu nhi n theo ph n phi đu tr n kh ng gian kh a K.
Chng minh bo mt ho n ho cho One-Time Pad:
Vi One-Time Pad, ch c mt kh a k duy nht tha m n:
V vy, x c sut đ m h a mt bn r bt kỳ th nh bn m c l như nhau cho mi bn r :
6. Nhưc đim ca One-Time Pad
Mc d One-Time Pad c bo mt ho n ho, n kh ng thc tế v :
1. Kh a phi d i bng bn r : Alice v Bob cn trao đi mt kh a d i bng th ng đip tc khi giao ếp. Nếu c phương
thc an to n đ trao đi kh a, h c th d ng phương thc đ đ trao đi trc ếp th ng đip.
2. Kh a ch d ng mt ln: Nếu s dng li kh a cho hai th ng đip kh c nhau, t nh bo mt s b ph v.
ế
7. Đnh lý ca Shannon v bo mt ho n ho
Claude Shannon chng minh rng mt mt m c bo mt ho n ho th sng kh a phi ln hơn hoc bng sng
bn r :
8. Kết lun
Mt m One-Time Pad c bo mt ho n ho nhưng kh ng thc tế. Trong c c b i hc ếp theo, ch ng ta s t m hiu c ch ci
thin mt m đ va đm bo bo mt cao va c th ng dng thc tế.

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ế.