TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

TRẦN VĂN DŨNG
BÀI TOÁN LOGARITH RỜI RẠC VÀ ỨNG DỤNG
TRONG MẬT MÃ KHOÁ CÔNG KHAI
LUẬN VĂN THẠC SỸ KỸ THUẬT
HÀ NỘI - 2008
TẬP ĐOÀN BƯU CHÍNH VIỄN THÔNG VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

TRẦN VĂN DŨNG
BÀI TOÁN LOGARITH RỜI RẠC VÀ ỨNG DỤNG
TRONG MẬT MÃ KHOÁ CÔNG KHAI
Ngành : Kỹ thuật điện tử
Mã số : 60.52.70
LUẬN VĂN THẠC SỸ KỸ THUẬT
Người hướng dẫn khoa học: GS.TS NGUYỄN BÌNH
HÀ NỘI - 2008
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
LỜI CẢM ƠN
Trước tiên, tôi xin chân thành cảm ơn GS.TS Nguyễn Bình, người trực tiếp
hướng dẫn, chỉ bảo, giúp đỡ tôi trong quá trình viết luận văn.
Tôi cũng muốn nói lời cảm ơn tới các thầy, cô giáo, Ban Giám đốc Học viện
Công nghệ Bưu chính Viễn thông, Khoa Quốc tế và sau đại học và các đồng nghiệp
đang cùng công tác tại Viễn thông Phú Thọ đã tận tình chỉ bảo và tạo mọi điều kiện
giúp đỡ, động viên tôi trong suốt quá trình học tập.
Cuối cùng tôi xin gửi lời cảm ơn đến bố mẹ, tất cả gia đình, bạn bè đã giúp đỡ
động viên tôi trong suốt quá trình học tập để tôi có được đến hôm nay.
Xin chân thành cảm ơn!.
Hà nội, 08-08-2008

2.3.2.Thuật toán bước đi lớn bước đi nhỏ ( Baby-step giant-step ) 15
2.3.3.Thuật toán của Pollard 15
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-ii-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
2.3.4.Thuật toán Pohlig – Hellman 16
2.3.5.Thuật toán tính chỉ số ( Index-Calculus) 17
2.3.5.1.Tính chỉ số trên GF(p) 18
2.3.5.2.Tính chỉ số trên GF(2n) 20
2.3.5.3. Sàng trường số đặc biệt SNFS 22
2.3.5.4. Sàng trường số tổng quát GNFS 22
CHƯƠNG 3 24
3.1.Hệ mật Pohlig – Hellman 24
3.2.Hệ mật Massey - Omura 28
3.3.Hệ mật Diffie - Hellman 38
3.3.1.Bài toán Diffie – Hellman: 38
3.3.2 Khởi tạo Diffie Hellman 39
3.3.3 Trao đổi khoá Diffie Hellman 39
3.4.Hệ mật trên đường cong Eliptic 40
3.4.1.Giới thiệu chung về đường cong Eliptic 40
3.4.1.1Quy tắc \“cộng\ 43
3.4.1.2Quy tắc phép nhân đôi 46
3.4.1.3.Bài toán Logarit rời rạc trên đường cong Eliptic (ECDLP) 46
3.4.2. Đường cong Eliptic trên trường hữu hạn: 47
3.4.2.1. Đường cong eliptic trên trường Fp ( p là số nguyên tố ) 47
3.4.2.2.Đường cong eliptic trên trường 48
3.4.2.3.Phép nhân đường cong 52
3.4.3.Xây dựng các hệ mật trên đường cong Elliptic 53
3.4.3.1.Mã hoá dữ liệu 53
3.4.3.2.Thao tác giải mã 54

