Lý thuyết số trong mã hóa thông tin

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

******

PHẠM THANH LÊ

LÝ THUYẾT SỐ

TRONG MÃ HÓA THÔNG TIN

Chuyên ngành: Phương pháp Toán sơ cấp

Mã số: 60.46.40

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng - Năm 2013

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: PGS.TS NGUYỄN GIA ĐỊNH

Phản biện 1: TS. NGUYỄN DUY THÁI SƠN

Phản biện 2: TS. HOÀNG QUANG TUYẾN

Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ khoa học, họp tại Đại học Đà Nẵng vào ngày 25 tháng 05

năm 2013.

Có thể tìm hiểu luận văn tại:

- Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư Phạm, Đại học Đà Nẵng.

1

MỞ ĐẦU

1. Lý do chọn đề tài

Mật mã là một ngành khoa học nghiên cứu các kỹ thuật toán

học nhằm cung cấp các dịch vụ bảo vệ thông tin. Đây là ngành khoa

học quan trọng, có nhiều ứng dụng trong đời sống – xã hội. Ngày

nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử dụng

ngày càng phổ biến trong các lĩnh vực khác nhau trên thế giới.

Mật mã hiện đại có những đòi hỏi mới mang tính nguyên tắc

hơn so với mật mã thường dùng trước đây. Những hệ thống mật mã

cũ khi biết được khoá lập mã của họ ta dễ dàng tìm ra khoá giải mã.

Các hệ thống mật mã hiện đại đã khắc phục được những nhược điểm

đó: công nghệ mã hóa mà phương pháp chung (thuật toán) là công

khai, còn việc triển khai thì cho phép thay đổi được theo một tham số

do từng người sử dụng tự ấn định (mỗi giá trị của tham số sẽ xác

định một cách mã hóa riêng), việc lập mã và giải mã chỉ có thể được

thực hiện khi biết được tham số đó. Một hệ mã như vậy không chỉ

đáp ứng được đòi hỏi của những chuyên gia về bảo mật thông tin, mà

còn rất phù hợp cho các ứng dụng mang tính toàn dân nơi mà người

sử dụng không hề có một chút nghiệp vụ về bảo mật và an toàn

thông tin nói chung.

Để có được những hệ mã đáp ứng các yêu cầu trên, người ta

dựa vào các công cụ Toán học, đặc biệt là các phương pháp của Lý

thuyết số. Có thể nói, lý thuyết số là một trong những kiến thức toán

học lâu đời nhất. Với sự phát triển của khoa học máy tính và công

nghệ thông tin, lý thuyết số đã đóng góp những ứng dụng thực tế bất

ngờ và quan trọng, đặc biệt trong lĩnh vực mã hóa thông tin.

2

Xuất phát từ tính thời sự của mã hóa thông tin và nhu cầu

muốn tìm hiểu về vai trò của lý thuyết số trong mã hóa thông tin,

chúng tôi quyết định chọn đề tài với tên gọi “Lý thuyết số trong mã

hóa thông tin” để tiến hành nghiên cứu. Ngày nay, công nghệ mã

hóa đã phát triển đến mức vượt ra ngoài khả năng thâu tóm của bất

cứ một tài liệu nào, cho nên đề tài này cũng chỉ có thể trình bày

những khía cạnh cơ bản nhất trong lĩnh vực mã hóa thông tin hiện

nay, cùng với những kiến thức toán học làm cơ sở cho nó. Chúng tôi

hy vọng đây là một tài liệu tham khảo tốt cho những người bắt đầu

tìm hiểu về Mã hóa thông tin và hy vọng một số ví dụ minh hoạ đặc

sắc góp phần làm phong phú thêm các kết quả trong lĩnh vực này.

2. Mục tiêu nghiên cứu

Nghiên cứu mã hóa thông tin qua các phương pháp mã hóa

dựa trên công cụ lý thuyết số.

3. Đối tượng và phạm vi nghiên cứu

3.1. Đối tượng nghiên cứu

Mã hóa thông tin và vai trò của lý thuyết số trong các

phương pháp mã hóa.

3.2. Phạm vi nghiên cứu

Mật mã học và các ứng dụng.

4. Phương pháp nghiên cứu

Đề tài này đã sử dụng các phương pháp nghiên cứu sau:

- Phương pháp nghiên cứu tư liệu gồm: Các tài liệu tham

khảo, các bài báo khoa học, các đề tài nghiên cứu có liên quan…

- Phương pháp tiếp cận lịch sử: Sưu tầm, phân tích và tổng

hợp tư liệu.

