TÌM HIỂU HỆ MÃ CHUẨN CÀI ĐẶT DES VÀ THÁM MÃ 3 VÒNG

MỤC LỤC

 I .1   Giới thiệu. 3

I.2 Các Hệ Mã Thông Dụng:3

e. Phương pháp Affine. 4

f. Phương pháp Vigenere. 5

I.2 LẬP MÃ DES. 14

I. 3 THÁM MÃ DES. 16

I.3.1. Thám mã hệ DES - 3 vòng. 19

II.3.2. Thám mã hệ DES 6-vòng. 23

II.3. 3  Các thám mã vi sai khác. 27

1. CÀI ĐẶT THÁM MÃ DES 3 VÒNG.. 27

III.1 Giao Diện .27

III.2 XỬ LÝ

 LỜI NÓI ĐẦU

 Hiện nay, nước ta đang trong giai đoạn tiến hành công nghiệp hóa, hiện đại hóa đất nước. Tin học được xem là một trong những ngành mũi nhọn. Tin học đã và đang đóng góp rất nhiều cho xã hội trong mọi khía cạnh của cuộc sống.

 Mã hóa thông tin là một ngành quan trọng và có nhiều ứng dụng trong đời sống xã hội. Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử dụng ngày càng phổ biến hơn trong các lĩnh vực khác nhau trên Thế giới, từ các lĩnh vực an ninh, quân sự, quốc phòng…, cho đến các lĩnh vực dân sự như thương mại điện tử, ngân hàng…

 Ứng dụng mã hóa và bảo mật thông tin trong các hệ thống thương mại điện tử, giao dịch chứng khoán,… đã trở nên phổ biến trên thế giới và sẽ ngày càng trở nên quen thuộc với người dân Việt Nam. Tháng 7/2000, thị trường chứng khoán lần đầu tiên được hình thành tại Việt Nam; các thẻ tín dụng bắt đầu được sử dụng, các ứng dụng hệ thống thương mại điện tử đang ở bước đầu được quan tâm và xây dựng. Do đó, nhu cầu về các ứng dụng mã hóa và bảo mật thông tin trở nên rất cần thiết.

I.                MỘT SỐ PHƯƠNG PHÁP MÃ HÓA

I .1   Giới thiệu

Định nghĩa 1.1: Một hệ mã mật (cryptosystem) là một bộ-năm (P, C, K, E, D) thỏa mãn các điều kiện sau:

1.  P là không gian bản rõ. tập hợp hữu hạn tất cả các mẩu tin nguồn cần mã hóa có thể có
2. C  là không gian bản mã. tập hợp hữu hạn tất cả các mẩu tin có thể có sau khi mã hóa
3. K là không gian khoá. tập hợp hữu hạn các khóa có thể được sử dụng
4. Với mỗi khóa kÎK, tồn tại luật mã hóa e_kÎE  và luật giải mã d_kÎD tương ứng. Luật mã hóa e_k: P ® C và luật giải mã e_k: C ® P là hai ánh xạ thỏa mãn

Tính chất 4. là tính chất chính và quan trọng của một hệ thống mã hóa. Tính chất này bảo đảm việc mã hóa một mẩu tin xÎP bằng luật mã hóa e_kÎEcó thể được giải mã chính xác bằng luật d_kÎD.

Định nghĩa 1.2: Z_m được định nghĩa là tập hợp {0, 1, ..., m-1}, được trang bị phép cộng (ký hiệu +) và phép nhân (ký hiệu là ´). Phép cộng và phép nhân trong Z_m được thực hiện tương tự như trong Z, ngoại trừ kết quả tính theo modulo m

Ví dụ: Giả sử ta cần tính giá trị 11 ´ 13 trong Z₁₆. Trong Z, ta có kết quả của phép nhân 11´13=143. Do 143º15 (mod 16) nên 11´13=15 trong Z₁₆.

Một số tính chất của Z_m