Hình 3.9. Phép cộng trên đường cong Elliptic P+Q=R 44
Hình 3.10. Phép nhân đôi 46
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-v-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
DANH MỤC CÁC BẢNG
Bảng 1.1.So sánh độ an toàn giữa khóa bí mật và khóa công khai 10
Bảng 3.2.So sánh số lượng các thao tác đối với các phép toán trên đường cong Elliptic
trong hệ toạ độ Affine và hệ tọa độ chiếu 51
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-vi-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
DANH MỤC TỪ VIẾT TẮT
AES Advanced Encryption Standard Chuẩn mã dữ liệu tiên tiến
DES Data Encryption Standard Chuẩn mã dữ liệu
ECC Elliptic curves Cryptographically Hệ mật trên đường cong Elliptic
ECDLP Elliptic Curves Discrete Logarithm
Problem
Bài toán Logarith rời rạc trên đường
cong Elliptic
MDV Mã dịch vòng
MHV Mã hoán vị
MTT Mã thay thế
RSA Thuật toán RSA
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-vii-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
LỜI NÓI ĐẦU
Trong sự phát triển của xã hội loài người, kể từ khi có sự trao đổi thông tin
thì vấn đề bảo mật thông tin được đặt ra như một nhu cầu tất yếu. Tuy nhiên,

bao gồm mật mã khoá bí mật ( như DES, 3DES, RC4, AES…), mật mã khoá công
khai (RSA, DIFFIE – HELLMAN…). Mật mã khoá bí mật: quá trình mã hóa và giải
mã một thông điệp sử dụng cùng một mã khóa gọi là khóa bí mật (secret key)
hay khóa đối xứng (symmetric key). Do đó, vấn đề bảo mật thông tin đã mã hóa
hoàn toàn phụ thuộc vào việc giữ bí mật nội dung của mã khóa đã được sử dụng. Với
tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý hiện nay,
phương pháp mã hóa chuẩn (Data Encryption Standard – DES) đã trở nên không
an toàn trong bảo mật thông tin.
Nếu như vấn đề khó khăn đặt ra đối với các phương pháp mã hóa bí mật chính là
bài toán trao đổi mã khóa thì ngược lại, các phương pháp mã hóa khóa công khai
giúp cho việc trao đổi mã khóa trở nên dễ dàng hơn. Nội dung của khóa công
khai (public key) không cần phải giữ bí mật như đối với khóa bí mật trong các
phương pháp mã hóa bí mật. Vấn đề đặt ra đối với mật mã khoá công khai chính là
phải tìm ra được hàm mật mã là một hàm dễ tính toán, song việc tìm hàm ngược
(giải mã ) phải là rất khó khăn (đối với bất kỳ ai không được trao quyền giải mã). Ta
nhận thấy bài toán logarith rời rạc là một bài toán khó ( chưa có một thuật toán nào
hiệu quả để tính logarith rời rạc một cách tổng quát) trong khi bài toán ngược luỹ
thừa rời rạc lại không khó (có thể sử dụng thuật toán bình phương và nhân). Với
mục đích là nghiên cứu tìm hiểu các hệ mật mã khoá công khai được sinh ra dựa
trên bài toán logarith rời rạc để đánh giá mức độ bảo mật thông tin của các hệ mật
trên so với các hệ mật mã khác. Luận văn gồm 04 chương cụ thể như sau:
Chương 1: Tổng quan về mật mã học
- Khái quát về mật mã học.
- Trình bày tổng quát các hệ mật mã và phân loại, các phương pháp thám
mã.
- Ưu nhược điểm của các hệ mật mã.
Chương 2: Bài toán logarith rời rạc
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-2-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ

hướng nghiên cứu chuyên sâu vào từng lĩnh vực ứng dụng đặc thù với những đặc
trưng riêng. Ứng dụng của khoa học mật mã không chỉ đơn thuần là mã hóa và giải
mã thông tin mà còn bao gồm nhiều vấn đề khác nhau cần được nghiên cứu và giải
quyết
:
chứng thực nguồn gốc nội dung thông tin (kỹ thuật chữ ký điện tử), chứng
nhận tính xác thực về người sở hữu mã khóa (chứng nhận khóa công cộng), các
quy trình giúp trao đổi thông tin và thực hiện giao dịch điện tử an toàn
trên mạng Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các
hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu cầu đa
dạng của các hệ thống ứng dụng khác nhau trong thực tế, ví dụ như hệ thống bỏ
phiếu bầu cử qua mạng, hệ thống đào tạo từ xa, hệ thống quản lý an ninh của các
đơn vị với hướng tiếp cận sinh trắc học, hệ thống cung cấp dịch vụ
multimedia trên mạng với yêu cầu cung cấp dịch vụ và bảo vệ bản quyền sở hữu
trí tuệ đối với thông tin số
1.1.2.Sơ lược về mật mã học
Khoa học về mật mã (cryptography) bao gồm:
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-4-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
- Mật mã học (cryptography).
- Phân tích mật mã (cryptannalysis)
Mật mã học là khoa học nghiên cứu cách ghi bí mật thông tin nhằm biến bản
tin rõ thành các bản mã.
Phân tích mật mã là khoa học nghiên cứu cách phá các hệ mật nhằm phục hồi
bản rõ ban đầu từ bản mã. Việc tìm hiểu các thông tin về khoá và các phương pháp
biến đổi thông tin cũng là một nhiệm vụ quan trọng của phân tích mật mã.
Có ba phương pháp tấn công cơ bản của thám mã:
- Tìm khoá vét cạn.
- Phân tích thống kê.