- Phương pháp tiếp cận hệ thống.

3

5. Ý nghĩa khoa học và thực tiễn của đề tài

- Đề tài đã tổng quan các kết quả của các tác giả đã nghiên

cứu liên quan đến mã hóa thông tin và vai trò của lý thuyết số trong

các phương pháp mã hóa nhằm xây dựng một tài liệu tham khảo cho

những ai muốn nghiên cứu về mã hóa thông tin.

- Đề tài đã chứng minh chi tiết và làm rõ một số mệnh đề,

cũng như đưa ra một số ví dụ minh họa đặc sắc nhằm làm cho người

đọc dễ dàng tiếp cận vấn đề được đề cập.

6. Cấu trúc luận văn

Mở đầu

Chương 1: Kiến thức cơ sở

Chương 2: Các khái niệm cơ bản của mã hóa và các hệ mã

đối xứng

Chương 3: Các hệ mã mũ và mã phi đối xứng.

Kết luận.

CHƯƠNG 1

KIẾN THỨC CƠ SỞ

1.1. PHÉP TÍNH ĐỒNG DƯ VÀ CÁC VẤN ĐỀ LIÊN QUAN

1.1.1. Số nguyên tố và định lý cơ bản của Số học

Định lý 1.1. Mọi hợp số n đều có ước nguyên tố nhỏ hơn n .

Định lý 1.2. Mọi số nguyên lớn hơn 1 đều phân tích được một

cách duy nhất dưới dạng tích các lũy thừa của các số nguyên tố khác

nhau, trong đó các thừa số được viết theo thứ tự không giảm.

Hệ quả 1.1. Nếu p là một số nguyên tố và p | ab thì ít nhất một

trong 2 số a, b phải chia hết cho p. Ước chung lớn nhất của 2 số tự

nhiên a, b được kí hiệu là UCLN(a, b) hay đơn giản là (a, b). Khi 2

4

số tự nhiên có ước chung lớn nhất là 1 thì chúng được gọi là nguyên

tố cùng nhau.

1.1.2. Thuật toán Euclid và mở rộng

a. Thuật toán Euclid

El. (Kết thúc?) Nếu b = 0, in ra a và kết thúc thuật toán.

E2. (Chia Euclid) Đặt r ← a mod b, a ← b, b ← r, và quay

về bước El.

b. Thuật toán Euclid mở rộng

Cho hai số nguyên không âm u, v. Tìm (u1,u2,u3) sao cho

(u, v) = u3 = uu1 + vu2

Trong tính toán, ta thêm vào các ẩn phụ (v 1,v2,v3), (t 1,t 2,t 3 )

và luôn có trong mọi bước các đẳng thức sau đây:

ut1 + vt2 = t3, uv1 + vv2 = v3, uu1 + vu2 = u3

Edl. (Xuất phát) Đặt (u1,u2,u3) ← (1,0,u), (v1,v2,v3) ← (0,1,v).

Ed2. (Kiểm tra v3 = 0 ?) Nếu v3 = 0, thuật toán kết thúc.

Ed3. (Chia, trừ). Đặt q ← 3

3

u

v

 

   

, và sau đó đặt

(t1,t 2,t 3) ← (u1,u2,u3) - q(v1,v2,v3),

(u1,u2,u3) ← (v1,v2,v3), (v1,v2,v3) ← (t1,t 2,t 3)

và quay về bước Ed2.

1.1.3. Phi - hàm Euler

Định nghĩa 1.2. Hàm Euler φ(n) là hàm xác định với mọi số

nguyên dương n, được định nghĩa là số các số nguyên dương không

vượt quá n và nguyên tố cùng nhau với n.

Hệ quả 1.2. Số p là nguyên tố khi và chỉ khi φ(p) = p – 1.

Tổng quát hơn, khi p là số nguyên tố và r là một số nguyên

dương bất kì thì: φ(p

r

) = p

r-1

(p-1) = p

r

(1 – 1/p).

5

Định lý 1.3. Hàm Euler là một hàm nhân tính, nghĩa là với m,

n là các số nguyên dương nguyên tố cùng nhau, ta có:

φ(m.n) = φ(m). φ(n).

Hệ quả 1.3. Giả sử

1 2

1 2 ...

k

a a a

k

n p p p  là phân tích của n thành

thừa số nguyên tố. Khi đó ta có:

1 2

1 1 1 ( ) 1 1 ... 1

k

n n

p p p

    

              

1.1.4. Phép tính đồng dư và phương trình đồng dư

Định nghĩa 1.3. Giả sử m là một số nguyên dương. Ta nói, hai

