MỘt số phưƠng pháp mã HÓa dữ liệu mở đầu

Ngày nay trong mọi hoạt động của con người thông tin đóng một vai trò quan trọng không thể thiếu. Xã hội càng phát triển nhu cầu trao đổi thông tin giữa các thành phần trong xã hội ngày càng lớn. Mạng máy tính ra đời đã mang lại cho con người rất nhiều lợi ích trong việc trao đổi và xử lý thông tin một cách nhanh chóng và chính xác. Chính từ những thuận lợi này đã đặt ra cho chúng ta một câu hỏi, liệu thông tin đi từ nơi gửi đến nơi nhận có đảm bảo tuyệt đối an toàn, ai có thể đảm bảm thông tin của ta không bị truy cập bất hợp pháp. Thông tin được lưu giữ, truyền dẫn, cùng sử dụng trên mạng lưới thông tin công cộng có thể bị nghe trộm, chiếm đoạt, xuyên tạc hoặc phá huỷ dẫn đến sự tổn thất không thể lường được. Đặc biệt là đối với những số liệu của hệ thống ngân hàng, hệ thống thương mại, cơ quan quản lý của chính phủ hoặc thuộc lĩnh vực quân sự được lưu giữ và truyền dẫn trên mạng. Nếu như vì nhân tố an toàn mà thông tin không dám đưa lên mạng thì hiệu suất làm việc cũng như hiệu suất lợi dụng nguồn dữ liệu đều sẽ bị ảnh hưởng. Trước các yêu cầu cần thiết đó, việc mã hoá thông tin sẽ đảm bảo an toàn cho thông tin tại nơi lưu trữ cũng như khi thông tin được truyền trên mạng.

Kỹ thuật mật mã thông qua việc biến đổi hoặc mã hoá thông tin, biến đổi những thông tin nhạy cảm, vấn đề cơ mật thành những văn tự mã hoá có dạng hỗn loạn, làm cho bọn tin tặc khó lòng mà đọc hiểu được, từ đó sẽ đạt được hai mục đích: một là, làm cho bọn tin tặc không biết làm thế nào để giải mã nên cũng không thể thu được những thông tin có bất kỳ ý nghĩa nào trong chuỗi mật mã hỗn loạn đó; hai là làm cho tin tặc không có khả năng làm giả thông tin với chuỗi mật mã hỗn loạn như thế. Khoa học nghiên cứu kỹ thuật mật mã gọi là mật mã học.

Mật mã học bao gồm hai nhánh, là mật mã học lập mã và mật mã học phân tích. Mật mã học lập mã với ý là tiến hành mã hoá thông tin để thực hiện việc che giấu thông tin, còn mật mã học phân tích là ngành học nghiên cứu phân tích giải dịch mật mã. Hai cái đối lập với nhau, nhưng lại thúc đẩy lẫn nhau.

Dùng phương pháp mật mã có thể che dấu và bảo hộ những thông tin cơ mật, làm cho người chưa được uỷ quyền không thể lấy được thông tin, những thông tin được giấu kín kia được gọi là văn bản rõ, mật mã có thể đem văn bản rõ biến đổi thành một loại hình khác, gọi là văn bản mật. Sự biến đổi văn bản rõ thành văn bản mật gọi là mã hoá bảo mật, quá trình người thu nhận hợp pháp khôi phục từ văn bản mật trở thành văn bản rõ được gọi là quá trình giải mã (hoặc giải mật). Người thu nhận phi pháp có ý đồ phân tích từ văn bản mật ra thành văn bản rõ, gọi là giải dịch.

Một hệ mật là một bộ 5 (P, C, K, E, D) thoả mãn các điều kiện sau:

+ P là một tập hữu hạn các bản rõ có thể

+ C là tập hữu hạn các bản mã có thể

+ K (không gian khoá) là tập hữu hạn các khoá có thể

+ Đối với mỗi kK có một quy tắc mã e_k: P -> C và một quy tắc giải mã tương ứng d_kD. Mỗi e_k: P -> C và d_k: C -> P là những hàm mà: d_k(e_k(x)) = x với mọi bản rõ xP.

Tính chất 4 là tính chất chủ yếu. Nội dung của nó là nếu một bản rõ x được mã hoá bằng e_k và bản mã nhận được sau đó được giải mã bằng d_k thì ta phải thu được bản rõ ban đầu x. Trong trường hợp này hàm mã hoá e_k phải là hàm đơn ánh, nếu không việc giải mã sẽ không thể thực hiện được một cách tường minh.

4. Phân loại các hệ mật mã

