1

Khóa luận tốt nghiệp

Trƣờng Đại Học Sƣ phạm Hà Nội
2 Khoa toán
== o0o==

đỗ ngọc tấn

cơ sở toán học của mã đối xứng

khoá luận tốt nghiệp đại học
Chuyên ngành: ứng dụng

Người hướng dẫn khoa học

ts. Trần minh tƣớc

hà nội – 2010

Đỗ Ngọc Tấn

K32 CN Toán


2

Khóa luận tốt nghiệp

Đỗ Ngọc Tấn

K32 CN Toán


MỤC LỤC
Lời cảm ơn ………………….………………………………………………. 1
Lời cam đoan ………………………………………………………………... 2
Mở đầu ………………………………………………………………………. 3

CHƢƠNG 1. CÁC KIẾN THỨC CHUẨN BỊ
1.1. Phép đồng dư và vấn đề liên quan ……………………………………… 5
1.2. Trường hữu hạn ………………………………………………………… 7
1.3. Trường số (mở rộng đại số) …………………………………………….. 11

CHƢƠNG 2. MÃ ĐỐI XỨNG
2.1. Một số thuật ngữ và khái niệm …………………………………………. 14
2.2. Một số hệ mã đối xứng
2.2.1. Khái niệm chung ……………………………………………………… 15
2.2.2. Hệ mã dữ liệu tiêu chuẩn DES ……………………………………….. 15
2.2.3.Tiêu chuẩn mã nâng cao AES và thuật toán Rijndael ………………… 21
Kết luận …………………………………………………………………….. 42
Tài liệu tham khảo ………………………………………………………….. 43



LỜI CẢM ƠN
Để hoàn thành Khóa luận tốt nghiệp của mình em đã nhận được sự
hướng dẫn, chỉ bảo tận tình của TS.Trần Minh Tƣớc, sự giúp đỡ, động viên
của các thầy cô trong tổ toán ứng dụng, cùng tất cả các thầy cô và các bạn
sinh viên trong khoa toán Trường Đại học sư phạm Hà Nội 2.

Em xin chân thành cảm ơn sự giúp đỡ quý báu, chỉ đạo tận tình của thầy
Trần Minh Tƣớc. Em cũng xin nói lời cảm ơn tới các thầy cô và các bạn
sinh viên.

Hà nội, tháng 5 năm 2010
Sinh viên thực hiện
Đỗ Ngọc Tấn



LỜI CAM ĐOAN
Tôi xin cam đoan nội dung khóa luận này hoàn toàn là kết quả nghiên
cứu của riêng tôi dưới sự chỉ dẫn khoa học của thầy Trần Minh Tước. Tôi xin
chịu mọi trách nhiệm về lời cam đoan của mình.

Tác giả
Đỗ Ngọc Tấn



MỞ ĐẦU
Lý do chọn đề tài
Có thể nói, mật mã đã xuất hiện từ thời cổ đại. Người ta cho rằng,
người đầu tiên áp dụng mật mã một cách có hệ thống để đảm bảo bí mật
thông tin quân sự là nhà quân sự thiên tài của La mã cổ đại Julius Caesar.
Ngày nay mật mã không chỉ được dùng trong quân sự và ngoại giao
mà còn được dùng trong rất nhiều các lĩnh vực khác như kinh tế, thương mại,
truyền thông… Thừa nhận ý nghĩa quan trọng mang tính sống còn của mật mã
trong thời đại ngày nay, đông đảo các chuyên gia đã đầu tư công sức để
nghiên cứu, tìm tòi những điều mới mẻ và hiệu quả của mật mã.

