BỘ GIÁO DỤC VÀ ĐÀO TẠO
LÊ THANH PHÚC
VIỆN ĐẠI HỌC MỞ HÀ NỘI
LUẬN VĂN THẠC SỸ
CÔNG NGHỆ THÔNG TIN
CHUYÊN NGÀNH CÔNG NGHỆ THÔNG TIN
BÀI TOÁN LOGARITHM RỜI RẠC VÀ HỆ MẬT
ELGAMAL CÓ SỬA ĐỔI
LÊ THANH PHÚC
2015-2017
HÀ NỘI - 2017
BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN ĐẠI HỌC MỞ HÀ NỘI
LUẬN VĂN THẠC SỸ
BÀI TOÁN LOGARITHM RỜI RẠC VÀ HỆ MẬT
ELGAMAL CÓ SỬA ĐỔI
LÊ THANH PHÚC
CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ: 60.48.02.018
NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. NGUYỄN BÌNH
HÀ NỘI - 2017
LỜI CAM ĐOAN
Luận văn thạc sĩ đánh dấu cho những thành quả, kiến thức tôi đã tiếp thu đƣợc
trong suốt quá trình rèn luyện, học tập tại trƣờng. Tôi xin cam đoan luận văn “Bài
toán Logarithm rời rạc & Hệ mật ElGamal có sửa đổi” đã đƣợc hoàn thành bằng
quá trình học tập và nghiên cứu của tôi dƣới sự hƣớng dẫn, góp ý và chỉnh sửa của
GS. TS. Nguyễn Bình.
Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề đƣợc trình bày là
những tìm hiểu và nghiên cứu của cá nhân tôi hoặc là trích dẫn các nguồn tài liệu và
một số trang web hợp pháp đƣợc đƣa ra ở phần Tài liệu tham khảo.
Tôi xin cam đoan những lời trên là sự thật và chịu mọi trách nhiệm trƣớc thầy
cô và hội đồng bảo vệ luận văn thạc sĩ.
Hà Nội, ngày 12 tháng 12 năm 2017
HỌCVIÊN
Lê Thanh Phúc
i
LỜI CẢM ƠN
Học viên xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện
Đại học Mở Hà Nội và Viện công nghệ thông tin đã mang lại cho học viên kiến
thức vô cùng quý giá và bổ ích trong suốt quá trình học tập chƣơng trình cao học tại
trƣờng. Đặc biệt học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo GS.TS
Nguyễn Bình- Học viện Bƣu chính viễn thông đã định hƣớng khoa học và đƣa ra
những góp ý, gợi ý, chỉnh sửa quý báu, quan tâm, tạo điều kiện thuận lợi trong suốt
quá trình nghiên cứu hoàn thành luận văn này.
Cuối cùng, học viên xin chân thành cảm ơn các bạn bè đồng nghiệp, các bạn
học Viên lớp CNTT khóa 2015 - 2017, những ngƣời đồng hành trong suốt khóa học
và có nhiều góp ý bổ ích cho tôi. Cảm ơn gia đình và ngƣời thân đã quan tâm, giúp
đỡ và chia sẻ với học viên trong suốt quá trình học tập.
Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi những
thiếu sót nhất định. Học viên rất mong nhận đƣợc những sự góp ý quý báu của thầy
cô và các bạn.
Một lần nữa học viên xin đƣợc gửi lời cảm ơn chân thành và sâu sắc.
Hà Nội, ngày 12 tháng 12 năm 2017
HỌCVIÊN
Lê Thanh Phúc
ii
MỤC LỤC
LỜI CAM ĐOAN ....................................................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT ................................................v
DANH MỤC CÁC BẢNG BIỂU ............................................................................. vi
DANH MỤC CÁC HÌNH VẼ.................................................................................. vii
MỞ ĐẦU .....................................................................................................................1
CHƢƠNG 1. TỔNG QUAN VỀ BÀI TOÁN LOGARITHM RỜI RẠC VÀ CÁC
HỆ MẬT MÃ ..............................................................................................................4
1.1.
Tổng quan về bài toán logarithm rời rạc [1] ....................................................4
1.1.1. Bài toán Logarithm trên trƣờng số thực R .................................................4
1.1.2. Bài toán Logarithm trên trƣờng hữu hạn....................................................5
1.1.3. Thuật toán logarithm rời rạc.......................................................................8
1.1.3.1.
Phƣơng pháp đơn định .....................................................................8
1.1.3.2.
Thuật toán Adleman .......................................................................10
1.1.3.3.
Thuật toán vét cạn ..........................................................................11
1.1.3.5.
Thuật toán Shank ...........................................................................11
1.1.3.6.
Thuật toán tính logarithm rời rạc đối với nhóm cyclic ..................13
1.1.3.7.
Tính chỉ số trên GF(p) ....................................................................14
1.1.3.8.
Tính chỉ số trên GF(2n) ..................................................................15
1.2.
Tổng quan mật mã học [4, Tr.11] ...................................................................17
1.3.
Vấn đề về mã hóa [4, Tr.12-15] ......................................................................18
1.3.1. Khái niệm mật mã ....................................................................................18
1.3.2. Khái niệm về mã hóa................................................................................19
1.3.3. Phân loại mã hóa [4, Tr.20-97] ................................................................20
1.3.3.1.
Hệ mã hóa khóa đối xứng ..............................................................20
1.3.3.2.
Hệ mã hóa khóa bất đối xứng ........................................................24
Hệ mật đƣờng cong Eliptic ...............................................................................30
Hệ mã hóa RSA [4, tr.74-79]............................................................................31
Hệ mã hóa Paillier ............................................................................................32
iii
1.4.
Lý thuyết độ phức tạp của thuật toán [1] ........................................................33
1.5.
Kết luận chƣơng 1 ...........................................................................................36
CHƢƠNG 2. XÂY DỰNG HỆ MẬT ELGAMAL CÓ SỬA ĐỔI ..........................38
2.1.
Hệ mật mã Elgamal [2, tr.5]............................................................................38
2.1.1. Thuật toán mật mã ElGamal cổ điển ..........................................................38
2.2.
Hệ mã hóa ElGamal sửa đổi ...........................................................................43
2.2.1. Thuật toán thứ nhất [5] ...............................................................................43
2.2.2. Thuật toán thứ hai [3, tr.17-20]...................................................................45
2.3.
Chƣơng trình thực nghiệm hệ mã hóa công khai Elgamal sửa đổi .................49
2.4.
Kết luận chƣơng 2 ...........................................................................................51
CHƢƠNG 3. PHÂN TÍCH HIỆU NĂNG AN TOÀN CỦA HỆ MẬT ELGAMAL
CÓ SỬA ĐỔI & ỨNG DỤNG TRONG KỸ THUẬT MÃ HÓA PGP ĐỂ BẢO
MẬT EMAIL ............................................................................................................52
3.1
Đánh giá Hệ mật ElGamal [5] ........................................................................52
3.2
Hệ mật ElGamal sửa đổi: ................................................................................53
3.3
Tìm hiểu kỹ thuật mã hóa PGP sử dụng hệ mã hóa khóa công khai Elgamal,
RSA trong mã hóa Email [13] ...................................................................................55
3.3.1. Giới thiệu về hệ mã hóa PGP ...................................................................55
3.3.2. Các thuật toán sử dụng trong PGP ...........................................................55
3.4
Tổng kết chƣơng 3 ..........................................................................................69
KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU TIẾP THEO .........................................70
1.
Hạn chế:....................................................................................................70
2.
Hƣớng phát triển ......................................................................................70
TÀI LIỆU THAM KHẢO .........................................................................................71
Tiếng Việt .............................................................................................................71
Tiếng nƣớc ngoài ..................................................................................................71
Internet ..................................................................................................................71
iv
DANH MỤC CÁC THUẬT NGỮ, CHỮ VIẾT TẮT
STT
Từ viết tắt
Tiếng Anh
Tiếng Việt
1
CA
Certificate Authority
Cơ quan chứng thực chữ ký số
2
DS
Digital Signatures
Chữ ký số
3
DSA
Digital Signature Algorithm
Giải thuật chữ ký điện tử
4
DES
Data Encryption Standard
Chuẩn mã hóa dữ liệu
5
EMAIL
Electronic Mail
Thƣ điện tử
6
ID
7
RSA
Rivest, Shamir and Adleman
8
PGP
Pretty Good Privacy
9
PKI
Public Key Infrastructure
Cơ sở hạ tầng khóa công khai
10
SHA
Secure Hash Algorithm
Giải thuật băn an toàn
11
SSL
Secure Socket Layer
Giao thức an ninh thông tin
12
UCLN
Gcd
Ƣớc chung lớn nhất
13
XCB
14
NSA
Chỉ danh ngƣời dùng trên mạng
Giải thuật mã hóa công khai
Phần mềm mã hóa dữ liệu và xác
thực
Xyclic cục bộ
National Security Agency
v
Cơ quan An ninh Quốc gia Mỹ
DANH MỤC CÁC BẢNG BIỂU
Trang
Bảng 1.1. Các giá trị của y = 2x mod 19 trên Z*19 .................................................... 05
Bảng 1.2. Các giá trị log2x(mod 19) trên Z*19 ......................................................... 06
Bảng 1.3. Bài toán logarithm rời rạc trên Z*19......................................................... 07
Bảng 1.4. Bảng chi phí thời gian phân tích sốnguyên n ra thừa số nguyên tố ......... 34
Bảng 3.1. Bảng so sánh tốc độ mã hóa .................................................................... 53
Bảng 3.2. Bảng so sánh tốc độ giải mã .................................................................... 53
Bảng 3.3. Bảng kết quả so sánh thời gian mã hóa của hệ mật trƣớc và sau sửa đổi 54
vi
DANH MỤC CÁC HÌNH VẼ
Trang
Hình 1.1. Đồ thị hàm số y=ax và y = logax ............................................................. 05
Hình 1.2. Quá trình mã hoá và giải mã .................................................................... 20
Hình 1.3. Sơ đồ hoạt động của mã hóa khóa đối xứng ............................................ 21
Hình 1.4. Sơ đồ hoạt động của mã hóa khóa bất đối xứng ...................................... 25
Hình 1.5. Mã hoá thông điệp sử dụng khoá công khai ............................................ 26
Hình 1.6. Giải mã thông điệp sử dụng khoá riêng của ngƣời nhận ......................... 26
Hình 1.7. Hệ mật Omura- Massey xây dựng trên bài toán lôgarith rời rạc ............. 29
Hình 1.8. Quá trình truyền tin sử dụng hệ mật Omura – Massey ............................ 29
Hinh 2.1. Hệ mã Emlgamal ...................................................................................... 40
Hình 2.2. Sơ đồ chứng nhận khóa công khai ........................................................... 42
Hình 2.3. Giao diện sinh khóa .................................................................................. 49
Hình 2.4. Kết quả sinh khóa ..................................................................................... 50
Hình 2.6. Mã hóa và giải mã .................................................................................... 50
Hình 3.1. Quá trình mã hóa một thông điệp trong PGP ........................................... 56
Hình 3.2. Quá trình giải mã một thông điệp trong PGP........................................... 58
vii
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Cùng với sự phát triển của công nghệ thông tin và truyền thông, mạng máy
tính đang trở thành một phƣơng tiện điều hành thiết yếu trong mọi lĩnh vực hoạt
động của xã hội. Việc trao đổi thông tin và dữ liệu trong môi trƣờng mạng ngày
càng trở nên phổ biến và đang dần thay thế các phƣơng thức truyền tin trực tiếp.
Khi ngày càng nhiều thông tin đƣợc trao đổi thì nhu cầu về bảo mật thông tin là một
vấn đề đặt ra cho nhiều ngành, lĩnh vực và nhiều quốc gia...Để bảo vệ các thông tin
khỏi sự truy cập trái phép cần phải kiểm soát đƣợc những vấn đề nhƣ: thông tin
đƣợc tạo ra, lƣu trữ và truy nhập nhƣ thế nào, ở đâu, bởi ai và vào thời điểm nào.
Giải quyết các vấn đề trên, kỹ thuật mật mã hiện đại phải đảm bảo các dịch vụ an
toàn cơ bản: (1) bí mật (Confidential); (2) xác thực (Authentication); (3) đảm bảo
tính toàn vẹn (Integrity).
Hệ mật mã ra đời nhằm đảm bảo các dịch vụ an toàn cơ bản trên nhƣ: hệ mật
mã với khóa sở hữu riêng (Private Key Cryptosystems), hệ mã với khóa bí mật
(Secret Key Cryptosystems), hệ mã truyền thống (Conventional Cryptosystems) đều
là những hệ mật mã sử dụng mã khóa đối xứng. Hệ mật mã với khóa công khai cho
phép ngƣời sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa
chung bí mật trƣớc đó; mật mã hóa khóa công khai đƣợc thiết kế sao cho khóa sử
dụng trong quá trình mã hóa khác biệt với khóa sử dụng trong quá trình giải mã;
khóa sử dụng dùng để mã hóa và ngƣợc lại, tức là hai khóa này có quan hệ với nhau
về mặt toán học nhƣng không thể suy diễn đƣợc ra nhau. Một trong những thuật
toán mã khóa công khai đƣợc phát triển dựa trên Hệ mật mã ElGamal cho phép giải
quyết tốt các yêu cầu bảo mật thông tin thực hiện đồng thời việc xác thực về nguồn
gốc và tính toàn vẹn của thông tin. Luận văn sẽ trình bày về hệ mật mã ElGamal và
xem xét các biến thể của nó.
2. Mục tiêu, đối tƣợng, phạm vi và phƣơng pháp nghiên cứu
Mục tiêu nghiên cứu: Tìm hiểu hoạt động của hệ mật mã khóa công khai và
các biến thể thuật toán ElGamal để đƣa ra sửa đổi đối với hệ mật. Đánh giá tính bảo
1
mật thông tin, xác thực về nguồn gốc thông tin, xác thực về tính toàn vẹn của thông
tin của hệ thống.
Đối tượng nghiên cứu: Hệ mật mã ElGamal là đối tƣợng chính nghiên cứu của
đề tài nhằm phát hiện các phƣơng pháp tấn công qua đó tìm hiểu các ứng dụng thử
nghiệm đánh giá mã hóa với thuật toán ElGamal.
Phạm vi nghiên cứu: Đề tài nghiên cứu và đánh giá hiệu quả tính an toàn của
hệ mật ElGamal sửa đổi. Xây dựng hoặc tìm hiểu các thuật toán thử nghiệm trên
chữ ký số giúp tăng tính an toàn cho chữ ký số Elgamal/ RSA.
Phương pháp nghiên cứu
* Phương pháp lý thuyết
- Tìm hiểu nghiên cứu về mật mã, cơ sở toán học của hệ mật mã
- Tìm hiểu bài toán logarithm rời rạc và hệ mật ElGamal; thủ tục trao đổi khóa
Diffie- Hellman; các phƣơng pháp che giấu dữ liệu và các điều kiện lũy đẳng và
giao hoán của các hệ mật.
- Lý thuyết chung về hệ mật khóa công khai từ đó đƣa ra những sửa đổi của hệ
mật ElGamal.
* Phương pháp thực nghiệm
- Sửa đổi hệ mật bằng cách giữ nguyên cấu trúc trao đổi khóa Diffie-Hellman,
sửa đổi kiểu che giấu dữ liệu.
- Đánh giá hiệu quả và tính an toàn của Hệ mật ElGamal.
3. Cấu trúc luận văn
Luận văn đƣợc tác giả trình bày trong 3 chƣơng, có phần mở đầu, danh mục
hình vẽ, danh mục từ viết tắt, danh mục bảng, phần kết luận, phần mục lục, phần tài
liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc sau:
Chƣơng 1: Tổng quan về bài toán Logarithm rời rạc và các hệ mật mã
Trong chƣơng này, luận văn trình bày một số khái niệm cơ bản trong toán học
mà các hệ mã hoá thƣờng sử dụng nhƣ: modulo, số nguyên tố, vành Zn, các phép
toán cộng, nhân, bài toán logarithm rời rạc trên không gian Zn, Zn*,...Sau đó đƣa ra
các khái niệm mật mã, các thuật toán mã hoá, chữ ký số phục vụ cho việc mã hoá và
giải mã thông tin.
2
Chƣơng 2: Xây dựng hệ mật Elgamal có sửa đổi
Tập trung nghiên cứu hệ mật mã Elgamal cổ điển và đƣa ra những đánh giá về
ƣu nhƣợc điểm từ đó đƣa ra những sửa đổi đối với thuật toán hệ mật mã khóa công
khai ElGamal, tính chất đồng cấu của hệ mật mã ElGamal và sơ đồ chia sẻ bí mật
theo ngƣỡng Shamir.
Chƣơng 3: Phân tích hiệu năng an toàn của hệ mật Elgamal có sửa đổi và tìm
hiểu các ứng dụng có sử dụng thuật toán mã hóa khóa công khai
Cài đặt thử nghiệm chƣơng trình mô phỏng thuật toán hệ mật mã khóa công
khai ElGamal sửa đổi và kỹ thuật chia sẻ khóa bí mật. Demo ứng dụng mã hóa và
giải mã trong việc gửi nhận thƣ điện tử.
3
CHƢƠNG 1. TỔNG QUAN VỀ BÀI TOÁN LOGARITHM RỜI
RẠC VÀ CÁC HỆ MẬT MÃ
1.1. Tổng quan về bài toán logarithm rời rạc [1]
Bài toán Logarithm rời rạc là sự kết nối của phép tính logarithm trên trƣờng số
thực vào các nhóm hữu hạn. Với hai số thực x,y và cơ số a>0, a 1, nếu ax - y =0 thì
x đƣợc gọi là logarithm cơ số a của y, ký hiệu x = logay. Bài toán logarithm rời rạc
là bài toán khó. Trong khi bài toán ngƣợc lũy 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).
1.1.1.
Bài toán Logarithm trên trường số thực R
Bài toán thuận:
Hàm số y =ax với a,x R việc tính toán hàm mũ này có thể đƣợc thực hiện dễ
dàng bằng thuật toán nhân và bình phƣơng.
Ví dụ 1:
Cho p là một số nguyên tố, xét nhóm nhân các số nguyên modulo p:
Zp* = { 1,2….,p } với phép nhân modulo p.
Nếu ta tính lũy thừa bậc k của một số trong nhóm rồi rút gọn theo modulo p
thì ta đƣợc một số trong nhóm đó. Quá trình này đƣợc gọi là lũy thừa rời rạc
modulo p. Chẳng hạn với p = 17, lấy a = 3, k = 4 ta có: 34 = 81 = 13 mod 17.
Logarithm rời rạc là phép tính ngƣợc lại :
Biết: 3k = 13 (mod 17) hãy tìm k?
Thực hiện tƣơng tự nhƣ thuật toán Shank → k=4. Tuy nhiên đây là một bài
toán tƣơng đối khó. Trong trƣờng hợp p lớn (có ít nhất 150 chữ số) thì bài toán trở
thành bất khả thi → an toàn.
Bài toán ngƣợc:
Phép tính ngƣợc của hàm mũ chính là hàm logarithm y= logax, việc tính toán
hàm ngƣợc logarithm này khó khăn hơn nhiều so với hàm thuận. Tuy nhiên, cả hai
phép mũ và logarithm đều là các hàm đồng biến cho nên có thể xác định giá trị
tƣơng đối của hàm logarithm nhƣ hình dƣới đây
4
Hình 1.1: Đồ thị hàm số y=ax và y = logax
Một số tính chất của hàm logarithm.
y =logabc =logab +logac
y = loga = logab - logac
loga1 = 0
y = logax -1 = - logax.
Bài toán Logarithm trên trường hữu hạn
1.1.2.
Xét với vành đa thức Zp* với p là số nguyên tố thì theo định lý nếu p là nguyên
tố thì Zp là một trƣờng (Zp = GF(2)).
Tập tất cả các phần tử khác không của trƣờng sẽ tạo nên một nhóm nhân xyclic Z*p.
Z*p= Zp/{0}={1,2,...,p -1}
Bài toán thuận: y = ax mod p, (a,x Z*p)
Ví dụ 2:
Xét p = 19, a = 2 ta có các giá trị y = ax nhƣ trong bảng dƣới đây:
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2x
2
4
8
16 13
7
14
9
18
17
15
11
3
6
12
5
10
1
Bảng 1.1: Các giá trị của y = 2x mod 19 trên Z*19
Chú ý:
+ Nếu a là một phần tử nguyên thủy thì ax sẽ đi qua tất cả các phần tử của
nhóm.
5
+ Nếu a là phần tử nguyên thủy thì ai cũng là nguyên thủy với (i,p-1)= 1(p là
số nguyên tố).
Trong ví dụ trên các giá trị của i thỏa mãn (i, 18)=1 là i = (1,5,7,11,13,17). Số
lƣợng các giá trị của i bằng giá trị hàm (p-1).
Ni = (p-1) = (18)=6
Cách tính hàm Phi-Euler
nhƣ sau:
(1)= 1, và (n) = (p-1)pk-1 với n là lũy thừa bậc k của số nguyên tố p; nếu m
và n là hai số nguyên tố cùng nhau thì (mn)= (m). (n)
Nếu n = P1k1 ............. prkr trong đó các Pjlà các số nguyên tố phân biệt thì
(n) = (p1- 1)p1k1-1 .............. (P1- 1)prkr-1
(n) = n ∏
p|n
Nhƣ vậy trong nhóm Z*19 có 6 phần tử nguyên thủy:
2 = 2i ; 13 = 25; 14 = 27; 15 = 211; 3 = 213; 10 = 217
Các phần tử nguyên thủy này tạo thành các cặp nghịch đảo nhƣ sau:
(2,10)
2 = 10-1
(13,3)
13 = 3-1
14 = 15-1
(14,15)
Bài toán ngƣợc: y = logax, (a,x
Z*p)
Từ bảng trên ta tính đƣợc giá trị hàm log2x nhƣ sau:
x
1
2
3
4
5
6
7
8
2x
2
4
8
16
13
7
14 9 18 17 15 11
3
6
12
5
10
1
log2x
18
1
13
2
16
14
6
5
7
11
4
10
9
3
9
8
10 11 12 13 14 15 16 17 18
17 12 15
Bảng 1.2: Các giá trị log2x(mod 19) trên Z*19
Vì 218 = 1 nên log21 = 18
Một số tính chất của hàm logarit rời rạc a-1
+ y = logabc = (logab + logac)modp- 1 + y = loga = (logab - logac)modp-1
+ loga-1x = - logax = p - 1 - loga
+ loga1 = 0 = p - 1( coi 0 = p - 1)
Nhận xét: Từ hai bảng trên ta thấy hai hàm thuận và ngƣợc đều không phải là
6
hàm đồng biến, khi biết bài toán thuận thì mới tìm đƣợc bài toán ngƣợc. Do đó việc
giải bài toán ngƣợc giống bài toán vét cạn, phải thử lần lƣợt các trƣờng hợp.
Việc xác định logarithm của một phần tử bất kỳ trong trƣờng hợp là bài toán
khó giải.
Bài toán thuận:
Cho Z*pvới plà số nguyên tố, a là một phần tử nguyên thủy a Z*p.
Yêu cầu tìm y = logax với a, x Z*p.
Nhận xét: x
Z*p thì:
-
Bài toán có nghiệm khi α là phần tử nguyên thủy
-
Bài toán có thể không có nghiệm khi α là phần tử bất kỳ
Ví dụ:
Với trƣờng hợp p = 19 ta đã tính đƣợc 6 phần tử nguyên thủy nhƣ trong bảng
1.1. Ta sẽ đi tìm bài toán logarithm rời rạc với cơ số 6 phần tử nguyên thủy này.
Tuy nhiên ta có thể áp dụng tính chất của hàm logarithm rời rạc để tính
logarithm với cơ số là các cặp số nghịch đảo.
loga-1x= - logax = p - 1 - logax, hayloga-1x+ logax = p - 1
Tức là (2,10) là cặp số nghịch đảo, khi đó log10x = p - 1 - log2x = 18 - log2x
Tƣơng tự (13,3) và (14,15)là các cặp nghịch đảo nênlog3x = 18 - log13x và
log15x = 18 - log14x
Với quy tắc nhƣ thế có thể tính đƣợc các giá trị logarithm nhƣ trong bảng dƣới đây:
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
x
2
4
8
16
13
7
14
9
18
17
15
11
3
6
12
5
10
1
log2x
18
1
13
2
16
14
6
3
8
17
12
15
5
7
11
4
10
9
log10x
18
17
5
16
2
4
12
15
10
1
6
3
13
11
7
14
8
9
13x
13
17
12
4
14
11
10
16
18
6
2
7
15
5
8
9
3
1
log13x
18
11
17
4
14
10
12
15
16
7
6
3
1
5
13
8
2
9
log3x
18
7
1
14
4
8
6
3
2
11
12
15
17
13
5
10
16
9
14x
14
6
8
17
10
7
3
4
18
5
13
11
2
9
12
16
15
1
log14x
18
13
7
8
10
2
6
3
14
5
12
15
11
1
17
16
4
9
log15x
18
5
11
10
8
16
12
15
4
13
6
3
7
17
1
2
14
9
*
Bảng 1.3. Bài toán logarithm rời rạc trên Z
7
19
Có thể tính 13x thông qua 2x, ta thấy 13 = 25 do đó 13x= 25x,
tƣơng tự nhƣ thế có thể tính 14x= 27x
Phương pháp
– Pollaid đối với bài toán logarithm rời rạc
Bài toán logarithm rời rạc theo modulo là số nguyên tố p. Chúng ta muốn giải
phƣơng trình ax
b(modp).
Để làm việc này chúng ta xem 3 dãy số:{ui}, {vi}, {zi}, i = 0,1,2,...,Đƣợc xác định
nhƣ sau:
u0=v0=0, z0=1
ui+1 ui + 1(modp-1), nếu nhƣ 0 p.
Từ đây dẫn đến sự đúng đắn của thuật toán. Đánh giá độ phức tạp của thuật
toán cũng rõ ràng đúng, bởi vì tập từ N phần tử có thể sắp xếp cần O(N log N) lệnh
số học.
1.1.3.2. Thuật toán Adleman
Trong phần này chúng ta xem thuật toán giải phƣơng trình
ax ≡ b(modp)
(3.2)
ở đây p là số nguyên tố. Thuật toán này có độ phức tạp là Lp[ ;c]với một số giá trị
của hằng số c. Chúng ta cho rằng a(mod p) có bậc là p-1.
Thuật toán
Tầng 1. Hình thành cơ sở nhân tử, bao gồm tất cả các số nguyên tố q,
√
Q≤B=
Tầng 2. Bằng cách chọn lựa chúng ta tìm số tự nhiên risao cho
ari≡ q aiq (mod p) ,q là số nguyên tố
qB
Từ đây dẫn đến
(3.3), q là số nguyên tố
Tầng 3. Chọn số lƣợng đủ lớn biểu thức (3.3), giải hệ phƣơng trình tuyến tính thu
đƣợc ứng với các ẩn logaq -logarithmh rời rạc của phần tử của cơ sở nhân tử.
Tầng 4. Bằng cách lựa chọn chúng ta tìm ra một giá trị của r, sao cho
ar.b ≡
q
q
. p1... pk (modp)
q B
ở đây p1,.., pk - là các số nguyên tố với độ lớn “trung bình”, có nghĩa
B < pi< B1, với B =
√
Tầng 5. Bằng cách tính toán tƣơng tự nhƣ tầng 2 và 3 của thuật toán, tìm ra
logarithm rời rạc logapi đối với các số nguyên tố p1,...,pk ở tầng 4.
Tầng 6. Xác định giá trị cần tìm logab:
10
Kết thúc thuật toán.
1.1.3.3. Thuật toán vét cạn
Đây là thuật toán tự nhiên nhất và kém hiệu quả nhất để tính logarithmth rời
rạc. Ngƣời ta cứ thử tính
0,
1,
2,
… cho đến khi nào đạt đƣợc β thì thôi. Phƣơng
pháp này đòi hỏi O(n) phép toán nhân với n là cấp của α và do đó không hiệu quả
khi n lớn và rõ ràng là hàm mũ thực sự theo logn.
1.1.3.4. Thuật toán bƣớc đi lớn bƣớc đi nhỏ (Baby-step giant-step)
Giả sử m = [√ ] với n là cấp của α.
Thuật toán bƣớc đi lớn bƣớc đi nhỏ là sự thoả hiệp giữa thời gian và bộ nhớ của
phƣơng pháp vét cạn và dựa trên quan sát sau là nếu β = αx thì chúng có thể viết:
x = im + j với 0 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 β( -m)-i với i lần lƣợt chạy từ 0
đến (m – 1) và tra trong bảng (j,
j)
chừng nào có đƣợc đẳng thức β( -m)i = αj thì
dừng lại.
Thuật toán này đòi hỏi không gian lƣu trữ là O(√ ) phần tử nhóm và đòi hỏi O(√ )
phép nhân để xây dựng và O(√ logn) phép so sánh để sắp xếp. Ngoài ra nó cũng
cần O(√ ) phép toán nhân và O(√ ) phép toán tra bảng. Tựu chung là nó có thời
gian chạy O(√ ) phép toán nhóm.
1.1.3.5. Thuật toán Shank
Thuật toán này có tên gọi khác là thuật toán thời gian và bộ nhớ. Tƣ tƣởng của
thuật toán là nếu ta có đủ bộ nhớ thì có thể sử dụng bộ nhớ đó để giảm thời gian
thực hiện của thuật toán.
Input: Số nguyên tố p, phần tử nguyên thủy a cua Z*p, số nguyên y.
Output: Cần tìm a sao cho beta =alphaa mod p
Thuật toán :
Gọim = [(p-1)1/2](lấy phần nguyên).
Bƣớc 1: Tính alphamj mod p với 0 ≤ j ≤ m-1.
11
- Xem thêm -