TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 KHOA TOÁN

NGUYỄN HỒNG NHUNG

BÀI TOÁN LOGARIT RỜI RẠC VÀ ỨNG DỤNG TRONG MẬT MÃ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng

Người hướng dẫn khoa học TS Trần Vĩnh Đức

Hà Nội - 2015

Em xin chân thành cảm ơn Thầy giáo Trần Vĩnh Đức đã tận tình hướng dẫn, giúp đỡ cm
trong suốt thời gian thực hiộn khóa luận.
Em xin chân thành cảm ơn các thầy, các cô trong tổ ứng dụng-khoa Toán, trường Dại học sư
phạm Hà Nội 2 đã tạo mọi điều kiện giúp đỡ em hoàn thành khóa luận này.


Em xin chân thành cảm ơn gia đình và bạn bè đã tạo mọi điều kiện thuân lợi cho em trong
quá trình thực hiện khóa luận.

Em xin chân thành cảm ơn.
LỜI CẢM ƠN
Hà Nội, tháng 05 năm 2015 Sinh viên

Nguyễn Hồng Nlmng

Em xin cam đoan, dưới sự hướng dẫn của Thầy giáo Trần Vĩnh Dức khóa luận "Bài toán
logarit rời rạc và ứng dụng trong mật mã"
được hoàn thành không trùng với bất kỳ đề tài nào khác.
Trong quá trình hoàn thành khóa luận, em đã thừa kế những thành tựu của các nhà khoa

Ngoài phần mở đầu, kết luận, danh mục tài liệu tham khảo thì khóa luận bao
gồm 2 chương:
Chương 1: Tong quan về lí thuyết nhóm.
Chương 2: Dài toán logarit rời rạc và ứng dụng trong mật mã.


Chương 1
Tổng quan về lý thuyết nhóm
Chương này giới thiộu tổng quan một vài kốt quả của lý thuyết nhóm có ứng
dụng trong bài toán logarit rời rạc.
Trước hết, ta nói về lũy thừa các phần tử trong F* (với Fp = {0,1, ...,p — 1}, p
nguyên tố là một trường) lũy thừa chỉ đơn giản là việc lặp lại phép nhân. Chúng ta nhấn
mạnh một số đặc trưng quan trọng của phép nhân trong F* và một vài tính chất cơ bản.
Các tính chất này là:
•

Có một phần tử 1 G thỏa mãn l.a = a với mỗi a G F*.

•

Mỗi a G F* có một nghịch đảo a~l G F* thỏa mãn a.a~l = a~l.0, = 1.

•

Phép nhân có tính kết hợp: a.(b.c) = (a.b).c với mọi a, 6, c G F*.

•

Phcp nhân có tính giao hoán: a.b = b.a với mọi a, b G F*.


Ví dụ 1.1. Nhóm có mặt khắp nơi trong toán học và trong khoa

#G.
học tự

nhiên. Dưới đây là m,ột số ví dụ:
(a) G = F* và * = phép nhân. Phần tử đơn vị ỉ,à

e = 1,phần

tử

nghịch đảo tồn tại. G ỉà một nhóm hữu hạn có bậc p — 1.
(b) G = 'LỊN7J và * = phép cộng. Phần tử đơn vị là e — 0 và phần tử đối của a là
—a. G ỉ,à một nhóm, hữu hạn cố bậc N.


Kìióa luận tốt nyỉiiệp
(c) G = z và * = phép cộng. Phần tử đơn

vị là e = 0

và phần hi đối

không phải

là một nhóm,

phép nhân


G tốt
và cho
X là số nguycn dương. Khi đóg x có nghĩa làNguyễn Hồng
ta áp dụng phép toán nhóm X lần tới phần tử g ,
g x = g * g * g * .. .*g
^
V
^
X lần lặp lại
Nếu X là một số nguycn âm, ta định nghĩa gx là
g° = e là các phần

{g~1)~x. Cho X =

0, tập

tử đơn vị của G.

Định nghĩa 1.2.

Cho G là một nhỏm, và cho a

phần

£ G là

một

tử của
tại một số nguyên dương d, với a d = e. số d nhỏ nhất



Kìióa luận tốt nyỉiiệp
Chính xác hơn, cho n = |ơ| ỉà bậc của G và cho d

