i
®¹i häc th¸i nguyªn
Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG
MÃ VĂN LAI
NGHIÊN CỨU VÀ PHÁT TRIỂN
PHƢƠNG PHÁP RÚT GỌN CHỮ KÍ SỐ
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
th¸i nguyªn - n¨m 2014
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
ii
MỤC LỤC
MỤC LỤC.................................................................................................................... i
DANH MỤC CÁC CHỮ VIẾT TẮT ........................................................................ iv
DANH MỤC CÁC HÌNH VẼ .....................................................................................v
MỞ ĐẦU ......................................................................................................................1
Chƣơng 1:TỔNG QUAN VỀ MẬT MÃ KHOÁ CÔNG KHAI VÀ CHỮ KÝ SỐ ....3
1.1. Tổng quan về mật mã ........................................................................................3
1.1.1. An toàn và bảo mật thông tin ......................................................................3
1.1.2. Mật mã học ..................................................................................................4
1.1.3. Tiêu chuẩn đánh giá hệ mật mã...................................................................7
1.2. Mật mã khóa công khai .....................................................................................7
1.2.1. Giới thiệu .....................................................................................................7
1.2.2. Độ an toàn của mật mã công khai .............................................................12
1.2.3. Các ứng dụng của mật mã công khai ........................................................12
1.2.4. Độ phức tạp tính toán của mã công khai. ..................................................12
1.2.5. Những vấn đề về thám mã.........................................................................13
1.3. Hàm băm mật mã .............................................................................................14
1.3.1. Tổng quan về hàm băm .............................................................................14
1.4. Chữ ký số .........................................................................................................17
1.4.1. Khái niệm về chữ ký số .............................................................................17
1.4.2. Thực hiện chữ kí số ...................................................................................19
1.5. Tóm tắt chƣơng ................................................................................................21
Chƣơng 2:CÁC CƠ SỞ TOÁN HỌC VÀ MÔ HÌNH XÂY DỰNG CÁC LƢỢC ĐỒ
CHỮ KÍ SỐ ................................................................................................................22
2.1. Một số vấn đề toán học liên quan ....................................................................22
2.1.1. Nhóm .........................................................................................................22
2.1.2. Vành ..........................................................................................................23
2.1.3. Các kiến thức cần thiết khác .....................................................................24
2.2. Bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố .....................26
2.2.1. Một số vấn đề phân tích một số ra thừa số nguyên tố ...............................26
2.2.2. Thuật toán RSA .........................................................................................31
2.2.3. Độ an toàn của hệ mật mã RSA ................................................................32
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
iii
2.3. Bài toán logarit rời rạc trong trƣờng hữu hạn ..................................................33
2.3.1. Vấn đề logarit rời rạc.................................................................................33
2.3.2. Sơ đồ chữ kí số Elgamal............................................................................40
2.4. Hệ mật mã đƣờng cong Elliptic .......................................................................44
2.4.1. Vấn đề về đƣờng cong Elliptic ..................................................................44
2.4.2. Ứng dụng lý thuyết đƣờng cong elliptic vào chữ kí số .............................46
2.5. Tóm tắt chƣơng ................................................................................................48
Chƣơng 3:PHÁT TRIỂN PHƢƠNG PHÁP RÚT GỌN CHỮ KÍ SỐ ......................49
3.1. Đặt vấn đề ........................................................................................................49
3.2. Phƣơng pháp hình thành chữ kí số ..................................................................49
3.2.1. Phƣơng pháp rút gọn chữ kí số .................................................................49
3.2.2. Sơ đồ thuật toán .........................................................................................52
3.2.3. Thảo luận về độ an toàn của sơ đồ chữ kí số mới .....................................53
3.3. Sơ đồ chữ kí dựa vào số nguyên tố δ ...............................................................55
3.3.1. Hàm đƣợc sử dụng ....................................................................................55
3.3.2. Sơ đồ chữ kí số ..........................................................................................55
3.3.3. Thảo luận về độ an toàn sơ đồ chữ kí số ...................................................57
3.3.4. Đánh giá về độ an toàn của sơ đồ chữ kí số mới.......................................58
3.4. Xây dựng chƣơng trình demo ..........................................................................61
3.4.1. Thƣ viện hàm các phép tính trên số lớn ....................................................61
3.4.2. Thuật toán kiểm tra một số lớn là nguyên tố.............................................62
3.4.3. Thuật toán Gordon sinh số nguyên tố mạnh .............................................62
3.4.5. Sơ đồ khối các thủ tục kí và xác nhận chữ kí ............................................63
3.4.6. Các chức năng chính của chƣơng trình ứng dụng .....................................67
3.5. Tóm tắt chƣơng ................................................................................................71
KẾT LUẬN ................................................................................................................72
TÀI LIỆU THAM KHẢO..........................................................................................73
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
iv
DANH MỤC CÁC CHỮ VIẾT TẮT
Là bậc của số nguyên α
Nối độ dài bit của x và y
Gcd(x, y)
Ƣớc số chung lớn nhất của x và y
Lcm(x, y)
Bội số chung nhỏ nhất của x và y
ECC
Elliptic Curve Cryptography – Mật mã trên đƣờng cong
Elliptic
ECES
Elliptic Curve Encrypt Scheme
ECDSA
Elliptic Curve Digital Signature Algorithm – Thuật toán chữ
kí số trên đƣờng cong Elliptic
MD5
Message – Digest algorithm 5 hàm băm mật mã tiêu chuẩn
128 bít
SHA
(Secure Hash Algorithm hay thuật giải băm an toàn
RSA
Rivest – Shamir – Adleman
Zm
Vành thƣơng hữu hạn m
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
v
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Cách mã hóa khóa bí mật .............................................................................6
Hình 1.2. Cách mã hóa khóa công cộng ......................................................................6
Hình 1.3. Hàm băm trong chữ ký số ..........................................................................14
Hình 1.4 Sơ đồ chữ kí số ............................................................................................21
Hình 2.1 Thuật toán Pollar .........................................................................................27
Hình 2.2. Thuật toán Shanks ......................................................................................34
Hình 2.3. Thuật toán Pohlig – Hellman .....................................................................38
Hình 3.1. Sơ đồ thủ tục tạo một bộ khóa ...................................................................64
Hình 3.2. Sơ đồ thủ tục kí ..........................................................................................65
Hình 3.3. Sơ đồ thủ tục xác minh một chữ kí ............................................................66
Hình 3.4. Giao diện chính của chƣơng trình ứng dụng ..............................................67
Hình 3.5. Chức năng tạo bộ khoá...............................................................................68
Hình 3.6. Chức năng kí văn bản.................................................................................68
Hình 3.7. Chức năng xác thực chữ kí – kiểm tra chữ kí là sai ...................................69
Hình 3.8. Chức năng xác thực chữ kí – kiểm tra chữ kí là đúng ...............................69
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
1
MỞ ĐẦU
Mật mã (Cryptography) là ngành khoa học là ngành nghiên cứu các kỹ thuật
toán học nhằm cung cấp các dịch vụ bảo vệ thông tin. Đây là ngành khoa học quan
trọng, có nhiều ứng dụng trong đời sống xã hội. Ngày nay, các ứng dụng mã hóa và
an toàn thông tin đang đƣợc sử dụng ngày càng phổ biến trong các lĩnh vực khác
nhau trên thế giới, từ các lĩnh vực an ninh, quốc phòng… cho đến các lĩnh vực dân
sự nhƣ thƣơng mại điện tử, ngân hàng…
Vai trò của mật mã trong các giải pháp an toàn thông tin – đề cập đến vấn
đề nghiên cứu và ứng dụng mật mã để bảo vệ thông tin.
Trong mật mã vấn đề bảo mật luôn đi đôi với vấn đề xác thực thông tin, đặc
biệt trong hệ thống mật mã khóa công khai vấn đề xác thực là vô cùng quan trọng.
Để giải quyết đƣợc vấn đề xác thực, trong thực tế có một giải pháp kỹ thuật vừa đơn
giản vừa hiệu quả là sử dụng chữ ký số. Việc sử dụng chữ ký số ngày càng có nhiều
ứng dụng trong thực tế, không chỉ giới hạn trong Ngành Mật Mã mà còn đƣợc áp
dụng trong một số lĩnh vực vô cùng quan trọng nhƣ trong lĩnh vực Chính phủ điện
tử, Thƣơng mại điện tử,… để xác thực ngƣời gửi, nội dung và nguồn gốc thông tin,
chống chối từ.
Vai trò của các thuật toán chữ ký số dựa trên các ứng dụng rộng rãi của chúng.
Việc nghiên cứu, tối ƣu và phát triển các lƣợc đồ chữ ký số luôn đƣợc đặt ra
trong thực tiễn (nhằm phát triển các lƣợc đồ chữ ký số tối ƣu, hoặc các lƣợc đồ phù
hợp cho các ứng dụng phát triển thực tiễn).
Việc nghiên cứu và phát trỉển các lược đồ chữ ký số mới – một trong những
mục tiêu chính được đặt ra trong thực tiễn nhằm nâng cao tính độc lập trong
xây dựng các giải pháp an toàn thông tin.
Trong thực tế, một yêu cầu rất quan trọng đƣợc đăt ra khi tối ƣu và phát triển
các lƣợc đồ chữ ký số ứng dụng trong các môi trƣờng hạn chế về băng thông và tài
nguyên là các lƣợc đồ chữ ký số với chiều dài chữ ký số ngắn (Giải quyết bài toán
làm sao cho độ dài chữ ký tối thiểu nhất có thể mà không thể giả mạo chữ ký đƣợc).
Vịệc nghiên cứu và phát triển các lược đồ chữ ký số rút gọn thể hiện tính
khoa học và thực tiễn cao.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
2
Kết quả nghiên cứu của đề tài nhằm góp phần định hƣớng và tự phát triển các
lƣợc đồ chữ ký số có khả năng ứng dụng trong thực tiễn.
Mục tiêu của đề tài:
Nghiên cứu các giải pháp xây dựng và khả năng ứng dụng chữ ký số trong bảo
vệ an toàn thông tin.
- Mật mã khóa công khai;
- Hàm băm mật mã;
- Các kiểu chữ ký số;
- Các ứng dụng của chữ ký số.
Nghiên cứu các cơ sở toán học, mô hình xây dựng và đánh giá các lƣợc đồ chữ
ký số.
- Chữ ký số dựa trên tính khó của bài toán phân tích một số nguyên lớn ra các
thừa số nguyên tố;
- Chữ ký số dựa trên tính khó của bài toán logarit rời rạc;
- Chữ ký số dựa trên tính khó của bài toán logarit rời rạc trên các điểm nhánh
của vành Elliptic.
Phát triển phƣơng pháp rút gọn chữ ký số dựa trên tính khó của bài toán phân
tích một số nguyên lớn ra các thừa số nguyên tố.
Xây dựng lƣợc đồ rút gọn chữ ký số mới và biến thể của nó. Đánh giá độ an
toán của các lƣợc đồ đề xuất dựa trên các phƣơng trình chứng minh đã đƣợc công
nhận trên thế giới.
Xây dựng các chƣơng trình mô phỏng và đánh giá kết quả nghiên cứu cần đạt đƣợc.
Cấu trúc của luận văn gồm 3 chƣơng:
Chƣơng 1: Tổng quan về mật mã khóa công khai và chữ ký số
Chƣơng 2: Các cơ sở toán học và mô hình xây dựng các lƣợc đồ chữ ký số
Chƣơng 3: Phát triển phƣơng pháp rút gọn chữ ký số.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
3
Chƣơng 1
TỔNG QUAN VỀ MẬT MÃ KHOÁ CÔNG KHAI VÀ CHỮ KÝ SỐ
1.1. Tổng quan về mật mã
1.1.1. An toàn và bảo mật thông tin
Khi nhu cầu trao đổi thông tin dữ liệu ngày càng lớn và đa dạng, các tiến bộ về
điện tử - viễn thông và công nghệ thông tin không ngừng đƣợc phát triển ứng dụng
để nâng cao chất lƣợng và lƣu lƣợng truyền tin thì các quan niệm ý tƣởng và biện
pháp bảo vệ thông tin dữ liệu cũng đƣợc đổi mới. Bảo vệ an toàn thông tin dữ liệu là
một chủ đề rộng, có liên quan đến nhiều lĩnh vực và trong thực tế có thể có rất nhiều
phƣơng pháp đƣợc thực hiện để bảo vệ an toàn thông tin dữ liệu. Các phƣơng pháp
bảo vệ an toàn thông tin dữ liệu có thể đƣợc quy tụ vào ba nhóm sau:
- Bảo vệ an toàn thông tin bằng các biện pháp hành chính
- Bảo vệ an toàn thông tin bằng các biện pháp kỹ thuật (phần cứng).
- Bảo vệ an toàn thông tin bằng các biện pháp thuật toán (phần mềm).
Ba nhóm trên có thể đƣợc ứng dụng riêng rẽ hoặc phối kết hợp. Môi trƣờng
khó bảo vệ thông tin nhất và cũng là môi trƣờng đối phƣơng dễ xâm nhập nhất đó là
môi trƣờng mạng và truyền tin. Biện pháp hiệu quả nhất và kinh tế nhất hiện nay
trên mạng truyền tin và mạng máy tính là biện pháp thuật toán.
An toàn thông tin bao gồm những nội dung sau:
- Tính bí mật: Tính kín đáo riêng tƣ của thông tin
- Tính xác thực của thông tin, bao gồm xác thực đối tác (bài toán nhận dạng),
xác thực thông tin trao đổi
- Tính trách nhiệm: Đảm bảo ngƣời gửi thông tin không thể thoái thác trách
nhiệm về thông tin mà mình đã gửi.
Để đảm bảo an toàn thông tin dữ liệu trên đƣờng truyền tin và trên mạng máy
tính có hiệu quả thì điều trƣớc tiên là phải lƣờng trƣớc hoặc dự đoán trƣớc các khả
năng không an toàn, khả năng xâm phạm, các sự cố rủi ro có thể xảy ra đối với
thông tin dữ liệu đƣợc lƣu trữ và trao đổi trên đƣờng truyền tin cũng nhƣ trên mạng.
Xác định càng chính xác các nguy cơ nói trên thì càng quyết định đƣợc tốt các giải
pháp để giảm thiểu các thiệt hại. Có hai loại hành vi xâm phạm thông tin dữ liệu đó
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
4
là: vi phạm chủ động và vi phạm thụ động. Vi phạm thụ động chỉ nhằm mục đích
cuối cùng là nắm bắt đƣợc thông tin (đánh cắp thông tin). Việc làm đó có khi không
biết đƣợc nội dung cụ thể nhƣng có thể dò ra đƣợc ngƣời gửi, ngƣời nhận nhờ thông
tin điều khiển giao thức chứa trong phần đầu các gói tin. Kẻ xâm nhập có thể kiểm
tra đƣợc số lƣợng, độ dài và tần số trao đổi. Vì vậy vi phạm thụ động không làm sai
lệch hoặc hủy hoại nội dung thông tin dữ liệu đƣợc trao đổi.Vi phạm thụ động thƣờng
khó phát hiện nhƣng có thể có những biện pháp ngăn chặn hiệu quả. Vi phạm chủ động
là dạng vi phạm có thể làm thay đổi nội dung, xóa bỏ, làm trễ, sắp xếp lại thứ tự hoặc
làm lặp lại gói tin tại thời điểm đó hoặc sau đó một thời gian. Vi phạm chủ động có thể
thêm một số thông tin ngoại lai để làm sai lệch thông tin trao đổi. Vi phạm chủ động dễ
phát hiện nhƣng để ngăn chặn thì khó khăn hơn nhiều. Một thực tế là không có một
biện pháp bảo vệ an toàn thông tin dữ liệu nào là an toàn tuyệt đối. Một hệ thống dù
đƣợc bảo vệ chắc chắn đến đâu cũng không thể đảm bảo là an toàn tuyệt đối.
1.1.2. Mật mã học
Mật mã học bao gồm hai lĩnh vực: mã hóa (cryptography) và thám mã
(cryptanalysis-codebreaking) trong đó:
- Mã hóa: nghiên cứu các thuật toán và phƣơng thức để đảm bảo tính bí mật và
xác thực của thông tin (thƣờng là dƣới dạng các văn bản lƣu trữ trên máy tính). Các
sản phẩm của lĩnh vực này là các hệ mật mã, các hàm băm, các hệ chữ ký số, các cơ
chế phân phối, quản lý khóa và các giao thức mật mã:
- Thám mã: Nghiên cứu các phƣơng pháp phá mã hoặc tạo mã giả. Sản phẩm
của lĩnh vực này là các phƣơng pháp thám mã, các phƣơng pháp giả mạo chữ ký,
các phƣơng pháp tấn công các hàm băm và các giao thức mật mã.
Trong giới hạn của luận văn này tác giả chủ yếu vào tìm hiểu một số hệ mã
hóa, các hàm băm, các hệ chữ ký số. Nhƣ thế mã hóa có thể đƣợc định nghĩa đơn
giản nhƣ sau:
Định nghĩa 1.1
Mã hóa (cryptography) là một ngành khoa học của các phương pháp truyền tin
bảo mật. Trong tiếng Hy Lạp, “Cryto” (krypte) có nghĩa là che dấu hay đảo lộn,
còn “Graphy” (grafik) có nghĩa là từ.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
5
Ngƣời ta quan niệm rằng: những từ, những ký tự của văn bản gốc có thể hiểu
đƣợc sẽ cấu thành nên bản rõ (P – Plaintext), thƣờng thì đây là các đoạn văn bản
trong một ngôn ngữ nào đó; còn những từ, những ký tự ở dạng bí mật không thể
hiểu đƣợc thì đƣợc gọi là bản mã (C – Ciphertext).
a. Vai trò của hệ mật mã
Các hệ mật mã phải thực hiện đƣợc các vai trò sau:
- Hệ mật mã phải che dấu đƣợc nội dung của văn bản rõ (Plain Text) để đảm
bảo sao cho chỉ ngƣời chủ hợp pháp của thông tin mới có quyền truy cập thông tin
(Secrety), hay nói cách khác là chống truy cập không đúng quyền hạn.
- Tạo các yếu tố xác thực thông tin, đảm bảo thông tin lƣu hành trong hệ thống
đến ngƣời nhận hợp pháp là xác thực (Authenticity).
- Tổ chức các sơ đồ chữ ký số, đảm bảo không có hiện tƣợng giả mạo, mạo
danh để gửi thông tin trên mạng.
Ƣu điểm lớn nhất của bất kỳ hệ mật mã nào đó là có thể đánh giá đƣợc độ
phức tạp tính toán mà “kẻ địch” phải giải quyết bài toán để có thể lấy đƣợc thông
tin của dữ liệu đã đƣợc mã hóa. Tuy nhiên mỗi hệ mật mã có một số ƣu và nhƣợc
điểm khác nhau, nhƣng nhờ đánh giá đƣợc độ phức tạp tính toán mà ta có thể áp
dụng các thuật toán mã hóa khác nhau cho từng ứng dụng cụ thể tùy theo từng
yêu cầu về độ an toàn.
b. Các thành phần của một hệ mật mã:
Một hệ mật mã là một bộ 5 (P, C, K, E, D) thỏa mãn các điều kiện sau:
- P là một tập hợp hữu hạn các bản rõ (Plain Text), nó đƣợc gọi là không gian
bản rõ.
- C là tập các hữu hạn các bản mã (Crypto), nó còn đƣợc gọi là không gian các
bản mã. Mỗi phần tử của C có thể nhận đƣợc bằng cách áp dụng phép mã hóa Ek lên
một phần tử của P, với k
K.
- K là tập hữu hạn các khóa hay còn gọi là không gian khóa. Đối với mỗi phần
tử k của K đƣợc gọi là một khóa (Key). Số lƣợng của không gian khóa phải đủ lớn
để “kẻ địch” không đủ thời gian để thử mọi khóa có thể (phƣơng pháp vét cạn).
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
6
- Đối với mỗi
có một quy tắc mã ek: P → C và một quy tắc giải mã
tƣơng ứng dk D. Mỗi ek: P → C và dk C → P là những hàm mà: dk (ek(x)) = x với
mọi bản rõ x
P.
c. Phân loại hệ mật mã
Có nhiều cách để phân loại hệ mật mã. Dựa vào cách truyền khóa có thể phân
các hệ mật mã thành hai loại:
- Hệ mật đối xứng (hay còn gọi là mật mã khóa bí mật): là những hệ mật dùng
chung một khóa cả trong quá trình mã hóa dữ liệu và giải mã dữ liệu. Do đó khóa
phải đƣợc giữ bí mật tuyệt đối.
Hình 1.1. Cách mã hóa khóa bí mật
- Hệ mật mã bất đối xứng (hay còn gọi là mật mã khóa công khai): Các hệ mật
này dùng một khóa để mã hóa sau đó dùng một khóa khác để giải mã, nghĩa là khóa
để mã hóa và giải mã là khác nhau. Các khóa này tạo nên từng cặp chuyển đổi
ngƣợc nhau và không có khóa nào có thể suy đƣợc từ khóa kia. Khóa dùng để mã
hóa có thể công khai nhƣng khóa dùng để giải mã phải giữ bí mật.
Hình 1.2. Cách mã hóa khóa công cộng
Ngoài ra nếu dựa vào thời gian đƣa ra hệ mật mã ta còn có thể phân làm hai
loại: Mật mã cổ điển (là hệ mật mã ra đời trƣớc năm 1970) và mật mã hiện đại (ra
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
7
đời sau năm 1970). Còn nếu dựa vào cách thức tiến hành mã thì hệ mật mã còn đƣợc
chia làm hai loại là mã dòng (tiến hành mã từng khối dữ liệu, mỗi khối lại dựa vào
các khóa khác nhau, các khóa này đƣợc sinh ra từ hàm sinh khóa, đƣợc gọi là dòng
khóa) và mã khối (tiến hành mã từng khối dữ liệu với khóa nhƣ nhau)
1.1.3. Tiêu chuẩn đánh giá hệ mật mã
Để đánh giá một hệ mật mã ngƣời ta thƣờng đánh giá thông qua các tính chất sau:
- Độ an toàn: Một hệ mật mã đƣợc đƣa vào sử dụng điều đầu tiên phải có độ
an toàn cao. Ƣu điểm của mật mã là có thể đánh giá đƣợc độ an toàn thông qua độ
an toàn tính toán mà không cần phải cài đặt. Một hệ mật mã đƣợc coi là an toàn nếu
để phá hệ mật mã này phải dùng n phép toán. Mà để giải quyết n phép toán cần thời
gian vô cùng lớn, không thể chấp nhận đƣợc.
Một hệ mật mã đƣợc gọi là tốt thì nó cần phải đảm bảo các tiêu chuẩn sau:
+ Chúng phải có phƣơng pháp bảo vệ mà chỉ dựa trên sự bí mật của các khóa,
công khai thuật toán.
+ Khi cho khóa công khai ek và bản rõ P thì chúng ta dễ dàng tính đƣợc eka(P)
= C. Ngƣợc lại khi cho dk và bản mã C thì dễ dàng tính đƣợc dk(M) = P. Khi không
biết dk thì không có khả năng tìm đƣợc M từ C, nghĩa là khi cho hàm f: X → Y thì
việc tính y = f(x) với mọi x
X là dễ còn việc tìm x khi biết y lại là vấn đề khó và
nó đƣợc gọi là hàm một chiều.
+ Bản mã C không đƣợc có các đặc điểm gây chú ý, nghi ngờ.
- Tốc độ mã và giải mã: Khi đánh giá hệ mật mã chúng ta phải chú ý đến tốc
độ mã và giải mã. Hệ mật tốt thì thời gian mã và giải mã nhanh.
- Phân phối khóa: Một hệ mật mã phụ thuộc vào khóa, khóa này đƣợc truyền
công khai hay truyền khóa bí mật. Phân phối khóa bí mật thì chi phí sẽ cao hơn so
với các hệ mật có khóa công khai. Vì vậy đây cũng là một tiêu chí khi lựa chọn hệ
mật mã.
1.2. Mật mã khóa công khai
1.2.1. Giới thiệu
Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang đƣợc nghiên cứu
Alice (ngƣời gửi) và Bob (ngƣời nhận) bằng cách chọn một khóa bí mật K. Sau đó.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
8
Alice dùng khóa K để mã hóa theo luật ek và Bob dùng khóa K đó để giải mã theo
luật giải dk. Trong hệ mật này, dk hoặc giống nhƣ ek hoặc dễ dàng nhận đƣợc từ nó
vì quá trình giải mã hoàn toàn tƣơng tự nhƣ quá trình mã, nhƣng thủ tục khóa thì
ngƣợc lại. Nhƣợc điểm lớn của hệ mật này là nếu ta để lộ ek thì làm cho hệ thống
mất an toàn, chính vì vậy chúng ta phải tạo cho các hệ mật mã này một kênh an toàn
mà kinh phí để tạo một kênh an toàn không phải là rẻ.
Ý tƣởng xây dựng một hệ mật mã khóa công khai là tìm một hệ mật mã không
có khả năng tính toán để xác định dk nếu biết đƣợc ek. Nếu thực hiện đƣợc nhƣ vậy
thì quy tắc mã ek có thể đƣợc công khai bằng cách công bố nó trong danh bạ, và khi
Alice (ngƣời gửi) hoặc bất cứ một ai đó muốn gửi một bản tin cho Bob (ngƣời nhận)
thì ngƣời đó không phải thông tin trƣớc với Bob về khóa mật, mà ngƣời gửi sẽ mã
hóa bản tin bằng cách dùng luật mã công khai ek. Khi bản tin này đƣợc truyền cho
Bob (ngƣời nhận) thì chỉ có duy nhất Bob mới có thể giải đƣợc bản tin này bằng
cách sử dụng luật giải mã bí mật dk.
Ý tƣởng về hệ mật mã khóa công khai đã đƣợc Diffie và Heliman đƣa ra vào
năm 1976. Còn việc thực hiện hệ mật mã khóa công khai thì lại đƣợc Rivest. Shamin
và Adieman đƣa ra đầu tiên vào năm 1977. Họ đã tạo nên hệ mật mã RSA nổi tiếng.
Kể từ đó đã có một số hệ mật mã đƣợc công bố, độ mật của từ hệ dựa trên các bài
toán tính toán khác nhau. Trong đó quan trọng nhất là các hệ mật mã sau:
- Hệ mật mã RSA
Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên
tố các số nguyên tố lớn.
- Hệ mật mã xếp balô Merkle – Hellman.
Hệ mật mã này và các hệ có liên quan dựa trên tính khó giải của bài toán tổng
các tập con.
- Hệ mật mã McEliece
Hệ mật mã này dựa trên lý thuyết mã đại số và vẫn đƣợc coi là an toàn. Hệ mật
mã McEliece dựa trên bài toán giải mã cho các mã tuyến tính.
- Hệ mật mã ElGamal
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
9
Hệ mật mã ElGamal dựa trên tính khó giải của bài toán Logarit rời rạc trên các
trƣờng hữu hạn.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
10
- Hệ mật mã Chor – Rivest
Hệ mật mã Chor – Rivest cũng đƣợc xem nhƣ một loại hệ mật xếp balô. Tuy
nhiên hệ mật này vẫn còn đƣợc coi là hệ mật mã an toàn.
- Hệ mật mã trên các đường cong Elliptic.
Các hệ này là biến tƣớng của hệ mật mã khác, chúng làm việc trên các đƣờng
cong Elliptic chứ không phải trên các trƣờng hữu hạn. Hệ mật mã này đảm bảo độ
mật với khóa số nhỏ hơn các hệ mật khóa công khai khác. Một chú ý quan trọng là
một hệ mật mã khóa công khai không bao giờ có thể đảm bảo đƣợc độ mật tuyệt đối
(an toàn vô điều kiện). Sở dĩ nhƣ vậy vì đối phƣơng nghiên cứu một bản mã C có thể
mã lần lƣợt các bản rõ có thể bằng luật công khai ek cho tới khi anh ta tìm đƣợc một
bản rõ duy nhất P bảo đảm C = ek(P). Bản rõ P này chính là kết quả giải mã của C.
Bởi vậy ta chỉ nghiên cứu độ mật về mặt tính toán của hệ này.
Một chú ý quan trọng và có ích khi nghiên cứu nữa là khái niệm về hàm cửa
sập một chiều. Ta định nghĩa khái niệm này một cách không hình thức.
Định nghĩa 1.2
Hàm f: X→Y được gọi là hàm một chiều nếu tính y = f(x) với mọi x
X là dễ
nhưng việc tìm x khi biết y lại là vấn đề khó.
Thực ra phát biểu trên chỉ là định nghĩa phi hình thức (do thuật ngữ “khó”
đƣợc dùng đến là không định lƣợng và thậm chí sau này chúng ta đã biết là ngay cả
khi đã định lƣợng bằng sự không tồn tại thuật toán giải bài toán ngƣợc trong phạm
vi đa thức thì khái niệm “khó” nêu trên có tồn tại hay không cũng chƣa đƣợc ai
khẳng định rõ ràng) và điều đáng tiếc hơn nữa là tất cả các hàm ứng cử viên cho
khái niệm này cho đến nay chỉ mới “đƣợc coi là một chiều”.
Chúng ta dễ dàng thống nhất đƣợc với nhau là chỉ riêng hàm một chiều là không
đủ để xây dựng thành một luật mã theo kiểu công khai hàm mã hóa do vì chính bản
thân chủ nhân của bức điện mật cũng gặp phải hoàn cảnh tƣơng tự nhƣ ngƣời khác.
Nhƣ vậy để có thể giải mã một cách hữu hiệu thì ngƣời giải mã phải có một “hiểu biết
tuyệt mật” nào đó về khóa giải (một hiểu biết theo kiểu nếu biết nó thì cách giải dễ
dàng) “hiểu biết tuyệt mật” này đƣợc gọi là cửa sập. Hàm một chiều nhƣ trên đƣợc gọi
là hàm một chiều có cửa sập.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
11
Dĩ nhiên dù không biết cửa sập thì ngƣời thám mã vẫn có thể sử dụng hiểu biết
về hàm f để lần lƣợt tính tất cả các giá trị f(x) cho mọi bản rõ x cho tới khi tìm đƣợc
bản rõ thỏa mãn y = f(x). Bản rõ tìm đƣợc trên chính là kết quả giải mã của y. Ngoài
ra ngƣời thám mã còn có thể sử dụng nhiều phƣơng pháp tấn công khác nhằm vào
đặc thù riêng của từng hàm f để tìm ra bản rõ trong các trƣờng hợp riêng rẽ khác chứ
không nhất thiết phải giải bài toán ngƣợc.
Tóm lại độ an toàn của hệ mật mã khóa công khai không chỉ phụ thuộc vào độ
khó của việc giải bài toán ngƣợc mà tính bền của sự an toàn này còn phụ thuộc vào
các phƣơng pháp tấn công của các thám mã, vả lại nhƣ đã trình bày ở trên thì toàn
bộ các hệ mật mã khóa công khai đang đƣợc sử dụng đều chƣa đƣợc sự khẳng định
về tính “khó” mà ngay cả khi đã có sự đảm bảo này thì có sự tiến bộ không ngừng
của công nghệ tính toán, thì hiển nhiên nhiều vấn đề chƣa thể chấp nhận đƣợc trong
hiện tại sẽ đƣợc chấp nhận trong tƣơng lai.
Hàm mã công khai ek của Bob phải là một hàm dễ tính toán. Song việc tính
hàm ngƣợc (tức là hàm giải mã) phải rất khó khăn (đối với bất kỳ ai không phải là
Bob). Đặc tính dễ tính toán nhƣng khó tính ngƣợc thƣờng đƣợc gọi là đặc tính một
chiều. Bởi vậy điều cần thiết là ek phải là một hàm một chiều.
Các hàm một chiều đóng một vai trò trọng yếu trong mật mã học: Chúng rất
quan trọng trong việc xây dựng các hệ mật mã khóa công khai và trong nhiều lĩnh
vực khác. Đáng tiếc là, mặc dù có rất nhiều hàm đƣợc coi là hàm một chiều nhƣng
cho tới nay vẫn không tồn tại đƣợc một hàm nào có thể minh chứng đƣợc là hàm
một chiều.
Để xây dựng một hệ một hệ mật mã khóa công khai thì việc tìm một hàm một
chiều vẫn chƣa đủ. Ta không muốn ek là hàm một chiều đối với Bob vì anh ta phải
có khả năng giải mã các bản tin nhận đƣợc có hiệu quả. Điều cần thiết là Bob phải
có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm ngƣợc của ek. Nhƣ vậy
Bob có thể giải mã một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nào đó về
K. Bởi vậy một hàm đƣợc gọi là cửa sập một chiều nếu nó là hàm một chiều và nó
sẽ trở nên dễ tính ngƣợc nếu biết một cửa sập nhất định.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
12
1.2.2. Độ an toàn của mật mã công khai
Về khía cạnh an toàn, các thuật toán mật mã hóa khóa bất đối xứng cũng không
khác nhiều với các thuật toán mã hóa khóa đối xứng. Có những thuật toán đƣợc dùng
rộng rãi, có thuật toán chủ yếu trên lý thuyết; có thuật toán vẫn đƣợc xem là an toàn,
có thuật toán đã bị phá vỡ… Cũng cần lƣu ý là những thuật toán đƣợc dùng rộng rãi
không phải lúc nào cũng đảm bảo an toàn. Một số thuật toán có những chứng minh về
độ an toàn với những tiêu chuẩn khác nhau. Nhiều chứng mình gắn với việc phá vỡ
thuật toán với những bài toán nổi tiếng vẫn đƣợc cho là không có lời giải trong thời
gian đa thức. Nhìn chung, chƣa có thuật toán nào đƣợc chứng minh là an toàn tuyệt
đối (nhƣ hệ thống mật mã sử dụng khóa mật một lần). Vì vậy, cũng giống nhƣ tất cả
các thuật toán mật mã nói chung, các thuật toán mã hóa khóa công khai cần phải đƣợc
sử dụng một cách thận trọng.
1.2.3. Các ứng dụng của mật mã công khai
Ứng dụng rõ ràng nhất của mật mã hóa khóa công khai là bảo mật: một văn
bản đƣợc mã hóa bằng khóa công khai của một ngƣời sử dụng thì chỉ có thể giải mã
với khóa bí mật của ngƣời đó.
Các thuật toán tạo chữ ký số khóa công khai có thể dùng để nhận thự. Một
ngƣời sử dụng có thể mã hóa văn bản với khóa bí mật của mình. Nếu một ngƣời
khác có thể giải mã với khóa công khai của ngƣời gửi thì có thể khẳng định rằng
văn bản thực sự xuất phát từ ngƣời nắm giữ khóa bí mật tƣơng thích với khóa công
khai đó.
Các đặc điểm trên còn có ích cho nhiều ứng dụng khác nhƣ: tiền điện tử thỏa
thuận khóa…
1.2.4. Độ phức tạp tính toán của mã công khai.
Để đạt đƣợc độ an toàn tƣơng đƣơng, thuật toán mật mã hóa khóa bất đối xứng
đòi hỏi khối lƣợng tính toán nhiều hơn đáng kể so với các thuật toán mật mã hóa khóa
đối xứng. Vì thế trong thực tế hai dạng mã hóa này thƣờng đƣợc dùng một cách bổ sung
cho nhau để đạt đƣợc hiệu quả cao. Trong mô hình này, một bên tham gia trao đổi
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
13
thông tin tạo ra một khóa đối xứng dùng cho phiên giao dịch. Khóa này sẽ đƣợc trao đổi
an toàn thông quan hệ thống mã hóa khóa bất đối xứng. Sau đó hai bên trai đổi thông
tin bí mật bằng hệ thống mã hóa đối xứng trong suốt phiên giao dịch.
1.2.5. Những vấn đề về thám mã
Tồn tại khả năng một ngƣời nào đó có thể tìm ra đƣợc khóa bí mật. Không
giống với hệ thống mật mã sử dụng một lần (one-time pad) hoặc tƣơng đƣơng, chƣa
có thuật toán mã hóa khóa bất đối xứng nào đƣợc chứng minh là an toàn trƣớc các
tấn công dựa trên bản chất toán học của thuật toán. Khả năng tồn tại một mối quan
hệ nào đó giữa 2 khóa hay một điểm yếu của thuật toán dẫn tới cho phép giải mã
không cần tới khóa hay chỉ cần khóa mã mã công khai vẫn chƣa đƣợc loại trừ. An
toàn của các thuật toán này đều dựa trên các ƣớc lƣợng về khối lƣợng các phép tính
cần phải tính toán để giải các bài toán gắn với chúng nhƣng các ƣớc lƣợng này lại
luôn thay đổi tùy thuộc khả năng của máy tính và các phát hiện toán học mới.
Mặc dù vậy, độ an toàn của các thuật toán mật mã khóa công khai cũng tƣơng
đối đảm bảo. Nếu thời gian để phá một mã (bằng phƣơng pháp duyệt toàn bộ) đƣợc
ƣớc lƣợng là 1000 năm thì thuật toán này hoàn toàn có thể dùng để mã hóa các
thông tin về thẻ tín dụng – Rõ ràng là thời gian phá mã lớn hơn nhiều lần thời gian
tồn tại của thẻ (vài năm).
Nhiều điểm yếu của một số thuật toán mật mã hóa khóa bất đối xứng đã đƣợc
tìm ra trong quá khứ. Thuật toán đóng gói ba lô là một ví dụ. Nó chỉ đƣợc xem là
không an toàn khi một dạng tấn công không lƣờng trƣớc bị phát hiện. Gần đây, một
số dạng tấn công đã đơn giản hóa việc tìm khóa giải mã dựa trên việc đo đạc chính
xác thời gian mà một hệ thống phần cứng thực hiện mã hóa. Vì vậy, việc sử dụng
mã hóa khóa bất đối xứng không thể đảm bảo an toàn tuyệt đối. Đây là một lĩnh vực
đang đƣợc tích cực nghiên cứu để tìm ra những dạng tấn công mới.
Một điểm yếu tiềm tàng trong việc sử dụng khóa bất đối xứng là khả năng bị
tấn công dạng kẻ tấn công đứng giữa (man in the middle attack): kẻ tấn công lợi
dụng việc phân phối khóa công khai để thay đổi khóa công khai. Sau khi đã giả mạo
đƣợc khóa công khai, kẻ tấn công đứng ở giữa 2 bên để nhận các gói tin, giải mã rồi
lại mã hóa khóa đúng và gửi đến nơi nhận để tránh bị phát hiện. Dạng tấn công kiểu
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
14
này có thể phòng ngừa bằng các phƣơng pháp trao đổi khóa an toàn nhằm đảm bảo
nhận thực ngƣời gửi và toàn vẹn thông tin. Một điều cần lƣu ý là khi các chính phủ
quan tâm đến dạng tấn công này: họ có thể thuyết phục (hay bắt buộc) nhà cung cấp
chứng thực số xác nhận một khóa giả mạo và có thể đọc các thông tin mã hóa.
1.3. Hàm băm mật mã
1.3.1. Tổng quan về hàm băm
a. Định nghĩa hàm băm
Hàm băm mật mã là hàm toán học chuyển đổi một thông điệp có độ dài bất kỳ
thành một dãy bit có độ dài cố định (tùy thuộc vào thuật toán băm). Dãy bit này
đƣợc gọi là thông điệp rút gọn (message digest) hay giá trị băm (hash value), đại
diện cho thông điệp ban đầu.
Ví dụ 1.1
Nhƣ khi B muốn kí một bức điện x (độ dài bất kì), đầu tiên anh ta tính cốt của
bức điện z = h(x) (độ dài cố định) và sau đó kí y = sigk9(z). Anh ta phát cặp (x,y) lên
kênh truyền, bây giờ việc kiểm tra có thể thực hiện bằng việc tính lại cốt của bức
điện z = h(x), sau đó kiểm tra verk(x,y) có băng TRUE hay không.
Hình 1.3. Hàm băm trong chữ ký số
Dễ dàng nhận thấy rằng hàm băm h không phải là một song ánh. Do đó, với
thông điệp x bất kỳ, tồn tại thông điệp x’ ≠ x sao cho h(x) = h(x’). Lúc này ta nói
rằng “có sự đụng độ xảy ra”. Một hàm băm h đƣợc gọi là an toàn (hay “ít bị đụng
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
15
độ”) khi không thể xác định đƣợc (bằng cách tính toán) cặp thông điệp x và x‟ thỏa
mãn x’ ≠ xvà h(x) = h(x’). Trên thực tế, các thuật toán băm là hàm một chiều, do đó,
rất khó để xây dựng lại thông điệp ban đầu từ thông điệp rút gọn.
Hàm băm giúp xác định đƣợc tính toàn vẹn dữ liệu của thông tin: mọi thay đổi,
dù là rất nhỏ, trên thông điệp cho trƣớc, ví dụ nhƣ đổi giá trị 1 bit, đều làm thay đổi
thông điệp rút gọn tƣơng ứng. Tính chất này hữu ích trong việc phát sinh, kiểm tra
chữ ký số, các đoạn mã chứng nhận thông điệp, phát sinh số ngẫu nhiên, tạo ra khóa
cho quá trình mã hóa…
b. Tính an toàn của hàm băm.
- Tính an toàn của hàm băm đối với hiện tƣợng đụng độ
Hàm băm đƣợc xem là an toàn đối với hiện tƣợng đụng độ khi rất khó tìm
đƣợc hai thông điệp có cùng giá trị băm.
Nhận xét: Trong một tập hợp mà các phần tử mang một trong N giá trị cho
trƣớc với xác suất bằng nhau, chúng ta cần khoảng
phép thử ngẫu nhiên để tìm
ra một cặp phần tử có cùng giá trị.
Nhƣ vậy, phƣơng pháp hàm băm đƣợc xem là an toàn đối với hiện tƣợng đụng
độ nếu chƣa có phƣơng pháp tấn công nào có thể tìm ra cặp thông điệp có cùng giá
trị hàm băm với số lƣợng tính toán ít hơn đáng kể so với ngƣỡng 2n/2, với n là kích
thƣớc (tính bằng bit) của giá trị băm.
Phƣơng pháp tấn công dựa vào đụng độ:
+ Tìm ra 2 thông điệp có nội dung khác nhau nhƣng cùng giá trị băm.
+ Ký trên một thông điệp, sau đó, ngƣời ký sẽ không thừa nhận đây là chữ ký
của mình mà nói rằng mình đã ký trên một thông điệp khác.
+ Nhƣ vậy, cần phải chọn 2 thông điệp “đụng độ” với nhau trƣớc khi ký.
-
Tính 1 chiều
Hàm băm đƣợc xem là hàm một chiều khi cho trƣớc giá trị băm, không thể tái
tạo lại thông điệp ban đầu, hay còn gọi là “tiềm ảnh” (“pre-image”). Nhƣ vậy, trong
trƣờng hợp lý tƣởng, cần phải thực hiện hàm băm cho khoảng 2n thông điệp để tìm
ra đƣợc “tiềm ảnh” tƣơng ứng với một giá trị băm.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
- Xem thêm -
.PDF 
79 
115 
84 