Trong công nghệ mã hóa thông tin về phương diện nghiên cứu và ứng
dụng, Mã đối xứng có một vai trò quan trọng. Mã đối xứng là hệ mã mà trong
đó việc lập mã và giải mã cùng sử dụng chung một chìa khóa mã.
Các loại mã đối xứng điển hình trong lý thuyết mật mã như: Hệ mã dữ
liệu tiêu chuẩn (DES), Mã hoá dữ liệu quốc tế (IDEA), Hệ mã SAFER, và gần
đây là sự ra đời của loại mật mã có tính bảo mật cao đó là mã AES do
Rijndael nghiên cứu.
Trong đề tài này tôi đặt vấn đề nghiên cứu về vai trò của toán học trong
lý thuyết mật mã nói chung thể hiện trong một số hệ mã đối xứng như DES,
AES và lấy tên đề tài là “Cơ sở toán học của mã đối xứng”.
Mục tiêu của đề tài
Tìm hiểu sơ qua về công nghệ mã hóa thông tin cụ thể là về một số hệ
mã đối xứng điển hình.
*Đối tƣợng, phạm vi và phƣơng pháp nghiên cứu
+ Đối tượng: Một số hệ mã đối xứng.



+ Phạm vi: Tìm hiểu về các hệ mã đối xứng và chú trọng đến cơ sở toán
học của các hệ mã đối xứng.
+ Phương pháp nghiên cứu: Nghiên cứu tư liệu, phân tích, tổng hợp dựa
trên các kết quả của số học và lý thuyết số.
Ý nghĩa lý luận và thực tiễn của đề tài
Trên thế giới nói đến thuật ngữ “Lý thuyết mật mã” hay “Công nghệ
mã hóa thông tin” không phải là một thuật ngữ xa lạ. Nhưng ở Việt Nam khi
nói đến thuật ngữ này là nói đến một vấn đề mới mẻ đối với sinh viên các
ngành khoa học cơ bản.
Là sinh viên ngành Toán, thực hiện đề tài “Cơ sở toán học của mã đối
xứng” chúng tôi sẽ được tiếp cận với một lĩnh vực khá mới mẻ của toán học
nhưng đã có ứng dụng hiệu quả trong thực tế. Việc thực hiện đề tài cũng là

một lần tập dượt nghiên cứu khoa học nhằm nâng cao tri thức của bản thân
đồng thời cũng để hiểu thêm về hoạt động nghiên cứu khoa học nói chung và
nghiên cứu toán nói riêng.



CHƢƠNG 1. CÁC KIẾN THỨC CHUẨN BỊ
1.1. Phép đồng dƣ và vấn đề liên quan
1.1.1 Số nguyên tố

* Ký hiệu Z là tập các số nguyên …, 
2,1,0,1,2...

và N là tập số tự

nhiên (tức là các số nguyên không âm 0,1,2,3...)

* Với a,b Z ta nói rằng b chia hết cho a nếu như b có thể viết
thành
tích của a với một số nguyên khác ; khi đó ta cũng có thể nói rằng a chia hết
b , hay a là một ước số của b , và ký
hiệu
+ Nếu a,b,c
Z và

b
c.

a|b
thì


a | bc

+ Nếu a | b và b | c
thì

a|c

+ Nếu a | b
và

a | b c

a|c
thì

a | b . Ta có một số tính chất sau:

+ Nếu a | b và a không chia hết c thì a không chia hết
cả

b c
và

* Số tự nhiên lớn hơn 1 mà không chia hết cho bất kỳ số tự nhiên nào
khác ngoài 1 và chính nó được gọi là số nguyên tố.
* Ước chung lớn nhất của 2 số tự nhiên a và b là số lớn nhất trong các
tập ước chung của 2 số đó, được ký hiệu là gcd(a,b)
Như vậy, nếu


d|a
và

d|b
thì

d | gcda,b

hay đơn giản là  a,b  .


* Khi 2 số tự nhiên có ước chung lớn nhất là 1 thì ta nói rằng chúng
nguyên tố cùng nhau.
1.1.2. Phi hàm EULER
Với nN số lượng các số tự nhiên bé hơn n và nguyên tố cùng
nhau
với n được kí hiệu là (n) . Hàm
(n)

được gọi là phi hàm Euler.

