Download miễn phí Giáo trình Mật mã hóa
Tất cả các hệ mật thảo luận ở trên ít nhiều đều xoay quanh phép
thaythế: các ký tự của bản rõ được thay thế bằng các ký tự khác trongbản
mã. ýtưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ
thay đôỉi vị trí của chúng bằng cách sắp xếp lại các ký tự này. MHV (còn
được gọi là mã chuyển vị) đã được dùng từ hàng trăm năm nay. Thật ra thì sự
phân biệt giữa MHV và MTT đã được Giovani Porta chỉ ra từ 1563. Định
nghĩa hình thức cho MHV được nêu ra trên hình 1.7.
Không giống nhưMTT, ở đây không có các phép toán đại số nào cần
thực hiện khi mã hoá và giải mã nên thích hợp hơn cả là dùng các ký tự mà
không dùng các thặng dưtheo modulo 26. Dưới đây là một ví dụ minh hoạ
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
=BA, thậm chí đố với ma trận vuông A và B).
Ma trận đơn vị m ì m (ký hiệu là Im ) là ma trận cấp m ì m có các số 1
nằm ở đ−ờng chéo chính và các số 0 ở vị trí còn lại. Nh− vậy ma trận đơn vị
2 ì 2 là:
Im đ−ợc gọi là ma trận đơn vị vì AIm = A với mọi ma trận cấp l ì m và ImB =B
với mọi ma trận cấp m ì n. Ma trận nghịch đảo của ma trận A cấp m ì m (
nếu tồn tại) là ma trận A-1 sao cho AA-1 = A-1A = Im . Không phải mọi ma
trận đều có nghịch đảo, nh−ng nếu tồn tại thì nó duy nhất.
Với các định nghĩa trên, có thể dễ dàng xây dựng công thức giải mã đã
nêu: Vì y = xK, ta có thể nhân cả hai vế của đẳng thức với K-1 và nhận đ−ợc:
yK-1 = (xK)K-1 = x(KK-1) = xIm = x
( Chú ý sử dụng tính chất kết hợp)
Có thể thấy rằng, ma trận mã hoá ở trên có nghịch đảo trong Z26:
vì
I2 =
1 0
0 1
11 8
3 7
-1
=
7 18
23 11
12 8
3 7
8 18
23 11
= 11ì7+8ì23 11ì18+8ì11
3ì7+7ì23 3ì18+7ì11
Vietebooks Nguyễn Hoàng Cương
Trang 17
(Hãy nhớ rằng mọi phép toán số học đều đ−ợc thực hiện theo modulo 26).
Sau đây là một ví dụ minh hoạ cho việc mã hoá và iải mã trong hệ mật
mã Hill.
Via dụ 1.5
Từ các tính toán trên ta có:
Giả sử cần mã hoá bản rõ "July". Ta có hai phần tử của bản rõ để mã hoá:
(9,20) (ứng với Ju) và (11,24) (ứng với ly). Ta tính nh− sau:
và
Bởi vậy bản mã của July là DELW. Để giải mã Bob sẽ tính
và
=
261 286
182 131
= 1 0
0 1
Giả sử khoá K =
11 8
3 7
K-1 =
7 18
23 11
(9,20)
11 8
3 7
= (99+60, 72+140) = (3,4)
(11,24)
11 8
3 7
= (121+72, 88+168) = (11,22)
(3,4)
7 18
23 11
= (9,20)
(11,22)
7 18
23 11
= (11,24)
Vietebooks Nguyễn Hoàng Cương
Trang 18
Nh− vậy Bob đã nhận đ−ợc bản đúng.
Cho tới lúc này ta đã chỉ ra rằng có thể thực hiện phép giải mã nếu K
có một nghịch đảo. Trên thực tế, để phép giải mã là có thể thực hiện đ−ợc,
điều kiện cần là K phải có nghịch đảo. ( Điều này dễ dàng rút ra từ đại số
tuyến tính sơ cấp, tuy nhiên sẽ không chứng minh ở đây). Bởi vậy, chúng ta
chỉ quan tâm tới các ma trận K khả nghich.
Tính khả nghịch của một ma trận vuông phụ thuộc vào giá trị định
thức của nó. Để tránh sự tổng quát hoá không cần thiết, ta chỉ giới hạn trong
tr−ờng hợp 2ì2.
Định nghĩa 1.5
Định thức của ma trận A = (a,i j ) cấp 2ì 2 là giá trị
det A = a1,1 a2,2 - a1,2 a2,1
Nhận xét: Định thức của một ma trận vuông cấp mm có thể đ−ợc tính theo
các phép toán hằng sơ cấp: hãy xem một giáo trình bất kỳ về đại số tuyến
tính.
Hai tính chất quan trọng của định thức là det Im = 1 và quy tắc nhân
det(AB) = det A ì det B.
Một ma trận thức K là có nghịch đảo khi và chỉ khi định thức của nó
khác 0. Tuy nhiên, điều quan trọng cần nhớ là ta đang làm việc trên Z26 . Kết
quả t−ơng ứng là ma trận K có nghịch đảo theo modulo 26 khi và chỉ khi
UCLN(det K,26) = 1.
Sau đây sẽ chứng minh ngắn gọn kết quả này.
Tr−ớc tiên, giả sử rằng UCLN(det K,26) = 1. Khi đó det K có nghịch
đảo trong Z26 . Với 1 ≤ i ≤ m, 1 ≤ j ≤ m, định nghĩa Ki j ma trận thu đ−ợc từ K
bằng cách loại bỏ hàng thứ i và cột thứ j. Và định nghĩa ma trận K* có phần
tử (i,j) của nó nhận giá trị(-1) det Kj i (K
* đ−ợc gọi là ma trận bù đại số của
K). Khi đó có thể chứng tỏ rằng:
K-1 = (det K)-1K* .
Bởi vậy K là khả nghịch.
Ng−ợc lại K có nghịch đảo K-1 . Theo quy tắc nhân của định thức
Vietebooks Nguyễn Hoàng Cương
Trang 19
1 = det I = det (KK-1) = det K det K-1
Bởi vậy det K có nghịch đảo trong Z26 .
Nhận xét: Công thức đối với ở trên không phải là một công thức tính toán có
hiệu quả trừ các tr−ờng hợp m nhỏ ( chẳng hạn m = 2, 3). Vớim lớn, ph−ơng
pháp thích hợp để tính các ma trận nghịch đảo phải dựa vào các phép toán
hằng sơ cấp.
Trong tr−ờng hợp 2ì2, ta có công thức sau:
Định lý 1.3
Giả sử A = (ai j) là một ma trận cấp 2 ì 2 trên Z26 sao cho det A =
a1,1a2,2 - a1,2 a2,1 có nghịch đảo. Khi đó
Trở lại ví dụ đã xét ở trên . Tr−ớc hết ta có:
Vì 1-1 mod 26 = 1 nên ma trận nghịch đảo là
Đây chính là ma trận đã có ở trên.
Bây giờ ta sẽ mô tả chính xác mật mã Hill trên Z26 (hình 1.6)
Hình 1.6 Mật m∙ HILL
A-1 = (det A)-1
a2,2 -a1,2
-a2,1 a1,1
det 11 8
3 7
= 11 ì 7 - 8 ì3 mod 2
= 77 - 24 mod 26 = 53 mod 26
= 1
11 8
3 7
-1
=
7 18
23 11
Cho m là một số nguyên d−ơng có định. Cho P = C = (Z26 )
m và cho
K = { các ma trận khả nghịch cấp m ì m trên Z26}
Với một khoá K ∈K ta xác định
eK(x) = xK
và dK(y) = yK
-1
Tất cả các phép toán đ−ợc thực hiện trong Z26
Vietebooks Nguyễn Hoàng Cương
Trang 20
1.1.5 M∙ hoán vị (MHV)
Tất cả các hệ mật thảo luận ở trên ít nhiều đều xoay quanh phép
thaythế: các ký tự của bản rõ đ−ợc thay thế bằng các ký tự khác trongbản
mã. ý t−ởng của MHV là giữ các ký tự của bản rõ không thay đổi nh−ng sẽ
thay đôỉi vị trí của chúng bằng cách sắp xếp lại các ký tự này. MHV (còn
đ−ợc gọi là mã chuyển vị) đã đ−ợc dùng từ hàng trăm năm nay. Thật ra thì sự
phân biệt giữa MHV và MTT đã đ−ợc Giovani Porta chỉ ra từ 1563. Định
nghĩa hình thức cho MHV đ−ợc nêu ra trên hình 1.7.
Không giống nh− MTT, ở đây không có các phép toán đại số nào cần
thực hiện khi mã hoá và giải mã nên thích hợp hơn cả là dùng các ký tự mà
không dùng các thặng d− theo modulo 26. D−ới đây là một ví dụ minh hoạ
Ví dụ 1.6
Giả sử m = 6 và khoá là phép hoán vị ( π ) sau:
Hình 1.7 M∙ hoán vị
Khi đó phép hoán vị ng−ợc π -1 sẽ là:
Bây giờ giả sử có bản rõ
Shesellsseashellsbytheseashore
Tr−ớc tiên ta nhóm bản rõ thành các nhóm 6 ký tự:
1 2 3 4 5 6
3 5 1 6 4 2
Cho m là mộ số nguyên d−ơng xác định nào đó. Cho P = C = (Z26 )
m và
cho K gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá π ( tức là
một hoán vị) ta xác định
eπ(x1, . . . , xm ) = (xπ(1), . . . , xπ(m))
và dπ(x1, . . . , xm ) = (yπ -1(1), . . . , yπ -1(m))
trong đó π -1 là hoán vị ng−ợc của π
1 2 3 4` 5 6
3 6 1 5 2 4
Vietebooks Nguyễn Hoàng Cương
Trang 21
shesel | lsseas | hellsb | ythese | ashore
Bây giờ mỗi nhóm 6 chữ cái đ−ợc sắp xếp lại theo phép hoán vị π, ta có:
EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS
Nh− vậy bản mã là
EESLSH SALSES LSHBLE HSYEET HRAEOS
Nh− vậy bản mã đã đ−ợc mã theo cách t−ơng tự banừg phép hoán vị đảo π -1.
Thực tế mã hoán vị là tr−ờng hợp đặc biệt của mật mã Hill. Khi cho
phép hoán vị π của tập {1, . . . ,m}, ta có thể xác định một ma trận hoán vị
m ì m thích hợp Kπ = { ki,j} theo công thức:
( ma trận hoán vị là ma trận trong đó mỗi hàng và mỗi cột chỉ có một số "1",
còn tất cả các giá trị khác đều là số "0". Ta có thể thu đ−ợc một ma trận hoán
vị từ ma trận đơn vị bằng cách hoán vị các hàng hay cột).
Dễ dàng thấy rằng, phép mã Hill dùng ma trận Kπ trên thực tế t−ơng
đ−ơng với phép mã hoán vị dùng hoán vị π. Hơn nữa K-1π= Kπ -1 tức ma trận
nghịch đảo của Kπ là ma trận hoán vị xác định theo hoán vị π -1. Nh− vậy,
phép giải mã Hill t−ơng đ−ơng với phép giải mã hoán vị.
Đối với hoán vị π đ−ợc dung trong ví dun trên, các ma trận hoán vị kết
hợp là:
ki,j=
1 nếu j = π(i)
0 với các tr−