là bậc của a, tức

Nguyễn Hồng

là, a d là số mủ dương nhỏ nhất của a bằng e. Khi đó
a n = e và d, I n.
Chứng minh. Chúng ta cho chứng minh đơn giản trong trường hợp G là giao
hoán.
Vì G là hữu hạn, chúng ta có thể liột kc các phần tử của nó như sau
G — {gi, 92,

9n}-

Bây giờ chứng ta nhân mỗi phần tử của G với a để có được một tập mới, chúng ta gọi là
Sa,
= {ữ *
2

* ... * g

n

= 01 * 02 * ■ ■ • * 9n

■

nhân với (gi ★ §2 * ... * 9n)~l được an = e. □


Chương 2
Bài toán logarit rời rạc và ứng dụng trong mật
mã
2.1.

Bài toán logarit rời rạc
Bài toán logarit rời rạc là bài toán xuất hiện ở nhiều dạng, bao gồm cả các dạng

mod p mô tả trong phần này và các dạng đường cong elliptic hiộn đang được sử dụng
rộng rãi trong thực tế. Các đề xuất đầu ticn về giao thức trao đổi khóa chung do Diffic
và Hcllman, dựa trcn bài toán logarit rời rạc trong trường hữu hạn ¥p.
Cho p là một số nguyên tố (lớn). Chúng ta biết rằng tồn tại một phần tử nguycn
thủy g. Điồu này có nghĩa mỗi phần tử khác không của ¥p tương đương với một lũy
thừa của g. Dặc biệt, bằng định lí Fermat nhỏ có gP-1 _ ^ lũy thừa nhỏ nhất của g là
bằng 1. Tương tự, dãy các phần tử
h g , g 2 , g 3 , - , g p ~ 2 e Fp
là một dãy đầy đủ các phần tử trong F* theo một thứ tự.


>

Dôi khi, vì sự cụ thể, ta đề cập đến “các” logarit rời rạc như các số nguyên X nằm giữa
0 và p — 2 thỏa mãn g x = h mod p.
Chú ý 2.2. Không khó để chứng minh rằng
log g (ab) = log g (a) + log g (b) với mọi a,b G F*.
Trong thuật ngữ toán học, logarit rời rạc logg là phép đẳng cấu nhóm

từ F* đến z/ ( p — 1)Z.
Ví dụ 2.1. Số p = 56509 là số nguyên tố, và ta kiểm, tra xem, g =
2 có là một căn nguyên thủy mô đun p. Làm, thế nào để tính
toán ỉogarit rời rạc của h = 38679? Rỗ ràng phương pháp duy
nhất ỉ,à tính toán


Kìióa luận tốt nyỉiiệp
Nguyễn Hồng
cho đến khi ta tìm, thấy một số lũy thừa đó bằng 38679. Ta thấy rằng log (J Ợi) =
11235, có thể xác minh điều này bằng cách tính toán 211235 mod 56509 và kiểm tra
rằng nó bằng 38679.
Chú ý 2.3. Phát biểu của chúng ta trong bài toán logarit rời rạc bao gồm, các
giả định rằng cơ số g là một căn nguyên thủy m,ô đun p, nhưng diều này là không
đúng. Nói chung, đối với bất kỳ g G

và bất kỳ h £ ¥*, bài

toán logarit rời rạc là xác định một số mũ X thỏa mẫn g x = h mocl p, giả sử
rằng tồn tại X.
Định nghĩa 2.2. Cho G là một nhóm, với phép nhân *. Dài toán logarit cho G là

A = g a mod p vhD = g b mod p
Alice tính toán này

Bob tính toán này

Họ tiếp tục trao đổi các giá trị tính toán, Alice gửi cho Bob A và Bob gửi D cho Alicc.
Lưu ý rằng Evc thấy được các giá trị của A và D, vì chúng được gửi qua các kênh
truyền thông không an toàn.
Cuối cùng, Bob và Alice một lần nữa sử dụng số nguyên bí mật của họ để tính
toán
A' = Da mod p và D' = Ab mod p
s
'-----------V----------'
----------V---------'
Alice tính toán này

Bob tính toán này

Các giá trị mà họ tính toán, A và D tương ứng, thực sự giống nhau, khi đó
A' = D a = (g l ’Ỵ = g ab = (g“) b = A h = D' mod p.
Giá trị chung này là chìa khoá trao đổi chúng.
Ví dụ 2.2. Alice và Bob đồng ý sử dụng số nguyên tố p = 941 và căn nguyên thủy
g = 627. Alice chọn khóa bí mật a = 347 và tính A = 390 = 62 7347 mod 941. Tương
tự như vậy, Dob chọn khóa bí mật b = 781 và tính D = 691 = 627781 mod 941 .
Alice gửi Bob số 390 và Dob gửi Alice số 691. Cả hai truyền đi được thực hiện
trên một kênh khổng an toàn, vì vậy cả hai A = 390 và D = 691 được xem, xét
công khai. Các số a = 347 và b = 781 không được truyền đi mà giữ bí mật. Sau
đó, Alice và Dob đều có thể tính toán số
470 = 62 7347'781 = A b = B a mod 941,
vậy 470 là chia sẻ bí mật của họ.


ElGamal (PKC ElGamal) được dựa trên bài toán logarit rời rạc cho F*.
PKC ElGamal là ví dụ đầu tiên của ta về một hệ thống mật mã khóa công khai.
Alice bắt đầu bằng việc xuất bản thông tin bao gồm một khóa công khai và một thuật
toán. Khóa công khai chỉ đơn giản là một con số, và các thuật toán là phương pháp mà
Bob mã hóa thông tin của mình bằng cách sử dụng khóa công khai của Alice. Alice
không tiết lộ khóa riêng của mình. Các khóa riêng cho phép Alice giải mã các thông tin
đã được mã hóa bằng khóa công khai của mình.


Kìióa luận tốt nyỉiiệp
Nguyễn Hồng
Vì PKC ElGamal, Alice cần một số nguyên tố lớn p mà bài toán logarit rời rạc
trong F* là khó khăn, và cô ấy cần một phần tử g mô đun p lớn (nguyên tố). Alice chọn
một số bí mật để làm khóa riêng của cô, và cô ấy tính toán con số
A = g a mod p.
Chú ý giống Diffie-Hellman trao đổi khóa. Alice công bố khóa công khai Ả của cô và
khóa riêng cô ấy giữ bí mật một mình.
Bây giờ giả sử Bob muốn mã hóa một thông tin bằng khóa công khai A của
Alicc. Ta sõ cho rằng thông tin m của Bob là một số nguycn giữa 2 và p. Dể mã hóa ra,
đầu tiên Bob chọn ngẫu nhiên số k khác mô đun p. Bob sử dụng k để mã hóa một và chỉ
một thông tin, và sau đó ông đã loại bỏ nó. Số k được gọi là một chìa khóa không lâu,
vì nó tồn tại duy nhất nhằm mục đích mã hóa một thông tin.
Bob lấy klioá công khai thông tin 771 của ông ấy, chọn ngẫu nhiên chìa khóa k
tạm thời, khóa A Alice công khai và sử dụng chúng để tính toán hai con số
Ci = gk mod p và c2 = mAk mod p.
(Hãy nhớ rằng g và p là các tham số công khai, vì Bob cũng biết giá trị của chúng.) Văn
bản viết thành mật mã của Bob, nghĩa là, mã hoá của
Ông ấy về ra, là cặp số (ci,c2), ông ấy gửi cho Alice.
Làm thế nào để Alice giải mã bản mã (ci,c2) của Bob? Từ đó Alice biết là cô có
,


Kìióa luận tốt nyỉiiệp
Nguyễn Hồng
Eve biết tham số p và (/ công khai, và cô cũng biết được giá trị của A = ga mod p vì
khóa công khai A của Alice được mọi người biết đến. Nếu Eve có thể giải quyết bài
toán logarit rời rạc, cô ấy có thể tìm thấy a và giải mã thông tin. Nếu không thì nó sẽ
xuất hiện khó khăn cho Eve để tìm ra bần rõ.
Ví dụ 2.3. Alice sử dụng số nguyên tố p = 467 và

căn nguyên thủy g = 2.

Cô chọn a = 153 là chìa khóa cá nhân của mình


Kìióa luận tốt nyỉiiệp
Nguyễn Hồng
Định nghĩa 2.4. (Kí h i ệ u bậc). Cho /(;x ) v à g ( : x ) ỉ , à h à m , s ố của X l ấ y g i á
trị dương. Chúng ta nói rằng "f ỉà o ỉớn của g " và viết
f(x) = ơ(g(x))
nếu có hằng số dương c và c sao cho
f ( x ) < c g ( x ) với mọi X > c.
Dặc biệt, chúng ta viết f(x) = 0(1) nếu f(x) bị chặn với m,ọi X > c.
Các mệnh đề tiếp theo cho một phương pháp mà đôi khi có thể được sử
dụng để chứng minh rằng f(x) = 0(g(x)).
Mệnh đề 2.1. Nếu giới hạn
/0*0
lim
x->oo g[x)
tồn tại (và là hữu hạn), thì f(x) = 0(g(x)).


Kìióa luận tốt nyỉiiệp
Nguyễn Hồng
Chứng minh. Giả sử L là giới hạn. Theo định nghĩa của giới hạn, cho bất kỳ e >
0 và một hằng số Ct sao cho

/O)

< € với mọi X > Ct.
9( x )

-L


(x + 2)cos 2 (x) = ơ(x), khi đó (x + 2)cos 2 (x) < X + 2 < 2x với mọi X > 2.
Ví dụ 2.5. Dưới đây là một vài ví dụ kí hiệu về o lớn.
(a)x2 + ựx = 0(x2).
(,c)k 300 = 0(2 k ).
(d)(ỉnkf 75 = O(k omi ).

(6)5 + 6x2 — 37x5 = ơ(x5).
(e)k 2 2 k = ơ(e 2k ).
(f)N ỉ0 2 N = 0(e N ).


2.5.

Kìióa luận tốt nyỉiiệp

Nguyễn Hồng

Thuật toán va chạm cho DLP

Trong phần này, chúng ta mô tả một thuật toán logarit rời rạc do Shanks. Nó là
một thuật toán ví dụ về sự va chạm, hoặc giao ở giữa. Thuật toán của Shanks làm viộc
trong nhóm bất kỳ.
Chúng ta bắt đầu bằng cách nhắc lại thời gian chạy của các thuật toán để giải
quyết DLP.
Mệnh đề 2.2. (Giới hạn tầm, thường cho DLP). Cho G ỉ,à một nhổm, và cho g £
G là một phần tử có bậc N. (Nhớ lại rằng diều này cố nghĩa ỉ,à = e và không
có lũy thừa dương của g nhỏ hơn tuơng đương với phần tử đồng nhất e.) Khi
đó bài toán logarit rời rạc
9X = h (2.2)
có thế được giải quyết trong O(N) bước, mà mỗi bước bao gồm phép nhân với

347

2

6181

13357

3

5763

12423

4

1128

13153

5

8431

7928

6 16568

1139



4230

9195

20

9880

13628

21

9963

10126

22 15501

5416

23

13640

6854

24 15680

5276

14 16911

10221

15

4351

16289

16

1612

4062

k

h.uk

k

g

25

4970

12260


4754

32

7583

14567

Bảng 2.1: Babystcp-giantstcp để giải 9704a’ = 13896 mod
17389
Ví dụ 2.6. Chúng ta minh họa phương pháp Baby step-giantstep của Shanks
bằng cách sử dụng nỏ đê giải quyết bài toán ỉogarit rời rọ,c
g x = h trong F* với g — 9704, h — 13896, và p = 17389.
Số 9704 có bậc 1242 trong F^7389. Dặt n = ịy/ 1242J + 1 và u = g~ n = 9704-36 =
2494. Bảng 2.1 dẫy các giá trị của g k và h.u k khỉ k = 1,2,... Từ
bảng, chúng ta tìm, thấy sự va chạm,

Nguyễn Hồng


Kìióa luận tốt nyỉiiệp

Nguyễn Hồng

97047 = 14567 = 13896.249432 trong F17389.
Dằng cách sử dụng m,ột thực tế rằng 2494 = 9704-38, chúng ta tính toán 13896 =
9704\2494“32 = 97047.(970436)32 = 9704115íl trong F17389.
Do đỏ X = 1159 giải quyết bài toán 9704x trong Fi7389.

2.6.