Tạo Số Giả Ngẫu Nhiên Và Mật Mã Dòng - .6 Mô Hình An Toàn Mạng

1 .6 Mô hình an toàn mạng

2.5 Tạo số giả ngẫu nhiên và mật mã dòng

2.5.1 Nguyên lí tạo số giả ngẫu nhiên

Số ngẫu nhiên đóng vai trò quan trọng trong việc s dụng mật mã hóa cho các ứng dụng, các giao thức, và các thuật toán an toàn mạng khác nhau như trong các sơ đồ h n hối khóa và nhận thực lẫn nhau, tạo khóa hiên, tạo các khóa cho thuật toán mật mã khóa công khai RSA, hay tạo luồng bit cho mật mã dòng đối xứng.

54

Có hai tiêu chí được s dụng để đánh giá tính ngẫu nhiên của chuỗi ngẫu nhiên, đó

là:

 Phân phối đồng nhất: phân phối các bit trong chuỗi phải là đồng nhất; nghĩa

là tần suất xuất hiện của các bit 0 và 1 phải là như nhau.

 Độc lập: không chuỗi con nào trong chuỗi ngẫu nhiên đó có thể được suy ra từ các chuỗi con khác.

Trong các ứng dụng như nhận thực lẫn nhau, tạo khóa hiên, và mật mã dòng, tính không thể dự đoán trư c được yêu cầu. Yêu cầu này không ch là chuỗi số đó là ngẫu nhiên thống kê mà các thành hần kế tiế trong chuỗi đó còn hải là không dự đoán trư c được. V i các chuỗi ngẫu nhiên “đúng”, mỗi số là độc lậ thống kê v i các số khác trong chuỗi đó và vì vậy là không thể dự đoán trư c được. Mặc dù, các số ngẫu nhiên đúng được s dụng trong một số ứng dụng, chúng có một số hạn chế như tính không hiệu quả. Do vậy, việc s dụng các thuật toán để tạo các chuỗi số ngẫu nhiên là hiệu quả hơn.

Các ứng dụng mật mã hóa thường tận dụng các kỹ thuật thuật toán cho việc tạo số ngẫu nhiên. Các thuật toán này là xác định và vì vậy tạo ra các chuỗi số không hải là ngẫu nhiên thống kê. Tuy nhiên, nếu thuật toán tốt, chuỗi số kết quả sẽ qua được nhiều bài kiểm tra về tính ngẫu nhiên. Các số như vậy được gọi là các số giả ngẫu nhiên.

Hình 2.30 mô tả bộ tạo số ngẫu nhiên đúng (TRNG) v i hai bộ tạo số giả ngẫu nhiên. TRNG có đầu vào là một nguồn thực sự ngẫu nhiên; nguồn này thường được đề cậ đến là nguồn entro y (entro y source). Nguồn entro y được lấy ra từ môi trường vật lý của máy tính và có thể tính đến cả các mẫu định thời bấm hím, hoạt động của ổ đĩa, sự di chuyển chuột, và các giá trị tức thời của đồng hồ hệ thống. Một nguồn, hoặc sự kết hợ của các nguồn, được coi là đầu vào của thuật toán để tạo ra đầu ra là chuỗi nhị h n ngẫu nhiên. TRNG có thể ch đơn giản là hé biến đổi các nguồn tương tự thành đầu ra nhị h n.

Ngược lại, RNG có đầu vào là một giá trị cố định, được gọi là hạt giống (seed), và tạo ra chuỗi bit đầu ra s dụng một thuật toán xác định. Thường thì seed được tạo ra bởi một bộ TRNG. Như ch ra trong hình 2.30, một số kết quả của thuật toán được hản hồi lại như là đầu vào của thuật toán bằng một đường hồi tiế . Chú ý rằng, dòng bit đầu ra được xác định ch bởi một hoặc nhiều giá trị đầu vào, do đó kẻ tấn công mà biết thuật toán và seed thì có thể tạo lại toàn bộ dòng bit.

55

 Bộ tạo số giả ngẫu nhiên: thuật toán được s dụng để tạo ra chuỗi bit kết thúc mở được gọi là PRNG. Ứng dụng phổ biến cho chuỗi bit này là đầu vào của mật mã dòng đối xứng.

 Hàm giả ngẫu nhiên ( RF): RF được s dụng để tạo ra chuỗi bit giả ngẫu

nhiên có độ dài cốđịnh. RF cũng có đầu vào là seed và một thông tin khác

như là ID người s dụng hay ID ứng dụng.

Hình 2.30: Nguyên lý tạo số ngẫu nhiên và giả ngẫu nhiên

2.5.2 Bộ tạo số giả ngẫu nhiên

