HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG

LƢƠNG VĂN QUYÊN NGHIÊN CỨU KHẢ NĂNG ỨNG DỤNG CỦA HỆ MẬT TRÊN BÀI
TOÁN LOGARIT RỜI RẠC TRONG CHỮ KÝ SỐ
Chuyên ngành : Kỹ thuật Viễn thông
Mã số : 60.52.02.08

TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013
Công nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

TS. Ngô Đức Thiện
1

MỞ ĐẦU

1. Lý do chọn đề tài:
Ngày nay cùng với sự phát triển của các ngành khoa học, công nghệ thông tin
và truyền thông đã có những bước tiến mang tính đột phá, trong đó phải kể đến sự phát
triển của mạng Internet và mạng truyền số liệu. Điều này làm cho việc trao đổi, truyền
thông tin qua mạng ngày càng trở nên phổ biến trong mọi lĩnh vực của đời sống xã hội.
Cùng với sự phát triển của mạng thông tin và truyền thông cũng kéo theo sự gia tăng
một số lượng tội phạm lợi dụng kẽ hở bảo mật của mạng để tấn công, ăn cắp, làm giả
thông tin gây ra những thiệt hại to lớn.
Tại nước ta trong những năm gần đây việc tiến hành xây dựng chính phủ điện
tử đã và đang được các cơ quan chức năng nghiên cứu và đề xuất các giải pháp đầu tư
thích hợp, tại các ngân hàng việc cung cấp các dịch vụ giao dịch qua mạng ngày càng
phổ biến với hầu hết các khách hàng như dịch vụ Ebank, ví điện tử, dịch vụ thẻ….Về
mặt văn hóa báo mạng ngày càng phát triển cả về số lượng và chất lượng, cùng với
mạng truyền hình số, truyền hình cable ngày càng trở nên phổ biến, dịch vụ mạng có
thể cung cấp cho mọi đối tượng có đủ điều kiện và nhu cầu tiếp cận, và một vấn đề nảy
sinh đó là đã có một số lượng tội phạm lợi dụng kẽ hở bảo mật để tấn công, thay đổi
thông tin làm ảnh hưởng đến uy tín, gây thiệt hại rất lớn về kinh tế các tổ chức và cá
nhân.
Để đối phó với những vấn đề đó việc cần thiết là phải xây dựng được hệ thống

+ Nghiên cứu các sơ đồ chữ ký số điển hình, áp dụng một số hệ mật xây dựng
trên bài toán logarit rời rạc và các lược đồ chữ ký số.
+ Xây dựng các chương trình tính toán tham số cho hệ mật xây dựng trên bài
toán logarit rời rạc và mô phỏng một sơ đồ chữ ký số cụ thể sử dụng bài
toán này.
3. Đối tƣợng và phạm vi nghiên cứu:
+ Đối tương nghiên cứu: Mật mã khóa công khai, hàm băm xác thực và chữ
ký số.
+ Phạm vi nghiên cứu: Áp dụng các hệ mật khóa công khai sử dụng bài toán
logarit rời rạc vào sơ đồ chữ ký số.
4. Phƣơng pháp nghiên cứu:
Sử dụng lý thuyết về mật mã học, các cấu trúc đại số trên vành đa thức. Kết hợp
với việc tính toán và mô phỏng hệ mật khóa công khai, hàm băm và chữ ký số.
3

CHƢƠNG I TỔNG QUAN VỀ MẬT MÃ HỌC VÀ CHỮ KÝ SỐ

1.1. Cơ sở toán học của mật mã.
1.1.1. Số nguyên.
Tập số nguyên   
 Định nghĩa 1.1 [1] : Cho   , a là ước của b nếu       . Ký
hiệu a|b.
 Định nghĩa 1.2 [1]: c là ước chung của a và b nếu c|a và c|b.
 Định nghĩa 1.3 [1] (ƣớc chung lớn nhất - UCLN) : Số nguyên dương d là
UCLN của các số nguyên a và b ( Ký hiệu   ) nếu:
- d là ước chung của a và b.
- Nếu   c|a và c|b thì c|d.
 Định nghĩa 1.4 [1] (bội chung nhỏ nhất - BCNN) : Số nguyên dương d là
