GIÁO TRÌNH AN TOÀN THÔNG TIN - CHƯƠNG 1 AN TOÀN DỮ LIỆU TRÊN MẠNG MÁY TÍNH

Chia sẻ: Lê Đắc Nhường | Ngày: | Loại File: DOCX | Số trang:85

Thêm vào BST

Báo xấu

440
lượt xem 106
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ngày nay, với sự phát triển mạnh mẽ của công nghệ thông tin việc ứng dụng các công nghệ mạng máy tính trở nên vô cùng phổ cập và cần thiết. Công nghệ mạng máy tính đã mang lại những lợi ích to lớn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: GIÁO TRÌNH AN TOÀN THÔNG TIN - CHƯƠNG 1 AN TOÀN DỮ LIỆU TRÊN MẠNG MÁY TÍNH

MỤC LỤC
CHƯƠNG 1 AN TOÀN DỮ LIỆU TRÊN MẠNG MÁY TÍNH Ngày nay, với sự phát triển mạnh mẽ của công nghệ thông tin việc ứng dụng các công nghệ mạng máy tính trở nên vô cùng phổ cập và cần thiết. Công nghệ mạng máy tính đã mang lại những lợi ích to lớn. Sự xuất hiện mạng Internet cho phép mọi người có thể truy cập, chia sẽ và khai thác thông tin một cách dễ dàng và hiệu quả. Các công nghệ E-mail cho phép mọi người có thể gửi thư cho người khác cũng như nhận thư ngay trên máy tính của mình. Gần đây có công nghệ E-business cho phép thực hiện các hoạt động thương mại trên mạng máy tính. Việc ứng dụng các mạng cục bộ trong các tổ chức, công ty hay trong một quốc gia là rất phong phú. Các hệ thống chuyển tiền của các ngân hàng hàng ngày có thể chuyển hàng tỷ đôla qua hệ thống của mình. Các thông tin về kinh tế, chính trị, khoa học xã hội được trao đổi rông rãi. Tuy nhiên lại nảy sinh vấn đề về an toàn thông tin. Đó cùng là một quá trình tiến triển hợp logic: khi những vui thích ban đầu về một siêu xa lộ thông tin, bạn nhất định nhận thấy rằng không chỉ cho phép bạn truy nhập vào nhiều nơi trên thế giới, Internet còn cho phép nhiều người không mời mà tự ý ghé thăm máy tính của bạn. Thực vậy, Internet có những kỹ thuật tuyệt vời cho phép mọi người truy nhập, khai thác, chia sẻ thông tin. Những nó cũng là nguy cơ chính dẫn đến thông tin của bạn bị hư hỏng hoặc phá huỷ hoàn toàn. Có những thông tin vô cùng quan trọng mà việc bị mất hay bị làm sai lệch có thể ảnh hưởng đến các tổ chức, các công ty hay cả một quốc gia. Các thông tin về an ninh quốc gia, bí mật kinh doanh hay các thông tin tài chính là mục tiêu của các tổ chức tình báo nước ngoài về chính trị hay công nghiệp hoặc kẻ cắp nói chung. Bọn chúng có thể làm mọi việc có thể để có được những thông tin quý giá này. Thử tưởng tượng nếu có kẻ xâm nhập được vào hệ thống chuyển tiền của các ngân hàng thì ngân hàng đó sẽ chịu những thiệt hại to lớn như mất tiền có thể dẫn tới bị phá sản. Chưa kể nếu hệ thông thông tin an ninh quốc gia bị đe doạ thì hậu quả không thể lường trước được. Theo số liệu của CERT(Computer Emegency Response Team - “Đội cấp cứu máy tính”), số lượng các vụ tấn công trên Internet được thông báo cho tổ chức này là ít hơn 200 vào năm 1989, khoảng 400 vào năm 1991, 1400 vào năm 1993, và 2241 vào năm 1994. Những vụ tấn công này nhằm vào tất cả các máy tính có mặt trên Internet, các máy tính của tất cả các công ty lớn như AT&T, IBM, các trường đ ại học, các c ơ quan nhà nước, các tổ chức quân sự, nhà băng... Một số vụ tấn công có quy mô khổng lồ (có tới 100.000 máy tính bị tấn công). Hơn nữa, những con số này chỉ là phần nổi của tảng băng. Một phần rất lớn các vụ tấn công không được thông báo, vì nhiều lý do, trong đó có thể kể đến nỗi lo bị mất uy tín, hoặc đơn giản những người quản tr ị hệ thống không hề hay biết những cuộc tấn công nhằm vào hệ thống của họ. Không chỉ số lượng các cuộc tấn công tăng lên nhanh chóng, mà các phương pháp tấn công cũng liên tục được hoàn thiện. Điều đó một phần do các nhân viên quản tr ị hệ thống được kết nối với Internet ngày càng đề cao cảnh giác. Cũng theo CERT, những cuộc tấn công thời kỳ 1988-1989 chủ yếu đoán tên người sử dụng-mật khẩu (UserID-password) hoặc sử dụng một số lỗi của các chương trình và hệ điều hành (security hole) làm vô hiệu hệ thống bảo vệ, tuy nhiên các cuộc tấn công vào thời Trang 2 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin gian gần đây bao gồm cả các thao tác như giả mạo địa chỉ IP, theo dõi thông tin truyền qua mạng, chiếm các phiên làm việc từ xa (telnet hoặc rlogin). Để vừa bảo đảm tính bảo mật của thông tin lại không làm giảm sự phát triển của việc trao đổi thông tin quảng bá trên toàn cầu thì một giải pháp tốt nhất là mã hoá thông tin. Có thể hiểu sơ lược mã hoá thông tin là che đi thông tin của mình làm cho kẻ tấn công nếu chặn được thông báo trên đường truyền thì cũng không thể đọc được và phải có một giao thức giữa người gửi và người nhận để có thể trao đổi thông tin, đó là các cơ chế mã và giải mã thông tin. Ngày nay thì việc mã hoá đã trở nên phổ cập. Các công ty phần mềm lớn trên th ế giới đều có nghiên cứu và xây dựng các công cụ, thuật toán mã hoá đ ể áp dụng cho thực tế. Mỗi quốc gia hay tổ chức đều có những cơ chế mã hoá riêng đ ể bảo vệ hệ thống thông tin của mình. Một số vấn đề an toàn đối với nhiều mạng hiện nay:  Một người dùng chuyển một thông báo điện tử cho một người sử dụng khác. Một bên thứ ba trên cùng mạng LAN này sử dụng một thiết bị nghe trộm gói để lấy thông báo và đọc các thông tin trong đó.  Cũng trong tình huống trên bên thứ ba chặn thông báo, thay đổi các thành phần của nó và sau đó lại gửi cho người nhận. Người nhận không hề nghi ngờ gì trừ khi nhận ra thông báo đó là vô lý, và có thể thực hiện vài hành động d ựa trên các thành phần sai này đem lại lợi ích cho bên thứ ba.  Người dùng log vào một server mà không sử dụng mật khẩu được mã hoá. Một người khác đang nge trộm trên đường truyền và bắt được mật khẩu logon của người dùng, sau đó có thể truy nhập thông tin trên server như người sử dụng.  Một người quản trị hệ thống không hiểu về khía cạnh an toàn và yêu cầu c ủa hệ thống và vô tình cho phép người dùng khác truy nhập vào thư mục chứa các thông tin hệ thống. Người dùng phát hiện ra họ có thể có được các thông tin hệ thống và có thể dùng nó phục vụ cho loựi ích của mình. Trang 3 GV. Lê Đắc Nhường
CHƯƠNG 2 CÁC VẤN ĐỀ CƠ BẢN Trong phần này sẽ trình bày về một số cơ sở toán học của mã hóa, điều này s ẽ giúp ta nắm được một cách chi tiết hơn về các phương pháp mã hóa. 2.1 Lý thuyết số 2.1.1 Khái niệm đồng dư Modulo Định nghĩa 1: Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó ta viết a ≡ b(mod m) nếu m chia hết cho b-a. Mệnh để a ≡ b(mod m) được gọi là “a đồng dư với b theo mođun m”. Giả sử chia a và b cho m và ta thu được thương nguyên và phần dư, các phần d ư nằm giữa 0 và m-1, nghĩa là a = q1m + r1 và b = q2m + r2 trong đó 0 ≤ r1 ≤ m-1 và 0 ≤ r2 ≤ m-1. Khi đó có thể dễ dàng thấy rằng a ≡ b(mod m) khi và chỉ khi r1 = r2 . Ta sẽ dùng ký hiệu a mod m để xác định phần dư khi a được chia cho m (chính là giá trị r1 ở trên). Như vậy: a≡ b(mod m) khi và chỉ khi (a mod m) = (b mod m). Nếu thay a bằng a mod m thì ta nói rằng a được rút gọn theo modulo m. Nhận xét: Nhiều ngôn ngữ lập trình của máy tính xác định a mod m là phần dư trong dải -m+1,…,m-1 có cùng dấu với a. Ví dụ -18 mod 7 sẽ là –4, giá trị này khác với giá trị 3 là giá trị được xác định theo công thức trên. Tuy nhiên, để thuận tiện ta sẽ xác định a mod m luôn là một số không âm. Bây giờ ta có thể định nghĩa số học mođun m: Z m được coi là tập hợp {0,1,…,m-1} có trang bị hai phép toán cộng và nhân. Việc cộng và nhân trong Zm được thực hiện giống như cộng và nhân các số thực ngoại trừ một điểm là các kết quả được rút gọn theo mođun m. 2.1.2 Định lý về đồng dư thức Định lí 1: Đồng dư thức ax ≡ b (mod m) chỉ có một nghiệm duy nhất x ∈ Zm với mọi b ∈ Zm khi và chỉ khi UCLN(a,m) = 1. Ta giả sử rằng, UCLN(a,m) = d >1. Khi đó, với b = 0 thì đồng dư thức ax ≡ 0 (mod m) sẽ có ít nhất hai nghiệm phân biệt trong Zm là x = 0 và x = m/d. 2.1.3 Khái niệm phần tử nghịch đảo Định nghĩa 2: Giả sử a ∈ Zm. Phần tử nghịch đảo (theo phép nhân) của a là phần tử a-1 ∈ Zm sao cho aa-1 ≡ a-1a ≡ 1 (mod m) Bằng các lý luận tương tự như trên, có thể chứng tỏ rằng a có nghịch đ ảo theo mođun m khi và chỉ khi UCLN(a,m) = 1, và nếu nghịch đảo này tồn tại thì nó phải là duy nhất. Ta cũng thấy rằng, nếu b = a-1 thì a = b-1. Nếu m là số nguyên tố thì mọi phần tử khác không của Zm đều có nghịch đảo. 2.1.4 Thuật toán Euclide Cho hai số tự nhiên a,n. Ký hiệu (a,n) là ước số chung lớn nhất của a,n; φ(n) là số các số nguyên dương < n và nguyên tố với n. Giả sử n > a. Thuật toán Euclide tìm UCLN (a,n) được thực hiện bằng một dãy các phép chia liên tiếp sau đây: Đặt r0 = n, r1 = a, r0 = q1r1 + r2 , 0 < r2 < r1 Trang 4 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin r1 = q2r2 + r3 , 0 < r3 < r2 ……………………… rm-2 = qm-1rm-1 + rm , 0 < rm < rm-1 rm-1 = qmrm Thuật toán phải kết thúc ở một bước thứ m nào đó. Ta có: (n,a) = (r0,r1) = (r1,r2) = …… = (rm-1,rm) = rm Vậy ta tìm được rm = (n,a). Mở rộng thuật toán Euclide bằng cách xác định thêm dãy số t0, t1,…,tm : t0 = 0, t1 = 1, tj = tj-2 – qj-1tj-1 mod r0 , nếu j ≥ 2 , ta dễ chứng minh bằng qui nạp rằng: rj ≡ tjr1 (mod r0) Do đó, nếu (n,a) = 1, thì tm = a-1 mod n 2.1.5 Phần tử nguyên thủy và logarith rời rạc Cho số n nguyên dương. Ta biết rằng tập các thặng dư thu gọn theo mođun n (tức là tập các số nguyên dương < n và nguyên tố với n) lập thành một nhóm với phép nhân mod n, ta ký hiệu là Zn* . Nhóm đó có cấp (số phần tử) là φ(n). Một phẩn tử g ∈ Zn* có cấp m, nếu m là số nguyên dương bé nhất sao cho gm = 1 trong Zn*. Theo một định lý đại số, ta có m | φ(n) (ký hiệu m là ước số của φ(n)) vì vậy với φ mọi b ∈ Zn* ta luôn có: b (n) ≡ 1 (mod n) Nếu p là số nguyên tố, thì do φ(p) = p-1, nên ta có với mọi b nguyên tố với p bp-1 ≡ 1 (mod p) (1) Nếu b có cấp p-1, thì p-1 là số mũ bé nhất sao cho có công thức (1), do đó các phần tử b, b2,…, bp-1 đều khác nhau, và lập thành Zp*. Nói cách khác, b là một phẩn tử sinh, hay như thường gọi là phần tử nguyên thủy của Zp* ; và khi đó Zp* là một nhóm cyclic. Trong lý thuyết số, người ta đã chứng minh đươc các định lý sau đây: • Với mọi số nguyên tố p, Zp* là nhóm cyclic, và số các phần tử nguyên thủy của Zp* bằng φ(p-1) • Nếu g là phần tử nguyên thủy theo mođun p, thì β = gi, với mọi i mà (i,p-1) = 1, cũng là phần tử nguyên thủy theo mođun p 2.1.6 Thặng dư bậc hai và ký hiệu Legendre Cho p là một số nguyên tố lẻ, và x là một số nguyên dương ≤ p-1. x được gọi là một thặng dư bậc hai theo mođun p, nếu phương trình: y2 ≡ x (mod p) có lời giải. Ta có tiêu chuẩn Euler sau đây: x là thặng dư bậc hai theo mođun p, nếu và chỉ nếu x(p-1)/2 ≡ 1 (mod p) Tiêu chuẩn đó được chứng minh như sau: Giả sử có x ≡ y2 (mod p). Khi đó có: Trang 5 GV. Lê Đắc Nhường
x(p-1)/2 ≡ (y2)(p-1)/2 ≡ yp-1 ≡ 1 (mod p) ; Ngược lại, giả sử rằng x(p-1)/2 ≡ 1 (mod p). Lấy b là một phần tử nguyên thủy (mod p), ta có x ≡ bi (mod p) với số i nào đó. Ta có: x(p-1)/2 ≡ (bi)(p-1)/2 (mod p) ≡ bi(p-1)/2 (mod p) Vì b có cấp p-1, do đó p-1 phải là ước số của i(p-1)/2, suy ra i phải là s ố ch ẵn, và căn bậc hai của x là ± bi/2. Giả sử p là số nguyên tố lẻ. Với mọi a ≥ 0, ta định nghĩa ký hiệu Legendre như sau: Ta có tính chất quan trọng sau đây: nếu p là số nguyên tố lẻ thì với mọi số nguyên a≥ 0, ta có: ≡ a(p-1)/2 (mod p). 2.1.7 Một số thuật toán kiểm tra tính nguyên tố Ta phát biểu một số tính chất sau đây, chúng là cơ sở cho việc phát triển một số thuật toán xác suất thử tính nguyên tố của các số nguyên. Solovay_Strassen : Nếu n là số nguyên tố, thì với mọi 1 ≤ a ≤ n-1: ≡ a(n-1)/2 (mod n). Nếu n là hợp số thì: | {a: 1 ≤ a ≤ n-1, ≡ a(n-1)/2 (mod n)}| ≤ (n-1)/2 Solovay_Strassen (cải tiến bởi Lehmann): Nếu n là số nguyên tố, thì với mọi 1 ≤ a ≤ n-1: a(n-1)/2 ≡ ± 1 (mod n); Nếu n là hợp số thì: | {a: 1 ≤ a ≤ n-1, a(n-1)/2 ≡ ± 1(mod n)}| ≤ (n-1)/2 2.2 Lý thuyết về độ phức tạp tính toán 2.2.4 Độ phức tạp tính toán Lý thuyết thuật toán và các hàm tính ra đời từ những năm 30 đã đặt nền móng cho các nghiên cứu về các vấn đề “tính được”, “giải được”, và đã thu được nhiều kết quả rất quan trọng. Nhưng từ cài “tính được” một cách trừu tượng, tiềm năng đ ến vi ệc tính được trong thực tế của khoa học tính toán bằng máy tính điện t ử là một kho ảng cách rất lớn. Lý thuyết về độ phức tạp tính toán được nghiên cứu bắt đầu t ừ những Trang 6 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin năm 60 đã bù đắp cho khoảng trống đó, cho ta nhiều tri thức cơ bản, đồng thời có nhiều ứng dụng thực tế rất phong phú. Độ phức tạp (về không gian hay thời gian) của một quá trình tính toán là số ô nhớ hay số các phép toán được thực hiện trong quá trình tính toán đó. Độ phức tạp tính toán của một thuật toán được hiểu là một hàm số f, sao cho với mỗi n, f(n) là là số ô nhớ hay số các phép toán tối đa mà thuật toán thực hiện quá trình tính toán của mình trên các dữ liệu vào có độ lớn n. Độ phức tạp tính toán của một bài toán (của một hàm) được định nghĩa là độ phức tạp của một thuật toán tốt nhất có thể tìm được để giải bài toán (hay tính hàm) đó. Một bài toán được cho bởi: • Một tập các dữ liệu vào Y • Một câu hỏi dạng R(I)? với I ∈ Y, lời giải bài toán là đúng hay không Ví dụ: • Bài toán đồng dư bậc hai o Dữ liệu: Các số nguyên dương a,b,c o Câu hỏi: Có hay không số x < c sao cho x2 ≡ a mod b ? • Bài toán hợp số o Dữ liệu: Số nguyên dương N o Câu hỏi: Có hay không hai số m,n > 1 sao cho N = m× n ? 2.2.5 Các lớp phức tạp Ta định nghĩa P là lớp các bài toán có độ phức tạp thời gian là đa thức tức l ớp các bài toán mà đối với chúng có thuật toán giải bài toán đó trong thời gian đa thức. Một lớp quan trọng các bài toán đã được nghiên cứu nhiều là lớp NP, tức các bài toán mà đối với chúng có thuật toán không đơn định để giải trong thời gian đa thức. Thuật toán không đơn định là một mô hình tính toán trừu tượng, đ ược giả đ ịnh là sau mỗi bước có thể có một số hữu hạn bước được lựa chọn đồng thời tiếp sau. Nhiều bài toán được chứng tỏ là thuộc lớp NP, nhưng chưa ai chứng minh được là chúng thuộc lớp P hay không. Và một vấn đề cho đến nay vẫn còn mở, chưa có lời giải là: NP = P ? Một cách trực giác, lớp NP bao gồm các bài toán khó hơn phức tạp hơn các bài toán thuộc lớp P, nhưng điều có vẻ hiển nhiên trực giác đó vẫn chưa được chứng minh hay bác bỏ. Giả sử NP ≠ P, thì trong NP có một lớp con các bài toán được gọi là NP_đầy đủ , đó là những bài toán mà bản thân thuộc lớp NP, và mọi bài toán bất kỳ thuộc l ớp NP đều có thể qui dẫn về bài toán đó bằng một hàm tính được trong thời gian đa thức. Cho đến nay, người ta đã chứng minh được hàng trăm bài toán thuộc nhiều lĩnh vực khác nhau là NP_đầy đủ. Bài toán đồng dư bậc hai kể trên là NP_đầy đủ, bài toán hợp số không là NP_đầy đủ, nhưng chưa tìm được một thuật toán làm việc trong thời gian đa thức giải nó. Trang 7 GV. Lê Đắc Nhường
2.3 Hàm một phía và hàm cửa sập một phía Hàm f(x) được gọi là hàm một phía, nếu tính y = f(x) là dễ, nhưng việc tính ngược x=f (y) là rất khó. Có thể hiểu “dễ” là tính được trong thời gian đa thức (với đa th ức -1 bậc thấp), và “khó” là không tính được trong thời gian đa thức. Ví dụ: Hàm f(x) = gx (mod p) (p là số nguyên tố, g là phần tử nguyên thủy theo mođun p) là hàm một phía. Vì biết x tính f(x) là khá đơn giản, nhưng biết f(x) để tính x thì với các thuật toán đã biết hiện nay đòi hỏi một khối lượng tính toán cỡ O(exp(lnp lnlnp)112) phép tính (nếu p là số nguyên tố cỡ 200 chữ số thập phân, thì khối lượng tính toán trên đòi hỏi một máy tính 1 tỷ phép tính/giây làm việc không nghỉ trong khoảng 3000 năm) Hàm f(x) được gọi là hàm cửa sập một phía, nếu tính y = f(x) là dễ, tính x = f-1(y) là rất khó, nhưng có cửa sập z để tính x = fz-1(y) là dễ Ví dụ: Cho n = p× q là tích của hai số nguyên tố lớn, a là số nguyên, hàm f(x)=xa(mod n) là hàm cửa sập một phía, nếu chỉ biết n và a thì tính x = f -1(y) là rất khó, nhưng nếu biết cửa sập, chẳng hạn hai thừa số của n, thì s ẽ tính đ ược f-1(y) khá dễ. Trên đây là hai thí dụ điển hình, và cũng là hai trường hợp đ ược s ử dụng r ộng rãi về hàm một phía và hàm cửa sập một phía. Vì đây là những điểm then chốt của lý thuyết mật mã khóa công khai, nên việc tìm kiếm các loại hàm một phía và cửa sập một phía được nghiên cứu rất khẩn trương, và đến nay tuy có đạt được một số kết quả, nhưng việc tìm kiếm vẫn tiếp tục, đầy hứng thú nhưng cũng đầy khó khăn. Trang 8 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin CHƯƠNG 3 GIỚI THIỆU VỀ MÃ HÓA 3.1 Các thuật ngữ Hệ mật mã là tập hợp các thuật toán và các thủ tục kết hợp để che dấu thông tin cũng như làm rõ nó. Mật mã học nghiên cứu mật mã bởi các nhà mật mã học, người viết mật mã và các nhà phân tích mã. Mã hoá là quá trình chuyển thông tin có thể đọc gọi là bản rõ thành thông tin không thể đọc gọi là bản mã. Giải mã là quá trình chuyển ngược lại thông tin được mã hoá thành bản rõ. Thuật toán mã hoá là các thủ tục tính toán sử dụng để che dấu và làm rõ thông tin. Thuật toán càng phức tạp thì bản mã càng an toàn. Một khoá là một giá trị làm cho thuật toán mã hoá chạy theo cách riêng biệt và sinh ra bản rõ riêng biệt tuỳ theo khoá. Khoá càng lớn thì bản mã kết quả càng an toàn. Kích thước của khoá được đo bằng bit. Phạm vi các giá trị có thể có của khoá đ ược gọi là không gian khoá. Phân tích mã là quá trình hay nghệ thuật phân tích hệ mật mã hoặc kiểm tra tính toàn vẹn của nó hoặc phá nó vì những lý do bí mật. Một kẻ tấn công là một người (hay hệ thống) thực hiện phân tích mã để làm hại hệ thống. Những kẻ tấn công là những kẻ thọc mũi vào chuyện người khác, các tay hacker, những kẻ nghe trộm hay những các tên đáng ngờ khác, và họ làm những việc thường gọi là cracking 3.2 Định nghĩa hệ mật mã. Hệ mật mã: là một hệ bao gồm 5 thành phần (P, C, K, E, D) thoả mãn các tính chất sau P ( Plaintext ) là tập hợp hữu hạn các bản rõ có thể. C ( Ciphertext ) là tập hợp hữu hạn các bản mã có thể. K ( Key ) là tập hợp các bản khoá có thể. E ( Encrytion ) là tập hợp các qui tắc mã hoá có thể. D ( Decrytion ) là tập hợp các qui tắc giải mã có thể. Chúng ta đã biết một thông báo thường được tổ chức dưới dạng bản rõ. Người gửi sẽ làm nhiệm vụ mã hoá bản rõ, kết quả thu được gọi là bản mã. Bản mã này được gửi đi trên một đường truyền tới người nhận sau khi nhận được bản mã người nhận giải mã nó để tìm hiểu nội dung. Dễ dàng thấy được công việc trên khi sử dụng định nghĩa hệ mật mã : EK( P) = C và DK( C ) = P 3.3 Những yêu cầu đối với hệ mật mã Cung cấp một mức cao về độ tin cậy, tính toàn vẹn, sự không từ chối và sự xác thực. Trang 9 GV. Lê Đắc Nhường
 Độ tin cậy: cung cấp sự bí mật cho các thông báo và dữ liệu được lưu bằng việc che dấu thông tin sử dụng các kỹ thuật mã hóa.  Tính toàn vẹn: cung cấp sự bảo đảm với tất cả các bên rằng thông báo còn lại không thay đổi từ khi tạo ra cho đến khi người nhận mở nó.  Tính không từ chối: có thể cung cấp một cách xác nhận rằng tài liệu đã đến từ ai đó ngay cả khi họ cố gắng từ chối nó.  Tính xác thực: cung cấp hai dịch vụ: đầu tiên là nhận dạng nguồn gốc của một thông báo và cung cấp một vài sự bảo đảm rằng nó là đúng sự thực. Thứ hai là kiểm tra đặc tính của người đang logon một hệ thống và sau đó tiếp tục kiểm tra đặc tính của họ trong trường hợp ai đó cố gắng đột nhiên kết nối và giả dạng là người sử dụng 3.4 Các phương pháp mã hoá 3.4.1 Mã hoá đối xứng khoá bí mật Định nghĩa: Thuật toán đối xứng hay còn gọi thuật toán mã hoá cổ điển là thuật toán mà tại đó khoá mã hoá có thể tính toán ra được từ khoá giải mã. Trong rất nhiều trường hợp, khoá mã hoá và khoá giải mã là giống nhau. Thuật toán này còn có nhiều tên gọi khác như thuật toán khoá bí mật, thuật toán khoá đơn giản, thuật toán một khoá. Thuật toán này yêu cầu người gửi và người nhận phải thoả thuận một khoá trước khi thông báo được gửi đi, và khoá này phải được cất giữ bí mật. Độ an toàn của thuật toán này vẫn phụ thuộc và khoá, nếu để lộ ra khoá này nghĩa là bất kỳ người nào cũng có thể mã hoá và giải mã thông báo trong hệ thống mã hoá. Sự mã hoá và giải mã của thuật toán đối xứng biểu thị bởi : EK( P ) = C và DK( C ) = P Trong hình vẽ trên thì : K1có thể trùng K2, hoặc K1 có thể tính toán từ K2, hoặc K2 có thể tính toán từ K1. Nơi ứng dụng 3.4.1.1 Sử dụng trong môi trường mà khoá đơn dễ dàng được chuyển như là trong cùng một văn phòng. Cũng dùng để mã hoá thông tin để lưu trữ trên đĩa. Các vấn đề đối với phương pháp mã hoá này 3.4.1.2 Các phương mã hoá cổ điển đòi hỏi người mã hoá và người giải mã phải cùng chung một khoá. Khi đó khoá phải được giữ bí mật tuyệt đối, do vậy ta dễ dàng xác định một khoá nếu biết khoá kia. Hệ mã hoá đối xứng không bảo vệ được sự an toàn nếu có xác suất cao khoá người gửi bị lộ. Trong hệ khoá phải được gửi đi trên kênh an toàn nếu kẻ đ ịch t ấn công trên kênh này có thể phát hiện ra khoá. Vấn đề quản lý và phân phối khoá là khó khăn và phức tạp khi sử dụng hệ mã hoá cổ điển. Người gửi và người nhận luôn luôn thông nhất với nhau về vấn đề khoá. Việc thay đổi khoá là rất khó và dễ bị lộ. Trang 10 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin Khuynh hướng cung cấp khoá dài mà nó phải được thay đổi thường xuyên cho mọi người trong khi vẫn duy trì cả tính an toàn lẫn hiệu quả chi phí sẽ c ản tr ở r ất nhi ều tới việc phát triển hệ mật mã cổ điển. 3.4.2 Mã hoá phi đối xứng khoá công khai Định nghĩa: Vào những năm 1970 Diffie và Hellman đã phát minh ra một hệ mã hoá mới được gọi là hệ mã hoá công khai hay hệ mã hoá phi đối xứng. Thuật toán mã hoá công khai là khác biệt so với thuật toán đối xứng. Chúng đ ược thiết kế sao cho khoá sử dụng vào việc mã hoá là khác so với khoá giải mã. Hơn nữa khoá giải mã không thể tính toán được từ khoá mã hoá. Chúng được gọi với tên h ệ thống mã hoá công khai bởi vì khoá để mã hoá có thể công khai, một người bất kỳ có thể sử dụng khoá công khai để mã hoá thông báo, nhưng chỉ một vài người có đúng khoá giải mã thì mới có khả năng giải mã. Trong nhiều hệ thống, khoá mã hoá gọi là khoá công khai (public key), khoá giải mã thường được gọi là khoá riêng (private key). Trong hình vẽ trên thì : K1 không thể trùng K2, hoặc K2 không thể tính toán từ K1. Đặc trưng nổi bật của hệ mã hoá công khai là cả khoá công khai (public key) và bản tin mã hoá (ciphertext) đều có thể gửi đi trên một kênh thông tin không an toàn. Nơi ứng dụng 3.4.2.1 Sử dụng chủ yếu trên các mạng công khai như Internet khi mà khoá chuyển tương đối khó khăn. Điều kiện hệ mã hóa khóa công khai 3.4.2.2 Diffie và Hellman đã xác đinh rõ các điều kiện của một hệ mã hoá công khai như sau: 1. Việc tính toán ra cặp khoá công khai KB và bí mật kB dựa trên cơ sở các điều kiện ban đầu phải được thực hiện một cách dễ dàng, nghĩa là thực hiện trong thời gian đa thức. 2. Người gửi A có được khoá công khai của người nhận B và có bản tin P cần gửi đi thì có thể dễ dàng tạo ra được bản mã C. C = EKB (P) = EB (P) Công việc này cũng trong thời gian đa thức. 3. Người nhận B khi nhận được bản tin mã hóa C với khoá bí mật k B thì có thể giải mã bản tin trong thời gian đa thức. P = DkB (C) = DB[EB(M)] 4. Nếu kẻ địch biết khoá công khai KB cố gắng tính toán khoá bí mật thì khi đó chúng phải đương đầu với trường hợp nan giải, trường hợp này đòi hỏi nhiều yêu cầu không khả thi về thời gian. 5. Nếu kẻ địch biết được cặp (KB,C) và cố gắng tính toán ra bản rõ P thì giải quyết bài toán khó với số phép thử là vô cùng lớn, do đó không khả thi. Trang 11 GV. Lê Đắc Nhường
