CHƯƠNG MỞ ĐẦU
1.Tên đề tài:
LÝ THUYẾT ĐỘ PHỨC TẠP VÀ ỨNG DỤNG
2.Lý do chọn đề tài
Trong mọi thời đại thông tin đều có ý nghĩa không thể thiếu đối với con người cùng với các hoạt động kinh tế, chính trị và xã hội. Đặc biệt ở thế kỷ 21, thế kỷ công nghệ thông tin, thông tin được khai thác triệt để, nó đóng vai trò ngày càng quan trọng hơn đối với mọi quốc gia trên thế giới. Do đó chúng ta phải làm sao bảo đảm được tính trong suốt của thông tin nghĩa là thông tin không bị thay đổi , sai lệch, lộ trong suốt quá trình chuyển từ nơi gửi đến nơi nhận
Ngày nay với sự xuất hiện của máy tính hiện đại và mạng máy tính đang trở thành công cụ đắc lực phục vụ cho mọi mặt của đời sống xã hội.
Lý thuyết độ phức tạp là vấn đề trung tâm đang được nghiên cứu của ngành khoa học máy tính. Việc nghiên cứu lý thuyết độ phức tạp và ứng dụng của nó vừa là cơ sở động lực cho khoa học máy tính phát triển, vừa góp phần hiệu quả vào việc giải quyết các bài toán trong thực tế.
Ngoài những yêu cầu do thực tế và xã hội đặt ra, việc lựa chọn đề tài còn xuất phát từ việc yêu thích môn học chuyên đề lý thuyết độ phức tạp của thuật toán nói riêng và của khoa học máy tính nói chung
3. Mục đích, nhiệm vụ của đề tài
* Mục đích:
- Tìm hiểu sâu về lý thuyết độ phức tạp và mật mã khoá công khai RSA
- Xây dựng chương trình ứng dụng áp dụng lý thuyết độ phức tạp có ý nghĩa thực tiễn
* Nhiệm vụ:
- Đưa ra một báo cáo tìm hiểu về lý thuyết độ phức tạp và mật mã khoá công khai RSA
- Xây dựng được chương trình áp dụng lý thuyết độ phức tạp có ý nghĩa thực tiễn
30 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 3548 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Đề tài Lý thuyết độ phức tạp và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO KHOA HỌC
ĐỀ TÀI:
LÝ THUYẾT ĐỘ PHỨC TẠP VÀ ỨNG DỤNG
Chuyên ngành : Khoa học máy tính
Giáo viên hướng dẫn : PGS.TSKH.Vũ Đình Hòa.
Sinh viên thực hiện: Lưu Thị Lan Hương
Lớp _K54A.
Hà Nội , 4/2008.
CHƯƠNG MỞ ĐẦU
Tên đề tài
Lý do chọn đề tài
Mục đích, nhiệm vụ của đề tài
CHƯƠNG I. TỔNG QUAN VỀ THUẬT TOÁN
Định nghĩa thuật toán
Các đặc trưng của thuật toán
Phân tích thuật toán và đánh giá thời gian thực hiện thuật toán
Phân tích thuật toán
Tại sao lại cần có thuật toán hiệu quả
Các bước phân tích thuật toán
Tính hiệu quả của thuật toán
Đánh giá thời gian thực hiện thuật toán
Các vấn đề liên quan đến thuật toán
Thiết kế thuật toán
Tính đúng đắn của thuật toán
Biểu diễn thuật toán
CHƯƠNG II. LÝ THUYẾT ĐỘ PHỨC TẠP
2.1 Máy tính Turing tất định
2.1.1 Định nghĩa
2.1.2 Cấu tạo
2.1.3 Hoạt động
2.2 Máy tính Turing không tất định
2.1.1 Định nghĩa
2.1.2 Cấu tạo
2.1.3 Hoạt động
2.3 Các bài toán quyết định
2.4 Các bài toán lớp P, NP và mối quan hệ giữa lớp P và lớp NP
2.4.1 Các bài toán lớp P
2.4.2 Các bài toán lớp NP
2.4.3 Mối quan hệ giữa lớp P và lớp NP
2.5 Bài toán lớp NPC
2.5.1 Phép dẫn với thời gian đa thức
2.5.2 Bài toán lớp NPC
2.5.3 Mối quan hệ giữa các bài toán lớp P, NP và NPC
2.5.4 Một số bài toán NPC
2.5.4.1 Bài toán SAT
2.5.4.2 Bài toán 3-CNF-SAT
2.5.4.3 Bài toán Vertex-Cover
2.5.4.4 Bài toán Clique
2.5.4.5 Bài toán Subset-Sum
2.5.4.6 Bài toán Knapsack
2.5.4.7 Bài toán Hamilton Cycle
2.5.4.8 Bài toán Traveling Salesman
CHƯƠNG III. MẬT MÃ VÀ MẬT MÃ KHOÁ CÔNG KHAI RSA
I. Mật mã
1. Định nghĩa về mật mã và hệ mật mã
1.1 Một số khái niệm trong mật mã
1.2 Định nghĩa về hệ mật mã
2.Một số yêu cầu đối với hệ mật mã
II. Mật mã khoá công khai RSA
1. Đặt vấn đề
2. Giải thuật RSA
2.1 Chọn khoá
2.2 Mã hoá
2.3 Giải mã
2.4 Ví dụ minh hoạ
3. Ðộ an toàn của hệ RSA
4. Ứng dụng của hệ mật mã RSA
5. Chữ ký điện tử
5.1 Giới thiệu về chữ ký điện tử và vấn đề xác nhận
5.2 Sơ đồ chữ ký RSA
5.3 Tấn công chữ ký điện tử
CHƯƠNG IV. DEMO VỚI RSA
CHƯƠNG MỞ ĐẦU
1.Tên đề tài:
LÝ THUYẾT ĐỘ PHỨC TẠP VÀ ỨNG DỤNG
2.Lý do chọn đề tài
Trong mọi thời đại thông tin đều có ý nghĩa không thể thiếu đối với con người cùng với các hoạt động kinh tế, chính trị và xã hội. Đặc biệt ở thế kỷ 21, thế kỷ công nghệ thông tin, thông tin được khai thác triệt để, nó đóng vai trò ngày càng quan trọng hơn đối với mọi quốc gia trên thế giới. Do đó chúng ta phải làm sao bảo đảm được tính trong suốt của thông tin nghĩa là thông tin không bị thay đổi , sai lệch, lộ trong suốt quá trình chuyển từ nơi gửi đến nơi nhận
Ngày nay với sự xuất hiện của máy tính hiện đại và mạng máy tính đang trở thành công cụ đắc lực phục vụ cho mọi mặt của đời sống xã hội.
Lý thuyết độ phức tạp là vấn đề trung tâm đang được nghiên cứu của ngành khoa học máy tính. Việc nghiên cứu lý thuyết độ phức tạp và ứng dụng của nó vừa là cơ sở động lực cho khoa học máy tính phát triển, vừa góp phần hiệu quả vào việc giải quyết các bài toán trong thực tế.
Ngoài những yêu cầu do thực tế và xã hội đặt ra, việc lựa chọn đề tài còn xuất phát từ việc yêu thích môn học chuyên đề lý thuyết độ phức tạp của thuật toán nói riêng và của khoa học máy tính nói chung
3. Mục đích, nhiệm vụ của đề tài
* Mục đích:
- Tìm hiểu sâu về lý thuyết độ phức tạp và mật mã khoá công khai RSA
- Xây dựng chương trình ứng dụng áp dụng lý thuyết độ phức tạp có ý nghĩa thực tiễn
* Nhiệm vụ:
- Đưa ra một báo cáo tìm hiểu về lý thuyết độ phức tạp và mật mã khoá công khai RSA
- Xây dựng được chương trình áp dụng lý thuyết độ phức tạp có ý nghĩa thực tiễn
CHƯƠNG 1
TỔNG QUAN VỀ THUẬT TOÁN
1. Định nghĩa thuật toán
Ta có thể định nghĩa (không chính thức) về thuật toán như sau:
Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, hoặc hành động cần thực hiện… để cho ta lời giải của bài toán
1.2 Các đặc trưng của thuật toán
1.2.1 Đầu vào (Input)
Đầu vào của thuật toán chính là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các giá trị này cần được lấy từ các tập hợp giá trị cụ thể nào đó.
1.2.2 Đầu ra (Output)
Mỗi thuật toán có một hoặc nhiều dữ liệu ra. Đó là các dữ liệu có quan hệ hoàn toàn xác định với các dữ liệu vào, và là kết quả của sự thực hiện thuật toán.
1.2.3 Tính xác định
Ở mỗi bước, các thao tác phải rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn là trong cùng một điều kiện, hai bộ xử lí cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau.
1.2.4 Tính khả thi
Tất cả các phép toán có mặt trong thuật toán phải đủ đơn giản. Điều đó có nghĩa là, các phép toán có thể được thực hiện trực tiếp (bằng giấy và but).
1.2.5 Tính dừng
Với mọi bộ dữ liệu đầu vào(lấy từ các tập của dữ liệu vào), thuật toán phải dừng sau một số hữu hạn bước thực hiên.
1.2.6 Tính đơn trị (uniqueness)
Các giá trị trung gian của thuật toán trong từng bước và kết quả thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào và kết quả của các bước trước.
1.2.7 Tính tổng quát (generality)-Tính phổ dụng
Với mọi tập đầu vào thuộc dạng của bài toán thuật toán đều có thể giải được. Tức là thuật toán phải dùng để giải được một lớp các bài toán cùng loại.
Phân tích thuật toán và đánh giá thời gian thực hiện thuật toán
1.3.1 Phân tích thuật toán
Phân tích thuật toán là quá trình tìm ra những đánh giá về thời gian tính và dung lượng bộ nhớ cần thiết để thực hiện thuật toán
Hầu hết các bài toán đều có rất nhiều thuật toán khác nhau để giải quyết chúng và nhiệm vụ của chúng ta là phải tìm ra thuật toán tốt nhất để thực hiện bài toán đã đặt ra
Þ Muốn làm được điều đó thì ta cần tiến hành phân tích thuật toán rồi so sánh các thuật toán với nhau
1.3.2 Tại sao lại cần có thuật toán hiệu quả?
Kỹ thuật máy tính ngày càng tiến bộ rất nhanh, các máy tính lớn có thể đạt hàng trăm triệu phép toán mỗi giây. Tuy nhiên có những thuật toán mà độ phức tạp về thời gian là rất lớn mà các máy tính hiện đại nhất cũng tốn rất nhiều thời gian. Khi đó thì việc phân tích thuật toán để tìm ra những thuật toán hiệu quả là rất cần thiết.
Ví dụ bài toán tháp Hà Nội, nếu sử dụng giải thuật đệ quy để chuyển 64 đĩa thảo mãn yêu cầu bài toán thì cần khoảng 500 tỉ năm (giả sử mỗi lần chuyển 1 đĩa hết 1 giây
1.3.3 Phân tích hiệu quả thực hiện của thuật toán
Khi phân tích hiệu quả của thuật toán người ta quan tâm đến hai yếu tố:
- Độ phức tạp về thời gian: Là số bước tính toán hay số phép toán (phép toán sơ cấp) cần để thực hiện thuật toán
- Độ phức tạp không gian: Là yêu cầu về bộ nhớ lưu trữ cần có để thuật toán có thể thực hiện được. Yếu tố này chủ yếu phụ thuộc vào cấu trúc dữ liệu được sử dụng
Ngoài ra khi lựa chọn thuật toán người ta còn căn cứ vào tính đơn giản, dễ hiểu, dễ cài đặt của thuật toán.
1.3.4 Phân tích thời gian thực hiện thuật toán
Thời gian thực hiện một giải thuật (hay chương trình thể hiện giải thuật đó) phụ thuộc vào rất nhiều yếu tố:
- Kích thước của dữ liệu đưa vào
- Các kiểu lệnh và tốc độ xử lý của máy tính, ngôn ngữ viết chương trình và chương trình dịch ngôn ngữ ấy
Nhưng những yếu tố này không đồng đều với mọi loại máy trên đó cài đặt giải thuật, vì vậy không thể dựa vào chúng khi xác lập T(n).
1.3.4.1 Độ phức tạp về thời gian của giải thuật
Nếu thời gian thực hiện một giải thuật là T(n) = cn2 (với c là hằng số) thì ta nói: Độ phức tạp về thời gian của giải thuật này có cấp là n2 (hay cấp độ lớn của thời gian thực hiện giải thuật là n2) và ta ký hiệu
T(n) = O(n2) (ký hiệu chữ O lớn)
Một cách tổng quát có thể định nghĩa:
Một hàm f(n) được xác định là O(g(n))
f(n) = O(g(n)) và được gọi là cấp g(n) nếu tồn tại các hằng số c và n0 sao cho:
f(n) ≤ cg(n) khi n ³ n0
nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n), với mọi giá trị của n từ một điểm nào đó. Thông thường các hàm thể hiện độ phức tạp về thời gian của giải thuật có dạng: log2n, n, nlog2n, n2,n3, 2n, n!, nn
log2n
n
nlog2n
n2
n3
2n
0
1
0
1
1
2
1
2
2
4
8
4
2
4
8
16
64
16
3
8
24
64
512
256
4
16
64
256
4096
65536
5
32
160
1024
32768
2147483648
Các hàm như 2n, n!, nn được gọi là hàm loại mũ. Một giải thuật mà thời gian thực hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các hàm như log2n, n, nlog2n, n2,n3 được gọi là các hàm loại đa thức. Giải thuật với thời gian thực hiện có cấp hàm đa thức thì thường chấp nhận được.
1.3.4.2 Xác định độ phức tạp về thời gian
* Quy tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 kế tiếp nhau sẽ là:
T1(n) + T2(n) = O(max(f(n),g(n)))
Ví dụ: Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện từng bước lần lượt là O(n2), O(n3) và O(nlog2n) thì thời gian thực hiện 2 bước đầu là O(max(n2, n3)) = O(n3). Thời gian thực hiện chương trình sẽ là O(max(n3, nlog2n)) = O(n3).
Một ứng dụng khác của quy tắc này là nếu g(n) ≤ f(n) với mọi n ³ n0 thì O(f(n) + g(n)) cũng là O(f(n)). Chẳng hạn: O(n4 + n2) = O(n4) và O(n+log2n) = O(n).
* Quy tắc nhân: Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là:
T1(n)T2(n) = O(f(n)g(n))
Ví dụ: Câu lệnh gán: x:=x+1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1).
Câu lệnh for i:=1 to n do x:=x+1;
có thời gian thực hiện O(n.1) = O(n)
Câu lệnh: for i:=1 to n do
for j:=1 to n do x:=x+1;
có thời gian được đánh giá là O(n.n) = O(n2)
Cũng có thể thấy O(cf(n)) = O(f(n)). Ví dụ O(n2/2) = O(n2)
1.4 Các vấn đề liên quan đến thuật toán
1.4.1 Thiết kế thuật toán
Có một số kỹ thuật thiết kế thuật toán chung như:
- Chia để trị (divide and conque)
- Phương pháp tham lam (greedy method)
- Phương pháp quy hoạch động (dynamic programing)
Nắm được các kỹ thuật thiết kế thuật toán là rất quan trọng giúp tìm ra các thuật toán mới cho các bài toán mới.
1.4.2 Tính đúng đắn của thuật toán
Khi đưa ra một thuật toán ta phải chứng minh được thuật toán đó khi thực hiện sẽ cho kết quả đúng với mọi bộ dữ liệu vào hợp lệ.
1.4.3 Biểu diễn thuật toán
Có nhiều phương pháp biểu diễn thuật toán. Có thể biểu diễn thuật toán bằng cách liệt kê từng bước, bằng ngôn ngữ tự nhiên, bằng sơ đồ khối… Tuy nhiên để đảm bảo tính chính xác của thuật toán thì để biểu diễn thuật toán người ta thường dùng các cách sau: Liệt kê từng bước, dùng sơ đồ khối, dùng ngôn ngữ lập trình(thường là giả mã lệnh)
CHƯƠNG II
LÝ THUYẾT ĐỘ PHỨC TẠP
Máy tính Turing
Máy tính Turing là một máy tính toán trừu tượng, vừa có khả năng của máy tính thực sự, vừa cho phép định nghĩa về mặt toán học về những gì có thể tính toán được
2.1 Máy tính Turing tất định
2.1.1 Định nghĩa
Máy Turing tất định là một bộ M = (S, A , d1, d2, d3 , q0, , qr) trong đó
S: Là bảng chữ cái
A: Tập hữu hạn trạng thái bên trong
d1: Là hàm kí tự
d1: (S È {}) ´ A ® (S È {})
d2: Là hàm dịch chuyển
d2: (S È {}) ´ A ® {-1,0,1}
d2: Là hàm trạng thái
d3: (S È {}) ´ A ® A
q0: Trạng thái ban đầu (q0 Î A)
qr: Trạng thái kết thúc (qr Î A)
: Ký tự rỗng
2.1.2 Cấu tạo
Máy tính Turing tất định là một máy trừu tượng bao gồm:
- Một bảng chữ cái S
- Băng vô hạn có thể mở rộng về một phía hoặc cả hai phía. Trên băng được chia thành các ô chứa một kí hiệu lấy từ bảng chữ cái S
- Một tập trạng thái bên trong A
- Một đầu đọc ghi luôn đặt vào một ô trên băng và ta nói đầu đọc ghi đang nhìn ô đó. Đầu đọc ghi này có thể di chuyển mỗi lần một ô (về cả hai phía trên băng). Tại một ô có thể đọc hay ghi một kí tự vào ô đó
- Một bộ điều khiển có thể ở bất kì trạng thái nào trong một tập hữu hạn trạng thái, trong đó có một trạng thái ban đầu và một trạng thái kết thúc
0
1
0
1
1
0
Tập trạng thái bên trong
Máy Turing tất định
1.2.3 Hoạt động
- Đầu đọc ghi đọc kí tự trên ô của băng, phụ thuộc vào trạng thái bên trong mà đầu đọc viết một kí tự thuộc (S È ) lên ô
- Đầu đọc ghi dịch chuyển một ô sang phải, sang trái hoặc là đứng yên tại chỗ
- Trạng thái bên trong được được thay đổi tuỳ thuộc vào kí hiệu được đọc và trạng thái ban đầu
Điều đáng ngạc nhiên là máy Turing làm được tất cả những việc mà các máy tính khác làm được
Máy tính Turing có thể có nhiều băng nhưng nó không làm được gì nhiều hơn máy tính Turing một băng (tương đương với máy tính một băng)
2.2 Máy tính Turing không tất định
2.1.1 Định nghĩa
Máy Turing không tất định là một bộ M = (S, A , d1, d2, d3 , q0, , qr) trong đó
S: Là bảng chữ cái
A: Tập hữu hạn trạng thái bên trong
d1: Là hàm kí tự
d1: (S È {}) ´ A ® (S È {})
d2: Là hàm dịch chuyển
d2: (S È {}) ´ A ® {-1,0,1}
d2: Là hàm trạng thái
d3: (S È {}) ´ A ® A
q0: Trạng thái ban đầu (q0 Î A)
qr: Trạng thái kết thúc (qr Î A)
: Ký tự rỗng
2.1.2 Cấu tạo
Máy tính Turing tất định là một máy trừu tượng bao gồm:
- Một bảng chữ cái S
- Băng vô hạn có thể mở rộng về một phía hoặc cả hai phía. Trên băng được chia thành các ô chứa một kí hiệu lấy từ bảng chữ cái S
- Một tập trạng thái bên trong A
- Một đầu đọc ghi luôn đặt vào một ô trên băng và ta nói đầu đọc ghi đang nhìn ô đó. Đầu đọc ghi này có thể di chuyển mỗi lần một ô (về cả hai phía trên băng). Tại một ô có thể đọc hay ghi một kí tự vào ô đó
- Một bộ xử lý phỏng đoán song song
0
1
1
0
1
0
Tập trạng thái bên trong
1
Đầu đọc ghi
Bộ phận phỏng đoán
Máy tính Turing không tất định
2.1.3 Hoạt động
- Đầu đọc ghi đọc kí hiệu nhận được trên băng, viết kí tự mốc dịch chuyển, đổi trạng thái như máy Turing tất định
- Bộ phỏng đoán xử lý song song giúp máy xử lý dữ liệu một cách song song. Do đó máy Turing không tất định có thể xử lý đồng thời các phỏng đoán.
- Giả sử máy làm việc với một input x Î S được đặt vào các ô từ 1 đến çxçcủa băng. Giai đoạn phỏng đoán được thực hiện trên phần băng bên trái của dữ liệu vào trước khi quá trình tính toán bắt đầu và được thực hiện bởi cơ chế phỏng đoán và đầu phỏng đoán. Quá trình này cho phép viết lên các ô bên trái mỗi ô một kí hiệu nào đó cho đến khi dừng lại ta có một từ trên phía trái của phần băng chứa input (gọi là từ được dự đoán ), và giai đoạn phỏng đoán hoàn thành
Máy bắt đầu hoạt động như một máy tính Turing tất định thông thường. Yếu tố không tất định ở chỗ trong giai đoạn phỏng đoán việc biết kí tự vào các ô bên trái của dữ liệu vào là không xác định, tức là có thể viết theo nhiều khả năng khác nhau, xuất phát từ một dữ kiện ban đầu, máy tính Turing không tất định có nhiều quá trình tính toán có thể khác nhau do từ được dự đoán có nhiều khả năng khác nhau
Sự khác nhau của máy tính Turing tất định và máy tính Turing không tất định
2.3 Các bài toán quyết định
* Định nghĩa bài toán quyết định
Bài toán quyết định là bài toán mà câu trả lời của nó chỉ là “yes” hoặc “no” (tương ứng với true/1 hay false/0)
Về nguyên tắc mọi bài toán đều có thể biểu diễn lại dưới dạng bài toán quyết định tương ứng
*Ví dụ về bài toán quyết định
Ví dụ 1: Bài toán kiểm tra số nguyên tố
Instance: Cho một số nguyên tố n>2
Question: n có phải là số nguyên tố hay không?
Ví dụ 2: Bài toán HC (Hamilton cycle)
Instance: Cho đồ thị vô hướng G = (V,E)
Question: Hỏi đồ thị vô hướng G = (V,E) có chu trình Hamilton hay không?
2.4 Lớp P, NP và mối quan hệ giữa lớp P và lớp NP
2.4.1 Lớp P
* Định nghĩa:
Lớp P là lớp những bài toán giải quyết được bằng máy tính Turing tất định trong thời gian đa thức
* Ví dụ: Thuật toán Ơclide tìm UCLN của hai số là thuật toán giải được trong thời gian đa thức. Do đó bài toán tìm UCLN của hai số m và n thuộc lớp P
2.4.2 Lớp NP
* Định nghĩa:
Lớp NP là lớp các bài toán có thể giải được bằng máy Turing không tất định trong khoảng thời gian đa thức
* Ví dụ: Bài toán chu trình Hamilton
Instance: Cho đồ thị vô hướng G = (V,E)
Question: Hỏi đồ thị vô hướng G = (V,E) có chu trình Hamilton hay không?
2.4.3 Mối quan hệ giữa lớp P và lớp NP
NP
P
Mối quan hệ giữa lớp P và NP
2.5 Bài toán lớp NPC
2.5.1 Phép dẫn với thời gian đa thức
* Định nghĩa:
Cho n P1 và P2 là hai bài toán quyết định
Py là lớp các Instance ứng với YES
Py là lớp các Instance ứng với NO
Một cách biến đổi f biến mỗi Instance của P1 thành Instance của P2 được gọi là phép dẫn thời gian đa thức nếu nó thoả mãn:
- Phép dẫn f thực hiện được trong thời gian đa thức bởi máy tính Turing
- Mỗi dữ kiện thuộc P1(y) thành dữ kiện thuộc P2(y)
- Mỗi dữ kiện thuộc P1(n) thành dữ kiện thuộc P2(n)
f
f(x)
dữ kiện P2
thuật toán P2
thuật toán P1
Yes/NO
dữ kiện P1
Hình : Minh hoạ một phép dẫn bài toán P1 thành P2 trong thời gian đa thức
2.5.2 Bài toán lớp NPC
*Định nghĩa: Một bài toán thuộc lớp NP mà mọi bài toán thuộc lớp NP khác đều dẫn được về nó với thời gian đa thức được gọi là bài toán NPC
* Tính chất: Một bài toán P là NPC nếu nó thoả mãn:
1, P Î NP
2, Với " P’ Î NP thì P’ dẫn được về P với thời gian đa thức
Như vậy để chứng minh một bài toán là NPC ta cần chứng minh hai điều:
1, Bài toán đó phải thuộc lớp NP
2, Mọi bài toán thuộc lớp NP đều dẫn được về bài toán đó với thời gian đa thức
2.5.3 Mối quan hệ giữa các bài toán lớp P, NP và NPC
Mối quan hệ giữa P, NP và NPC được biểu diễn như hình sau:
NPC
P
NP
Mối quan hệ giữa lớp P, NP và NPC
2.5.4 Một số bài toán NPC
2.5.4.1 Bài toán SAT
Bài toán SAT được phát biểu dưới dạng quyết định như sau:
- Instance: Cho biểu thức Boolean f(x1,…,xn)
- Question: Cho biết f có thỏa được hay không?
Định lý Cook: Bài toán SAT là NPC
2.5.4.2 Bài toán 3-CNF-SAT
Bài toán 3-CNF-SAT được phát biểu dưới dạng bài toán quyết định như sau:
- Instance: C = {C1, C2,…,Cm} là các biểu thức logic độ dài 3
- Question: $ bảng chân lý để tất cả các Ci đều đúng
2.5.4.3 Bài toán Vertex-Cover
Instance: Cho đồ thị G =(V,E) và số kÎN* thoả mãn k £ çVç
Question: Tồn tại hay không một tập con V’ của V sao cho çV’ç<k và mỗi cạnh {u,e} Î E thì một trong 2 đỉnh u hoặc e (hoặc cả đỉnh u và e ) phải thuộc V’
2.5.4.4 Bài toán Clique
Instance: Cho đồ thị G = (V,E) và số kÎN* thoả mãn k £ çVç
Question: Tồn tại hay không một tập con V’ của V sao cho çV’ç³ k mà mọi cặp đỉnh trong V’ đều được nối bởi 1 cạnh trong E
2.5.4.5 Bài toán Subset-Sum
Bài toán tổng hợp con (Subset-Sum) cho một tập hữu hạn S Ì N và một đích t Î N. Hỏi có một tập con S’ Í S mà tổng các thành phần của nó có bằng giá trị t đã cho hay không? Chẳng hạn như S = {1,4,16,64,256,1040,1041,1093,1284,1334,1500} và t = 3754 thì tập con S’ = {1,16,64,256,1040,1093,1284} là một nghiệm
Bài toán Subset-Sub được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho tập hợp S = {s1,s2,…,sn} trong đó Si Î N, N là một số nguyên dương; t là một số nguyên
Question: Tồn tại hay không một tập con của S mà tổng các phần tử của nó bằng t
2.5.4.6 Bài toán Knapsack
Cho S là một tập gồm n đối tượng phân biệt, mỗi đối tượng i có kích thước là một số nguyên si và giá trị tương ứng là wi. Với 2 số nguyên là s và w cho trước, câu hỏi đặt ra là có tồn tại tập hợp T Í S sao cho si £ s và wi ³ w
Bài toán Knapsack được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho tập S = {(si,wi),…,(sn,wn)} với si Î Z, wi Î R+
Question: Có tồn tại T Í S sao cho si £ s và wi ³ w
2.5.4.7 Bài toán Hamilton Cycle
Bài toán chu trình Hamilton là bài toán đi xác định xem với một đồ thị G = (V,E) cho trước có chứa một chu trình Hamilton(chu trình đơn chứa mọi đỉnh của G). Bài toán được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho đồ thị G = (V,E)
Question: G có chứa một chu trình đơn đi quan mọi đỉnh hay không?
2.8.4.8 Bài toán Traveling Salesman
Bài toán Traveling Salesman được phát biểu dưới dạng bài toán đồ thị là: Cho đồ thị G cùng tham số k nguyên, mỗi cạnh e của G có một trọng số nguyên c(e). Câu hỏi đặt ra là có tồn tại một chu trình thăm tất cả các đỉnh của G (mỗi đỉnh đúng một lần) mà tổng trọng số các cạnh đã đi qua không vượt quá k không? Bài toán được phát biểu dưới dạng bài toán quyết định như sau:
Instance: Cho tập n thành phố C = {C1,…,Cn} với khoảng cách
d(Ci,Cj) Î Z+ và một số nguyên dương B
Question: Có tồn tại một hoán vị p trên {1,2,…,n} sao cho:
d(Cp(i),Cp(i+1)) + d(Cp(m),Cp(1)) £ B hay không?
Ta có sơ đồ tổng quát để chứng minh một bài toán là NPC như sau
Bài toán LÎLP
LP
SAT
3-CNF-SAT
Vertex-Cover
Subset-Sum
Knapsack
Clique
Hamilton
Traveling salesman
Hình Sơ đồ chứng minh một số bài toán NPC
CHƯƠNG III. MẬT MÃ VÀ MẬT MÃ KHOÁ CÔNG KHAI RSA
I. Mật mã
1. Định nghĩa về mật mã và hệ mật mã
1.1 Một số khái niệm trong mật mã
Bản rõ: Là thông điệp gốc chứa thông tin cần mã hoá
Bản mã: Là thông điệp chứa các kí tự sau khi đã được mã hoá
Mã hoá: Là quá trình che dấu thông tin bằng phương pháp nào đó để làm ẩn nội dung bên trong
Giải mã: Là quá trình biến đổi lại bản mã thành bản rõ
Khoá (Key): Là một giá trị dùng để thực hiện một thuật toán mã hoá. Khoá có thể là một số, một xâu kí tự …Khoá này có thể nhận một hay nhiều giá trị
Quá trình mã hoá và giải mã được thực hiện như trong sơ đồ sau:
Bản rõ
Bản mã
Bản rõ gốc
Mã hóa
Giải mã
Sơ đồ quá trình mã hoá và giải mã
1.2 Định nghĩa về hệ mật mã
* Đinh nghĩa hệ mật mã
Một hệ mật mã bao gồm 5 thành phần (P,C,K,E,D), trong đó:
P: Tập hợp hữu hạn các bản rõ có thể
C: Tập hợp hữu hạn các bản mã có thể
K: Tập hợp các bản khoá có thể
E: Tập hợp các quy tắc mã hoá có thể
D: Tập hợp các quy tắc giải mã có thể
Các thành phần trên phải thoả mãn tính chất sau: Với mỗi k Î K thì tồn tại duy nhất hàm ek Î E và dk Î D sao cho thoả mãn đồng thời 2 tính chất sau:
ek : P ® C và dk: C ® P
dk(ek(x)) = x và e(d(x)) = x với " x Î P
Hàm ek được gọi là hàm lập mã (khoá lập mã)
Hàm dk được gọi là hàm giải mã (khoá giải mã)
Cặp (ek,dk) được gọi là một khóa của hệ mật mã
2. Một số yêu cầu đối với hệ mật mã
Một hệ mật mã phải đảm bảo các yêu cầu sau:
Bí mật: Thông tin chỉ được tiết lộ cho người được phép
Toàn vẹn: Thông tin không thể bị thay đổi mà không bị phát hiện
Xác thực: Người gửi (hay người nhận) có thể chứng minh đúng là họ đã gửi (hay nhận) thông tin
Không thể chối bỏ: Người gửi (hay người nhận) có thể chối bỏ việc họ đã gửi (hay nhận) thông tin
II. Mật mã khoá công khai RSA
1. Đặt vấn đề
Hệ mật mã khoá công khai này do ba nhà khoa học Rivest- Shamir-Adleman đề ra trước tiên và thường được gọi vắn tắt là RSA. Hệ mã RSA dựa trên bài toán phân tích số nguyên n thành tích các thừa số nguyên tố, gần như không thể tìm lại được hai số nguyên tố lớn p và q từ tích của chúng là n = p*q. Mặt khác, lại có thể sinh ra rất nhanh số nguyên tố ngẫu nhiên lớn
Việc mã hoá công khai dựa vào số n trong khi đó việc giải mã lại đòi hỏi phải biết được p và q
2. Giải thuật RSA
2.1 Chọn khoá
Hệ RSA bao gồm một cặp khoá (N,e) và (N,d). Để tìm các giá trị d,e và n tiến hành như sau:
Bước1: Chọn p và q là hai số nguyên tố ngẫu nhiên lớn (trong ứng dụng thực tế p và q lên đến khoảng vài trăm chữ số), p và q được giữ bí mật.
Bước 2: Đặt N=p*q và j(N) = (p-1)(q-1)
N càng lớn thì việc phân tích ra thừa số nguyên tố càng phức tạp
Bước 3: Chọn e (e > 1(j(N))) nguyên tố cùng nhau với j(N) và một số d thoả mãn hệ thức: ed º 1 mod
Vì e và j(N) nguyên tố cùng nhau nên hệ thức trên có nghiệm
Một cách dễ dàng để đảm bảo e là nguyên tố cùng nhau với j(N) là là chọn e là số nguyên tố lớn hơn p-1 hoặc q-1 thoả mãn UCLN(e,j(N)) = 1
Cặp số nguyên (N,e) lập thành một mã khoá công khai
Cặp số nguyên (N,d) lập thành một mã khoá bí mật
N: Modul từ tích pq
e: Số mũ mã hoá công khai
d: Số mũ mã hoá bí mật
2.2 Mã hoá
* Phương pháp tiến hành:
Để mã hoá văn bản rõ P theo phương pháp RSA, trước tiên ta hiển thị bản rõ như một từ trên bộ chữ cái {0,1,…,9}. Từ này đươc chia thành các khối với kích thước thích hợp p1, p2,…,pk (với k là số nguyên). Các khối này được mã hoá riêng rẽ bằng cách dùng cặp (N,e). Bản rõ P được mã hoá bằng cách nâng từng khối lên luỹ thừa e theo modul N
Bản rõ P= p1, p2,…,pk
Bản mã C = c1, c2,…,ck
Tức là Ci = Pie mod N
Một kích thước thích hợp của các khối là số nguyên j duy nhất thoả mãn bất đẳng thức: 10j-1 0)
* Thuật toán mã hoá RSA (mã hoá bản rõ P dùng khoá công khai (N,e)):
Bước 1: Thêm vào P một số kí tự ngẫu nhiên nào đó nếu cần thiết để chiều dài của P là bội số của độ dài khối
Bước 2: Tính số khối:
NumberOfBlock = Length(P)/BlockLength
Bước 3: Khởi tạo j = 1
For i = 1 to NumberOfBlock do
Lấy ra kí tự con pi từ P gồm BlockLength kí tự bắt đầu từ vị trí j
Chuyển pi sang dạng số ci
Tính ci = cie mod N
Tăng j thêm BlockLength
2.3 Giải mã
Việc giải mã với RSA bằng cách nâng mỗi khối ci lên luỹ thừa d theo modul N để phục hồi bản rõ
Pi = Cid mod N = (Pie)d mod N đối với mỗi khối ci
e, d phải được chọn sao cho Ped mod N = W
* Thuật toán giải mã RSA
Giải mã dùng khoá bí mật d
Khởi tạo P = xâu rỗng
For i = 1 to NumberOfBlock do
Tính ci = cid mod N
Chuyển ci sang xâu kí tự pi
P = P + pi
Return P
Chọn p và q
Tính N = p*q
Tính j(n)
Chọn e
Tính d để: edº1(mod j(n))
C = Pe (mod N)
P = C d (mod N)
e
d
Sơ đồ quá trình thực hiện giải thuật RSA
2.4 Ví dụ minh hoạ
B1: Chọn p = 47, q = 59 là hai số nguyên tố
B2: Ta có: p*q=47*59 = 2773
(p-1)(q-1) = 46*58 = 2668
Þ N = 2773 và mod j(N) = 2668
B3: Xác định e và d, chọn e = p + 1, tăng e cho đến khi UCLN (e,j(N) ) = 1 và ta tính được d = 1089
e*d mod j(N) = 49 * 1089 mod 2668 = 53361 mod 2668 = 1
Như vậy, xác định xong cặp khoá (N,e), (N,d)
Các kí tự trong bản rõ được chuyển số bằng cách dùng bảng mã sau:
A
B
C
D
E
F
G
H
I
J
K
L
M
00
01
02
03
04
05
06
07
08
09
10
11
12
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
Trong trường hợp quan tâm đến kí tự dấu cách thì coi kí tự này có mã 00, A có mã 01,…, Z có mã 26
Cho bản rõ P = “VIDUMINHHOA”
Chia P thành các khối gồm 2 kí tự, thêm vào P kí tự X để độ dài của no là bội của số khối Þ P = “VIDUMINHHOAX”
Vì mỗi kí tự tương ứng có mã số là hai chữ số nên các khối của bản rõ dưới dạng sẽ gồm bốn chữ số, tức là 103 < N < 104
W1 w2 w3 w4 w5 w6
Bản rõ: VI DU MI NH HO AX
Dạng số: 2108 0320 1208 1307 0714 0023
c1 c2 c3 c4 c5 c6
Mỗi khối trong các khối trên sau đó được nâng lên luỹ thừa 17 theo modul 2773
Bản mã có dạng 083207281251138609170746
3. Ðộ an toàn của hệ RSA
Tính bảo mật của RSA chủ yếu dựa vào việc giữ bí mật khóa giải mã hay giữ bí mật các thừa số p,q của N. Một vài phương thức tấn công điển hình của kẻ địch:
Trường hợp1: Kẻ địch biết được mođun N, khóa công khai e và bản tin mã hóa C, khi đó kẻ địch sẽ tìm ra bản tin gốc kẻ địch thường tấn công vào hệ thống mật mã bằng phương thức sau đây: Trước tiên dựa vào phân tích thừa số mođun N. Tiếp theo sau chúng sẽ tìm cách tính toán ra hai số nguyên tố p và q, và có khả năng thành công khi đó sẽ tính được f(N) = (p-1)(q-1) và khóa bí mật d. Ta thấy N cần phải là tích của hai số nguyên tố, vì nếu N là tích của hai số nguyên tố thì thuật toán phân tích thừa số đơn giản cần tối đa N1/2 bước, bởi vì có một số nguyên tố nhỏ hơn N1/2. Mặt khác, nếu N là tích của n số nguyên tố, thì thuật toán phân tích thừa số đơn giản cần tối đa N1/n bước.
Trường hợp2: Chúng ta xét trường hợp khi kẻ địch nào đó biết được mođun N và f(N), khi đó kẻ địch sẽ tìm ra bản tin gốc (Plaintext) bằng cách sau:
Biết f(N) thì có thể tính p,q theo hệ phương trình:
p´q = N, (p-1)(q-1) = f(N)
do đó p và q là nghiệm của phương trình bậc hai:
x2 - (n - f(N) +1) + n = 0
Ví dụ: n=84773093, và biết f(N) = 84754668. Giải phương trình bậc hai tương ứng ta sẽ được hai nghiệm p=9539 và q=8887.
Ðộ an toàn của thuật toán RSA dựa trên cơ sở những khó khăn của việc xác định các thừa số nguyên tố của một số lớn. Bảng dưới đây cho biết các thời gian dự đoán, giả sử rằng mỗi phép toán thực hiện trong một micro giây.
Số các chữ số trong
số được phân tích
Thời gian phân tích
50
4 giờ
75
104 giờ
100
74 năm
200
4.000.000 năm
300
5´1015 năm
500
4´1025 năm
4. Ứng dụng của hệ mật mã RSA
Hệ mã hóa RSA được ứng dụng rộng rãi chủ yếu cho Web và các chương trình email. Ngày nay, RSA còn được sử dụng rộng rãi trong các công nghệ bảo mật, sử dụng cho thương mại điện tử
5. Chữ ký điện tử
5.1 Giới thiệu về chữ ký điện tử và vấn đề xác nhận
Chữ ký điện tử là một phương pháp ký một thông điệp được lưu trữ ở dạng thư tín điện tử. Hiểu theo nghĩa thông thường một thông điệp được ký có thể được truyền trên mạng máy tính. Khi truyền tin trên mạng, các văn bản được truyền đi dưới dạng số hoá. Vấn đề đặt ra là người gửi có nhận trách nhiệm về văn bản gửi đi đó không? Việc xác nhận trách nhiệm của người gửi đối với văn bản đó cũng là thể hiện trong thủ tục truyền tin nhưng rõ ràng nảy sinh ra nhiều vấn đề mà cách xác nhận trong việc chuyển văn bản kiểu truyền thống chưa gặp phải.
Vấn đề thứ nhất: Trong cách truyền thống chữ kí của người gửi dưới dạng một văn bản viết tay là bằng chứng xác nhận trách nhiệm của người gửi đối với văn bản đó. Với văn bản điện tử, người ta có thể cắt dán và lắp ghép các dãy bit một cách dễ dàng. Giả sử người đó có một chữ kí dưới dạng một văn bản thì ai dám đảm bảo là chữ ký đó chịu trách nhiệm đối với toàn văn bản. Như vậy một chữ ký điện tử nếu có phải được ký cho từng bit của văn bản, chứ không phải là một chữ ký rời ở cuối văn bản
Vấn đề thứ hai là xác nhận chữ ký: Chữ ký tay được xác nhận bằng cách so với nguyên mẫu. Chữ ký điện tử là một dãy các bit không thể thử bằng cách so sánh vật lý với một mẫu cho sẵn mà phải xác nhận bằng thuật toán dựa vào mối quan hệ toán học nào đó
Vấn đề thứ ba là việc sao chép một dạng văn bản cùng chữ ký: Nếu là chữ ký viết tay thì dễ phân biệt bản gốc với bản sao do đó không dùng lại được văn bản có chữ ký thật. Văn bản điện tử cùng chữ ký thì có thể nhân bản tuỳ ý không ai phân biệt được bản gốc hay bản sao, cho nên nguy cơ dùng lại là có thật. Phải tránh nguy cơ đó chẳng hạn bằng cách dán nhãn thời gian cho văn bản được ký
Ðịnh nghĩa sơ đồ chữ ký: Một sơ đồ chữ ký số là bộ 5 (P,A, K,S,V) thoả mãn các điều kiện dưới đây:
P là tập hữu hạn các bức điện (thông điệp) có thể.
A là tập hữu hạn các chữ ký có thể.
K không gian khoá là tập hữu hạn các khoá có thể, mỗi k Î K gồm hai thành phần, k = (K’,K’’) trong đó
+ K’ là khoá bí mật dùng để ký
+ K’’ là khoá công khai dùng để xác nhận chữ ký
Với mỗi k Î K tồn tại một thuật toán ký sigk S và là một thuật toán xác minh verk V. Mỗi sigk : PA và verk: P×a {true,false} là những hàm sao cho mỗi thông điệp xP và mối chữ ký ya thoả mãn phương trình dưới đây.
True nếu y=sig(x)
False nếu y≠sig(x)
verk =
Với mỗi k thuộc K hàm sigk và verk là các hàm có thời gian đa thức. verk sẽ là hàm công khai, sigk là bí mật. Không thể dể dàng tính toán để giả mạo chữ ký của B trên thông điệp x. Nghĩa là x cho trước, chỉ có B mới có thể tính được y để verk = True. Một sơ đồ chữ ký không thể an toàn vô điều kiện vì C có thể kiểm tra tất cả các chữ số y có thể có trên thông điệp x nhờ dùng thuật toán verk công khai cho đến khi anh ta tìm thấy một chữ ký đúng. Vì thế, nếu có đủ thời gian, C luôn luôn có thể giả mạo chữ ký của B. Như vậy, giống như trường hợp hệ thống mã khoá công khai, mục đích của chúng ta là tìm các sơ đồ chữ ký số an toàn về mặt tính toán.
5.2 Sơ đồ chữ ký RSA
Sơ đồ chữ ký RSA được phát minh bởi 3 nhà nghiên cứu Rivest, Shamir và Adleman, đây là sơ đồ có ứng dụng thực tế rộng rãi nhất dựa trên công nghệ sử dụng khóa chung. Các phương pháp tấn công RSA đầu tiên (multicative property) và các vấn đề khác liên quan tới chữ ký RSA được đưa ra bởi Ðavia và Jonge và Chaum. Sau đây là sơ đồ chữ ký RSA.
a. Thuật toán sinh khoá :
Một thực thể A tạo một khoá công khai RSA và khoá riêng tương ứng theo phương thức sau:
Sinh ra hai số nguyên tố lớn ngẫu nhiên p và q cùng kých thước bit
Tính n = pq và f = (p - 1)(q - 1 )
Chọn một số tự nhiên ngẫu nhiên a thoả mãn điều kiện sau: 1< a < f và USCLN(a, f) = 1 hay a Z*p .
Sử dụng giải thuật mở rộng Euclide để tính toán số tự nhiên duy nhất b sao cho 1< b <f và ab º 1 (mod f)
Khoá công khai của A là K’ = (n,a) khoá riêng của A là K” = b
b. Thuật toán sinh và xác định chữ ký :
Mỗi phần tử A ký một thông điệp m M. Mỗi thực thể B có thể xác định được chữ ký của A và khôi phục lại thông điệp từ chữ ký
* Sinh chữ ký: thực thể A làm theo các bước sau:
Tính m' = H(m), là một số nguyên trong khoảng [0, n-1]
Tính s = m'd mod n
Chữ ký của A cho m là s
*Xác nhận chữ ký : Thực thể B làm theo các bước sau:
Nhận khoá công khai của A là (n, b)
Tính m' = sb mod n
Kiểm tra m' MR nếu không sẽ không chấp nhận chữ ký
Lấy lại thông điệp m từ m = H-1(m')
c. Tóm tắt lược đồ ký theo RSA :
Cho n = pq với p và q là các số nguyên tố.Cho p = a = Zn
Định nghĩa: p = {(n, p, q, a, b) || n=pq, p và q là nguyên tố, ab 1 mod f(n)}. Các giá trị n, b là công khai. Ta định nghĩa
Sigk(x) = xa mod n và
Verk(x,y) = true x yb (mod n) với x, y Zn
Nếu độ dài thông điệp x lớn, ta sử dụng hàm băm như trên
Ví dụ : ví dụ sau đây sử dụng sơ đồ ký RSA, với thông điệp lớn
* Sinh khoá:
Thực thể A chọn số nguyên tố p = 7927 và q = 6997 và tính n = pq = 5546521 và f = 7926x6996 = 55450296. A chọn a = 5 và giải ab = 5b º1 (mod 55450296) được b = 44360237. Khoá công khai của A là (n = 55465219, a = 5) và khoá riêng của A là b = 44360237
* Sinh chữ ký::
Ðể ký một thông điệp m = 31229978, A tính m'1 = H(m) = 31229978 và tính toán chữ ký s = m1'b mod n = 312299784430237 mod 55465219 = 30729435
* Xác nhận chữ ký:
B tính m'2 = sa mod n = 307294355 mod 55465219 = 31229978. Cuối cùng B chấp nhận chữ ký vì m’2 = m’1
5.3 Tấn công chữ ký điện tử
Khi nói đến chữ ký điện tử, chúng ta luôn mục tiêu an toàn lên hàng đầu. Một chữ ký điện tử chỉ thực sự được áp dụng trong thực tế nêu như nó được chứng minh là không thể giả mạo. Mục tiêu lớn nhất của kẻ tấn công các sơ đồ chữ ký chính là giả mạo chữ ký; điều này có nghĩa là kẻ tấn công sẽ sinh ra được chữ ký của người ký lên thông điệp mà chữ ký này sẽ được chấp nhận bởi người xác nhận. Trong thực tế các hành vi tấn công chữ ký điện tử hết sức đa dạng, để dễ dàng phân tích một sơ đồ chữ ký là an toàn hay không người ta tiến hành kiểm nghiệm độ an toàn của chữ ký trước các sự tấn công sau:
Total break: Một kẻ giả mạo không những tính được thông tin về khoá riêng (private key) mà còn có thể sử dụng một thuật toán sinh chữ ký tương ứng tạo ra được chữ ký cho thông điệp.
Selective forgert: Kẻ tấn công có khả năng tạo ra được một tập hợp các chữ ký cho một lớp các thông điệp nhất định, các thông điệp này được ký mà không cần phải có khoá mật của người ký.
Existential forgery: Kẻ tấn công có khả năng giả mạo chữ ký cho một thông điệp, kẻ tấn công không thể hoặc có rất ít khả năng kiểm soát thông điệp được giả mạo này.
Ngoài ra, hầu hết các chữ ký điện tử đều dựa vào cơ chế mã hoá khoá công khai, các chữ ký điện tử dựa trên cơ chế này có thể bị tấn công theo các phương thức sau:
Key-only attacks: Kẻ tấn công chỉ biết khóa chung của người ký.
Message attacks: ở đây kẻ tấn công có khả năng kiểm tra các chữ ký khác nhau có phù hợp với một thông điệp có trước hay không. Ðây là kiểu tấn công rất thông dụng trong thực tế nó thường được chia làm 3 lớp:
Known-message attack: Kẻ tấn công có chữ ký cho một lớp các thông điệp.
Chosen-message attack: Kẻ tấn công dành được các chữ ký đúng cho một danh sách các thông điệp trước khi tiến hành hoạt động phá huỷ chữ ký, cách tấn công này là non-adaptive (không mang tính phù hợp) bởi vì thông điệp được chọn trước khi bất kỳ một chữ ký nào được gửi đi.
Adaptive-chosen message attack: Kẻ tấn công được phép sử dụng người ký như là một bên đáng tin cậy, kẻ tấn công có thể yêu cầu chữ ký cho các thông điệp mà các thông điệp này phụ thuộc vào khoá công khai của người ký, như vậy kẻ tấn công có thể yêu cầu chữ ký của các thông điệp phụ thuộc vào chữ ký và thông điệp dành được trước đây và qua đó tính toán được chữ ký.
CHƯƠNG IV. DEMO VỚI RSA
KẾT LUẬN:
Hiện nay nói chung mật mã và mật mã khoá công khai RSA đã trở thành một phần không thể thiếu của rất nhiều lĩnh vực trong cuộc sống. Nó giữ gìn tính riêng tư cho những thông tin nhạy cảm, quan trọng hay cung cấp các dịch vụ đảm bảo an toàn dữ liệu trong các dao dịch, kết nối điện tử. Có được thành công đó bên cạnh sự phát triển của kỹ thuật phần cứng và cơ sở hạ tầng, không thể không nói đến vai trò của khoa học máy tính mà trong đó lý thuyết độ phức tạp là một lĩnh vực hết sức quan trọng. Các kết quả nghiên cứu giúp chúng ta có cái nhìn thống nhất đối với những vấn đề phức tạp, từ đó có thể xem xét giải quyết vấn đề một cách hợp lý tuỳ theo hoàn cảnh cụ thể.
Nội báo cáo đã nghiên cứu những vấn đề cơ bản của lý thuyết độ phức tạp và ứng dụng của nó trong mật mã khoá công khai RSA. Qua đó làm rõ tầm quan trọng và ý nghĩa của việc nghiên cứu lý thuyết độ phức tạp trong thực tiễn. Tuy nhiên do thời gian có hạn nên báo cáo không đi sâu chi tiết vào mọi vấn đề và chắc chắn không tránh khỏi những thiếu sót, khiếm khuyết. Kính mong thầy cô và bạn bè góp ý và giúp đỡ,
TÀI LIỆU THAM KHẢO
A. TÀI LIỆU
1. Đoàn Tiến Vinh – Lý thuyết độ phức tạp và bảo mật thông tin (luận văn cao học) - Đại học sư phạm Hà Nội- 2006
2. Nguyễn Thị Như – Lý thuyết độ phức và ứng dụng (luận văn tốt nghiệp 2007)
3. Hà Huy Khoái- Nhập môn số học thuật toán (NXB Khoa học)
4. Đỗ Xuân Lôi- Cấu trúc dữ liệu và giải thuật
5. Vũ Đình Hoà, Đỗ Trung Kiên- Thuật toán và độ phức rạp thuật toán
B. INTERNET
1. http:// www.rsa.com
2. RSA Securityn Inc-
Các file đính kèm theo tài liệu này:
- Báo cáo nghiên cứu khoa học-đề tài Lý thuyết độ phức tạp và ứng dụng (Chuyên ngành - Khoa học máy tính).doc