Ví dụ: (5) 4 , (6) 2, (7) 6


1.1.3. Phép tính đồng dƣ và phƣơng trình đồng dƣ
1.1.3.1. Phép tính đồng dƣ
Ta ký hiệu
m , nói cách
khác


a b

nếu như a và b sai khác nhau một bội của

(mod m) a

nếu a b chia hết cho m .

b (mod
m)
Quan hệ đồng dư modulo m dẫn đến việc phân hoạch tập số nguyên
thành m lớp, mỗi lớp chứa các số nguyên đồng dư với nhau theo modulo m
tập các lớp này được kí hiệu là Zm và chứa đúng m phần tử. Mỗi lớp trong
tập
Zm

có đúng một số nằm trong 0,1,...,

cho nên mỗi số nguyên

m 1

trong đoạn này được xem đại diện cho một lớp của tập Zm .
Một số tính chất của phép đồng dư
 a a (mod m);
 Nếu a b
(mod m)

thì b a (mod m) ;


 Nếu a b
(mod m)

và b c
(mod m)

thì a c (mod m) ;

 Nếu a b (mod m) , c d (mod m) thì
a c b d
(mod m) ,

a.c b.d (mod m)

Như vậy ta có thể tự do thực hiện các phép tính số học thông thường
trên tập Zm .
Nếu x là một phần tử trong Zm
sao cho

và gcd (x, m) 1 thì tồn tại
các số

u,v


u.x
v.m

1, tức là


u.x 1(mod m) , nên người ta nói x có
nghịch
1
1
x
hay
.
đảo ( trong Zm ) là u và thường ký hiệu phần tử nghịch đảo là
x
Tập các phần tử trong
Zm

mà có nghịch đảo thường được ký hiệu là

*

Z m rõ ràng tập này có số phần tử nghịch đảo bằng (m) , và trên tập
này
ngoài các phép cộng, trừ, nhân ta còn có thể đưa vào phép chia


Nếu a b (mod m) , c d (mod m) với gcd (c,
a.c 1 b.d 1 (mod
m)  1 thì
m)


Ví dụ: Với

ta có 7 4(mod9)

Z9  0,1,2,3,...,8 Z9 
1 và
*1,2,4,5,7,8
 ,

cho phép chia của 2 cho 7 (trong Z* ) được thực hiện như sau:
9
2

2.7 1 4.2 8(mod 9)
7
Ta đương nhiên cũng có 2
7.8(mod 9)

vì 7.8 56 6.9 2

1.1.3.2. Phƣơng trình đồng dƣ tuyến
tính
Khi gcd (a, m)
1

ax b (mod m)

(tức a là phần tử của Z* ) thì ta có ngay nghiệm
m

1

x a b (mod m) . Khi gcd (a, có 2 khả năng xảy ra:
m) g

+ phương trình có nghiệm khi g chia hết b , vì rằng khi ấy phương
trình đã cho tương đương với phương trình (a / g)x b / g (mod m trong
/ g)
đó hệ số a / g là số nguyên tố cùng nhau với m / g
+ phương trình vô nghiệm nếu g không chia hết b , vì hiệu của 2 số
chia hết cho g thì không thể là một số không chia hết cho g .
1.2. TRƢỜNG HỮU HẠN
1.2.1.

Trƣờng Fp
Với p là một số nguyên bất kì, trên tập các lớp đồng dư modulo p tức

là Z ta có thể thực hiện được các phép tính cộng, trừ, nhân. Khi p là số
p

nguyên tố thì với mỗi phần tử khác không




Zp

ta luôn tìm được phần tử


nghịch đảo



1


nghĩa

Z
theo

1

 .

1(mod p) và do đó có thể

thực hiện

p

được phép chia (cho các phần tử khác 0 ), theo nghĩa sau: :
. 1
Khi đó Z p có cấu trúc của một trường và ta kí hiệu trường này là
trường Fp . Tập các phần tử khác 0 của trường này lập thành một nhóm đối
với phép nhân và được kí hiệu là F * . Như vậy:
p