BCNN của hai số nguyên a và b ( Ký hiệu   


nguyên tố cùng nhau với n. Hàm 




được gọi là hàm Phi Euler.
 Một số tính chất của hàm phi Euler :
- Nếu P là số nguyên tố thì ta có    .
- Nếu



  thì 



 








- Nếu   



 



 

 





4

1.1.3. Các số nguyên MODULO N.
 Định nghĩa 1.8 [1] : Cho n là số nguyên dương, hai số nguyên a và b được gọi
là đồng dư với nhau theo modulo n (được ký hiệu là   ) nếu :
 .
 Các tính chất : Với 



   ta có :
- Tính chất về sự tồn tại :    khi và chỉ khi cả a và b đều có phần
dư khi chia cho n.
- Tính phản xạ :   .
- Tính đối xứng : Nếu    thì ta có   .
- Tính chất bắc cầu : Nếu có    và    thì ta có  
.
- Tính tuyến tính : Nếu   

 và   

  

 được xác định khi b
là phần tử khả nghịch.
 Định lý 1.1 [1] : Cho   

, khi đó a là phần tử khả nghịch (

 

) nếu
và chỉ nếu :



 .
 Các định nghĩa về phần tử nghịch đảo :
- Cho  

, phần tử nghịch đảo của  nếu có là một số nguyên
  

thỏa mãn :    ( x nếu tồn tại thì nó là duy nhất và a được
gọi là khả nghịch, phần tử nghịch đảo của a được ký hiệu là 

.
- Phép chia


  


 

, trong
trường hợp n là số nguyên tố thì 




      

.
 Định nghĩa 1.13 [1] : Cấp của 


là số phần tử trong 


(được ký hiệu là



). Theo định nghĩa của hàm Phi – Euler ta có 


  .
 Định nghĩa 1.14 [1] : Cho   


. Cấp của a là số nguyên dương nhỏ nhất t

 với mọi số nguyên a.
 

  với mọi số nguyên a.
 Định nghĩa1.15 [1] : Cho   


, nếu cấp của  là  thì  được gọi là
phần tử sinh hay phần tử nguyên thủy của 


. Nếu 


có một phần tử sinh thì



được gọi là cyclic.
 Một số tính chất của phần tử sinh :
- Nếu  là một phần tử sinh của 


thì : 








.
- 


có phần tử sinh khi và chỉ khi   

hay 

khi  là số nguyên tố lẻ
và   . Còn nếu n là số nguyên tố thì chắc chắn 


có phần tử sinh.
1.1.5. Các thặng dƣ bậc hai :
 Định nghĩa 1.16 [1] : Phần từ   


được gọi là thặng dư bậc 2 theo modulo n
nếu   




 . Gọi 

là tập các thặng dư bậc 2 và 









.
+Với    trong đó  là các số nguyên tố. Khi đó   

khi và chỉ khi
  

và   

. Vậy số thặng dư bậc 2 là :







   , số
thặng dư không bậc 2 là :








 Trong các hệ mật mã khóa bí mật thì do việc sử dụng khóa bí mật nên độ an
toàn của hệ mật liên quan trực tiếp đến quá trình bảo mật khóa bí mật.
 Khi số lượng khóa bí mật tăng lên việc quản lý các khóa này càng trẻ nên phức
tạp. Khi giao dịch với với nhiều đối tượng khác nhau thì một người có thể phải
giữ nhiều khóa bí mật.
 Nội dung của bản rõ không thể xác thực được nguồn gốc cũng như không có
tính chất không thể phủ nhận của chủ thể.
1.3.2. Hệ mật mã khóa công khai.
1.3.2.1. Sơ đồ hệ mật khóa công khai.
Mật mã khóa công khai, sử dụng một cặp chìa khóa có liên quan với nhau về
mặt toán học, một khóa công khai dùng để mã hoá (public key) và một khóa riêng
dùng để giải mã (private key). Một thông điệp sau khi được mã hóa bởi khóa công
khai sẽ chỉ có thể được giải mã với khóa riêng tương ứng, sơ đồ mật mã khóa công
khai được thể hiện ở hình 1.2. Bản rõ M
Bản mã C
Bản mã C
Bản rõ M
Nguồn tin
Bộ mã hoá
Kênh mở
(không an toàn)
Bộ giải mã
Nhận tin
Kênh an toàn
Thám mã
Nguồn khoá
K

Người nhận
Người gửi
Khóa công
khai(public key)Bản mã (C)
Khóa riêng
(private key)Bản rõ(m)
Bản rõ(m)
Kênh mở
9

 Mật mã khóa công khai có ưu điểm nổi bật đó là tính an toàn của hệ mã cao hơn,
việc phân phối và quản lý khóa đơn giản hơn, và một đặc điểm quan trọng là
khi khóa bị lộ dễ dàng xác định được chủ thể làm lộ khóa.
 Mật mã khóa công khai có nhược điểm là tốc độ chậm nên chưa thể thay thế
hoàn toàn hệ thống mã hoá khoá bí mật được, nó ít được sử dụng để mã hoá dữ
liệu mà thường dùng để mã hoá khoá.
1.4. Hàm băm, một số sơ đồ xác thực thông tin.
1.4.1. Định nghĩa và các đặc trƣng của hàm băm.
Định nghĩa 1.18[1] : Hàm băm là các thuật toán không sử dụng khóa để mã
hóa (ở đây ta dùng thuật ngữ “băm” thay cho “mã hóa”), nó có nhiệm vụ “lọc”
(băm) thông điệp được đưa vào theo một thuật toán h một chiều nào đó, rồi đưa ra
một bản băm – văn bản đại diện – có kích thước cố định. Do đó người nhận không
biết được nội dung hay độ dài ban đầu của thông điệp đã được băm bằng hàm băm.
Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội dung thông

- Các hàm băm không khóa MDC.
- Các hàm băm có khóa MAC.

Hình 1.3. Phân loại hàm băm.
1.4.3. Tính toàn vẹn và các sơ đồ xác thực thông tin.
 Tính toàn vẹn của dữ liệu:
Định nghĩa 1.19 [1] : Tính toàn vẹn của dữ liệu là tính chất đảm bảo dữ liệu
không bị sửa đổi một các bất hợp pháp kể từ khi dữ liệu được tạo ra, được phát tán
hoặc đang được lưu giữ bởi một nguồn được xác định.
Định nghĩa 1.20 [1] : Xác thực tính nguyên bản của dữ liệu là một kiểu xác
thực đảm bảo một bên liên lạc được chứng thực là nguồn thực sự tạo ra dữ liệu đó ở
một thời điểm nào đó trong quá khứ.
Xác thực thông báo là một thuật ngữ được dùng tương đương với xác thực
nguyên gốc của dữ liệu.
 Các sơ đồ xác thực thông tin:

Hàm băm
Không có khoá
Có khoá
Các ứng dụng khác
Các ứng dụng khác
MAC
OWHF
CRHF
MDC
11 Hình 1.4 Sơ đồ chỉ sử dụng MDC và mã hóa



So sánh
Giải mã
k
M



Thông báo M
MDC
Thám mã



Kênh an toàn
Bên phát
Kênh mở



MDC
So sánh
Bên thu
Đ
S
12

Về mặt lý tưởng chữ ký có các đặc tính sau :
- Chữ ký là bằng chứng thể hiện người ký có chủ định ký văn bản.
- Chữ ký thể hiện “Chủ Quyền ”, nó làm cho người nhận văn bản biết rằng ai

từng hệ mật mã. Trong chương này cũng đưa ra khái niệm tổng quan về hàm băm và
chữ ký số và các sơ đồ xác thực thông tin.
Thông báo
M
MDC
Thám mã



Bên phát
Kênh mở
MDC
Bên thu
Đ
S
Mã hóa



được gọi là logarit cơ số a của b và được kí hiệu là   

. Như vậy ta có :
- Bài toán thuận :   

(  ).
- Bài toán ngược :   

(    )
Một số tính chất hàm logarit : Với       ta có:
-   

   ;
-   

   ;
-   



   ;
-   



  ;
-   




điều kiện sau :
 R là một nhóm giao hoán đối với phép cộng :
- Phép cộng có tính kết hợp:   

 

       ;
- Phép cộng có phần tử trung hòa:           ;
- Mọi phần tử của R có phần tử đối :   

  

 

   ;
- Phép cộng có tính giao hoán:         ;
 Phép nhân có tính chất phân phối với phép cộng :   

  

 
 .
 Phép nhân có tính chất kết hợp :   



  .
 Phép nhân có phần tử đơn vị :         .
 Một vành được gọi là giao hoán nếu :     .
15

Bảng 2.1. Tính   

, các cặp nghịch đảo 

.
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



2
4
8





 . Vậy tập
các phần tử nguyên thủy của 

là :



.
- Các phần từ nguyên thủy tạo thành các cặp nghịch đảo :   

(do
   ),   

(do    ),   

(do
  ). Bảng sau thể hiện quan hệ các cặp nghịch đảo.
 Bài toán ngƣợc :   

 với   



Dựa trên các tính chất của hàm logarit ta có :
-   


      ;
Các cặp nghich đảo
16

Ví dụ 2.2 : Cho     . Ta tính   

 với   


, từ bảng đã tính ở Ví dụ 2.1.2.2.1 các giá trị của hàm ngược.
Bảng 2.2. Tính   

 từ 

với   

 .
x
1
2
3
4
5
6
7
8
9
10
11
12

18
1
13
2
16
14
6
3
8
17
12
15
5
7
11
4
10
9
Do 

  vậy nên ta có 

=18; 

  vậy nên ta có 

=1, tương tự ta
tính được các phần tử   

 khác.


 

    .
 Xét cặp nguyên thủy (2,10) :
- Ta có 

     

 (với   và   ) ta lập được bảng :
Bảng 2.3. Tính các logarit rời rạc   

 và   

.
x
1
2
3
4
5
6
7
8
9
10
11
12
13
14

13
2
16
14
6
3
8
17
12
15
5
7
11
4
10
9



18
17
5
16
2
4
12
15
10
1
6

Chẳng hạn với   , lấy   ,    ta có : 

   .
Lôgarit rời rạc là phép tính ngược lại:
Biết : 

  hãy tìm k.
2.3. Các hệ mật xây dựng trên bài toán logarit rời rạc.
2.3.1. Trao đổi và thỏa thuận khóa Diffie – Hellman.
Bài toán : Giả sử A và B cần thống nhất 1 khóa K dung cho hệ khóa bí mật. Để
thỏa thuận khóa K chung cho cả hai bên qua một kênh không an toàn, với yêu cầu
khóa K không bị lộ, khi đó A và B có thể dung thủ tục thỏa thuận khóa Diffie –
Hellman như sau :
Trước hết chọn một số nguyên tố thích hợp  và  là một phần tử nguyên thủy
của 


, các giá trị  được công khai.
A
- A chọn x ngẫu nhiên (      ) và
tính 

 sau đó gửi cho B.
- A nhận được 

và tính 



.

Hình 2.1. Tấn công kẻ đứng giữa.
Việc Diffie – Hellman bị tấn công theo phương pháp “kẻ đứng giữa” có thể
được khắc phục bằng cách sử dụng xác thực trong trao đổi khóa.
A
B
B’
A’
K
1
K
2
18

2.3.2. Hệ mật Omura – Massey.
 Ý tƣởng xây dựng hệ mật Omura – Massey : Bản tin m từ A sẽ được mã hóa
bằng khóa riêng 

để thu được bản mã 

và được gửi cho B. Phía B sẽ tiếp
tục mã hóa 

bằng khóa riêng 

để thu được bản mã 

và gửi lại cho A.
Phía A nhận được bản mã 

sẽ tiến hành giải mã với khóa riêng 

+ A tính 

 rồi gửi cho B.
+ B tính 



  

.

+ B tính 



 rồi gửi cho A.

+ B tính 



  .
 Nhận xét :
- Để tìm bản tin M thám mã phải giải bài toán logarit rời rạc.
- Về mặt hiểu quả truyền tin thì hệ mật Omura – Massey cho tốc độ truyền tin
thấp  


, phương pháp này chỉ thích hợp cho việc truyền tin ngắn hoặc
truyền khóa (phân phối khóa cho một hệ mật khóa bí mật).

- Bước 1 : A tính 

  



  

.
- Bước 2 : A tính 

 



  
Nhận xét :
- Để giải mã thì thám mã phải tìm được  (khóa bí mật), muốn tìm được  thì
thám mã phải giải bài toán logarit rời rạc ( tính   



) với  lớn không
thể giải được và hệ mật có thể coi là an toàn.
- Hệ mật elgamal có nhược điểm đó là bản mã thu được sau khi mã hóa sẽ có độ
dài gấp 2 lần so với bán tin ban đầu, do đó hiệu quả truyền tin không cao.
2.4. Áp dụng hệ mật elgamal vào sơ đồ chữ ký số.

Hình 2.2. Sơ đồ chữ ký số dung hệ mật elgamal.




m’
20

 Quá trình sinh khóa :
- Bước 1 : Chọn số nguyên tố lớn ,  là phần tử nguyên thủy  


.
- Bước 2 : Chọn a ngẫu nhiên       và tính 

.
- Bước 3 : + Tính khóa công khai : 

.
+ Khóa bí mật là :.
 Quá trình tạo ký :
- Bước 1 : Đặt   

với       .
- Bước 2 : Chọn số nguyên ngẫu nhiên  :        và     .
- Bước 3 : Thực hiện tính :



 















- Bước 3 : Tiến hành so sánh 

và 

, nếu 

 

có nghĩa là chữ ký đúng, còn


 

đồng nghĩa với việc văn bản hoặc chữ ký đã bị sửa đổi.
2.5. Kết luận chƣơng.
Trong chương này đã đi nghiên cứu về bài toán logarit rời rạc và ứng dụng kết
quả có được từ việc nghiên cứu bài toán logarit rời rạc để xây dựng các hệ mật khóa
công khai. Từ kết quả nghiên cứu có được, nội dung chương cũng đã nêu ra bản chất
bài toán logarit rời rạc và ứng dụng xây dựng chữ ký số trên bài toán logarit rời rạc.

(  


).
- Bài toán ngược :   

(  


).
 Ý tƣởng xây dựng chƣơng trình :
- Vào P là số nguyên tố, xây dựng chương trình tìm tất cả các phần từ nguyên
thủy 


.
- Chọn một phần tử nguyên thủy  bất kỳ từ các phần tử nguyên thủy tìm được
và nhập một số  bất kỳ thỏa mãn điều kiện :   


.
- Xây dưng chương trình tính   

 và   

(  


). Và
cho hiển thị kết quả tính toán ra màn hình.

Hình 3.2. Giao diện chƣơng trình sinh khóa Elgamal.
3.3. Xây dựng chƣơng trình mô phỏng chữ ký số.
 Đặt vấn đề : Vào một đoạn văn bản bất kỳ, thực hiện ký số cho văn bản và gửi
đi. Phía nhận sẽ kiểm tra tính xác thực chữ ký.
 Ý tƣởng xây dựng chƣơng trình :
- Nhập một đoạn văn bản bất kỳ.
23

- Thực hiện băm theo thuật toán cho trước để tạo ra tóm lược cho đoạn văn bản
đã nhập, thực hiện băm tạo ra bản băm 64bits(có độ dài vừa phải để có thể phù
hợp với máy tính cá nhân và tạo ra khả năng tính toán nhanh hơn).
- Thực hiện ký số bằng hệ mật elgamal dùng khóa bí mật. Thực hiện chia bản
băm 64bits thành 8 đoạn mỗi đoạn 8bits, tiến hành mã hóa từng 8bit một tạo ra
hiệu quả tính toán nhanh. Sau khi tính toán xong thì ghép lại để thu được chữ
ký.
- Gửi bản tin cùng với chữ ký cho phía nhận.
- Phía nhận thực hiện băm văn bản nhận được với cùng thuật toán băm với phía
gửi.
- Giải mã chữ ký số với khóa công khai với cùng cách sử lý 8bits/đoạn như phần
xử lý ký
- Tính toán để tiến hành xác thực chữ ký.
 Xây dựng giao diện chƣơng trình mô phỏng nhƣ sau :

Hình 3.3. Chƣơng trình mô phỏng chữ ký số dung Elgamal.
3.4. Kết luận chƣơng.
Trong chương này đã đi phân tích các yêu cầu xây dựng chương trình mô
phỏng từ đó đưa ra các ý tưởng xây dựng chương trình và tìm các thuật toán phù hợp
để xây dựng chương trình mô phỏng. Trong quá trình xây dựng chương trình mô
phỏng đã chú ý đến việc tính toán xử lí nhanh các chương trình mã hóa, giải mã, tạo
bản băm để có thể đảm bảo chương chình có thể chạy với tốc độ nhanh và phù hợp với