Bài giảng Truyền và bảo mật thông tin

'92 rằng họ sẽ chế tạo một chíp có 50 ngàn tranzistor có thể mã hoá với tốc độ 1 Gbít/s bằng cách dùng nhịp có tốc độ 250MHz. Giá của chíp này vào khoảng 300$. Truyền và bảo mật thông tin 275 DES trong thực tế „ Tới năm 1991 đã có 45 ứng dụng phần cứng và chương trình cơ sở của DES được Uỷ ban tiêu Chuẩn quốc gia Mỹ (NBS) chấp thuận. „ Một ứng dụng quan trọng của DES là trong giao dịch ngân hàng Mỹ - (ABA) DES được dùng để mã hoá các số định danh cá nhân (PIN) và việc chuyển tài khoản bằng máy thủ quỹ tự động (ATM). DES cũng được Hệ thống chi trả giữa các nhà băng của Ngân hàng hối đoái (CHIPS) dùng để xác thực các giao dụch vào khoản trên 1,5×1012 USA/tuần. DES còn được sử dụng rộng rãi trong các tổ chức chính phủ. Chẳng hạn như bộ năng lượng, Bộ Tư pháp và Hệ thống dự trữ liên bang. Truyền và bảo mật thông tin 276 Double DES và Triple DES „ DES bội hai „ Mã hóa: C = DESK2[DESK1(M)] „ Giải mã: M = DESK1-1[DESK2-1(C)] ¾ Có 256 sự lựa chọn cho khóa K1 và 256 sự lựa chọn cho khóa K2. Bởi vậy có 2112 sự lựa chọn cho cặp khóa (K1, K2) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 70 Truyền và bảo mật thông tin 277 Double DES và Triple DES „ DES bội ba „ Mã hóa: „ Giải mã: ¾ Với TDES việc tìm khóa vét cạn yêu cầu khoảng: 2112 = 5,1923.1023 phép tính TDES, bởi vậy thực tế khó có thể thám mã thành công. ( )[ ]{ }MDESDESDESC 1K12K1K −= ( )[ ]{ }CDESDESDESM 11K2K11K −−= Truyền và bảo mật thông tin 278 „ Nguồn gốc AES (Advanced Encryption Standards) : „ Rõ ràng cần phải thay thế DES, vì có những tấn công về mặt lý thuyết có thể bẻ được nó. „ Do đó Viện chuẩn quốc gia Hoa kỳ US NIST ra lời kêu gọi tìm kiếm chuẩn mã mới vào năm 1997. Sau đó có 15 đề cử được chấp nhận vào tháng 6 năm 1998. Và được rút gọn còn 5 ứng cử viên vào tháng 6 năm 1999. Đến tháng 10 năm 2000, mã Rijndael được chọn làm chuẩn mã nâng cao và được xuất bản là chuẩn FIPS PUB 197 vào 11/2001. „ Yêu cầu của AES „ Là mã khối đối xứng khoá riêng. „ Kích thước khối dữ liệu 128 bit và độ dài khoá là tùy biến: 128, 192 hoặc 256 bit. „ Chuẩn mã mới phải mạnh và nhanh hơn Triple DES. Mã mới có cơ sở lí thuyết mạnh để thời gian sống của chuẩn khoảng 20-30 năm (cộng thêm thời gian lưu trữ). „ Khi đưa ra thành chuẩn yêu cầu cung cấp chi tiết thiết kế và đặc tả đầy đủ. Đảm bảo rằng chuẩn mã mới cài đặt hiệu quả trên cả C và Java. II.2.2. Các chuẩn mã dữ liệu nâng cao (AES) Truyền và bảo mật thông tin 279 „ Chuẩn mã nâng cao AES – Rijndael: có các đặc trưng sau: „ Có 128/192/256 bit khoá và 128 bit khối dữ liệu. „ Thiết kế để: „ chống lại các tấn công đã biết „ tốc độ nhanh và nén mã trên nhiều CPU „ Đơn giản trong thiết kế Các chuẩn mã dữ liệu nâng cao Truyền và bảo mật thông tin 280 Thảo luận chung về hệ mật mã đối xứng „ Tính an toàn, phụ thuộc vào: „ Không gian khóa phải đủ lớn để xác suất thành công khi tìm kiếm ngẫu nhiên là rất nhỏ „ Với các phép trộn thích hợp các hệ mã đối xứng có thể ra một hệ mã mới có tính an toàn cao „ Vấn đề bảo mật khi truyền khóa cần được xử lý nghiêm túc: „ Sử dụng kênh an toàn „ Sử dụng nghi thức Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 71 Truyền và bảo mật thông tin 281 Thảo luận chung về hệ mật mã đối xứng „ Ví dụ, với các hệ mã giao hoán, có thể sử dụng nghi thức sau, giả sử A cần truyền thồn diệp w cho B, mỗi bên sử dụng hệ mã riêng: „ A gửi eA(w) cho B „ B gửi eB(eA(w)) cho A „ A gửi dA(eB(eA(w))=dA(eA(eB(w))= eB(w) cho B „ B giải mã dB(eBw) = w eA eB A B Truyền và bảo mật thông tin 282 Thảo luận chung về hệ mật mã đối xứng „ Thám mã: „ Phương pháp thám mã tùy thuộc vào từng hệ mã. „ Có thể kết hợp các đặc trưng thống kê và bản rõ „ Về nguyên tắc, có thể bẻ khóa các hệ mã đối xứng với thời gian và phương pháp thích hợp „ Cài đặt: hầu hết có thể cài đặt tương đối dễ với tốc độ thực thi cao Truyền và bảo mật thông tin 283 Chương III. Hệ mã khóa công khai II.1. Tổng quan về các hệ mã khóa công khai II.2. Hệ mật Merkle – Hellman II.3. Hệ mật RSA II.4. Tổng kết Truyền và bảo mật thông tin 284 II.1. Tổng quan về các hệ mã khóa công khai „ Hệ thống bảo mật đối xứng: dễ dàng xác định một khóa khi biết khóa kiaÆ không đảm bảo bảo mật nếu xác suất khóa gửi bị lộ cao. „ Ý tưởng hệ mật mã công khai thuộc về Diffie và Hellman(1975): Việc biết ek không làm lộ dk: người thám mã biết ek (về nguyên tắc có thể biết hàm ngược của ek – tức là dk), tuy nhiên việc tính dk là bất trị, ít ra là đối với hầu hết các khóa. Hàm ek như trên gọi là hàm một phía Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 72 Truyền và bảo mật thông tin 285 II.1. Tổng quan về các hệ mã khóa công khai Mô hình hệ mật mã công khai E D Bộ sinh khóa Khóa bí mật ks p c p Khóa công khai kp Kênh không an toàn Truyền và bảo mật thông tin 286 II.1. Tổng quan về các hệ mã khóa công khai Các điều kiện cho hệ bảo mật không đối xứng: 1. Từ điều kiện ban đầu, việc tính Kp và Ks, là (tại máy nhận B) dễ dàng (khoảng thời gian đa thức) 2. Người gửi A, với khóa công khai Kp và bản thông báo p, có thể dễ dàng tính bản mã: c=Ekp(p) 3. Máy nhận B sử dụng bảng mã c và khóa ks có thể tái tạo bản thông báo: p=Dks(c) cũng với thời gian đa thức Truyền và bảo mật thông tin 287 II.1. Tổng quan về các hệ mã khóa công khai Các điều kiện cho hệ bảo mật không đối xứng: 4. Nếu biết khóa công khai kp , muốn tìm ra khóa bí mật ks hay “điều kiện ban đầu” thì gặp vấn đề khó không thực hiện được 5. Nếu biết kp và bản mã c cũng khó có thể tính ra bản rõ p Truyền và bảo mật thông tin 288 II.1. Hệ mật Merkle – Hellman „ Bài toán xếp ba lô (Knapsack): „ Cho trước các tập các giá trị a1, , an với ai >0 (các vật cần gói), và tổng đích T (khả năng chứa của ba lô). „ Liệu có tồn tại một vector “lựa chọn” V = [v1, , vn], với vi ∈ {0, 1}, trong đó: „ vi = 1 ⇔ ai được chọn cho tổng (hay vật được chọn xếp vào ba lô) „ vi = 0 ⇔ ai không được chọn cho tổng (hay vật không được chọn xếp vào ba lô) sao cho: ∑ = =∗ n i ii Tva 1 )( Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 73 Truyền và bảo mật thông tin 289 II.2. Hệ mật Merkle – Hellman „ Giới thiệu về các ba lô của Merkle – Hellman „ Ý tưởng chính đằng sau sơ đồ ba lô Merkle – Hellman là để mã một thông báo nhị phân như một lời giải cho bài toán ba lô „ Ba lô được biểu diễn như một vecto các số hạng nguyên, trong đó thứ tự của các số hạng là rất quan trọng. „ Thực sự có 2 ba lô, một “ba lô dễ” và một “ba lô khó” Truyền và bảo mật thông tin 290 II.2. Hệ mật Merkle – Hellman „ Chi tiết về phương pháp Merkle – Hellman „ Bài toán ba lô tổng quát: „ Cho tập giá trị a1, a2, , an và một tổng T. Tính giá trị vi để cho: T = v1a1 + v2a2 + + vnan với vi ∈ {0,1} Truyền và bảo mật thông tin 291 II.2. Hệ mật Merkle – Hellman „ Ví dụ: T = 53, dãy số nguyên (17, 38, 73, 4, 11, 1) „ Loại 73; „ Thử 17, tổng mới (53 – 17) = 36. Loại 38, nhưng 4+11+1<36. Kết luận 17 không là số hạng trong lời giải „ Thử 38, tổng mới (53 – 38) = 15. Thấy tổng các số hạng còn lại là 4+11=15. Vậy lời giải là 38 + 4 + 11. Truyền và bảo mật thông tin 292 II.2. Hệ mật Merkle – Hellman „ Lời giải của bài toán được tiến hành theo thứ tự, ta xét mỗi số nguyên có thể góp phần vào tổng và đã rút gọn bài toán tương ứng. „ Khi một lời giải không đưa ra tổng mong muốn, ta quay lại, loại bỏ các phỏng đoán gần và thử lần lượt. „ Với dãy nhiều số nguyên, rất khó tìm lời giải, đặc biệt khi tất cả chúng đều lớn như nhau đến mức ta không thể loại trực tiếp được số nào. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 74 Truyền và bảo mật thông tin 293 II.2. Hệ mật Merkle – Hellman „ Các ba lô siêu tăng: „ Giả sử bài toán có thêm một hạn chế phụ: Các số nguyên của S phải lập thành một dãy siêu tăng, nghĩa là một số nguyên phải lớn hơn tổng của tất cả các số đứng trước nó. Khi đó mỗi số nguyên ak sẽ có dạng: „ Ví dụ: {1, 4, 11, 17, 38, 73} là một dãy siêu tăng ∑− = > 1 1 k j jk aa Truyền và bảo mật thông tin 294 II.2. Hệ mật Merkle – Hellman „ Nếu ta hạn chế bài toán ba lô thành các dãy siêu tăng, ta có thể dễ dàng nói một số hạng có trong tổng không. „ Nếu tổng nằm giữa ak và ak+1 thì nó phải bao hàm ak như một số hạng. Ngược lại nếu tổng nhỏ hơn ak thì nó không thể bao hàm ak như một số hạng. Truyền và bảo mật thông tin 295 II.2. Hệ mật Merkle – Hellman „ Ví dụ: cho dãy {1, 4, 11, 17, 38, 73}. Giải bài toán với các tổng đích T = 96, T = 95 Truyền và bảo mật thông tin 296 II.2. Hệ mật Merkle – Hellman „ Kĩ thuật mã hóa: „ Các nguyên tắc của số học modulo: „ Trong số học thông thường, việc cộng hay nhân một dãy siêu tăng vẫn duy trì bản chất siêu tăng của nó, nên kết quả vẫn là một dãy siêu tăng. „ Trong số học modulo n, tính chất siêu tăng của một dãy có thể bị phá. „ Với những kết quả rút ra từ số học modulo. Diffie Hellman đã tìm ra cách phá bản chất siêu tăng của dãy số nguyên, bằng cách nhân tất cả các số nguyên với một hằng số w và lấy kết quả mod n, trong đó gcd(n, w) = 1. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 75 Truyền và bảo mật thông tin 297 II.2. Hệ mật Merkle – Hellman „ Biến đổi một ba lô siêu tăng: „ Để thực hiện thuật toán mã hóa Merkle – Hellman, ta cần một ba lô siêu tăng mà có thể biến đổi thành một ba lô khó. Cách làm như sau: „ Chọn số nguyên ban đầu.Chọn số nguyên thứ 2 lớn hơn số nguyên ban đầu.Chọn số nguyên thứ 3 lớn hơn tổng của 2 số đầu. „ Tiếp tục quá trình này bằng cách chọn các số nguyên mới lớn hơn tổng của tất cả các số nguyên đã chọn. • Dãy siêu tăng vừa được chọn được gọi là “ba lô dễ”. •Thể hiện bất kì của bài toán ba lô được lập từ ba lô đó có một lời giải rất dễ tìm! Truyền và bảo mật thông tin 298 II.2. Hệ mật Merkle – Hellman „ Thuật toán tạo khóa: „ Sau khi chọn một ba lô dễ là dãy siêu tăng [M1, M2, , Mn] và một modulo M: M > 2* Mn „ Chọn một số nhân W (1 ≤W ≤ M – 1) sao cho UCLN(W, M) = 1. „ Chọn một phép hoán vị ngẫu nhiên π của các số nguyên {1, 2, , n} „ Tính các giá trị ai = W*Mπ(i) mod M, với i = 1, 2, , n. Khi đó [a1, a2, , an] là một “ba lô khó” „ Ví dụ: „ Với ba lô siêu tăng [1, 2, 4, 9], W = 15, M =17. Ta thu được dãy [15, 13, 9, 16] „ Khi đó: „ Khóa công khai là tập các số [a1, a2, , an] „ Khóa bí mật là (π, M, W,(M1, , Mn)) „ Ta sẽ dùng cả hai ba lô khó và dễ trong phép mã hóa. Truyền và bảo mật thông tin 299 II.2. Hệ mật Merkle – Hellman „ Thuật toán mã công khai Merkle – Hellman: „ Mã hóa: „ Nhận khóa công khai của bên nhận A là [a1, ,an] „ Biểu thị bản tin m như một chuỗi nhị phân có độ dài n. Nghĩa là ta chia thông báo m thành các khối n bit. „ Tính số nguyên c = m1a1 + + mnan „ Gửi bản mã c cho bên nhận A. Truyền và bảo mật thông tin 300 II.2. Hệ mật Merkle – Hellman „ Giải mã: „ Tính d = W-1c mod M „ Sử dụng thuật giải xếp ba lô trong trường hợp dãy siêu tăng để tìm các số nguyên r1, r2, , rn, ri ∈ {0, 1} sao cho: d = r1M1 + r2M2 + + rnMn „ Các bit của bản rõ là mi = rπ(i), với i = 1, 2, , n „ Chứng minh? <M Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 76 Truyền và bảo mật thông tin 301 II.2. Hệ mật Merkle – Hellman Truyền và bảo mật thông tin 302 II.2. Hệ mật Merkle – Hellman „ Ví dụ: „ Cho n = 6, dãy siêu tăng (12, 17, 33, 74, 157, 316), M = 737, W = 635, thỏa mãn UCLN(W, M) = 1. „ Phép hoán vị π của {1, 2, 3, 4, 5, 6} được xác định như sau: π(1) = 3, π(2) = 6, π(3) = 1, π(4) = 2, π(5) = 5, π(6) = 4 „ Thực hiện mã hóa bản tin m = 101101, và thực hiện giải mã ngược lại từ bản mã vừa thu được? Truyền và bảo mật thông tin 303 II.3. Hệ mật Merkle – Hellman „ Tính ai = WMπ(i) mod M, khi đó ta thu được dãy khóa công khai (319, 196, 250, 477, 200, 559) „ Khóa bí mật (π, M, W(12, 17, 33, 74, 157, 316)) „ Mã hóa: „ Để mã bản tin ta tính: c = 319*1 + 196*0 + 250*1 + 477*1 + 200*0 + 559*1 = 1605 „ Gửi c cho bên nhận Truyền và bảo mật thông tin 304 II.3. Hệ mật Merkle – Hellman „ Giải mã: „ Tính W-1 mod M = 635-1 mod 737 = 513 „ Tính W-1 c mod M = 513*1605 mod 737 = 136. „ Giải bài toán xếp ba lô trong trường hợp dãy siêu tăng: 136 = 12r1 + 17r2 + 33r3 + 74r4 + 157r5 + 316r6 „ Ta nhận được: 136 = 12 + 17 + 33 + 74 „ Bởi vậy r1 = r2 = r3 = r4 = 1; r5 = r6 = 0 „ Sử dụng phép hoán vị π, ta sẽ tìm được các bit của bản rõ: m1 = r3 = 1, m2 = r6 = 0, m3 = r1 = 1, m4 = r5 = 1, m5 = r5 = 0, m6 = r4 = 1. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 77 Truyền và bảo mật thông tin 305 II.2. Hệ mật Merkle – Hellman „ Thám mã: „ Thông thường ta thường chọn giá trị của M từ 100 đến 200 chữ số, và mỗi số hạng Mi của ba lô dễ dài khoảng từ 200 – 400 chữ số. Chính xác hơn các Mi được chọn như sau: „ 1 ≤ M1 < 2200 „ 2200 ≤ M2 < 2201 „ 2201 ≤ M3 < 2202 „ „ Như vậy có xấp xỉ 2200 lựa chọn cho mỗi Mi. „ Có thể dùng dãy các số ngẫu nhiên để tạo một ba lô dễ, tạo dãy n số ngẫu nhiêu r1, , rn. Mỗi ri phải trong khoảng từ 0 đến 2200. Khi đó mỗi giá trị Mi được tính như sau: „ Mi = 2200+i+1 + ri, với i = 1, 2, , m Truyền và bảo mật thông tin 306 II.2. Hệ mật Merkle – Hellman „ Với các số hạng lớn như vậy, không thể thử tất cả các giá trị có thể có của Mi khi biết khóa công khai (a1, , an) và bản mã c. „ Ngay cả khi giả thiết một máy có thể thực hiện một phép tính trên một micro giây thì cũng mất 1047 năm để thử một trong 2200 lựa chọn cho mỗi của Mi. Một máy song song cực lớn với 1000 hay thậm chí 1.000.000 phần tử song song thì cũng không đủ để làm yếu phép mã! „ Phương pháp Merkle – Hellman dường như rất an toàn. Với các giá trị lớn thích hợp cho M, n thì các cơ hội phá được phương pháp bằng tấn công theo kiểu vét cạn là rất mong manh. Truyền và bảo mật thông tin 307 II.3. Hệ mật RSA „ RSA là mã công khai được sáng tạo bởi Rivest, Shamir & Adleman ở MIT (Trường Đại học Công nghệ Massachusetts) vào năm 1977. „ RSA là mã công khai được biết đến nhiều nhất và sử dụng rộng rãi nhất hiện nay. „ RSA dựa trên các phép toán lũy thừa trong trường hữu hạn các số nguyên theo modulo nguyên tố. Cụ thể, mã hoá hay giải mã là các phép toán luỹ thừa theo modulo số rất lớn. „ Việc thám mã, tức là tìm khoá riêng khi biết khoá công khai, dựa trên bài toán khó là phân tích một số rất lớn đó ra thừa số nguyên tố. Nếu không có thông tin gì, thì ta phải lần lượt kiểm tra tính chia hết của số đó cho tất cả các số nguyên tố nhỏ hơn căn của nó. Đây là việc làm không khả thi! Truyền và bảo mật thông tin 308 II.3. Hệ mật RSA „ Người ta chứng minh được rằng, phép lũy thừa cần O((log n)3) phép toán, nên có thể coi lũy thừa là bài toán dễ. „ Cần chú ý rằng ở đây ta sử dụng các số rất lớn khoảng 1024 bit, tức là cỡ 10350. „ Tính an toàn dựa vào độ khó của bài toán phân tích ra thừa số các số lớn. Bài toán phân tích ra thừa số yêu cầu O(elogn log logn) phép toán, đây là bài toán khó. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 78 Truyền và bảo mật thông tin 309 II.3.1. Một số cơ sở toán học của RSA „ Hàm Ole „ Cho n là một số nguyên dương. Khi thực hiện phép tính đồng dư n của mọi số nguyên khác ta nhận được tập đầy đủ các phần dư có thể có là: 0, 1, 2,, n-1 „ Từ tập trên ta tìm tập rút gọn Zn* bao gồm các số nguyên tố cùng nhau với n „ Φ(n)=|Zn*| Truyền và bảo mật thông tin 310 II.3.1. Một số cơ sở toán học của RSA „ Các tính chất của hàm Φ(n): „ Nếu p là số nguyên tố Ф(p) = p-1 „ Nếu UCLN(m, n) = 1, thì: Ф(m.n) = Ф(m).Ф(n) „ Nếu n = p1e1 pkek là phân tích ra thừa số nguyên tố của n thì: ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −=Φ kppp nn 11...1111)( 21 Truyền và bảo mật thông tin 311 II.3.1. Một số cơ sở toán học của RSA „ Định lý Ferma (Định lý Ferma nhỏ) ap-1 mod p = 1 trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội của p: UCLN(a, p) = 1. „ Hay với mọi số nguyên tố p và số nguyên a không là bội của p, ta luôn có ap = a (mod p) „ Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn p. Truyền và bảo mật thông tin 312 II.3.1. Một số cơ sở toán học của RSA „ Định lý Euler: Nếu UCLN(a,n)=1 Thì aΦ(n) = 1 (mod n) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 79 Truyền và bảo mật thông tin 313 II.3.2 Khởi tạo khoá RSA „ Mỗi người sử dụng tạo một cặp khoá công khai – riêng như sau: „ Chọn ngẫu nhiên 2 số nguyên tố lớn p và q „ Tính số làm modulo của hệ thống: N = p.q „ Tính Ф(N)=(p-1)(q-1) „ Chọn ngẫu nhiên khoá mã e „ Trong đó 1<e< Ф(N) và UCLN(e,Ф(N))=1 „ Tìm khoá giải mã d sao cho e.d=1 (mod Ф(N)) với 0≤d≤ Ф(N) „ Khoá công khai KU={e,N} „ Giữ khoá riêng bí mật KR={d} Truyền và bảo mật thông tin 314 II.3.3. Sử dụng RSA „ Để mã hoá mẩu tin M, người gửi: „ Lấy khoá công khai của người nhận KU={e,N} „ Tính C=Me mod N, trong đó 0≤M<N „ Để giải mã hoá bản mã, người sở hữu nhận: „ Sử dụng khóa riêng KR={d} „ Tính M=Cd mod N „ Lưu ý rằng bản tin M < N, do đó khi cần chia khối bản rõ. Truyền và bảo mật thông tin 315 II.3.4. Cơ sở của RSA „ Theo Định lý Ferma „ ap-1 mod p = 1 với p là SNT, UCLN(a,p)=1 „ Ta có N=p.q „ Ф(N)=(p-1)(q-1) „ e.d≡(1 mod Ф(N))=>e.d=1+k.Ф(N) đối với một giá trị k nào đó. „ Nếu UCLN(M,p) =1 ta có: Med-1 =1(mod p) => Med = M (mod p) , nếu UCLN(M,p) =p ta cũng có Med = M (mod p) =0 (mod p) „ Tương tự: Med = M (mod q) „ Vì p, q là SNT nên Med = M (mod pq)= M (mod N) =M =>Cd mod N =M Truyền và bảo mật thông tin 316 Chú ý (Số mũ vạn năng). „ Số λ=BCNN(p-1,q-1) đôi khi được gọi là số mũ vạn năng của n, có thể được dùng thay cho Φ=(p-1)(q- 1) khi tạo khoá RSA. Cần chú ý rằng là λ ước thực sự của Φ. „ Sử dụng có thể thu được số mũ giải mã d nhỏ hơn (làm cho giải mã nhanh hơn). „ Tuy nhiên, nếu p và q được chọn ngẫu nhiên thì UCLN(p-1,q-1) sẽ khá nhỏ và bởi vậy λ và Φ sẽ là các số có kích thước xấp xỉ. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 80 Truyền và bảo mật thông tin 317 II.3.5. Ví dụ hệ mật RSA „ Ví dụ „ Chọn các số nguyên tố: p=17 & q=11. „ Tính n = pq, n = 17×11=187 „ Tính Ф(n)=(p–1)(q-1)=16×10=160 „ Chọn e : UCLN(e,160)=1; Lấy e=7 „ Xác định d: de=1 mod 160 và d < 160 „ Giá trị cần tìm là d=23, vì 23×7=161= 160+1 „ Khoá công khai KU={7,187} „ Giữ khoá riêng bí mật KR={23} Truyền và bảo mật thông tin 318 II.3.5. Ví dụ hệ mật RSA „ Ví dụ áp dụng mã RSA trên như sau: „ Cho mẩu tin M = 88 (vậy 88<187) „ Mã C = 887 mod 187 = 11 „ Giải mã M = 1123 mod 187 = 88 Truyền và bảo mật thông tin 319 II.3.6. Một số thuật toán ứng dụng trong RSA Truyền và bảo mật thông tin 320 II.3.6. Một số thuật toán ứng dụng trong RSA Tính các nghịch đảo trong ZN „ VÀO : a ∈ ZN „ RA : a-1 (mod N) (nếu tồn tại). „ Dùng thuật toán Euclide mở rộng để tìm các số nguyên x và y sao cho ax+Ny=d trong đó d=UCLN(a,N). „ Nếu d>1 thì a-1 (mod N) không tồn tại. Ngược lại return(x). Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 81 Truyền và bảo mật thông tin 321 II.3.6. Một số thuật toán ứng dụng trong RSA „ Thuật toán nhân và bình phương có lặp để lấy luỹ thừa trong ZN. Truyền và bảo mật thông tin 322 Thuật toán nhân và bình phương có lặp để lấy luỹ thừa trong ZN. Truyền và bảo mật thông tin 323 II.3.6. Một số thuật toán ứng dụng trong RSA „ Kiểm tra tính nguyên tố „ Giả sử cần phải tìm một số nguyên tố rất lớn. Lấy ngẫu nhiên một số đủ lớn, ta cần phải kiểm tra xem số đó có phải là số nguyên tố không? „ Cách 1: Thử bằng phép chia „ Cách 2: sử dụng các phép kiểm tra tính nguyên tố thống kê dựa trên các tính chất: „ Mà mọi số nguyên tố phải thỏa mãn „ Nhưng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn tính chất đó Truyền và bảo mật thông tin 324 II.3.6. Một số thuật toán ứng dụng trong RSA „ Cụ thể là phép kiểm tra dựa trên Định lý Ferma như sau: „ Nếu số n cần kiểm tra tính nguyên tố là số nguyên tố, thì nó sẽ thoã mãn định lý Ferma đối với mọi số a nhỏ hơn nó an-1 mod n = 1. „ Như vậy, lấy ngẫu nhiên số a và kiểm tra xem nó có tính chất trên không. Nếu có thì n có thể là số nguyên tố, nếu cần độ tin cậy lớn hơn, thì ta kiểm tra liên tiếp nhiều lần như vậy với các số ngẫu nhiên a được chọn. Sau mỗi lần qua được phép thử, xác suất để n là số nguyên tố lại tăng lên Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 82 Truyền và bảo mật thông tin 325 II.3.7. Một số thuật toán ứng dụng trong RSA „ Chú ý rằng: „ nếu bi mod n = 1, thì: b2i mod n = (1)2 mod n = 1 và „ nếu bi mod n = n – 1, thì: b2i mod n = (n - 1)2 mod n = (n2 – 2n +1) mod n = 1 Truyền và bảo mật thông tin 326 II.3.6. Một số thuật toán ứng dụng trong RSA „ Kiểm tra số n có là số nguyên tố không, ta chỉ cần xét n là lẻ, khi đó n-1 là chẵn và biểu diễn nó dạng (n–1)= 2k.q „ Khi đó để tính an-1, ta tính aq, sau đó bình phương liên tiếp k lần. Truyền và bảo mật thông tin 327 II.3.6. Một số thuật toán ứng dụng trong RSA „ Thuật toán Miller - Rabin: „ TEST (n) is: 1. Tìm các số nguyên k, q, k > 0, q lẻ, và (n–1)= 2k.q 2. Chọn ngẫu nhiên số nguyên a, 1<a<n–1 3. if aq mod n = 1 then return (“có thể nguyên tố"); 4. for j = 0 to k – 1 do 5. if (a2^j.q mod n = n-1) then return(" có thể nguyên tố ") return (“hợp số") Truyền và bảo mật thông tin 328 II.3.6. Một số thuật toán ứng dụng trong RSA „ Các xem xét về mặt xác suất „ Nếu thuật toán Miller Rabin trả về số “composite” thì số đó chắc chắn không là số nguyên tố, vì khi đó số n và số a < n không thoả mãn định lý Fecma, tức là an-1 mod n ≠ 1. „ Ngược lại số đó có thể là số nguyên tố hoặc giả nguyên tố theo nghĩa nó thoả mãn định lý Fecma với số a < n. Người ta chứng minh được rằng xác suất để số giả nguyên tố đó không là số nguyên tố là là ¼. Suy ra nếu lặp t phép thử với các lựa chọn ngẫu nhiên khác nhau của số a, thì khi đó xác suất để số n sau t phép thử là số nguyên tố là: 1-(1/4)t „ Ví dụ. Sau 10 bước, t = 10, mà số đã cho n đều có thể là nguyên tố, thì xác suất để n là số nguyên tố là 1 – (1/4)10 > 0.99999. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 83 Truyền và bảo mật thông tin 329 II.3.6. Một số thuật toán ứng dụng trong RSA „ Định lí phần dư Trung Hoa Nếu n1, , nk nguyên tố cùng nhau từng đôi một thì hệ sau: Có nghiệm duy nhất theo modulo N = n1nk: „ Với yi=(N/ni)-1 (mod ni) ( ) ( ) ( )kk 22 11 nmodax ........................ nmodax nmodax ≡ ≡ ≡ )(mod)/( 1 NxynNx ii k i i∑ = = Truyền và bảo mật thông tin 330 II.3.6. Một số thuật toán ứng dụng trong RSA „ Có thể triển khai Định lý Trung Hoa theo một số cách như sau: „ 1. Tính toán theo modulo số lớn: „ Để tính A mod M, với M (M= m1m2..mk) khá lớn và A là biểu thức số học nào đó. Trước hết ta cần tính tất cả ai = A mod mi. Sau đó sử dụng công thức: Trong đó: Mi = M/mi McaA k i ii mod 1 ⎟⎠ ⎞⎜⎝ ⎛= ∑ = ( ) kimMMc iiii ≤≤×= − 1;mod1 Truyền và bảo mật thông tin 331 II.3.6. Một số thuật toán ứng dụng trong RSA „ Ví dụ 178 mod 77=? „ Áp dụng định lý phần dư Trung hoa, ta coi A = 1718, m1 = 7, m2 = 11. Khi đó M1 = 11, M2 = 7 và „ 11-1 mod 7 = 4-1 mod 7 = 2, suy ra c1 = 11*2 = 22; „ 7-1 mod 11 = 8, suy ra c2 = 7*8 = 56; „ 178 mod 7 = (17 mod 7)8 mod 7 = 38 mod 7 = (32)4 mod 7 = a1 = 2; „ 178 mod 11 = (17 mod 11)8 mod 11 = 68 mod 11 = (62)4 mod 11 = 34 mod 11 = a2 = 4; „ Vậy 178 mod 77 = (2*22 + 4*56) mod 77 = 268 mod 77 = 37 mod 77 = A = 37; Truyền và bảo mật thông tin 332 II.3.7. Hiệu quả và an toàn „ Mã hiệu quả: „ Mã sử dụng lũy thừa của khoá công khai e, nếu giá trị của e nhỏ thì tính toán sẽ nhanh, nhưng dễ bị tấn công. Thường chọn e nhỏ hơn hoặc bằng 65537 (216-1), tức là độ dài khoá công khai là 16 bit. Chẳng hạn trong ví dụ trên ta có thể lựa chọn e = 23 hoặc e = 7. „ Ta có thể tính mã hoá nhanh, nếu biết n=pq và sử dụng Định lý phần dư Trung Hoa với mẩu tin M theo các Modulo p và q khác nhau. Nếu khoá công khai e cố định thì cần tin tưởng rằng khi chọn n ta luôn có gcd(e,Ф(n)) = 1. Loại bỏ mọi p, q mà làm cho Ф(n) không nguyên tố cùng nhau với e. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 84 Truyền và bảo mật thông tin 333 II.3.7. Hiệu quả và an toàn „ Giải mã hiệu quả: „ Có thể sử dụng Định lý phần dư Trung Hoa để tính theo mod p và q, sau đó kết hợp lại để tìm ra bản rõ. Vì ở đây người sử dụng khoá riêng biết được p và q, do đó có thể sử dụng kỹ thuật này. „ Nếu sử dụng định lý phần dư Trung Hoa để giải mã thì hiệu quả là nhanh gấp 4 lần so với giải mã tính trực tiếp. Truyền và bảo mật thông tin 334 II.3.7. Hiệu quả và an toàn „ Sinh khoá RSA „ Người sử dụng RSA cần phải xác định ngẫu nhiên 2 số nguyên tố rất lớn p, q thông thường khoảng 512 bit. „ Sau khi chọn được một khoá e hoặc d nguyên tố cùng nhau với Ф(n), dễ dàng tính được khoá kia chính là số nghịch đảo của nó qua thuật toán Euclide mở rộng. Truyền và bảo mật thông tin 335 II.3.7. Hiệu quả và an toàn „ An toàn của RSA „ Trên thực tế có nhiều cách tấn công khác nhau đối với mã công khai RSA như sau: „ Tìm kiếm khoá bằng phương pháp vét cạn, phương pháp này không khả thi với kích thước đủ lớn của các số „ Tấn công bằng toán học dựa vào độ khó việc tính Ф(n) bằng cách phân tích n thành hai số nguyên tố p và q hoặc tìm cách tính trực tiếp Ф(n). „ Trong quá trình nghiên cứu việc thám mã người ta đề xuất kiểu tấn công thời gian trong khi giải mã, tức là căn cứ vào tốc độ mã hoá và giải mã các mẩu tin cho trước mà phán đoán các thông tin về khoá. Truyền và bảo mật thông tin 336 II.2.8. Điểm bất động „ Giả sử rằng cặp khóa công khai là .(e,n)=(17,35) „ Giả sử thông báo có giá trị M= 8. „ Ta có C=.817 mod 35= 8 „ Như vậy mã hóa của thông báo vẫn là thông báo ban đầu. Nói một cách khác với khóa mã là 17 thì thông tin không được che dấu. Rõ ràng là phải tránh được tình trạng này định lý sau cho ta tính được số bản tin không thể che dấu được với một lựa chọn cho trước của . Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 85 Truyền và bảo mật thông tin 337 II.3.8. Điểm bất động Định lí: Nếu các thông báo được mã bằng hệ mật RSA với cặp khóa công khai (e,N) với N = p.q thì số các thông báo không thể che dấu được là σM=(1+UCLN(e-1, p-1))(1+UCLN(e-1, q-1) VD: p=5, q=7, e=2 -> σM =4 Các thông báo không bị che dấu là {0,1,15,21} Truyền và bảo mật thông tin 338 Bài tập hệ mật RSA „ Bài tập áp dụng: „ Cho p = 17, q = 19 „ Tính n? „ Cho e = 23, tìm d? „ Hãy mã hóa và giải mã cho các số 68, 12 Truyền và bảo mật thông tin 339 II.4. Hệ mật ElGamal „ Định nghĩa: cho a ∈ZN, bậc t của a (ký hiệu là ord(a)) là số nguyên dương nhỏ nhật sao cho at=1 (mod N) „ Nếu a ∈ZN* và có bậc φ(N) thì ta gọi a là phần tử sinh hay phần tử nguyên thủy của tập ZN. „ Theo định lý Euler, nếu a ∈ZN* thì aφ(N)=1 (mod N), => t là ước số của φ(N) Truyền và bảo mật thông tin 340 II.4. Hệ mật ElGamal „ Hệ mật ElGamal dựa vào bài toán logarit rời rạc „ Bài toán logarit rời rạc trên trường Zp: „ I = (p, α, β), trong đó p là số nguyên tố, α ∈ Zp* là phần tử nguyên thủy, β ∈ Zp*, tìm số nguyên a duy nhất, 0 ≤ a ≤ p – 2 để αa ≡ β mod p, chúng ta kí hiệu số nguyên a là logαβ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 86 Truyền và bảo mật thông tin 341 II.4. Hệ mật ElGamal „ Để ngăn cản các tấn công đã biết thì số nguyên tố p phải là số có ít nhất 150 chữ số và p-1 chứa ít nhất một thừa số nguyên tố lớn. „ Thực tế, không có thuật toán thời gian đa thức có thể giải được bài toán này. „ Tính thiết thực của bài toán logarit rời rạc trong mật mã? „ Là sự khó giải nhưng phép toán ngược của hàm mũ lại có thể tính hiệu quả nhờ phương pháp nhân bình phương có lặp (square-and-multiply method). „ Nói một cách khác, phép mũ mod p là hàm một chiều với các số nguyên tố p thích hợp. Truyền và bảo mật thông tin 342 3.5 Hệ mật ElGamal „ Hệ mật ElGamal „ Thuật toán tạo khoá: Tạo 1 khoá công khai và một khoá bí mật tương ứng : „ Tạo 1 số nguyên tố p lớn và một phần tử sinh α của nhóm nhân Zp* của các số nguyên mod p. „ Chọn một số nguyên ngẫu nhiên a, 1 ≤ a ≤ p – 2 và tính αa mod p „ Khoá công khai là bộ 3 số (p, α, αa), khoá bí mật là a. Truyền và bảo mật thông tin 343 3.5 Hệ mật ElGamal „ Thuật toán mã hoá: B mã hoá một thông tin báo m để gửi cho A bản mã cần gửi. B phải thực hiện các bước sau: „ Nhận khoá công khai (p, α, αa) của A. „ Biểu thị bản tin dưới dạng một số nguyên m trong dãy {0, 1, , p – 1} „ Chọn số nguyên ngẫu nhiên k, 1 ≤ k ≤ p – 2 „ Tính γ = αk mod p và δ = m(αa)k mod p . „ Gửi bản mã c = (γ, δ) cho A. Truyền và bảo mật thông tin 344 3.5 Hệ mật ElGamal „ Thuật toán giải mã: để khôi phục bản rõ m từ c, A phải thực hiện các bước sau: „ Sử dụng khóa riêng a để tính γp-1-a mod p (chú ý γ p-1-a = γ -a γ p-1= γ -a = γ -ak) (Nhớ lại: ĐL Ferma: γ p-1 mod p=1 với p là SNT) „ Khôi phục bản rõ bằng cách tính (γ-a)δ mod p. „ Chứng minh? „ Thuật toán trên cho phép A thu được bản rõ vì: γ-aδ ≡ α-ak.mαak ≡ m mod p (δ = m(αa)k) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 87 Truyền và bảo mật thông tin 345 3.5 Hệ mật ElGamal Ví dụ: cho p = 17 „ Xác định các phần tử nguyên thủy của Z*17 „ Giả sử „ Chọn a=3, α=2, αa mod 17 = 8 ÆKhóa công khai (p, α, αa) = (17, 2, 8). Khóa bí mật a = 3 „ Tính bản mã với bản rõ m = 7, chọn ngẫu nhiên k = 4.: γ = αk mod p =16 δ = mαak mod p = 7*23*4 mod 17= 10 ÆBản mã c=(16,10) „ Giải mã: (γp-1-a)δ mod p=1617-1-3*10 mod 17 = 7 Truyền và bảo mật thông tin 346 II.4. Tổng kết Kỹ thuật cửa sập (Trap Door) để xây dụng hàm 1 phía trong các hệ mã khóa công khai : i. Xuất phát từ bài toán bất trị Q ii. Xét một bài toán con dễ Q1 của Q. iii. Xáo trộn Q1 sao cho bài toán thu được Q1’ có vẻ giống bài toán Q. Q1 như 1 khóa lập mã công khai iv. Giữ bí mật thông tin làm sao khôi phục Q1 từ Q1’. Thông tin này được xem là cửa sập. Truyền và bảo mật thông tin 347 II.4. Tổng kết „ Các đặc trưng của khoá công khai „ Các thuật toán khoá công khai dùng 2 khoá với các đặc trưng sau: „ Không có khả năng tính toán để tìm khoá giải mã nếu chỉ biết thuật toán mã và khoá dùng để mã. „ Có thể dễ dàng mã hoá hoặc giải mã mẩu tin nếu biết khoá tương ứng „ Trong một số sơ đồ: một khoá bất kỳ trong hai khoá có thể dùng để mã, còn khoá kia dùng để giải mã. Chúng có vai trò đối ngược nhau. Truyền và bảo mật thông tin 348 II.4. Tổng kết „ Mặc dù an toàn nhưng các hệ mã khóa công khai đòi hỏi tài nguyên lớn khi thực thi: thời gian và bộ nhớÆ Trong thực tế các hệ mã này thường chỉ được sử dụng trong những công đoạn quan trọng như: chứng thực, tạo chữ ký, cất giữ mật khẩu, mã hóa khóa „ Với những ứng dụng cụ thể, đòi hỏi phải có các nghi thức và quy trình bảo mật thích hợp Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 88 Truyền và bảo mật thông tin 349 II.4. Tổng kết „ Khoá công khai ra đời hỗ trợ thêm để giải quyết một số bài toán an toàn, chứ không phải thay thế khoá riêng. Cả hai khoá cùng tồn tại, phát triển và bổ sung cho nhau „ Khi cần gửi thông tin qua mạng, người ta thường mã hóa chúng bằng một thuật toán đối xứng. Khóa bí mật của hệ mã này được mã bằng một hệ mật mã khóa công khai để truyền qua cho người nhận Truyền và bảo mật thông tin 350 II.4. Tổng kết Ví dụ kết hợp 2 loại mật mã: „ Đối tượng cần truyền tin A gửi tín hiệu yêu cầu nhận tin tới đối tượng B „ Đối tượng B chấp nhận và gửi khoá công khai KPB cho đối tượng A „ Đối tượng A sinh ra khoá bí mật K, mã hoá thành EKpB(K), rồi gửi cho B „ Đối tượng B nhận EKPB (K), dùng KSBgiải mã lại thành K, và gửi sẵn sàng nhận tin cho A „ Đối tượng A chuẩn bị gói tin P, mã hoá thành K(P), rồi gửi cho B „ Đối tượng B nhận gói K(P), giải mã thành P, và lưu lại cho mình Truyền và bảo mật thông tin 351 II.4. Tổng kết „ Tại sao lại phải dùng mã khoá công khai? „ Người ta muốn giải quyết hai vấn đề sau về khoá nảy sinh trong thực tế: „ Phân phối khoá - làm sao có thể phân phối khóa an toàn mà không cần trung tâm phân phối khoá tin cậy „ Chữ ký điện tử - làm sao có thể kiểm chứng được rằng mẩu tin gửi đến nguyên vẹn từ đúng người đứng tên gửi. „ Nếu chỉ dùng khoá đối xứng, thì không có giải pháp cho hai bài toán trên. Truyền và bảo mật thông tin 352 II.4. Tổng kết „ Ứng dụng khoá công khai „ Có thể phân loại các ứng dụng của khoá công khai thành 3 loại khác nhau: „ Mã/giải mã – cung cấp bảo mật. Đây là ứng dụng bảo mật truyền thống giống như ta vẫn thường dùng với khoá đối xứng. „ Chữ ký điện tử - cung cấp xác thực. Một trong các ứng dụng mới của khoá công khai mà khoá đối xứng không thể thực hiện được, đó là khoá công khai có đủ cơ sở để xác nhận người gửi và có thể là một lựa chọn để tạo chữ ký điện tử của người gửi. „ Một số thuật toán mã công khai phù hợp với mọi ứng dụng, còn một số khác chuyên dùng cho ứng dụng cụ thể. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 89 Truyền và bảo mật thông tin 353 Chương IV. Chữ ký điện tử và các hàm băm „ IV.1. Chữ ký điện tử „ IV.2. Các hàm băm Truyền và bảo mật thông tin 354 IV.1. Chữ ký điện tử IV.1.1. Khái niệm về chữ ký điện tử IV.1.2. Sơ đồ chữ ký RSA IV.1.3. Sơ đồ chữ ký Elgamal IV.1.4. Chuẩn chữ kí số (DSS) Truyền và bảo mật thông tin 355 IV.1.1. Khái niệm về chữ ký điện tử „ Sơ đồ chữ ký điện tử (CKĐT) là phương pháp kí một bức điện lưu dưới dang điện tử. Chẳng hạn một bức điện có ký hiệu được truyền trên mạng máy tinh. „ Là một cơ chế xác thực hóa cho phép đính kèm một mã số vào thông điệp tương tự như là việc kí một chữ ký lên môt văn bản bình thường. Truyền và bảo mật thông tin 356 IV.1.1. Khái niệm về chữ ký điện tử „ Khác biệt giữa CKĐT và chữ ký thường: Bản copy đồng nhất với bản gốc Æ bị dùng lạiÆ khắc phục bằng cách dán nhãn thời gian Bản copy thường khác với bản gốc Kiểm tra nhờ thuật toán xác thực công khai, sơ đồ chữ ký an toàn ngăn chặn được giả mạo Kiểm tra bằng cách so sánh nó với các chữ kí xác thực khácÆ dễ giả mạo Không gắn theo kiểu vật lý, là sự mã hóa, “không nhìn thấy” Là một phần vật lý của tài liệu Chữ ký điện tửChữ ký thường Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 90 Truyền và bảo mật thông tin 357 IV.1.1. Khái niệm về chữ ký điện tử „ Một sơ đồ chữ kí số thường chứa hai thành phần: „ Thuật toán kí và thuật toán xác minh. Chữ kí sig(x) nhận được có thể kiểm tra bằng thuật toán xác minh công khai ver. Truyền và bảo mật thông tin 358 IV.1.1. Khái niệm về chữ ký điện tử Định nghĩa „ 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: 1. P là tập hữu hạn các bức điện có thể. 2. A là tập hữu hạn các chữ kí có thể. 3. K không gian khoá là tập hữu hạn các khoá có thể. 4. Với mỗi k thuộc 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 : P → A và verk: P×A →{true,false} là những hàm sao cho mỗi bức điện x∈ P và mối chữ kí y∈ A thoả mãn phương trình dưới đây: True nếu y=sigk(x) verk(x,y)= False nếu y ≠ sigk(x) Truyền và bảo mật thông tin 359 IV.1.1. Khái niệm về chữ ký điện tử „ sigk và verk là các hàm thời gian đa thức. „ Verk là hàm công khai sigk là mật. „ Không thể dể dàng tính toán để giả mạo chữ kí „ Một sơ đồ chữ kí không thể an toàn vô điều kiện có thể kiểm tra tất cả các chữ số y có thể có trên bức điện x nhờ dùng thuât toán ver công khai cho đến khi tìm thấy một chữ kí đúng. Truyền và bảo mật thông tin 360 IV.1.2. Sơ đồ chữ ký RSA „ Độ an toàn rất cao, dựa vào ưu điểm của hệ mã RSA, „ Đảo ngược hàm mã và giải mã Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 91 Truyền và bảo mật thông tin 361 IV.1.2. Sơ đồ chữ ký RSA Sơ đồ chữ ký RSA Cho n= pq, p và q là các số nguyên tố. Cho P =A= Zn và định nghĩa: K= {(n,p,q,a,b):n=pq,p và q là nguyên tố, ab ≡1(mod φ(n)) }. Các giá trị n và b là công khai, còn p, q, a là bí mật Ta định nghĩa : sigk(x)= xa mod n và verk(x,y)= true ⇔ x ≡yb (mod n) với x,y ∈Zn Truyền và bảo mật thông tin 362 IV.1.2. Sơ đồ chữ ký RSA „ Chữ ký thường dùng kết hợp với hàm mã hóa công khai: „ Giả sử rằng, A muốn gửi thông điệp đã mã hóa và ký đến B: „ A tính y= sigA(x) và sau đó mã cả x và y bằng hàm mã khoá công khai eB của B, „ B nhận được z = eB(x,y), dùng hàm dB giải mã z để nhận được (x,y). Sau đó kiểm tra xem verA(x,y) có bằng True hay không. Truyền và bảo mật thông tin 363 IV.1.2. Sơ đồ chữ ký RSA „ Nếu đầu tiên A mã x rồi sau đó mới kí lên bản mã thì sao?. Tức là: „ A tính: z=eB(x) và y= sigA(z). „ A sẽ truyền cặp (z,y) tới B. „ B sẽ dùng verA xác minh chữ ký và dùng dB giải mã z, nhận x Æ Một vấn đề tiểm ẩn trong biện pháp này là nếu C nhận được cặp (z,y) có thể thay chữ kí y của A bằng chữ kí của mình: y’ = sigC(z)=sigC(eB(x)). Khi đó nếu C truyền(z, y’ ) đến B thì chữ kí C được B xác minh bằng verC và B có thể suy ra rằng, bản rõ x xuất phát từ C. „ Do khó khăn này, hầu hết người sử dụng được khuyến nghị nên kí trước khi mã. Truyền và bảo mật thông tin 364 IV.1.3. Sơ đồ chữ ký Elgamal „ Sơ đồ chữ kí Elgamal đã từng dưới thiệu trong bài báo năm 1985. Bản cả tiến của sơ đồ này đã được Viện Tiêu chuẩn và Công Nghệ Quốc Gia Mỹ (NIST) chấp nhận làm chữ kí số. Sơ đồ Elgamal (E.) được thiết kế với mục đích dành riêng cho chữ kí số, khác sơ đồ RSA dùng cho cả hệ thống mã khoá công khai lẫn chữ kí số. „ Đối với sơ đồ E, có nhiều chữ kí hợp lệ trên bức điện cho trươc bất kỳ. Thuật toán xác minh phải cố khả năng chấp nhận bất kì chữ kí hợp lệ khi xác thực. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 92 Truyền và bảo mật thông tin 365 IV.1.3. Sơ đồ chữ ký Elgamal „ Định nghĩa: cho a ∈ZN, bậc t của a (ký hiệu là ord(a)) là số nguyên dương nhỏ nhật sao cho at=1 (mod N) „ Nếu a ∈ZN* và có bậc φ(N) thì ta gọi a là phần tử sinh hay phần tử nguyên thủy của tập ZN. „ Theo định lý Euler, nếu a ∈ZN* thì aφ(N)=1 (mod N), => t là ước số của φ(N) Truyền và bảo mật thông tin 366 IV.1.3. Sơ đồ chữ ký Elgamal Sơ đồ chữ ký Elgamal: Cho p là số nguyên tố sao cho bài toán logarit rời rạc trên Zp là khó và giả sử α ∈ Zn là phần tử nguyên thủy, P = Zp* , A = Zp* × Zp-1 và định nghĩa : K ={(p,α ,a,β ): β ≡ αa (mod p)}. Giá trị p,α ,β là công khai, còn a là mật. „ Với K = (p,α ,a,β ) và một số ngẫu nhiên (bí mật) k∈ Zp-1. và định nghĩa : Sigk(x,y) =(γ ,δ), trong đó γ = αk mod p và δ =(x-aγ) k-1 mod (p-1). „ Với x,γ ∈ Zp* và δ ∈ Zp-1 , ta định nghĩa : Ver(x,γ ,δ ) = True ⇔ βγ γδ ≡ αx (mod p). Truyền và bảo mật thông tin 367 IV.1.3. Sơ đồ chữ ký Elgamal „ Nếu chữ kí được thiết lập đúng khi xác minh sẽ thành công vì : βγ γδ ≡ αaγ αk δ (mod p)= α aγ +k δ (mod p) „ Mặt khác ta có: a γ+ k δ = a γ+ (k(x-aγ) k-1 mod (p-1)) = a γ + (x - a γ) mod (p-1) = a γ + x mod (p-1) - a γ mod (p-1) = x (mod p-1) => a γ+ k δ =t(p-1)+x (với t là một số nguyên nào đó) => α aγ +k δ (mod p) = α t(p-1) α x (mod p) = α x (mod p) (Do αp-1 mod p=1 khi p là SNT - Định lý Ferma) „ Vì vậy: βγ γδ = α aγ +k δ (mod p) ≡ αx(mod p) Truyền và bảo mật thông tin 368 IV.1.3. Sơ đồ chữ ký Elgamal Ví dụ „ Giả sử cho p = 467, α =2,a = 127; khi đó: β = αa mod p = 2127 mod 467=132 „ Bức điện x = 100, chọn số ngẫu nhiên k =213 (chú ý là UCLN(213,466) =1 và 213-1 mod 466 = 431. Khi đó γ =2213 mod 467 = 29 và δ =(100-127 × 29) 431 mod 466 = 51. „ Bất kỳ ai cũng có thể xác minh chữ kí bằng các kiểm tra : 13229 2951 ≡ 189 (mod 467) và 2100 ≡ 189 (mod 467) „ Vì thế chữ kí là hợp lệ. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 93 Truyền và bảo mật thông tin 369 IV.1.3. Sơ đồ chữ ký Elgamal „ Xét độ mật của sơ đồ chữ kí E. Giả sử, C thử giả mạo chữ kí trên bức điện x cho trước không biết a. Nếu C chọn γ và sau đó thử tìm giá trị δ tương ứng, anh ta phải tính logarithm rời rạc logγ αxβ-γ. Mặt khác, nếu đầu tiên ta chọn δ và sau đó thử tìm γ và thử giải phương trình: βγ γδ ≡ αx(mod p). để tìm γ. Đây là bài toán chưa có lời giải nào: Tuy nhiên, dường như nó chưa được gắn với đến bài toán đã nghiên cứu kĩ nào nên vẫn có khả năng có cách nào đó để tính δ và γ đồng thời để (δ, γ) là một chữ kí. Hiện thời không ai tìm được cách giải song củng ai không khẳng định được rằng nó không thể giải được. Truyền và bảo mật thông tin 370 IV.1.3. Sơ đồ chữ ký Elgamal „ Tuy nhiên, có một cách để C có thể kí lên bức điện ngẫu nhiên bằng việc chọn γ, δ và x đồng thời: giả thiết i và j là các số nguyên 0 ≤ i ≤ p-2, 0 ≤ j ≤ p-2 và UCLN(j,p-2) = 1. Khi đó C thực hiện các tính toán sau: γ = αi βj mod p δ = -γ j-1 mod (p-1) x = -γ i j-1 mod (p-1) „ trong đó j-1 được tính theo modulo (p-1) (ở đây đòi hỏi j nguyên tố cùng nhau với p-1). Truyền và bảo mật thông tin 371 IV.1.3. Sơ đồ chữ ký Elgamal „ Xem (δ, γ) là giá trị chữ ký cho bức điện x. Việc xác minh sẽ hợp lệ: Truyền và bảo mật thông tin 372 IV.1.3. Sơ đồ chữ ký Elgamal „ Vấn đề khác: có thể giả mạo chữ ký bằng cách sử dụng chữ ký trước đó ký cho nhiều bức khác: „ Nếu có cặp (δ, γ) và x, lấy h, i va ̀ j là các số nguyên, trong đó 0≤ i, j, h ≤ p-2 và UCLN (h γ - j δ, p-1) = 1. Tính: „ Cặp (λ, μ) là chữ ký cho bức điện x’ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 94 Truyền và bảo mật thông tin 373 IV.1.4. Chuẩn chữ kí số (DSS) „ Chuẩn chữ kí số(Digital Signature Standard- DSS) là phiên bản cải tiến của sơ đồ chữ kí Elgamal. Nó được công bố trong Hồ Sơ trong liên bang vào ngày 19/5/94 và được làm chuẩn voà 1/12/94 tuy đã được đề xuất từ 8/91. Truyền và bảo mật thông tin 374 IV.1.4. Chuẩn chữ kí số „ Giả sử p là số nguyên tố 512 bít sao cho bài toán logarithm rời rạc trong Zp khong Giải được, cho q là số nguyên tố 160 bít là ước của (p-1). Giả thiết α ∈ Zp là căn bậc q của 1 modulo p (αq≡1 (mod p). Cho P =Zp . A = Zq× Zq và định nghĩa : K = {(p,q,α ,a,β ) : β ≡ αa (mod p)} các số p, q, α và β là công khai, còn a mật. „ Với K = (p,q,α ,a,β )và với một số ngẫu nhiên (mật) k ,1 ≤ k ≤ q-1, ta định nghĩa: sig (x,k) = (γ ,δ) trong đó γ =(αk mod p) mod q và δ = (x +aγ )k-1 mod q „ Với x ∈ Zp và γ ,δ ∈ Zq , qua trình xác minh sẽ hoàn toàn sau các tính toán : e1= xδ-1 mod q e2= γδ-1 mod q „ ver (x, γ, δ) = true ⇔( αe1βe2 mod p) mod q = γ Truyền và bảo mật thông tin 375 IV.1.4. Chuẩn chữ kí số „ Chú ý: p-1=qt, với t là số nguyên „ Để chọn α, ta có thể chọn g bất kỳ ∈ Zp* và tính α =gt bởi vì khi đó: αq (mod p) =gtq (mod p) = g(p-1) (mod p) = 1 (mod p) (ĐL Ferma) Truyền và bảo mật thông tin 376 IV.1.4. Chuẩn chữ kí số Ví dụ: „ Giả sử p=29 q =7, p = 4q+1. „ 3 ∈ Zp* nên ta có thể lấy: α = 34 mod 29 =23 „ Chọn a =5, khi đó : β = αa mod p=235 mod 29=25 „ Ký bức điện x = 6: „ Chọn số ngẫu nhiên k =3=> k-1=5 : khi đó: γ =(αk mod p) mod q =(233 mod 29) mod 7=2 „ và δ = (x +aγ )k-1 mod q =(6+5*2)*5 mod 7=3 „ Chữ kí (2, 3) trên bức điện 6 được xác minh bằng các tính toán sau:δ-1 = 5 e1= xδ-1 mod q=6*5 mod 7=2 e2= γδ-1 mod q=2*5 mod 7=3 ( αe1βe2 mod p) mod q=232*253 mod 29 mod 7=2 (= γ ) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 95 Truyền và bảo mật thông tin 377 Mô hình ứng dụng CKĐT Truyền và bảo mật thông tin 378 IV.2. Các hàm băm IV.2.1. Khái niệmhàm băm IV.2.2. Tính chất hàm băm IV.2.3. Một số hàm băm nổi tiếng IV.2.4. Ứng dụng các hàm băm Truyền và bảo mật thông tin 379 IV.2.1. Khái niệm hàm băm Đặt vấn đề „ Với các sơ đồ ký số, chỉ cho phép ký các bức thông điệp (thông tin) có kích thước nhỏ. „ Đối với thông điệp lớn (chẳng hạn vài chục MB)? Có giải pháp đơn giản là chặt bản thông điệp ra nhiều đoạn nhỏ (chẳng hạn 160 bit) rồi ký lên từng đoạn. Biện pháp này sẽ gặp những vấn đề gì? Truyền và bảo mật thông tin 380 IV.2.1. Khái niệm hàm băm Các vấn đề mắc phải: „ Thứ nhất: kích thước thông điệp sẽ lớn lên (nếu sử dụng DSS thì riêng kích thước chữ ký gấp đôi thông điệp). „ Thứ hai: với các chữ ký “an toàn” thì tốc độ chậm vì chúng dùng nhiều phép tính số học phức tạp như số mũ modulo. „ Thứ ba : vấn đề nghiêm trọng hơn đó là kết quả sau khi ký, nội dung của thông điệp có thể bị xáo trộn các đoạn với nhau, hoặc một số đoạn trong chúng có thể bị mất mát, trong khi người nhận cần phải xác minh lại thông điệp. Ta cần phải bảo vệ tính toàn vẹn của thông điệp. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 96 Truyền và bảo mật thông tin 381 IV.2.1. Khái niệm hàm băm Giải pháp cho các vấn đề vướng mắc đến chữ ký số là dùng hàm băm (Hash) để trợ giúp cho việc ký số. Các thuật toán băm với đầu vào là các bức thông điệp có dung lượng, kích thước tùy ý (vài KB đến vài chục MB thậm chí hơn nữa) – các bức thông điệp có thể là dạng văn bản, hình ảnh, âm thanh, file ứng dụng v.v - và với các thuật toán băm: MD2, MD4, MD5, SHA cho các bản băm đầu ra có kích thước cố định (128 bit với dòng MD, 160 bit với SHA) được gọi là cốt của bức điện (message digest). Truyền và bảo mật thông tin 382 IV.2.1. Khái niệm hàm băm Định nghĩa „ Hàm băm là các thuật toán không sử dụng khóa để mã hóa (ở đây ta dùng thuật ngữ “băm” thay cho “mã hóa”), nó có nhiệm vụ “lọc” (băm) thông điệp được đưa vào theo một thuật toán h một chiều nào đó, rồi đưa ra một bản băm – văn bản đại diện – có kích thước cố định. Do đó người nhận không biết được nội dung hay độ dài ban đầu của thông điệp đã được băm bằng hàm băm. „ Giá trị của hàm băm là duy nhất, và không thể suy ngược lại được nội dung thông điệp từ giá trị băm này. Truyền và bảo mật thông tin 383 IV.2.1. Khái niệm hàm băm Kết hợp CKĐT với hàm băm: y=sigA(z)z=h(x) verA(z,y) z=h(x) true false y x x A B K ê n h k h ô n g a n t o à n Truyền và bảo mật thông tin 384 IV.2.1. Khái niệm hàm băm Kết hợp CKĐT với hàm băm: „ Giả sử A muốn gửi cho B thông điệp x. A thực hiện các bước sau: 1. A băm thông điệp x, thu được bản đại diện z = h(x) – có kích thước cố định 128 bit hoặc 160 bit. 2. A ký số trên bản đại diện z bằng khóa bí mật của mình, thu được bản ký số y = sigA(z). 3. A gửi (x, y) cho B „ Khi B nhận được (x, y). B thực hiện các bước sau: 1. B dùng thuật toán băm – tương ứng với thuật toán băm mà A dùng – để băm thông điệp x đi kèm, nhận được z=h(x). 2. B kiểm tra chữ ký số để xác minh xem thông điệp mà mình nhận được có phải được gửi từ A hay ko bằng cách sử dùng hàm verA(z,y) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 97 Truyền và bảo mật thông tin 385 IV.2.2. Tính chất hàm băm „ Tính chất 1: Hàm băm không va chạm yếu „ Không gian hàm băm nhỏ hơn không gian thông điệpÆ có sự đụng độ: tồn tại 2 thông điệp x, x’, x≠x’ mà h(x)=h(x’) „ Do đó có thể tấn công: „ Người A gửi cho B (x, y) với y = sigA(h(x)). Nhưng trên đường truyền, tin bị lấy trộm. Tên trộm, bằng cách nào đó tìm được một bản thông điệp x’ có h(x’) = h(x) mà x’ ≠ x. Sau đó, hắn đưa x’ thay thế x rồi truyền tiếp cho người B. Người B nhận được và vẫn xác thực được thông tin đúng đắn. „ Để tránh tấn công trên, hàm băm phải không va chạm yếu Truyền và bảo mật thông tin 386 IV.2.2. Tính chất hàm băm „ Tính chất 1: Hàm băm không va chạm yếu: Hàm băm h là không va chạm yếu nếu khi cho trước một bức điện x, không thể tiến hành về mặt tính toán để tìm ra một bức điện x’ ≠ x mà h(x’) = h(x). Truyền và bảo mật thông tin 387 IV.2.2. Tính chất hàm băm „ Tính chất 2: Hàm băm không va chạm mạnh: „ Xét một kiểu tấn công: Đầu tiên, tên giả mạo tìm ra được hai bức thông điệp x’ và x (x’ ≠ x) mà có h(x’) = h(x) (ta coi bức thông điệp x là hợp lệ, còn x’ là giả mạo). Tiếp theo, hắn đưa cho ông A và thuyết phục ông này kí vào bản tóm lược h(x) để nhận được y. Khi đó (x’, y) là bức điện giả mạo nhưng hợp lệ. „ Để tránh kiểu tấn công này, hàm h phải thỏa mãn tính không va chạm mạnh: Hàm băm h là không va chạm mạnh nếu không có khả năng tính toán để tìm ra hai bức thông điệp x và x’ mà x ≠ x’ và h(x) = h(x’). Truyền và bảo mật thông tin 388 IV.2.2. Tính chất hàm băm „ Tính chất 3: Hàm băm một chiều: „ Việc giả mạo các chữ kí trên bản tóm lược thông báo z ngẫu nhiên thường xảy ra với sơ đồ chữ kí. Giả sử tên gải mạo tính chữ kí trên bản tóm lược thông báo z ngẫu nhiên như vậy. Sau đó anh ta tìm x sao cho z= h(x). Nếu làm được như vậy thì (x,y) là bức điện giả mạo hợp lệ. Để tránh được tấn công này, h cần thoả mãn tính chất một chiều: Hàm Hash h là một chiều nếu khi cho trước một bản tóm lược thông báo z, không thể thực hiện về mặt tính toán để tìm bức điện x sao cho h(x) = z. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 98 Truyền và bảo mật thông tin 389 IV.2.3. Một số hàm băm nổi tiếng „ IV.2.3.1. Hàm băm MD5 IV.2.3.2. Hàm băm SHA Truyền và bảo mật thông tin 390 IV.2.3.1. Hàm băm MD5 (Message Digest) „ Ronald Rivest là người đã phát minh ra các hàm băm MD2, MD4 (1990) va ̀ MD5 (1991). „ Hàm MD5 là bản cải tiến được dùng rộng rãi nhất, là nguyên tắc chung cho nhiều hàm băm khác „ Đầu ra MD là 128 bit, MD5 được xem là an toàn „ Tuy nhiên, với sự phát triển của thuật toán thám mã hiện nay, các hàm băm 128 bit được khuyến nghị là không nên dùng cho các hệ thống mới Truyền và bảo mật thông tin 391 IV.2.3.2. Hàm băm SHA (Secure Hash Algorithm) „ Được công bố trong Hồ sơ Liên bang năm 1992 và được chấp nhận làm tiêu chuẩn vào năm 1993 do Viện Tiêu Chuẩn và Công Nghệ Quốc Gia (NIST) „ Được thiết kế dựa trên những nguyên tắc của MD4/MD5 nhưng phức tạp hơn „ Kết quả đầu ra có độ dài 160 bit. „ Tốt hơn MD5 Truyền và bảo mật thông tin 392 IV.2.4. Ứng dụng các hàm băm „ Úng dụng chính của các hàm băm là sử dụng với CKĐT „ Xác thực tính nguyên vẹn của dữ liệu trên đường truyền: „ Truyền cả dữ liệu lẫn giá trị băm, „ Khi nhận được dữ liệu, sử dụng hàm băm tính kết quả và so sánh với giá trị băm nhận được „ Xác thực người dùng: lưu tên tài khoản và giá trị băm của mật khẩu. Để kiểm tra xem người đăng nhập hợp lệ: băm mật khẩu nhập vào và so sánh với giá trị mật khẩu lưu trong hệ thống.