Đồ án Thuật toán mã hoá và viết chương trình mã hoá ADFGVX

Lời nói đầu Khoa học mật mã đã ra đời từ hàng nghìn năm. Tuy nhiên, trong suốt nhiều thế kỷ, các kết quả của lĩnh vực này hầu như không được ứng dụng trong các lĩnh vực dân sự thông thường của đời sống – xã hội mà chủ yếu được sử dụng trong lĩnh vực quân sự, chính trị, ngoại giao... 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 trong các lĩnh vực khác nhau trên thế giới, từ các lĩnh vựcan 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… Với sự phát triển ngày càng nhanh chóng của Internet và các ứng dụng giao dịch điện tử trên mạng, nhu cầu bảo vệ thông tin trong các hệ thống và ứng dụng điện tử ngày càng được quan tâm và có ý nghĩa hết sức quan trọng. Các kết quả của khoa học mật mã ngày càng được triển khai trong nhiều lĩnh vực khác nhau của đời sống – xã hội, trong đó phải kể đến rất nhiều những ứng dụng đa dạng trong lĩnh vực dân sự, thương mại...Các ứng dụng mã hóa thông tin cá nhân, trao đổi thông tin kinh doanh, thực hiện các giao dịch điện tử qua mạng... đã trở nên gần gũi và quen thuộc với mọi người. Chúng ta phải thừa nhận rằng những rủi ro gặp phải trong quá trình giao dịch, kinh doanh trên mạng là hiện hữu; nguy cơ bị thay đổi, sao chép hoặc mất dữ liệu trên mạng thực sự một trở ngại trong giao dịch điện tử. Việc xác thực điện tử và kiểm tra tính toàn vẹn dữ liệu trong giao dịch điện tử là một trong các biện pháp đảm bảo an toàn thông tin; và vấn đề này là thật sự cần thiết và cấp bách. Với tầm quan trọng của việc mã hoá và bảo mật thông tin trong hầu hết mọi lĩnh vực đặc biệt là lĩnh vực Công Nghệ Thông Tin với đồ án của mình em xin được phép trình bày một số thuật toán mã hoá và viết chương trình mã hoá “ADFGVX” . Khi làm đồ án này mặc dù đã hết sức cố gắng nhưng cũng không tránh khỏi những sai sót nhất định em mong thầy cô cùng các bạn đóng góp thêm những ý kiến để từ đó em có thể phát triển hơn nữa đồ án chuyên nghành lần này thành đồ án tốt nghiệp.Xin trân trọng cảm ơn Mục lục Trang Lời mở đầu 1 Mục lục 3 Danh mục các hình 4 Chương 1:Tổng quan 5 1.1Mật mã học 5 1.2 Hệ thống mã hóa (cryptosystem) 6 1.3 Hệ thống mã hóa quy ước (mã hóa đối xứng) 7 1.4 Hệ thống mã hóa khóa công cộng (mã hóa bất đối xứng) 8 1.5 Kết hợp mã hóa quy ước và mã hóa khóa công cộng 8 Chương 2 Một số phương pháp mã hóa quy ước 9 2.1 Hệ thống mã hoá quy ước 9 2.2 Phương pháp dịch chuyển 10 2.3 Phương pháp thay thế 11 2.4 Phương pháp Affine 12 2.5 Phương pháp Vinegere 15 2.6 Phương pháp Hill 16 2.7 Mã hoán vị (MHV) 18 2.8 Phương pháp DES (Data Encryption Standard) 20 Chương 3 Các thuật toán ứng viên AES 24 3.1 Phương pháp chuẩn mã hoá nâng cao AES 24 3.2 Phương pháp mã hoá MARS 25 3.3 Phương pháp mã hoá RC6 30 3.4 Phương pháp mã hoá Serpent 35 Chương 4 Mật mã hoá ADFGVX 39 4.1 Lịch sử 39 4.2 Phương pháp bảo mật 40 4.3 Sơ đồ khối 45 4.4 Thuật toán 49 4.5 Bảng demo trước khi mã hoá 54 4.6Bảng demo sau khi mã hoá 55 4.5 Nhận xét về mã hoá ADFGVX và hướng phát triển đồ án 55 NHẬN XÉT GIÁO VIÊN HƯỚNG DẪN 56 NHẬN XÉT GIÁO VIÊN PHẢN BIỆN 57 TÀI LIỆU THAM KHẢO 58 Số TT Mô tả 01 Mô hình hệ thống mã hoá quy ước 02 Quy trình phát sinh dãy LiRj từ dãy Li-1Ri-1và khóa Ki 03 Quy trình mã hoá MARS 04 Cấu trúc mã hoá RC6 05 Chu trình thứ i trong quy trình mã hoá RC6 06 Mô hình phát sinh khoá Chương 1 Tổng Quan Nội dung của chương 1 giới thiệu tổng quan các khái niệm cơ bản về mật mã học và hệ thống mã hóa, đồng thời giới thiệu sơ lược về hệ thống mã hóa quy ước và hệ thống mã hóa khóa công cộng. 1.1 Mật mã học Mật mã học là ngành khoa học ứng dụng toán học vào việc biến đổi thông tin thành một dạng khác với mục đích che dấu nội dung, ý nghĩa thông tin cần mã hóa. Đây 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… Cùng với sự phát triển của khoa học máy tính và Internet, các nghiên cứu và ứng dụng của khoa học mật mã ngày càng trở nên đa dạng hơn, mở ra nhiều hướng nghiên cứu chuyên sâu vào từng lĩnh vực ứng dụng đặc thù với những đặc trưng riêng. Ứng dụng của khoa học mật mã không chỉ đơn thuần là mã hóa và giải mã thông tin mà còn bao gồm nhiều vấn đề khác nhau cần được nghiên cứu và giải quyết: chứng thực nguồn gốc nội dung thông tin (kỹ thuật chữ ký điện tử), chứng nhận tính xác thực về người sở hữu mã khóa (chứng nhận khóa công cộng), các quy trình giúp trao đổi thông tin và thực hiện giao dịch điện tử an toàn trên mạng... Những kết quả nghiên cứu về mật mã cũng đã được đưa vào trong các hệ thống phức tạp hơn, kết hợp với những kỹ thuật khác để đáp ứng yêu cầu đa dạng của các hệ thống ứng dụng khác nhau trong thực tế, ví dụ như hệ thống bỏ phiếu bầu cử qua mạng, hệ thống đào tạo từ xa, hệ thống quản lý an ninh của các đơn vị với hướng tiếp cận sinh trắc học, hệ thống cung cấp dịch vụ multimedia trên mạng với yêu cầu cung cấp dịch vụ và bảo vệ bản quyền sở hữu trí tuệ đối với thông tin số... 1.2 Hệ thống mã hóa (cryptosystem) Định nghĩa 1.1: Hệ thống mã hóa (cryptosystem) là một bộ năm (P, C, K, E, D) thỏa mãn các điều kiện sau: 1. Tập nguồn P là tập hữu hạn tất cả các mẩu tin nguồn cần mã hóa có thể có 2. Tập đích C là tập hữu hạn tất cả các mẩu tin có thể có sau khi mã hóa 3. Tập khóa K là tập hữu hạn các khóa có thể được sử dụng 4. E và D lần lượt là tập luật mã hóa và giải mã. Với mỗi khóa k ε K , tồn tại luật mã hóa ke ε E và luật giải mã k d ε D tương ứng. Luật mã hóa: k e P →C và luật giải mã : k e C →P là hai ánh xạ thỏa mãn ( ( )) , k k d e x = x ε x ε P 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 một mẩu tin x ε P được mã hóa bằng luật mã hóa ke ε E có thể được giải mã chính xác bằng luật k d ε D . Định nghĩa 1.2: Zm đượ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 Zm đượ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 Z16 . 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 Z16 . Một số tính chất của Zm 1. Phép cộng đóng trong Zm , , m a bε Z , m a + bε Z 2. Tính giao hoán của phép cộng trong Zm , , m a bε Z , a + b = b + a 3. Tính kết hợp của phép cộng trong Zm , , , m a b cε Z , (a + b) + c = a + (b + c) 4. Zm có phần tử trung hòa là 0, , m a bε Z , a + 0 = 0 + a = a 5. Mọi phần tử a trong Zm đều có phần tử đối là m − a 6. Phép nhân đóng trong Zm , , m a bε Z , m a×bε Z 7. Tính giao hoán của phép nhân trong Zm , , ma bε Z , a ×b = b× a 8. Tính kết hợp của phép nhân trong Zm , , , m a b cε Z , (a×b)×c = a×(b×c) 9. Zm có phần tử đơn vị là 1, , m a bε Z , 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, , , ma b cε Z , (a + b)× c = a× c + b× c Zm có các tính chất 1, 3 – 5 nên tạo thành một nhóm. Do Zm có tính chất 2 nên tạo thành nhóm Abel. Zm có các tính chất (1) – (10) nên tạo thành một vành. 1.3 Hệ thống mã hóa quy ước (mã hóa đối xứng) Trong hệ thống mã hóa quy ước, quá trình mã hóa và giải mã một thông điệp sử dụng cùng một mã khóa gọi là khóa bí mật (secret key) hay khóa đối xứng (symmetric key). Do đó, vấn đề bảo mật thông tin đã mã hóa hoàn toàn phụ thuộc vào việc giữ bí mật nội dung của mã khóa đã được sử dụng. Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý hiện nay, phương pháp mã hóa chuẩn (Data Encryption Standard – DES) đã trở nên không an toàn trong bảo mật thông tin. Do đó, Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (National Institute of Standards and Technology – NIST) đã quyết định chọn một chuẩn mã hóa mới với độ an toàn cao nhằm phục vụ nhu cầu bảo mật thông tin liên lạc của chính phủ Hoa Kỳ cũng như trong các ứng dụng dân sự. Thuật toán Rijndael do Vincent Rijmen và Joan Daeman đã được chính thức chọn trở thành chuẩn mã hóa nâng cao (Advanced Encryption Standard – AES) từ 02 tháng 10 năm 2000. 1.4 Hệ thống mã hóa khóa công cộng (mã hóa bất đối xứng) Nếu như vấn đề khó khăn đặt ra đối với các phương pháp mã hóa quy ước chính là bài toán trao đổi mã khóa thì ngược lại, các phương pháp mã hóa khóa công cộng giúp cho việc trao đổi mã khóa trở nên dễ dàng hơn. Nội dung của khóa công cộng (public key) không cần phải giữ bí mật như đối với khóa bí mật trong các phương pháp mã hóa quy ước. Sử dụng khóa công cộng, chúng ta có thể thiết lập một quy trình an toàn để truy đổi khóa bí mật được sử dụng trong hệ thống mã hóa quy ước. Trong những năm gần đây, các phương pháp mã hóa khóa công cộng, đặc biệt là phương pháp RSA [45], được sử dụng ngày càng nhiều trong các ứng dụng mã hóa trên thế giới và có thể xem như đây là phương pháp chuẩn được sử dụng phổ biến nhất trên Internet, ứng dụng trong việc bảo mật thông tin liên lạc cũng như trong lĩnh vực thương mại điện tử. 1.5 Kết hợp mã hóa quy ước và mã hóa khóa công cộng Các phương pháp mã hóa quy ước có ưu điểm xử lý rất nhanh và khả năng bảo mật cao so với các phương pháp mã hóa khóa công cộng nhưng lại gặp phải vấn đề khó khăn trong việc trao đổi mã khóa. Ngược lại, các phương pháp mã hóa khóa công cộng tuy xử lý thông tin chậm hơn nhưng lại cho phép người sử dụng trao đổi mã khóa dễ dàng hơn. Do đó, trong các ứng dụng thực tế, chúng ta cần phối hợp được ưu điểm của mỗi phương pháp mã hóa để xây dựng hệ thống mã hóa và bảo mật thông tin hiệu quả và an toàn Chương 2 Một số phương pháp mã hóa quy ước Trong chương 1 chúng ta đã tìm hiểu tổng quan về mật mã học và hệ thống mật mã .Nội dung của chương 2 sẽ giới thiệu chi tiết hơn về hệ thống mã hóa quy ước Một số phương pháp mã hóa quy ước kinh điển như phương pháp Phương pháp Affine ,Phương pháp Vigenere ,Phương pháp Hill , Phương pháp mã hóa hoán vị….cùng với các phương pháp mã hóa theo khối được sử dụng phổ biến trong những thập niên gần đây như DES, Tripple DES, AES cũng được giới thiệu trong chương này. 2.1 Hệ thống mã hóa quy ước Hệ thống mã hóa quy ước là hệ thống mã hóa trong đó quy trình mã hóa và giải mã đều sử dụng chung một khoá - khóa bí mật. Việc bảo mật thông tin phụ thuộc vào việc bảo mật khóa. Trong hệ thống mã hóa quy ước, thông điệp nguồn được mã hóa với mã khóa k được thống nhất trước giữa người gửi A và người nhận B. Người A sẽ sử dụng Một số phương pháp mã hóa quy ướcmã khóa k để mã hóa thông điệp x thành thông điệp y và gửi y cho người B; người B sẽ sử dụng mã khóa k để giải mã thông điệp y này. Vấn đề an toàn bảo mật thông tin được mã hóa phụ thuộc vào việc giữ bí mật nội dung mã khóa k. Nếu người C biết được mã khóa k thì C có thể “mở khóa” thông điệp đã được mã hóa mà người A gửi cho người B. Hình 1 :Mô hình hệ thống mã hoá quy ước 2.2 Phương pháp mã dịch chuyển Phương pháp mã hóa dịch chuyển 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. Trong trường hợp đặc biệt k = 3 , phương pháp mã hóa bằng dịch chuyển được gọi là phương pháp mã hóa Caesar Thuật toán Mã hóa dịch chuyển là một phương pháp mã hóa đơn giản, thao tác xử lý mã hóa và giải mã được thực hiện nhanh chóng. Tuy nhiên, trên thực tế, phương pháp này có thể dễ dàng bị phá vỡ bằng cách thử mọi khả năng khóa k ∈K . Điều này hoàn toàn có thể thực hiện được do không gian khóa K chỉ có n phần tử để chọn lựa. Ví dụ: Để mã hóa một thông điệp được biểu diễn bằng các chữ cái từ A đến Z (26 chữ cái), ta sử dụng 26 P = C = K = Z . Khi đó, thông điệp được mã hóa sẽ không an toàn và có thể dễ dàng bị giải mã bằng cách thử lần lượt 26 giá trị khóa k ε K . Tính trung bình, thông điệp đã được mã hóa có thể bị giải mã sau khoảng n / 2 lần thử khóa k ε K . 2.3 Phương pháp mã hoá thay thế Phương pháp mã hóa thay thế (Substitution Cipher) là một trong những phương pháp mã hóa nổi tiếng và đã được sử dụng từ hàng trăm năm nay. Phương pháp này thực hiện việc mã hóa thông điệp bằng cách hoán vị các phần tử trong bảng chữ cái hay tổng quát hơn là hoán vị các phần tử trong tập nguồn P. Thuật toán Đây là một phương pháp đơn giản, thao tác mã hóa và giải mã được thực hiện nhanh chóng. Phương pháp này khắc phục điểm hạn chế của phương pháp mã hóa bằng dịch chuyển là có không gian khóa K nhỏ nên dễ dàng bị giải mã bằng cách thử nghiệm lần lượt n giá trị khóa k ∈K . Trong phương pháp mã hóa thay thế có không gian khóa K rất lớn với n! phần tử nên không thể bị giải mã bằng cách “vét cạn” mọi trường hợp khóa k. Tuy nhiên, trên thực tế thông điệp được mã hóa bằng phương pháp này vẫn có thể bị giải mã nếu như có thể thiết lập được bảng tần số xuất hiện của các ký tự trong thông điệp hay nắm được một số từ, ngữ trong thông điệp nguồn ban đầu! 2.4Phương pháp Affine Trong mã Affine ta giới hạn chỉ xét các hàm mã có dạng : e(x)=ax + b mod 26 Trong đó a , b ε Z26 .Các hàm này được gọi là các hàm Affine Để việc giải mã có thể thực hiện được , yêu cầu cần thiết là các hàm Affine phải đơn ánh .Nói cách khác với bất kỳ y ε Z26 , ta muốn có đồng nhất thức sau: ax +b≡ y (mod 26) Phải có nghiệm duy nhất. Đồng dư thức này tương đương với ax≡ y-b(mod 26) Vì y thay đổi trên Z26 nên y-b cũng thay đổi trên Z26..Bởi vậy ta chỉ nghiên cứu phương trình đồng dư: ax ≡ y (mod 26) (y ε Z26 ). Ta biết rằng phương trình này có nghiệm duy nhất đối với mỗi y khi và chỉ khi UCLN(a,26)=1(ở đây hàm UCLN là ước chung lớn nhất của các biến của nó ).Trước tiên ta giả sử rằng, UCLN (a,26)=d>1.Khi đó đồng dư thức ax≡ 0(mod 26) sẽ có ít nhất 2 nghiệm phân biệt trong Z26 là x=0 va x=26/d.Trong trường hợp này, e(x)=ax+b mod 26 không phải là một hàm đơn ánh và bởi vậy nó không phải là một hàm đơn ánh hợp lệ Ví dụ, do UCLN(4,26) = 2 nên 4x +7 không là hàm mã hoá hợp lệ : x và x+13 sẽ mã hoá thành cùng một giá trị đối với bất kỳ x ε Z26 Ta giả thiết UCLN(a,26) = 1. Giả sử x1 và x2 nào đó thoả mảng: ax1 ≡ ax2 (mod 26) Khi đó: a(x1- x2) ≡ 0(mod 26) Bởi vậy: 26 | a(x1- x2) Bây giờ ta sử dụng một tính chất của phép chia sau: Nếu USLN(a,b)=1 và a|bc thì a |c. Vì 26|a(x1- x2) và USLN(a,26) = 1 nên ta có: 26 | (x1- x2) Nghĩa là: x1 ≡ x2 (mod 26) Tới đây ta chứng tỏ rằng,nếu UCLN(a,26) = 1 thì một đồng thức dạng ax ≡ y (mod 26) chỉ có ( nhiều nhất) một nghiêm trong Z26 .Do đó nếu ta cho x thay đổi trên Z26 thì ax mod 26 sẽ nhận đựơc 26 giá trị khác nhau theo modulo 26 và đồng dư thức ax ≡ y (mod 26) chỉ có một nghiệm y duy nhất Không có gì đặc biệt đối với số 26 trong khẳng định này.Bởi vậy bằng cách tương tự ta có thể chứng minh được kết quả sau : Định lý 2.4.1 Đồng dư thức ax ≡ b mod m chỉ có một nghiệm duy nhất x ε Zm với mọi b ε Zm và chỉ khi UCLN(a,m) = 1. Vì 26 = 2 ×13 nên các giá trị a ε Z26 thoả mãn UCLN(a,26)là a = 1 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 và 25. tham số có thể là một phần tử bất kỳ trong Z26 .Như vậy , mã Affine có 12 × 26 = 312 khoá có thể (dĩ nhiên con số này quá ít để đảm bảo an toàn) Bây giờ ta sẽ xét bài toán chung với modulo m.Ta cần một định nghĩa khác trong lý thuyết số . Định nghĩa 2.4.2 Giả sử a ≥ 1và m ≥ 2 là các số nguyên .UCLN(a,m) = 1thì ta nói rằng a và m là hai nguyên tố cùng nhau. Số các số nguyên trong Zm nguyên tố cùng nhau vời m thường được ký hiệu là φ(m). Một kết quả quan trọng trong lý thuyết số cho at giá trị của φ(m) theo các thừa số trong phép phân tích theo luỹ thừa các số nguyên tố của m . Định nghĩa 2.4.3 Giả sử a ε Zm .Phần tử nghịch đảo (theo phép nhân ) của a là phần tử a-1 ε Zm sao cho aa-1 ≡ aa-1 ≡ 1 (mod m). Bằng các lý luận tương tự như trên , có thể chwungs tỏ a có nghịch đảo theo modulo m khi và chỉ khi UCLN(a,m) =1,và nếu nghich đảo này tồn tại thì nó phải là duy nhất .ta cũng thay rằng nếu b = a-1 th× a = b-1.Nếu p là số nguyên tố thì mọi phần tử khác không của Zp đều có nghịch đảo .Một vài trong đó mọi phần tử đều có nghịch đảo được gọi là một trường . Trong phần sau sẽ mô tả một thuật toán hữu hiệu để tính các nghịch đảo của Zm vời m tùy ý.tuy nghien , trong Z26, chỉ bằng phương pháp thử và sai cũng có thể tìm được các nghich đảo của các phần tử nguyên tố cùng nhau với 26:1-1=1,3-1=9,5-1=21….( có thể dễ dàng kiểm chứng điều này , ví dụ 7 × 5 = 105 ≡ 1 mod 26 , bởi vậy7-1=15) Xét phương trình đồng dư y ≡ ax+b (mod 26).Phương trình này tương đương với ax ≡ y-b ( mod 26) Vì UCLN(a,26) =1 nên a có nghịch đảo theo modulo 26.Nhân cả 2 vế đồng thức dư a-1 ta có: a-1 (ax) ≡a-1 (y-b) (mod 26) Áp dụng tính kết hợp với phép nhân modulo a-1 (ax) ≡ (a-1 a)x ≡ 1x ≡ x. Kết quả là x ≡a-1 (y-b) (mod 26).Đây là một công thức tường minh cho x.Như vậy hàm giải mã là d(y) = a-1 (y-b) mod 26 Cho P=C=Z26 và giả sử P= {(a,b) ε Z26 *Z26 :UCLN(a,26)=1} Với K=(a,b) ε K, ta định nghĩa: Ek(x)=ax+b mod 26 Và Dk(y)=a-1(y-b) mod 26 x,y ε Z26 Ví dụ: Giả sử K = (7,3).Như đã nêu trên 7-1 mod 26 = 15 .Hàm mã hóa là : eK(x) = 7x+3 Và hàm giải mã tương ứng là dK(x) = 15(y-3) = 15y -19 Ở đây tất cả các phép toán đều thực hiện trên Z 26.ta sẽ kiểm tra liệu dK(eK(x)) = x với mọi x ε Z26 không ? Dùng các tính toán trên Z26 , ta có : dK(eK(x)) =dK(7x+3) =15(7x+3)-19 = x +45 -19 = x. Để minh hoạ , ta hãy mã hoá bản rõ “hot”.Trước tiên biến đổi các bản chữ h,o,t thành các thặng dư theo modulo 26.Ta được các số tương tứng là 7, 14 và 19.Bây giờ sẽ mã hoá : 7 × 7 +3 mod 26 = 52 mod 26 = 0 7 × 14 + 3 mod 26 = 101 mod 26 =23 7 × 19 +3 mod 26 = 136 mod 26 = 6 Bởi vậy 3 kí hiệu của bản mã là 0,23 và 6 tương ứng với xâu ký tự AXG 2.5 Phương pháp Vigenere Trong phương pháp mã hóa bằng thay thế cũng như các trường hợp đặc biệt của hương pháp này (mã hóa bằng dịch chuyển, mã hóa Affine,…), ứng với một hóa k được chọn, mỗi phần tử xε P được ánh xạ vào duy nhất một phần tử ∈C . Nói cách khác, ứng với mỗi khóa k ε K , một song ánh được thiết lập từ vào C. Phương pháp Vigenere sử dụng một từ khóa có độ ài m. Có thể xem như hương pháp mã hóa Vigenere Cipher bao gồm m phép Mã hóa bằng dịch chuyển đượ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 Cipher có số phần tử là nm , 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 háp mã hóa bằng dịch chuyển. 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 mã hóa bằng dịch chuyển.Thuật toán 2.6 Phương pháp Hill Phương pháp Hill được Lester S. Hill công bố năm 1929: Cho số nguyên dương m, định nghĩa P = C = Znm . Mỗi phần tử x ε P là một bộ m thành phần, mỗi thành phần thuộc Zn . Ý 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 .Thuật toán: Ví dụ : Giả sử khoá : K= Từ các tính toán trên ta có: K-1= Giả sử cần mã hoá bản rõ “July”.Ta có 2 phần tử bản rõ để mã hoá :(9,20) (ứng với Ju) và (11,24) (ứng với ly).Ta tính như sau : (9,20)= (99+60,72+140)=(3,4) Và: (11,24)= (121 +72, 88+168)=(11,22) Bởi vậy bản mã của “July” là DELW.Để giải mã ta sẽ tính : (3,4)=(9,20) Và: (11,22)= (11,24) Như vậy ta nhận được bản đúng.Cho tới lúc này ta chỉ ra rằng có thể thực hiện phép giải mã nếu K có một nghịch đảo.Trên thực tế để phép giải mã là có thể thực hiện được , điều kiện cần là K phải có khoá nghịch đảo.Bởi vậy chúng ta chỉ quan tâm đến ma trận khả nghịch. Tính khả nghịch của một ma trận vuông phụ thuộc vào giá trị định thức của nó .Để tránh sự tổng quát hoá không cần thiết, ta chỉ giới hạn trong trường hợp 2×2. Định nghĩa:Địng thức của ma trận A = (a,i j ) cấp 2× 2 là giá trị : det A = a1,1 a2,2 - a1,2 a2,1 Nhận xét:định thức của một ma trận vuông cấp mm có thể được tính theo các phép toán hằng sơ cấp.Hai tính chất quan trọng của định thức là det Im = 1 và quy tắc nhân det(AB) = det A × det B. Một ma trận K là có