5
Các tính chất của một hệ mật mã
•Nếu một hệ mật có thể sử dụng được trong thực tế thì nó
phải thoả mãn một số tính chất nhất định:
1. Các hàm mã hoá e
K
và các hàm giải mã d
K
phải có
khả năng tính toán được một cách hiệu quả.
2. Đối phương dựa trên xâu bản mã phải không có khả
năng xác định khoá k đã dùng hoặc không có khả năng xác
định được xâu bản rõ x.
6
Số học modulo m
•Giả sử a và b là các số nguyên và m là một số nguyên
dương. Khi đóta viết a ≡ b (mod m) nếu m chia hết cho
(b-a). Mệnh đề a ≡ b (mod m) được gọi là "a đồng dư với
b theo modulo m".
• Phân tích a và b theo m như sau:
¾a = q
1
m + r
1
và b = q
2
m + r
2
trong đó0 ≤ r
1
≤ m-1 và 0
≤ r
2
≤ m-1. (chú ý: r
1
và r
2
là không âm)
¾Dễ dàng thấy rằng a ≡ b (mod m) khi và chỉ khi r
1
= r
2
.
Ta sẽ dùng ký hiệu a mod m (không dùng các dấu
ngoặc). Như vậy: a ≡ b (mod m) khi và chỉ khi a mod m
= b mod m.
¾Nếu thay a bằng a mod m thì ta nói rằng a được rút gọn
theo modulo m.
7
Số học modulo m (tiếp)
• Nhận xét: Nhiều ngôn ngữ lập trình của máy tính xác định
a mod m là phần dư trong dải -m+1, ., m-1 có cùng dấu
với a.
•Vídụ -17 mod 7 sẽ là -3, tuy nhiên theo định nghĩa ở trên
thì -17 mod 7 = (-3)*7 +4 (4 là đối của -3 theo phép cộng:
4= 7+(-3)).
•Bây giờ ta có thể định nghĩa số học modulo m - Z
m
như
sau: Z
m
là tập hợp {0,1,. . .,m-1} và được trang bị hai phép
toán cộng và nhân. Việc cộng và nhân trong Z
m
được thực
hiện giống như cộng và nhân các số nguyên ngoại trừ một
điểm là các kết quả được rút gọn theo modulo m.
8
Số học modulo m – ví dụ
•Vídụ tính 11× 13 trong Z
16
tương tự như với các số
nguyên ta có:
–11 ×13 = 143.
– Để rút gọn 143 theo modulo 16, ta thực hiện phép chia
bình thường: 143 = 8 × 16 + 15,
–Bởi vậy 143 mod 16 = 15 trong Z
16
.
•
9
Số học modulo m–tính chất của các phép toán
1. Phép cộng là đóng, tức với bất kì a,b ∈ Zm ,a +b ∈ Zm
2. Phép cộng là giao hoán, tức là với a,b bất kì ∈ Zm: a+b = b+a
3. Phép cộng là kết hợp, tức là với bất kì a,b,c ∈ Zm: (a+b)+c =
a+(b+c)
4. 0 là phần tử đơn vị của phép cộng, có nghĩa là với a bất kì ∈ Zm:
a+0 = 0+a = a
5. Phần tử nghịch đối của phép cộng của phần tử bất kì (a ∈ Zm ) là
m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với bất kì a ∈ Zm .
6. Phép nhân là đóng, tức là với a,b bất kì ∈ Zm, ab ∈ Zm .
7. Phép nhân là giao hoán, nghĩa là với a,b bất kì ∈ Zm, ab = ba
8. Phép nhân là kết hợp, nghĩa là với a,b,c ∈ Zm , (ab)c = a(cb)
9. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a ∈ Zm: a×1 =
1×a = a
10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với
a,b,c ∈ Zm , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac)
10
Số học modulo m – nhận xét
•Vìphần tử đối của phép cộng tồn tại trong Z
m
nên ta cũng
có thể thực hiện phép trừ trong Z
m
. Ta định nghĩa a-b
trong Z
m
là a+m-b mod m. Một cách tương đương có thể
tính số nguyên a-b rồi rút gọn theo modulo m.
•Vídụ : Để tính 11-18 trong Z
31
:
– Ta tính 11+13 mod 31 = 24.
– Hoặc, có thể lấy 11-18 được -7 rồi sau đó tính -7 mod
31 = 24.
11
Mã dịch vòng (shift cipher)
•Hệ mật mã dịch vòng:
– P = C = K = Z
26
–Với 0 ≤ k ≤ 25 , các hàm mã và giải mã như sau:
•e
k
(x) = x +k mod 26
•vàd
k
(y) = y-k mod 26
•(x,y ∈ Z
26
)
– Nhận xét: Trong trường hợp K = 3, hệ mật mã thường
được gọi là mã Caesar đã từng được Julius Caesar sử
dụng.
12
Mã dịch vòng (shift cipher)
• Ta sẽ sử dụng MDV (với modulo 26) để mã hoá một văn
bản tiếng Anh thông thường bằng cách thiết lập sự tương
ứng giữa các kí tự và các thặng dư theo modulo 26 như
sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25. Vì phép tương ứng này
còn dùng trong một vài ví dụ nên ta sẽ ghi lại để còn tiện
dùng sau này, ta có bảng ánh xạ chi tiết sau:
13
Mã dịch vòng (shift cipher) - ví dụ
•Giả sử khoá cho mã dịch vòng là k = 11 và bản rõ là:
wewillmeetatmidnight
• Trước tiên biến đổi bản rõ thành dãy các số nguyên nhờ
dùng phép tương ứng trên. Ta có:
w-22 e-4 w-22 i-8 l-11 l-11 m-12 e-4 e-4 t-19
a-0 t-19 m-12 i-8 d-3 n-13 i-8 g-6 h-7 t-19
•sau đócộng 11 vào mỗi giá trị rồi rút gọn tổng theo
modulo 26 (công thức e
k
(x) = x +k mod 26):
7 15 7 19 22 22 23 15 15 4
114231914241917184
•Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu
được bản mã sau: HPHTWWXPPELEXTOYTRSE
14
Mã dịch vòng (shift cipher) - ví dụ
•Nhận xét: Trong ví dụ trên, ta đã dùng các chữ in hoa cho
bản mã, các chữ thường cho bản rõ để tiện phân biệt.
•Giải mã bản mã này:
–Bob sẽ biến đổi bản mã thành dãy các số nguyên rồi trừ
đi giá trị cho 11 và rút gọn theo modulo 26 (công thức
d
k
(y) = y-k mod 26)
–Cuối cùng biến đổi lại dãy này thành các ký tự.
Không có nhận xét nào:
Đăng nhận xét