›
›

An toàn và bảo mật thông tin - Chương 3,4,5

pdf 72 trang phuongnguyen 2720
Download
Bạn đang xem 20 trang mẫu của tài liệu "An toàn và bảo mật thông tin - Chương 3,4,5", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_an_toan_va_bao_mat_thong_tin.pdf

Nội dung text: An toàn và bảo mật thông tin - Chương 3,4,5

  1. Chương 3 Chuẩn mã dữ liệu DES (Data Encryption Standard) 3.1. Giới thiệu chung về DES Chuẩn mã hoá dữ liệu DES được Văn phòng tiêu chuẩn của Mỹ (U.S National Bureau for Standards) công bố năm 1971 để sử dụng trong các cơ quan chính phủ liên bang. Giải thuật được phát triển tại Công ty IBM dựa trên hệ mã hoá LUCIFER của Feistel. DES là thuật toán mã hoá khối (block algrithm), với cỡ của một khối là 64 bít. Một khối 64 bít bản rõ được đưa vào, sau khi mã hoá dữ liệu đưa ra là một khối bản mã 64 bít. Cả mã hoá và giải mã đều sử dụng cùng một thuật toán và khoá. Khoá mã có độ dài 64 bít, trong đó có 8 bít chẵn lẻ được sử dụng để kiểm soát lỗi. Các bít chẵn lẻ nằm ở các vị trí 8, 16, 24, , 64. Tức là cứ 8 bít khoá thì trong đó có 1 bít kiểm soát lỗi, bít này qui định số bít có giá trị “1” của khối 8 bít đó theo tính bù chẵn. Nền tảng để xây dựng khối của DES là sự kết hợp đơn giản của các kỹ thuật thay thế và hoán vị bản rõ dựa trên khoá. DES sử dụng 16 vòng lặp, nó áp dụng cùng một kiểu kết hợp của các kỹ thuật trên khối bản rõ 16 lần (Như sơ đồ mã) Thuật toán chỉ sử dụng các phép toán số học và lôgíc trên các số 64 bít, vì vậy nó dễ dàng thực hiện vào những năm 1970 trong điều kiện về công nghệ phần cứng lúc bấy giờ. Ban đầu, sự thực hiện các phần mềm kiểu này rất thô sơ, nhưng hiện tại thì việc đó đã tốt hơn, và với đặc tính lặp 55
  2. đi lặp lại của thuật toán đã tạo nên ý tưởng sử dụng chíp với mục đích đặc biệt này. DES có một số đặc điểm sau: ♦ Sử dụng khoá 56 bít. ♦ Xử lý khối vào 64 bít, biến đổi khối vào thành khối ra 64 bít. ♦ Mã hoá và giải mã được sử dụng cùng một khoá. ♦ DES được thiết kế để chạy trên phần cứng. DES thường được sử dụng để mã hoá các dòng dữ liệu mạng và mã hoá dữ liệu được lưu trữ trên đĩa. 56
  3. 3.2. Mô tả thuật toán 57
  4. DES thực hiện trên từng khối 64 bít bản rõ. Sau khi thực hiện hoán vị khởi đầu, khối dữ liệu được chia làm hai nửa trái L0 và phải R0, mỗi nửa 32 bít. Từ L0 và R0 sẽ lặp 16 vòng, tại mỗi vòng tính: Li=Ri-1 Ri=Li-1⊕f(Ri-1,Ki) với i= 1, 2, ,16 Tại vòng thứ 16, R16 đổi chỗ cho L16. Sau đó ghép 2 nửa R16, K16 cho đi qua hoàn vị nghịch đảo của hoàn vị IP sẽ tính được bản mã. Bản mã cũng có độ dài 64 bít. Trong đó hàm f được thực hiện như sau: Sơ đồ tính hàm f(Ri-1,Ki) 58
  5. R K i-1 i E E(R ) i-1 + B B B B B B B B 1 2 3 4 5 6 7 8 S S S S S S S S 1 2 3 4 5 6 7 8 c c c c c c c c 1 2 3 4 5 6 7 8 f(R ,K ) i-1 i Khối Ri-1 có độ dài 32 bít cho đi qua hoàn vị mở rộng E được một khối có độ dài 48 bít. Khối này XOR với khóa Ki, kết quả được một khối có độ dài 48 bit. Khối này sẽ được chia làm 8 khối B1, B2, ., B8. Mỗi khối này có độ dài là 6 bít. Từng khối Bi cho đi qua hộp Si sẽ biến một khối có độ dài 6 bit thành một khối Ci có độ dài 4 bít. Các khối Ci ghép lại được một khối có độ dài 32 bit. Khối này cho đi qua hoàn vị P cho ra kết quả của hàm f(Ri-1, Ki). Mỗi hộp S là một bảng gồm 4 hàng và 16 cột được đánh số từ 0. Như vậy mỗi hộp S có hàng 0,1,2,3. Cột 0,1,2, ,15. Mỗi phần tử của hộp là 59
  6. một số 4 bít. Sáu bít vào hộp S sẽ xác định số hàng và số cột để tìm kết quả ra. Mỗi khối Bi có 6 bít kí hiệu là b1, b2, b3, b4, b5 và b6. Bít b1 và b6 được kết hợp thành một số 2 bít, nhận giá trị từ 0 đến 3, tương ứng với một hàng trong bảng S. Bốn bít ở giữa, từ b2 tới b5, được kết hợp thành một số 4 bít, nhận giá trị từ 0 đến 15, tương ứng với một cột trong bảng S. Ví dụ, giả sử khối B6 là 110010 ta đưa qua hộp S6. Bít đầu tiên và bít cuối cùng kết hợp thành 10, tương ứng với hàng thứ 2 của hộp S6. Bốn bít giữa kết hợp thành 1001, tương ứng với cột thứ 9 của hộp S 6. Phần tử hàng 2 cột 9 của hộp S6 là 0. Giá trị 0000 được thay thế cho 110010. Sơ đồ tính khóa K1, K2, , K16 K PC-1 C D D 0 0 0 LS LS 1 1 C D D PC-2 K 1 1 1 1 . . LS LS 16 16 C D D PC-2 K 16 16 16 16 60
  7. Từ khóa K bí mật có độ dài 64 bít đi qua hoán vị chọn PC1 cho một khối có độ dài 56 bit. Khối này chia làm 2 nửa C0 và D0 mỗi nửa 28 bít. Từ khối này sẽ thực hiện qua 16 vòng lặp. C0 và D0 sẽ dịch vòng trái LS1 bít cho khối C1 và D1. Hai khối C1 và D1 sẽ ghép lại thành một khối 56 bít rồi cho qua hoán vị chọn PC2 được khóa K1 có độ dài 48 bít. Từ khối C1 và D1 dịch vòng trái LS2 bít được khối C2 và D2, ghép 2 khối C2 và D2 được một khối 56 bit. Cho khối này qua hoán vị chọn PC2 được khóa K2 cũng có độ dài 48 bít. Tương tự cho đến khóa K16. Trong đó bảng số bít dịch trái tại mỗi vòng là: Vòng i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Số bít dịch 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 3.3.Hoán vị khởi đầu Hoán vị khởi đầu đổi chỗ khối dữ liệu vào, thay đổi vị trí của các bít trong khối dữ liệu vào. Bảng hoán vị khởi đầu này, và tất cả các bảng khác sau này, được đọc từ trái qua phải, từ trên xuống dưới. Ví dụ, hoán vị khởi đầu chuyển bít 1 thành bít 58, bít 2 thành bít 50, bít 3 thành bít 42, Bảng hoán vị khởi đầu. 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Hoán vị khởi đầu và tương ứng là hoán vị ngược không làm ảnh hưởng đến sự an toàn của DES. 61
  8. 3.4. Hoán vị chọn Đầu tiên, khoá 64 bít được giảm xuống thành một khoá 56 bít bằng cách bỏ qua 8 bít chẵn lẻ. Sự loại bỏ được thực hiện theo Bảng sau: Bảng hoán vị chọn PC1: 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 Các bít chẵn lẻ này có thể được sử dụng để đảm bảo rằng không có lỗi nào xảy ra khi đưa khoá vào. Sau khi khoá 56 bít được trích ra, một khoá khác 48 bít được sinh ra cho mỗi vòng của DES. Bảng hoán vị chọn PC2: 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 3.5. Hoán vị mở rộng Ở thao tác này, nửa phải của dữ liệu, Ri, được mở rộng từ 32 bít thành 48 bít. Bởi vì sự thực hiện này thay đổi thứ tự của các bít bằng cách lặp lại một bít nào đó, nó được hiểu như là một sự hoán vị mở rộng. Sự thực hiện này nhằm mục đích tạo ra kết quả là dữ liệu cùng cỡ với khoá để thực hiện thao tác XOR. Định nghĩa hoán vị mở rộng - hộp E. Với mỗi bộ 4 bít của khối dữ liệu vào, bít đầu tiên và bít thứ tư mỗi bít tương ứng với 2 bít của khối dữ liệu ra, trong khi bít thứ hai và bít thứ ba mỗi bít tương ứng với một bít của 62
  9. khối dữ liệu ra. Bảng dưới mô tả vị trí của các bít trong khối dữ liệu ra theo khối dữ liệu vào. Ví dụ, bít ở vị trí thứ 3 của khối dữ liệu vào được chuyển tới vị trí thứ 4 trong khối dữ liệu ra. Và bít ở vị trí 21 của khối dữ liệu vào được chuyển tới vị trí 30 và 32 trong khối dữ liệu ra. Bảng hoán vị mở rộng E: 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 12 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 63
  10. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 32 48 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Hoán vị mở rộng 64
  11. Mặc dù khối dữ liệu ra rộng hơn khối dữ liệu vào, nhưng một khối dữ liệu vào chỉ có duy nhất một khối dữ liệu ra. 3.6. Hộp thay thế S Sau khi được nén, khoá được XOR với khối mở rộng, 48 bít kết quả được chuyển sang giai đoạn thay thế. Sự thay thế được thực hiện bởi 8 hộp thay thế (substitution boxes, S-boxes). Khối 48 bít được chia thành 8 khối 6 bít. Mỗi khối được thực hiện trên một hộp S riêng biệt (separate S-box): khối 1 được thực hiện trên hộp S1, khối 2 được thực hiện trên hộp S2, , khối 8 được thực hiện trên hộp S8. Hộp S thứ nhất 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 Hộp S thứ 2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 Hộp S thứ 3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 65
  12. Hộp S thứ 4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 Hộp S thứ 5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 66
  13. Hộp S thứ 6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 Hộp S thứ 7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 Hộp S thứ 8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 3.7. Hộp hoán vị P Khối dữ liệu 32 bít ra của hộp thay thế S được hoán vị tiếp trong hộp P. Sự hoán vị này ánh xạ mỗi bít dữ liệu vào tới một vị trí trong khối dữ liệu ra, không bít nào được sử dụng hai lần và cũng không bít nào bị bỏ qua. Nó được gọi là hoán vị trực tiếp (straight permutation). Bảng hoán vị cho ta vị trí của mỗi bít cần chuyển. Ví dụ, bít 4 chuyển tới bít 21, trong khi bít 32 chuyển tới bít 4. Bảng hộp hoán vị P 67
  14. 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Cuối cùng, kết quả của hộp hoá vị P được XOR với nửa trái của khối 64 bít khởi đầu. Sau đó, nửa trái và phải được chuyển đổi cho nhau và một vòng mới được tiếp tục. 3.8. Hoán vị cuối cùng Hoán vị cuối cùng là nghịch đảo của hoán vị khởi đầu, và nó được mô tả trong bảng dưới. Chú ý rằng nửa trái và nửa phải không được tráo đổi sau vòng cuối cùng của DES, thay vào đó khối nối R16L16 được sử dụng như khối dữ liệu ra của hoán vị cuối cùng. Không có gì đưa ra ở đây; tráo đổi các nửa và dịch vòng hoán vị sẽ cho chính xác như kết quả trước, điều đó có nghĩa là thuật toán có thể được sử dụng cho cả mã hoá và giải mã. Bảng hoán vị cuối cùng: 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 3.9. Giải mã DES Sau khi thay đổi, hoán vị, XOR, và dịch vòng, chúng ta có thể nghĩ rằng thuật toán giải mã phức tạp, khó hiểu như thuật toán mã hoá và hoàn toàn khác thuật toán mã hoá. Trái lại, sự hoạt động được lựa chọn để đưa ra một đặc tính hữu ích: cùng thuật toán làm việc cho cả mã hoá và giải mã. 68
  15. Với DES, có thể sử dụng cùng chức năng để giải mã hoặc mã hoá một khối. Chỉ có sự khác nhau đó là các khoá phải được sử dụng theo thứ tự ngược lại. Nghĩa là, nếu các khoá mã hoá cho mỗi vòng là k1, k2, k3 , , k15, k16 thì các khoá giải là k16, k15, , k3, k2, k1. Giải thuật để tổng hợp khoá cho mỗi vòng cũng tương tự. Có khác là các khoá được dịch phải và số vị trí bit để dịch được lấy theo chiều ngược lại. 3.10. Phần cứng và phần mềm thực hiện DES Việc mô tả DES khá dài dòng song việc thực hiện DES rất hữu hiệu bằng cả phần cứng lẫn phần mềm. Các phép tính số học duy nhất được thực hiện là phép XOR các xâu bít. Hàm mở rộng E, các hộp S, các hoán vị khởi -1 đầu IP, hoán vị cuối cùng IP và việc tính toán các khoá k1, k2, , k16 đều có thể thực hiện được cùng lúc bằng tra bảng hoặc bằng cách nối cứng chúng thành mạch. Một phần mềm DES trên máy tính lớn IBM 3090 có thể thực hiện 32.000 phép tính mã hoá trong một giây. Với máy vi tính thì tốc độ thấp hơn. Bảng sau đưa ra kết quả thực tế và sự đánh giá cho bộ xử lý của Intel và Motorola. Bảng tốc độ của DES trên các bộ vi xử lý khác nhau Tốc độ BUS Khối DES Bộ vi xử lý ( Mhz ) ( bít ) (/giây) 8088 4.7 8 370 68000 7.6 16 900 80286 6.0 16 1.100 68020 16.0 32 3.500 68030 16.0 32 3.900 69
  16. 80286 25.0 16 5.000 68030 50.0 32 9.600 68040 25.0 32 16.000 68040 40.0 32 23.200 80486 33.0 32 40.600 (Chú ý : Phần mềm này được viết trên C và Assembler, và có thể mua được từ Utimaco-Belgium, Interleuvenlaan 62A, B-300 leuven, Belgium. Cỡ mã xấp xỉ 64K. ANSI C thực hiện chậm hơn khoảng 20%.) Một ứng dụng rất quan trọng của DES là trong giao dịch ngân hàng Mỹ. DES được dùng để mã hoá các số định danh các nhân (PIN) và việc chuyển tài khoản được thực hiện bằng máy thủ quỹ tự động (ATM). DES còn được sử dụng rộng dãi trong các tổ chức chính phủ. 3.11. Sự an toàn của DES Đã có rất nhiều sự nghiên cứu về độ dài của khoá, số vòng lặp, và thiết kế của hộp S (S-boxes). Hộp S có đặc điểm là khó hiểu, không có bất cứ sự rõ ràng nào như tại sao chúng phải như vậy. Mọi tính toán trong DES ngoại trừ các hộp S đều tuyến tính, tức việc tính XOR của hai đầu ra cũng giống như phép XOR hai đầu vào rồi tính toán đầu ra. Các hộp S chứa đựng thành phần phi tuyến của hệ là yếu tố quan trọng nhất đối với sự an toàn của hệ thống. Tính bảo mật của một hệ mã hoá đối xứng là một hàm hai tham số: độ phức tạp của thuật toán và độ dài của khoá. Giả sử rằng tính bảo mật chỉ phụ thuộc vào độ phức tạp của thuật toán. Có nghĩa rằng sẽ không có phương pháp nào để phá vỡ hệ thống mật mã hơn là cố gắng thử mọi khoá có thể, phương pháp đó được gọi là brute- force attack. Nếu khoá có độ dài 8 bít, suy ra sẽ có 28=256 khoá. Vì vậy, sẽ 70
  17. mất nhiều nhất 256 lần thử để tìm ra khoá đúng. Nếu khoá có độ dài 56 bít, thì sẽ có 256 khoá có thể sử dụng. Giả sử một Suppercomputer có thể thử một triệu khoá trong một giây, thì nó sẽ cần 2000 năm để tìm ra khoá đúng. Nếu khoá có độ dài 64 bít, thì với chiếc máy trên sẽ cần 600,000 năm để tìm ra khoá đúng trong số 264 khoá. Nếu khoá có độ dài 128 bít, thì sẽ mất 1025 năm để tìm ra khoá đúng. Vũ trụ chỉ mới tồn tại 1010 năm, vì vậy 1025 thì một thời gian quá dài. Với một khoá 2048 bít, một máy tính song song thực hiện hàng tỉ tỉ phép thử trong một giây sẽ tiêu tốn một khoảng thời gian là 10597 năm để tìm ra khoá. Lúc đó vũ trụ có lẽ không còn tồn tại nữa. Khi IBM đưa ra thiết kế đầu tiên của hệ mã hoá LUCIFER, nó có khoá dài 128 bít. Ngày nay, DES đã trở thành một chuẩn về mã hoá dữ liệu sử dụng khoá 56 bít, tức kích thước không gian khoá là 256. Rất nhiều nhà mã hoá hiện đang tranh luận về một khoá dài hơn của DES. Nhiều thiết bị chuyên dụng đã được đề xuất nhằm phục vụ cho việc tấn công DES với bản rõ đã biết. Sự tấn công này chủ yếu thực hiện tìm khoá theo phương pháp vét cạn. Tức với bản rõ X 64 bít và bản mã Y tương ứng, mỗi khoá có thể đều được kiểm tra cho tới khi tìm được một khoá k thoả mãn Ek(X)=Y (có thể có nhiều hơn một khoá k như vậy). Vào năm 1979, Diffie và Hellman tuyên bố rằng với một máy tính chuyên dụng bản mã hoá DES có thể được phá bằng cách thử mọi trường hợp của khoá trong vòng một ngày và giá của máy tính đó là 20 triệu đôla. Vào năm 1981, Diffie đã tăng lên là cần hai ngày để tìm kiếm và giá của chiếc máy tính đó là 50 triệu đôla. 3.12. Tranh luận về DES. Khi DES được đề xuất như một chuẩn mật mã, đã có rất nhiều ý kiến phê phán. Một lý do phản đối DES có liên quan đến các hộp S. Mọi tính toán liên quan đến DES ngoại trừ các hộp S đều tuyến tính, tức việc tính 71
  18. phép hoặc loại trừ của hai đầu ra cũng giống như phép hoặc loại trừ của hai đầu vào rồi tính tóan đầu ra. Các hộp S – chứa đựng thành phần phi tuyến của hệ mật là yếu tố quan trong nhất đối với độ mật của hệ thống ( Ta đã thấy trong chương 1 là các hệ mật tuyến tính – chẳng hạn như Hill – có thể dễ dàng bị mã thám khi bị tấn công bằng bản rõ đã biết). Tuy nhiên tiêu chuẩn xây dựng các hộp S không được biết đầy đủ. Một số người đã gợi ý là các hộp S phải chứa các “cửa sập” được dấu kín, cho phép Cục An ninh Quốc gia Mỹ (NSA) giải mã được các thông báo nhưng vẫn giữ được mức độ an toàn của DES. Dĩ nhiên ta không thể bác bỏ được khẳng định này, tuy nhiên không có một chứng cớ nào được đưa ra để chứng tỏ rằng trong thực tế có các cửa sập như vậy. Năm 1976 NSA đã khẳng định rằng, các tính chất sau của hộp S là tiêu chuẩn thiết kế: P0 Mỗi hàng trong mỗi hộp S là một hoán vị của các số nguyên 0,1, ,15. P1 Không một hộp S nào là một hàm Affine hoặc tuyến tính các đầu vào của nó. P2 Việc thay đổi một bít vào của S phải tạo nên sự thay đổi ít nhất là hai bít ra. P3 Đối với hộp S bất kì và với đầu vào x bất kì S(x) và S(x ⊕ 001100) phải khác nhau tối thiểu là hai bít ( trong đó x là xâu bít độ dài 6 ). Hai tính chất khác nhau sau đây của các hộp S có thể coi là được rút ra từ tiêu chuẩn thiết kế của NSA. P4 Với hộp S bất kì, đầu vào x bất kì và với e, f ∈{0,1}: S(x) ≠ S(x ⊕ 11ef00. P5 Với hộp S bất kì , nếu cố định một bít vào và xem xét giá trị của một bít đầu ra cố định thì các mẫu vào để bít ra này bằng 0 sẽ xấp xỉ bằng số mẫu ra để bít đó bằng 1.( Chú ý rằng, nếu cố định giá trị bít vào thứ nhất hoặc bít vào thứ 6 thì có 16 mẫu vào làm cho một bít ra cụ thể bằng 0 và có 16 72
  19. mẫu vào làm cho bít này bằng 1. Với các bít vào từ bít thứ hai đến bít thứ 5 thì điều này không còn đúng nữa. Tuy nhiên phân bố kết quả vẫn gần với phân bố đều. Chính xác hơn, với một hộp S bất kì, nếu ta cố định giá trị của một bít vào bất kì thì số mẫu vào làm cho một bít ra cố định nào đó có giá trị 0 (hoặc 1) luôn nằm trong khoảng từ 13 đến 19. Người ta không biết rõ là liệu có còn một chuẩn thiết kế nào đầy đủ hơn được dùng trong việc xây dựng hộp S hay không. Sự phản đối xác đáng nhất về DES chính là kích thước của không gian khoá: 256 là quá nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bi chuyên dụng đã được đè xuất nhằm phục vụ cho việc tấn công với bản rõ đã biết. Phép tấn công này chủ yếu thực hiện tìm khoá theo phương pháp vét cạn. Tức với bản rõ x 64 bít và bản mã y tương ứng, mỗi khoá đều có thể được kiểm tra cho tới khi tìm được một khoá K thảo mãn eK(x) = y. Cần chú ý là có thể có nhiều hơn một khoá K như vậy). Ngay từ năm 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra được 106khoá/giây. Một máy có thể tìm toàn bộ không gian khoá cỡ 106 trong khoảng 1 ngày. Họ ước tính chi phí để tạo một máy như vậy khoảng 2.107$. Trong cuộc hội thảo tại hội nghị CRYPTO’93, Michael Wiener đã đưa ra một thiết kế rất cụ thể về máy tìm khoá. Máy này có khả năng thực hiện đồng thời 16 phép mã và tốc độ tới 5× 107 khoá/giây. Với công nghệ hiện nay, chi phí chế tạo khoảng 10,5$/khung. Giá của một khung máy chứa 5760 chíp vào khoảng 100.000$ và như vậy nó có khả năng tìm ra một khoá của DES trong khoảng 1,5 ngày. Một thiết bị khung 10 khung máy như vậy có giá chừng 106 $ sẽ giảm thời gian tìm kiếm khoá trng bình xuống còn 3,5 giờ. 73
  20. 3.13 DES trong thực tế. Mặc dù việc mô tả DES khá dài dòng song người ta có thể thực hiện DES rất hữa hiệu bằng cả phần cứng lẫn phần mền. Các phép toán duy nhất cần được thực hiện là phép hoặc loại trừ các xâu bít. Hàm mở rộng E, các hộp S, các hoán vị IP và P và việc tính toán các giá tri K1, . ,K16 đều có thể thực hiện được cùng lúc bằng tra bảng (trong phần mền) hoặc bằng cách nối cứng chúng thành một mạch. Các ứng dụng phần cứng hiện thời có thể đạt được tốc độ mã hoá cực nhanh. Công ty Digital Equipment đã thông báo tại hội nghị CRUPTO’92 rằng họ sẽ chế tạo một xung có 50 ngàn xung có thể mã hoá với tốc độ 1 Gbít/s bằng cách xung nhịp có tốc độ 250MHz. Giá của xung này vào khoảng 300$. 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. 3.14. Các chế độ hoạt động của DES. Có 4 chế độ làm việc đã được phát triển cho DES: Chế độ chuyển mã điện tử (ECB: electronic codebook mode ), chế độ phản hồi mã (CFB: Cipher feedback mode), chế độ liên kết khối mã (CBC: Cipher block chaining mode) và chế độ phản hồi đầu ra (OFB: Output feedback mode). Chế độ ECB tương ứng với cách dùng thông thường của mã khối: với một 74
  21. dãy các khối bản rõ cho trước x1,x2,. . .( mỗi khối có 64 bít), mỗi xi sẽ được mã hoá bằng cùng một khoá k để tạo thành một chuỗi các khối bản mã y1y2 Ở chế độ CBC mỗi khối bản mã yi sẽ thực hiện phép XOR với bản rõ xi+1 sau đó mới thực hiện mã theo quy tắc yi+1 = eK(yi⊕xi+1) i ≥ 1. Việc sử dụng chế độ CBC được mô tả như sau: Chế độ CBC. Chế độ CFB cũng xuất phát từ véc tơ khởi tạo ban đầu y 0=IV có độ dài 64 bít, được mã theo quy tắc: yi=ek(yi-1) ⊕xi-1 . Giải mã của cơ chế CFB theo quy tắc: xi= ek(xi-1) ⊕ yi Chế độ OFB cũng sử dụng véc tơ khởi tạo y0=IV có độ dài 64 bít, mã theo quy tắc: z1=ek(y0) zi=ek(zi-1) với i=2,3, yi=zi ⊕ xi 75
  22. Chế độ này sinh viên tự vẽ sơ đồ Trong các chế độ OFB và CFB dòng khoá được tạo ra sẽ được cộng mod 2 với bản rõ (tức là nó hoạt động như một hệ mã dòng). OFB thực sự là một hệ mã dòng đồng bộ: dòng khoá được tạo bởi việc mã lặp véc tơ khởi tạo 64 bít (véc tơ IV). Ta xác định z0 =IV và rồi tính dòng khoá z1z2 . . . theo quy tắc zi = eK(zi-1), i≥ 1. Dãy bản rõ x1x2 . . . sau đó sẽ được mã hoá bằng cách tính yi = xi ⊕ zi,i ≥ 1. Trong chế độ CFB, ta bắt đầu với y0 = IV (là một véc tơ khởi tạo 64 bít) và tạo phần tử zi của dòng khoá bằng cách mã hoá khối bản mã trước đó. Tức zi = eK(yi-1), i ≥ 1. Cũng như trong chế độ OFB: yi = xi ⊕ zi,i ≥ 1. Việc sử dụng CFB được mô tả bên dưới (chú ý rằng hàm mã DES eK được dùng cho cả phép mã và phép giải mã ở các chế độ CFB và OFB). Chế độ CFB 76
  23. Cũng còn một số biến tấu của OFB và CFB được gọi là các chế độ phản hồi K bít (1 < K < 64 ). ở đây ta đã mô tả các chế độ phản hồi 64 bít. Các chế độ hản hồi 1 bít và 8 bít thường được dùng trong thực tế cho phép mã hoá đồng thời 1 bit (hoặc byte) số liệu. Bốn chế độ công tác có những ưu, nhược điểm khác nhau. ở chế độ ECB và OFB, sự thay đổi của một khối bản rõ xi 64 bít sẽ làm thay đổi khối bản mã yi tương ứng, nhưng các khối bản mã khác không bị ảnh hưởng. Trong một số tình huống đây là một tính chất đáng mong muốn. Ví dụ, chế độ OFB thường được dùng để mã khi truyền vệ tinh. Mặt khác ở các chế độ CBC và CFB, nếu một khối bản rõ xi bị thay đổi thì yi và tất cả các khối bản mã tiếp theo sẽ bi ảnh hưởng. Như vậy các chế độ CBC và CFB có thể được sử dụng rất hiệu quả cho mục đích xác 77
  24. thực. Đặc biệt hơn, các chế độ này có thể được dùng để tạo mã xác thực bản tin ( MAC - message authentication code). MAC được gắn thêm vào các khối bản rõ để thuyết phục Bob tin rằng, dãy bản rõ đó thực sự là của Alice mà không bị Oscar giả mạo. Như vậy MAC đảm bảo tính toàn vẹn (hay tính xác thực) của một bản tin ( nhưng tất nhiên là MAC không đảm bảo độ mật). Ta sẽ mô tả cách Bob sử dụng chế độ BCB để tạo ra một MAC. Ta bắt đầu bằng véc tơ khởi tạ IV chứa toàn số 0. Sau đó dùng chế đô CBC để tạo các khối bản mã y1,. . . ,yn theo khoá K. Cuối cùng ta xác định MAC là yn. Alice sẽ phát đi dãy các khối bản rõ x1,x2,. . . ,xn cùng với MAC. Khi Bob thu được x1. . .xn anh ta sẽ khôi phục lại y1. . .yn bằng khoá K bí mật và xác minh xem liệu yn có giống với MAC mà mình đã thu được hay không. Nhận thấy Oscar không thể tạo ra một MAC hợp lệ do anh ta không biết khoá K mà Alice và Bob đang dùng. Hơn nữa Oscar thu chặn được dãy khối bản rõ x1. . .xn và thay đổi ít nhiều nội dung thì thì chắc chắn là Oscar không thể thay đổi MAC để được Bob chấp nhận. Thông thường ta muốn kết hợp cả tính xác thực lẫn độ bảo mật. Điều đó có thể thực hiện như sau: Trước tiên Alice dùng khoá K1 để tạo MAC cho x1. . . xn . Sau đó Alice xác định xn+1 là MAC rồi mã hoá dãy x1. . .xn+1 bằng khoá thứ hai K2 để tạo ra bản mã y1. . .yn+1 . Khi Bob thu được y1. . .yn+1 , trước tiên Bob sẽ giải mã ( bằng K2) và kiểm tra xem xn+1 có phải là MAC đối với dãy x1. . .xn dùng K1 hay không. Ngược lại, Alice có thể dùng K1 để mã hoá x1. . .xn và tạo ra được y1 yn , sau đó dùng K2 để tạo MAC yn+1 đối với dãy y1. . .yn. Bob sẽ dùng K2 để xác minh MAC và dung K1 để giải mã y1. . .yn 78
  25. Chương 4 Mật mã công khai 4.1. Giới thiệu về hệ mật mã khóa công khai. 4.1.1. Giới thiệu. Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang được nghiên cứu Alice (người gửi) và Bob (người nhận) bằng cách chọn một khoá bí mật K. Sau đó Alice dùng khoá K để mã hoá theo luật eK và Bod dùng khoá K đó để giải mã theo luật giải dK . Trong hệ mật này, dK hoặc giống như eK hoặc dễ dàng nhận được từ nó vì quá trình giải mã hoàn toàn tương tự như quá trình mã, nhưng thủ tục khoá thì ngược lại. Nhược điểm lớn của hệ mật này là nếu ta để lộ eK thì làm cho hệ thống mất an toàn, chính vì vậy chúng ta phải tạo cho các hệ mật này một kênh an toàn mà kinh phí để tạo một kênh an toàn không phải là rẻ. Ý tưởng xây dựng một hệ mật khoá công khai là tìm một hệ mật không có khả năng tính toán để xác định dK nếu biết được eK. Nếu thực hiện được như vậy thì quy tắc mã eK có thể được công khai bằng cách công bố nó trong danh bạ, và khi Alice (người gửi) hoặc bất cứ một ai đó muốn gửi một bản tin cho Bob (người nhận) thì người đó không phải thông tin trước với Bob (người nhận) về khoá mật, mà người gửi sẽ mã hoá bản tin bằng cách dùng luật mã công khai eK. Khi bản tin này được chuyển cho Bob (người nhận) thì chỉ có duy nhất Bob mới có thể giải được bản tin này bằng cách sử dụng luật giải mã bí mật dK. Ý tưởng về hệ mật khoá công khai đã được Diffie và Heliman đưa ra vào năm 1976. Còn việc thực hiện hệ mật khoá công khai thì lại được Rivest. Shamin và Adieman đưa ra đầu tiên vào năm 1977. Họ đã tạo nên hệ mật RSA nổi tiếng. Kể từ đó đã có một số hệ mật được công bố, 79
  26. độ mật của từng hệ dựa trên các bài toán tính toán khác nhau. Trong đó quan trọng nhất là các hệ mật sau: • Hệ mật RSA Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích số nguyên lớn thành tích các thừa số nguyên tố. • Hệ mật xếp balô Merkle – Hellman. Hệ này dựa vào độ khó giải của bài toán tổng các tập con tổng quát (bài toán Knapsack). • Hệ mật ElGamal Hệ ElGamal dựa trên tính khó giải của bài toán Logarit rời rạc trên các trường hữu hạn. • Hệ mật Chor – Rivest Hệ mật Chor – Rivest cũng được xem như một loại hệ mật xếp balô. Tuy nhiên hệ mật này vẫn còn được coi là hệ mật an toàn. • Hệ mật trên các đường cong Elliptic. Các hệ này là biến tướng của hệ mật khác, chúng làm việc trên các đường cong Elliptic chứ không phải trên các trường hữu hạn. Hệ mật này đảm bảo độ mật vơí khoá số nhỏ hơn các hệ mật khoá công khai khác. Một chú ý quan trọng là một hệ mật khoá công khai không bao giờ có thể bảo đảm được độ mật tuyệt đối (an toàn vô điền kiện). Sở dĩ vậy vì đối phương nghiên cứu một bản mã C có thể mã lần lượt các bản rõ có thể bằng luật mã công khai eK cho tới khi anh ta tìm được một bản rõ duy nhất P bảo đảm C = eK(P). Bản rõ P này chính là kết quả giải mã của C. Bởi vậy ta chỉ nghiên cứu độ mật về mặt tính toán của hệ này. 80
  27. Một chú ý quan trọng và có ý ích khi nghiên cứu nữa là khái niệm về hàm cửa sập một chiều. Ta định nghĩa khái niệm này một cách không hình thức. Định nghĩa: Hàm f: X →Y đực gọi là hàm một chiều nếu tính y=f(x) với mọi x ∈ X là dễ nhưng việc tìm x khi biết y lại là vấn đề khó. Thực ra phát biểu trên chỉ là định nghĩa phi hình thức (do thuật ngữ “khó” được dùng đến là không định lượng và thậm chí sau này chúng ta đã biết là ngay cả khi đã định lượng bằng sự không tồn tại thuật toán giải bài toán ngược trong phạm vi đa thức thì khái niệm “khó” nêu trên có tồn tại hay không cũng chưa được ai khẳng định rõ ràng) và điều đáng tiếc hơn nữa là tất cả các hàm ứng cử viên cho khái niệm này cho đến nay chỉ mới được coi là một chiều. Chúng ta dễ dàng thống nhất được với nhau là chỉ riêng hàm một chiều là không đủ để xây dựng thành một luật mã theo kiểu công khai hàm mã hoá do vì chính bản thân chủ nhân của bức điện mật cũng gặp phải hoàn cảnh tương tự như người khác. Như vậy để có thể giải mã một cách hữu hiệu thì người giải mã phải có một “hiểu biết tuyệt mật” nào đó về khoá giải (một hiểu biết theo kiểu nếu biết nó thì cách giải dễ dàng) “hiểu biết tuyệt mật” này được gọi là cửa sập. Hàm một chiều như trên được gọi là hàm một chiều có cửa sập. Dĩ nhiên dù không biết cửa sập thì người thám mã vẫn có thể sử dụng hiểu biết về hàm f để lần lượt tính tất cả các giá trị f(x) cho mọi bản rõ x cho tới khi tìm được bản rõ thoả mãn y=f(x). Bản rõ tìm được trên chính là kết quả giải mã của y. Ngoài ra người thám mã còn có thể sử dụng nhiều phương pháp tấn công khác nhằm vào đặc thù riêng của từng hàm f để tìm ra bản rõ trong các trường hợp riêng rẽ khác chứ không nhất thiết phải giải bài toán ngược. 81
  28. Tóm lại độ an toàn của hệ mật khoá công khai không chỉ phụ thuộc vào độ khó của việc giải bài toán ngược mà tính bền của sự an toàn này còn phụ thuộc vào các phương pháp tấn công của các thám mã, vả lại như đã trình bày ở trên thì toàn bộ các hệ khoá mật công khai đang được sử dụng đều chưa được sự khẳng định về tính “khó” mà ngay cả khi đã có sự đảm bảo này thì có sự tiến bộ không ngừng của công nghệ tính toán thì hiển nhiên nhiều vấn đề chưa thể chấp nhận được trong hiện tại sẽ được chấp nhận trong tương lai. Thực tế không chỉ đối với các hệ mât khoá công khai do vậy quan niệm mới về tính an toàn tương đối mà với nó đã nẩy sinh ra các hệ mật khoá công khai đồng thời cũng đặt cho chúng ta nhiều bài toán nghiêm túc phải giải quyết khi sử dụng hệ mật này. Chương này giới thiệu cụ thể một số hệ mật công khai mà với nó sự an toàn cũng như khả năng ứng dụng của nó đã được các bộ óc vĩ đại trên thế giới thừa nhận là hệ mật khoá công khai sáng giá nhất, đó là hệ mật khoá công khai RSA. Hàm mã công khai ek của Bob phải là một hàm dễ tính toán. Song việc tính hàm ngược (tức là hàm giải mã) phải rất khó khăn (đối với bât kỳ ai không phải là Bob). Đặc tính dễ tính toán nhưng khó tính ngược thường được gọi là đặc tính một chiều. Bởi vậy điều cần thiết là e k phải là một hàm một chiều. Các hàm một chiều đóng một vai trò trọng yếu trong mật mã học: Chúng rất quan trọng trong việc xây dựng các hệ mật khoá công khai và trong nhiều lĩnh vực khác. Đáng tiếc là, mặc dù có rất nhiều hàm được coi là hàm một chiều nhưng cho tới nay vẫn không tồn tại được một hàm nào có thể chứng minh được là một hàm một chiều. Sau đây là một ví dụ về một hàm được coi là hàm một chiều. Giả sử n là tích của hai số nguyên p và q, giả sử b là một số nguyên dương. Khi đó ta xác định ánh xạ f:Zn→ Zn là f(x)=xb mod n. 82
  29. (với b và n được chọn thích hợp thì đây chính là hàm mã RSA). Để xây dựng một hệ mật khoá công khai thì việc tìm một hàm một chiều vẫn chưa đủ. Ta không muốn ek là một hàm một chiều đối với Bob vì anh ta phải có khả năng giải mã các bản tin nhận được có hiệu quả. Điều cần thiết là Bob phải có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm ngược của ek. Như vậy Bob có thể giải mã một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nào đó về K. Bởi vậy một hàm được gọi là cửa sập một chiều nếu nó là hàm một chiều và nó sẽ trở nên dễ tính ngược nếu biết một cửa sập nhất định. 4.1.2. Nhắc lại một số kiến thức số học liên quan Định nghĩa: Hàm Phi Euler của số nguyên dương n là số các số nguyên tố cùng nhau với n nhỏ hơn n.Kí hiệu θ(n) Ví dụ: θ(6)=2, θ(26)=12 Tính chất của hàm Phi euler: 1. Nếu n là số nguyên tố thì θ(n) = n-1 Ví dụ: θ(7)=6 2. Nếu p, q là 2 số nguyên tố cùng nhau thi: θ(p*q)=θ(p)*θ(q) ví dụ θ(26)=θ(2*13)=θ(2)*θ(13)=1*12=12 3. Nếu p là số nguyên tố thi: θ(pr)=(p-1)*pr-1 Định lý: Nếu a, n là nguyên tố cùng nhau thi aθ(n)=1 mod n 83
  30. 4.2. Hệ mật RSA 4.2.1. Thuật toán RSA RSA là tên viết tắt của ba tác giả Rivest, Sharmir, Adleman của trường MIT đã đề ra hệ mật mã công khai. Hệ mật này được đề xuất năm 1977, dựa trên cơ sở tính các luỹ thừa trong số học. Độ an toàn của hệ mật dựa trên độ khó của việc phân tích thành thừa số nguyên tố của các số nguyên lớn. Nhiều hệ mật khoá công khai sau này đã được phát triển nhưng đều thua kém hệ RSA. Các hệ balo cửa sập đã bị phá vỡ và cho đến nay, ngoài hệ RSA, chưa có một hệ nào khác cung cấp được cả độ an toàn và chữ ký số. a). a. Thuật toán tạo khoá Bước 1: B (người nhận) tạo hai số nguyên tố lớn ngẫu nhiên p và q (p<>q) Bước 2: B tính n=p*q và Φ (n) = (p-1)(q-1) Bước 3: B chọn một số ngẫu nhiên e (0 < e < Φ (n)) sao cho ƯCLN(b, Φ (n))=1 Bước 4: B tính d=e-1 mod Φ (n) bằng cách dùng thuật toán Euclide Bước 5: B công bố n và e trong danh bạ làm khoá công khai (public key), còn d làm khoá bí mật (private key). b). b. Thuật toán mã hoá và giải mã + Mã hoá: Bước 1: A nhận khoá công khai của B. Bước 2: A biểu diễn thông tin cần gửi thành số m (0 <= m <= n-1) Bước 3: Tính c= me mod n 84
  31. Bước 4: Gửi c cho B. + Giải mã: B giải mã bằng cách tính m=cd mod n c) Chứng minh hệ mật RSA + Cần chứng minh: m = cd mod n Thật vậy Vì ed = 1 mod Φ (n) nên ed = kΦ (n) + 1 cd mod n =(me mod n)d mod n = med mod n = mk. Φ (n)+1 mod n = (mΦ (n))k .m mod n =m(đpcm) * Ví dụ: B chọn p=5, q=7. Khi đó n=35, Φ =24 Chọn e = 5 (e và Φ nguyên tố cùng nhau). Letter m m e c=m e mod n Encrypt I 12 1524832 17 c c d m=c d mod n letter Decrypt 17 481968572106750915091411825223072000 123.3 4.2.2. Một số thuật toán triển khai trong RSA I *Thuật toán “bình phương và nhân” như sau: 85
  32. Tính xb mod n l−1 ∑ b 2i 2 ≤ ≤ Trước hết biểu diễn b= i=0 i trong đó bi = 0 hoặc 1, 0 i l-1. i) z=1 ii) cho i chạy từ giá trị l-1 về 0 z=z2 mod n Nếu bi = 1 thì z=z*x mod n iii) giá trị cần tìm chính là giá trị z cuối cùng. Như vậy sử dụng thuật toán “bình phương và nhân” sẽ làm giảm số phép nhân modulo cần thiết, để tính x mod n nhiều nhất là 2, trong l là số bít trong biểu diễn nhị phân của b. Vì l ≤ k nên có thể coi xb mod n được thực hiện trong thời gian đa thức 0(k3). * Thuật toán Ơclít mở rộng. Begin Φ g0:= ()n ; g1:=e; u0:=1; u1:=0; v0:=0; v1:=1; ≠ While gi 0 do Begin y:=gi-1 div gi ; gi+1:= gi-1 – y.gi ; ui+1:= ui-1 – y.ui ; vi+1:= vi-1 – y.vi ; i:= i+1 ; 86
  33. End; x:= vi-1; If x>0 then d:=x else d:=x+ Φ()n ; END. Vì vậy muốn xây dựng hệ RSA an toàn thì n=pq phải là một số đủ lớn, để không có khả năng phân tích nó về mặt tính toán. Để đảm bảo an toàn nên chọn các số nguyên tố p và q từ 100 chữ số trở lên. Tuy nhiên máy tính thông thường khó có thể tính toán với số nguyên lớn đến mức như vậy. Do đó cần phải có thư viện các thuật toán làm việc với các số nguyên lớn. Ta có thể lưu trữ số lớn như sau: - Phân tích số lớn thành số nhị phân. - Chia số nhị phân thành các khối 32 bít, lưu vào mảng, mỗi phần tử của mảng lưu 32 bít. Ví dụ: giả sử a là số lớn được phân tích thành số nhị phân a = a0a1 an 32 bít 32 bít 32 bít a0 a1 an * Cộng hai số lớn: Số a a0 a1 an Số b b0 b1 bn Số c c0 c1 cn cn+1 87
  34. Có một ô nhớ 32 bít để ghi số nhớ khi cộng 2 số, ban đầu ô nhớ này bằng 0. Khi cộng thì các phần tử tương ứng cộng với nhau nhớ + a0 + b0 = c0 nhớ + a1 + b1 = c1 nhớ + ai + bi = ci Để xem kết quả có nhớ hay không khi tổng ci < ai thì nhớ = 1 Mảng lưu trữ tổng bao giờ cũng lớn hơn mảng của các số hạng tổng một phần tử, phần tử mảng cuối cùng này (cn+1) lưu số nhớ. * Nhân số lớn Khi nhân 2 số 32 bit sẽ tạo ra số 64 bít nhưng hiện nay máy tính không lưu được số 64 bít, nên nó chia số 64 bít thành 2 số 32 bít (32 bít thấp và 32 bít cao). Ban đầu nhớ = 0. 32 bít 32 bít low high Như vậy khi nhân a0 x b0 + nhớ = c0 (c0 là số 64 bít), số c0 sẽ chia thành 2 số 32 bít và ghi vào mảng c phần tử c0 là số 32 bít thấp và số nhớ là 32 bít cao. Phần tử tiếp theo c1 = a0 x b1 + a1 x b0 + nhớ. c1 cũng chia làm 2 số 32 bít và ghi lại vào mảng c phần tử c 1 số 32 bít thấp và số nhớ là 32 bít cao. Tương tự như vậy ta có tổng quát sau: 88
  35. i = + ci nho∑ a k b i− k k =0 Điều cốt yếu trong việc thiết lập hệ RSA là tạo ra các số nguyên tố lớn (khoảng 100 chữ số). Quá trình thực hiện trong thực tế là : trước hết tạo ra các số ngẫu nhiên lớn, sau đó kiểm tra tính nguyên tố của nó bằng cách dùng thuật toán xác suất Monte – Carlo thời gian đa thức (như thuật toán Miller – Rabin hoặc thuật toán Solovay – Strasen). Đây là các thuật toán kiểm tra tính nguyên tố nhanh của số n trong thời gian đa thức theo log 2n, là số các bít trong biểu diễn nhị phân của n). Tuy nhiên vẫn có khả năng thuật toán kiểm tra n là số nguyên tố nhưng thực tế n vẫn là hợp số. Bởi vậy, bằng cách thay đổi thuật toán nhiều lần, có thể giảm xác suất sai số dưới một ngưỡng cho phép. Thuật toán kiểm tra số nguyên tố: thuật toán Miller – Rabin - Phân tích n – 1 = 2k . m , với m lẻ - Chọn ngẫu nhiên một số a sao cho 1 ≤ a≤ n-1 - Tính b ≡ am mod n. - Nếu b = 1 thì n là số nguyên tố và thoát. - For i:=1 to k-1 do - Nếu b = -1 thì n là số nguyên tố, nếu không b = b2 mod n. - Trả lời n là hợp số. Xác suất sai lầm của thuật toán này là < 1/4. Trong thực tế thì chưa được biết có một thuật toán kiểm tra chắc chắn số sinh ra có phải nguyên tố hay không. Một vấn đề quan trọng khác: là cần phải kiểm tra bao nhiêu số nguyên tố ngẫu nhiên (với kích thước xác định) cho tới khi tìm được một số 89
  36. nguyên tố. Một kết quả nổi tiếng trong lý thuyết số (gọi là định lý số nguyên tố) phát biểu rằng: số các số nguyên tố không lớn hơn N xấp xỉ bằng N/lnN. Bởi vậy, nếu p được chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1/lnp. 4.2.3. Độ an toàn của hệ mật RSA. a.Bài toán phân tích số và việc phá hệ mật RSA. Cách tấn công dẽ thấy nhất đối với hệ mật RSA là người thám mã sẽ cống gắng phân tích n ra thừa số nguyên tố n=p*q và khi đó anh ta dễ dàng tính được ϕ(n)=(p-1)(q-1) và do đó tìm được thông tin cửa sập d tương ứng với thông tin mã hoá E bằng thuật toán Euclide. Như vậy chúng ta thấy ngay rằng việc phá hệ mật RSA là “dễ hơn” bài toán phân tích số nguyên ra thừa số nguyên tố tuy nhiên cũng chưa có một kết quả nào chỉ ra rằng bài toán phân tích số là thực sự khó hơn cho nên người ta thường thừa nhận rằng bài toán phá hệ RSA là tương đương với bài toán phân tích số nguyên thành thừa số người. Để đảm bảo tính khó phân tích ra thừa số của n=p*q thì yêu cầu đầu tiên là p,q là các số nguyên tố lớn xấp xỉ bằng nhau và là số nguyên tố “mạnh “. Khái niệm “mạnh” ở đây chỉ bắt nguồn từ ý nghĩa khó phân tích do vậy nó sẽ được bổ xung cùng với kết quả có được của khả năng phân tích số. Nói một cách khác là khái niệm “mạnh” bao gồm sự loại trừ các lớp số nguyên tố mà với chúng tồn tại thuật toán phân tích hiệu quả, chúng ta có thể biết đến một khái niệm sơ khai của tính “mạnh” đó là các số nguyên tố p mà p-1 và p+1 có chứa thừa số nguyên tố lớn. b.Việc tấn công hệ mật RSA khác phương pháp phân tích số. Một kết quả thú vị là một thuật toán bất kỳ để tính số mũ giải mã d đều có thể được dùng như một chương trình con trong thuật toán xác suất kiểu Las Vegas để phân tích n. 90
  37. Như vậy mặc dù rằng nếu d bị lộ thì việc phân tích n cũng không còn ý nghĩa theo quan điểm phá hệ mật tuy nhiên kết quả trên dù sao cũng cho ta một thuật toán phân tích số n khi biết d với xác suất thành công không quá ½ của mỗi lần chọn số ngẫu nhiên làm đầu vào cho thuật toán. 4.2.4. Các thuật toán phân tích số. Trong phần này giới thiệu một số thuật toán phân tích số nguyên được coi là “mạnh nhất” theo nghĩa thời gian tính tốt nhất hiện nay. Việc trình bày của chúng tôi dựa trên quan điểm không phải là đưa ra thuật toán chi tiết nhằm mục đích phân tích số nguyên mà chủ yếu nêu ra ý tưởng của thuật toán và quan trọng nhất là đưa ra thông số về thời gian tính của chúng nhằm chứng minh cho kích thước tối thiểu của các modulo được sử dụng trong mật mã theo dạng tích hai số nguyên tố lớn. Các thuật toán được kể đến bao gồm thuật toán sàng bậc hai, thuật toán phân tích trên đường cong Elliptic, thuật toán sàng trường số nhưng do hai thuật toán sau đều cần phải có kiến thức bổ trợ khá cồng kềnh về đại số hiện đại vả lại điều kiện về tài liệu lại không đủ chi tiết nên bài giảng này chỉ trình bày thuật toán sàng bậc hai và cũng dừng ở những nét chính yếu nhất. Các thuật toán phân tích số: * Thuật toán sàng Eratosthenes Đây là thuật toán có tính phổ thông, với n có ước nhỏ thì việc áp dụng thuật toán này là hiệu quả. Thời gian tính của nó là 0( n ). Thuật toán được mô tả như sau: i) p=1 ii) p=p+1 iii) Tính r = n mod p. Nếu r > 0 quay về bước 2. Ngược lại p là ước của N, dừng chương trình. 91
  38. * Thuật toán sàng đồng dư Thuật toán được mô tả như sau: ∈ * i) Lấy ngẫu nhiên hai số a và b, với a,b Zn ii) Kiểm tra gcd((a-b) mod n,n) >1 hoặc gcd((a+b) mod n,n)>1 - Nếu đúng thì gcd((a-b) mod n,n) >1 hoặc gcd((a+b) mod n,n)>1 là ước của n dừng chương trình. - Ngược lại quay về i Phân tích thuật toán này dưới góc độ xác suất: Cho p là ước nguyên tố nhỏ nhất của n, thế thì cần có tối thiểu bao nhiêu cặp a,b được xét đến để xác suất có ít nhất một cặp trong số đó thoả mãn ((a ± b) mod p) ≡ 0 ≥ 0.5 ? Bài toán trên được gọi là bài toán “trùng ngày sinh” và số m tối thiểu cần tìm trong bài toán sẽ là m ≈ c.p, với c là một hằng số tính được nào đó. Thuật toán có thể thành công với xác suất >0.5, sau không quá m bước. Bằng cách duyệt dần thì thời gian của thuật toán không khác gì thời gian của phép sàng. Tác giả J.M.Pollard đã sử dụng một phương pháp còn gọi là “phương pháp δ ”. Chỉ cần thông qua m bước có thể duyệt được m cặp khác nhau như đã nêu trên trong thuật toán. * Thuật toán Pollard Thuật toán hiệu quả trong việc tìm các ước nhỏ là thuật toán dựa vào phương pháp δ và được gọi là thuật toán Pollard. Thời gian tính của thuật toán này chỉ còn là 0( n ). . Với p là ước nguyên tố nhỏ nhất của n. Trong trường hợp tồi nhất (p ≈ n ) thì thời gian tính của thuật toán cũng chỉ là 4 n Phương pháp δ của Pollard: 92
  39. Tìm hai phần tử đồng dư modilo p (a ≡ ± b mod p) nhưng không đồng dư modulo n. Lúc này p sẽ là ước của gcd(n, (a mb) mod n). Có thể mô tả thuật toán như sau: Chọn dãy giả ngẫu nhiên {xi mod n, i=1,2, } được xác định như sau: ≡ 2 ≠ ≠ xi+1 (xi + a) mod n với a 0 và a -2 còn giá trị đầu x0 tuỳ ý. Thuật toán: i) i=0 ii) i:=i+1 iii) Xét gcd((x2i – xi) mod n,n) > 1 - Nếu đúng ta có p = gcd((x2i – xi) mod n,n). Dừng chương trình - Ngược quay về bước ii) Chúng ta đi phân tích thời gian của thuật toán: ≡ 2 2 ≡ 2 2 x2i – xi (x2i-1 + a) – (x i-1 + a) x 2i-1 – x i-1) ≡ ≡ (x2i-1 – xi-1)(x2i-1+ xi-1) ≡ (x2i-1 + xi-1)(x2i-2 + xi-2) (xi + x0)(xi – x0) Tại bước thứ i chúng ta xét đến i+1 cặp khác nhau và cũng dễ dàng nhận ra rằng các cặp được xét trong mọi bước là không giống nhau, do đó hiển nhiên với p bước chúng ra đã có p cặp khác nhau được xét đến và như đã phân tích ở trên. Thuật toán thành công với xác suất > 0.5 hay thuật toán của Pollard được thực hiện trong 0( n ) bước. * Thuật toán p-1 Thuật toán p – 1 của Pollard là thuật toán phân tích số nguyên n dựa vào phân tích của p – 1với p là một ước nguyên tố của n. Đây là một thuật toán có tác dụng nếu ta biết được các ước nguyên tố của một thừa số p của 93
  40. n nói chung và đặc biệt nếu n có một thừa số nguyên tố p mà p – 1 chỉ gồm những ước nguyên tố nhỏ nhất thì thuật toán có hiệu quả. Thuật toán này chỉ có hai đầu vào là n số nguyên lẻ cần được phân tích và một số b. Các bước của thuật toán i) Đầu vào là hai số n và b ii) a:=2 iii) for j:=2 to b do a: = aj mod n iv) d = gcd(a-1,n) v) if 1 < d < n then d là một thừa số của n else không tìm được thừa số của n. Ví dụ: Giả sử n = 15770708441 và b=180. áp dụng thuật toán p – 1 ta có: + a = 1160221425 + d = 135979 Thực tế phân tích đầy đủ n thành các ước nguyên tố là: N = 15770708441 =135979 x 115979 Phép phân tích sẽ thành công do 135978 chỉ gồm các thừa số nguyên tố nhỏ: 135978 = 2 x 3 x 131 x 173 Trong thuật toán có (b-1) luỹ thừa theo modulo, mỗi luỹ thừa cần nhiều nhất là 2log2b phép nhân modulo dùng thuật toán bình phương và nhân. Việc tìm ước chung lớn nhất có thể được thực hiện trong thời gian 0((log n)3) bằng thuật toán Ơclít. Bởi vậy, độ phức tạp của thuật toán là 0(b log b (log n)2 + (logn)3) 94
  41. Nếu b là 0((log n)i với một số nguyên i xác định nào đó thì thuật toán thực sự là thuật toán thời gian đa thức, tuy nhiên với phép chọn b như vậy, xác suất thành công sẽ rất nhỏ. Mặt khác, nếu tăng kích thước của b lên thật lớn thì thuật toán sẽ thành công nhưng nó sẽ không nhanh hơn phép chia thử. Điểm bất lợi của thuật toán này là nó yêu cầu n phải có ước nguyên tố p sao cho p - 1 chỉ có các thừa số nguyên tố bé. Ta có thể xây dựng được hệ mật RSA với modulo n = p.q hạn chế được việc phân tích theo phương pháp này. Trước tiên tìm một số nguyên tố lớn p1 sao cho p = 2p1 + 1 cũng là một số nguyên tố và một số nguyên tố lớn q1 sao cho q = 2q1 + 1 cũng là một số nguyên tố. Khi đó modulo của RSA n = p.q sẽ chống được cách phân tích theo phương pháp p – 1. * Thuật toán p ± 1 Thuật toán p ± 1 của Williams cũng dựa vào kết quả phân tích của p ± 1 với p là một ước nguyên tố của n. Để tiện nghiên cứu phương pháp p ± 1, trước hết điểm lại một số kết quả của chính liên quan đến dãy Lucas Định nghĩa 1: (dãy Lucas) Cho a, b là hai nghiệm của phương trình x2 – px + q = 0 (1) m− m = a b =m + m Ký hiệu u và vm a b (2) m a− b Các dãy {um}, {vm}, m = 0, 1, 2, gọi là dãy Lucas của phương trình (1) Ngược lại phương trình (1) gọi là phương trình đặc trưng của dãy (2) Tính chất 1: Nếu i là ước của j thì ui ước của uj Tính chất 2: Ta có u0 = 0, u1 = 1, v0 = 2, v1 = p và ∀ m > 1 thì um và vm được tính theo công thức sau: 95
  42. m u+ v +  p− Q  u v  m1 m 1  =   1 1  um v m  1 0  u0 v 0  2 2 Định lý: {um} là dãy Lucas của phương trình (1) với p – 4Q = d ∆ có ∆ không có ước chính phương (hay bình phương tự do). Nếu p không là ∆  ∆  − ≡ ước của 4Q thì up   0mod p ở đây   là ký hiệu Legendre p  p  Thuật toán p ± 1 log i) log2 n qk Q = 2 q k , i = 1, j = 0 * ii) Lấy ∆ không có ước chính phương ngẫu nhiên trong Zn . Tìm R, S nguyên sao cho R2 – 4S = ∆ d2 với d ≠ 0 nào đó. Xét gcd( ∆ Q, n) > 1 - Nếu đúng ta có ước của n là gcd( ∆ Q, n). Dừng chương trình ≡ - Ngược lại tính b u0 mod n ( phần tử thứ Q trong dãy Lucas của phương trình x2 – Rx +S = 0) iii) Xét đẳng thức b = 0 - Nếu đúng chuyển sang (iv) - Ngược lại chuyển sang (vi) < iv) Xét jlogq n - Nếu đúng j = j + 1, Q = Q/q quay về (iii) - Ngược lại chuyển sang (v) v) Xét i < k - Nếu đúng thì : i = i+1, j = 0 ≠ - Nếu b 1 thì Q = Q.qi quay về (iv) 96
  43. - Ngược lai quay về (i) vi) Xét gcd(b,n) > 1 - Nếu đúng có ước của n là gcd(b,n). Dừng chương trình - Ngược lại quay về (iv) ∆  Ta thấy rằng để vét hết các khả năng p + 1 (trong trường hợp   = p  ∆  -1 và p -1 (trong trường hợp   = 1)) là ước của Q. Việc xét đẳng thức b = p  0 trong mỗi bước, nếu sai nhằm đảm bảo cho ta b không là bội của n và nếu p + 1 hoặc p – 1 là ước của Q thì theo các kết quả ở tính chất và định lý trên cho ta b là bội của p và như vậy gcd(b,n) là ước thực sự của n. Tóm lại, thuật toán trên rõ ràng hiệu quả trong cả hai trường hợp p + 1 hoặc p – 1 chỉ gồm các ước nguyên tố nhỏ, tuy nhiên căn cứ vào công thức tính các giá trị của dãy Lucas, ta thấy ngay rằng hệ số nhân của thuật toán này là lớn hơn nhiều so với thuật toán của Pollard trong trường hợp cùng phân tích được n với ước p của nó có p – 1 chỉ gồm các ước nhỏ bởi vì thay cho việc tính một luỹ thừa thông thường thì thuật toán của Lucas phải tính một luỹ thừa của một ma trận Từ thuật toán trên, ta có thể kết luận: - p phải là một số lớn - Các ước phải có kích thước xấp xỉ nhau - Các ước không được xấp xỉ nhau về giá trị - Ước nguyên tố p của modulo n không được có p + 1 hoặc p – 1 phân tích hoàn toàn ra các thừa số nguyên tố nhỏ 97
  44. - Không có số Lucas ui = 0 mod p với i bé đối với các phương trình đặc trưng có biểu thức ∆ nhỏ - P phải có khoảng cách luỹ thừa 2 đủ lớn. * Phương pháp Ơ le: Phương pháp Ơ le chỉ có tác dụng đối với một lớp số nguyên đặc biệt cụ thể là chỉ dùng phân tích cho các số nguyên là tích của các số nguyên tố cùng dạng r2 + DS2. Thuật toán dựa trên cơ sở là đẳng thức của Legendre (còn gọi là đẳng thức Diophantus) Đẳng thức Diophantus: (x2 + Ly2)(a2 + Lb2) = (x ± Lyb)2 + L(xb mya)2 Chứng minh: Biến đổi vế phải đẳng thức trên: (xa ± Ly2) + L(xb mya)2 = x2a2 ± 2Labxy + L2y2b2 + Lx2b2 m2Labxy + Ly2a2 = a2(x2 + Ly2) + Lb2(Ly2 + x2)) = (a2 + Ly2)(x2 + Ly2) Sau đó Ơ le đã chứng minh được rằng: Định lý: Nếu n có hai biểu diễn khác nhau n = r2 + Ls2 = u2 + Lv2 với gcd() = 1 thì n phân tích được thành tích của hai thừa số n=p.q cùng dạng p = x2 + Ly2 và q= a2 + Lb2 Như vậy điều kiện nhận biết số nguyên n là tích của hai ước số đều có dạng r2 + Ls2 là n cũng có dạng đó và có hai biểu diễn khác nhau theo dạng trên. Thứ nhất, ta thấy rằng từ n = r2 + Ls2 nên để tìm biểu diễn theo dạng đã nêu trên của n ta có thể tiến hành bằng cách duyệt theo s cới nhận biết n – Ls2 là số chính phương. Với phương pháp dò tìm trên thì giá trị s tối đa n  cần xét đến là   và đây cũng là cận tính toán của thuật toán Ơle. b  98
  45. Giả sử đã tìm được hai biểu diễn khác nhau của n là: n = r 2 + Ls2 = u2 + Lv2. Không mất tính tổng quát ta coi r, s, u, v không âm và r > u. Khi đó giải hệ phương trình sau đây ta tìm được x, y, a, b xa+ Lyb = rv  xa− Lyb =± u  xb− ya =± s xb+ ya = v Dấu trừ của phương trình (2) và 93) được lấy khi vế trái tương ứng âm. Một điều khó khăn khi thực hiện thuật toán phân tích Ơle là vấn đề xác định tham số L. Nhìn chung việc thực hiện thuật toán Ơlư chỉ áp dụng cho những số n mà bản thân nó đã biết một biểu diễn. Tuy nhiên lại có thể bằng cách dò tìm L chúng ta có thể thành công trong việc phân tích. Như vậy thuật toán nay chỉ dùng cho một lớp số đặc biệt nên khó được dùng để tạo nên một tiêu chuẩn thích hợp cho các modulo hợp số. * Phương pháp sàng Dyxon và sàng bậc hai Trong phần này giơi thiệu thuật toán phân tích hai số nguyên được coi là mạnh nhất theo nghĩa thời gian tính tốt nhất hiện nay. ý tưởng của một loạt khá lớn các thuật toán phân tích số như phương pháp phân tích các dạng chính phương Danien Shaks, phương pháp đặc biệt của Ơle, phương pháp khai triển liên phân số của Morrison và Brillhart, phương pháp sàng bậc hai của Pomerance, Dixon là cố tìm được x ≠ ± y mod n sao cho x2 ≡ y2 mod n, còn kỹ thuật tìm cụ thể như thế nào thì chính là nội dung riêng của từng thuật toán Thuật toán Dixon được thực hiện như sau: 99
  46. - Sử dụng một tập B chứa các số nguyên tố bé và gọi là cơ sở phân tích - Chọn một vài số nguyên x sao cho tất cả các thừa số nguyên tố của x2 mod n nằm trong cơ sở B, - Lấy tích của một vài giá trị x sao cho mỗi nguyên tố trong cơ sở được sử dụng một số chẵn lần. Chính điều này dẫn đến một đồng dư thức dạng mong muốn x2 ≡ y2 mod n mà ta hy vọng sẽ đưa tới việc phân tích n và suy ra gcd(x-y,n) là một ước của n. Ví dụ: Giả sử chọn: n = 15770708441, B = {2, 3, 5, 7, 11, 13} Và chọn ba giá trị x là : 8340934156, 12044942944, 2773700011 Xét ba đồng dư thức: 83409341562 ≡ 3x7 (mod n) 120449429442 ≡ 2x7x13 (mod n) 27737000112 ≡ 2x3x13 (mod n) Lấy tích của ba đồng dư thức trên: (8340934156 x 12044942944 x 2773700011)2 ≡ (2 x 3 x 7 x 13)2 mod n Rút gọn biểu thức bên trong dấu ngoặc trong modulo đó ta có: 95034357852 ≡ 5462 (mod n) Suy ra x = 9503435785  y = 546 Tính gcd(x-y,n) = gcd(9503435785 – 546, 15770708441) = 1157759 100
  47. Ta nhận thấy 115759 là một thừa số của n Giả sử: - B = {p1, , pB} là một cơ sở phân tích - C lớn hơn B một chút (chẳng hạn C = B + 10) α α α - Có đồng dư thức: 2 ≡ 1j 2 j Bj (mod n) xj p1 p 2 p B Với 1≤ j≤ C, mỗi j, xét véc tơ: =α α α ∈ B aj(1 j mod 2, 2 j mod 2, , Bj mod 2) ( Z 2 ) Nếu có thể tìm được một tập con các aj sao cho tổng theo modulo 2 là vectơ (0, 0, ,0) thì tích của các xj tương ứng sẽ được sử dụng mỗi nhân tử trong B một số chẵn lần. Ví dụ: Xét lại ví dụ trên n = 15770708441, B = {2, 3, 5, 11, 13} Cho ba vectơ a1, a2, a3 : A1 = (0, 1, 0, 1, 0, 0) A2 = (1, 0, 0, 1, 0, 1) A3 = (1, 1, 0, 0, 0, 1) Suy ra a1 + a2 + a3 = (0, 0, 0, 0, 0, 0) mod 2 Trong trường hợp này nếu C B, sự phụ thuộc tuyến tính này 101
  48. nhất định phải tồn tại và ta có thể dễ dàng tìm được bằng phương pháp loại trừ Gaux. Lý do giải thích tại sao lấy C > B + 1 là do không có gì đảm bảo để một đồng dư thức cho trước bất kỳ sẽ tạo được phân tích n. Người ta chỉ ra rằng khoảng 50% thời gian thuật toán cho ra x ≡ ± y (mod n). Tuy nhiên nếu C > B + 1 thì có thể nhận được một vài đồng dư thức như vậy. Hy vọng là ít nhất một trong các đồng dư thức kết quả sẽ dẫn đến việc phân tích n. Vấn đề cần đặt ra là phải làm như thế nào để nhận được các số nguyên 2 xj mà các giá trị xj mod n có thể phân tích hoàn toàn trên cơ sở B. Một số phương pháp có thể thực hiện được điều đó. Biện pháp sàng bậc hai do   Pomerance đưa ra dùng các số nguyên dạng xj = j + n  , j = 1, 2, dùng để xác định các xj phân tích được trên B. Nếu B là một số lớn thì thích hợp hơn cả là nên phân tích số nguyên xj trên B. Khi B càng lớn thì càng phải gom nhiều đồng dư thức hơn trước khi có thể tìm ra một số quan hệ phụ thuộc và điều này dẫn đến thời gian thực hiện cỡ 0(e(1+ 0(1) lnn ln ln n ) ) Với 0(1) là một hàm tiến tới 0 khi n tiến tới ∞ Thuật toán sàng trường số là thuật toán cũng phân tích n bằng cách xây dựng một đồng dư thức x2 ≡ y2 mod n, song nó lại được thực hiện bằng cách tính toán trên vành các số đại số. * Thời gian tính các thuật toán trên thực tế Thuật toán đường cong Elliptic hiệu quả hơn nếu các thừa số nguyên tố của n có kích thước khác nhau. Một số rất lớn đã được phân tích bằng 102
  49. n thuật toán đường cong Elliptic là số Fermat (22 − 1) ( được Brent thực hiện năm 1988). Thời gian tính của thuật toán này được tính là 0(e(1+ 0(1) 2lnp ln ln p ) ) p là thừa số nguyên tố nhỏ nhất của n Trong trường hợp nếu hai ước của n chênh lệch nhau nhiều thì thuật toán đường cong Elliptic tỏ ra hơn hẳn thuật toán sàng bậc hai. Tuy nhiên nếu hai ước của n xấp xỉ nhau thì thuật toán sàng bậc hai nói chung trội hơn thuật toán đường cong Elliptic. Sàng bậc hai là một thuật toán thành công nhất khi phân tích các modulo RSA với n = p.q và p, q là các số nguyên tố có cùng kích thước. Năm 1983, thuật toán sàng bậc 2 đã phân tích thành công số có 69 chữ số, số này là một thừa số của 2251 – 1 (do Davis, Holdredye và Simmons thực hiện). Đến năm 1989 đã có thể phân tích được các số có tới 106 chữ số theo thuật toán này ( do Lenstra và Manasse thực hiện), nhờ phân bố các phép tính cho hàng trăm trạm làm việc tách biệt ( người ta gọi phương pháp này là “Phân tích thừa số bằng thư tín điện tử”). Các số RSA – d với d là chữ số thập phân của số RSA (d = 100 ÷ 500) được công bố trên Internet như là sự thách đố cho các thuật toán phân tích số. Vào 4/1994 Atkins, Lenstra và Leyland đã phân tích được một số 129 chữ số, nhờ sử dụng sàng bậc hai. Việc phân tích số RSA – 129 trong vòng một năm tính toán với máy tính có tốc độ 5 tỷ lệnh trên 1 giây, với công sức của hơn 600 nhà nghiên cứu trên thế giới. Thuật toán sàng trường số là một thuật toán mới nhất trong ba thuật toán. Thuật toán sàng trường số cũng phân tích số nguyên n bằng việc xây dựng đồng dư thức x2 ≡ y2 mod n. Nhưng việc thực hiện bằng cách tính toán 103
  50. trên các vành đại số Sàng trường số vẫn còn trong thời kỳ nghiên cứu. Tuy nhiên theo dự đoán thì phải chứng tỏ nhanh hơn với các số có trên 125 chữ số thập phân. Thời gian tính của thuật toán sàng trường số là 3 3 2 0(e(1.92− 0(1)) lnn (lnln n ) ) Việc trình bày các thuật toán phân tích trên để hiểu rõ một phần nào các biện pháp tấn công vào RSA để có thể xây dựng một hệ mật an toàn hơn. Từ các thuật toán trên yêu cầu đối với p và q nên thoả mãn: - Các số nguyên p và q phải xấp xỉ nhau về độ dài nhưng không được xấp xỉ nhau về độ lớn. - Các số p ± 1 và q ± 1 phải có ít nhất một thừa số nguyên tố lớn - Phải có khoảng luỹ thừa 2 đủ lớn - Giá trị F = gcd(p ± 1, q ± 1) không được lớn hơn 3 n - Các số p và q phải là các số có ít nhất 100 chữ số thập phân Nhận xét đầu để ngăn chặn khả năng tấn công bởi thuật toán sơ đẳng nhất, đó là thuật toán sàng, đồng thời như các phân tích trên thì đã đưa bài toán phân tích về trường hợp khó giải nhất, của ngay thuật toán được đánh giá là có triển vọng nhất đó là thuật toán dựa vào phương pháp trường số. Nhận xét thứ hai dựa vào khả năng của thuật toán Pollard và thuật toán Williams mà khả năng đó phụ thuộc chủ yếu vào việc các số p ± 1 và q ± 1 phân tích được hoàn toàn qua các số nguyên tố trong tập B. Trong tập B có thể là tập các số nguyên tố nhỏ hơn 32 bits. Ngược lại cũng có thể sử dụng tập B lớn hơn. Do đó nhận xét này cũng hợp lý. Việc có một tham số công khai như số mũ lập mã e chắc chắn phải cung cấp thêm thông tin cho bài toán phân tích số. Do đó cần tìm hiểu mức 104
  51. độ ảnh hưởng của thông tin này để xây dựng nên một yêu cầu với số mũ e này và phần nào đó có tính đối ngẫu liên quan cả số mũ giải mã d. Để cho một số nguyên tố đáp ứng tiêu chuẩn về độ dài thì đối với hệ mật sử dụng bài toán logarit cần các số nguyên tố có độ dài khoảng gấp rưỡi so với các số nguyên tố dùng cho loại hệ mật dựa trên bài toán phân tích số. Nếu có được một thuật toán nhanh (thuật toán xác suất như Rabin – Miller) thì thời gian tính cũng phải cỡ 0(n3) ( với n là độ dài khoảng gấp rưỡi so với các số nguyên tố trong các số nhỏ hơn n theo Direcle là ln n Π()n ≈ , do vậy khả năng tìm được số nguyên tố 521 bít so với một số n nguyên tố 350 bit lâu hơn gấp nhiều lần. Thiết kế một hệ mật sử dụng bài toán logarit rời rạc chỉ cần đúng một số nguyên tố trong khi để có một tính năng tương đương, thì hệ mật dựa trên bài toán phân tích số nguyên ra thừa số nguyên tố cần đến 2k số nguyên tố cho hệ thống có k người sử dụng. Các số nguyên tố cần dùng cho hệ mật thứ hai đòi hỏi phải có các ước nguyên tố lớn, dẫn đến khả năng tìm kiếm số nguyên tố cũng sẽ khó khăn hơn nhiều so với hệ mật thứ nhất. 4.3. Một số hệ mật mã công khai khác Trong chương này ta sẽ xem xét một số hệ mật khoá công khai khác. Hệ mật Elgamal dựa trên bài toán logarithm rời rạc là bài toán được dùng nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dành nhiều thời gian để thảo luận về bài toán quan trọng này. Ở các phần sau sẽ xem xét sơ lược một số hệ mật khoá công khai quan trọng khác bao gồm các hệ thống loại Elgamal dựa trên các trường hữu hạn và các đường cong elliptic, hệ mật xếp ba lô Merkle-Helman và hệ mật McElice. 105
  52. 4.3.1.Hệ mật Elgamal và bài toán logarithm rời rạc. Hệ mật Elgamal được xây dựng trên bài toán logarithm rời rạc . Chúng ta sẽ bắt đầu bằng việc mô tả bài toán bài khi thiết lập môi trường * hữu hạn Zp, p là số nguyên tố (Nhớ lại rằng nhóm nhân Zp là nhóm cyclic * và phần tử sinh của Zp được gọi là phần tử nguyên thuỷ). Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết p phải có ít nhất 150 chữ số và (p-1) phải có ít nhất một thừa số nguyên tố lớn. Lợi thế của bài toán logarithm rời rạc trong xây dựng hệ mật là khó tìm được các logarithm rời rạc, song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu quả theo thuật toán “bình phương và nhân”. Nói cách khác, luỹ thừa theo modulo p là hàm một chiều với các số nguyên tố p thích hợp. Elgamal đã phát triển một hệ mật khoá công khai dựa trên bài toán logarithm rời rạc. Bài toán logarithm rời rạc được phát biểu như sau: I = (p,α,β) trong đó p là số nguyên tố, α ∈ Zp là phần tử nguyên thuỷ , β ∈ Zp* Mục tiêu:Hãy tìm một số nguyên duy nhất a, 0 ≤ a ≤ p-2 sao cho: αa ≡ β (mod p) Ta sẽ xác định số nguyên a bằng logα β Hệ mật mã Elgamal là một hệ không tất định vì bản mã phụ thuộc vào cả bản rõ x lẫn giá trị ngẫu nhiên k do Alice chọn. Bởi vậy, sẽ có nhiều bản mã được mã từ cùng bản rõ. Hệ mật khoá công khai Elgamal trong Zp* 106
  53. a. Tạo khóa: Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho α ∈ Zp* là phần tử nguyên thuỷ.Giả sử P = Zp* , C = Zp* × Zp* . Ta định nghĩa: K = {(p, α,a,β): β ≡ αa (mod p)} Các giá trị p, α,β được công khai, còn a là khóa bí mật b. Mã: Chọn một số ngẫu nhiên bí mật k ∈ Zp-1, ta xác định: ek (x,k) = (y1 ,y2 ) trong đó k y1 = α mod p k y2 = xβ mod p c. Giải mã * với y1 ,y2 ∈ Zp ta xác định: a -1 dk(y1 ,y2 ) = y2 (y1 ) mod p Sau đây sẽ nmô tả sơ lược cách làm việc của hệ mật Elgamal .Bản rõ x k k được “che dấu” bằng cách nhân nó với β để tạo y2 . Giá trị α cũng được gửi đi như một phần của bản mã. Bob – người biết số mũ bí mật a có thể k k k tính được β từ α . Sau đó anh ta sẽ “tháo mặt nạ” bằng cách chia y2 cho β để thu được x. Ví dụ: Cho p = 2579, α = 2, a = 765. Khi đó β = 2765 mod 2579 = 949 Bây giờ ta giả sử Alice muốn gửi thông báo x = 1299 tới Bob. Giả sử số ngẫu nhiên k mà cô chọn là k = 853. Sau đó cô ta tính 853 y1 = 2 mod 2579 107
  54. = 435 y2 = 1299 × 949853 mod 2579 = 2396 Khi đó Bob thu được bản mã y = (435,2396), anh ta tính x = 2396 × (435765)-1 mod 2579 = 1299 Đó chính là bản rõ mà Alice đã mã hoá. 4.3.2 Mật mã Balô. 4.3.2.1. Cơ sở của mật mã balô Mật mã balô xuất phát từ bài toán tổng tập con tổng quát (bài toán balô- hay bài toán knapsack). Bài toán được phát biểu như sau: Cho dãy các số dương S={s1, s2, ., sn} và một số dương C. Hỏi có tồn tại một tập con nằm trong S sao cho tổng tập con đó bằng C. (Hỏi có tồn tại một véc tơ nhị phân x=(x1, x2, , xn) sao cho C=∑xi.si (i=1 n)) Đây là bài toán khó có thời gian là hàm mũ O(2n). Nếu S là dãy siêu tăng thì bài toán trên giải được với thời gian tuyến tính O(n). Định nghĩa: Dãy S gọi là siêu tăng nếu mọi si>∑sj (j=1, i-1) (tức là phần tử đứng sau lớn hơn tổng các phần tử đứng trước nó) Khi đó bài toán tổng tập con được phát biểu như sau: 108
  55. Cho dãy siêu tăng S={s1, s2, ., sn} và một số dương C. Hỏi có tồn tại một tập con nằm trong S sao cho tổng tập con đó bằng C. (Hỏi có tồn tại một véc tơ nhị phân x=(x1, x2, , xn) sao cho C=∑xi.si (i=1 n)) Khi đó bài toán được giải như sau: For i:=n downto 1 do Begin If C>=si then xi=1 Else xi:=0; C:=C-xi.si; End; If C=0 then “bài toán có đáp án là véc tơ x” Else “bài toán không có đáp án”; Áp dụng bài toán này ta sử dụng dãy S siêu tăng làm khóa bí mật. Sau đó tác động lên dãy S để biến đổi thành một dãy bất kỳ, và công khai dãy này là khóa công khai. Ta có hệ mật mã balô như sau: 4.3.2.2. Thuật toán: * Tạo khóa: - Chọn dãy siêu tăng S={s1, s2, , s3} - Chọn p sao cho p>∑si (i=1 n) - Chọn a sao cho 1 khóa công khai là t, khóa bí mật là: a, p, S 109
  56. * Mã: Chọn bản rõ là dãy nhị phân x=(x1, x2, , xn) Tính bản mã y=∑xi.ti (i=1 n) Gửi bản mã y * Giải mã: - Tính C=a-1.y mod p - Giải bài toán ba lô với S là dãy siêu tăng và số dương C để tìm bản rõ x * Chứng minh tính đúng của hệ mật mã ba lô (Bạn đọc tự chứng minh) Ví dụ: (Như một bài tập). 110
  57. Chương 5 Các sơ đồ chữ kí số 5.1. Giới thiệu. Điều đầu tiên cần phân biệt rõ ràng 2 khái niệm chữ ký điện tử và chữ ký số. Trên môi trường mạng, bất cứ dạng thông tin nào được sử dụng để nhận biết một con người đều được coi là chữ ký điện tử. Ví dụ 1 đoạn âm thanh hoặc hình ảnh được chèn vào cuối e-mail, đó cũng là chữ ký điện tử. Chữ ký số là một dạng chữ ký điện tử, an toàn nhất và cũng được sử dụng rộng rãi nhất. Chữ ký này hình thành dựa trên kỹ thuật mã khoá công khai (PKI), theo đó mỗi người sử dụng cần có một cặp khóa bao gồm khóa bí mật và công khai. Người chủ chữ ký sử dụng khoá bí mật để tạo chữ ký số (trên cơ sở kết hợp với nội dung thông điệp dữ liệu), ghép nó với thông điệp dữ liệu và gửi đi. Người nhận dùng mã công khai giải mã chữ ký số để biết được người đó là ai. Tất cả quy trình ký và giải mã chữ ký số đều được thực hiện bằng phần mềm. Điểm quan trọng là các cặp khóa trên do những nhà cung cấp dịch vụ chứng thực chữ ký số (Certification Aithority - CA) cấp (hoặc xác minh là đủ điều kiện an toàn) sau khi đã kiểm tra, xác minh chủ của nó (cá nhân, tổ chức) là có thực. Đồng thời, nhà cung cấp dịch vụ cũng giao cho cá nhân, tổ chức đó một chứng thư số - tương đương như chứng minh thư nhân dân hay giấy xác nhận sự tồn tại của cơ quan, tổ chức trên môi trường mạng. Chứng thư đó có chứa khóa công khai của tổ chức, cá nhân và được duy trì tin cậy trên cơ sở dữ liệu của nhà cung cấp dịch vụ chứng thực, do vậy người nhận có thể truy cập vào cơ sở dữ liệu đó để xác minh xem đúng là có người đó hay không. 111
  58. Trong chương này, chúng ta xem xét các sơ đồ chữ kí số (còn được gọi là chữ kí số). Chữ kí viết tay thông thường trên tài liệu thường được dùng để xác người kí nó. Chữ kí được dùng hàng ngày chẳng hạn như trên một bức thư nhận tiền từ nhà băng, kí hợp đồng Chữ ký số là phương pháp kí một bức điện lưu dưới dạng đ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. Chương này trình bày một vài sơ đồ chữ kí số. Ta sẽ thảo luận trên một vài khác biệt cơ bản giữa các chữ kí thông thường và chữ kí số. Đầu tiên là một vấn đề kí một tài liệu. Với chữ kí thông thường, nó là một phần vật lý của tài liệu. Tuy nhiên, một chữ kí số không gắn theo kiểu vật lý vào bức điện nên thuật toán được dùng phải “không nhìn thấy” theo cách nào đó trên bức điện. Thứ hai là vấn đề về kiểm tra. Chữ kí thông thường được kiểm tra bằng cách so sánh nó với các chữ kí xác thực khác. Ví dụ, ai đó kí một tấm séc để mua hàng, người bán phải so sánh chữ kí trên mảnh giấy với chữ kí nằm ở mặt sau của thẻ tín dụng để kiểm tra. Dĩ nhiên, đây không phải là phươg pháp an toàn vì nó dễ dàng giả mạo. Mặt khác, các chữ kí số có thể được kiểm tra nhờ dùng một thuật toán kiểm tra công khai. Như vậy, bất kỳ ai cũng có thể kiểm tra được chữ kí số. Việc dùng một sơ đồ chữ kí an toàn có thể sẽ ngăn chặn được khả năng giả mạo. Sự khác biệt cơ bản khác giữa chữ kí số và chữ kí thông thường bản copy tài liệu được kí băng chữ kí số đồng nhất với bản gốc, còn copy tài liệu có chữ kí trên giấy thường có thể khác với bản gốc. Điều này có nghĩa là phải cẩn thận ngăn chăn một bức kí số khỏi bị dùng lại. Vì thế, bản thân bức điện cần chứa thông tin (chẳng hạn như ngày tháng) để ngăn nó khỏi bị dùng lại. 112
  59. 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. Bob có thể kí bức điện x dùng thuật toán kí an toàn. Chữ kí y=sig(x) nhận được có thể kiểm tra bằng thuật toán xác minh công khai ver(x,y). Khi cho trước cặp (x,y), thuật toán xác minh có giá trị TRUE hay FALSE tuỳ thuộc vào chữ kí được thực hiện như thế nào. Dưới đây là định nghĩa hình thức của chữ kí: Đị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: P là tập hữu hạn các bức điện có thể. A là tập hữu hạn các chữ kí có thể. K không gian khoá là tập hữu hạn các khoá có thể. 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=sig(x) verk = False nếu y# sig(x) Với mỗi k thuộc K hàm sigk và verk là các hàm thời gian đa thức. Verk sẽ 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í của Bob trên bức điện x. Nghĩa là x cho trước, chỉ có Bob mới có thể tính được y để verk = True. Một sơ đồ chữ kí không thể an toàn vô điều kiện vì Oscar có thể kiểm tra tất cả các chữ số y có thể có trên bức điện x 113
  60. nhờ dùng thuật toán ver công khai cho đến khi anh ta tìm thấy một chữ kí đúng. Vi thế, nếu có đủ thời gian. Oscar luôn luôn có thể giả mạo chữ kí của Bob. Như vậy, giống như trường hợp hệ thống mã khoá công khai, mục đích của chúng ta là tìm các sơ đồ chữ kí số an toan về mặt tính toán. Xem thấy rằng, hệ thống mã khoá công khai RSA có thể dùng làm sơ đồ chữ kí số. Như vậy, Bob kí bức điện x dùng qui tắc giải mã RSA là dk. Bob là người tạo ra chữ kí vì dk = sigk là mật. Thuật toán xác minh dùng qui tắc mã RSA ek. Bất kì ai cũng có thể xác minh chữ kí vì ek được công khai. Chú ý rằng, ai đó có thể giả mạo chữ kí của Bob trên một bức điện “ ngẫu nhiên” x bằng cách tìm x=ek(y) với y nào đó, khi đó y= sigk(x). Một giải pháp xung quanh vấn đề khó khăn này là yêu cầu bức điện chưa đủ phần dư để chữ kí giả mạo kiểu này không tương ứng với bức điện. Nghĩa là x trừ một xác suất rất bé. Có thể dùng các hàm hash trong việc kết nối với các sơ đồ chữ kí số sẽ loại trừ được phương pháp giả mạo này. Sơ đồ chữ kí RSA Cho n= p*q, p và q là các số nguyên tố. Cho P =A= Zn ab ≡ 1(mod(φ(n))). Các giá trị n và b là công khai, a giữ bí mật. Hàm kí: a sigk(x)= x mod n và kiểm tra chữ kí: b verk (x,y)= true ⇔ x ≡ y (mod n) ∈ (x,y Zn) Ta xét tóm tắt cách kết hợp chữ kí và mã khoá công khai. Giả sử rằng, Alice tính toán chữ kí y= sigAlice(x) và sau đó mã cả x và y bằng hàm mã khoá công khai eBob của Bob, khi đó cô ta nhận được z = eBob(x,y). Bản mã z sẽ được truyền tới Bob. Khi Bob nhận được z, anh ta sẽ trước hết sẽ giải 114
  61. mã hàm dBob để nhận được (x,y). Sau đó anh ta dùng hàm xác minh công khai của Alice để kiểm tra xem verAlice(x,y) có bằng True hay không. Song nếu đầu tiên Alice mã x rồi sau đó mới kí tên bản mã nhận được thì khi đó cô tính : y= sigAlice(eBob(x)). Alice sẽ truyền cặp (z,y) tới Bob. Bob sẽ giải mã z, nhận x và sau đó xác minh chữ kí y trên x nhờ dùng verAlice. Một vấn đề tiểm ẩn trong biện pháp này là nếu Oscar nhận được cặp (x,y) kiểu này, được ta có thay chữ kí y của Alice bằng chữ kí của mình. , Y = sigOscar(eBob(x)). (Chú ý, Oscar có thể kí bản mã eBob(x) ngay cả khi anh ta không biết bản rõ x). Khi đó nếu Oscar truyền (x, y’ ) đến Bob thì chữ kí Oscar được Bob xác minh bằng verOscar và Bob có thể suy ra rằng, bản rõ x xuất phát từ Oscar. Do khó khăn này, hầu hết người sử dụng được khuyến nghị nếu kí trước khi mã. 5.2. Sơ đồ chữ kí ELGAMAL Sau đây ta sẽ mô tả 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ố. Sơ đồ E, là không tất định giống như hệ thống mã khoá công khai Elgamal. Điều này có nghĩa là 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. Nếu chữ kí được thiết lập đúng khi xác minh sẽ thành công vì : 115
  62. γ δ γ γ β γ ≡ αa αk (mod p) ≡ αx(mod p) là ở đây ta dùng hệ thức : a γ + k δ ≡ x (mod p-1) Sơ đồ chữ kí số 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ử α ∈ Zp là phần tử nguyên thuỷ của Zp* , a thuộc 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 (mật) k∈ Zp-1. định nghĩa : Sigk(x,y) =(γ ,δ), trong đó γ = αk mod p -1 và δ =(x-aγ ) k mod (p-1). Với x,γ ∈ Zp và δ ∈ Zp-1 , ta định nghĩa : γ δ Ver(x, γ ,δ ) = true ⇔ β γ ≡ αx(mod p). Bob tính chữ kí bằng cách dùng cả gía trị mật a (là một phần của khoá) lẫn số ngẫu nhiên mật k (dùng để kí lên bức điện x). Việc xác minh có thực hiện duy nhất bằng thông báo tin công khai. Chúng ta hãy xét một ví dụ nhỏ minh hoạ. Giả sử cho p = 467, α =2, a = 127, khi đó: β = αa mod p 116
  63. = 2127 mod 467 = 132 Nếu Bob muốn kí lên bức điện x = 100 và 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ệ. Xét độ mật của sơ đồ chữ kí E. Giả sử, Oscar thử giả mạo chữ kí trên bức điện x cho trước không biết a. Nếu Oscar chọn γ và sau đó thử x -γ . tìm giá trị δ tương ứng, anh ta phải tính logarithm rời rạc logγ α β Mặt khác, nếu đầu tiên ta chọn δ và sau đó thử tim γ 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. Nếu Oscar chọn δ và γ và sau đó tự giải tìm x, anh ta sẽ phải đối mặt với bài toán logarithm rời rạc, tức bài toán tính logα Vì thế Oscar không thể kí một bức điện ngẫu nhiên bằng biện pháp này. Tuy nhiên, có một cách để 117
  64. Oscar 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 đó 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). Ta nói rằng (γ , δ ) là chữ kí hợp lệ của x. Điều này được chứng minh qua việc kiểm tra xác minh : Ta sẽ minh hoạ bằng một ví dụ : Giống như ví dụ trước cho p = 467, α = 2, β =132. Giả sữ Oscar chọn i = 99,j = 179; khi đó j-1 mod (p-1) = 151. Anh ta tính toán như sau: γ = 299132197 mod 467 = 117 δ =-117 × 151 mod 466 = 51. x = 99 × 41 mod 466 = 331 Khi đó (117, 41) là chữ kí hợp lệ trên bức điện 331 như thế đã xác minh qua phép kiểm tra sau: 132117 11741 ≡ 303 (mod 467) và 2331 ≡ 303 (mod 467) Vì thế chữ kí là hợp lệ. Sau đây là kiểu giả mạo thứ hai trong đó Oscar bắt đầu bằng bức điện được Bob kí trước đây. Giả sử (γ , δ ) là chữ kí hợp lệ trên x. Khi đó Oscar 118
  65. có khả năng kí lên nhiều bức điện khác nhau. Giả sử i, j, h là các số nguyên, 0 ≤ h, i, j ≤ p-2 và UCLN (h γ - j δ, p-1) = 1. Ta thực hiện tính toán sau: λ = γ h αi βj mod p µ = δλ(hγ -jδ)-1 mod (p-1) x, = λ(hx+iδ ) -1 mod (p-1), Trong đó (hγ -jδ)-1 được tính theo modulo (p-1). Khi đó dễ dàng kiểm tra điệu kiện xác minh : λ µ β λ ≡ αx’ (mod p) vì thế (λ, µ)là chữ kí hợp lệ của x’. Cả hai phương pháp trên đều tạo các chữ kí giả mạo hợp lệ song không xuất hiện khả năng đối phương giả mạo chữ kí trên bức điện có sự lựu chọn của chính họ mà không phải giải bài toán logarithm rời rạc, vì thế không có gì nguy hiểm về độ an toàn của sơ đồ chữ kí Elgamal. Cuối cùng, ta sẽ nêu vài cách có thể phải được sơ đồ này nếu không áp dụng nó một cách cẩn thận (có một số ví dụ nữa về khiếm khuyết của giao thức). Trước hết, giá trị k ngẫu nhiên được dùng để tính chữ kí phải giữ kín không để lộ, vì nếu k bị lộ, khá đơn giản để tính : A = (x-k γ )δ-1 mod (p-1). Dĩ nhiên, một khi a bị lộ thì hệ thống bị phá và Oscar có thể dễ dàng giả mạo chữ kí. Một kiểu dùng sai sơ đồ nữa là dùng cùng giá trị k để kí hai bức điện khác nhau. điều này cùng tạo thuận lợi cho Oscar tinh a và phá hệ thống. Sau đây là cách thực hiện. Giả sử (γ , δ1) là chữ kí trên x1 và (γ , δ2) là chữ kí trên x2. Khi đó ta có: 119
  66. γ δ β γ 1 ≡ αx1 (mod p) γ δ và β γ 2 ≡ αx2(modp). Như vậy δ δ αx1-x2 ≡ α 1- 2 (mod p). Nếu viết γ = αk, ta nhận được phương trình tìm k chưa biết sau. δ δ αx1-x2 ≡ αk( 1 - 2) (mod p) tương đương với phương trình x1- x2 ≡ k( δ1- δ2) (mod p-1). Bây giờ giả sử d =UCLN(δ1- δ2, p-1). Vì d | (p-1) và d | (δ1-δ2) nên suy ra d | (x1-x2). Ta định nghĩa: ’ x = (x1- x2)/d ’ δ = (δ1- δ2)/d p’ = ( p -1 )/d Khi đó đồng dư thức trở thành: x’ ≡ k δ’ (mod p’ ) vì UCLN(δ’, p’ ) = 1,nên có thể tính: ε = (δ’)-1 mod p’ Khi đó giá trị k xác định theo modulo p’ sẽ là: k = x’ ε mod p’ Phương trình này cho d giá trị có thể của k k = x’ ε +i p’ mod p 120
  67. với i nào đó, 0 ≤ i ≤ d-1. Trong số d giá trị có có thế này, có thể xác định được một giá trị đúng duy nhất qua việc kiểm tra điều kiện γ ≡ αk (mod p) 5.3. Chuẩn chữ kí số. Chuẩn chữ kí số(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 vào 1/12/94 tuy đã được đề xuất từ 8/91. Trước hết ta sẽ nêu ra những thay đổi của nó so với sơ đồ Elgamal và sau đó sẽ mô tả cách thực hiện nó.Trong nhiều tinh huống, thông báo có thể mã và giải mã chỉ một lần nên nó phù hợp cho việc dùng với hệ mật bất kì (an toàn tại thời điểm được mã). Song trên thực tế, nhiều khi một bức điện được dùng làm một tài liệu đối chứng, chẳng hạn như bản hợp đồng hay một chúc thư và vì thế cần xác minh chữ kí sau nhiều năm kể từ lúc bức điện được kí. Bởi vậy, điều quan trọng là có phương án dự phòng liên quan đến sự an toàn của sơ đồ chữ kí khi đối mặt với hệ thống mã. Vì sơ đồ Elgamal không an toàn hơn bài toán logarithm rời rạc nên cần dung modulo p lớn. Chắc chắn p cần ít nhất là 512 bít và nhiều người nhất trí là p nên lấy p=1024 bít để có độ an toàn tốt.Tuy nhiên, khi chỉ lấy modulo p =512 thì chữ kí sẽ có 1024 bít. Đối với nhiều ứng dụng dùng thẻ thông minh thì cần lại có chữ kí ngắn hơn. DSS cải tiến sơ đồ Elgamal theo hướng sao cho một bức điện 160 bít được kí bằng chữ kí 302 bít song lại p = 512 bít. Khi đó hệ thống làm việc trong * 160 nhóm con Zn kích thước 2 . Độ mật của hệ thống dựa trên sự an toàn của * việc tìm các logarithm rời rạc trong nhóm con Zn . Sự thay đổi đầu tiên là thay dấu “ - “ bằng “+” trong định nghĩa δ, vì thế: δ = (x +α γ )k-1 mod (p-1) thay đổi kéo theo thay đổi điều kiện xác minh như sau: 121
  68. γ δ αx β ≡ γ (mod p) (1) Nếu UCLN (x + αγ, p-1) =1thì δ-1 mod (p-1) tồn tại và ta có thể thay đổi điều kiện (1) như sau: -1 -1 αxδ βγδ ≡ γ (mod )p (2) Đây là thay đổi chủ yếu trong DSS. Giả sử q là số nguyên tố 160 bít sao cho q | (q-1) và α là căn bậc q của một modulo p. (Dễ dàng xây dựng một (p-1)/q α như vậy: cho α0 là phần tử nguyên thuỷ của Zp và định nghĩa α = α0 mod p). Khi đó β và γ cũng sẽ là căn bậc q của 1. vì thế các số mũ Bất kỳ của α, β và γ có thể rút gọn theo modulo q mà không ảnh hưởng đến điều kiện xác minh (2). Điều rắc rối ở đây là γ xuất hiện dưới dạng số mũ ở vế trái của (2) song không như vậy ở vế phải. Vì thế, nếu γ rút gọn theo modulo q thì cũng phải rút gọn toàn bộ vế trái của (2) theo modulo q để thực hiện phép kiểm tra. Nhận xét rằng, sơ đồ (1) sẽ không làm việc nếu thực hiện rút gọn theo modulo q trên (1). DSS được mô tả đầy đủ trong sơ đồ dưới. Chú ý cần có δ ≡ 0 (mod q) vì giá trị δ-1 mod q cần thiết để xác minh chữ kí (điều này tương đương với yêu cầu UCLN(δ, p-1 ) =1 khi biến đổi (1) thành (2). Nếu Bob tính δ ≡ 0 (mod q) theo thuật toán chữ kí, anh ta sẽ loại đi và xây dựng chữ kí mới với số ngẫu nhiên k mới. Cần chỉ ra rằng, điều này có thể không gần vấn đề trên thực tế: xác xuất để δ ≡ 0 (mod q) chắc sẽ xảy ra cở 2-160 nên nó sẽ hầu như không bao giờ xảy ra. Chuẩn chữ kí số 122
  69. . Giả sử p là số nguyên tố 512 bít sao cho bài toán logarithm rời rạc trong Zp không giải được, cho p 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 modulo p: Cho p =Zp . a = Zq× Zp và định nghĩa : A = {(p,q,α ,a,β ) : β ≡ αa (mod p)} các số p, q, α và β là công khai, có 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: sigk (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 : -1 e1= xδ mod q -1 e2= γδ mod q e1 e2 verk(x, γ , δ) = true ⇔( α β mod p) mod q = γ Ví dụ: Giả sử q =101, p = 78 q+1 =7879.3 là phần tử nguyên thuỷ trong Z7879 nên ta có thể lấy: α = 378 mod 7879 =170 Giả sử a =75, khi đó : β = αa mod 7879 = 4576 Bây giờ giả sữ Bob muốn kí bức điện x = 1234 và anh ta chọn số ngẫu nhiên k =50, vì thế : k-1 mod 101 = 99 khi đó γ =(17030 mod 7879) mod 101 = 2518 mod 101 = 94 và δ = (1234 +75 × 94) mod 101 = 96 123
  70. Chữ kí (94, 97) trên bức điện 1234 được xác minh bằng các tính toán sau: δ-1 = 97-1 mod 101 =25 e1 = 1234 × 25mod 101 = 45 e2 = 94 × 25 mod 101 =27 (17045 456727 mod 7879)mod =2518 mod 101 = 94 vì thế chữ kí hợp lệ. Khi DSS được đề xuất năm 1991, đã có một vài chỉ trích đưa ra. Một ý kiến cho rằng, việc xử lý lựa chọn của NIST là không công khai. Tiêu chuẫn đã được Cục An ninh Quốc gia (NSA) phát triển mà không có sự tham gia của khôi công nghiệp Mỹ. Bất chấp những ưu thế của sơ đồ, nhiều người đã đóng chặt cửa không tiếp nhận. Còn những chỉ trích về mặt kĩ thuật thì chủ yếu là về kích thước modulo p bị cố định = 512 bít. Nhiều người muốn kích thước này có thể thay đổi được nếu cần, có thể dùng kích cỡ lớn hơn. Đáp ứng những đòi hỏi này, NIST đã chọn tiêu chuẩn cho phép có nhiều cỡ modulo, nghĩa là cỡ modulo bất kì chia hết cho 64 trong phạm vi từ 512 đến 1024 bít. Một phàn nàn khác về DSS là chữ kí được tạo ra nhanh hơn việc xác minh nó. Trong khi đó, nếu dùng RSA làm sơ đồ chữ kí với số mũ xác minh công khai nhỏ hơn (chẳng hạn = 3) thì có thể xác minh nhanh hơn nhiều so với việc lập chữ kí. Điều này dẫn đến hai vấn đề liên quan đến những ứng dụng của sơ đồ chữ kí: 1.Bức điện chỉ được kí một lần, song nhiều khi lại cần xác minh chữ kí nhiều lần trong nhiều năm. Điều này lại gợi ý nhu cầu có thuật toán xác minh nhanh hơn. 124
  71. 2.Những kiểu máy tính nào có thể dùng để kí và xác minh ? Nhiều ứng dụng, chẳng hạn các thẻ thông minh có khả năng xử lý hạn chế lại liên lạc với máy tính mạnh hơn. Vi thế có nhu cầu nhưng thiết kế một sơ đồ để có thực hiện trên thẻ một vài tính toán. Tuy nhiên, có những tình huống cần hệ thống mình tạo chữ kí, trong những tình huống khác lại cần thẻ thông minh xác minh chữ kí. Vì thế có thể đưa ra giải pháp xác định ở đây. Sự đáp ứng của NIST đối với yêu cầu về số lần tạo xác minh chữ kí thực ra không có vấn đề gì ngoài yêu cầu về tốc độ, miễn là cả hai thể thực hiện đủ nhanh. 125
  72. TÀI LIỆU THAM KHẢO [1] Douglas R. stinson, Cryptography_ Theory and Practice, CRC Press, 1995. [2] Man Toung Rhee, Hanyang University, Cryptography and Secure Communications, McGRAW - HILL BOOK CO, 1994. [3] Ph.D William Stallings, Network and Internetwork Security Principles and Practice, PRENTICE HALL, 1995. [4] Phạm Huy Điển - Hà Huy Khoái, Mã hóa thông tin - Cơ sở toán học và ứng dụng, Viện Toán học, 2004. [5] Hà Huy Khoái, Nhập môn số học và thuật toán, Nhà xuất bản khoa học - 1997 [6] PGS-TS. Thái Hồng Nhị - TS. Phạm Minh Việt, An toàn thông tin - Mạng máy tính, truyền tin số và truyền dữ liệu, Nhà xuất bản khoa học và kỹ thuật, 2004. [7] PGS-TS. Nguyễn Bình, Giáo trình Mật mã học, Nhà xuất bản bưu Điện, 2004 [8] Nguyễn Xuân Dũng, Bảo mật thông tin mô hình và ứng dụng, NXB Thống kê 126