Trong hần này, hai kiểu thuật toán cho bộ RNG được trình bày.

Các bộ tạo đồng dạng tuyến tính (Linear Congruential)

ỹ thuật được s dụng rộng rãi cho việc tạo số giả ngẫu nhiên là thuật toán đồng dạng. Thuật toán này có 4 tham số như sau:

Chuỗi số ngẫu nhiên {Xn} được tính như sau:

1 ( ) mod

n n

X   aX c m

Nếu m, a, c, và X0 là số nguyên, kĩ thuật này sẽ tạo ra chuỗi số nguyên v i mỗi số nguyên nằm trong dải 0 Xn m.

56

Việc lựa chọn các giá trị cho a, c, và m là vấn đềthen chốt trong việc hát triển một bộ tạo số ngẫu nhiên tốt. Ví dụ, v i a = c = 1. Chuỗi được tạo ra rõ ràng là không thỏa mãn. V i các giá trị a 7, c = 0, m = 32, và X0 = 1. Bộ tạo ngẫu nhiên tạo ra chuỗi {7, 17, 23, 1, 7,...}, chuỗi này cũng không thỏa mãn. Trong số 32 giá trị có thể, ch bốn giá trị được s dụng; do đó, chuỗi đó được coi là có chu kỳ là 4. Nếu thay a bằng 5, thì chuỗi m i là {5, 25, 29, 17, 21, 9, 13, 1, 5, ...}, khi đó chu kỳ tăng lên thành 8.

Nếu m là một số rất l n, có khả năng tạo ra một chuỗi dài các số ngẫu nhiên khác nhau. Tiêu chí chung đó là m gần v i số nguyên không m l n nhất có thể đối v i mỗi máy tính xác định trư c. Do đó, giá trị của m gần hoặc bằng 231sẽ được lựa chọn.

Có ba tiêu chí được s dụng để đánh giá bộ tạo sốngẫu nhiên như sau:

 Hàm tạo sẽ là hàm tạo toàn chu kỳ. Nghĩa là, hàm tạo sẽ tạo ra tất cả các số

từ0 đến m-1 trư c khi lặp lại.

 Chuỗi được tạo ra phải là ngẫu nhiên

 Hàm sẽ thực hiện một cách hiệu quả v i số 32 bit.

V i các giá trị thích hợ của a, c, và m, chuỗi số tạo ra có thể đá ứng được ba tiêu chí đánh giá trên. V i tiêu chí đánh giá đầu tiên, nếu m là số nguyên tố và c = 0, thì đối v i giá trị nào đó của a, chu kỳ của hàm tạo số ngẫu nhiên sẽ là m-1. Đối v i số 32 b , giá trị nguyên tố của m là 231-1. Do đó, hàm tạo số ngẫu nhiên trở thành:

 31 

1 ( ) mod 2 1

n n

X   aX 

Độ mạnh của thuật toán đồng dạng tuyến tính hụ thuộc vào số nh n a và m được lựa chọn. Tuy nhiên, không có sự ngẫu nhiên nào trong thuật toán, ngoại trừ việc lựa chọn giá trị khởi tạo X0. hi giá trị đó được lựa chọn, các số còn lại là chuỗi theo sau được xác định. Điều này là lợi thế cho các kẻ tấn công. Nếu kẻ tấn công biết rằng thuật toán đồng dạng tuyến tính được s dụng và nếu các tham số đã biết (ví dụ a = 75, c = 0, m = 231-1), thì khi một số được hát hiện ra, tất cả các số tiế theo sẽ biết được, ch cần biết một hần nhỏ của chuỗi số là đủ để xác định các tham số của thuật toán. Giả s rằng kẻ tấn công có khả năng xác định các giá trị X0, X1, X2, và X3, thì

1 ( 0 ) mod X  aX c m 2 ( 1 ) mod X  aX c m 3 ( 2 ) mod X  aX c m

57

Từ các hương trình này, các giá trị của a, c, và m có thể tìm được.

Do đó, mục tiêu của bộ RNG là làm sao để hần chuỗi mà kẻ tấn công có thể khám há ra là không đủ để xác định các thành hần tiế theo của chuỗi. Mục tiêu đó có thể đạt được bằng một số cách, ví dụ như s dụng đồng hồ hệ thống nội để thay đổi dòng số ngẫu nhiên. Một cách s dụng đồng hồ là khởi tạo lại chuỗi đó sau mỗi N số s dụng giá trị đồng hồ hiện tại (mod m) làm seed m i. Cách khác đơn giản hơn là thêm giá trị đồng hồ hiện tại vào mỗi số ngẫu nhiên (mod m).