1. Phép cộng đóng trong Z_m, i.e., " a, b Î Z_m, a+b Î Z_m
2. Tính giao hoán của phép cộng trong Z_m, i.e., " a, b Î Z_m, a+b =b+a
3. Tính kết hợp của phép cộng trong Z_m, i.e., " a, b, c Î Z_m, (a+b)+c =a+(b+c)
4. Z_m có phần tử trung hòa là 0, i.e., " a Î Z_m, a+0=0+a=a
5. Mọi phần tử a trong Z_m đều có phần tử đối là m – a
6. Phép nhân đóng trong Z_m, i.e., " a, b Î Z_m, a´bÎ Z_m
7. Tính giao hoán của phép cộng trong Z_m, i.e., " a, b Î Z_m, a´b=b´a
8. Tính kết hợp của phép cộng trong Z_m, i.e.,  " a, b, c Î Z_m, (a´b)´c =a´(b´c)
9. Z_m có phần tử đơn vị là 1, i.e., " a Î Z_m, a´1=1´a=a
10. Tính phân phối của phép nhân đối với phép cộng, i.e.,  " a, b, c Î Z_m, (a+b)´c =(a´c)+(b´c)
11. Z_mcó các tính chất 1, 3 – 5 nên tạo thành 1 nhóm. Do Z_m có tính chất 2 nên tạo thành nhóm Abel. Z_m có các tính chất (1) – (10) nên tạo thành 1 vành

I.2 Các Hệ Mã Thông Dụng:

1. Hệ Mã Đầy (Shift Cipher )

                 Shift Cipher là một trong những phương pháp lâu đời nhất được sử dụng để mã hóa. Thông điệp được mã hóa bằng cách dịch chuyển (xoay vòng) từng ký tự đi k  vị trí trong bảng chữ cái.

 Phương pháp Shift Cipher

                    Cho P = C = K = Z₂₆. Với 0 £ K £ 25, ta định nghĩa

            e_K = x + K mod 26

           d_K = y - K mod 26

(x,y Î Z₂₆)

 trong đó 26 là số ký tự  trong bảng chữ cái La tinh, một cách tương tự cũng có thể định nghĩa cho một bảng chữ cái bất kỳ. Đồng thời ta dễ dàng thấy rằng mã đẩy là một hệ mật mã vì d_K(e_K(x)) = x với mọi xÎZ₂₆.                   

1. Hệ KEYWORD-CEASAR

Trong hệ mã này khóa là một từ  nào đó được chọn trước, ví dụ PLAIN. Từ này xác định dãy số nguyên trong Z₂₆ (15,11,0,8,13) tương ứng với vị trí các chữ cái của các chữ được chọn trong bảng chữ cái. Bây giờ bản rõ sẽ được mã hóa bằng cách dùng các hàm lập mã theo thứ  tự:

                       e₁₅, e₁₁, e₀, e₈, e₁₃, e₁₅, e₁₁, e₀, e₈, e,...

với e_K là hàm lập mã trong hệ mã chuyển.

1. Hệ Mã Vuông (SQUARE)

Trong hệ này các từ khóa được dùng theo một cách khác hẳn. Ta dùng bảng chữ cái tiếng Anh (có thể bỏ đi chữ  Q, nếu muốn tổng số các chữ số là một số chính phương) và đòi hỏi mọi chữ  trong từ  khóa phải khác nhau. Bây giờ  mọi chữ của bảng chữ cái được viết dưới dạng một hình vuông, bắt đầu bằng từ  khóa và tiếp theo là những chữ cái còn lại theo thứ tự của bảng chữ.

d. Mã thế vị

 Một hệ mãkhác khánổi tiếng . Hệ mã này đã được sử dụng hàng trăm năm nay. Phương pháp :

Cho P = C = Z₂₆. K gồm tất cả các hoán vị có thể có của 26 ký hiệu 0,...,25.  Với mỗi hoán vị pÎK, ta định nghĩa:

e_p(x) = p(x)

và định nghĩa                 d_p(y) = p^-1(y)

với p ^-1 là hoán vị ngược của hoán vị p.

Trong mã thế vị ta có thể lấy P và C là các bảng chữ cái La tinh. Ta sử dụng Z₂₆ trong mã đẩy vì lập mã và giải mã đều là các phép toán đại số.

       e. Phương pháp Affine

 Cho P = C = Z₂₆ và cho

      K = {(a,b) Î Z₂₆ ´ Z₂₆ : gcd(a,26) = 1}

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

                         e_K(x) = ax+b mod 26

 và

                              d_K = a^-1(y-b) mod 26

  (x,y Î Z₂₆)

Phương pháp Affine lại là một trường hợp đặc biệt khác của Substitution Cipher.

Để có thể giải mã chính xác thông tin đã được mã hóa bằng hàm e_kÎ E thì e_k phải là một song ánh. Như vậy, với mỗi giá trị yÎZ₂₆, phương trình ax+bºy (mod 26) phải có nghiệm duy nhất xÎZ₂₆.

Phương trình ax+bºy (mod 26)  tương đương với axº(y–b ) (mod 26). Vậy, ta chỉ cần khảo sát phương trình axº(y–b ) (mod 26)