số nguyên a và b là đồng dư với nhau modulo m nếu m chia hết hiệu

a - b. Để chỉ a đồng dư với b modulo m, ta ký hiệu: a  b (mod m).

Phương trình đồng dư tuyến tính ax  b (mod m) thỏa mãn:

Khi UCLN(a,m) = 1 thì có ngay nghiệm x a

-1

b (mod m).

Khi UCLN(a,m) = g thì có hai khả năng xảy ra:

1. Nếu g chia hết b thì phương trình đã cho tương đương với

phương trình (a/g)x  (b/g)(mod m/g) và (a/g, m/g) = 1.

2. Nếu g không chia hết b thì phương trình vô nghiệm.

1.1.5. Định lý Fermat và các mở rộng

Định lý 1.4 (Định lý Fermat nhỏ). Nếu p là một số nguyên tố

còn a là một số nguyên thì a

p

 a (mod p). Nếu p không chia hết a

thì a

p - 1

 1(mod p).

Định lý 1.5 (Định lý mở rộng (Euler)). Nếu m là số nguyên

dương và a là số nguyên tố cùng nhau với m thì ( ) 1(mod ) m

a m 



Trong trường hợp riêng, khi m là số nguyên tố thì ( ) m = m-1

và ta có định lý Fermat nhỏ.

Hệ quả 1.4. Nếu (c, m) = 1 và a  b (mod φ(m)) với a, b là

các số tự nhiên, thì c

a

= c

b

(mod m).

6

Hệ quả 1.5. Nếu e, d là các số nguyên thỏa mãn e.d

e.d m   1(mod ( )) thì với mọi số c nguyên tố cùng nhau với m, ta có

(c

e

)

d  c (mod m).

1.1.6. Tính toán với đồng dư của luỹ thừa bậc lớn

Ngoài việc sử dụng hệ quả của Định lý Euler để tính toán

người ta còn thường hay sử dụng nhất là phương pháp bình phương

liên tiếp.

1.1.7. Định lý Phần dư Trung Hoa

Định lý 1.6. Giả sử m1, m2,…, mr là các số nguyên dương

nguyên tố cùng nhau từng đôi một. Khi đó, hệ phương trình đồng dư:

(mod ) i i x a m  , i = 1, 2, …, r

có nghiệm duy nhất modulo M = m1m2…mr

.

1.1.8. Thặng dư bình phương và ký hiệu Legendre

Định nghĩa 1.4. Cho số nguyên tố p. Số nguyên a được gọi là

thặng dư bình phương (mod p) nếu như a và p nguyên tố cùng nhau

và tồn tại số nguyên x thoả mãn phương trình x

2

≡ a (mod p).

Nguyên lý căn bậc 2. Một trong hai "nghiệm" của thặng dư

bình phương cũng là một thặng dư bình phương.

Định nghĩa 1.5 (Ký hiệu Legendre). Với số nguyên tố p > 2

và số nguyên bất kỳ a, số nguyên sau gọi là ký hiệu Legendre:

L(a,p) :=

a

p

    =

1

2

p

a



(mod p)

và L(a,p) :=

a

p

    =

0

1

-1











nếu a chia hết cho p

nếu a là một thặng dư bình phương

(mod p)

các trường hợp còn lại

7

Định nghĩa 1.6 (Ký hiệu Jacobi). Với số nguyên n=p1.p2 .. .pk

trong đó pi (i =

______

1, k ) là các số nguyên tố còn a nằm trong hệ thặng

dư thu gọn của n, số nguyên sau gọi là ký hiệu Jacobi:

J(a,n) = L(a,p1)L(a,p2) . . . L(a,pk )

Như vậy khi n là số nguyên tố thì J(a,n) = L(a,n).

1.2. LIÊN PHÂN SỐ

1.2.1. Khái niệm liên phân số

Định nghĩa 1.7. Cho một số hữu tỉ

a

b

với a, b nguyên và b >0.

Ta thực hiện thuật toán Euclid trên a, b. Giả sử ta được:

0 0 0

0 1 1 1 0

3 2 1 1 1 2

2 1

, (0 )

, (0 )

.......................

, (0 )

n n n n n n

n n n

a ba r r b

b r a r r r

r r a r r r

r r a

     

 

   

   

   



Như vậy, phân số

a

b

có thể viết:

1

1

1 1

1

1

o

o o o

o

n

n

a r

a a .... a

b b b

a

r

a

a



      



 

Cách viết như trên được gọi là biểu diễn số hữu tỉ

a