Bộ tạo BBS (Blum Blum Shub)

Một hương há hổ biến để tạo các số giả ngẫu nhiên an toàn được biết như là bộ tạo BBS (hình 2.31). Hoạt động của bộ tạo BBS như sau. Đầu tiên, lựa chọn hai số nguyên tố l n, và q. Hai số đó khi chia cho 4 đều có số dư là 3, nghĩa là

(mod 4) (mod 4) 3

p q 

Ví dụ, các số nguyên tố 7 và 11 đều thỏa mãn điều kiện trên. Đặt n p q.

Hình 2.31: Sơ đồ khối bộ tạo BBS

Tiế theo, chọn số ngẫu nhiên s, sao cho cả và q đều không hải là thừa số của s. Sau đó, bộ tạo BBS tạo ra chuỗi bit Bi theo thuật toán sau:

58   2 0 2 1 mod 1 mod mod 2 i i i i X s n for i to X X n B X      

Do đó, bit có ý nghĩa thấ nhất được lấy ra tại mỗi vòng lặ . Bảng sau ch ra ví dụ hoạt động của bộ tạo BBS v i n192649 383 503  và seed s101355.

Bảng 2.5: ví dụ hoạt động của bộ tạo BBS

BBS còn được gọi là bộ tạo bit giả ngẫu nhiên an toàn bảo mật (CS RBG). Tính an

toàn của BBS hụ thuộc vào hai thừa số nguyên tố và q của n.

2.5.3 Mật mã dòng

Mật mã dòng thực hiện mật mã bản rõ theo từng byte tại một thời điểm, mặc dù mật mã dòng có thể được thiết kế để hoạt động trên từng bit tại một thời điểm hoặc trên đơn vị l n hơn 1 byte tại một thời điểm. Hình 2.32 đưa ra sơ đồ cấu trúc của mật mã dòng. Trong cấu trúc này, khóa là đầu vào của bộ tạo bit giả ngẫu nhiên. Bộ tạo bit giả ngẫu nhiên này tạo ra dòng số 8 bit ngẫu nhiên. Đầu ra của bộ tạo, được gọi là dòng khóa, được kết hợ một byte tại một thời điểm v i dòng bản rõ s dụng hé XOR. Ví dụ, nếu byte tiế theo được tạo ra bởi bộ tạo này là 01101100 và byte bản rõ tiế theo là 11001100, thì byte bản mã sẽ là:

59

Hình 2.32: Sơ đồ mật mã dòng

Như vậy, có thể thấy mật mã dòng tương tự như mật mã hóa One-Time ad. Điểm quan trọng nhất của các mật mã dòng là bộ tạo số ngẫu nhiên. Nếu chọn khóa có chiều

dài ngắn thì không bảo đảm an toàn, còn nếu chọn khóa có chiều dài bằng chiều dài bản tin như One-Time ad thì lại không thực tế. Bộ tạo số củamật mã dòng c n bằng giữa hai điểm này, cho hé dùng một khóa ngắn nhưng dãy số tạo ra bảo đảm một độ ngẫu nhiên

cần thiết như khóa của One-time ad, dùng rằng không hoàn toàn thực sự ngẫu nhiên. hần tiế theo trình bày hương há mật mã hóa dòng tiêu biểu là RC4.

2.5.4 RC4

RC4 là một hương há mật mã dòng được thiết kế vào năm 1987 bởi Ron Rivest

cho RSA. Nó là một mật mã dòng có kích thư c khóa thay đổi v i các hoạt động hư ng byte. Thuật toán được dựa trên việc s dụng hé hoán vị ngẫu nhiên. RC4 được dùng trong giao thức SSL để bảo mật dữ liệu trong quátrình truyền dữ liệu giữa Web Server và trình duyệt Web. Ngoài ra RC4 còn được s dụng trong giao thức mã hóa WEP và giao

thức W A (Wifi rotected Access) của mạng Wireless LAN.

Thuật toán RC4 là khá đơn giản. hóa có độ dài thay đổi từ 1 t i 128 byte (8 đến 2048 bit) được s dụng để khởi tạo vector S gồm 256 byte, v i các hần t là S[0],

60

đến 255. Đối v i quá trình mật mã hóa và giải mật mã, byte k (hình 2.32) được tạo ra từ S bằng cách lựa chọn một trong 255 hần t theo một cách có hệ thống. hi mỗi giá trị của k được tạo ra, các hần t trong S lại được hoán vị một lần nữa.

Khởi tạo S