F * F \ 0 1,2,..., p 1.
p
p
Từ nay, khi nói đến trường Fp hay nhóm F p* ta luôn hiểu rằng p là
một số nguyên tố.
Chú ý : Nếu p không là nguyên tố thì vẫn có thể định nghĩa một tập con bao

gồm các phần tử khả nghịch của Z và cũng ký hiệu là Z *p .
p

*
Một phần tử g
nếu như tập
được gọi là phần tử sinh của nhóm

Fp
F* p

các lũy thừa của g cũng chính là nhóm này, tức là 2 tập sau đây trùng nhau

g, g

2

,..., g

p 1

1,2,..., p 1

(không tính đến thứ tự).
Rõ ràng, một phần tử chỉ có thể là phần tử sinh khi mọi lũy thừa của nó
với bậc nhỏ hơn

( p 1) , bậc của nhóm, không phải là đơn vị. Ngược lại,
một


phần tử mà có lũy thừa bậc nào đó (nhỏ hơn hẳn ( p 1) ) bằng đơn vị
thì
không thể là phần tử sinh. Dễ thấy rằng một phần tử mà không sinh ra cả
nhóm thì lũy thừa của nó cũng sẽ sinh ra một nhóm con và, theo Định lý
Lagrange, ta biết rằng bậc của một nhóm con phải là ước của số lượng các
phần tử có trong nhóm chứa nó (tức là ước của ( p 1) ). Như vậy muốn
kiểm
tra xem một phần tử nào đó có phải là phần tử sinh hay không chỉ cần nâng nó
lên lũy thừa với bậc là ước của

( p  và xem xét: nếu tất cả lũy thừa này đều
1)

khác 1 thì nó là phần tử sinh (ngược lại thì không phải).


Người ta chứng minh được rằng nếu g là một phần tử sinh của nhóm
*

F p còn b là một số nguyên tố cùng nhau với ( p
thì g b cũng là phần tử
 1)
sinh của nhóm F * . Cho nên, số các phần tử sinh của
nhóm
p

các số nguyên tố với ( p  tức là bằng ( p 1).
1)

*


Fp

đúng bằng số


Cho phần tử sinh g F * . Khi ấy mọi
phần tử
p

h
có thể được biểu

F* p

diễn dưới dạng một lũy thừa nào đó của g . Tuy nhiên vấn đề tìm ra số x để
có được biểu diễn h  là vô cùng gian nan, và được mang danh là bài toán
gx
logarit rời rạc. Một điều thú vị là tính khó giải của bài toán này không làm
cho người ta khó chịu, mà ngược lại làm vui lòng các nhà mã hóa (một trong
những ứng dụng vào tin học sẽ được nói đến ở phần sau).
1.2.2.

Trƣờng F r
2
Đây cũng là loại trường có hữu hạn phần tử, nhưng có bản chất khác

biệt so với loại trường hữu hạn đã xem xét ở trên.
Ta kí hiệu F2


x

là tập các đa thức với hệ số nằm trong trường F2 (đã

xét ở trên). Có thể liệt kê ra rằng tập này có hai đa thức bậc 0 (là hai hằng số
0,1) hai đa thức bậc 1 là ( x
và

x 1), tức là có 4 đa thức bậc không vượt
quá

1 , và khó khăn lắm ta mới có thể nhận ra rằng, với mỗi số tự nhiên n , có tất

cả

đa thức với bậc không vượt quá x với dạng tổng quát là:

2 n1
n
an x n  a
n1  ... a1x a0 , ai F2 .
1
x

Hai đa thức được cộng hoặc nhân với nhau theo quy tắc thông thường,
chỉ lưu ý là các hệ số là các phần tử của trường

F2 , trong đó 1 1 0.

Ví dụ: (x 2 x 1)(x 2 x) (x 4 x3 x2 ) (x3 x2

x) x4 x.


