hellangel_85
New Member
Download miễn phí Luận văn Khảo sát mã ma trận, phân tích độ an toàn, hiệu năng và cải tiến
MỤC LỤC
Trang
Trang phụ bìa . 1
Lời Thank . 2
Mục lục . 3
Tóm tắt . 6
Các ký hiệu . 8
Chương 1: Các khái niệm cơ bản
1. Tổng quan . 9
2. Mật mã học (Cryptography) . 9
2.1. Mật mã học . 9
2.2. Hệ thống mã hóa(Cryptosystem) . 10
2.3. Mã hóa đối xứng . 11
3. Kiến thức lý thuyết số . 11
3.1. Modulo . 11
3.1.1. Định nghĩa . 11
3.1.2. Một số tính chất . 11
3.1.3. Định lý Fermat nhỏ . 12
4. Modulo ma trận . 13
4.1. Định nghĩa . 13
4.2. Tính chất . 14
Chương 2: Mã ma trận/Mã hill – Khảo sát không gian khóa
1. Mã thay thế (Substitution ciphers) . 16
1.1. Định nghĩa . 16
1.2. Ví dụ . 16
2. Mã ma trận (Matrix cipher) . 17
3. Mã Hill (Hill cipher) . 18
3.1. Bảng chữ cái (Alphabet) . 18
3.2. Hill – 2 cipher . 19
3.3. Thuật toán: Mã hóa với Hill cipher . 21
4. Không gian khóa . 24
4.1. Định nghĩa không gian khóa . 24
4.2. Khái niệm khóa yếu . 24
5. Khảo sát không gian khóa . 25
Ta xét khóa Klà ma trận vuông có kích thước d×d trên trường m ]
5.1. Xét không giankhóa trên trường p ](pnguyên tố) . 25
5.2. Xét không giankhóa là với đặc số nguyên tố p
5.4. Không gian tốt nhất của Alphabet . 30
6. Xét các trường hợp khóa yếu . 35
6.1. Ma trận đối hợp (Involutory matrix) . 35
6.1.1. Xây dựng ma trận đối hợp. 35
6.1.2. Đếm số ma trận đối hợp . 42
6.2. K là khóa yếu với Kv = v hay vK = v . 45
6.2.1. Xác định khóa yếu bằng định thức. 45
6.2.2. Xác định khóa yếu bằng trị riêng . 47
7. Tóm tắt . 50
Chương 3: Xây dựng thuật giải sinh khóa cho mã Hill
1. Định lý sinh khóa trên p ]. 51
2. Xác định cơ sở hình thành thuật giải . 53
3. Thuật giải . 55
4. Ví dụ . 56
5. Khảo sát không gian khóa vừa sinh theo thuật giải . 58
Chương 4: Các vấn đề liên quan đến mã Hill
1. Sinh khóa theo pincodes . 60
2. Cách tấn công mã Hill gốc. 65
3. Cải tiến thuật giải (sinh khóa từ pincodes và chuỗi ngẫu nhiên) . 66
4. Tính nhanh ma trận khả nghịch của khóa: Kết luận và kiến nghị . 71
Tài liệu thamkhảo . 72
Phụ lục Code demo thuật toán chương 4 . 74
Để 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:
znn ni zA A p A p A pφ = … …( ) ( )11mod , , mod , , mod i znn ni zB B p B p B pφ = … …
( ) ( ) ( )
( )
( )
1
1
1
1
1
1
mod , , mod , , mod
mod , , mod , , mod
= mod , , mod , , mod
=
i z
i z
i z
nn n
i z
nn n
i z
nn n
i z
A B A p A p A p
B p B p B p
A B p A B p A B p
φ φ+ = +
+ + +
… …
… …
… …
( )A Bφ +
( ) ( ) ( )
( )
( )
( )
1
1
1
1
1
1
. mod , , mod , , mod .
mod , , mod , , mod
= . mod , , . mod , , . mod
= .
i z
i z
i z
nn n
i z
nn n
i z
nn n
i z
A B A p A p A p
B p B p B p
A B p A B p A B p
A B
φ φ
φ
= … …
… …
… …
29
Bổ đề 3:
Nếu ma trận A khả nghịch mod m nếu và chỉ nếu ( )Aφ khả nghịch
Chứng minh:
Nếu A khả nghịch mod m thì ( ) ( )1 1( ) ( )A A AA Iφ φ φ φ− −= = . Do φ là
đẳng cấu vành nên ( )Aφ khả nghịch
Nếu ( )Aφ khả nghịch thì tồn tại B sao cho ( ) ( ) ( ) ( )A B AB Iφ φ φ φ= =
Vậy ta có A×B = I do đó A khả nghịch.
Định lý 3: [7, 2.3.3]
Số lượng ma trận vuông d×d trên ]m là (với 1 21 2 knn n km p p p= … )
( ) ( )2 11
0
( , ) i
k d
n d d j
m i i i
i j
GL d p p p
−−
=
⎛ ⎞= −⎜ ⎟⎝ ⎠∏ ∏] (2.8)
Chứng minh:
Gọi A là ma trận vuơng khả nghịch trên m] ; thì ( )Aφ khả nghịch.
Do φ là một đẳng cấu vành nên số lượng ma trận vuơng khả nghịch trên
m] sẽ bằng với số lượng các vectơ của φ . Ta cĩ:
( ) ( )11 mod , , mod , , mod zi nnn i zA A p A p A pφ → … …
Áp dụng định lý 2 thì từng thành phần mod iniA p có
( )2 1( 1)
0
i
d
n d d j
i i
j
p p p
−−
=
−∏
Vậy số vectơ của φ là: ( ) ( )2 11
0
i
k d
n d d j
i i i
i j
p p p
−−
=
⎛ ⎞−⎜ ⎟⎝ ⎠∏ ∏
Ta có: ( ) ( )2 11
0
( , ) i
k d
n d d j
m i i i
i j
GL d p p p
−−
=
⎛ ⎞= −⎜ ⎟⎝ ⎠∏ ∏]
30
5.4. Không gian tốt nhất của Alphabet
Định nghĩa
Đặt tỷ số giữa tổng các ma trận vuông cấp d > 0 khả nghịch với tổng
các ma trận vuông trên ]m , với m ≥ 2 là:
( , )
( , )
( )
m
d d m
GL d
f d m
M ×
= ]] (2.9)
Ý nghĩa của f(d,m) sẽ cho ta con số đánh giá để chọn ra kích thước
khóa và không gian Alphbet.
Nếu ( ) ( )/ /, ,f d m f d m> thì ta nên chọn d, m tương ứng với d là kích
thước khóa và m là lượng trong Alphabet.
Bổ đề 4:[7, bổ đề 4.3]
Nếu d là số nguyên dương và p là số nguyên tố thì
( )
2
1
0
1 1
0 0 1
( , )
( , )
( )
1 = 1 1
d
d i
p i
d
d d p
d i id d d
d d j
i i j
p pGL d
f d p
M p
p p p
p p p
−
=
×
− −
= = =
−
= =
⎛ ⎞ ⎛ ⎞ ⎛ ⎞− = − = −⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎝ ⎠ ⎝ ⎠
∏
∏ ∏ ∏
]
]
(2.10)
Định lý 4:[7, định lý 4.4]
Nếu d là số nguyên dương và m là số nguyên dương bất kỳ,
0
i
k
n
i
i
m p
=
=∏ thì :
( )
1 1
1, 1
k d
j
i j i
f d m
p= =
⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠∏∏ (2.11)
31
( )
( )
( )
2
2
2 2
2
2 2
2
1
( 1)
1 0
1
1 0
1
1
0
1
( , )
( , )
( )
=
=
i
i
i
i
i
i
k d
n d d l
i i i
i lm
k
n dd d m
i
i
k d
n d d d l
i i i i
i l
k
n d
i
i
d
n d d d l
k i i i i
l
n d
i i
p p p
GL d
f d m
M p
p p p p
p
p p p p
p
−−
= =
×
−−
= =
=
−−
=
=
⎛ ⎞−⎜ ⎟⎝ ⎠= =
⎛ ⎞−⎜ ⎟⎝ ⎠
⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠
∏ ∏
∏
∏ ∏
∏
∏∏
]
]
( )
2
1
0
1 1 1
1 = 1
d
d l
k k di i
l
jd
i i j ii
p p
pp
−
=
= = =
⎛ ⎞−⎜ ⎟ ⎛ ⎞⎜ ⎟ = −⎜ ⎟⎜ ⎟⎜ ⎟ ⎝ ⎠⎜ ⎟⎝ ⎠
∏∏ ∏∏
(2.12)
Nhận xét :
Từ (2.12) ta thấy f(d,m) không phụ thuộc vào số mũ của thừa số
nguyên tố trong phân tích thừa số nguyên tố của m (tức không phụ thuộc vào in )
Định lý 5:[7, định lý 4.6]
Cho d là nguyên dương và p là số nguyên tố thì
lim ( , ) 1
p
f d p→∞ = (2.13)
Chứng minh:
Áp dụng bổ đề 4:
1
1lim ( , ) lim 1 lim1 1→∞ →∞ →∞=
⎛ ⎞= − = =⎜ ⎟⎝ ⎠∏
d
jp p pj
f d p
p
32
Ta xét Hàm Zeta Riemann như sau:
1
1 1 1 1( )
1 2 3s s s sk
s
k
ζ ∞
=
= = + + +∑ …
(2.14)
Với ( )1ζ = ∞ (2.15)
Công thức tích Euler: (2.16)
1
1 1( ) 11
s
k p prime
s
s
k
p
ζ ∞
= −
= =
−
∑ ∏
1 1 1 1 1
1 1 2 1 3 1 5 1s s s s sp prime p p− − − − −
=− − − − −∏ " "
( )
1
1 1 11
1s sp pp p sζ
−∞ ∞
−
⎛ ⎞⎛ ⎞− = =⎜ ⎟⎜ ⎟ −⎝ ⎠ ⎝ ⎠∏ ∏
Áp dụng hàm Zeta Riemann và công thức Euler ta sẽ chứng minh
lim ( , ) 0
k
f d m
→∞
=
Định lý 6:[7, định lý 4.7]
Cho d là số nguyên dương và m là số nguyên dương với 11 k
nn
km p p= …
thì lim ( , ) 0
k
f d m
→∞
=
Chứng minh:
Từ định lý 4; (2.12) và ta xét 11= … knn km p p ; với k là số các số nguyên
tố trong phân tích thừa số nguyên tố của m; ta có:
1 1
1 1
1lim ( , ) lim 1
1 = lim 1
k d
jk k
i j i
d k
jk
j i i
f d m
p
p
→∞ →∞ = =
→∞ = =
⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠
⎛ ⎞−⎜ ⎟⎜ ⎟⎝ ⎠
∏∏
∏∏
(2.17)
33
Ta có:
1
1 1lim 1
( )
k
jk i ip jζ→∞ =
⎛ ⎞− =⎜ ⎟⎝ ⎠∏ (từ công thức tích Euler)
Do đó:
1 1 1 1
1 2
1 1lim ( , ) lim 1 lim 1
1 1 1 =
( ) (1) ( )
d k d k
j jk k k
j i j ii i
d d
j j
f d m
p p
j jζ ζ ζ
→∞ →∞ →∞= = = =
= =
⎛ ⎞ ⎛ ⎞= − = −⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
=
∏∏ ∏ ∏
∏ ∏
(2.18)
Theo (2.18) ta có (1)ζ = ∞ do đó
1 1
1lim 1 0
d k
jk
j i ip→∞ = =
⎛ ⎞− =⎜ ⎟⎜ ⎟⎝ ⎠∏∏
Vậy lim ( , ) 0
k
f d m
→∞
= nghĩa là k càng lớn thì số ma trận khả nghịch gần
bằng 0.
Ta xét các trường hợp sau:
Xét f(10,n) với n là các giá trị trong khoảng 2 đến 29.
Hình 2.1
34
Trong hình 2.1; với dấu . thì ta biểu diễn n là số nguyên tố trong khoảng
từ 2 đến 29 và dấu + là các trường hợp còn lại trong khoảng từ 2 đến 29.
Quan sát hình 2.1, ta thấy các trường hợp số nguyên tố thì f(10,p)luôn lớn
hơn các trường hợp còn lại.
Xét f(10,n) với n là các giá trị trong khoảng 29 đến 100
Hình 2.2
Với dấu . cho trường hợp f(10,29) và f(10,n) với n là các hợp số trong
khoảng từ 30 đến 100.
Quan sát hình 2.2 ta thấy f(10,n) và f(10,29) ta thấy f(10,29) luôn nằm trên
f(10,n).
Vậy khi chọn không gian cho Alphabet thì ta không cần chọn m quá lớn;
và ta nên chọn là số nguyên tố.
35
Kết luận:
- Không gian bảng chữ cái không cần lớn.
- Bảng chữ cái nên có số lượng là một số nguyên tố.
- Ta chỉ khảo sát và sinh khóa trên trường p] với p là số nguyên tố.
6. Xét các trường hợp khóa yếu
6.1. Ma trận đối hợp (Involutory matrix)
6.1.1. Xây dựng ma trận đối hợp
6.1.1.1. Ma trận đối hợp trên trường ; 2p p >]
Gọi H là ma trận đối hợp n × n trên trường p] , nghĩa là 2 nH I= nên H có
thể là:
1. nI
2. nI−
3. r r s
s r s
I Z
J
Z I
×
×
⎛ ⎞= ⎜ ⎟−⎝ ⎠
Với ,0r s n s n+ = < <
Định lý 7: (Theo [9])
Điều kiện cần và đủ để ma trận vuông H với kích thước n × n, trên
trường ; 2>] p p với 0 < s < n, thì 2 2nH I Q P= − × là ma trận đối hợp với 2Q là
ma trận n × s và 2P là ma trận s × n sao cho 2 2 2 sP Q I× = × (với s < n và hạng của
2P bằng s thì luơn tồn tại 2Q sao cho 2 2 2 sP Q I× = × ).Tương tự cho 1 1 nH Q P I= × −
với 1Q là ma trận n × r và 1P là ma trận r × n sao cho 1 1 2 rP Q I× = × và r + s = n
(với r < n và hạng của 1P bằng r thì luôn tồn tại 1 1 2 rP Q I× = × )
36
Chứng minh
Điều kiện cần.
Ta đặt 1H Q J Q−= × × ; với Q là ma trận khả nghịch bất kỳ trên p]
Ta đặt ( )/ /1 2Q Q Q= ; với /2Q là ma trận có kích thước n s×
Và đặt 11
2
P
Q
P
− ⎛ ⎞= ⎜ ⎟⎝ ⎠
; với 2P là ma trận có kích thước s n×
( ) 11 / / / /1 2 1 1 2 2
2
n
P
Q Q Q Q Q P Q P I
P
− ⎛ ⎞× = × = × + × =⎜ ⎟⎝ ⎠
(2.19)
( ) / /11 / / 1 1 1 21 2 / /
2 2 1 2 2
r r s
s r s
...