Thuật toán: Mã hóa với Hill cipher – Tài liệu text

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.64 MB, 91 trang )

21
92 39
96 59 39
98 5 10
9 1 10 11
mod 29 164 65 164 111 65 168
19 7 19 24
7 23
C ⎛
⎞ ⎛
⎞ =
= ⎜
⎟ ⎜
⎟ ⎝
⎠ ⎝
⎠
Để tìm ciphertext thì ta viết ma trận ta vừa tính được như sau: 5 19 10 7 9 19 1 24 10 7 11 23
Như vậy mã hóa thông điệp “QUANG∪THANH∪” thì ta thu dược cipher text là “FTKHJTBYKHLX”
Việc giả mã thì ta tính ma trận khả nghòch của K theo mod 29.
1 −
= ×
M K
C

3.3. Thuật toán: Mã hóa với Hill cipher

Chúng ta giả sử chiều dài của Alphabet là m 1. Hill – d cipher, khóa sẽ là ma trận vuông K bậc d với các phần tử trong
m
. Thuật toán mã hóa Hill dùng để mã hóa plaintext cho trước được thực hiện qua các bước sau :
Mã hóa 1. Người gởi tách plaintext ra thành k nhóm mỗi nhóm là một
vectơ có d ký tựtương ứng với bậc của khóa và việc tách này được thực hiện từ trái qua phải. Nếu nhóm cuối không đủ d ký tự thì ta sẽ điền thêm ký tự cuối của
plaintext cho đến khi nhóm cuối có đủ d ký tự hoặc ta điền vào các ký tự đặc biệt như khoảng trắng. Chuyển các vectơ này thành vectơ cột.
2. Thay thế các ký tự tương ứng thành các chữ số từ 0 đến m – 1 theo bảng Alphabet mà ta đã đònh nghóa.
3. Viết k vectơ cột thành ma trận; có số dòng là d và thực hiện phép nhân ma trận khóa K với ma trận M vừa tạo theo modulo m.
C = K × M modulo m 2.3 4. Sau khi được tích của hai ma trận thì ta sẽ thu được ma trận C.
Từ ma trận C ta sẽ viết lại thành k nhóm, mỗi nhóm gồm có d phần tửsố phần tử
22 của một c
ột ma trận. Sau đó ta sẽ tương ứng các số trong nhóm thành các ký tự và kết quả là ta sẽ tìm được ciphertext.
Giải mã: 1. Khi nhận được ciphertext thì người nhận cũng sẽ tách ciphertext
thành k nhóm với mỗi nhóm có d ký tự. 2. Thay thế các ký tự tương ứng thành các chữ số từ 0 đến m – 1
theo bảng Alphabet mà ta đònh nghóa. 3. Viết k nhóm thành ma trận có số dòng là d và thực hiện phép
nhân với K
-1
và tích này tính theo modulo m. M= K
-1
× Cmodulo m 2.4 4. Sau khi có M thì ta viết lại thành k nhóm, mỗi nhóm có d phần
tửmột cột của ma trận. Sau đó ta sẽ tương ứng các số trong nhóm thành các ký tự và kết quả là ta sẽ tìm được plaintext; có thể lược bỏ một số ký tự thêm vào
như khoảng trắng. Ví dụ :
Với Alphabet của tiếng Anh gồm 26 ký tự ta sẽ thêm ba ký tự đặt biệt vào gồm có “. , ? ,
∪
khoảng trắng ”
A B C D E F G
H I
J K
L M N O
0 1 2 3 4 5 6
7 8
9 10 11 12 13 14
P Q R S T U V W
X Y
Z. ? ∪
15 16 17 18 19 20 21 22
23 24 25 26 27 28
Ta cần mã hóa thông điệp WANT ∪HELP. Plaintext là: WANT ∪HELP.
23
17 5 20 23 9
3 11 2 12
K ⎛
⎞ ⎜
⎟ = ⎜
⎟ ⎜
⎟ ⎝
⎠
1. Ta viết plain text của ta thành từng nhóm có chiều dài là 3. Trong trường hợp chiều dài của nhóm cuối không đủ 3 thì ta thêm ký tự khoảng trắng
vào sao cho nhóm có chiều dài laø 3. WAN T∪H ELP . ∪∪
2. Ta thay thế các ký tự thành số theo quy tắc của bảng trên 22 0 13 19 28 7 4 11 15 26 28 28
Ta viết plaintext dưới dạng ma traän
22 19 4 26 0 28 11 28
13 7 15 28 M
⎛ ⎞
⎜ ⎟
= ⎜ ⎟
⎜ ⎟
⎝ ⎠
3. Ta tính ciphertext và bắt đầu gởi đi
17 5 20 22 19 4 26
25 13 11 1 23 9 3
0 28 11 28 23 14 4
6 mod 29 11 2 12
13 7 15 28 21 1 14 11
C K M ⎛
⎞ ⎛ ⎞ ⎛
⎞ ⎜
⎟ ⎜ ⎟ ⎜
⎟ = ×
= ×
= ⎜
⎟ ⎜ ⎟ ⎜
⎟ ⎜
⎟ ⎜ ⎟ ⎜
⎟ ⎝
⎠ ⎝ ⎠ ⎝
⎠
4. Ta viết lại dưới dạng vectơ dòng 25 23 21 13 14 1 11 4 14 1 6 11
Dựa vào bảng chữ cái ánh xạ thành số ta được ZXVNOBLEOBGL
Như vậy plaintext sau khi được mã hóa thu được như sau ZXVNOBLEOBGL
Để giải mã thì ta thực hiện như sau; ta lấy
1
K C
−
×
24
Ta có :
1
16 27 27 25 10
9 15
5 27
K
−
⎛ ⎞
⎜ ⎟
= ⎜ ⎟
⎜ ⎟
⎝ ⎠
1
16 27 27 25 13 11 11
22 19 4 26 25 10 9
23 14 4 6
0 28 11 28 15 5 27
21 1 14 11 13 7 15 28
M K C
−
⎛ ⎞ ⎛
⎞ ⎛ ⎞
⎜ ⎟ ⎜
⎟ ⎜ ⎟
= × =
× =
⎜ ⎟ ⎜
⎟ ⎜ ⎟
⎜ ⎟ ⎜
⎟ ⎜ ⎟
⎝ ⎠ ⎝
⎠ ⎝ ⎠
Ta tính được ma trận M và tìm được plaintext đã gởi.
4. Không gian khóa 4.1. Đònh nghóa không gian khóa