Hiện nay người ta đã thiết kế ra nhiều loại hệ thống mật mã, nếu như lấy khoá mật mã làm tiêu chuẩn có thể phân các hệ mật mã thành hai loại:

+ Theo sự mở rộng của quy mô mạng lưới, việc quản lý khoá mật mã trở thành một việc khó khăn.

+ Không có cách nào giải quyết vấn đề xác nhận thông tin.

+ Thiếu năng lực kiểm tra tự động sự tiết lộ khoá mật mã.

 Do đó, việc bảo mật dữ liệu trên mạng nên dùng cơ chế bảo mật hỗn hợp kết hợp giữa mật mã đối xứng và mật mã bất đối xứng, tức là khi giải mã thì dùng mật mã đối xứng, khi truyền đưa khoá mật mã thì dùng mật mã bất đỗi xứng. Như thế tức là đã giải quyết được khó khăn trong việc quản lý khoá mật mã, vừa lại giải quyết được vấn đề tốc độ giải mã. Không còn hoài nghi gì nữa, nó là một phương pháp tương đối tốt để giải quyết vấn đề an toàn thông tin khi truyền đưa trên mạng hiện nay.

Mã hoá cổ điển là phương pháp mã hoá đơn giản nhất xuất hiện đầu tiên trong lịch sử ngành mã hoá. Thuật toán đơn giản và dễ hiểu. Những phương pháp mã hoá này là cở sở cho việc nghiên cứu và phát triển thuật toán mã hoá đối xứng được sử dụng ngày nay.

Trước khi mã hoá một bản rõ thành bản mã bằng các phương pháp mã hoá, ta xét một sự một thiết lập tương ứng giữa các ký tự và các thặng dư theo modulo 26 như sau: A0, B1, …, Z25 hoặc:

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

a) Mật mã CAESAR

Một trong số những người sử dụng mật mã được biết sớm nhất, đó là julias caesar (xê-da). Ông đã làm cho các bức thư trở nên bí mật bằng cách dịch mỗi chữ cái đi ba chữ cái về phía trước trong bảng chữ cái ( và ba chữ cái cuối cùng thành ba chữ cái đầu tiên). Đây là 1 ví dụ về sự mã hoá, tức là quá trình làm cho bức thư trở nên bí mật.

Phương pháp mã hoá của CAESAR có thể được biểu diễn bởi hàm f, hàm này gán cho số nguyên không âm p, p  25, số nguyên f(p) trong tập 0, 1, 2, … , 25 sao cho: f(p)=(p+3) mod 26.

Như vậy, trong phiên bản mã hoá của bức thư, chữ cái được biểu diễn bởi p sẽ được thay bằng chữ cái được biểu diễn bởi: (p+3) mod 26

Trước hết, thay các chữ cái trong bức thư gốc thành các số, ta được:

12 4 4 19 24 14 20 8 13 19 7 4 15 0 17 10

bây giờ thay các số p đó bằng f(p)=(p+3) mod 26, ta được:

15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13

dịch trở lại các chữ cái, ta được bức thư đã mã hoá là:

PHHW BRX LQ WKH SDUN

Để phục hồi lại bức thư gốc đã được mã hoá theo mật mã của CAESAR, ta cần phải dùng hàm ngược f ^-1 của f: f ^-1(p)=(p-3) mod 26 . Nói cách khác, để tìm lại bức thư gốc, mỗi một chữ cái lùi lại ba chữ trong bảng chữ cái, với ba chữ cái đầu tiên chuyển thành ba chữ cái cuối cùng tương ứng của bảng chữ cái.

• 
  Mã thay thế có thể được mô tả như sau:
  

e_(x) = (x) và

d_(y) = ^-1(y)

trong đó ^-1 là hoán vị ngược của 

Hàm giải mã là phép hoán vị ngược, điều này được thực hiện bằng cách viết hàng thứ hai lên trước rồi sắp xếp theo thứ tự chữ cái. Ta nhận được:

Sử dụng mã vigenère, ta có thể gán cho mỗi khoá k một chuỗi kí tự có độ dài m được gọi là từ khoá. Mật mã vigenère sẽ mã hoá đồng thời m kí tự: mỗi phần tử của bản rõ tương đương với m kí tự.

Mã vigenère có thể được mô tả như sau:

Cho m là một số nguyên dương cố định nào đó. định nghĩa P=C=K=(Z)^m với khoá k=(k₁, k₂, …, k_m), ta xác định:

e_k(x₁, x₂, …, x_m)=(x₁+k₁, x₂+k₂, …, x_m+k_m) và