3.5 Các hệ mã hóa đơn giản Đối tượng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh không mật cho hai người sử dụng (tạm gọi là Alice và Bob) sao cho đối phương (Oscar) không thể hiểu được thông tin được truyền đi. Kênh này có thể là một đường dây điện thoại hoặc một mạng máy tính. Thông tin mà Alice muốn gửi cho Bob (bản rõ) có thể là một văn bản tiếng Anh, các dữ liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tuỳ ý. Alice sẽ mã hoá bản rõ bằng một kháo đã được xacs định trước và gửi bản mã kết quả trên kênh. Oscar có bản mã thu trộm được trên kênh song không thể xác định nội dung của bản rõ, nhưng Bob (người đã biết khoá mã) có thể giải mã và thu được bản rõ. Ta sẽ mô tả hình thức hoá nội dung bằng cách dung khái niệm toán học như sau: Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) thoả mãn các điều kiện sau: P là một tập hữu hạn các bản rõ có thể. C là một tập hữu hạn các bản mã có thể. K (không gian khoá) là tập hữu hạn các khoá có thể. Đối với mỗi k∈ K có một quy tắc mã ek: P → C và một quy tắcv giải mã tương ứng dk ∈ D. Mỗi ek: P → C và dk: C → P là những hàm mà: dk(ek (x)) = x với mọi bản rõ x ∈ P. Trong tính chất 4 là tính chất chủ yếu ở đây. Nội dung của nó là nếu một bản rõ x được mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng dk thì ta phải thu được bản rõ ban đầu x. Alice và Bob sẽ áp dụng thủ tục sau dùng hệ mật khoá riêng. Trước tiên họ chọn một khoá ngẫu nhiên K ∈ K . Điều này được thực hiện khi họ ở cùng một chỗ và không bị Oscar theo dõi hoặc khi họ có một kênh mật trong trường hợp họ ở xa nhau. Sau đó giả sử Alice muốn gửi một thông baó cho Bob trên một kênh không mật và ta xem thông báo này là một chuỗi: x = x1,x2 ,. . .,xn với số nguyên n ≥ 1 nào đó. Ở đây mỗi ký hiệu của mỗi bản rõ xi ∈ P , 1 ≤ i ≤ n. Mỗi xi sẽ được mã hoá bằng quy tắc mã ek với khoá K xác định trước đó. Bởi vậy Alice sẽ tính yi = ek(xi), 1 ≤ i ≤ n và chuỗi bản mã nhận được: y = y1,y2 ,. . .,yn sẽ được gửi trên kênh. Khi Bob nhận đươc y1,y2 ,. . .,yn anh ta sẽ giải mã bằng hàm giải mã dk và thu được bản rõ gốc x1,x2 ,. . .,xn. Hình dưới là một ví dụ về một kênh liên lạc Hình 3.3. Kênh liên lạc Rõ ràng là trong trường hợp này hàm mã hoá phải là hàm đơn ánh ( tức là ánh xạ 1- 1), nếu không việc giải mã sẽ không thực hiện được một cách tường minh. Ví dụ y = ek(x1) = ek(x2) trong đó x1 ≠ x2 , thì Bob sẽ không có cách nào để biết liệu sẽ phải giải mã thành x1 hay x2 . Chú ý rằng nếu P = C thì mỗi hàm mã hoá là một phép hoán vị, tức là nếu tập Trang 12 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin các bản mã và tập các bản rõ là đồng nhất thì mỗi một hàm mã sẽ là một sự sắp xếp lại (hay hoán vị ) các phần tử của tập này. Do các ví dụ của chúng ta xét trên tập dữ liệu là bảng chữ cái nên chúng ta coi bảng chữ cãi tiếng anh là tập hợp gồm 26 giá trị như bảng bên dưới. ABCDEF GHI J KLM 0 1 2 3 4 5 6 7 8 9 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 3.5.1 Mã dịch vòng Mã dịch vòng được xác định trên Z26 (do có 26 chữ cái trên bảng chữ cái tiếng Anh) mặc dù có thể xác định nó trên Zm với modulus m tuỳ ý. Dễ dàng thấy rằng, MDV sẽ tạo nên một hệ mật như đã xác định ở trên, tức là dK (eK(x)) = x với mọi x∈ Z26 . Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) Giả sử P = C = K = Z26 với 0 ≤ k ≤ 25 , định nghĩa: eK(x) = x +K mod 26 dK(x) = y -K mod 26 (x,y ∈ Z26) và Nhận xét: Trong trường hợp K = 3, hệ mật thường được gọi là mã Caesar đã từng được Julius Caesar sử dụng. Ta sẽ sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh thông thường bằng cách thiết lập sự tương ứnggiữa các kí tự và các thặng dư theo modulo 26 như sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25. Ví dụ 1: Giả sử khoá cho MDV là K = 11 và bản rõ là: wewillmeetatmidnight Trước tiên biến đổi bản rõ thành dãy các số nguyên nhờ dùng phép tương ứng trên. Ta có: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu được bản mã sau: HPHTWWXPPELEXTOYTRSE Để giả mã bản mã này, trước tiên, Bob sẽ biến đổi bản mã thành dãy các số nguyên rồi trừ đi giá trịcho 11 ( rút gọn theo modulo 26) và cuối cùng biến đổi lại dãy nàythành các ký tự. Nhận xét: Trong ví dụ trên , ta đã dùng các chữ in hoa cho bản mã, các chữ thường cho bản rõ để tiện phân biệt. Quy tắc này còn tiếp tục sử dụng sau này. Nếu một hệ mật có thể sử dụng được trong thực tế thì nó phảo thoả mãn một số tính chất nhất định. Ngay sau đây sẽ nêu ra hai trong số đó: Trang 13 GV. Lê Đắc Nhường
1. Mỗi hàm mã hoá eK và mỗi hàm giải mã dK phải có khả năng tính toán được một cách hiệu quả. 2. Đối phương dựa trên xâu bản mã phải không có khả năng xác đ ịnh khoá K đã dùng hoặc không có khả năng xác định được xâu bản rõ x. Tính chất thứ hai xác định (theo cách khá mập mờ) ý tưởng ý t ưởng "bảo mật". Quá trình thử tính khoá K (khi đã biết bản mã y) được gọi là mã thám (sau này khái niệm này sẽ đực làm chính xác hơn). Cần chú ý rằng, nếu Oscar có thể xác định được K thì anh ta có thể giải mã được y như Bob bằng cách dùng dK. Bởi vậy, vi ệc xác định K chí ít cũng khó như việc xác định bản rõ x. Nhận xét: MDV (theo modulo 26) là không an toàn vì nó có thể bị thám theo phương pháp vét cạn. Do chỉ có 26 khoá nên dễ dàng thử mọi khoá dK có thể cho t ới khi nhận được bản rõ có nghĩa. Điều này được minh hoạ theo ví dụ sau: Ví du 2: Cho bản mã JBCRCLQRWCRVNBJENBWRWN ta sẽ thử liên tiếp các khoá giải mã d0 ,d1 .. . và y thu được: jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk jxynyhmnsynrjexfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvodyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwfojof astitchintimesavesnine Tới đây ta đã xác định được bản rõ và dừng lại. Khoá tương ứng K = 9. Trung bình có thể tính được bản rõ sau khi thử 26/2 = 13 quy tắc giải mã. Như đã chỉ ra trong ví dụ trên , điều kiện để một hệ mật an toàn là phép tìm khoá vét cạn phải không thể thực hiện được; tức không gian khoá phải rất lớn. Tuy nhiên, một không gian khoá lớn vẫn chưa đủ đảm bảo độ mật. 3.5.2 Mã thay thế Một hệ mật nổi tiếng khác là hệ mã thay thế. Hệ mật này đã được sử dụng hàng trăm năm. Trò chơi đố chữ "cryptogram" trong các bài báo là những ví dụ về MTT. Trên thực tế MTT có thể lấy cả P và C đều là bộ chữ cái tiếng anh, gồm 26 chữ cái. Ta dùng Z26 trong MDV vì các phép mã và giải mã đều là các phép toán đ ại s ố. Tuy nhiên, trong MTT, thích hợp hơn là xem phép mã và giải mã như các hoán vị của các kí tự. Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) Cho P =C = Z26 . K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . . ,25 Với mỗi phép hoán vị π ∈K , ta định nghĩa: Trang 14 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin eπ(x) = π(x) dπ(y) = π -1(y) và trong đó π -1 là hoán vị ngược của π. Sau đây là một ví dụ về phép hoán vị ngẫu nhiên π tạo nên một hàm mã hoá (cũng như trước, các kí hiệu của bản rõ được viết bằng chữ thường còn các kí hiệu của bản mã là chữ in hoa). a b c d e f g h i j k l M X N Y A H P O G Z Q W B T n o p q r s t u v w x y Z S F L R C V M U E K J D I Như vậy, eπ (a) = X, eπ (b) = N,. . . . Hàm giải mã là phép hoán vị ngược. Điều này được thực hiện bằng cách viết hàng thứ hai lên trước rồi sắp xếp theo thứ tự chữ cái. Ta nhận được: A B C D E F G H I J K L M d l r y v o h e z x w p T N O P Q R S T U V W X Y Z b g f j q n m u s k a c I Bởi vậy dπ (A) = d, dπ(B) = 1, . . . Bài tập: giải mã bản mã sau bằng cách dùng hàm giải mã đơn giản: M G Z V Y Z L G H C M H J M Y X S S E M N H A H Y C D L M H A. Mỗĩ khoá của MTT là một phép hoán vị của 26 kí tự. Số các hoán vị này là 26!, lớn hơn 4 × 10 26 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện được, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thấy rằng MTT có thể dễ dàng bị thám bằng các phương pháp khác. 3.5.3 Mã Apphin MDV là một trường hợp đặc biệt của MTT chỉ gồm 26 trong số 26! các hoán vị có thể của 26 phần tử. Một trường hợp đặc biệt khác của MTT là mã Affine được mô tả dưới đây. trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng: e(x) = ax + b mod 26, a,b ∈ Z26 . Các hàm này được gọi là các hàm Affine (chú ý rằng khi a = 1, ta có MDV). Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine phải là đơn ánh. Nói cách khác, với bất kỳ y ∈ Z26, ta muốn có đồng nhất thức sau: ax + b ≡ y (mod 26) phải có nghiệm x duy nhất. Đồng dư thức này tương đương với: ax ≡ y-b (mod 26) Vì y thay đổi trên Z26 nên y-b cũng thay đổi trên Z26 . Bởi vậy, ta chỉ cần nghiên cứu phương trình đồng dư: ax ≡ y (mod 26) (y∈ Z26 ). Ta biết rằng, phương trình này có một nghiệm duy nhất đối với mỗi y khi và chỉ khi UCLN(a,26) = 1 (ở đây hàm UCLN là ước chung lớn nhất của các biến của nó). Trước tiên ta giả sử rằng, UCLN(a,26) = d > 1. Khi đó, đồng dư thức ax ≡ 0 (mod 26) Trang 15 GV. Lê Đắc Nhường
sẽ có ít nhất hai nghiệm phân biệt trong Z26 là x = 0 và x = 26/d. Trong trường hợp này, e(x) = ax + b mod 26 không phải là một hàm đơn ánh và bởi vậy nó không th ể là hàm mã hoá hợp lệ. Giải thích theo một cách khác như sau: Phép lập mã được cho bởi một hàm apphin dạng: e(x) = ax + b mod 26 Để có được phép giải mã tương ứng, tức là để cho phương trình sau có nghiệm: ax + b = c mod 26 có lời giải đối với x (với bất kỳ c cho trước), theo một định lý số học, điều kiện c ần và đủ là a nguyên tố với 26, tức là UCLN(a,26) = 1. Khi UCLN(a,26)=1 thì có: a-1 Z26 sao cho a.a-1=a-1.a=1 mod 26. và do đó nếu y=ax+b mod 26 thì x=a-1(y-b) mod 26 và ngược lại Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) Cho P = C = Z26 và giả sử P = { (a,b) ∈ Z26 × Z26 : UCLN(a,26) =1 } Với K = (a,b) ∈K , ta định nghĩa: eK(x) = ax +b mod 26 dK(y) = a-1(y-b) mod 26, x,y ∈ Z26 và Ví dụ: Giả sử K = (7,3). Như đã nêu ở trên, 7-1 mod 26 = 15. Hàm mã hoá là eK(x) = 7x+3 Và hàm giải mã tương ứng là: dK(x) = 15(y-3) = 15y -19 Ở đây, tất cả các phép toán đều thực hiện trên Z26. Ta sẽ kiểm tra liệu dK(eK(x)) = x với mọi x Z26 không?. Dùng các tính toán trên Z26 , ta có dK(eK(x)) =dK(7x+3) =15(7x+3)-19 = x +45 - 19 = x. Để minh hoạ, ta hãy mã hoá bản rõ "hot". Trước tiên biến đổi các chữ h, o, t thành các thặng du theo modulo 26. Ta được các số tương ứng là 7, 14 và 19. Bây giờ sẽ mã hoá: 7x7 +3 mod 26 = 52 mod 26 = 0 7 x14 + 3 mod 26 = 101 mod 26 =23 7 x19 +3 mod 26 = 136 mod 26 = 6 Bởi vậy 3 ký hiệu của bản mã là 0, 23 và 6 tương ứng với xâu ký t ự AXG. Việc giải mã sẽ do bạn thực hiện như một bài tập. 3.5.4 Mã Vigenère Trong cả hai hệ MDV và MTT (một khi khoá đã được chọn) mỗi ký t ự s ẽ đ ược ánh xạ vào một ký tự duy nhất. Vì lý do đó, các hệ mật còn được gọi hệ thay thế đơn biểu. Bây giờ ta sẽ trình bày ( trong hùnh 1.5) một hệ mật không phải là bộ ch ữ đ ơn, Trang 16 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin đó là hệ mã Vigenère nổi tiếng. Mật mã này lấy tên của Blaise de Vigenère sống vào thế kỷ XVI. Sử dụng phép tương ứng A ⇔ 0, B ⇔ 1, . . . , Z ⇔ 25 mô tả ở trên, ta có thể gắn cho mỗi khoa K với một chuỗi kí tự có độ dài m được gọi là từ khoá. Mật mã Vigenère sẽ mã hoá đồng thời m kí tự: Mỗi phần tử của bản rõ tương đương với m ký tự. Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) Cho m là một số nguyên dương cố định nào đó. Định nghĩa P = C = K = (Z26)m . Với khoá K = (k1, k2, . . . ,km) ta xác định : eK(x1, x2, . . . ,xm) = (x1+k1, x2+k2, . . . , xm+km) và dK(y1, y2, . . . ,ym) = (y1-k1, y2-k2, . . . , ym-km) trong đó tất cả các phép toán được thực hiện trong Z26 Ví dụ: Giả sử m =6 và từ khoá là CIPHER. Từ khoá này tương ứng với dãy số K=(2,8,15,4,17). Giả sử bản rõ là xâu: thiscryptosystemisnotsecure Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dư theo modulo 26, viết chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau: Bởi vậy, dãy ký tự tương ứng của xâu bản mã sẽ là: VPX Z G IAX IVWPU BTTM J PWI Z ITWZT Để giải mã ta có thể dùng cùng từ khoá nhưng thay cho cộng, ta tr ừ cho nó theo modulo 26. Ta thấy rằng các từ khoá có thể với số độ dài m trong mật mã Vigenère là 26m, bởi vậy, thậm chí với các giá trị m khá nhỏ, phương pháp tìm kiếm vét cạn cũng yêu cầu thời gian khá lớn. Ví dụ, nếu m = 5 thì không gian khoá cũng có kích thước lớn hơn 1,1 × 107 . Lượng khoá này đã đủ lớn để ngăn ngừa việc tìm khoá bằng tay( chứ không phải dùng máy tính). Trong hệ mật Vigenère có từ khoá độ dài m,mỗi ký tự có thể được ánh xạ vào trong m ký tự có thể có (giả sử rằng từ khoá chứa m ký tự phân biệt). Một hệ mật như vậy được gọi là hệ mật thay thế đa biểu (polyalphabetic). Nói chung, việc thám mã hệ thay thế đa biểu sẽ khó khăn hơn so việc thám mã hệ đơn biểu. 3.5.5 Mã HILL Trong phần này sẽ mô tả một hệ mật thay thế đa biểu khác được gọi là mật mã Hill. Mật mã này do Lester S.Hill đưa ra năm 1929. Giả sử m là một số nguyên dương, đặt P = C = (Z26)m . Ý tưởng ở đây là lấy m tổ hợp tuyến tính của m ký tự trong một phần tử của bản rõ để tạo ra m ký tự ở một phần tử của bản mã. Ví dụ nếu m = 2 ta có thể viết một phần tử của bản rõ là x = (x 1,x2) và một phần tử của bản mã là y = (y1,y2). Ở đây, y1cũng như y2 đều là một tổ hợp tuyến tính của x1và x2. Chẳng hạn, có thể lấy y1 = 11x1+ 3x2 y2 = 8x1+ 7x2 Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau Trang 17 GV. Lê Đắc Nhường
Nói chung, có thể lấy một ma trận K kích thước m × m làm khoá. Nếu một phần tử ở hàng i và cột j của K là k i,,j thì có thể viết K = (ki,,j), với x = (x1, x2, . . . ,xm) ∈ P và K ∈K , ta tính y = eK(x) = (y1, y2, . . . ,ym) như sau: Nói một cách khác y = xK. Chúng ta nói rằng bản mã nhận được từ bản rõ nhờ phép biến đổi tuyến tính. Ta sẽ xét xem phải thực hiện giải mã như thế nào, tức là làm thế nào để tính x từ y. Bạn đã làm quen với đại số tuyến tính sẽ thấy rằng phải dùng ma trận nghịch đảo K -1 để giả mã. Bản mã được giải mã bằng công thức y K-1 . Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) Cho m là một số nguyên dương có định. Cho P = C = (Z26 )m và cho K = { các ma trận khả nghịch cấp m × m trên Z26} Với một khoá K ∈K ta xác định eK(x) = xK dK(y) = yK -1 và Tất cả các phép toán được thực hiện trong Z26 Ví dụ: Giả sử có khóa Từ các tính toán trên ta có: Giả sử cần mã hoá bản rõ "July". Ta có hai phần tử của bản rõ đ ể mã hoá: (9,20) (ứng với Ju) và (11,24) (ứng với ly). Ta tính như sau: Và Bởi vậy bản mã của July là DELW. Để giải mã Bob sẽ tính: và Như vậy Bob đã nhận được bản đúng. Cho tới lúc này ta đã chỉ ra rằng có thể thực hiện phép giải mã nếu K có một nghịch đảo. Trên thực tế, để phép giải mã là có thể thực hiện được, điều kiện cần là K phải có nghịch đảo. ( Điều này dễ dàng rút ra từ đại số tuyến tính sơ cấp, tuy nhiên sẽ không chứng minh ở đây). Bởi vậy, chúng ta chỉ quan tâm tới các ma tr ận K kh ả nghich. Tính khả nghịch của một ma trận vuông phụ thuộc vào giá trị đ ịnh thức c ủa nó. Để tránh sự tổng quát hoá không cần thiết, ta chỉ giới hạn trong trường hợp 2× 2. Định nghĩa : Định thức của ma trận A = (a,i j ) cấp 2× 2 là giá trị det A = a1,1 a2,2 - a1,2 a2,1 Một ma trận thức K là có nghịch đảo khi và chỉ khi định thức của nó khác 0. Tuy nhiên, điều quan trọng cần nhớ là ta đang làm việc trên Z 26 . Kết quả tương ứng là ma trận K có nghịch đảo theo modulo 26 khi và chỉ khi UCLN(det K,26) = 1. Định lý: Giả sử A = (ai j) là một ma trận cấp 2 × 2 trên Z26 sao cho: det A = a1,1a2,2 - a1,2 a2,1 có nghịch đảo. Khi đó Trang 18 GV. Lê Đắc Nhường
Trường Đại học Hải Phòng Bài giảng: An toàn thông tin Trở lại ví dụ đã xét ở trên . Trước hết ta có: =(11.7-8.3) mod 26 = 77 - 24 mod 26 = 53 mod 26 =1 Vì 1-1 mod 26 = 1 nên ma trận nghịch đảo là (do theo modulo 26) Đây chính là ma trận đã có ở trên. 3.5.6 Mã hoán vị Tất cả các hệ mật thảo luận ở trên ít nhiều đều xoay quanh phép thay thế: các ký tự của bản rõ được thay thế bằng các ký tự khác trongbản mã. Ý tưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này. MHV (còn được gọi là mã chuyển vị) đã được dùng từ hàng trăm năm nay. Thật ra thì sự phân biệt giữa MHV và MTT đã được Giovani Porta chỉ ra từ 1563. Định nghĩa hình thức cho MHV được nêu ra bên dưới. Không giống như MTT, ở đây không có các phép toán đại số nào cần thực hiện khi mã hoá và giải mã nên thích hợp hơn cả là dùng các ký tự mà không dùng các thặng dư theo modulo 26. Dưới đây là một ví dụ minh hoạ Định nghĩa: Một hệ mật là một bộ 5 (P,C,K,E,D) Cho m là mộ số nguyên dương xác định nào đó. Cho P = C = (Z26 )m và cho K gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá π ( tức là một hoán vị) ta xác định eπ(x1, . . . , xm ) = (xπ(1), . . . , xπ(m)) dπ(x1, . . . , xm ) = (yπ -1(1), . . . , yπ -1(m)) và trong đó π -1 là hoán vị ngược của π Ví dụ: Giả sử m = 6 và khoá là phép hoán vị ( π ) sau: Khi đó phép hoán vị ngược π -1 sẽ tương ứng như trên: Bây giờ giả sử có bản rõ Shesellsseashellsbytheseashore Trước tiên ta nhóm bản rõ thành các nhóm 6 ký tự: shesel | lsseas | hellsb | ythese | ashore Bây giờ mỗi nhóm 6 chữ cái được sắp xếp lại theo phép hoán vị π, ta có: EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS Như vậy bản mã là EESLSH SALSES LSHBLE HSYEET HRAEOS Như vậy bản mã đã được mã theo cách tương tự bằng phép hoán vị đảo π -1. Thực tế mã hoán vị là trường hợp đặc biệt của mật mã Hill. Khi cho phép hoán vị π của tập {1, . . . ,m}, ta có thể xác định một ma trận hoán vị m × m thích hợp Kπ= {ki,j} theo công thức: (ma trận hoán vị là ma trận trong đó mỗi hàng và mỗi cột chỉ có một số "1", còn tất cả các giá trị khác đều là số "0". Ta có thể thu được một ma trận hoán vị từ ma tr ận đơn vị bằng cách hoán vị các hàng hoặc cột). Trang 19 GV. Lê Đắc Nhường
Dễ dàng thấy rằng, phép mã Hill dùng ma trận Kπ trên thực tế tương đương với phép mã hoán vị dùng hoán vị π. Hơn nữa K-1π= Kπ -1 tức ma trận nghịch đảo của Kπ là ma trận hoán vị xác định theo hoán vị π -1. Như vậy, phép giải mã Hill tương đương với phép giải mã hoán vị. Đối với hoán vị π được dung trong ví dụ trên, các ma trận hoán vị kết hợp là: Bạn có thể kiểm tra để thấy rằng, tích của hai ma trận này là một ma trận đơn vị. Trang 20 GV. Lê Đắc Nhường