Chúng ta giả sử chiều dài của Alphabet là m 1. Hill – d cipher, khóa sẽ là ma trận vuông K bậc d với các phần tử trong. Thuật toán mã hóa Hill dùng để mã hóa plaintext cho trước được thực hiện qua các bước sau :Mã hóa 1. Người gởi tách plaintext ra thành k nhóm mỗi nhóm là mộtvectơ có d ký tựtương ứng với bậc của khóa và việc tách này được thực hiện từ trái qua phải. Nếu nhóm cuối không đủ d ký tự thì ta sẽ điền thêm ký tự cuối củaplaintext cho đến khi nhóm cuối có đủ d ký tự hoặc ta điền vào các ký tự đặc biệt như khoảng trắng. Chuyển các vectơ này thành vectơ cột.2. Thay thế các ký tự tương ứng thành các chữ số từ 0 đến m – 1 theo bảng Alphabet mà ta đã đònh nghóa.3. Viết k vectơ cột thành ma trận; có số dòng là d và thực hiện phép nhân ma trận khóa K với ma trận M vừa tạo theo modulo m.C = K × M modulo m 2.3 4. Sau khi được tích của hai ma trận thì ta sẽ thu được ma trận C.Từ ma trận C ta sẽ viết lại thành k nhóm, mỗi nhóm gồm có d phần tửsố phần tử22 của một cột ma trận. Sau đó ta sẽ tương ứng các số trong nhóm thành các ký tự và kết quả là ta sẽ tìm được ciphertext.Giải mã: 1. Khi nhận được ciphertext thì người nhận cũng sẽ tách ciphertextthành k nhóm với mỗi nhóm có d ký tự. 2. Thay thế các ký tự tương ứng thành các chữ số từ 0 đến m – 1theo bảng Alphabet mà ta đònh nghóa. 3. Viết k nhóm thành ma trận có số dòng là d và thực hiện phépnhân với K-1và tích này tính theo modulo m. M= K-1× Cmodulo m 2.4 4. Sau khi có M thì ta viết lại thành k nhóm, mỗi nhóm có d phầntửmột cột của ma trận. Sau đó ta sẽ tương ứng các số trong nhóm thành các ký tự và kết quả là ta sẽ tìm được plaintext; có thể lược bỏ một số ký tự thêm vàonhư khoảng trắng. Ví dụ :Với Alphabet của tiếng Anh gồm 26 ký tự ta sẽ thêm ba ký tự đặt biệt vào gồm có “., ? ,khoảng trắng ”A B C D E F GH IJ KL M N O0 1 2 3 4 5 67 89 10 11 12 13 14P Q R S T U V WX YZ. ? ∪15 16 17 18 19 20 21 2223 24 25 26 27 28Ta cần mã hóa thông điệp WANT ∪HELP. Plaintext là: WANT ∪HELP.2317 5 20 23 93 11 2 12K ⎛⎞ ⎜⎟ = ⎜⎟ ⎜⎟ ⎝1. Ta viết plain text của ta thành từng nhóm có chiều dài là 3. Trong trường hợp chiều dài của nhóm cuối không đủ 3 thì ta thêm ký tự khoảng trắngvào sao cho nhóm có chiều dài laø 3. WAN T∪H ELP. ∪∪2. Ta thay thế các ký tự thành số theo quy tắc của bảng trên 22 0 13 19 28 7 4 11 15 26 28 28Ta viết plaintext dưới dạng ma traän22 19 4 26 0 28 11 2813 7 15 28 M⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠3. Ta tính ciphertext và bắt đầu gởi đi17 5 20 22 19 4 2625 13 11 1 23 9 30 28 11 28 23 14 46 mod 29 11 2 1213 7 15 28 21 1 14 11C K M ⎛⎞ ⎛ ⎞ ⎛⎞ ⎜⎟ ⎜ ⎟ ⎜⎟ = ×= ×= ⎜⎟ ⎜ ⎟ ⎜⎟ ⎜⎟ ⎜ ⎟ ⎜⎟ ⎝⎠ ⎝ ⎠ ⎝4. Ta viết lại dưới dạng vectơ dòng 25 23 21 13 14 1 11 4 14 1 6 11Dựa vào bảng chữ cái ánh xạ thành số ta được ZXVNOBLEOBGLNhư vậy plaintext sau khi được mã hóa thu được như sau ZXVNOBLEOBGLĐể giải mã thì ta thực hiện như sau; ta lấyK C24Ta có :16 27 27 25 109 155 27⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠16 27 27 25 13 11 1122 19 4 26 25 10 923 14 4 60 28 11 28 15 5 2721 1 14 11 13 7 15 28M K C⎛ ⎞ ⎛⎞ ⎛ ⎞⎜ ⎟ ⎜⎟ ⎜ ⎟= × =× =⎜ ⎟ ⎜⎟ ⎜ ⎟⎜ ⎟ ⎜⎟ ⎜ ⎟⎝ ⎠ ⎝⎠ ⎝ ⎠Ta tính được ma trận M và tìm được plaintext đã gởi.4. Không gian khóa 4.1. Đònh nghóa không gian khóa

Xem thêm: Lịch sử Internet – Wikipedia tiếng Việt

Bạn đang đọc: Thuật toán: Mã hóa với Hill cipher – Tài liệu text

Source: https://thomaygiat.com
Category : Kỹ Thuật Số