d_k(y₁, y₂, …, y_m)=(y₁-k₁, y₂-k₂, …, y_m-k_m)

trong đó tất cả các phép toán được thực hiện trong Z₂₆

Ví dụ: mã hoá bản rõ: thiscryptosystemisnotsecure với m=6 và từ khoá là CIPHER bằng mã vigenère.

Từ khóa CIPHER tương ứng với dãy số k=(2, 18, 15, 7, 4, 17)

Biến đổi các phần tử của bản rõ thành các thặng dư theo modulo 26, viết chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau:

Dãy kí tự: 21, 15, 23, 25, 6, 8, 0, 23, 8, 21, 22, 15, 20, 1, 19, 19, 12, 9, 15, 22, 8, 25, 8, 19, 22, 25, 19. Sẽ tương ứng với xâu bản mã là:

VPXZGIAXIVWPUBTTMJPWIZITWZT

Để giải mã ta biến đổi các phần tử của bản mã thành các thặng dư theo modulo 26, viết chúng thành các nhóm 6 rồi trừ với từ khoá theo modulo 26. kết quả ta sẽ ra được bản rõ như sau: thiscryptosystemisnotsecure

Ý tưởng của mã hoán vị là giữ các ký tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này.

Mã hoán vị có thể được mô tả như sau:

Cho m là một số nguyên dương xác định nào đó. Cho P=C=(Z₂₆)^m và K gồm tất cả các hoán vị của 1, …, m. Đối với một khoá  (tức là một hoán vị) ta xác định. e_(x₁, …, x_m)=(x_(1), …, x_(m)) và

d_(y₁, …, y_m)=(y_ˉạ(1) , … , y_ˉạ(m) )

trong đó  ^-1 là hoán vị ngược của 

Trước tiên ta nhóm bản rõ thành các nhóm 6 ký tự:

shesel / lsseas / hellsb / ythese / ashore

Bây giờ mỗi nhóm 6 chữ cái được sắp xếp lại theo hoán vị , ta có:

EESLSH / SALSES / LSHBLE / HSYEET / HRAEOS

Như vậy bản mã là: EESLSHSALSESLSHBLEHSYEETHRAEOS

Để giải mã ta sử dụng phép hoán vị ngược của  là  ^-1 có dạng:

Ta cũng nhóm bản mã thành nhóm 6 ký tự:

EESLSH / SALSES / LSHBLE / HSYEET / HRAEOS

Mỗi nhóm 6 chữ cái được sắp xếp lại theo hoán vị ngược  ^-1 ta có:

shesel / lsseas / hellsb / ythese / ashore

Cuối cùng ta thu được bản rõ là: shesellsseashellsbytheseashore

Lược đồ mã hoá được sử dụng phổ biến nhất dựa trên cơ sở của DES được phát triển vào năm 1977 bởi cục tiêu chuẩn quốc gia Mỹ, bây giờ là học viện tiêu chuẩn và công nghệ quốc gia (NIST), chuẩn xử lý thông tin liên bang. Đối với DES, dữ liệu được mã hoá trong khối 64 bit sử dụng khoá 56 bit. Thuật toán chuyển 64 bit đầu vào, biến đổi và đưa ra 64 bit đầu ra.

DES được sử dụng phổ biến. Nó cũng là chủ đề của rất nhiều cuộc tranh luận về mức độ an toàn. Để hiểu rõ giá trị của những cuộc tranh luận về DES chúng ta xem qua lại lịch sử của DES.

Cuối những năm 1960, IBM đã đưa ra dự án nghiên cứu trong bảo mật máy tính. Dự án kết thúc vào năm 1971 với việc cho ra đời thuật toán gọi là LUCIFER, hệ mật LUCIFER đã được sử dụng trong hệ thống phân phát tiền, cũng được phát triển bởi IBM. LUCIFER là một khối mã hoá Feistel được thực hiện trên khối 64 bit, sử dụng khoá có độ dài 128 bit. Những kết quả đầy hứa hẹn đưa ra bởi dự án LUCIFER, IBM đã bắt tay vào công việc đầy nỗ lực để phát triển thành một sản phẩm mã hoá thương mại có thể bán được, đó là một sản phẩm lý tưởng có thể thực hiện được trên một chíp đơn. Công đầu phải kể đến Walter Tuchman và Carl Meyer, nó không chỉ làm rắc rối cho những nhà thiết kế mà còn cần phải có những lời khuyên của những nhà kỹ thuật và tư vấn ở bên ngoài đó là NSA. Kết quả của nỗ lực này là một phiên bản LUCIFER có chọn lọc kỹ lưỡng, phiên bản này có thể chống lại các phương pháp giải dịch, nhưng nó cũng làm giảm độ dài khoá xuống còn 56 bit, để phù hợp trên một chip đơn.