7.Mật mã là chuyên ngành khoa học của Khoa học máy tính nghiên cứu về
các nguyên lý và phương pháp mã hoá. Hiện nay người ta đưa ra nhiều chuẩn an
toàn cho các lĩnh vực khác nhau của công nghệ thông tin.
8.Thám mã nghiên cứu các nguyên lý và phương pháp giải mã mà không
biết khoá. Thông thường khi đưa các mã mạnh ra làm chuẩn dùng chung giữa các
người sử dụng, các mã đó được các kẻ thám mã cũng như những người phát triển
mã tìm hiểu nghiên cứu các phương pháp giải một phần bản mã với các thông tin
không đầy đủ.
9.Lý thuyết mã bao gồm cả mật mã và thám mã. Nó là một thể thống nhất,
để đánh giá một mã mạnh hay không, đều phải xét từ cả hai khía cạnh đó. Các nhà
khoa học mong muốn tìm ra các mô hình mã hóa khái quát cao đáp ứng nhiều chính
sách an toàn khác nhau.
1.2.Các hệ mật và các phương pháp thám mã
1.2.1.Các hệ mật mã khoá bí mật
Hệ thống mã hóa bí mật là hệ thống mã hóa trong đó quy trình mã hóa và
giải mã đều sử dụng chung một khoá - khóa bí mật. Việc bảo mật thông tin phụ
thuộc vào việc bảo mật khóa.
Trong hệ thống mã hóa quy ước, thông điệp nguồn được mã hóa với mã khóa k
được thống nhất trước giữa người gửi A và người nhận B. Người A sẽ sử dụng mã
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-6-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
khóa k để mã hóa thông điệp x thành thông điệp y và gửi y cho người B;
người B sẽ sử dụng mã khóa k để giải mã thông điệp y này. Vấn đề an toàn bảo
mật thông tin được mã hóa phụ thuộc vào việc giữ bí mật nội dung mã khóa k.
Nếu người C biết được mã khóa k thì C có thể “mở khóa” thông điệp đã được mã
hóa mà người A gửi cho người B
.
Hình 1.1. Mô hình hệ thống mã khoá bí mật
Có 3 phương pháp chính trong mật mã khoá bí mật ( mật mã khoá riêng hay

các ứng dụng mã hóa và bảo vệ thông tin. RSA nhanh chóng trở thành chuẩn mã
hóa khóa công cộng trên toàn thế giới do tính an toàn và khả năng ứng dụng của
nó.
Một hệ thống khóa công cộng sử dụng hai loại khóa trong cùng một cặp
khóa: khóa công cộng (public key) được công bố rộng rãi và được sử dụng trong
mã hóa thông tin, khóa riêng (private key) chỉ do một người nắm giữ và được
sử dụng để giải mã thông tin đã được mã hóa bằng khóa công cộng. Các phương
pháp mã hóa này khai thác những ánh xạ f mà việc thực hiện ánh xạ ngược f
–1
rất khó so với việc thực hiện ánh xạ f. Chỉ khi biết được mã khóa riêng thì mới có
thể thực hiện được ánh xạ ngược f
–1
.Khi áp dụng hệ thống mã hóa khóa công
cộng, người A sử dụng mã khóa công cộng để mã hóa thông điệp và gửi cho người
B. Do biết được mã khóa riêng nên B mới có thể giải mã thông điệp mà A đã mã
hóa. Người C nếu phát hiện được thông điệp mà A gửi cho B, kết hợp với thông tin
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-8-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
về mã khóa công cộng đã được công bố, cũng rất khó có khả năng giải mã được
thông điệp này do không nắm được mã khóa riêng của B.
Hình 1.2. Mô hình hệ thống mã khoá công khai
1.2.3.Các phương pháp thám mã các hệ mật mã khoá bí mật
Trước tiên ta phân biệt các mức độ tấn công khác nhau vào các hệ mật. Sau
đây là một số loại thông dụng nhất.
Chỉ có bản mã:
Thám mã chỉ có xâu bản mã y.
Bản rõ đã biết:
Thám mã có xâu bản rõ x và xâu bản mã tương ứng y.
Bản mã được lựa chọn:

toàn

giữa

khóa

bí

mật

và

khóa

công
khai
Phương

pháp

mã
hoá bí mật
Phương

pháp

mã

hóa


bản

PGP

cũ
(kích

thước

tối

thiểu)
80 SKIPJACK 512
Short

DSS, PGP
“low

grade”
96 768 PGP

“high

grade”
112 3DES

với

2


H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
khóa công khai phải sử dụng mã khóa có độ dài lớn hơn nhiều lần mã khóa được
sử dụng trong mã hóa bí mật. Điều này được thể hiện rõ hơn qua đồ thị so sánh chi
phí cần thiết để công phá khóa bí mật và khóa công cộng trong Hình 1.3. Kích
thước mã khóa được tính dựa trên mô hình đánh giá, ước lượng chi phí phân tích
mật mã do Hội đồng Nghiên cứu Quốc gia Hoa Kỳ (National Research Council)
đề nghị [11].
Hình 1.3.Đồ thị so sánh chi phí công phá khoá bí mật và khoá công cộng
Trên thực tế, khóa công cộng dễ bị tấn công hơn khóa bí mật. Để tìm ra được
khóa bí mật, người giải mã cần phải có thêm một số thông tin liên quan đến các
đặc tính của văn bản nguồn trước khi mã hóa để tìm ra manh mối giải mã thay vì
phải sử dụng phương pháp vét cạn mã khóa. Ngoài ra, việc xác định xem thông
điệp sau khi giải mã có đúng là thông điệp ban đầu trước khi mã hóa hay không lại
là một vấn đề khó khăn. Ngược lại, đối với các khóa công cộng, việc công phá hoàn
toàn có thể thực hiện được với điều kiện có đủ tài nguyên và thời gian xử lý. Ngoài
ra, để có thể giải mã một thông điệp sử dụng phương pháp mã hóa khóa công
cộng, người giải mã cũng không cần phải vét cạn toàn bộ không gian mã khóa mà
chỉ cần khảo sát trên tập con của không gian này.
Bên cạnh đó, khóa công khai còn là mục tiêu tấn công đáng giá đối với những
người giải mã hơn các khóa bí mật. Khóa công cộng thường dùng để mã hóa các
khóa bí mật khi thực hiện việc trao đổi mã khóa bí mật. Nếu khóa công khai bị
phá thì các thông điệp sau đó sử dụng mã khóa này cũng bị giải mã. Trong khi đó,
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-11-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
nếu chỉ phát hiện được một mã khóa bí mật thì chỉ có thông điệp sử dụng mã khóa
này mới bị giải mã. Trên thực tế, mã khóa bí mật thường chỉ được sử dụng một lần
nên ít có giá trị hơn so với khóa công cộng. Tóm lại, mặc dù khóa công cộng được
dùng để mã hóa các thông tin ngắn nhưng đây lại là các thông tin quan trọng.
.

β β
>
thì ta có:
1 2 1 2
1
1 2
2
log ( . ) log log .
log ( ) log log .
α α α
α α α
β β β β
β
β β
β
+ = +
+ = −
(2.2)
Tính chất 2: Với
0
β
>
, x bất kỳ thì ta có:
log log .
x
x
α α
β β
=
(2.3)

thể tìm được một số nguyên tố x duy nhất thoả mãn:
β α
=
x
(2.5)
Ta có thể viết: log
α
β
= x.
Bài toán logarith rời rạc chính là bài toán tìm x.
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-13-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
2.2.2.Các tính chất cơ bản
Nếu
γ
là một phần tử sinh khác của Z
p
thì

log log .log .
γ γ α
β α β
=
(2.6)

log . log log .
γ γ γ
α β α β
= +

15
x 18 5 11 10 8 16 12 15 4 13 6 3 7 17 1 2 14 9
log
4
x 9 \ \ 1 8 7 3 \ 4 \ 6 \ \ \ \ 2 5 \
Từ bảng trên ta có: 2
13
≡
3 mod 19.
Nhìn chung đây là một bài toán rất khó khi p đủ lớn ( chẳng hạn p
≈
10
200
).
2.2.4.Nhận xét
So sánh giữa 2 bài toán logarith tuyến tính và logarith rời rạc trình bày ở trên
ta rút ra một số kết luận như sau:
- Đối với bài toán logarith tuyến tính: khi giải bài toán ngược thì đây cũng là
một bài toán khó giải nhưng ta có thể ước đoán được giá trị của nó trong một
khoảng xác định. Vì vậy nó vẫn là một bài toán dễ tìm ra lời giải.
- Đối với bài toán logarith rời rạc: ngoài tính khó giải của bài toán ngược ra
ta còn không thể ước đoán được giá trị của nó. Đây là một bài toán rất khó giải hiện
này không có thuật toán nào có hiệu quả để giải bài toán này. Do vậy các nhà
nghiên cứu mật mã học xây dựng các hệ mật có khả năng bảo mật cao dựa trên tính
khó giải của bài toán logarith rời rạc.
Tr n V n D ngầ ă ũ Lu n v n Th c s k thu tậ ă ạ ỹ ỹ ậ
-14-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
2.3.Các phương pháp giải bài toán logarith rời rạc
2.3.1.Thuật toán vét cạn

≤
i,j < m. Từ đó
α
x
=
α
im
α
j
hay
β
(
α
-m
)
i
=
α
j
. Vậy nên người ta
có thể lập bảng (j,
α
j
) với 0
≤
j < m.
Sau đó lần lượt tính
β
(
α

) phép toán tra bảng. Tựu chung là
nó có thời gian chạy O(
n
) phép toán nhóm.
2.3.3.Thuật toán
ρ
của Pollard
Đây là thuật toán ngẫu nhiên với cùng thời gian chạy như trong thuật toán
bước đi lớn bước đi nhỏ nhưng không cần đến không gian lưu trữ nhiều.
Nó chia nhóm G thành ba tập S
1
, S
2
, S
3
như nhau dựa trên tính chất dễ kiểm
nghiệm. Định nghĩa dãy các phần tử của nhóm x
0
, x
1
, x
2
, … với x
0
=1 như sau:
x
i+1
=
f
(x

i
S
2
Nếu x
i
S
3
-15-
H c vi n Công ngh B u chính Vi n thôngọ ệ ệ ư ễ
Dãy các phần tử của nhóm sẽ xác định hai dãy số nguyên a
0
, a
1,
a
2
, … và b
0
,
b
1,
b
2
, … thoả mãn x
i
=
.
ai bi
α β
với i
0

b
i+1
=
efd
=

1
mod
2 mod
i
i
i
b
n
b n
b
+





(2.11)
Người ta áp dụng thuật toán tìm chu trình của Floyd để tìm hai phần tử của nhóm x
i
và x
2i
sai cho x
i
= x

i
- b
2i
).log
α
β

≡
( a
2i
- a
i
) (mod n)
Với điều kiện là b
i

≠
b
2i
(mod n) thì chúng ta có thể dễ dàng giải phương trình đồng
dư này để tính ra log
α
β
. Trên thực tế thì xác xuất để cho b
i

≠
b
2i
(mod n) là rất

i
e
với 1
≤
i
≤
r và sau đó sử dụng thuật toán
Gauss làm việc với định lý phần dư Trung Hoa để tìm ra x mod n.
Mỗi số x
i
được tính theo các chữ số l
o
, l
1
, …, l
1
i
e −
trong biểu diễn p
i
phân rã
của x
i
= l
0
+ l
1
p
1
+ … + l

Nếu x
i
S
1
Nếu x
i
S
2
Nếu x
i
S
3
-16-