An toàn mạng máy tính - Bài 3: Các giải thuật mã hoá dữ liệu

AN TOÀN MẠNG MÁY TÍNH ThS. Tô Nguyễn Nhật Quang Trường Đại Học Công Nghệ Thông Tin Khoa Mạng Máy Tính và Truyền Thông ATMMT - TNNQ 2 NỘI DUNG MÔN HỌC 1. Tổng quan về an ninh mạng 2. Các phần mềm gây hại 3. Các giải thuật mã hoá dữ liệu 4. Mã hoá khoá công khai và quản lý khoá 5. Chứng thực dữ liệu 6. Một số giao thức bảo mật mạng 7. Bảo mật mạng không dây 8. Bảo mật mạng vành đai 9. Tìm kiếm phát hiện xâm nhập CÁC GIẢI THUẬT Mà HOÁ DỮ LIỆU BÀI 3 ATMMT - TNNQ 4 Các giải thuật mã hoá dữ liệu 1. Giới thiệu về mật mã hoá 2. Lịch sử của mật mã 3. Giải thuật mã hoá cổ điển 4. Giải thuật mã hoá hiện đại 5. Bẻ gãy một hệ thống mật mã 6. Bài tập ATMMT - TNNQ 5 1. Giới thiệu về mật mã hoá „ Giới thiệu – Mật mã hoá được sử dụng kể từ cổ đại cho đến tận ngày nay. – Hiện nay, các giao dịch tài chính, chuyển khoản, mua sắm hàng hoá, thư từ, tài liệu được thực hiện nhiều qua môi trường mạng đòi hỏi dữ liệu phải được bảo mật tốt => phải được mã hoá. ATMMT - TNNQ 6 1. Giới thiệu về mật mã hoá „ Một số khái niệm – Thông báo, văn bản: là một chuỗi hữu hạn các ký hiệu lấy từ một bảng chữ cái Z nào đó và được ký hiệu là m. – Mật mã hoá: là việc biến đổi một thông báo sao cho nó không thể hiểu nổi đối với bất kỳ người khác ngoài người nhận được mong muốn. – Phép mật mã hoá thường được ký hiệu là e(m), với m là thông báo cần mã hoá. ATMMT - TNNQ 7 1. Giới thiệu về mật mã hoá „ Một số khái niệm – Khoá: là một thông số đầu vào của phép mã hoá hoặc giải mã. Khoá dùng để mã hoá ký hiệu là ke, khoá dùng để giải mã ký hiệu là kd. – Chuỗi mật mã: là chuỗi nguỵ trang, tức là chuỗi thông báo qua phép mật mã hoá và thường được ký hiệu là c: c=e(m,ke). – Phép giải mã d(c,kd) là quá trình xác định thông báo gốc (m) từ chuỗi mật mã c và khoá giải mã kd, và thường được ký hiệu là d(c,kd): d(c,kd)=m. ATMMT - TNNQ 8 1. Giới thiệu về mật mã hoá ATMMT - TNNQ 9 2. Lịch sử của mật mã Mật mã học là ngành có lịch sử hàng ngàn năm. Mật mã học cổ điển với bút và giấy. Mật mã học hiện đại với điện cơ, điện tử, máy tính. Sự phát triển của mật mã học đi liền với sự phát triển của phá mã (thám mã): – Phát hiện ra bức điện Zimmermann khiến Hoa Kỳ tham gia Thế chiến I – Việc phá mã thành công hệ thống mật mã của Đức Quốc xã góp phần đẩy nhanh thời điểm kết thúc thế chiến II. Hai sự kiện khiến cho mật mã học trở nên đại chúng: – Sự xuất hiện của tiêu chuẩn mật mã hóa DES. – Sự ra đời của các kỹ thuật mật mã hóa khóa công khai. ATMMT - TNNQ 10 2. Lịch sử của mật m㠄 Mật mã học cổ điển – Các chữ tượng hình không tiêu chuẩn tìm thấy trên các bức tượng Ai Cập cổ đại (cách đây khoảng 4500 năm tr.CN). – Mã hóa thay thế bảng chữ cái đơn giản như mật mã hóa Atbash (khoảng năm 500-600 tr.CN). – Người La Mã xây dựng mật mã Caesar. ATMMT - TNNQ 11 2. Lịch sử của mật m㠄 Mật mã học trong thế chiến thứ 2 – Người Đức sử dụng rộng rãi một hệ thống máy rôto cơ điện tử có tên gọi là máy Enigma. – Phe Đồng minh sử dụng máy TypeX của Anh và máy SIGABA của Mỹ, đều là những thiết kế cơ điện dùng rôto tương tự như máy Enigma, song với nhiều nâng cấp hơn. ATMMT - TNNQ 12 Máy Enigma ATMMT - TNNQ 13 Máy Enigma ATMMT - TNNQ 14 2. Lịch sử của mật m㠄 Mật mã học hiện đại – Cha đẻ của mật mã học hiện đại là Claude Shannon. – Tiêu chuẩn mật mã hóa dữ liệu (Data Encryption Standard) là một phương thức mã hoá công khai được công bố tại Mỹ vào ngày 17.03.1975. – Với chiều dài khoá chỉ là 56-bit, DES đã được chứng minh là không đủ sức chống lại những tấn công kiểu vét cạn (brute force attack - tấn công dùng bạo lực). ATMMT - TNNQ 15 2. Lịch sử của mật m㠄 Mật mã học hiện đại – Năm 2001, DES đã chính thức được thay thế bởi AES (Advanced Encryption Standard - Tiêu chuẩn mã hóa tiên tiến). – Trước thời kỳ này, hầu hết các thuật toán mật mã hóa hiện đại đều là những thuật toán khóa đối xứng (symmetric key algorithms), trong đó cả người gửi và người nhận phải dùng chung một khóa, và cả hai người đều phải giữ bí mật về khóa này. – Đối với mật mã hóa dùng khóa bất đối xứng, người ta phải có một cặp khóa có quan hệ toán học để dùng trong thuật toán, một dùng để mã hóa và một dùng để giải mã. Phổ biến nhất là mã hoá RSA. ATMMT - TNNQ 16 2. Lịch sử của mật m㠄 Mật mã học hiện đại ATMMT - TNNQ 17 2. Lịch sử của mật m㠄 Mật mã học hiện đại Mã hoá RSA ATMMT - TNNQ 18 3. Giải thuật mã hoá cổ điển Các yêu cầu cơ bản đối với giải thuật mật mã hoá là: – Có tính bảo mật cao – Công khai, dễ hiểu. Khả năng bảo mật được chốt vào khoá chứ không vào bản thân giải thuật. – Có thể triển khai trên các thiết bị điện tử. ATMMT - TNNQ 19 3. Giải thuật mã hoá cổ điển „ Mã thay thế đơn giản (Substitution Cipher) – Trong phép này, khoá là một hoán vị h của bảng chữ cái Z và mỗi ký hiệu của thông báo được thay thế bằng ảnh của nó qua hoán vị h. – Khoá thường được biểu diễn bằng một chuỗi 26 ký tự. Có 26! (≈ 4.1026) hoán vị (khoá) – Ví dụ: khoá là chuỗi UXEOS, ký hiệu A trong thông báo sẽ được thay bằng U, ký hiệu B sẽ được thay bằng X – Ö Phá mã? ATMMT - TNNQ 20 3. Giải thuật mã hoá cổ điển „ Mã thay thế đơn giản (Substitution Cipher) Chọn một hoán vị p: Z26Æ Z26 làm khoá. VD: – Mã hoá ep(a)=X – Giải mã dp(A)=d ATMMT - TNNQ 21 3. Giải thuật mã hoá cổ điển „ Mã thay thế n-gram – Thay vì thay thế các ký tự, người ta có thể thay thế cho từng cụm 2 ký tự (diagram), 3 ký tự (trigram) hoặc tổng quát cho từng cụm n ký tự (n-gram). – Với bảng chữ cái gồm 26 ký tự tiếng Anh thì phép thay thế n-gram sẽ có khoá là một hoán vị của 26n n-gram khác nhau. – Ö Phá mã? ATMMT - TNNQ 22 3. Giải thuật mã hoá cổ điển „ Mã thay thế n-gram Trong trường hợp diagram thì hoán vị gồm 262 diagram và có thể biểu diễn bằng một dãy 2 chiều 26x26 trong đó các hàng biểu diễn ký hiệu đầu tiên, các cột biểu diễn ký hiệu thứ hai, nội dung của các ô biểu diễn chuỗi thay thế. A B A EG RS B BO SC ATMMT - TNNQ 23 3. Giải thuật mã hoá cổ điển „ Mã hoán vị bậc d (Permutation Cypher) – Đối với một số nguyên dương d bất kỳ, chia thông báo m thành từng khối có chiều dài d. Rồi lấy một hoán vị h của 1, 2, , d và áp dụng h vào mỗi khối. – Ví dụ: nếu d=5 và h=(4 1 3 2 5), hoán vị (1 2 3 4 5) sẽ được thay thế bằng hoán vị mới (4 1 3 2 5). ATMMT - TNNQ 24 3. Giải thuật mã hoá cổ điển 3. Mã hoán vị bậc d Ví dụ: ta có thông báo m = JOHN IS A GOOD ACTOR Qua phép mã hoá này m sẽ trở thành chuỗi mật mã c sau: c = NJHO AI S DGOO OATCR Ö Phá mã? ATMMT - TNNQ 25 3. Giải thuật mã hoá cổ điển 4. Mã dịch chuyển (Shift Cypher) Vigenère và Caesar Trong phương pháp Vigenère, khoá bao gồm một chuỗi có d ký tự. Chúng được viết lặp lại bên dưới thông báo và được cộng modulo 26. Các ký tự trắng được giữ nguyên không cộng. Nếu d=1 thì khoá chỉ là một ký tự đơn và được gọi là phương pháp Caesar (được đưa ra sử dụng đầu tiên bởi Julius Caesar). Ö Phá mã? ATMMT - TNNQ 26 Ví dụ: Plaintext: CRYPTOGRAPHY Ciphertext: HWDUYTLWFUMD (Shift of 5) C=(p+4) mod 26 The classic Caesar Shift chart ATMMT - TNNQ 27 Mã dịch chuyển – Shift Cypher ATMMT - TNNQ 28 Ví dụ: Từ khoá: CHIFFRE Mã hoá: VIGENERE Kết quả: XPOJSVVG Vigenère Encryption – Block Cypher (1523 – 1596) ATMMT - TNNQ 29 3. Giải thuật mã hoá cổ điển 5. One - time Pad: h e l p n e e d e d 001 000 010 100 101 000 000 011 000 011 e=000 h=001 l=010 d=011 p=100 n=101 a=110 Encryption: Plaintext ⊕ Key = Ciphertext 111 101 110 101 111 100 000 101 110 000 110 101 100 001 010 100 000 110 110 011 a n p h l p e a a d Plaintext: Key: Ciphertext: ATMMT - TNNQ 30 3. Giải thuật mã hoá cổ điển 6. Mã tuyến tính (Affine Cipher) Mã tuyến tính là mã thay thế có dạng: e(x) = ax + b (mod 26), với a, b ∈ Z26. Nếu a = 1 ta có mã dịch chuyển. Giải mã: Tìm x? y = ax + b (mod 26) ax = y – b (mod 26) x = a-1(y – b) (mod 26). ATMMT - TNNQ 31 3. Giải thuật mã hoá cổ điển 7. Phương pháp phá mã cổ điển: Dựa vào đặc điểm ngôn ngữ. Dựa vào tần suất xuất hiện của các chữ cái trong bảng chữ cái thông qua thống kê từ nhiều nguồn văn bản khác nhau, dựa vào số lượng các ký tự trong bảng mã để xác định thông báo đầu vào. ATMMT - TNNQ 32 Tần suất của các ký tự trong ngôn ngữ tiếng Anh ATMMT - TNNQ 33 4. Giải thuật mã hoá hiện đại „ Thường sử dụng mã khối kết hợp với các phép hoán vị và thay thế. „ Việc biến đổi văn bản được thực hiện nhiều lần trong một số vòng lặp. „ Khoá con của các vòng lặp sẽ khác nhau và được sinh ra từ khoá ban đầu. „ Phổ biến có DES, AES, RSA... ATMMT - TNNQ 34 4. Giải thuật mã hoá hiện đại 1. Phân loại Mã hoá khoá đối xứng (symmetric): – Block ciphers: mã hoá các khối có chiều dài cố định 64 bit hoặc 128 bit. Phổ biến có IDEA, RC2, DES, Triple DES, Rijndael (AES), MARS, RC6, Serpent, Twofish, DESX, DESL, DESXL. – Stream ciphers: mã hoá từng bit của thông điệp. Đại diện là RC4. Mã hoá khoá bất đối xứng (asymmetric): RSA ATMMT - TNNQ 35 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES DES (Data Encryption Standard) được sử dụng rộng rãi trên thế giới. Dùng khoá có độ dài 56 bit để mã hoá các khối dữ liệu 64 bit. Cả bên mã hoá lẫn bên giải mã đều dùng chung một khoá và DES thuộc vào hệ mã khoá bí mật. Xét về độ an toàn, hiện nay 3DES (một cải tiến của DES) được đánh giá là có độ an toàn cao vì độ dài khoá của nó gấp 3 lần so với DES. ATMMT - TNNQ 36 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 37 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 38 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 39 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 40 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 41 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 42 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 43 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 44 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 45 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 46 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 47 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 48 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 49 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 50 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 51 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 52 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 53 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 54 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 55 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 56 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 57 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 58 4. Giải thuật mã hoá hiện đại 2. Chuẩn mã hoá dữ liệu DES ATMMT - TNNQ 59 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA Được sử dụng phổ biến trong thương mại điện tử Đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. Thuật toán RSA có hai khóa: – khóa công khai (hay khóa công cộng) – khóa bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. ATMMT - TNNQ 60 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau : – Bob muốn gửi cho Alice một thông tin mật. – Alice sẽ gửi cho Bob một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. – Bob nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa. – Sau đó Bob gửi chiếc hộp lại cho Alice. – Alice mở hộp với chìa khóa của mình và đọc thông tin trong thư. – Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật. ATMMT - TNNQ 61 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA Bob Alice ATMMT - TNNQ 62 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA Chọn một số ngẫu nhiên lớn để sinh cặp khóa. Dùng khoá công khai để mã hóa, nhưng dùng khoá bí mật để giải mã. ATMMT - TNNQ 63 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA Dùng khoá bí mật để ký một thông báo; dùng khoá công khai để xác minh chữ ký. Tổ hợp khoá bí mật của mình với khoá bí mật của người khác tạo ra khoá dùng chung chỉ hai người biết. ATMMT - TNNQ 64 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA ATMMT - TNNQ 65 4. Giải thuật mã hoá hiện đại 3. Hệ mã hoá công khai RSA Các giải thuật mã hoá DES và RSA còn được ứng dụng vào chữ ký điện tử. Giải thuật RSA là rất an toàn nhưng tốc độ mã hoá và giải mã chậm hơn giải thuật DES hàng ngàn lần. Thông thường người ta thường kết hợp hai phương pháp mã hoá DES và RSA như sau: – DES mã hoá khối văn bản. – RSA để mã hoá khoá mà DES đã dùng để mã hoá khối văn bản. ATMMT - TNNQ 66 5. Bẻ gãy một hệ thống mật mã Những chuyên gia mật mã hay những kẻ tấn công thường được giả thiết biết đầy đủ thông tin về hàm mã hoá e và hàm giải mã d. Các chuyên gia này cũng có thể có thêm nhiều thông tin hỗ trợ như các thống kê về ngôn ngữ, kiến thức về ngữ cảnh... Với một chuỗi mật mã nào đó, họ thiếu khoá k để có thể sử dụng d để giải mã c một cách chính xác. ATMMT - TNNQ 67 5. Bẻ gãy một hệ thống mật mã ATMMT - TNNQ 68 5. Bẻ gãy một hệ thống mật mã Các khả năng tấn công trên hệ thống: 1. Tấn công chỉ dựa trên chuỗi mật mã (crytogram-only attack): đối phương chỉ biết một vài mẫu chuỗi mật mã c. 2. Tấn công dựa trên văn bản đã biết (known-plaintext attack): Trong trường hợp này những người tấn công được giả thiết là đã biết một độ dài đáng kể của văn bản thông báo và chuỗi mật mã tương ứng, và từ đó cố gắng tìm ra khoá. 3. Tấn công dựa trên văn bản được chọn (chosen-plaintext attack): những người tấn công có thể đã có được một số lượng tuỳ ý của các cặp thông báo và chuỗi mật mã tương ứng (m, c). ATMMT - TNNQ 69 5. Bẻ gãy một hệ thống mật mã Các khả năng tấn công trên hệ thống: Kiểu tấn công Đối phương nắm được ciphertext only attack Chỉ văn bản mã c known plaintext attack Cả văn bản nguồn p và văn bản mã c chosen plaintext attack Đột nhập được vào máy mã hoá. Tự chọn văn bản p và mã hoá lấy được văn bản mã c tương ứng. chosen ciphertext attack Đột nhập được vào máy giải mã. Tự chọn văn bản mã c và giải mã lấy được văn bản p tương ứng. ATMMT - TNNQ 70 5. Bẻ gãy một hệ thống mật mã Key size (bits) Number of alternative keys Time required at 1 decryption/μs Time required at 106 decryption/μs 32 232 = 4.3 x 109 231 μs = 35.8 minutes 2.15 milliseconds 56 256 = 7.2 x 1016 255 μs = 1142 years 10.01 hours 128 2128 = 3.4 x 1038 2127 μs = 5.4 x 1024 years 5.4 x 1018 years 168 2168 = 3.7 x 1050 2167 μs = 5.9 x 1036 years 5.9 x 1030 years 26 characters (permutation) 26! = 4 x 1026 2 x 1026 μs = 6.4 x 1012 years 6.4 x 106 years Thời gian trung bình để tìm khoá theo kiểu vét cạn ATMMT - TNNQ 71 6. Bài tập 1. Giải thích cơ chế của việc bẻ gãy mật mã của hệ thống sau: ATMMT - TNNQ 72 6. Bài tập 2. Tìm mã hoá của các ký số 1-9: Mỗi biểu tượng trong số chín biểu tượng xuất hiện trong mảng dưới đây (U{♥♠◊♣y) mã hóa duy nhất một trong các chữ số 1 đến 9. Cột ngoài cùng bên phải là các tổng số ở mỗi hàng Hàng dưới cùng cho các tổng số ở mỗi cột. Một dấu hỏi có thể đại diện cho bất kỳ một hoặc hai chữ số và không nhất thiết phải cùng một số trong mỗi trường hợp. ATMMT - TNNQ 73 6. Bài tập 2. Tìm mã hoá của các ký số 1-9: ATMMT - TNNQ 74 6. Bài tập 3. Sử dụng công cụ Cryptool Cryptool là một ứng dụng miễn phí chạy trên Windows, thường được sử dụng để phân tích các giải thuật mã hoá. Phiên bản hiện nay là 1.4.30. Địa chỉ download Cryptool: ATMMT - TNNQ 75 6. Bài tập 4. Nêu cơ chế hoạt động và viết ứng dụng cho phép mã hoá và giải mã với 2 (hai) trong số những giải thuật mã hoá sau: i. Vigenère ii. Hill. iii. Affine iv. Playfair v. Solitaire ATMMT - TNNQ 76 6. Bài tập 5. Nêu chi tiết cơ chế hoạt động của giải thuật mã hoá DES. 6. Trình bày tổng quan về cơ chế hoạt động của các giải thuật RC4 và RSA. 7. Viết ứng dụng mã hoá và giải mã cho một giải thuật mã hoá hiện đại tuỳ chọn. ATMMT - TNNQ 77