Năm 1973 cục tiêu chuẩn quốc gia Mỹ (NBS) đưa ra một yêu cầu đề nghị cho một chuẩn mã hoá quốc tế. IBM đã đưa ra xem xét những kết quả của dự án Tuchman-Meyer. Kết quả nó được đề nghị là thuật toán tốt nhất và được công nhận vào năm 1977 như là một chuẩn mã hoá dữ liệu.

Trước khi được công nhận như là một chuẩn mã hoá dữ liệu, DES đã trở thành chủ đề của nhiều cuộc phê bình mạnh mẽ, và sự phê bình này vẫn chưa lắng xuống cho đến ngày hôm nay. Có hai mặt được đưa ra làm nổi giận những nhà phê bình. Đầu tiên, chiều dài khoá của thuật toán LUCIFER nguyên thuỷ của IBM là 128 bit nhưng hệ thống được đề nghị chỉ dùng 56 bit, một sự giảm rất lớn trong độ dài khoá 72 bit. Những nhà phê bình lo sợ rằng (và vẫn sợ) chiều dài khoá quá nhỏ để chống lại những cuộc tấn công quy mô lớn. Mặt thứ 2 cần quan tâm là tiêu chuẩn thiết kế cho cấu trúc bên trong của DES, những hộp S phải được coi là mật. Như vậy, những người sử dụng không thể chắc chắn rằng cấu trúc bên trong của DES là tự do cho bất kỳ những điểm yếu được che dấu, điều này sẽ cho phép NSA hướng tới những thông báo giải mã không có lợi cho khoá. Những sự kiện xảy ra sau, đặc biệt gần đây làm việc trên những sự giải dịch khác nhau, dường như chỉ rõ rằng DES có một cấu trúc bên trong rất mạnh.

Ý tưởng về một hệ mật khoá công khai đã được Diffie và Hellman đưa ra vào 1976. Còn việc hiện thực hóa hệ mật khoá công khai thì do Rivest, Shamir và Adleman đưa ra đầu tiên vào 1977, họ đã tạo nên hệ mật RSA nổi tiếng.

Hệ mật này sử dụng các tính toán trong Z_n , trong đó n là tích của 2 số nguyên tố phân biệt p và q. Ta có thể mô tả hệ mật RSA như sau:

Cho n=p.q trong đó p và q là các số nguyên tố. Đặt P=C=Z_n và định nghĩa:

K=(n,p,q,a,b):n=pq, p,q là các số nguyên tố, ab1(mod (n))

Với K =(n,p,q,a,b) ta xác định

e_k(x)=x^b mod n

d_k(y)=y^a mod n

(x,y  Z_n) các giá trị n và b được công khai và các giá trị p, q,a được giữ kín, (n)=(p-1)(q-1)

Quá trình thực hiện hệ mật RSA: (người gửi:Alice; người nhận:Bob)

+ Bob tạo hai số nguyên tố lớn p và q

+ Bob tính n=pq và (n)=(p-1)(q-1)