Để bắt đầu, các hần t của S được thiết lậ v i các giá trị từ 0 đến 255 theo tứ tự tăng dần; nghĩa là S[0]=0, S[1]=1,..., S[255]=255. Một vector tạm thời T cũng được tạo ra. Nếu độ dài khóa là 256 byte, thì được chuyển t i T. Nếu không, đối v i khóa có độ dài keylen byte, keylen hần t đầu tiên của T được sao ché từ , và sau đó được lặ lại nhiều lần để điền đầy vào T. Hoạt động đó có thể tóm tắt như sau:

0 255 [ ] ; [ ] [ mod ]; for i to do S i i T i K i keylen   

Tiế theo, T được s dụng để tạo ra hoán vị đầu tiên của S, cụ thể như sau:

  0; 0 255 [i]+T[ ] mod 256; w ( [ ],S[ ]); j for i to do j j S i S ap S i j    

Bởi vì hé toán thực hiện trên S ch là tráo đổi các hần t của S, ảnh hưởng duy nhất là hoán vị.S vẫn chứa tất cả các số từ 0 đến 255.

Tạo dòng

hi vector S đã được khởi tạo, khóa đầu vào không còn được s dụng nữa. Việc tạo dòng được thực hiện như sau:

, 0; w ( ) ( 1) mod 256; (j [ ]) mod 256; w ( [ ],S[ ]); t (S[ ] [ ]) mod 256; [ ]; i j hile true i i j S i S ap S i j i S j k S t        

Để mật mã hóa, thực hiện hé XOR giá trị k v i byte tiế theo của bảnrõ. Để giải mật mã, thực hiện XOR giá trị k v i byte tiế theo của bản mã.

61

Hình 2.33: RC4

Quá trình tạo số của RC4 cũng tạo ra dãy số ngẫu nhiên, khó đoán trư c, vì vậy RC4 đạt được mức độ an toàn cao hơn mật mã hóa One-Time Pad. Mật mã hóa RC4 hoàn

toàn được thực hiện trên các số nguyên một byte do đó tối ưu cho việc thiết lậ bằng hần mềm và tốc độ thực hiện nhanh hơn so v i mật mã khối.

62

Chương 3: Mật mã khóa bất đối xứng 3.1. Mật mã khóa công khai và RSA

3.1.1 Nguyên lí hệ thống mật mã khóa công khai

hái niệm về mật mã khóa công khai hát triển từ một nỗ lực tấn công hai trong những vấn đề khó khăn của mã hóa đối xứng. Vấn đề đầu tiên là h n hối khóa và vấn đề thứ hai là chữ ký số. Vấn đề h n hối khóa trong hệ mật đối xứng yêu cầu hoặc (1) hai thành viên cùng chia sẻ khóa và cách nào để h n hối cho chúng, hoặc (2) s dụng một trung t m h n hối khóa. Whitfield Diffie, người hát hiện ra mã hóa khóa công khai (cùng v i Martin Hellman, Đại học Stanford), lý luận rằng yêu cầu thứ hai này hủ nhận bản chất của mật mã: khả năng duy trì bí mật tổng thể sẽ x m hạm thông tin riêng tư. Vấn đề thứ hai không liên quan vấn đề đầu tiên, là chữ ký kỹ thuật số. Nếu việc s dụng mật mã đã trở nên hổ biến, không ch trong những tình huống qu n sự mà còn trong thương mại và mục đích cá nh n, thì tin nhắn điện t và các văn bản sẽ cần xác nhận tương đương v i chữ ký được s dụng trong các tài liệu giấy.

3.1.1.1 ệ ậ

Giải thuật bất đối xứng dựa trên cơ chế s dụng một khóa để mã hóa và một khóa khác (có liên quan t i khóa mã) để giải mã. Các giải thuật này có đặc điểm quan trọng sau đ y.

 Nó là tính toán khả thi để xác định một khóa giải mã duy nhất thông hiểu về thuật toán mã hóa và khóa mã hóa.

Thêm vào đó, đối v i một số thuật toán như RSA còn bổ sung một số đặc tính sau: Một trong hai khoá có liên quan có thể được s dụng để mã hóa, và cái còn lại để giải mã.

Một lưu đồ mã hóa khóa công khai có sáu thành hần (hình 3.1a);

 laintext (bản rõ): Đ y là bản tin hoặc dữ liệu có thể đọc được và là đầu vào của thuật toán.

 Thuật toán mã hóa: Các thuật toán mã hóa thực hiện các biến đổi khác nhau trên bản rõ.

63

 hóa công cộng và khóa riêng: Đ y là một cặ chìa khóa đã được chọn để nếu một khóa được s dụng để mã hóa, thì khóa kia được s dụng để giải mã. Các hé chuyển đổi chính xác được thực hiện bởi các thuật toán hụ