Bài giảng Lý thuyết mật mã và an toàn thông tin - 2
Phân loại mã dòng:
1. Mã tuần hoàn: Tồn tại k để zi = zi +k với mọi i, ví
dụ như mã dịch chuyên, mã vigener.
2. Mã đồng bộ: khóa lập mã không phụ thuộc vào
bản rõ (các mã cổ điển đã học đều là mã đồng bộ).
Một ví dụ của mật mã dòng không đồng bộ được
biết đến là mật mã khóa tự động được cho trong hình
1.9. nhìn bề ngoài giống với mật mã Vigenère.
Lí do dùng thuật ngữ “khóa tự động” là văn bản gốc
được sử dụng khóa (ngoại trừ khóa ban đầu K).
22 trang |
Chia sẻ: vutrong32 | Lượt xem: 1117 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Lý thuyết mật mã và an toàn thông tin - 2, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1.1.5 Mật mã Hill
Mật mã này được phát minh vào năm 1929 bởi
Lester S. Hill. Cho một số nguyên dương m và
định nghĩa P = C = (Z26)
m. Ý tưởng của thuật
toán là lấy m tổ hợp tuyến tính của m kí tự chữ
cái trong một phần tử văn bản gốc , theo đó sản
xuất m kí tự chữ cái trong một phần tử văn bản
mã.
Hình 1.6 Mật mã Hill
Cho m là một số nguyên dương cho trước. Cho P = C
= (Z26)
m và cho
K = {các ma trận m m có nghịch đảo trên Z26 }
Cho một khóa K, chúng ta định nghĩa
eK(x) = xK
và
dK(y) = yK
-1 , với K-1 là ma trận nghịch đảo của
K, ở đây tất cả các phép toán được thực hiện trong Z26
Định nghĩa 1.5
Định thức của ma trận 2 2 A = (ai,j) là giá trị
det A = a1,1a2,2 – a1.2a2,1
Nhận xét: Định thức của một ma trận vuông m m
có thể được tính bởi các phép toán cơ bản, xem
trong các sách đại số tuyến tính.
Hai đặc tính quan trọng của định thức là det Im = 1
và qui tắc nhân
det(AB) = det A det B.
Ví dụ 1.5
Giả sử khóa là K=
Từ việc tính toán ta thu được
K-1 =
Giả sử chúng ta muốn mã hóa văn bản july. Chúng ta
có 2 phần của văn bản mã là: (9,20) (tương ứng ju)
và (11,24) (tương ứng ly). Chúng ta tính như sau:
(9,20) = (99 + 60, 72 + 140) = (3,4)
và
(11,24) = (121 + 72, 88 + 168) = (11,22).
11 8
3 7
7 18
23 11
11 8
3 7
11 8
3 7
Ví dụ: nếu m = 2 chúng ta có thể viết một
phần tử văn bản là x = (x1,x2) và một phần tử
mật mã là y = (y1,y2), ở đây y1, y2 là một tổ
hợp tuyến tính của x1 và x2. Chúng ta có thể
có:
y1 = 11x1 + 3x2
y2 = 8x1 + 7x2
Tất nhiên ta cũng có thể viết dưới dạng ma trận như
sau:
(y1,y2) = (x1, x2)
11 8
3 7
Do đó, mã hóa của july là DELW . Để giải mã, Bob
sẽ tính toán như sau:
(3,4) = (9,20)
Và
(11,22) = (11,24).
Do đó, văn bản thu được là đúng.
7 18
23 11
7 18
23 11
Trong trường hợp tổng quát, chúng ta sẽ lấy ma trận K
m m là khóa. Nếu đầu vào ở hàng i và cột j của K là
ki,j thì chúng ta viết K=(ki,j). Cho x = (x1,xm) P và
K K, chúng ta tính y = eK(x) = (y1, .ym) như sau:
(y1,y2, ,.ym) = (x1,x2,.,xm)
Cách viết khác y = xK
1,1 1,2 1,
2,1 2,2 2,
,1 ,2 ,
...
...
...
m
m
m m m m
k k k
k k k
k k k
Chúng ta nói rằng văn bản mã thu được từ văn bản
gốc bằng phép biến đổi tuyến tính. Chúng ta phải
xem xét việc giải mã sẽ được thực hiện như thế nào,
làm thế nào để tính x từ y. Những người đã học đại
số tuyến tính sẽ nhận ra rằng chúng ta sử dụng ma
trận nghịch đảo K-1 để giải mã. Văn bản mã được
giải mã sử dụng công thức x = yK-1 trong mod 26.
Một ma trận số thực K có nghịch đảo nếu và chỉ nếu
định thức của nó là khác không. Tuy nhiên, một điều
quan trọng cần nhớ rằng chúng ta đang làm việc
vượt quá Z26. Kết quả liên quan tới mục đích của
chúng ta là một ma trận K có nghịch đảo moldulo 26
nếu và chỉ nếu gcd(det K, 26) =1.
1.1.6 Mật mã hoán vị
Tất cả hệ thống mật mã chúng ta thảo luận về sâu xa
nó bao hàm sự thay thế: văn bản gốc được thay thế
bởi văn bản mã khác. Ý tưởng của mật mã hoán vị là
giữ nguyên văn bản gốc nhưng thay đổi vị trí của
chúng bằng cách sắp xếp lại chúng. Mật mã hoán vị
(còn được gọi là mật mã chuyển đổi vị trí) đã được
sử dụng trong hàng trăm năm. Trong thực tế, sự
khác biệt giữa mật mã hoán vị và mật mã thay thế đã
được chú ý rất sớm từ năm 1563 bởi Giovanni Porta.
Một định nghĩa hình thức được cho trong hình 1.7
Hình 1.7 Mật mã hoán vị
Cho m là một số nguyên dương cho trước. Cho P
= C = (Z26)
m và cho K gồm tất cả các hoán vị của
{1,,m}. Cho một khóa (nghĩa là một hoán vị)
chúng ta định nghĩa
Và
ở đây là hoán vị nghịch đảo từ .
1 (1) ( )( ,..., ) ( ,...,m me x x x x
1 11 (1) ( )
( ,..., ) ( ,...,m md y y y y
1
Ví dụ 1.6
Cho m = 6 và khóa là hoán vị được cho như sau:
Khi đó ta có hoán vị nghịch đảo -1 là
1 2 3 4 5 6
3 5 1 6 4 2
1 2 3 4 5 6
3 6 1 5 2 4
Giả sử chúng ta có văn bản
Shesellsseashellsbytheseashore
trước tiên chúng ta nhóm văn bản đã cho thành các
nhóm, mỗi nhóm 6 chữ cái
Shesel | lsseas | hellsb | ythese | ashore
Bây giờ mỗi nhóm gồm 6 chữ cái là sắp xếp tùy ý hoán
vị kết quả như sau:
ELSEHS | SSLASE | LBHSEL | HEYSTE | HEARSO
Vì thế văn bản đã mã hóa là:
ELSEHS | SSLASE | LBHSEL | HEYSTE | HEARSO
1 2 3 4 5 6
3 5 1 6 4 2
Văn bản đã mã hóa có thể được giải mã tương tự như
cách đã mã hóa, sử dụng hoán vị nghịch đảo -1
Trên thực tế, mật mã hoán vị là trường hợp đặc biệt
của mật mã Hill. Cho một hoán vị của của tập hợp
{1,,m}, chúng ta có thể định nghĩa ma trận hoán vị
(kết hợp) m m, K = (ki,j) với
k j,i =
(một ma trận hoán vị là một ma trận mà mọi hàng và
cột đều chứa chính xác một giá trị “1” và các vị trí
khác đều chứa giá trị “0”. Một ma trận hoán vị có thể
thu được từ một ma trận đồng nhất bằng cách hoán vị
các hàng và cột.)
1 neu j= (i)
0 truonghopkhac
Ví dụ:
1 2 3 4 5 6
3 5 1 6 4 2
001000
000010
010000
000001
100000
000100
K
1.1.7 Mật mã dòng
Trong hệ thống mật mã chúng ta đã tìm hiểu vấn đề
này, văn bản với các phần tử kế tiếp là mật mã sử
dụng khóa K. văn bản mã xâu y thu được như sau:
y = y1y2=eK(x1)eK(x2)
Hệ thống mật mã kiểu này thường được gọi là mật
mã khối
Một cách tiếp cận khác là sử dụng cái được gọi là
mật mã dòng. Ý tưởng cơ bản là sản sinh một khóa
dòng z = z1z2., và sử dụng nó để mã hóa xâu gốc x
= x1x2tùy ý theo qui tắc
y = y1y2=ez1(x1)ez2(x2)
hoạt động của mật mã dòng là như sau: cho K K là
khóa và x1x2 là xâu gốc. Hàm fi được sử dụng để
sản sinh zi (phần tử thứ i của khóa dòng), ở đây fi là
hàm của khóa K và i-1 kí tự đầu của xâu gốc:
zi = fi (K, x1,,xi-1).
phần tử khóa dòng zi đã sử dụng để mã hóa xi, kết
quả yi = ezi(xi). vì thế để mã hóa xâu gốc
x1x2.....chúng ta sẽ tính
z1, y1, z2, y2
Giải mã xâu đã mã hóa y1y2 có thể được hoàn
thành bởi việc tính
z1, x1, z2, x2.
Định nghĩa 1.6
Mật mã dòng là một bộ (P,C,K,L,F, , D) thỏa mãn
các điều kiện sau:
1. P là tập hợp hữu hạn của các văn bản gốc
2. C là tập hợp hữu hạn của các văn bản mã
3. K là tập hợp hữu hạn của các khóa
4. L là tập hợp hữu hạn gọi là bảng chữ cái khóa
5. F = ( f1, f2..) là hàm tạo khóa. Với i 1
fi:K P
i-1 L
6. Với mỗi z L, có một qui tắc mã hóa ez và tương ứng có
một qui tắc giải mã dz Lz ez : P C và dz : C P là
các hàm sao cho dz(ez(x)) = x với mọi văn bản gốc x P.
Phân loại mã dòng:
1. Mã tuần hoàn: Tồn tại k để zi = zi +k với mọi i, ví
dụ như mã dịch chuyên, mã vigener.
2. Mã đồng bộ: khóa lập mã không phụ thuộc vào
bản rõ (các mã cổ điển đã học đều là mã đồng bộ).
Một ví dụ của mật mã dòng không đồng bộ được
biết đến là mật mã khóa tự động được cho trong hình
1.9. nhìn bề ngoài giống với mật mã Vigenère.
Lí do dùng thuật ngữ “khóa tự động” là văn bản gốc
được sử dụng khóa (ngoại trừ khóa ban đầu K).
Hình 1.9 Mật mã khóa tự động
Cho P = C = K = L = Z26, cho z1 = K và zi = xi-1 (i 2).
Cho 0 z 25, định nghĩa
ez(x) = x + z mod 26
và dz(y) = y – z mod 26 (x,y thuộc Z26).
Ví dụ mã khóa tự động (không đồng bộ)
Giả sử khóa K = 8,
P = rendezvous.
Số hóa:
P -> 17 4 13 3 4 25 21 14 20 18
Khóa dòng là:
8 17 4 13 3 4 25 21 14 20
Bây giờ chúng ta cộng các phần tử tương ứng, qui về
modulo 26
C= 25 21 17 16 7 3 20 9 8 12
Đối chiếu trong bảng chữ cái ta có văn bản mã là:
ZVRQHDUJIM
Bây giờ hãy nhìn xem Alice giải mã như thế nào.
Trước hết cô sẽ chuyển xâu chữ cái thành dãy số
nguyên
25 21 17 16 7 3 20 9 8 12
Sau đó cô ấy tính
x1 = d8(25) = 25 – 8 mod 26 =17.
tiếp theo
x2 = d17(21) = 21 – 17 mod 26 = 4. và tiếp tục như
vậy. Mỗi lần cô ấy nhận được chữ cái văn bản gốc
khác nhau. Cô cũng sử dụng nó là phần tử khóa
dòng tiếp theo .. Cho đến khi giải mã hết bản mã.
Các file đính kèm theo tài liệu này:
- mon_mat_ma_an_toan_thong_tin_2_8324.pdf