Tiểu luận môn Bảo mật thông tin | Trường Đại học Đồng Tháp

Tiểu luận môn Bảo mật thông tin | Trường Đại học Đồng Tháp. Tài liệu được biên soạn dưới dạng file PDF gồm 21 trang, giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem!

TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA SƯ PHẠM TOÁN - TIN
BÀI TIỂU LUẬN
MÔN BẢO MẬT THÔNG TIN
Người thực hiện: Trương Ngọc Thơ
Lớp: ĐHSTIN20- -L2 BL
GVHD: ThS. Nguyễn Trọng Nhân
Bạc Liêu, tháng 12 m 2021
2
MỤC LỤC
Mở đầu .............................................................................................................. 3
Nội dung ........................................................................................................... 4
Chương 1. Mã Affine .................................................................................... 4
Chương 2. Bài tập minh hoạ ......................................................................... 9
Chương 3. Đánh giá hệ mã Affine ............................................................. 14
Chương 4. Cài đặt chương trình thử nghiệm hệ mã Affine trên Python ... 17
Kết luận ............................................................................................................ 20
1. Kết quả đạt được ..................................................................................... 20
2. Hạn chế ................................................................................................... 20
3. Hướng phát triển .................................................................................... 20
Tài liệu tham khảo .......................................................................................... 21
3
MỞ ĐẦU
Ngày nay, việc ứng dụng công nghệ thông tin vào các ngành nghề đã mang
lại rất nhiều lợi ích cho mọi mặt của cuộc sống. Bên cạnh đó cũng đưa ra những
thách thức khi hòa nhập toàn cầu về mặt đảm bảo an toàn thông tin. Vấn đề bảo
mật, xác thực đang rất được quan tâm. Bảo vệ an toàn thông tin dữ liệu một chủ
đề rộng, liên quan đến nhiều lĩnh vực trong thực tế thể rất nhiều
phương pháp được thực hiện để bảo vệ an toàn thông tin dliệu. Trong đó bảo
vệ an toàn thông tin bằng mật mã
Mật một ngành khoa học chuyên nghiên cứu các phương pháp truyền
tin bí mật. Mật mã bao gồm : Lập mã và phá mã. Lập mã bao gồm hai quá trình:
hóa và giải mã.
Hiện nay rất nhiều hệ mật mã. Nếu dựa vào cách truyền khóa thể phân
các hệ mật thành hai loại: mật đối xứng mật bất h và h đối xứng.
Ngoài ra nếu dựa vào cách thức tiến hành thì hệ mật còn được chia làm
hai loại mã dòng khối. Còn nếu dựa vào thời gian đưa ra hmật mã ta
còn thể phân làm hai loại: Mật cổ điển (là hệ mật ra đời trước năm 1970)
và mật mã hiện đại (ra đời sau năm 1970).
Trong bài tiểu luận này, em xin trình bày về một loại hệ mã hoá cổ điển là
Affine
Bài tiểu luận bao gồm các phần:
Chương 1: Affine
Chương 2: Bài tập minh họa
Chương 3: Đánh giá hệ mã Affine
Chương : Cài đặt chương trình thử nghiệm hệ mã Affine trên Python4 .
4
NỘI DUNG
Chương 1: Affine
Mã dịch vòng ( là mt trường hợp đặc biệt của mã thay thế (MDV) MTT)
chỉ gồm 26 trong số 26! Các hoán vị thể của 26 phần tử. Một trường hợp
đặc biệt khác của MTT là mã Affine được mô tả dưới đây.
Mật mã Affine là một dạng mật mã thay thế dùng một bảng chữ cái, trong đó mỗi
chữ cái được ánh xạ tới một số sau đó mã hóa qua một hàm số toán học đơn giản.
Mã Affine là một trường hợp đặc biệt của mã Caesar, trong đó các chữ cái được
mã hóa với hàm
Trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng:
e(x) = ax + b mod 26
a, b Z
26
. Các hàm này được gọi là các hàm Affine (chú ý rằng khi a =
1, có MDV). ta
Để việc giảicó thể thực hiện được, yêu cầu cần thiết là hàm Affine
phải là đơn ánh. Nói cách khác, với bất kỳ y , ta muốn có đồng nhất thức Z
26
sau:
ax + b y (mod 26)
phải nghiệm x duy nhất. Đồng thức này tương đương
với:
ax y-b (mod 26)
Vì y thay đổi trên b cũng thay đổi trên Z . Bởi vậy, ta chỉ cần Z nên y-
26 26
nghiên cứu phương trình đồng dư:
ax y (mod 26) Z(y
26
).
Ta biết rằng, phương trình này một nghiệm duy nhất đối với mỗi y
khi chỉ khi UCLN(a,26) = 1 (ở đây hàm UCLN là ước chung lớn nhất của
các biến của nó). Trước tiên ta giả sử rằng, UCLN(a,26) = d >1. Khi đó, đồng
thức ax 0 (mod 26) sẽ có ít nhất hai nghiệm phân biệt trong Z
26
là x = 0
5
x = 26/d. Trong trường hợp này, e(x) = ax + b mod 26 không phải một
hàm đơn ánh và bởi vậy không thể hàm hoá hợp lệ.
Ví dụ, do UCLN(4,26) = 2 nên 4x +7 không là hàm mã hoá hợp lệ: x
x+13 mã hoá sẽ thành cùng một giá trị đối với bất kì x Z .
26
Ta giả thiết UCLN(a,26) = 1. Giả sử với x nào đó thảo
1
x
2
mãn:
ax
1
(mod 26) ax
2
Khi đó
a(x
1
- x
2
) 0(mod 26) bởi vậy
26 | a(x - x )
1 2
Bây giờ ta sẽ sử dụn một chất của Nếug tính phép chia sau: UCLN(a,b)=1
và a | thì a | | bc c. 26 a(x
1
- x ) và UCLN(a,26) = 1 nên ta có:
2
26 | (x
1
-
x
2
) tức
x
1
x (mod 26)
2
Tới đây ta chứng tỏ rằng, nếu UCLN(a,26) = 1 thì một đồng dư thức dạng
ax y (mod 26) chỉ (nhiều nhất) một nghiệm trong Z . Do đó, nếu ta
26
cho x thay đổi trên Z
26
thì ax mod 26 sẽ nhận được 26 giá trị khác nhau theo
modulo 26 đồng thức ax y (mod 26) chỉ một nghiệm y duy nhất.
Không có gì đặc biệt đối vơí số 26 trong khẳng định này. Bởi vậy, bằng
cách tương tự ta có thể chứng minh được kết quả sau:
Định
Đồng thức ax b mod m x chỉ một nghiệm duy nhất Z
m
với mọi
b
Z khi khi UCLN(a,m) =
m
chỉ 1.
Vì 26 = 2 nên các giá a Z mãn UCLN(a,26) = 1 a = x 13 trị
26
thoả
6
1, 3, 5, 7, 9, 1 15, 17, 25. Tham b 1, 13, 19, 21, 23 số có thểmột phần tử
bất kỳ trong Z . Như vậy, mã Affine có 12 26 = 312 khoá có thể (dĩ nhiên
26
x
con này quá số nhỉ để bảo đảm an toàn).
Bây giờ ta sẽ xét bài toán chung với modulo m. Ta cần một định nghĩa
khác trong lý thuyết số.
Định nghĩa
Giả sử a 1 m 2 các nguyên. UCLN(a,m) = 1 t nói số ta rằng
a và m nguyên tcùng nhau. Số các số nguyên trong Z
m
nguyên tố cùng nhau
với m thường được hiệu là (m) (hàm này được gọi hàm Euler).
Một kết quả quan trọng trong lý thuyết số cho ta giá trị của (m) theo
các thừa số trong phép phân tích theo luỹ thừa các số nguyên tố của m. (Một
số nguyên p > 1 là số nguyên tố nếu nó không có ước dương nào khác ngoài 1
và p. Mọi số nguyên m > 1 thể phân tích được thành tích của các luỹ thừa
các số
nguyên theo duy = 2 tố cách nhất. dụ 60
3
x 3 x 5 = 2 x 7 98
2
).
Số khoá trong mã Affine trên Z bằng (m), trong đó (m) được cho
m
theo công thức trên. (Số các phép chọn của b m và số các phép chọn của a
(m) hàm hoá e(x) = + b). m = 60, (60)= với mã ax dụ, khi
(5.2 .3)=
2
(5). ). (3) = 2 x x (2
2
2 4 = 16 và số các khoá trong mã Affine
là 960.
Bây giờ ta sẽ xét xem các phép toán giải trong mật Affine với
modulo m = 26. Giả sử UCLN(a,26) = 1. Để giải cần giải phương trình
đồng y ax+b (mod theo 26) x. Từ thảo luận thấy rằng, phương trên trình
này một nghiệm duy nhất trong Z
26
. Tuy nhiên ta vẫn chưa biết một phương
pháp hữu hiệu để tìm nghiệm. Điều cần thiết đây một thuật toán hữu
hiệu để làm việc đó. Rất may một số kết quả tiếp sau về số học modulo sẽ
cung cấp một thuật toán giải mã hữu hiệu cần tìm.
Định nghĩa:
7
Giả
sử a Z .
m
Phần tử nghịch đảo (theo phép nhân) của a phần tử a
-1
Z sao cho
m
aa
-1
a
-1
ª 1 (mod m).
Bằng các lý luận tương tự như trên, thể chứng tỏ rằng a có nghịch đảo
theo modulo m khichỉ khi UCLN(a,m) =1, nếu nghịch đảo này tồn tại
thì
nó phải là duy nhất. Ta cũng thấy rằng, nếu b = a . Nếu p là số
-1
thì a = b
-1
nguyên tố thì mọi phần tử khác không của Z đều nghịch đảo. Một vành
P
trong đó mọi phần tử đều có nghịch đảo được gọi là một trường.
Trong phần sau sẽ mô tả một thuật toán hữu hiệu để tính các nghịch đảo
của Z với m tuỳ ý. Tuy nhiên, trong Z chỉ bằng phương pháp thử sai
m
26
,
cũng thể tìm các nguyên cùng nhau được các nghịch đảo của phần tử tố với
26: 1 = 3 = 5
-1
1,
-1
9,
-1
= = 21, 7 = 15,
-1
11
-1
19, 17
-1
=23, = 25
-1
25. (Có thể
dễ
dàng kiểm chứng lại điều này, ví dụ: 7 x = 105 1 mod 26, 15 bởi vậy 7
-1
= 15).
Xét trình y ax+b (mod 26). trình này phương đồng Phương tương
đương với
ax y-b ( mod 26)
UCLN(a,26) nên a theo modulo 26. Nhân hai =1 nghịch đảo cả
vế
của thức đồng dư với a
-1
ta có:
a
-1
(ax) a
-1
(y-b) (mod 26)
Áp tính dụng kết hợp của phép nhân modulo:
a
-1
(ax) (a
-1
a)x 1x x.
Kết quả
x a (mod 26).
-1
(y-b) Đây một thức tường công minh cho
x.
Như vậy hàm giải là:
d(y) = a
-1
(y-b) mod 26
Cho tả đầy đủ về Affine. Sau đây một dụ nhỏ
8
Mật Affine
dụ:
Giả sử K = (7,3). nêu Như đã trên, 7
-1
mod = 26 15. Hàm hoá
e
K
(x) =
7x+3
Và hàm giải tương ứng là:
d
K
(x) = 15(y- = 15y -3) 19
đây, tất đều thực hiện kiểm cả các phép toán trên Z .
26
Ta sẽ tra
liệu d (x)) = x
K
(e
K
với mọi Z không? Dùng x
26
các tính toán trên Z , ta
26
d
K
(e
K
(x)) =d
K
(7x+3)
=15(7x+3)- = x +45 -19= 19 x.
Cho
P = C
= Z
26
giả sử
P
= { (a,b) Z
26
Z
26
: UCLN(a,26) }=1
Với K = (a,b) ,
K
ta định nghĩa:
e
K
(x) = ax +b mod 26
d (y) = a
K
-1
(y-b) mod 26,
x,y Z
26
9
Chương 2: Bài tập minh họa
Bài tập: Cho khoá k=(5,3) áp dụng hoá Affine tiến hành hoá giải
bản rõ “TRUONGNGOC THO”
Giải
MÃ HOÁ
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
X12
X13
T
R
U
O
N
G
N
G
O
C
H
O
19
17
20
14
13
6
13
6
14
2
7
14
Ta có khoá k=(5,3) => a=5; b=3
Y1 = a.X1 +b mod 26
=5.19 + 3 mod 26
=20 U
Y2 = a.X2 +b mod 26
=5.17 + 3 mod 26
=10 K
Y3 = a.X3 +b mod 26
=5.20 + 3 mod 26
= 25 Z
Y4 = a.X4 +b mod 26
=5.14 + 3 mod 26
= V 21
Y5 = a.X5 +b mod 26
=5.13 + 3 mod 26
10
= 16 Q
Y6 = a.X6 +b mod 26
=5.6 + 3 mod 26
= 7 H
Y7 =a.X7 +b mod 26
=5.13 + 3 mod 26
= 16 Q
Y8 = a.X9 +b mod 26
=5.6 + 3 mod 26
= 7 H
Y9 = a.X9 +b mod 26
=5. + 3 mod 26 14
= 21 V
Y10 = a.X10 +b mod 26
=5.2 + 3 mod 26
= 13 N
Y11 = a.X11 +b mod 26
=5.19 + 3 mod 26
=20 U
Y12 = a.X12 +b mod 26
=5.7 + 3 mod 26
= 12 M
Y13 =a.X13 +b mod 26
=5.14 + 3 mod 26
11
= 21 V
Vậy sau khi mã hoá bản rõ “TRUONGNGOCTHO” ta thu được xâu kí tự
“UKZVQHHQVNUMV”
GIẢI MÃ
Y1
Y2
Y3
Y4
Y5
Y6
Y7
Y8
Y9
Y10
Y12
Y13
U
K
Z
V
Q
H
H
Q
V
N
M
V
20
10
25
21
16
7
7
16
21
13
12
21
Ta có khoá k=(5,3) => a=5; b=3
Tìm a mod 26 =?
-1
5.5 1 mod 26
-1
1 + 26.4 mod 26
5.21 mod 26
Vậy a
-1
mod 26 = 21
X1 = a (Y1 b) mod 26
-1
= 21( -3) mod 26 20
= 19 T
X2 = a 2 b) mod 26
-1
(Y
= 21( -3) mod 26 10
= R 17
X3 = a
-1
(Y3 b) mod 26
= 21( -3) mod 26 25
= U 20
X4 = a
-1
(Y4 b) mod 26
12
= 21( -3) mod 26 21
= O 14
X5 = a
-1
(Y5 b) mod 26
= 21( -3) mod 26 16
= N 13
X6 = a
-1
(Y6 b) mod 26
= 21( 7-3) mod 26
= G 6
X7 = a
-1
(Y7 b) mod 26
= 21( 7-3) mod 26
= N 13
X8 = a
-1
(Y8 b) mod 26
= 21( -3) mod 26 16
= G 6
X9 = a
-1
(Y9 b) mod 26
= 21( -3) mod 26 21
= O 14
X10 = a (Y10 b) mod 26
-1
= 21( -3) mod 26 13
= C 2
X11 = a (Y11 b) mod 26
-1
= 21( -3) mod 26 20
= T 19
X12 = a (Y12 b) mod 26
-1
13
= 21( -3) mod 26 12
= H 7
X13 = a (Y13 b) mod 26
-1
= 21( -3) mod 26 21
= O 14
Vậy sau khi giải mã ta thu được xâu kí tự “TRUONGNGOCTHO”
14
Chương 3: Đánh giá hệ mã Affine
Mã Affine nói riêng các loại mật mã thay thế nói chung có thể bị tấn công
bởi việc phân tích tần suất tự, theo đó không an toàn cho các thông điệp
ngắn. Đặc biệt trường hợp văn bản ngắn, tấn trong các kẻ công hoàn toàn có thể
sử dụng phương pháp tấn công vét cạn (lần lượt thay thế các ký tự trong bản
cho đến khi tìm được văn bản có ý nghĩa)! Đối với các văn bản dài, việc tấn công
vét này không thi. cạn khả
Việc tấn công dựa trên xác suất thể được phòng tránh bằng việc thêm
nhiễu (các tự vô nghĩa đối với nội dung văn bản), hoặc sử dụng các biến thể
ngôn ngữ.
Ví dụ bản sau: với văn
In cryptography, the ElGamal encryption system is an asymmetric key
encryption algorithm for public-key cryptography which is based on the Diffie -
Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal
encryption is used in the free GNU Privacy Guard software, recent versions of
PGP, and other cryptosystems. The DSA (Digital Signature Algorithm) is a
variant of the ElGamal signature scheme, which should not be confused with
ElGamal encryption.
Các tự số lần xuất hiện như sau:
B 1: T n t ng su xut hin c a các kí t trong văn bn
<BS>
)
(
-
,
.
1
5
9
8
a
c
b
e
d
g
15.24
0.21
0.21
0.43
0.86
0.86
0.21
0.21
0.21
0.21
6.87
3.65
1.07
9.01
2.36
3.43
f
i
h
k
m
l
o
n
p
s
r
u
t
w
v
y
1.72
6.22
4.29
0.64
2.79
3.65
4.08
5.15
2.79
4.94
5.36
1.72
6.01
1.07
0.64
3.65
Thêm vào gây các tự nhiễu một nhiên: cách ngẫu
I!n*) "!cry&$!!pto#g(*r(+$#a%&p#'"h*$y(), #"+%t()&'#)h$#!(e'+&
(+$E'"!'l#%Gam!al e$*n%$c)ry*p#t+&+#i%o*)$"*n%"+'
15
*sy#(#$%s""%#)('t(e'!$m i**!s !*()"%"'a#n
as$%'ym+#m*!e$t$*%&++!ric*$+%)$!)! k"e!$"y(!*
$e!nc+r*y$p*#%$&t&&#"#!%+(i)!(*on& al(&$)g+o&r+#ithm%
()f&(or pu+bli+*c''-k#e+%y
$"&*c)&&#r'#yp'to"g$&#'#(*%r'a&p$h$)!(y
$w+hic'h"+*%&& "'(&!%$%%#is$ ba*'s"%e+d&# (*%o!+((("n
%the$)+) D*+)i!ffie#++ )-$" !!He&l&l)m+"an$$ key*
#ex(c!*#*+h#(&)*a"n'$#g)e.$)&%!$+ (+'%I#*$)##t*(& w'a#s
*%!"d)(e!&*!'s!&"cr%i!be)&d+ "b%y)$ Ta!&'he!r++
El+$"(ga%$"m+al(#%*+ !"%'in *!"*19&)$&(*$85.
&El&)$'&'G!a!m!)(!a'()!++*&l
&e*&*nc+r&&"&+%$!)y$+!p!!('ti%#+&o'+n*' i*)$&&&s
*us)"ed#)#%)( i%+n(($# "the!)' &'(fr%e*)e'#( $G%$*N$'"'+U+
P+r&#%#&(i+(!*)#*"*&)"va#cy G$u*a"+&r*d
$&s&(+"()of(#tw'a!!re&$,& rece#'n((t) ve(+++r($"s"!i#(ons!
)o"f$'! P*(+GP,( an'd ot'he+r&%# cr!yp%to$*+'%sys%te#m)#s".
&Th'e D$SA (D$ig(i*tal *#+Signa!t+u!"re +Algo(r)i+t#hm) is
a'$" va)riant(* of t*$he (El'Gamal si%&(gnat#ure schem)%e',
%whic%h $sh)ould not be confused with ElGamal e&ncryption.
Các ký tự có tần suất xuất hiện như sau:
Bảng Tần suất 2: xuất hiện của các kí tự sau khi y nhiễu
!
<BS>
#
"
%
$
'
&
)
(
+
5.25
6.77
5.06
4.1
4.48
5.63
4.39
5.63
4.68
5.44
5.73
-
,
.
1
5
9
8
a
c
b
e
0.19
0.38
0.38
0.1
0.1
0.1
0.1
3.05
1.62
0.48
4.01
f
i
h
k
m
l
o
n
p
s
r
0.76
2.77
1.91
0.29
1.24
1.62
1.81
2.29
1.24
2.19
2.39
Sau khi thêm nhiễu, rõ ràng việc phân tích và phỏng đoán nội dung văn bản
16
sẽ gặp khăn hơn nhiều. khó Tuy nhiên cách này vẫn thể bị công tấn khi các
tự gây nhiễu được thêm vào không hoàn toàn p phân xác vỡ bố suất của các ký
tự nghĩa.
17
Chương : Cài đặt chương trình thử nghiệm hệ mã Affine trên Python4 .
CODE:
import detectEnglish
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
# Return Greatest Common Divisor of a and b
def gcd(a, b):
while a != 0:
a, b = b % a, a
return b
# Return Inverse Module of a with mod m
def inverseMod(a, m):
if gcd(a, m) != 1:
return None
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1,
v2, v3
return u1 % m
# Return Affine Cipher with MODE encrypt or decrypt
def affine_cipher(message, MODE, key):
message = message.upper()
translated = ''
18
modInverseOfKeyA = inverseMod(key[0], len(LETTERS))
if modInverseOfKeyA == None:
return None
for symbol in message:
if symbol in LETTERS:
symIndex = LETTERS.find(symbol)
if MODE.upper() == 'ENCRYPT':
translated += LETTERS[(symIndex * key[0] + key[1]) %
len(LETTERS)]
elif MODE.upper() == 'DECRYPT':
translated += LETTERS[(symIndex - key[1]) *
modInverseOfKeyA % len(LETTERS)]
else:
translated += symbol
return translated
# Crack Affine Cipher
def affine_crack(cipher):
for a in range(0, len(LETTERS)):
if gcd(a, len(LETTERS)) == 1:
for b in range(0, len(LETTERS)):
message = affine_cipher(cipher, 'DECRYPT', (a, b))
if detectEnglish.isEnglish(message):
return (a, b, message)
return (None, None)
19
key = (7, 2)
cipher = affine_cipher(message, 'ENCRYPT', key)
print('\n\nCipher text: ' + cipher)
message = affine_crack(cipher)
print('\n\nKey = [{0}, {1}]'.format(message[0], message[1]))
print('\nPlain text after crack: ' + message[2])
20
KẾT LUẬN
1. Kết quả đạt được
Bài tiểu luận tiến hành nghiên cứu giải quyết bài toán về hóa, giải
trên hệ mã cổ điển . Từ việc giải quyết bài toán. Bài toán nền tảng cho Affine
nhiều ứng dụng quan trọng thực tế như quảng cáo nhắm mục tiêu, các thống hệ
cung cấp tiếp thị dịch vụ thương mại điện tới đúng người tử dùng,
2. Hạn chế:
Nghiên Affine cứu Hệ chỉ sử dụng các tự bảng chữ bảng ch cái,
cái không lớn nên bị giới hạn bởi các bảng chữ cái
Dễ bị công tấn bằng tần cách phân tích số khó phòng ngừa.
Không có khả năng phục hồi văn bản gốc
3. Hướng triển phát
Thay Affine thế bằng hệ đối khác toàn (AES, DES) xứng an hơn như
| 1/21

Preview text:

TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA SƯ PHẠM TOÁN - TIN BÀI TIỂU LUẬN
MÔN BẢO MẬT THÔNG TIN
Người thực hiện: Trương Ngọc Thơ Lớp: ĐHSTIN20-L2-BL
GVHD: ThS. Nguyễn Trọng Nhân
Bạc Liêu, tháng 12 năm 2021 2 MỤC LỤC
Mở đầu .............................................................................................................. 3
Nội dung ........................................................................................................... 4
Chương 1. Mã Affine .................................................................................... 4
Chương 2. Bài tập minh hoạ ......................................................................... 9
Chương 3. Đánh giá hệ mã Affine ............................................................. 14
Chương 4. Cài đặt chương trình thử nghiệm hệ mã Affine trên Python .. . 17
Kết luận ............................................................................................................ 20
1. Kết quả đạt được ..................................................................................... 20
2. Hạn chế ................................................................................................... 20
3. Hướng phát triển ................................................................................... . 20
Tài liệu tham khảo .......................................................................................... 21 3 MỞ ĐẦU
Ngày nay, việc ứng dụng công nghệ thông tin vào các ngành nghề đã mang
lại rất nhiều lợi ích cho mọi mặt của cuộc sống. Bên cạnh đó cũng đưa ra những
thách thức khi hòa nhập toàn cầu về mặt đảm bảo an toàn thông tin. Vấn đề bảo
mật, xác thực đang rất được quan tâm. Bảo vệ an toàn thông tin dữ liệu là một chủ
đề rộng, có liên quan đến nhiều lĩnh vực và trong thực tế có thể có rất nhiều
phương pháp được thực hiện để bảo vệ an toàn thông tin dữ liệu. Trong đó có bảo
vệ an toàn thông tin bằng mật mã
Mật mã là một ngành khoa học chuyên nghiên cứu các phương pháp truyền
tin bí mật. Mật mã bao gồm : Lập mã và phá mã. Lập mã bao gồm hai quá trình: mã hóa và giải mã.
Hiện nay có rất nhiều hệ mật mã. Nếu dựa vào cách truyền khóa có thể phân
các hệ mật mã thành hai loại: hệ mật mã đối xứng và hệ mật mã bất đối xứng.
Ngoài ra nếu dựa vào cách thức tiến hành mã thì hệ mật mã còn được chia làm
hai loại là mã dòng và mã khối. Còn nếu dựa vào thời gian đưa ra hệ mật mã ta
còn có thể phân làm hai loại: Mật mã cổ điển (là hệ mật mã ra đời trước năm 1970)
và mật mã hiện đại (ra đời sau năm 1970).
Trong bài tiểu luận này, em xin trình bày về một loại hệ mã hoá cổ điển là mã Affine
Bài tiểu luận bao gồm các phần: Chương 1: Affine
Chương 2: Bài tập minh họa
Chương 3: Đánh giá hệ mã Affine
Chương 4: Cài đặt chương trình thử nghiệm hệ mã Affine trên Python. 4 NỘI DUNG Chương 1: Mã Affine
Mã dịch vòng (MDV) là một trường hợp đặc biệt của mã thay thế (MTT)
chỉ gồm 26 trong số 26! Các hoán vị có thể của 26 phần tử. Một trường hợp
đặc biệt khác của MTT là mã Affine được mô tả dưới đây.
Mật mã Affine là một dạng mật mã thay thế dùng một bảng chữ cái, trong đó mỗi
chữ cái được ánh xạ tới một số sau đó mã hóa qua một hàm số toán học đơn giản.
Mã Affine là một trường hợp đặc biệt của mã Caesar, trong đó các chữ cái được mã hóa với hàm
Trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng: e(x) = ax + b mod 26
a, b ∈ Z26 . Các hàm này được gọi là các hàm Affine (chú ý rằng khi a = 1, ta có MDV).
Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine
phải là đơn ánh. Nói cách khác, với bất kỳ y ∈ Z26, ta muốn có đồng nhất thức sau: ax + b ≡ y (mod 26)
phải có nghiệm x duy nhất. Đồng dư thức này tương đương với: ax ≡ y-b (mod 26)
Vì y thay đổi trên Z26 nên y-b cũng thay đổi trên Z26 . Bởi vậy, ta chỉ cần
nghiên cứu phương trình đồng dư: ax ≡ y (mod 26) (y ∈ Z26 ).
Ta biết rằng, phương trình này có một nghiệm duy nhất đối với mỗi y
khi và chỉ khi UCLN(a,26) = 1 (ở đây hàm UCLN là ước chung lớn nhất của
các biến của nó). Trước tiên ta giả sử rằng, UCLN(a,26) = d >1. Khi đó, đồng
dư thức ax ≡ 0 (mod 26) sẽ có ít nhất hai nghiệm phân biệt trong Z26 là x = 0 5
và x = 26/d. Trong trường hợp này, e(x) = ax + b mod 26 không phải là một
hàm đơn ánh và bởi vậy nó không thể là hàm m ã hoá hợp lệ.
Ví dụ, do UCLN(4,26) = 2 nên 4x +7 không là hàm mã hoá hợp lệ: x và x+13 s
ẽ mã hoá thành cùng một giá trị đối với bất kì x ∈ Z26 .
Ta giả thiết UCLN(a,26) = 1. Giả sử với x1 và x2 nào đó thảo mãn: ax1 ≡ ax2 (mod 26) Khi đ ó
a(x1- x2) ≡ 0(mod 26) bởi vậy 26 | a(x1- x2)
Bây giờ ta sẽ sử dụng một tính chất của phép chia sau: Nếu UCLN(a,b)=1
và a | bc thì a | c. V ì26 | a(x1- x2) và UCLN(a,26) = 1 nên ta có: 26 | (x1- x2) tức là x1 ≡ x2 (mod 26)
Tới đây ta chứng tỏ rằng, nếu UCLN(a,26) = 1 thì một đồng dư thức dạng
ax ≡ y (mod 26) chỉ có (nhiều nhất) một nghiệm trong Z26 . Do đó, nếu ta
cho x thay đổi trên Z26 thì ax mod 26 sẽ nhận được 26 giá trị khác nhau theo modulo 26 và đồng d
ư thức ax ≡ y (mod 26) chỉ c
ó một nghiệm y duy nhất.
Không có gì đặc biệt đối vơí số 26 trong khẳng định này. Bởi vậy, bằng
cách tương tự ta có thể chứng minh được kết quả sau: Định
Đồng thức ax ≡ b mod m chỉmột nghiệm duy nhất x ∈ Zm với mọi b
∈ Zm khi và chỉ khi UCLN(a,m) = 1. Vì 26 = 2 x 1
3 nên các giá trị a ∈ Z26 thoả mãn UCLN(a,26) = 1 là a = 6
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 2 3 v
à 25. Tham số b có thể là một phần tử
bất kỳ trong Z26 . Như vậy, mã Affine có 12 x 26 = 312 khoá có thể (dĩ nhiên
con số này quá nhỉ để bảo đảm an toàn).
Bây giờ ta sẽ xét bài toán chung với modulo m. Ta cần một định nghĩa
khác trong lý thuyết số.
Định nghĩa
Giả sử a ≥ 1 và m ≥ 2 l
à các số nguyên. UCLN(a,m) = 1 thì ta nói rằng
a và m là nguyên tố cùng nhau. Số các số nguyên trong Zm nguyên tố cùng nhau
với m thường đượchiệu là ∅(m) (hàm này được gọi là hàm Euler).
Một kết quả quan trọng trong lý thuyết số cho ta giá trị của ∅ (m) theo
các thừa số trong phép phân tích theo luỹ thừa các số nguyên tố của m. (Một
số nguyên p > 1 là số nguyên tố nếu nó không có ước dương nào khác ngoài 1
và p. Mọi số nguyên m > 1 có thể phân tích được thành tích của các luỹ thừa
các số nguyên tố theo cách duy nhất. V ídụ 60 = 32 x 3 x 5 và 98 = 2 x 72 ).
Số khoá trong mã Affine trên Zm bằng ∅ (m), trong đó ∅ (m) được cho
theo công thức trên. (Số các phép chọn của b là m và số các phép chọn của a là ∅ (m) với hàm m
ã hoá là e(x) = ax + b). Ví dụ, kh i m = 60, ∅ (60)= ∅
(5.22.3)= ∅ (5). ∅ (22). ∅ (3) = 2 x 2 x 4 = 16 và số các khoá trong mã Affine là 960.
Bây giờ ta sẽ xét xem các phép toán giải mã trong mật mã Affine với
modulo m = 26. Giả sử UCLN(a,26) = 1. Để giải mã cần giải phương trình
đồng dư y ≡ ax+b (mod 26) theo x. Từ thảo luận trên thấy rằng, phương trình
này có một nghiệm duy nhất trong Z26 . Tuy nhiên ta vẫn chưa biết một phương
pháp hữu hiệu để tìm nghiệm. Điều cần thiết ở đây là có một thuật toán hữu
hiệu để làm việc đó. Rất may là một số kết quả tiếp sau về số học modulo sẽ
cung cấp một thuật toán giải mã hữu hiệu cần tìm.
Định nghĩa: 7
Giả sử a ∈ Z -1
m . Phần tử nghịch đảo (theo phép nhân) của a là phần tử a ∈
Zm sao cho aa-1 ≡ a-1ª ≡ 1 (mod m).
Bằng các lý luận tương tự như trên, có thể chứng tỏ rằng a có nghịch đảo
theo modulo m khi và chỉ khi UCLN(a,m) =1, và nếu nghịch đảo này tồn tại
thì nó phải là duy nhất. Ta cũng thấy rằng, nếu b = a-1 thì a = b-1 . Nếu p là số
nguyên tố thì mọi phần tử khác không của ZP đều có nghịch đảo. Một vành
trong đó mọi phần tử đều có nghịch đảo được gọi là một trường.
Trong phần sau sẽ mô tả một thuật toán hữu hiệu để tính các nghịch đảo
của Zm với m tuỳ ý. Tuy nhiên, trong Z26, chỉ bằng phương pháp thử và sai
cũng có thể tìm được các nghịch đảo của các phần tử nguyên t ố cùng nhau với
26: 1-1 = 1, 3-1 = 9, 5-1 = 21, 7-1 = 15, 11-1 = 19, 17-1 =23, 25-1 = 25. (Có thể
dễ dàng kiểm chứng lại điều này, ví dụ: 7 x 15 = 105 ≡ 1 mod 26, bởi vậy 7-1 = 15).
Xét phương trình đồng dư y ≡ ax+b (mod 26). Phương trình này tương đương với ax ≡ y-b ( mod 26) Vì UCLN(a,26) =
1 nên a có nghịch đảo theo modulo 26. Nhân cả hai
vế của đồng dư thức với a-1 ta có: a-1(ax) ≡ a-1(y-b) (mod 26)
Áp dụng tính kết hợp của phép nhân modulo:
a-1(ax) ≡ (a-1a)x ≡ 1x ≡ x.
Kết quả là x ≡ a-1(y-b) (mod 26). Đây là một công thức tường minh cho x.
Như vậy hàm giải mã là: d(y) = a-1(y-b) mod 2 6
Cho mô tả đầy đủ về m
ã Affine. Sau đây là một ví dụ nhỏ 8
Cho P = C = Z26 và giả sử
P = { (a,b)  Z26  Z26 : UCLN(a,26) = 1 }
Với K = (a,b) K , ta định nghĩa: eK(x) = ax +b mod 26 và d -1 K(y) = a (y-b) mod 26, x,y  Z26 Mật mã Affine Ví dụ:
Giả sử K = (7,3). Như đã nêu ở trên, 7 -1 mod 2 6 = 15 .Hàm mã ho á l à eK (x) = 7x+3
Và hàm giải mã tương ứng là: dK(x) = 15(y-3) = 15y -19
Ở đây, tất cả các phép toán đều thực hiện trên Z2 . 6 Ta sẽ kiểm tra
liệu dK(eK(x)) = x với mọi x ∈ Z26 không? Dùng các tính toán trên Z26 , ta có dK(eK(x)) =dK(7x+3) =15(7x+3)-19 = x +45 -19= x. 9
Chương 2: Bài tập minh họa
Bài tập: Cho khoá k=(5,3) áp dụng mã hoá Affine tiến hành mã hoá và giải mã bản rõ “TRUONGNGOCTHO ” Giải MÃ HOÁ
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 T R U O N G N G O C T H O 19 17 20 14 13 6 13 6 14 2 19 7 14
Ta có khoá k=(5,3) => a=5; b=3 Y1 = a.X1 +b mod 26 =5.19 + 3 mod 26 =20  U Y2 = a.X2 +b mod 26 =5.17 + 3 mod 26 =10  K Y3 = a.X3 +b mod 26 =5.20 + 3 mod 26 = 25  Z Y4 = a.X4 +b mod 2 6 =5.14 + 3 mod 26 =2 1  V Y5 = a.X5 +b mod 26 =5.13 + 3 mod 26 10 = 16  Q Y6 = a.X6 +b mod 26 =5.6 + 3 mod 26 = 7  H Y7 =a.X7 +b mod 26 =5.13 + 3 mod 26 = 16  Q Y8 = a.X9 +b mod 26 =5.6 + 3 mod 26 = 7  H Y9 = a.X9 +b mod 26 =5.1 4 + 3 mod 26 = 21  V Y10 = a.X10 +b mod 26 =5.2 + 3 mod 26 = 13  N Y11 = a.X11 +b mod 26 =5.19 + 3 mod 26 =20  U Y12 = a.X12 +b mod 26 =5.7 + 3 mod 26 = 12  M Y13 =a.X13 +b mod 26 =5.14 + 3 mod 26 11 = 21  V
Vậy sau khi mã hoá bản rõ “TRUONGNGOCTHO” ta thu được xâu kí tự “UKZVQHHQVNUMV” GIẢI MÃ
Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Y12 Y13 U K Z V Q H H Q V N U M V 20 10 25 21 16 7 7 16 21 13 20 12 21
Ta có khoá k=(5,3) => a=5; b=3 Tìm a-1 mod 26 =? 5.5-1 ≡ 1 mod 26 ≡ 1 + 26.4 mod 26 ≡ 5.21 mod 26 Vậy a-1 mod 26 = 21 X1 = a-1 (Y1 – b) mod 26 = 21( 2 - 0 3) mod 26 = 19  T X2 = a-1 (Y2 – b) mod 26 = 21( 1 - 0 3) mod 26 = 17  R X3 = a-1 (Y3 – b) mod 26 = 21( 2 - 5 3) mod 26 = 20  U X4 = a-1 (Y4 – b) mod 26 12 = 21( 2 - 1 3) mod 26 = 14  O X5 = a-1 (Y5 – b) mod 26 = 21( 1 - 6 3) mod 26 = 13  N X6 = a-1 (Y6 – b) mod 26 = 21( 7-3) mod 26 = 6  G X7 = a-1 (Y7 – b) mod 26 = 21( 7-3) mod 26 = 13  N X8 = a-1 (Y8 – b) mod 26 = 21( 1 - 6 3) mod 26 = 6  G X9 = a-1 (Y9 – b) mod 26 = 21( 2 - 1 3) mod 26 = 14  O X10 = a-1 (Y10 – b) mod 26 = 21(1 3 -3) mod 26 = 2  C X11 = a-1 (Y11 – b) mod 26 = 21( 2 - 0 3) mod 26 = 19  T X12 = a-1 (Y12 – b) mod 26 13 = 21( 1 - 2 3) mod 26 = 7  H X13 = a-1 (Y13 – b) mod 26 = 21(2 1 -3) mod 26 = 14  O
Vậy sau khi giải mã ta thu được xâu kí tự “TRUONGNGOCTHO” 14
Chương 3: Đánh giá hệ mã Affine
Mã Affine nói riêng và các loại mật mã thay thế nói chung có thể bị tấn công
bởi việc phân tích tần suất ký tự, và theo đó không an toàn cho các thông điệp
ngắn. Đặc biệt trong trường hợp các văn bản ngắn, kẻ tấn công hoàn toàn có thể
sử dụng phương pháp tấn công vét cạn (lần lượt thay thế các ký tự trong bản mã
cho đến khi tìm được văn bản có ý nghĩa)! Đối với các văn bản dài, việc tấn công vét cạn này không kh ả thi.
Việc tấn công dựa trên xác suất có thể được phòng tránh bằng việc thêm
nhiễu (các ký tự vô nghĩa đối với nội dung văn bản), hoặc sử dụng các biến thể ngôn ngữ.
Ví dụ với văn bản sau:
In cryptography, the ElGamal encryption system is an asymmetric key
encryption algorithm for public-key cryptography which is based on the Diffie -
Hel man key exchange. It was described by Taher Elgamal in 1985. ElGamal
encryption is used in the free GNU Privacy Guard software, recent versions of
PGP, and other cryptosystems. The DSA (Digital Signature Algorithm) is a
variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption. Các ký tự c ó s
ố lần xuất hiện như sau: Bản
g 1: Tần suất xuất hiện của các kí tự trong văn bản ) ( - , . 1 5 9 8 a c b e d g 15.24 0.21
0.21 0.43 0.86 0.86 0.21 0.21 0.21 0.21 6.87 3.65 1.07 9.01 2.36 3.43 f i h k m l o n p s r u t w v y 1.72 6.22
4.29 0.64 2.79 3.65 4.08 5.15 2.79 4.94 5.36 1.72 6.01 1.07 0.64 3.65
Thêm vào các ký tự gây nhiễu một cách ngẫu nhiên:
I!n*) "!cry&$!!pto#g(*r(+$#a%&p#'"h*$y(), #"+%t()&'#)h$#!(e'+&
(+$E'"!'l#%Gam!al e$*n%$c)ry*p#t+&+#i%o*)$"*n%"+' 15 *sy#(#$%s""%#)('t(e'!$m i**!s !*()"%"'a#n
as$%'ym+#m*!e$t$*%&++!ric*$+%)$!)! k"e!$"y(!*
$e!nc+r*y$p*#%$&t&"#!%+(i)!(*on& al(&$)g+o&r+#ithm% ()f&(or pu+bli+*c' -k#e+%y
$"&*c)&r'#yp'to"g$'#(*%r'a&p$h$)!(y
$w+hic'h"+*%&& "'(&!%$%%#is$ ba*'s"%e+d (*%o!+((("n %the$)+) D*+)i!ffie#++ )-$" !!He&l&l)m+"an$$ key*
#ex(c!*#*+h#(&)*a"n'$#g)e.$)&%!$+ (+'%I#*$)##t*(& w'a#s
*%!"d)(e!&*!'s!&"cr%i!be)&d+ "b%y)$ Ta!&'he!r++ El+$"(ga%$"m+al(#%*+ !"%'in *!"*19&)$&(*$85.
&El&)$'&'G!a!m!)(!a'()!++*&l
&e*&*nc+r&&"&+%$!)y$+!p!!('ti%#+&o'+n*' i*)$&&&s
*us)"ed#)#%)( i%+n(($# "the!)' &'(fr%e*)e'#( $G%$*N$'"'+U+
P+r%#&(i+(!*)#*"*&)"va#cy G$u*a"+&r*d
$&s&(+"()of(#tw'a!!re&$,& rece#'n((t) ve(+++r($"s"!i#(ons!
)o"f$'! P*(+GP,( an'd ot'he+r&%# cr!yp%to$*+'%sys%te#m)#s".
&Th'e D$SA (D$ig(i*tal *#+Signa!t+u!"re +Algo(r)i+t#hm) is
a'$" va)riant(* of t*$he (El'Gamal si%&(gnat#ure schem)%e',
%whic%h $sh)ould not be confused with ElGamal e&ncryption.
Các ký tự có tần suất xuất hiện như sau:
Bảng 2: Tần suất xuất hiện của các kí tự sau khi gây nhiễu ! # " % $ ' & ) ( +
5.25 6.77 5.06 4.1 4.48 5.63 4.39 5.63 4.68 5.44 5.73 - , . 1 5 9 8 a c b e 0.19 0.38 0.38 0.1 0.1 0.1 0.1 3.05 1.62 0.48 4.01 f i h k m l o n p s r
0.76 2.77 1.91 0.29 1.24 1.62 1.81 2.29 1.24 2.19 2.39
Sau khi thêm nhiễu, rõ ràng việc phân tích và phỏng đoán nội dung văn bản 16
sẽ gặp khó khăn hơn nhiều. Tuy nhiên cách này vẫn có thể bị tấn công kh icác k ý
tự gây nhiễu được thêm vào không hoàn toàn phá vỡ phân b
ố xác suất của các ký tự có nghĩa. 17
Chương 4: Cài đặt chương trình thử nghiệm hệ mã Affine trên Python. CODE: import detectEnglish
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
# Return Greatest Common Divisor of a and b def gcd(a, b): while a != 0: a, b = b % a, a return b
# Return Inverse Module of a with mod m def inverseMod(a, m): if gcd(a, m) != 1: return None u1, u2, u3 = 1, 0, a v1, v2, v3 = 0, 1, m while v3 != 0: q = u3 // v3
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3 return u1 % m
# Return Affine Cipher with MODE encrypt or decrypt
def affine_cipher(message, MODE, key): message = message.upper() translated = ' 18
modInverseOfKeyA = inverseMod(key[0], len(LETTERS)) if modInverseOfKeyA == None: return None for symbol in message: if symbol in LETTERS:
symIndex = LETTERS.find(symbol)
if MODE.upper() == 'ENCRYPT':
translated += LETTERS[(symIndex * key[0] + key[1]) % len(LETTERS)]
elif MODE.upper() == 'DECRYPT': translated += LETTERS[(symIndex - key[1]) *
modInverseOfKeyA % len(LETTERS)] else: translated += symbol return translated # Crack Affine Cipher def affine_crack(cipher):
for a in range(0, len(LETTERS)):
if gcd(a, len(LETTERS)) == 1:
for b in range(0, len(LETTERS)):
message = affine_cipher(cipher, 'DECRYPT', (a, b))
if detectEnglish.isEnglish(message): return (a, b, message) return (None, None) 19 key = (7, 2)
cipher = affine_cipher(message, 'ENCRYPT', key)
print('\n\nCipher text: ' + cipher)
message = affine_crack(cipher)
print('\n\nKey = [{0}, {1}]'.format(message[0], message[1]))
print('\nPlain text after crack: ' + message[2]) 20 KẾT LUẬN
1. Kết quả đạt được
Bài tiểu luận tiến hành nghiên cứu giải quyết bài toán về mã hóa, giải mã
trên hệ mã cổ điển Affine. Từ việc giải quyết bài toán. Bài toán là nền tảng cho
nhiều ứng dụng quan trọng thực tế như quảng cáo nhắm mục tiêu, các hệ thống
cung cấp tiếp thị dịch vụ thương mại điện tử tới đúng người dùng, … 2. Hạn chế:
Nghiên cứu Hệ mã Affine chỉ sử dụng các ký tự là bảng chữ cái, bảng chữ
cái không lớn nên bị giới hạn bởi các bảng chữ cái
Dễ bị tấn công bằng cách phân tích tần số v à khó phòng ngừa.
Không có khả năng phục hồi văn bản gốc
3. Hướng phát triển
Thay thế Affine bằng hệ m
ã đối xứng khác an toàn hơn như (AES, DES)