i
đại học thái nguyên
Tr-ờng đại học CÔNG NGHệ THÔNG TIN Và TRUYềN THÔNG
V QUC THNH
TèM HIU MT S PHNG PHP
THM M H MT M KHểA CễNG KHAI
NG DNG TRONG BO MT D LIU
LUN VN THC S KHOA HC MY TNH
thái nguyên - năm 2014
S húa bi Trung tõm Hc liu i hc Thỏi Nguyờn
/>
ii
®¹i häc th¸i nguyªn
Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG
VŨ QUỐC THỊNH
TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP
THÁM MÃ HỆ MẬT MÃ KHÓA CÔNG KHAI
ỨNG DỤNG TRONG BẢO MẬT DỮ LIỆU
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Vũ Quốc Thịnh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
iv
ĐỊNH NGHĨA, VIẾT TẮT
Advanced Encryption Standard (AES)
Tiêu chuẩn tiên tiến
Asymmetric key cryptography
Mã hóa bất đối xứng
Authentication
Tính xác thực
Cipher text
Bản mã
Concatenate frequency of pairs
Tần số bộ đôi móc xích
Confidentiality
Integrity
Tính toàn vẹn
Key seed
Mầm khóa
Most Likelihood Ratio (MLR)
Tỷ số hợp lý cực đại
Non – repudation
Tính không thể chối bỏ
Plain text
Bản rõ
Private key
Khóa bí mật
Public key
Khóa công khai
Relative frequency
1.3. Phân loại các hệ mật mã ...................................................................................6
1.3.1. Mã hóa đối xứng .......................................................................................6
1.3.2. Mã hóa bất đối xứng .................................................................................7
1.4. Tiêu chuẩn đánh giá hệ mật mã......................................................................10
1.5. Hệ mật mã RSA .............................................................................................10
1.5.1. Mô tả hệ mật RSA ...................................................................................11
1.5.2. Thực thi hệ RSA......................................................................................13
1.5.3. Độ an toàn của hệ RSA ...........................................................................14
1.6. Thám mã .........................................................................................................15
1.6.1. Khái niệm ................................................................................................15
1.6.2. Các bƣớc cơ bản để tiến hành thám mã ..................................................19
1.7. Kết luận ..........................................................................................................26
CHƢƠNG 2: CÁC PHƢƠNG PHÁP THÁM MÃ HỆ MẬT MÃ KHÓA CÔNG
KHAI ............................................................................................................................. 27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
vi
2.1. Tính an toàn của hệ mật mã ...........................................................................27
2.1.1. An toàn vô điều kiện ...............................................................................27
2.1.2. An toàn đƣợc chứng minh .......................................................................27
2.1.3. An toàn tính toán .....................................................................................27
2.2. Các kiểu thám mã ...........................................................................................28
2.2.1. Tấn công dạng 1: Tìm cách xác định khóa bí mật ..................................28
2.2.2. Tấn công dạng 2: Tìm cách xác định bản rõ ...........................................30
2.3. Một số sơ hở dẫn đến tấn công hệ mật RSA ..................................................32
2.3.1. Biết (n) tìm đƣợc p, q ............................................................................33
2.3.2. Biết số mũ giải a ......................................................................................33
2.3.3. Giao thức công chứng .............................................................................34
viii
DANH MỤC HÌNH VẼ
Hình 1.1: Quá trình mã hóa và giải mã ........................................................................... 5
Hình 1.2: Mã hóa thông điệp sử dụng khóa công khai P ............................................... 8
Hình 1.3: Giải mã thông điệp sử dụng khóa riêng của ngƣời nhận ............................... 8
Hình 1.4: Mã hóa thông điệp sử dụng khóa bí mật S để mã thông điệp và................... 9
Hình 1.5: Giải mã thông điệp sử dụng khóa bí mật S để giải mã thông điệp và ........... 9
Hình 1.6: Sơ đồ biểu diễn thuật toán mã hóa RSA ...................................................... 13
Hình 3.1: Lƣu đồ giải thuật thám mã RSA ................................................................... 50
Hình 3.2: Giao diện chính của chƣơng trình thám mã RSA ........................................ 52
Hình 3.3: Nhập các tham số RSA ................................................................................ 53
Hình 3.4: Tính khóa bí mật d1, d2 ................................................................................ 54
Hình 3.5: Mã hóa ........................................................................................................... 55
Hình 3.6: Mã hóa thông điệp ........................................................................................ 56
Hình 3.7: Thám mã tìm ra khóa bí mật d1.................................................................... 57
Hình 3.8: Giải mã tìm ra bản rõ theo khóa d1 .............................................................. 58
Hình 3.9: Giải mã tìm ra thông điệp ............................................................................. 59
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
1
LỜI NÓI ĐẦU
Từ khi con ngƣời có nhu cầu trao đổi thông tin, thƣ từ với nhau thì nhu cầu
giữ bí mật và bảo mật tính riêng tƣ của những thông tin, thƣ từ đó cũng nảy sinh.
Hình thức thông tin trao đổi phổ biến sớm nhất là dƣới dạng các văn bản, để giữ bí
mã hiện đại nhằm góp phần bảo vệ an ninh thông tin trong tình hình mới nên em đã
chọn đề tài “Tìm hiểu một số phương pháp thám mã hệ mật mã khóa công khai
ứng dụng trong bảo mật dữ liệu” nhằm nghiên cứu và ứng dụng.
Trong khuôn khổ đề tài đƣợc giao, luận văn đƣợc trình bày trong 3 chƣơng.
Có phần mở đầu, phần kết luận, phần mục lục, 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 nhƣ sau:
Chƣơng 1: “Tổng quan về mật mã khóa công khai và thám mã”. Ở chƣơng
này, luận văn trình bày chi tiết về lịch sử cũng nhƣ các khái niệm về các hệ mã
thuộc dòng mã truyền thống cũng nhƣ dòng mã đối xứng, mã bất đối xứng giúp
chúng ta hiểu cơ sở lý thuyết về các hệ mật mã. Vấn đề thám mã nói chung và thám
mã đối với hệ mật RSA cũng đƣợc em trình bày kỹ trong chƣơng này.
Chƣơng 2: “Các phƣơng pháp thám mã hệ mật mã khóa công khai”.
Trên cơ sở hiểu các hệ mật đƣợc trình bày ở chƣơng 1, để có cái nhìn tổng quan về
vấn đề thám mã đối với hệ mật RSA và trên cơ sở trình bày các phƣơng pháp thám
mã đã tổng kết lại các phƣơng pháp và đánh giá kết quả của phƣơng pháp nhƣ: các
tấn công cơ bản - modul chung, tấn công vào số mũ công khai hoặc số mũ bí mật
nhỏ, giao thức công chứng...
Chƣơng 3: “Thử nghiệm phƣơng pháp thám mã với hệ RSA”. Qua nghiên
cứu các phƣơng pháp thám mã trong chƣơng 2, chƣơng 3 đề xuất phƣơng pháp tấn
công giao thức sử dụng hệ mật mã RSA có modul n chung. Để minh chứng cho
phƣơng pháp này, luận văn xây dựng thuật toán và cài đặt chƣơng trình thử nghiệm
trong hệ bảo mật.
Do mức độ phức tạp của công việc thám mã là rất lớn nên bài toán đặt ra với
giả thiết ngƣời thám mã biết đƣợc các thông tin và bản mã đƣợc mã hóa bởi RSA từ
bản rõ tƣơng ứng là một thông điệp dạng Text. Từ giả thiết này xây dựng thuật toán
để xác định khóa mật K đã sử dụng để mã hóa cũng nhƣ tìm ra bản rõ tƣơng ứng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
4
Mật mã (Cryptography) là tập hợp mọi phƣơng pháp (hoặc quy tắc) biến đổi
nào đó nhằm chuyển các thông báo (messages) dƣới dạng nhận thức đƣợc nội dung
(nhƣ chữ viết, tiếng nói, hình vẽ, hình ảnh…) thành dạng bí mật mà những ngƣời
ngoài cuộc không hiểu đƣợc nội dung nếu họ không biết đƣợc phƣơng pháp (hoặc
quy tắc) biến đổi đó.
1.2.2. Mật mã học
Mật mã học (Cryptology) là một bộ môn khoa học chuyên nghiên cứu về mật
mã và thám mã.
1.2.3. Bản rõ
Ta hiểu bản rõ (Plain text) tức là một bản thông báo có mang nội dung thông
tin mà ngƣời đọc có thể hiểu đƣợc nó nói cái gì hoặc là nó có ý nghĩa rõ ràng. Bản
rõ (bản thông báo) có thể tồn tại dƣới dạng chữ viết, tiếng nói, hình vẽ, biểu bảng…
tƣơng ứng ta sẽ có khái niện mã ký tự, mã thoại, mã fax, mã dữ liệu…
Bản rõ thƣờng đƣợc dùng biểu diễn (viết) dƣới dạng một dãy các chữ cái
theo quy tắc cú pháp nào đó hoặc ký hiệu thuộc bảng chữ cái A hữu hạn đƣợc xác
định trƣớc. Để trình bày, ta ký hiệu M là không gian các bản rõ (message space). Ví
dụ: M có thể là gồm dãy nhị phân, các văn bản tiếng Việt, hoặc mã chƣơng trình
của máy tính…
1.2.4. Bản mã
Bản mã (Cipher text) thƣờng cũng đƣợc biểu diễn dƣới dạng một dãy các ký
hiệu có thể cũng thuộc A nhƣng không theo một quy tắc cú pháp nào cả. Ngƣời ta
nói rằng đó là dãy ngẫu nhiên. Ta ký hiệu tập tất cả các bản mã ứng với các bản rõ
m là C.
1.2.5. Mã hóa
Hệ mật hiện đại cần phải đáp ứng đƣợc những yêu cầu sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
6
- Tính bảo mật (Confidentiality): đảm bảo dữ liệu đƣợc truyền đi một cách
an toàn và không bị lộ nếu nhƣ ai đó cố tình muốn có đƣợc thông điệp gốc ban đầu.
Chỉ những ngƣời đƣợc phép mới có khả năng đọc đƣợc nội dung thông tin ban đầu.
- Tính xác thực (Authentication): giúp cho ngƣời nhận thông điệp các định
đƣợc chắc chắn thông điệp mà họ nhận là thông điệp gốc ban đầu. Kẻ giả mạo không
thể giả dạng một ngƣời khác hay nói cách khác không thể mạo danh để gửi thông
điệp. Ngƣời nhận có khả năng kiểm tra nguồn gốc thông điệp mà họ nhận đƣợc.
- Tính toàn vẹn (Integrity): ngƣời nhận thông điệp có thể kiểm tra thông điệp
không bị thay đổi trong quá trình truyền đi. Kẻ giả mạo không thể có khả năng thay
thế dữ liệu ban đầu bằng dữ liệu giả mạo.
- Tính không thể chối bỏ (Non - repudation): ngƣời gửi, ngƣời nhận không
thể chối bỏ sau khi đã gửi hoặc nhận thông điệp.
1.3. Phân loại các hệ mật mã
Công nghệ thông tin phát triển, việc sử dụng máy tính gia tăng cùng với tốc độ
phát triển mạnh mẽ của Internet càng làm tăng nguy cơ bị đánh cắp các thông tin độc
quyền. Với mối đe dọa đó có nhiều biện pháp để đối phó song mã hóa là một phƣơng
pháp chính để có thể bảo vệ các giá trị của thông tin điện tử. Có thể nói mã hóa là công
cụ tự động, quan trọng nhất cho an ninh mạng và truyền thông. Có hai hình thức mã
hóa đƣợc sử dụng phổ biến là mã hóa đối xứng (symmetric - key cryptography) và mã
hóa bất đối xứng (asymmetric key cryptography).
1.3.1. Mã hóa đối xứng
Thuật toán đối xứng hay còn gọi là thuật toán mã hóa cổ điển. Thuật toán
này còn có nhiều tên gọi khác nhƣ thuật toán khóa bí mật, thuật toán đơn giản, thuật
toán một khóa.
Trong hệ mật này, khóa mã hóa khác với khóa giải mã. Về mặt toán học thì từ khóa
công rất khó tính đƣợc khóa riêng. Biết đƣợc khóa này không dễ dàng tìm đƣợc
khóa kia. Khóa giải mã đƣợc giữ bí mật trong khi khóa mã hóa đƣợc công bố công
khai. Một ngƣời bất kỳ có thể sử dụng khóa công khai để mã hóa tin tức, nhƣng chỉ
có ngƣời nào có đúng khóa giải mã mới có khả năng xem đƣợc bản rõ.
Ngƣời gửi A sẽ mã hóa thông điệp bằng khóa công của ngƣời nhận và ngƣời
nhận B sẽ giải mã thông điệp với khóa riêng tƣơng ứng của mình.
Quá trình này đƣợc mô tả trong hình 1.2 và 1.3.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
8
Hình 1.2: Mã hóa thông điệp sử dụng khóa công khai P
Hình 1.3: Giải mã thông điệp sử dụng khóa riêng của người nhận
Việc phát minh ra phƣơng pháp mã công khai tạo ra một cuộc “cách mạng”
trong công nghệ an toàn thông tin điện tử. Nhƣng thực tiễn triễn khai cho thấy tốc độ
mã hóa khối dữ liệu lớn bằng các thuật toán mã hóa công khai chậm hơn rất nhiều so
với hệ mã hóa đối xứng. Ví dụ, để đạt đƣợc độ an toàn nhƣ các hệ mã đối xứng mạnh
cùng thời, RSA đòi hỏi thời gian cho việc mã hóa một văn bản lâu hơn gấp hàng ngàn
lần. Do đó, thay bằng việc mã hóa văn bản có kích thƣớc lớn bằng lƣợc đồ khóa công
khai thì văn bản này sẽ đƣợc mã hóa bằng một hệ mã đối xứng có tốc độ cao nhƣ
DES, IDEA,…sau đó khóa đƣợc sử dụng trong hệ mã đối xứng sẽ đƣợc mã hóa sử
dụng mật mã khóa công khai. Phƣơng pháp này rất khả thi trong việc mã và giải mã
những văn bản có kích thƣớc lớn nhƣ đƣợc mô tả trong hình 1.4 và 1.5.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1.4. 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 đƣợ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 đƣợ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.
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.5. Hệ mật mã RSA
Có nhiều hệ thống khóa công khai đƣợc triển khai rộng rãi nhƣ hệ RSA, hệ
ElGamal sử dụng giao thức trao đổi khóa Diffie-Hellman và nổi lên trong những
năm gần đây là hệ đƣờng cong Elliptic. Trong số các hệ mật mã trên thì hệ RSA là
hệ đƣợc cộng đồng chuẩn quốc tế và công nghiệp chấp nhận rộng rãi trong việc
thực thi mật mã khóa công khai.
Hệ mật mã RSA, do Rivest, Shamir và Adleman tìm ra, đã đƣợc công bố lần
đầu tiên vào tháng 8 năm 1977 trên tạp chí Scientific American. Hệ mật mã RSA
đƣợc sử dụng rộng rãi trong thực tiễn đặc biệt cho mục đích bảo mật và xác thực dữ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
11
liệu số. Tính bảo mật và an toàn của chúng đƣợc bảo đảm bằng độ phức tạp của một
bài toán số học nổi tiếng là bài toán phân tích số nguyên thành các thừa số nguyên tố.
Hệ mật mã RSA đƣợc sử dụng để cung cấp sự bảo mật và đảm bảo tính xác
Vì ab
1(mod (n)) nên ta có ab = t. (n) + 1 với một số nguyên t
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1 nào đó.
/>
12
Giả sử x
Zn ;
a. Trƣờng hợp (x,n) =1
Khi đó ta có:
x
(n)
mod n = 1.
ya modn
(xb)a mod n
xt
pab mod q
p.p
(n)
p.p
(p). (q)
p.(p
Vậy ya modn
mod q
(p)
)
mod q
(q)
mod q
p
h.p modn = h.p = x.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
m = cd mod n
Hình 1.6: Sơ đồ biểu diễn thuật toán mã hóa RSA
Bản rõ gốc m
mm
Sau đây là một ví dụ về cách thức thực hiện của hệ RSA (tất nhiên không mật).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
14
Giả sử Bob chọn p = 101 và q = 113. Khi đó n = 11413 và (n) = 100 x 112
= 11200. Bob chọn ngẫu nhiên một số b và kiểm tra điều kiện UCLN ( (n), b) = 1
bằng thuật toán Euclide. Giả sử Bob chọn b = 3533, khi đó theo thuật toán Euclid
mở rộng: b-1 = 6597 mod 11200.
Bởi vậy, số mũ bí mật để giải mã của Bob là a = 6597.
Bob sẽ công bố n = 11413 và b = 3533 trong một danh bạ khóa công khai.
Bây giờ, giả sử Alice muốn gửi bản rõ x = 9726 tới Bob. Cô ta sẽ tính:
97263533 mod 11413 = 5761
rồi gửi bản mã 5761 trên kênh.
Khi Bob nhận đƣợc bản mã 5761, anh ta sử dụng số mũ bí mật a để tính ra x:
57616597mod 11413 = 9726.
1.5.3. Độ an toàn của hệ RSA
a. Bài toán phân tích số và việc phá hệ mật RSA
Cách tấn công dễ thấy nhất đối với hệ mật RSA là ngƣời thám mã sẽ cố gắng
phân tích n ra các thừa số nguyên tố n = p*q. Nếu thực hiện đƣợc phép phân tích
này thì có thể dễ dàng tính đƣợc (n) = (p - 1).(q - 1) và do đó tìm đƣợc thông tin
cửa sập d tƣơng ứng với thông tin mã hóa E bằng thuật toán Euclude. Nhƣ vậy
1.6.1. Khái niệm
Thám mã là quá trình khôi phục lại bản rõ hoặc khóa khi chỉ có bản mã
tƣơng ứng cho trƣớc (không biết khóa và quy tắc mã/dịch) gọi là thám mã. Ngƣời
làm công tác thám mã đƣợc gọi là ngƣời mã thám (Cryptanalysist) hay gọi là mã
thám viên.
Tổ chức làm công tác thám mã đƣợc gọi là đơn vị mã thám. Mã thám là một
bộ phận không thể thiếu của ngành tình báo điện tử. Hầu hết các quốc gia đều có bộ
phận tình báo điện tử này, nhƣng sự phát triển và hiệu quả của nó lại phụ thuộc vào
trình độ khoa học - công nghệ của từng nƣớc. Nƣớc nào có trình độ khoa học - công
nghệ càng cao thì khả năng của công tác thám mã nói riêng, tình báo điện tử nói
chung càng mạnh.
Mục tiêu của thám mã: Mục tiêu của thám mã (phá mã) là tìm những điểm yếu
hoặc không an toàn tổng phƣơng pháp mật mã hóa.Thám mã có thể đƣợc thực hiện
bởi những kẻ tấn công ác ý, nhằm làm hỏng hệ thống; hoặc bởi những ngƣời thiết kế
ra hệ thống với ý định đánh giá độ an toàn của hệ thống.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
16
Để nghiên cứu thám mã đƣợc các bản mã truyền thống, ngƣời mã thám phải
nghiên cứu các đặc trƣng cơ bản của bản rõ. Nói một cách khác, trong mọi ngôn
ngữ tự nhiên đều có những đặc trƣng bất biến mà mã thám viên cần nắm vững để
phục vụ việc phân tích các bản mã. Đó là quy luật tần số, quy luật trùng lặp, quy
luật văn phong, v.v...
a. Tần số (Frequency)
Ngƣời ta định nghĩa tần số xuất hiện một ký tự, một nhóm ký tự, một từ hay
một vần v.v... trong một văn bản là số lần xuất hiện của ký tự, nhóm ký tự, từ, vần
đó trong văn bản đã cho.
Ngƣời ta có thể tính tần số từ một hoặc nhiều văn bản (thông báo) của một
Trong thực tế, các loại văn bản khác nhau sẽ có văn phong không giống nhau
do phụ thuộc vào thói quen của từng ngƣời soạn thảo ra văn bản đó. Đây cũng là
quy luật đáng lƣu ý trong việc thám mã. Văn phong đƣợc chia thành các dạng:
- Dạng đầu văn bản (gọi là quy luật đầu điện):
Ví dụ: Công điện số…, báo cáo số…, kính gửi ông…, căn cứ Công văn số…,
phúc đáp Công văn số…
- Dạng thân văn bản (quy luật thân điện): Văn bản thƣờng có chia theo từng
mục hoặc không chia theo mục; Nội dung văn bản có khác nhau tuỳ theo từng loại
nội dung nhƣ ngoại giao, tình báo, quân sự, kinh tế, chính trị v.v...;
- Dạng cuối văn bản (quy luật cuối điện): Đoạn kết thúc một văn bản thƣờng
cũng có những quy luật: Mỗi ngƣời soạn thảo văn bản khác nhau sẽ có quy luật
khác nhau.
Ví dụ, thƣờng chấm hết thì có chữ stop, stopend; câu chào Salam và sau cùng
là tên, chức vụ, cấp bậc của ngƣời gửi thông báo, v.v... Những thông tin này đôi khi
rất quan trọng, giúp nhà mã thám thành công trong nhiệm vụ của mình.
d. Quy luật tình huống
Nhƣ đã đƣợc trình bày ở phần trƣớc, thám mã là tìm mọi biện pháp có thể để
khôi phục lại bản rõ và/hoặc khóa mã từ một số bản mã cho trƣớc. Điều này cho
thấy thám mã là một loại công việc khó khăn và phức tạp, nó vừa mang tính khoa
học lại vừa mang tính nghệ thuật. Rõ ràng, khoa học về mật mã càng phát triển thì
kỹ thuật thám mã càng gặp nhiều khó khăn.
Để chống lại việc thám mã của đối phƣơng, các nhà sản xuất mật mã phải
thiết kế các thuật toán mã hóa và các loại khóa mã sao cho các thông tin về khóa mã
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
/>
Copyright: Tài liệu đại học ©