Định lý1.1: Phương trình ax+bºy (mod 26) có nghiệm duy nhất xÎZ₂₆ với mỗi giá trị bÎZ₂₆  khi và chỉ khi a và 26 nguyên tố cùng nhau.

Vậy, điều kiện a và 26 nguyên tố cùng nhau bảo đảm thông tin được mã hóa bằng hàm e_k có thể được giải mã và giải mã một cách chính xác.

Gọi f(26) là số lượng phần tử thuộc Z₂₆ và nguyên tố cùng nhau với 26.

Định lý 1.2: Nếu  với p_i là các số nguyên tố khác nhau và e_i Π Z⁺,1 £i£m thì

Trong phương pháp mã hóa Affine , ta có 26 khả năng chọn giá trị b, f(26) khả năng chọn giá trị a. Vậy, không gian khóa K có tất cả nf(26) phần tử.

Vấn đề đặt ra cho phương pháp mã hóa Affine Cipher là để có thể giải mã được thông tin đã được mã hóa cần phải tính giá trị phần tử nghịch đảo a^–1 Î Z₂₆.

f. Phương pháp Vigenere

phương pháp mã hóa Vigenere sử dụng một từ khóa (keyword) có độ dài m. Có thể xem như phương pháp mã hóa Vigenere Cipher bao gồm m phép mã hóa Shift Cipher được áp dụng luân phiên nhau theo chu kỳ.

Không gian khóa K của phương pháp Vigenere có số phần tử là 26_­­­­, lớn hơn hẳn phương pháp số lượng phần tử của không gian khóa K trong phương pháp Shift Cipher. Do đó, việc tìm ra mã khóa k để giải mã thông điệp đã được mã hóa sẽ khó khăn hơn đối với phương pháp Shift Cipher.

 Phương pháp mã hóa Vigenere Cipher

 Chọn số nguyên dương m. Định nghĩa P = C = K = (Z₂₆)^m

K = { (k₀, k₁, ..., k_r-1) Î (Z₂₆)^r}

Với mỗi khóa k = (k0, k1, ..., k_r-1) Î K, định nghĩa:

e_k(x₁, x₂, ..., x_m) = ((x₁+k₁) mod 26, (x₂+k₂) mod n, ..., (x_m+k_m) mod 26)

d_k(y₁, y₂, ..., y_m) = ((y₁–k₁) mod n, (y₂–k₂) mod n, ..., (y_m–k_m) mod 26)

với x, y Î (Z₂₆)^m

 g. Hệ mã Hill

Phương pháp Hill Cipher được Lester S. Hill công bố năm 1929: Cho số nguyên dương m, định nghĩa P = C = (Z₂₆)^m. Mỗi phần tử xÎP là một bộ m thành phần, mỗi thành phần thuộc Z₂₆. Ý tưởng chính của phương pháp này là sử dụng m tổ hợp tuyến tính của m thành phần trong mỗi phần tử xÎP để phát sinh ra m thành phần tạo thành phần tử yÎC.

Phương pháp mã hóa Hill Cipher

Chọn số nguyên dương m. Định nghĩa:

P = C = (Z₂₆)^m và K là tập hợp các ma trận m´m khả nghịch

Với mỗi khóa , định nghĩa:

với x=(x₁, x₂, ..., x_m) Î P

và d_k(y) = yk^–1 với yÎ C

Mọi phép toán số học đều được thực hiện trên Z_n

h. Mã hoán vị

Những phương pháp mã hóa nêu trên đều dựa trên ý tưởng chung: thay thế mỗi ký tự trong thông điệp nguồn bằng một ký tự khác để tạo thành thông điệp đã được mã hóa. Ý tưởng chính của phương pháp mã hoán vị là vẫn giữ nguyên các ký tự trong thông điệp nguồn mà chỉ thay đổi vị trí các ký tự; nói cách khác thông điệp nguồn được mã hóa bằng cách sắp xếp lại các ký tự  trong đó.

Phương pháp mã hóa mã hoán vị

Chọn số nguyên dương m. Định nghĩa:

P = C = (Z₂₆)^m và K là tập hợp các hoán vị của m phần tử  {1, 2, ..., m}

Với mỗi khóa pÎ K, định nghĩa:

 và

với p^–1 hoán vị ngược của p

Phương pháp mã hoán vị chính là một trường hợp đặc biệt của phương pháp Hill. Với mỗi hoán vị p của tập hợp {1, 2, ..., m} , ta xác định ma trận k_p = (k_{i, j} ) theo công thức sau:

Ma trận k_p là ma trận mà mỗi dòng và mỗi cột có đúng một phần tử mang giá trị 1, các phần tử còn lại trong ma trận đều bằng 0. Ma trận này có thể thu được bằng cách hoán vị các hàng hay các cột của ma trận đơn vị I_m nên k_plà ma trận khả nghịch. Rõ ràng, mã hóa bằng phương pháp Hill với ma trận k_phoàn toàn tương đương với mã hóa bằng phương pháp mã hoán vị với hoán vị p.

1. Mã vòng

Trong các hệ trước đều cùng một cách thức là các phần tử kế tiếp nhau của bản rõ đều được mã hóa với cùng một khóa K. Như vậy xâu mã y sẽ có dạng sau:

y = y₁y₂... = e_K(x₁) e_K(x₂)...

Các hệ mã loại này thường được gọi là mã khối (block cipher).

Còn đối với các hệ mã dòng. Ý tưởng ở đây là sinh ra một chuỗi khóa z = z₁z₂..., và sử dụng nó để mã hóa xâu bản rõ x = x₁x₂...theo qui tắc sau:

 I.3  Quy trình thám mã:

Cứ mỗi phương pháp mã hoá ta lại có một phương pháp thám mã tương ứng nhưng nguyên tắc chung để việc thám mã được thành công thì yêu cầu người thám mã phải biết hệ mã nào được dùng hoá. Ngoài ra ta còn phải biết được bản mã và bản rõ ứng.

nhìn chung các hệ mã đối xứng là dễ cài đặt với tốc độ thực thi nhanh.

Tính an toàn của nó phụ thuộc vào các yếu tố :

• Không gian khoá phải đủ lớn
• với các phép trộn thích hợp các hệ mã đối xứng có thể tạo ra được một hệ mã mới có tính an toàn cao.
• bảo mật cho việc truyền khóa cũng cần được xử lý một cách nghiêm túc.

Và một hệ mã hoá dữ liệu ra đời (DES). DES  được xem như  là chuẩn mã hóa dữ liệu cho các ứng dụng từ ngày 15 tháng 1 năm 1977 do Ủy ban Quốc gia về Tiêu chuẩn của Mỹ xác nhận và cứ  5 năm một lần lại có chỉnh sửa, bổ sung.

DES là một hệ mã được trộn bởi các phép thế và hoán vị. với phép trộn thích hợp thì việc giải mã nó lại là một bài toán khá khó. Đồng thời việc cài đặt hệ mã này cho những ứng dụng thực tế lại khá thuận lợi. Chính  những lý do đó nó được ứng dụng rộng rãi của DES trong suốt hơn 20 năm qua, không những tại Mỹ mà còn là hầu như trên khắp thế giới. Mặc dù theo công bố mới nhất (năm 1998) thì mọi hệ DES, với những khả năng của máy tính hiện nay, đều có thể bẻ khóa trong hơn 2 giờ. Tuy nhiên DES cho đến nay vẫn là một mô hình chuẩn cho những ứng dụng bảo mật trong thực tế.

II. HỆ MÃ CHUẨN DES (Data Encryption Standard)

II.1 Đặc tả DES

Phương pháp DES mã hóa từ x có 64 bit với khóa k có 56 bit thành một từ có y  64 bit. Thuật toán mã hóa bao gồm 3 giai đoạn:

1. Với từ cần mã hóa x có độ dài 64 bit, tạo ra từ x₀ (cũng có độ dài 64 bit) bằng cách hoán vị các bit trong từ x theo một hoán vị cho trước IP (Initial Permutation). Biểu diễn x₀ = IP(x) = L₀R₀, L₀ gồm 32 bit bên trái của x₀, R₀ gồm 32 bit bên phải của x₀

Hình.1 Biểu diễn dãy 64 bit x thành 2 thành phần L và R

2. Xác định các cặp từ 32 bit L_i, R_i với 1£ i £ 16theo quy tắc sau:

L_i = R_i-1

R_i = L_i-1Å f (R_i-1, K_i)   

với Å biểu diễn phép toán XOR trên hai dãy bit, K₁, K₂, ..., K₁₆ là các dãy 48 bit phát sinh từ khóa K cho trước (Trên thực tế, mỗi khóa K_i được phát sinh bằng cách hoán vị các bit trong khóa K cho trước).

Hình.2 Quy trình phát sinh dãy 64 bit L_iR_i từ dãy 64 bit L_i-1R_i-1và khóa K_i

3. Áp dụng hoán vị ngược IP^-1 đối với dãy bit R₁₆L₁₆, thu được từ y gồm 64 bit. Như vậy, y = IP^-1 (R₁₆L₁₆)