+ Bob chọn một số ngẫu nhiên b (0

+ Bob tính a=b^-1 mod (n) bằng cách dùng thuật toán Euclide

+ Bob công bố n và b trong một danh bạ và dùng chúng làm khoá công khai.

Ví dụ: giả sử Bob chọn p=101 và q=113

Khi đó n=11413 và (n)=100x112=11200. vì 11200=2⁶5²7, nên có thể dùng một số nguyên b như một số mũ mã hoá khi và chỉ khi b không chia hết cho 2,5 hoặc 7.(vì thế trong thực tế Bob sẽ không phân tích (n)), anh ta sẽ kiểm tra điều kiện UCLN((n),b)=1 bằng thuật toán Euclide. Giả sử Bob chọn b=3533, khi đó theo thuật toán Euclide mở rộng: b^-1=6597 mod 11200. Bởi vậy, số mũ mật để giải mã cho Bob là a=6597. Bob sẽ công bố n=11413 và b=3533 trong một danh bạ. bây giờ, giả sử Alice muốn gửi bản rõ 9726 tới Bob. Cô ta sẽ tính

9726³⁵³³ mod 11413=5761 rồi gửi bản mã 5761 trên kênh. Khi Bob nhận được bản mã 5761, anh ta sử dụng số mũ a mật để tính: 5761⁶⁵⁹⁷ mod 11414=9726.

Với hệ mật RSA được trình bày ở trên ta thấy cách tấn công dễ thấy nhất đối với hệ mật này là thám mã cố gắng phân tích n ra các thừa số nguyên tố. Nếu thực hiện được phép phân tích này thì có thể dễ dàng tính được (n)=(p-1)(q-1) và rồi tính số mũ a và b đúng như Bob đã làm.Vì thế để hệ RSA được coi là mật thì nhất thiết n=pq phải là một số đủ lớn để việc phân tích nó sẽ không có khả năng về mặt tính toán.

Hệ mật Elgamal là một hệ mật mã công khai dựa trên bài toán logarithm rời rạc. Nó là một hệ mật 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 người gửi chọn. Bởi vậy sẽ có nhiều bản mã được mã từ cùng bản rõ.

Đặc trưng của bài toán: I = (p,,) trong đó p là số nguyên tố   Z_p là phần tử nguyên thuỷ,   Z_p^*

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 khoá công khai Elgamal trong Z_p^*:

Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Z_p là khó giải. cho   Z_p^* là phần tử nguyên thuỷ. Giả sử P=Z_p^*, C= Z_p^* x Z_p^*. Ta định nghĩa:

K=(p, ,a, ):   ^a (mod p)

Các giá trị p, ,  được công khai, còn a giữ kín

Với K=(p, ,a, ) và một số ngẫu nhiên bí mật k  Z_p-1 ta xác định:

e_k(x,k)=(y₁,y₂)

Trong đó

y₁ = ^k mod p

y₂ = x^k mod p

Với y₁, y₂  Z_p^* ta xác định:

d_k(y₁,y₂) = y₂(y₁^a)^-1 mod p

Ví dụ:

Cho p=2579,  =2, a=765. Khi đó =2⁷⁶⁵ mod 2579 = 949

Bây giờ giả sử người gửi muốn gửi thông báo x=1299 tới người nhận. Giả sử số ngẫu nhiên k mà người gửi chọn là k=853. Sau đó người gửi tính:

y₁ = 2⁸⁵³ mod 2579 = 435

y₂ = 1299 x 949⁸⁵³ mod 2579 = 2396

Khi người nhận thu được bản mã y = (435, 2396), người nhận tính

x = 2396 x (435⁷⁶⁵)^-1 mod 2579 = 1299

Đây chính là bản rõ mà người gửi đã mã hoá.

Để đánh giá một thuật toán mã hoá cần dựa vào các yếu tố như độ phức tạp, thời gian mã hoá và vấn đề phân phối khoá trong môi trường nhiều người dùng.

Các thuật toán mã hoá khoá đối xứng thường đơn giản dễ cài đặt, tốc độ mã hoá cao nhưng độ an toàn không cao do dễ bị lộ khoá. Khoá dễ bị đối phương sử dụng các hệ thống được thiết kế đặc biệt để chuyên phá khoá theo hình thức “biết từ hiện”, trong đó hệ thống thực hiện thử tất cả các khoá. Như thế, cho chuỗi từ hiện x và chuỗi mã tương ứng y, mọi khoá sẽ được thử để tìm khoá k thoả e_K(x)=y. Mà DES là một ví dụ điển hình với không gian khoá là 2⁵⁶ DES không đủ để an toàn ở mức độ cao. Mặc dù có những chỉ trích về độ an toàn, DES vẫn được áp dụng rộng rãi (chủ yếu là các ứng dụng ngân hàng), đó là do DES được cài đặt dễ dàng trên cả phần cứng cũng như phần mềm, vì DES chỉ sử dụng một phép toán cơ bản là phép XOR.

Các thuật toán mã hoá khoá công khai khắc phục được tình trạng dễ bị lộ khoá của thuật toán mã hoá khoá đối xứng. Tuy nhiên chi phí cài đặt cao, tốc độ mã hoá lại rất chậm.

RSA là thuật toán điển hình của mật mã hoá công khai, nó cho độ an toàn cao vì với n đủ lớn thì việc phân tích n =pq là khó có thể thực hiện được. Khi áp dụng vào trong thực tế nên sử dụng các số p và q có kích cỡ vào khoảng 100 chữ số để n có kích cỡ khoảng 200 chữ số, bởi vì hiện nay các thuật toán có thể phân tích một số có 130 chữ số.

Khoa CNTT

Th.s. Nguyễn Nguyên Ngọc

Tài liệu tham khảo

1. Lý thuyết mã

Nguyễn Thúy Vân, NXB khoa học và kỹ thuật

Nguyễn Bình, Viện kỹ thuật thông tin-1996