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


LỜI CẢM ƠN

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 đỡ em 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 Đạ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.

Hà Nội, tháng 05 năm 2015
Sinh viên

2

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

7

2.1. Bài toán logarit rời rạc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2. Diffie-Hellman trao đổi khóa bảo mật . . . . . . . . . . . . . . . . . . . . . . . .

9

2.3. Hệ thống mật mã khóa công khai ElGamal . . . . . . . . . . . . . . . . . . . . .

11

2.4. Bài toán logarit rời rạc khó đến mức nào? . . . . . . . . . . . . . . . . . . . . . .

14

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

16

2.6.

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


Quá trình thực hiện đề tài đã bước đầu làm quen với việc nghiên cứu
khoa học, tìm hiểu sâu hơn về bài toán logarit rời rạc và ứng dụng của nó
trong mật mã.
3. Nhiệm vụ nghiên cứu
Đề tài nghiên cứu nhằm đi sâu khai thác ứng dụng của bài toán
logarit rời rạc trong mật mã.
4. Phương pháp nghiên cứu
Đề tài được hoàn thành dựa trên sự kết hợp các phương pháp: nghiên
cứu lí luận, phân tích, tổng hợp, đánh giá.
5. Cấu trúc khóa luận
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: Tổng quan về lí thuyết nhóm.
Chương 2: Bà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∗p (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∗p 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 ∈ F∗p thỏa mãn 1.a = a với mỗi a ∈ F∗p .
• Mỗi a ∈ F∗p có một nghịch đảo a−1 ∈ F∗p thỏa mãn a.a−1 = a−1 .a = 1.
• Phép nhân có tính kết hợp: a.(b.c) = (a.b).c với mọi a, b, c ∈ F∗p .
• Phép nhân có tính giao hoán: a.b = b.a với mọi a, b ∈ F∗p .
Giả sử thay phép nhân trong F∗p bằng phép cộng trong Fp . Ta cũng thay 0

a (b c) = (a b) c với mọi a, b, c ∈ G.

Ngoài ra, nếu phần tử thỏa mãn
[Luật giao hoán] a b = b a với mọi a, b ∈ G,
thì nhóm này được gọi là một nhóm giao hoán hoặc một nhóm abel.
Nếu G có hữu hạn phần tử, ta nói rằng G là một nhóm hữu hạn. Bậc
của G là số phần tử trong G; nó được ký hiệu là |G| hoặc #G.
Ví dụ 1.1. Nhóm có mặt khắp nơi trong toán học và trong khoa học tự
nhiên. Dưới đây là một số ví dụ:
(a) G = F∗p và

= phép nhân. Phần tử đơn vị là e = 1, phần tử

nghịch đảo tồn tại. G là một nhóm hữu hạn có bậc p − 1.
(b) G = Z/N Z và

= phép cộng. Phần tử đơn vị là e = 0 và phần

tử đối của a là −a. G là một nhóm hữu hạn có bậc N .
3


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

(c) G = Z và

Nguyễn Hồng Nhung

= phép cộng. Phần tử đơn vị là e = 0 và phần tử đối



a b
c d

d
ad−bc
−c
ad−bc

=

−b
ad−bc
a
ad−bc

Chú ý rằng G là nhóm không giao hoán, ví dụ
1 1

1 1

0 1

0 1

.

1 1

1 1

Nếu x là một số nguyên âm, ta định nghĩa g x là (g −1 )−x . Cho x = 0, tập
g 0 = e là các phần tử đơn vị của G.
Định nghĩa 1.2. Cho G là một nhóm và cho a ∈ G là một phần tử của
nhóm. Giả sử tồn tại một số nguyên dương d với ad = e. Số d nhỏ nhất
như vậy được gọi là bậc của a. Nếu không có d như vậy, thì a được cho là
có bậc vô hạn.
Mệnh đề 1.1. Cho G là nhóm hữu hạn. Thì mỗi phần tử của G có bậc
hữu hạn. Ngoài ra, nếu a ∈ G có bậc d và nếu ak = e, thì d | k.
Chứng minh. Vì G là hữu hạn, dãy
a, a2 , a3 , a4 , ...
cuối cùng phải có một sự lặp lại. Nghĩa là tồn tại số nguyên dương i và j
với i < j sao cho ai = aj . Nhân cả hai vế với a−i và áp dụng tính chất của
nhóm ta được ai−j = e. Khi i − j > 0, chúng ta gọi d là số mũ dương nhỏ
nhất thỏa mãn ad = e.
Bây giờ giả sử rằng k ≥ d thỏa mãn ak = e. Chúng ta chia k cho d
để có được
k = dq + r với 0 ≤ r < d
Sử dụng ak = ad = e, chúng ta nhận thấy rằng
e = ak = adq+r = (ad )q ar = eq ar .
Nhưng d là số mũ dương nhỏ nhất của a thỏa mãn ad = e, vì vậy chúng
ta phải có r = 0. Do đó k = dq, vậy d | q.
5

✷


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

Nguyễn Hồng Nhung


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 tiên về
giao thức trao đổi khóa chung do Diffie và Hellman, dựa trên bài toán
logarit rời rạc trong trường hữu hạn Fp .
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ử nguyên thủy g. Điều này có nghĩa mỗi phần tử khác không của Fp
tương đương với một lũy thừa của g. Đặc biệt, bằng định lí Fermat nhỏ có
g p−1 = 1, và lũy thừa nhỏ nhất của g là bằng 1. Tương tự, dãy các phần
tử
1, g, g 2 , g 3 , ..., g p−2 ∈ F∗p
là một dãy đầy đủ các phần tử trong F∗p theo một thứ tự.
Định nghĩa 2.1. Cho g là một căn nguyên thủy của Fp và cho h là phần
tử khác không của Fp . Bài toán logarit rời rạc (DLP) là bài toán về tìm số

7


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

Nguyễn Hồng Nhung

mũ x sao cho
g x ≡ h mod p.


mod 56509


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

Nguyễn Hồng Nhung

cho đến khi ta tìm thấy một số lũy thừa đó bằng 38679. Ta thấy rằng
logg (h) = 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 điều
này là không đúng. Nói chung, đối với bất kỳ g ∈ F∗p và bất kỳ h ∈ F∗p , 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 mod 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 . Bài toán logarit
cho G là bài toán có đầu vào là hai phần tử g ∈ G và h ∈ G. Tìm số
nguyên x thỏa mãn:
g g g ... g = h
x lần

2.2.

Diffie-Hellman trao đổi khóa bảo mật
Thuật toán Diffie-Hellman trao đổi giải quyết tình trạng khó xử sau.

Alice và Bob muốn chia sẻ một khóa bí mật để sử dụng trong một thuật
toán mã hóa đối xứng, nhưng phương tiện truyền thông duy nhất của họ
không an toàn. Mỗi mẩu thông tin mà họ trao đổi được quan sát bởi đối

B cho Alice. Lưu ý rằng Eve thấy được các giá trị của A và B, 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 ≡ Ba

mod p và B ≡ Ab

Alice tính toán này

mod p

Bob tính toán này

Các giá trị mà họ tính toán, A và B tương ứng, thực sự giống nhau, khi
đó
A ≡ B a ≡ (g b )a ≡ g ab ≡ (g a )b ≡ Ab ≡ B

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 ≡
627347 mod 941. Tương tự như vậy, Bob chọn khóa bí mật b = 781 và tính
B = 691 ≡ 627781 mod 941 . Alice gửi Bob số 390 và Bob 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à B = 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à Bob đều có
thể tính toán số
470 ≡ 627347.781 ≡ Ab ≡ B a

giá trị đã biết g a mod p và g b mod p.
Rõ ràng là DHP không khó hơn DLP. Nếu Eve có thể giải quyết
DLP, thì cô ấy có thể tính toán số mũ bí mật a và b của Alice và Bob cắt
ra từ các giá trị A = g a và B = g b , và sau đó nó rất dễ dàng cho cô ấy để
tính toán khóa chia sẻ g ab của họ. (Trong thực tế, Eve cần phải tính toán
duy nhất a và b.) Nhưng chuyện này là chưa rõ ràng.

2.3.

Hệ thống mật mã khóa công khai ElGamal
Trong phần này chúng ta mô tả phiên bản hệ thống mật mã khóa

công khai của ElGamal (PKC ElGamal) được dựa trên bài toán logarit rời
11


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

Nguyễn Hồng Nhung

rạc cho F∗p .
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.
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∗p là khó khăn, và cô ấy cần một phần tử g mô đun

Nguyễn Hồng Nhung

ông ấy về m, là cặp số (c1 , c2 ), ông ấy gửi cho Alice.
Làm thế nào để Alice giải mã bản mã (c1 , c2 ) của Bob? Từ đó Alice
biết là cô có thể tính toán
x ≡ ca1

mod p,

và x−1 mod p. Tiếp theo Alice nhân c2 với x−1 , và được giá trị kết quả là
bản rõ m. Để biết tại sao, ta mở rộng giá trị của x−1 .c2 và thấy rằng
x−1 .c2 ≡ (ca1 )−1 .c2

mod p, khi x ≡ ca1

≡ (g ab )−1 .(mAk )

mod p,

mod p, khi c1 ≡ g k , c2 ≡ mAk

≡ (g ab )−1 .(m(g a )k )

mod p, khi A ≡ g a

mod p,

mod p,

≡ m mod p, khi số hạng g ak triệt tiêu lẫn nhau.

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

Nguyễn Hồng Nhung

Cuối cùng, cô ấy tính toán
c2 x−1 ≡ 57.14 ≡ 331

mod 467

và phục hồi thông tin bản rõ m.
Chú ý 2.4. Trong các hệ thống mật mã ElGamal, bản rõ là một số nguyên
m giữa 2 và p − 1, trong khi văn bản viết thành mật mã bao gồm hai số
nguyên c1 và c2 trong cùng khoảng biến thiên.

2.4.

Bài toán logarit rời rạc khó đến mức nào?
Ký hiệu bậc đã được phát minh ra để thực hiện những ý tưởng chính

xác. Nó phổ biến khắp toán học và khoa học máy tính và cung cấp một
cách tiện dụng để có được sự thu hút về độ lớn của con số.
Định nghĩa 2.4. (Kí hiệu bậc). Cho f (x) và g(x) là hàm số của x lấy giá
trị dương. Chúng ta nói rằng "f là O lớn của g" và viết
f (x) = O(g(x))
nếu có hằng số dương c và C sao cho
f (x) ≤ cg(x) với mọi x ≥ C.
Đặc biệt, chúng ta viết f (x) = O(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) = O(g(x)).
Mệnh đề 2.1. Nếu giới hạn

x3
Tương tự như vậy, chúng ta có x2 = O(2x ), khi đó
x2
lim
= 0.
x→∞ 2x
(Nếu bạn không biết giá trị của giới hạn này thì sử dụng quy tắc L’Hôpital
hai lần.)
Tuy nhiên, lưu ý rằng chúng ta có thể có f (x) = O(g(x)) ngay cả
khi giới hạn của f (x)/g(x) không tồn tại. Ví dụ, giới hạn
(x + 2)cos2 (x)
lim
x→∞
x
không tồn tại, nhưng
(x + 2)cos2 (x) = O(x), khi đó (x + 2)cos2 (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 = O(x2 ).

(b)5 + 6x2 − 37x5 = O(x5 ).

(c)k 300 = O(2k ).

(e)k 2 2k = O(e2k ).

(d)(lnk)375 = O(k 0.001 ).

g. Nếu một đáp án cho g x = h tồn tại, thì h sẽ xuất hiện trong dãy của
✷

bạn.

Mệnh đề 2.3. (Thuật toán Babystep-Giantstep của Shanks). Cho G là
một nhóm và cho g ∈ G là một phần tử có bậc N ≥ 2. Thì giải quyết bài
√
toán logarit rời rạc g x = h trong O( N .logN ) bước.
1. Cho n = 1 +

√

N , thì n >

√

N.

2. Tạo ra hai dãy,
Dãy 1 : e, g, g 2 , g 3 , ..., g n ,
2

Dãy 2 : h, h.g −n , h.g −2n , h.g −3n , ..., h.g −n .
16


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

Nguyễn Hồng Nhung


3

5763

12423

11 16360 16367

4

1128

13153

12 13259

7315

5

8431

7928

13

2549

6 16568


h.uk

k

gk

h.uk

17 10137 10230

25

4970

12260

18 17264

3957

26

9183

6578

19

4230


22 15501

5416

30 11969 12831

23

6854

13640

31

6045

4754

24 15680

5276

32

7583

14567

15774 16564

Định lý phần dư Trung Quốc mô tả giải pháp cho một hệ thống đồng

dư dồng thời. Đơn giản nhất là một hệ thống hai đồng dư,
x ≡ a mod m và x ≡ b mod n,

(2.3)

với gcd(m, n) = 1, trong đó trường hợp định lý phần dư của Trung Quốc
là một giải pháp độc đáo theo mô đun mn.
Ví dụ 2.7. Chúng ta tìm kiếm một số nguyên x đồng thời thỏa mãn cả hai
đồng dư
x≡1

mod 5 và x ≡ 9

mod 11.

(2.4)

Đồng dư đầu tiên cho chúng ta biết rằng x ≡ 1 mod 5 , vì vậy tất cả các
đáp án thỏa mãn đồng dư đầu tiên là tập hợp các số nguyên
x = 1 + 5y, y ∈ Z.

(2.5)

Thay thế (2.5) vào đồng dư thứ hai ở (2.4) cho
1 + 5y ≡ 9

mod 11, và do đó 5y ≡ 8 mod 11.



(2.8)

Chứng minh. Giả sử rằng đối với giá trị của i chúng ta đã tìm được
đáp án x = ci cho đồng dư đồng thời,
x ≡ a1 mod m1 , x ≡ a2 mod m2 , ..., x ≡ ai mod mi .

(2.9)

Ví dụ, nếu i = 1, thì c1 = a1 . Chúng ta sẽ giải thích làm thế nào để tìm
một đáp số cho thêm một đồng dư,
x ≡ a1 mod m1 , x ≡ a2 mod m2 , ..., x ≡ ai+1 mod mi+1 .
19


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

Nguyễn Hồng Nhung

Ý tưởng để tìm một đáp số có dạng
x = ci + m1 m2 ...mi y.
Chú ý rằng giá trị này của x vẫn thỏa mãn tất cả các đồng dư (2.9), chúng
ta chỉ cần chọn y do đó nó cũng thỏa mãn x ≡ ai+1 mod mi+1 . Nói cách
khác, chúng ta cần phải tìm một giá trị của y thỏa mãn
ci + m1 m2 ...mi y ≡ ai+1 mod mi+1 .
Ta có gcd(mi+1 , m1 m2 ...mi ) = 1 điều này hoàn thành chứng minh về sự
✷

tồn tại của đáp số.
Ví dụ 2.8. Chúng ta giải quyết đồng thời ba đồng dư

Giải đồng dư với mô đun phức hợp
Mệnh đề 2.4. Cho p là một số nguyên tố thỏa mãn p ≡ 3 mod 4. Cho a
là một số nguyên đồng dư x2 ≡ a mod p có một đáp án, như vậy tức là có
một căn bậc hai p. Thì
b ≡ a(p+1)/4

mod p

là một đáp án; nó thỏa mãn b2 ≡ a mod p.
Chứng minh. Cho g là một căn nguyên thủy mô đun p. Khi đó, a có
một căn bậc hai mô đun p và a là lũy thừa của g, nói a ≡ g 2k mod p. Bây
giờ chúng ta tính toán
b2 ≡ a

p+1
2

mod p, định nghĩa của b,

≡ (g 2k )

p+1
2

khi a ≡ g 2k ,

≡ g (p+1)k mod p
≡ a.(g p−1 )k mod p khi đó a ≡ g 2k mod p,
≡ a mod p khi đó g p−1 ≡ 1 mod p.
Do đó b thực sự là một căn bậc hai của a mô đun p.