Bài giảng An toàn và bảo mật hệ thống thông tin - Chương 7: bài toán n thành viên và bảo mật CSDL
Bài giảng An toàn và bảo mật hệ thống thông tin - Chương 1: Tổng quan về bảo mật hệ thống thông tin
82 0 0
Häc viÖn c«ng nghÖ bu chÝnh viÔn th«ng GIÁO TRÌNH PT IT C¥ së mËt m· häc Chủ biên: GS.TS Nguyễn Bình Cộng tác viên: TS. Ngô Đức Thiện Khoa KTĐT1 - Học viện CNBCVT Hà Nội - 2013 MỤC LỤC LỜI NÓI ĐẦU.............................................................................................................. i MỤC LỤC .................................................................................................................. iii CHƯƠNG 1. NHẬP MÔN MẬT MÃ HỌC .............................................................. 1 1.1. SƠ ĐỒ KHỐI ĐƠN GIẢN CỦA MỘT HỆ THỐNG THÔNG TIN SỐ .............. 1 1.2. SƠ LƯỢC VỀ MẬT MÃ HỌC .......................................................................... 2 1.3. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP ................................................................. 3 1.3.1. Khái niệm về thuật toán ............................................................................... 3 1.3.2. Độ phức tạp của thuật toán .......................................................................... 4 1.4. LÝ THUYẾT THÔNG TIN TRONG CÁC HỆ MẬT......................................... 7 1.4.1. Độ mật hoàn thiện. ...................................................................................... 7 1.4.2. Entropy ..................................................................................................... 13 IT BÀI TẬP CHƯƠNG 1. ........................................................................................... 22 CHƯƠNG 2. MẬT MÃ KHÓA BÍ MẬT ................................................................. 24 2.1. SƠ ĐỒ KHỐI MỘT HỆ TRUYỀN TIN MẬT.................................................. 24 2.2. MẬT MÃ THAY THẾ ..................................................................................... 25 PT 2.2.1. Mật mã dịch vòng [MDV] ......................................................................... 25 2.2.2. Mã thay thế [MTT] .................................................................................... 26 2.2.3. Mật mã Vigenère ....................................................................................... 26 2.3. MẬT MÃ HOÁN VỊ [MHV] ........................................................................... 31 2.4. MẬT MÃ HILL ............................................................................................... 32 2.5. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN XYCLIC CỦA VÀNH ĐA THỨC ............................................................................................................. 36 2.5.1. Nhóm nhân của vành ................................................................................. 36 2.5.2. Các phần tử cấp n và các nhóm nhân xyclic cấp n ...................................... 37 2.5.3. Hệ mật xây dựng trên các cấp số nhân xyclic ............................................. 38 2.6. CÁC HỆ MẬT MÃ TÍCH ................................................................................ 44 2.7. CÁC HỆ MÃ DÒNG ....................................................................................... 46 2.7.1. Sơ đồ chức năng của hệ mật mã dòng ........................................................ 46 2.7.2. Tạo dãy giả ngẫu nhiên [M-dãy] ................................................................ 48 2.8. CHUẨN MÃ DỮ LIỆU .................................................................................. 53 2.8.1. Mở đầu ...................................................................................................... 53 iii Ch¬ng 1: NhËp m«n mËt m· häc CHƯƠNG 1. NHẬP MÔN MẬT MÃ HỌC 1.1. SƠ ĐỒ KHỐI ĐƠN GIẢN CỦA MỘT HỆ THỐNG THÔNG TIN SỐ Đầu vào rõ Biến đổi A/D [Tương tự - số] Bản rõ Mã nguồn Bản mã Mã bảo mật Mã kênh Nguồn tin tương tự Từ mã được truyền IT Kênh truyền [Tạp âm, đa đường, giao thoa, nhiễu, nghe trộm] Đầu ra số Biến đổi D/A [Số - tương tự] Giải mã nguồn PT Nhận tin Bản rõ Bản mã Giải mã bảo mật Từ mã nhận được Giải mã kênh Hình 1.1. Sơ đồ hệ thống thông tin số Trường hợp nguồn tin đầu vào là nguồn tin số thì không cần bộ biến đổi A/D ở đầu vào và bộ biến đổi D/A ở đầu ra Trong hệ thống này khối mã bảo mật có chức năng bảo vệ cho thông tin không bị khai thác bất hợp pháp, chống lại các tấn công sau: - Thám mã thụ động: bao gồm các hoạt động: + Thu chặn. + Dò tìm. + So sánh tương quan. + Suy diễn. - Thám mã tích cực: bao gồm các hoạt động: + Giả mạo. + Ngụy trang. + Sử dụng lại. + Sửa đổi. 1 Ch¬ng 1: NhËp m«n mËt m· häc 1.2. SƠ LƯỢC VỀ MẬT MÃ HỌC Khoa học về mật mã [cryptology] bao gồm: - Mật mã học [cryptography]. - Phân tích mật mã [cryptanalysis]. Mật mã học là khoa học nghiên cứu cách ghi bí mật thông tin nhằm biến bản tin rõ thành các bản mã. Phân tích mã là khoa học nghiên cứu cách phá các hệ mật nhằm phục hồi bản rõ ban đầu từ bản mã. Việc tìm hiểu các thông tin về khóa và các phương pháp biến đổi thông tin cũng là một nhiệm vụ quan trọng của phân tích mật mã. Có ba phương pháp tấn công cơ bản của thám mã: Tìm khóa vét cạn. Phân tích thống kê. Phân tích toán học. IT Việc tấn công của thám mã có thể được thực hiện với các giả định: Tấn công chỉ với bản mã. Tấn công với bản rõ đã biết. Tấn công với các bản rõ được chọn. Tấn công với các bản mã được chọn. PT Chú ý: Một hệ mật có thể bị phá chỉ với bản mã thường là hệ mật có độ an toàn thấp. Một hệ mật là an toàn với kiểu tấn công có các bản rõ được chọn thường là một hệ mật có độ an toàn cao. Có 4 loại hệ mật mã sau: Hệ mật mã dòng. Hệ mật mã khối đối xứng. Hệ mật mã có hồi tiếp mật mã. Hệ mật mã khóa công khai [Bất đối xứng]. Ta sẽ nghiên cứu các loại hệ mật trên ở các chương sau. Khi xây dựng một hệ mật người ta thường xem xét tới các tiêu chuẩn sau: Độ mật cần thiết. Kích thước không gian khóa. Tính đơn giản và tốc dộ mã hóa và giải mã. Tính lan truyền sai. Tính mở rộng bản tin. 2 Ch¬ng 1: NhËp m«n mËt m· häc 1.3. THUẬT TOÁN VÀ ĐỘ PHỨC TẠP 1.3.1. Khái niệm về thuật toán 1.3.1.1. Định nghĩa thuật toán Có thể định nghĩa thuật toán theo nhiều cách khác nhau. Ở đây ta không có ý định trình bày chặt chẽ về thuật toán mà sẽ hiểu khái niệm thuật toán theo một cách thông thường nhất. Định nghĩa 1.1: Thuật toán là một quy tắc để với những dữ liệu ban đầu đã cho, tìm được lời giải của bài toán được xét sau một khoảng thời gian hữu hạn. Để minh họa cách ghi một thuật toán cũng như tìm hiểu các yêu cầu đề ra cho thuật toán, ta xét trên các ví dụ cụ thể sau đây: Cho n số X 1 , X 2 ,..., X n ta cần tìm m và j sao cho: m X j max X k IT 1k n Và j là lớn nhất có thể. Điều đó có nghĩa là cần tìm cực đại của các số đã cho và chỉ số lớn nhất trong các số cực đại. Với mục tiêu tìm số cực đại với chỉ số lớn nhất, ta xuất phát từ giá trị X [n ] . Bước thứ nhất, vì mới chỉ có một số ta có thể tạm thời xem m X [n ] và j n . Tiếp theo ta so sánh PT X [n ] với X [n 1] . Nếu X [n ] không nhỏ hơn X [n 1] thì ta giữ nguyên, trong trường hợp ngược lại, X [n 1] chính là số cực đại trong hai số đã xét và ta phải thay đổi m và j . Đặt m X [n 1] , j 1,..., n 1 . Với cách làm như trên, ở mỗi bước ta luôn nhận được số cực đại trong số những số đã xét. Bước tiếp theo là so sánh nó với những số đứng trước hoặc kết thúc thuật toán trong trường hợp không còn số nào đứng trước nó. 1.3.1.2. Thuật toán tìm cực đại M1: [Bước xuất phát] đặt j n , k n 1, m X [n ] M2: [Đã kiểm tra xong?]. Nếu k 0 , thuật toán kết thúc. M3: [So sánh]. Nếu X [k ] m , chuyển sang M5 M4: [Thay đổi m ]. Đặt j k , m X [k ] [Tạm thời m đang là cực đại]. M5: [Giảm k ]. Đặt k k 1 quay về M2. Dấu " " dùng để chỉ một phép toán quan trọng là phép thay chỗ [replacement]. Trên đây ta ghi thuật toán bằng ngôn ngữ thông thường. Trong trường hợp thuật toán được viết bằng ngôn ngữ của máy tính, ta có một chương trình. 3 Ch¬ng 1: NhËp m«n mËt m· häc Trong thuật toán có những số liệu ban đầu được cho trước khi thuật toán bắt đầu làm việc được gọi là các đầu vào [input]. Trong thuật toán trên đầu vào là các số X [1], X [2],..., X [n ] . Một thuật toán có thể có một hoặc nhiều đầu ra [output]. Trong thuật toán trên các đầu ra là m và j . Có thể thấy rằng thuật toán vừa mô tả thỏa mãn các yêu cầu của một thuật toán nói chung, đó là: - Tính hữu hạn: Thuật toán cần phải kết thúc sau một số hữu hạn bước. Khi thuật toán ngừng làm việc ta phải thu được câu trả lời cho vấn đề đặt ra. Thuật toán m rõ ràng thỏa mãn điều kiện này, vì ở mỗi bước ta luôn chỉ từ việc xem xét một số sang số đứng trước nó và số các số là hữu hạn. - Tính xác định: Ở mỗi bước thuật toán cần phải xác định, nghĩa là chỉ rõ việc cần làm. Nếu đối với người đọc thuật toán trên chưa thỏa mãn được điều kiện này thì đó là lỗi của người viết. IT Ngoài những yếu tố kể trên, ta còn phải xét đến tính hiệu quả của thuật toán. Có rất nhiều thuật toán về mặt lý thuyết là hữu hạn bước, tuy nhiên thời gian hữu hạn đó vượt quá khả năng làm việc của chúng ta. Những thuật toán đó sẽ không được xét đến ở đây, vì chúng ta chỉ quan tâm những thuật toán có thể sử dụng thực sự trên máy tính. PT Cũng do mục tiêu trên, ta còn phải chú ý đến độ phức tạp của các thuật toán. Độ phức tạp của một thuật toán có thể được đo bằng không gian tức là dung lượng bộ nhớ của máy tính cần thiết để thực hiện thuật toán và bằng thời gian, tức là thời gian máy tính làm việc. Ở đây khi nói đến độ phức tạp của thuật toán ta luôn hiểu là độ phức tạp của thời gian. 1.3.2. Độ phức tạp của thuật toán Thời gian làm việc của máy tính khi chạy một thuật toán nào đó không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào máy tính được sử dụng. Vì thế, để có một tiêu chuẩn chung, ta sẽ đo độ phức tạp của một thuật toán bằng số các phép tính phải làm khi thực hiện thuật toán. Khi tiến hành cùng một thuật toán, số các phép tính phải thực hiện còn phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thế độ phức tạp của thuật toán sẽ là một hàm số của độ lớn đầu vào. Trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết cỡ của chúng, tức là cần có một ước lượng đủ tốt của chúng. Trong khi làm việc, máy tính thường ghi các chữ số bằng bóng đèn sáng, tắt, bóng đèn sáng chỉ số 1, bóng đèn tắt chỉ số 0. Vì thế để thuận tiện nhất là dùng hệ đếm cơ số 2, trong đó để biểu diễn một số, ta chỉ cần dùng hai ký hiệu 0 và 1. Một ký hiệu 0 hoặc 1 được gọi là 1bit viết tắt của binary digit. Một số nguyên n biểu diễn bởi k chữ số 1 và 0 được gọi là một số k bit . Độ phức tạp của một thuật toán được đo bằng số các phép tính bit. Phép tính bit là một phép tính logic hay số học thực hiện trên các số một bit 0 và 1. Để ước lượng độ phức tạp của thuật toán ta dùng khái niệm bậc O lớn. 4 Ch¬ng 1: NhËp m«n mËt m· häc Định nghĩa 1.2: Giả sử f n và g n là hai hàm xác định trên tập hợp các số nguyên dương. Ta nói f n có bậc O-lớn của g n và viết f n O g n , nếu tồn tại một số C 0 sao cho với n đủ lớn. Các hàm f n và g n đều dương thì f n C g n . Ví dụ 1.1. : 1] Giả sử f n là đa thức: f n ad n d ad 1n d 1 ... a1n a 0 trong đó ad 0 . Dễ chứng minh f n O n d . 2] Nếu f n O g n , f2 n O g n thì f1 f2 O g . 3] Nếu f1 O g1 , f2 O g2 thì f1 f2 O g1g2 . lim n f n g n thì f O g IT 4] Nếu tồn tại giới hạn hữu hạn: 5] Với mọi số 0 , log n O n PT Định nghĩa 1.3: Một thuật toán được gọi là có độ phức tạp đa thức hoặc có thời gian đa thức, nếu số các phép tính cần thiết để thực hiện thuật toán không vượt quá O logd n , trong đó n là độ lớn của đầu vào và d là số nguyên dương nào đó. Nói cách khác nếu đầu vào là các số k bit thì thời gian thực hiện thuật toán là O k d , tức là tương đương với một đa thức của k . Các thuật toán với thời gian O n , 0 được gọi là thuật toán với độ phức tạp mũ hoặc thời gian mũ. Chú ý rằng nếu một thuật toán nào đó có độ phức tạp O g thì cũng có thể nói nó có độ phức tạp O h với mọi hàm h g . Tuy nhiên ta luôn luôn cố gắng tìm ước lượng tốt nhất có thể để tránh hiểu sai về độ phức tạp thực sự của thuật toán. Cũng có những thuật toán có độ phức tạp trung gian giữa đa thức và mũ. Ta thường gọi đó là thuật toán dưới mũ. Chẳng hạn thuật toán nhanh nhất được biết hiện nay để phân tích một số nguyên n ra thừa số là thuật toán có độ phức tạp: exp log n log log n 5 Ch¬ng 1: NhËp m«n mËt m· häc Khi giải một bài toán không những ta chỉ cố gắng tìm ra một thuật toán nào đó, mà còn muốn tìm ra thuật toán tốt nhất. Đánh giá độ phức tạp là một trong những cách để phân tích, so sánh và tìm ra thuật toán tối ưu. Tuy nhiên độ phức tạp không phải là tiêu chuẩn duy nhất để đánh giá thuật toán. Có những thuật toán về lý thuyết thì có độ phức tạp cao hơn một thuật toán khác, nhưng khi sử dụng lại có kết quả [gần đúng] nhanh hơn nhiều. Điều này còn tùy thuộc những bài toán cụ thể, những mục tiêu cụ thể và cả kinh nghiệm của người sử dụng. Chúng ta cần lưu ý thêm một số điểm sau đây. Mặc dù định nghĩa thuật toán mà chúng ta đưa ra chưa phải là chặt chẽ, nó vẫn quá cứng nhắc trong những ứng dụng thực tế. Bởi vậy chúng ta còn cần đến các thuật toán xác suất, tức là các thuật toán phụ thuộc vào một hay nhiều tham số ngẫu nhiên. Những thuật toán này về nguyên tắc không được gọi là thuật toán vì chúng có thể với xác suất rất bé, không bao giờ kết thúc. Tuy nhiên thực nghiệm chỉ ra rằng, các thuật toán xác suất thường hữu hiệu hơn các thuật toán không xác suất. Thậm chí trong rất nhiều trường hợp, chỉ có các thuật toán như thế là sử dụng được. IT Khi làm việc với các thuật toán xác suất, ta thường hay phải sử dụng các số ngẫu nhiên. Khái niệm chọn số ngẫu nhiên cũng cần được chính xác hóa. Thường thì người ta sử dụng một máy sản xuất số giả ngẫu nhiên nào đó. Tuy nhiên ở đây khi nói đến việc chọn số ngẫu nhiên ta hiểu đó là được thực hiện trên máy. Cần chú ý ngay rằng, đối với các thuật toán xác suất, không thể nói đến thời gian tuyệt đối, mà chỉ có thể nói đến thời gian hy vọng [expected]. PT Để hình dung được phần nào độ phức tạp của các thuật toán khi làm việc với những số lớn, ta xem Bảng 1.1 dưới đây cho khoảng thời gian cần thiết để phân tích một số nguyên n ra thừa số nguyên tố bằng thuật toán nhanh nhất được biết hiện nay. Bảng 1.1. Độ phức tạp để phân tích số nguyên ra thừa số nguyên tố Số chữ số thập phân Số phép tính bit Thời gian 50 1, 4.1010 3,9 giờ 75 9.1012 104 ngày 100 2,3.1015 74 năm 200 1, 2.1023 3,8.109 năm 300 1,5.1029 4,9.1015 năm 500 1,3.1039 4, 2.1025 năm Từ Bảng 1.1 trên, ta thấy rằng ngay với một thuật toán dưới mũ, thời gian làm việc với các số nguyên lớn là quá lâu. Vì thế nói chung người ta luôn cố gắng tìm những thuật toán đa thức. 6 Ch¬ng 1: NhËp m«n mËt m· häc 1.4. LÝ THUYẾT THÔNG TIN TRONG CÁC HỆ MẬT Năm 1949, Claude Shannon đã công bố một bài báo có nhan đề Lý thuyết thông tin trong các hệ mật trên tạp chí The Bell System Technical Journal. Bài báo đã có ảnh hưởng lớn đến việc nghiên cứu khoa học mật mã. Trong chương này ta sẽ thảo luận một vài ý tưởng trong lý thuyết của Shannon. 1.4.1. Độ mật hoàn thiện. Có hai quan điểm cơ bản về độ an toàn của một hệ mật. 1.4.1.1. Độ an toàn tính toán IT Độ đo này liên quan đến những nỗ lực tính toán cần thiết để phá một hệ mật. Một hệ mật là an toàn về mặt tính toán nếu một thuật toán tốt nhất để phá nó cần ít nhất N phép toán, N là số rất lớn nào đó. Vấn đề là ở chỗ, không có một hệ mật thực tế đã biết nào có thể được chứng tỏ là an toàn theo định nghĩa này. Trên thực tế, người ta gọi một hệ mật là "an toàn về mặt tính toán" nếu có một phương pháp tốt nhất phá hệ này nhưng yêu cầu thời gian lớn đến mức không chấp nhận được. [Điều này tất nhiên là rất khác với việc chứng minh về độ an toàn]. PT Một quan điểm chứng minh về độ an toàn tính toán là quy độ an toàn của một hệ mật về một bài toán đã được nghiên cứu kỹ và bài toán này được coi là khó. Ví dụ, ta có thể chứng minh một khẳng định có dạng. Một hệ mật đã cho là an toàn nếu không thể phân tích ra thừa số một số nguyên n cho trước". Các hệ mật loại này đôi khi gọi là An toàn chứng minh được". Tuy nhiên cần phải hiểu rằng, quan điểm này chỉ cung cấp một chứng minh về độ an toàn có liên quan để một bài toán khác chứ không phải là một chứng minh hoàn chỉnh về độ an toàn. [Tình hình này cũng tương tự như việc chứng minh một bài toán là NP đầy đủ: Có thể chứng tỏ bài toán đã cho chí ít cũng khó như một bài toán NP đầy đủ khác, song không phải là một chứng minh hoàn chỉnh về độ khó tính toán của bài toán]. 1.4.1.2. Độ an toàn không điều kiện Độ đo này liên quan đến độ an toàn của các hệ mật khi không có một hạn chế nào được đặt ra về khối lượng tính toán mà Oscar được phép thực hiện. Một hệ mật được gọi là an toàn không điều kiện nếu nó không thể bị phá thậm chí với khả năng tính toán không hạn chế. Khi thảo luận về độ an toàn của một hệ mật, ta cũng phải chỉ ra kiểu tấn công đang được xem xét. Trong chương ta thấy rằng, không một hệ mật nào trong các hệ mã dịch vòng, mã thay thế và mã Vigenère được coi là an toàn về mặt tính toán với phương pháp tấn công chỉ với bản mã [Với khối lượng bản mã thích hợp]. Điều mà ta sẽ làm trong phần này là để phát triển lý thuyết về các hệ mật có độ an toàn không điều kiện với phương pháp tấn công chỉ với bản mã. Có thể thấy rằng, cả ba hệ mật nêu trên đều là các hệ mật an toàn vô điều kiện chỉ khi mỗi phần tử của bản rõ được mã hoá bằng một khoá cho trước. Rõ ràng là độ an toàn không điều kiện của một hệ mật không thể được nghiên cứu theo quan điểm độ phức tạp tính toán vì thời gian tính toán cho phép không hạn chế. Ở đây lý 7 Ch¬ng 1: NhËp m«n mËt m· häc thuyết xác suất là nền tảng thích hợp để nghiên cứu về độ an toàn không điều kiện. Tuy nhiên ta chỉ cần một số kiến thức sơ đẳng trong xác suất; các định nghĩa chính sẽ được nêu dưới đây. Định nghĩa 1.4: Giả sử X và Y là các biến ngẫu nhiên. Kí hiệu xác suất để X nhận giá trị x là p[x] và để Y nhận giá trị y là p y . Xác suất đồng thời p x , y là xác suất để X nhận giá trị x và Y nhận giá trị y. Xác suất có điều kiện p x y là xác suất để X nhận giá trị x với điều kiện Y nhận giá trị y. Các biến ngẫu nhiên X và Y được gọi là độc lập nếu p x , y p x p y với mọi giá trị có thể x của X và y của Y. Quan hệ giữa xác suất đồng thời và xác suất có điều kiện được biểu thị theo công thức: p x , y p x y p y [1.1] p x , y p y x p x [1.2] IT Đổi chỗ x và y ta có: Từ hai biểu thức trên ta có thể rút ra kết quả sau:[được gọi là định lý Bayes] Định lý 1.1: [Định lý Bayes] PT Nếu p y 0 thì: p x y p x p y x p y [1.3] Hệ quả 1.1. x và y là các biến độc lập khi và chỉ khi: p x y p x , x , y . Trong phần này ta giả sử rằng, một khoá cụ thể chỉ dùng cho một bản mã. Giả sử có một phân bố xác suất trên không gian bản rõ P . Kí hiệu xác suất tiên nghiệm để bản rõ xuất hiện là pP [x ] . Cũng giả sử rằng, khóa K được chọn [bởi Alice và Bob] theo một phân bố xác suất xác định nào đó. [Thông thường khoá được chọn ngẫu nhiên, bởi vậy tất cả các khoá sẽ đồng khả năng, tuy nhiên đây không phải là điều bắt buộc]. Kí hiệu xác suất để khóa K được chọn là pK [K ] . Cần nhớ rằng khóa được chọn trước khi Alice biết bản rõ. Bởi vậy có thể giả định rằng khoá K và bản rõ x là các sự kiện độc lập. Hai phân bố xác suất trên P và K sẽ tạo ra một phân bố xác suất trên C . Thật vậy, có thể dễ dàng tính được xác suất pP [y ] với y là bản mã được gửi đi. Với một khoá K K , ta xác định: C K eK x : x P Ở đây C [K ] biểu thị tập các bản mã có thể nếu K là khóa. Khi đó với mỗi y C , ta có: 8