ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
K = {(a,b) ∈ Z
26
× Z
26
: gcd(a,26) = 1}
Với K = (a,b) ∈ K, ta xác đònh
e
K
(x) = ax+b mod 26
và
d
K
= a
-1
(y-b) mod 26
(x,y ∈ Z
26
)
Phương pháp Affine lại là một trường hợp đặc biệt khác của Substitution Cipher.
Để có thể giải mã chính xác thông tin đã được mã hóa bằng hàm e
k
∈ E thì e
k
phải là một
song ánh. Như vậy, với mỗi giá trò y∈Z
26
, phương trình ax+b≡y (mod 26) phải có nghiệm
duy nhất x∈Z
26
.
Phương trình ax+b≡y (mod 26) tương đương với ax≡(y–b ) (mod 26). Vậy, ta chỉ cần
khảo sát phương trình ax≡(y–b ) (mod 26)
Đònh lý1.1: Phương trình ax+b≡y (mod 26) có nghiệm duy nhất x∈Z
26
với mỗi giá trò b∈Z
26
khi và chỉ khi a và 26 nguyên tố cùng nhau.
Vậy, điều kiện a và 26 nguyên tố cùng nhau bảo đảm thông tin được mã hóa bằng hàm e
k
có thể được giải mã và giải mã một cách chính xác.
Gọi
φ
(26) là số lượng phần tử thuộc Z
26
và nguyên tố cùng nhau với 26.
Đònh lý 1.2: Nếu
∏
=
=
m
i
e
i
i
pn
1
với p
i
là các số nguyên tố khác nhau và e
i
∈ Z
+
, 1 ≤ i ≤ m thì
( )
( )
∏
=
−
−=
m
i
e
i
e
i
ii
ppn
1
1
φ
Trong phương pháp mã hóa Affine , ta có 26 khả năng chọn giá trò b,
φ
(26) khả năng chọn
giá trò a. Vậy, không gian khóa K có tất cả n
φ
(26) phần tử.
Vấn đề đặt ra cho phương pháp mã hóa Affine Cipher là để có thể giải mã được thông tin
đã được mã hóa cần phải tính giá trò phần tử nghòch đảo a
–1
∈ Z
26
.
f. Phương pháp Vigenere
phương pháp mã hóa Vigenere sử dụng một từ khóa (keyword) có độ dài m. Có thể xem
như phương pháp mã hóa Vigenere Cipher bao gồm m phép mã hóa Shift Cipher được áp
dụng luân phiên nhau theo chu kỳ.
Không gian khóa K của phương pháp Vigenere có số phần tử là 26, lớn hơn hẳn phương
pháp số lượng phần tử của không gian khóa K trong phương pháp Shift Cipher. Do đó, việc
tìm ra mã khóa k để giải mã thông điệp đã được mã hóa sẽ khó khăn hơn đối với phương
pháp Shift Cipher.
Phương pháp mã hóa Vigenere Cipher
Chọn số nguyên dương m. Đònh nghóa P = C = K = (Z
26
)
m
K = { (k
0
, k
1
, , k
r-1
) ∈ (Z
26
)
r
}
Với mỗi khóa k = (k0, k1, , k
r-1
) ∈ K, đònh nghóa:
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
e
k
(x
1
, x
2
, , x
m
) = ((x
1
+k
1
) mod 26, (x
2
+k
2
) mod n, , (x
m
+k
m
) mod 26)
d
k
(y
1
, y
2
, , y
m
) = ((y
1
–k
1
) mod n, (y
2
–k
2
) mod n, , (y
m
–k
m
) mod 26)
với x, y ∈ (Z
26
)
m
g. Hệ mã Hill
Phương pháp Hill Cipher được Lester S. Hill công bố năm 1929: Cho số nguyên dương
m, đònh nghóa P = C = (Z
26
)
m
. Mỗi phần tử x∈P là một bộ m thành phần, mỗi thành phần
thuộc Z
26
. Ý tưởng chính của phương pháp này là sử dụng m tổ hợp tuyến tính của m thành
phần trong mỗi phần tử x∈P để phát sinh ra m thành phần tạo thành phần tử y∈C.
Phương pháp mã hóa Hill Cipher
Chọn số nguyên dương m. Đònh nghóa:
P = C = (Z
26
)
m
và K là tập hợp các ma trận m×m khả nghòch
Với mỗi khóa
K
kkk
kk
kkk
k
mmmm
m
m
∈
=
,2,1,
,21,2
,12,11,1
L
MMM
LL
L
, đònh nghóa:
( ) ( )
==
mmmm
m
m
mk
kkk
kk
kkk
xxxxkxe
,2,1,
,21,2
,12,11,1
21
, ,,
L
MMM
LL
L
với x=(x
1
, x
2
, , x
m
) ∈ P
và d
k
(y) = yk
–1
với y∈ C
Mọi phép toán số học đều được thực hiện trên Z
n
h. Mã hoán vò
Những phương pháp mã hóa nêu trên đều dựa trên ý tưởng chung: thay thế mỗi ký tự
trong thông điệp nguồn bằng một ký tự khác để tạo thành thông điệp đã được mã hóa. Ý
tưởng chính của phương pháp mã hoán vò là vẫn giữ nguyên các ký tự trong thông điệp
nguồn mà chỉ thay đổi vò trí các ký tự; nói cách khác thông điệp nguồn được mã hóa bằng
cách sắp xếp lại các ký tự trong đó.
Phương pháp mã hóa mã hoán vò
Chọn số nguyên dương m. Đònh nghóa:
P = C = (Z
26
)
m
và K là tập hợp các hoán vò của m phần tử {1, 2, , m}
Với mỗi khóa π ∈ K, đònh nghóa:
( )
( ) ( ) ( )
( )
mm
xxxxxxe
ππππ
, ,, ,,
2121
=
và
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
( )
( ) ( ) ( )
( )
m
m
yyyyyyd
111
, ,, ,,
21
21
−−−
=
πππ
π
với π
–1
hoán vò ngược của π
Phương pháp mã hoán vò chính là một trường hợp đặc biệt của phương pháp Hill. Với
mỗi hoán vò π của tập hợp {1, 2, , m} , ta xác đònh ma trận k
π
= (k
i, j
) theo công thức sau:
( )
=
=
lại ngược hợptrường trong
nếu
,0
,1
,
ji
k
ji
π
Ma trận k
π
là ma trận mà mỗi dòng và mỗi cột có đúng một phần tử mang giá trò 1, các
phần tử còn lại trong ma trận đều bằng 0. Ma trận này có thể thu được bằng cách hoán vò
các hàng hay các cột của ma trận đơn vò I
m
nên k
π
là ma trận khả nghòch. Rõ ràng, mã hóa
bằng phương pháp Hill với ma trận k
π
hoàn toàn tương đương với mã hóa bằng phương pháp
mã hoán vò với hoán vò π.
d. Mã vòng
Trong các hệ trước đều cùng một cách thức là các phần tử kế tiếp nhau của bản rõ
đều được mã hóa với cùng một khóa K. Như vậy xâu mã y sẽ có dạng sau:
y = y
1
y
2
= e
K
(x
1
) e
K
(x
2
)
Các hệ mã loại này thường được gọi là mã khối (block cipher).
Còn đối với các hệ mã dòng. Ý tưởng ở đây là sinh ra một chuỗi khóa z = z
1
z
2
,
và sử dụng nó để mã hóa xâu bản rõ x = x
1
x
2
theo qui tắc sau:
) ()(
2121
21
xexeyyy
zz
==
I.3 Quy trình thám mã:
Cứ mỗi phương pháp mã hoá ta lại có một phương pháp thám mã tương ứng nhưng
nguyên tắc chung để việc thám mã được thành công thì yêu cầu người thám mã
phải biết hệ mã nào được dùng hoá. Ngoài ra ta còn phải biết được bản mã và bản
rõ ứng.
nhìn chung các hệ mã đối xứng là dễ cài đặt với tốc độ thực thi nhanh.
Tính an toàn của nó phụ thuộc vào các yếu tố :
• Không gian khoá phải đủ lớn
• với các phép trộn thích hợp các hệ mã đối xứng có thể tạo ra được một hệ
mã mới có tính an toàn cao.
• bảo mật cho việc truyền khóa cũng cần được xử lý một cách nghiêm túc.
Và một hệ mã hoá dữ liệu ra đời (DES). DES được xem như là chuẩn mã hóa dữ
liệu cho các ứng dụng từ ngày 15 tháng 1 năm 1977 do Ủy ban Quốc gia về Tiêu chuẩn
của Mỹ xác nhận và cứ 5 năm một lần lại có chỉnh sửa, bổ sung.
DES là một hệ mã được trộn bởi các phép thế và hoán vò. với phép trộn thích hợp
thì việc giải mã nó lại là một bài toán khá khó. Đồng thời việc cài đặt hệ mã này cho
những ứng dụng thực tế lại khá thuận lợi. Chính những lý do đó nó được ứng dụng rộng
rãi của DES trong suốt hơn 20 năm qua, không những tại Mỹ mà còn là hầu như trên khắp
thế giới. Mặc dù theo công bố mới nhất (năm 1998) thì mọi hệ DES, với những khả năng
của máy tính hiện nay, đều có thể bẻ khóa trong hơn 2 giờ. Tuy nhiên DES cho đến nay
vẫn là một mô hình chuẩn cho những ứng dụng bảo mật trong thực tế.
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
II. HỆ MÃ CHUẨN DES (Data Encryption Standard)
II.1 Đặc tả DES
Phương pháp DES mã hóa từ x có 64 bit với khóa k có 56 bit thành một từ có y 64 bit.
Thuật toán mã hóa bao gồm 3 giai đoạn:
1. Với từ cần mã hóa x có độ dài 64 bit, tạo ra từ x
0
(cũng có độ dài 64 bit) bằng cách
hoán vò các bit trong từ x theo một hoán vò cho trước IP (Initial Permutation). Biểu diễn
x
0
= IP(x) = L
0
R
0
, L
0
gồm 32 bit bên trái của x
0
, R
0
gồm 32 bit bên phải của x
0
L
0
R
0
x
0
Hình.1 Biểu diễn dãy 64 bit x thành 2 thành phần L và R
2. Xác đònh các cặp từ 32 bit L
i
, R
i
với 1≤ i ≤ 16theo quy tắc sau:
L
i
= R
i-1
R
i
= L
i-1
⊕ f (R
i-1
, K
i
)
với ⊕ biểu diễn phép toán XOR trên hai dãy bit, K
1
, K
2
, , K
16
là các dãy 48 bit phát
sinh từ khóa K cho trước (Trên thực tế, mỗi khóa K
i
được phát sinh bằng cách hoán vò
các bit trong khóa K cho trước).
L
i
-1
R
i
-1
f
K
i
⊕
L
i
R
i
Hình.2 Quy trình phát sinh dãy 64 bit L
i
R
i
từ dãy 64 bit L
i-1
R
i-1
và khóa K
i
3. Áp dụng hoán vò ngược IP
-1
đối với dãy bit R
16
L
16
, thu được từ y gồm 64 bit. Như
vậy, y = IP
-1
(R
16
L
16
)
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
Hàm f được sử dụng ở bước 2 là
A
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
S
1
J
E(A)
S
2
S
3
S
4
S
5
S
6
S
7
S
8
C
1
C
2
C
3
C
4
C
5
C
6
C
7
C
8
f(A,J)
E
+
P
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
Hàm f có gồm 2 tham số: Tham số thứ nhất A là một dãy 32 bit, tham số thứ hai J là
một dãy 48 bit. Kết quả của hàm f là một dãy 32 bit. Các bước xử lý của hàm f(A, J)như
sau:
• Tham số thứ nhất A (32 bit) được mở rộng thành dãy 48 bit bằng hàm mở rộng E.
Kết quả của hàm E(A) là một dãy 48 bit được phát sinh từ A bằng cách hoán vò theo
một thứ tự nhất đònh 32 bit của A, trong đó có 16 bit của A được lập lại 2 lần trong
E(A).
• Thực hiện phép toán XOR cho 2 dãy 48 bit E(A) và J, ta thu được một dãy 48 bit B.
Biểu diễn B thành từng nhóm 6 bit như sau:B = B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
• Sử dụng 8 ma trận S
1
, S
2
, , S
8
, mỗi ma trận S
i
có kích thước 4×16 và mỗi dòng của
ma trận nhận đủ 16 giá trò từ 0 đến 15. Xét dãy gồm 6 bit B
j
= b
1
b
2
b
3
b
4
b
5
b
6
,
S
j
(B
j
) được xác đònh bằng giá trò của phần tử tại dòng r cột c của S
j
, trong đó, chỉ số
dòng r có biểu diễn nhò phân là b
1
b
6
, chỉ số cột c có biểu diễn nhò phân là b
2
b
3
b
4
b
5
.
Bằng cách này, ta xác đònh được các dãy 4 bit C
j
= S
j
(B
j
), 1 ≤ j ≤ 8.
• Tập hợp các dãy 4 bit C
j
lại. ta có được dãy 32 bit C = C
1
C
2
C
3
C
4
C
5
C
6
C
7
C
8
. Dãy 32
bit thu được bằng cách hoán vò C theo một quy luật P nhất đònh chính là kết quả của
hàm F(A, J)
các hàm được sử dụng trong DES.
Hoán vò khởi tạo IP sẽ như sau:
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Điều này có nghóa là bit thứ 58 của x là bit đầu tiên của IP(x); bit thứ 50 của x là
bit thứ hai của IP(x) v.v.
Hoán vò ngược IP
-1
sẽ là:
IP
-1
40
39
38
37
36
35
8
7
6
5
4
3
48
47
46
45
44
43
16
15
14
13
12
11
56
55
54
53
52
51
24
23
22
21
20
19
64
63
62
61
60
59
32
31
30
29
28
27
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
34
33
2
1
42
41
10
9
50
49
18
17
58
57
26
25
Hàm mở rộng E được đặc tả theo bảng sau:
E – bảng chọn bit
32
4
8
12
16
20
24
28
1
5
9
13
17
21
25
29
2
6
10
14
18
22
26
30
3
7
11
15
19
23
27
31
4
8
12
16
20
24
28
32
5
9
13
17
21
25
29
1
Tám S-hộp và hoán vò P sẽ được biểu diễn như sau:
S
1
14
0
4
15
4
15
1
12
13
7
14
8
1
4
8
2
2
14
13
4
15
2
6
9
11
13
2
1
8
1
11
7
3
10
15
5
10
6
12
11
6
12
9
3
12
11
7
14
5
9
3
10
9
5
10
0
0
3
5
6
7
8
0
13
S
2
15
3
0
13
1
13
14
8
8
4
7
10
14
7
11
1
6
15
10
3
11
2
4
15
3
8
13
4
4
14
1
2
9
12
5
11
7
0
8
6
2
1
12
7
13
10
6
12
12
6
9
0
0
9
3
5
5
11
2
14
10
5
15
9
S
3
10
13
13
1
0
7
6
10
9
0
4
13
14
9
9
0
6
3
8
6
3
4
15
9
15
6
3
8
5
10
0
7
1
2
11
4
13
8
1
15
12
5
2
14
7
14
12
3
11
12
5
11
4
11
10
5
2
15
14
2
8
1
7
12
S
4
7
13
13
8
14
11
3
5
0
6
6
15
9
0
10
3
1
4
2
7
8
2
5
12
11
1
12
10
4
14
15
9
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
10
3
6
15
9
0
0
6
12
10
11
1
7
13
13
8
15
9
1
4
3
5
14
11
5
12
2
7
8
2
4
14
S
5
2
14
4
11
12
11
2
8
4
2
1
12
1
12
11
7
7
4
10
0
10
7
13
14
11
13
7
2
6
1
8
13
8
5
15
6
5
0
9
15
3
15
12
0
15
10
5
9
13
3
6
10
0
9
3
4
14
8
0
5
9
6
14
3
S
6
12
10
9
4
1
15
14
3
10
4
15
2
15
2
5
12
9
7
2
9
2
12
8
5
6
9
12
15
8
5
3
10
0
6
7
11
13
1
0
14
3
13
4
1
4
14
10
7
14
0
1
6
7
11
13
0
5
3
11
8
11
8
6
13
S
7
4
13
1
6
11
0
4
11
2
11
11
13
14
7
13
8
15
4
12
1
0
9
3
4
8
1
7
10
13
10
14
7
3
14
10
9
12
3
15
5
9
5
6
0
7
12
8
15
5
2
0
14
10
15
5
2
6
8
9
3
1
6
2
12
S
8
13
1
7
2
2
15
11
1
8
13
4
14
4
8
1
7
6
10
9
4
15
3
12
10
11
7
14
8
1
4
2
13
10
12
0
15
9
5
6
12
3
6
10
9
14
11
13
0
5
0
15
3
0
14
3
5
12
9
5
6
7
2
8
11
P
16
29
1
5
2
32
19
22
7
12
15
18
8
27
13
11
20
28
23
31
24
3
30
4
21
17
26
10
14
9
6
25
K là xâu có độ dài 64 bit, trong đó có 56 bit dùng làm khóa và 8 bit dùng để kiểm
tra sự bằng nhau (để phát hiện lỗi). Các bit ở các vò trí 8, 16, , 64 được xác đònh, sao cho
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
mỗi byte chứa số lẻ các số 1. Vì vậy, từng lỗi có thể được phát hiện trong mỗi 8 bit. Các
bit kiểm tra sự bằng nhau là được bỏ qua khi tính lòch khóa.
1. Cho khóa 64 bit K, loại bỏ các bit kiểm tra và hoán vò các bit còn lại của K
tương ứng với hoán vò (cố đònh) PC-1. Ta viết PC-1(K) = C
0
D
0
, với C
0
bao gồm 28 bit đầu
tiên của PC-1(K) và D
0
là 28 bit còn lại.
2. Với i nằm trong khoảng từ 1 đến 16, ta tính
C
i
= LS
i
(C
i-1
)
D
i
= LS
i
(D
i-1
)
và K
i
= PC-2(C
i
D
i
), LS
i
biểu diễn phép chuyển chu trình (cyclic shift) sang trái hoặc của
một hoặc của hai vò trí tùy thuộc vào trò của i; đẩy một vò trí nếu i = 1, 2, 9 hoặc 16 và
đẩy 2 vò trí trong những trường hợp còn lại. PC-2 là một hoán vò cố đònh khác.
Việc tính lòch khóa được minh họa như hình vẽ sau:
Các hoán vò PC-1 và PC-2 được sử dụng trong việc tính lòch khóa là như sau:
PC-1
57
1
10
49
58
2
41
50
59
33
42
51
25
34
43
17
26
35
9
18
27
K
PC-1
C
0
D
0
C
1
D
1
PC-2 K
1
LS
1
LS
1
LS
2
LS
2
LS
16
LS
16
C
16
D
16
PC-2 K
16
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
19
63
7
14
21
11
55
62
6
13
34
7
54
61
5
60
39
46
53
28
52
31
38
45
20
44
23
30
37
12
36
15
22
29
4
PC-2
14
3
23
16
41
30
44
46
17
28
19
7
50
40
49
42
11
15
12
27
31
51
39
50
24
6
4
20
37
45
56
36
1
21
26
13
47
33
34
29
5
10
8
2
55
48
53
32
Bây giờ ta sẽ hiển thò kết quả việc tính lòch khóa. Như đã nhận xét ở trên, mỗi
vòng sử dụng khóa 48 bit tương ứng với 48 bit trong K. Các thành phần trong các bảng sau
sẽ chỉ ra các bit trong K được sử dụng trong các vòng khác nhau.
I.2 LẬP MÃ DES
Đây là ví dụ về việc lập mã sử dụng DES. Giả sử ta mã hóa bản rõ sau trong dạng
thập lục phân (Hexadecimal)
0123456789ABCDEF
sử dụng khóa thập lục phân
133457799BBCDFF1
Khóa trong dạng nhò phân không có các bit kiểm tra sẽ là:
00010010011010010101101111001001101101111011011111111000.
p dụng IP, ta nhận được L
0
và R
0
(trong dạng nhò phân) :
L
0
L
1
= R
0
=
=
11001100000000001100110011111111
11110000101010101111000010101010
16 vòng lập mã được thể hiện như sau:
E(R
0
)
K
1
E(R
0
) ⊕
⊕⊕
⊕ K
1
Output S-hộp
f(R
0
,K
1
)
L
2
= R
1
=
=
=
=
=
=
011110100001010101010101011110100001010101010101
000110110000001011101111111111000111000001110010
011000010001011110111010100001100110010100100111
01011100100000101011010110010111
00100011010010101010100110111011
11101111010010100110010101000100
E(R
1
)
K
2
E(R
1
) ⊕
⊕⊕
⊕ K
2
=
=
=
011101011110101001010100001100001010101000001001
011110011010111011011001110110111100100111100101
000011000100010010001101111010110110001111101100
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Không có nhận xét nào:
Đăng nhận xét