Đa thức
gọi là
bất khả
quy (trên
một
trường
nào đó)
nếu nó
không
thể
phân tích thành của các đa thức bậc nhỏ hơn (với các hệ số trên trường đã
nói).
Ví dụ: x 2 2, x 2 là những đa thức bất khả quy trên trường số hữu tỷ Q ,
2
nhưng trên trường số thực R thì chỉ có đa thức x2  là đa thức bất khả quy.
2
Trên trường F ta
2
có
2

2
là khả quy ( vì x2 1
) còn
x
2
1

(x 1)

x x là đa thức bất khả quy (đây là đa thức bậc hai duy nhất bất khả
1


quy). Trong tập đa thức bậc 3 chỉ có hai đa thức bất khả quy là
3

2

3

x x 1, x x 1.
Tương tự như trên Z , trên
tập

F2 xta cũng đưa vào phép tính đồng dư

modulo một phần tử (tức là một đa thức) nào đó, và khi ấy F2

x

sẽ được

phân thành các lớp với các đại diện là đa thức bậc thấp hơn đa thức ta đã lấy
làm modulo.
Ví dụ: Nếu lấy đa thức x3 x (bất khả quy) làm modulo thì tập
1
F x/ x x 1 gồm các đa thức nhỏ hơn bậc 3 cụ thể là tập:

3

2

0,1, x, x 1, x

2

2

2



2

, x 1, x x, x x 1 , trong đó đại
diện của phần tử 0
chính là đa thức chọn làm modulo, nghĩa là

x3 x 1 0 . Trên tập
này ta có

thể thực hiện các phép cộng, trừ, nhân thông thường với lưu ý rằng
x3 x 1vì điều này tương
đương với

(trên F2 ).
x 3 x
1 0


Ví dụ: (x 2 x 1)(x 1) x 3 1 (x 1) 1
2
x(mod x x 1) .
Ngoài ra trên tập

F2  x / x3 x 1 ta còn thấy rằng.
4

3

2

x x .x (x 1).x x x .
Trong trường hợp chung , người ta chứng minh được rằng, với mỗi đa
thức bất khả quy

Pd
(x)

với bậc d , tập hợp F2 x/ Pd
(x)

là một trường chứa


đúng
d
2


phần tử, kí hiệu là F2
d

đa thức với bậc không vượt quá

mỗi phần tử của nó được thể hiện bằng một
d 1

Người ta cũng chứng minh được rằng tập các phần tử khác 0 của
trường F , được kí hiệu là F * , cũng lập thành một nhóm và được sinh bởi
d
d
2

2

một phần tử nào đó, tức là có cấu trúc tương tự như nhóm F * . Phần tử sinh
p


của nó cũng phải có các lũy thừa bậc là ước của (2  khác đơn vị, và số
d
1)
lượng phần tử sinh trong nhóm này là
 (2d

1) .

*


*

2

2

Ta dễ thấy rằng x là phần tử sinh của F 3 F 8 . Thật vậy g
ta có
với
x
2

2

3

4

4

2

5

4

g x , g x 1, g x x x, g x .x x
x  1
6


6

3

3

2

2

7

6

g x x .x (x 1) x 1, g x .x x
x 1

3

Một phần tử của nhóm F * được gọi là chính phương (perfect square) nếu
2d
như nó là bình phương của một phần tử khác trong nhóm.
Như vậy, hoàn toàn tương tự như trên ta có thể xây dựng các trường
hữu hạn dạng F * , với p là số nguyên tố bất kì (thay vì với p 2 )
d
p
Khi p 2 , có thể chỉ ra rằng một phần tử chính phương khi và chỉ
khi
( p  chính là đơn vị.
lũy thừa của nó với bậc d

1)
2
1.3. Trƣờng số (mở rộng đại số)
Cho đa thức với các hệ số nguyên
f (x) an x

n

... a1x 1, ai Z

 an1
n1
Số thỏa mãn phương
trình

f
được gọi là nghiệm của đa thức f .
()
0

2