b

dưới

dạng liên phân số.

Để đơn giản, ta dùng cách viết

a

b

= [a0;a1,...,an]. Liên phân số

[a0;a1,...,an] được gọi là liên phân số hữu hạn (cấp n).

8

1.2.2. Giản phân

Định nghĩa 1.8. Cho liên phân số (hữu hạn hoặc vô hạn)

0 1 2  [ ; , ,...] a a a .

Ta gọi giản phân thứ k (hay cấp k) của liên phân số δ là phân

số k

k

k

p

q

  , trong đó pk và qk được xác định bởi:

0 0

0

1

p a

q

 



 

, 1 1 0

1 1

p a a 1

q a

   

 

,

1 2

1 2

k k k k

k k k k

p a p p

q a q q

 

 

   

  

, k = 2, 3, …

Mệnh đề 1.3. Trong hai giản phân liên tiếp δk-1, δk thì giản

phân cấp lẻ lớn hơn giản phân cấp chẵn.

Hệ quả 1.6. Các giản phân là các phân số tối giản.

Mệnh đề 1.4. Tập hợp các giản phân cấp chẵn hợp thành một

dãy hữu tỉ tăng cùng chỉ số, còn tập hợp các giản phân cấp lẻ hợp

thành một dãy hữu tỉ giảm khi chỉ số tăng.

Mệnh đề 1.5. Mỗi giản phân cấp chẵn đều nhỏ hơn mọi giản

phân cấp lẻ.

Mệnh đề 1.6. Tập hợp các giản phân của một liên phân số vô

hạn hợp thành một dãy Cauchy hữu tỉ.

Định nghĩa 1.9. Giá trị của liên phân số hữu hạn

  a a a 0 1 ; ,...,

n  là giá trị của giản phân cuối cùng

n

 của nó. Giá trị

của liên phân số vô hạn   a a a 0 1 ; ,..., ,... k  là giới hạn của dãy các

giản phân ( )

s s

 

của nó.

Hệ quả 1.7. Giá trị của một liên phân số lớn hơn mọi giản

phân cấp chẵn và nhỏ hơn mọi giản phân cấp lẻ của nó.

1.3. TRƯỜNG HỮU HẠN

1.3.1. Trường Fp: Với p là một số nguyên tố bất kì, vành

 

__ __ _______

0,1,..., 1 p    p có cấu trúc một trường và trường này kí hiệu là Fp.

9

Tập các phần tử khác không 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à * Fp

.

1.3.2. Cách xây dựng trường Fq từ trường Fp

Giả sử Fq là một trường hữu hạn gồm q phần tử, đặc số p. Vì

Fq chứa phần tử 1 nên nó sẽ chứa trường Fp như một trường con. Do

Fq là trường hữu hạn nên nó là mở rộng hữu hạn của Fp, nghĩa là một

không gian vectơ r chiều trên Fp. Từ đó suy ra rằng Fq gồm p

r

phần

tử, tức là q = p

r

.

Định lí 1.7. Giả sử Fq là trường hữu hạn với q = p

r

phần tử.

Khi đó, mọi phần tử của Fq đều thỏa mãn phương trình X

q

– X = 0.

Định lí 1.8. Mọi trường hữu hạn đều có phần tử sinh. Nếu g là

một phần tử sinh của

* Fq

thì g

s

là phần tử sinh của

* Fq khi và chỉ khi

(s, q–1) = 1. Như vậy, tồn tại tất cả φ(q–1) phần tử sinh của

* Fq

.

1.4. ĐƯỜNG CONG ELLIPTIC

1.4.1. Khái niệm đường cong elliptic

Định nghĩa 1.10. Đường cong elliptic trên trường K là tập hợp

các điểm (x, y) thỏa mãn phương trình:

y

2

+ a1xy + a3y = x

3

+ a2x

2

+ a4x + a6 , với a1, a2, a3, a4, a6 ∈ K (1.1)

với một điểm O gọi là điểm vô cùng.

Đường cong elliptic với phương trình (1.1) được thêm vào các

điểm tại vô cùng để có đường cong tương ứng trong không gian xạ

ảnh: y

2

z + a1xyz + a3yz

2

= x

3

+ a2x

2

z + a4xz

2

+ a6z

3

(1.2)

1.4.2. Đường cong elliptic trên trường số thực

Đường cong elliptic E trên trường số thực  là tập hợp các

điểm (x, y) thỏa mãn công thức:

y

2

= x

3

+ a4 x + a6 , với a4, a6 ∈  (1.3)

cùng với một điểm O vô cùng.