Mã hóa bằng phương pháp hoán vị. Các loại và phương pháp mật mã. Mật mã hoán vị
Cái gọi là thay đổi lộ trình, dựa trên một số hình học. Một đoạn văn bản gốc được viết thành hình như vậy theo một quỹ đạo nhất định. Bản mã là chuỗi thu được bằng cách viết văn bản theo một quỹ đạo khác. Ví dụ: bạn có thể viết tin nhắn trong bảng hình chữ nhật bằng cách chọn lộ trình sau: chúng ta sẽ di chuyển theo chiều ngang, bắt đầu từ góc trên bên trái, luân phiên từ trái sang phải và từ phải sang trái. Chúng ta sẽ sao chép tin nhắn theo một lộ trình khác: theo chiều dọc, bắt đầu từ góc trên bên phải và di chuyển luân phiên từ trên xuống dưới và từ dưới lên trên.
Ví dụ (hoán vị định tuyến)
Hãy mã hóa cụm từ bằng phương pháp trên ví dụ về hoán vị tuyến đường, dùng bàn hình chữ nhật 4x7:
| P | R | Và | tôi | e | R | tôi |
| N | T | Tại | R | w | R | MỘT |
| ồ | quần què | P | e | R | e | Với |
| Và | ĐẾN | V. | ồ | N | MỘT | T |
Cụm từ được mã hóa trông như thế này:
masteraerreshrnoermiupvkitrpnoi
Việc đảo ngược các bước được mô tả trong quá trình giải mã không khó.
Một loại hoán vị tuyến đường được gọi là sắp xếp lại theo chiều dọc. Hệ thống này cũng sử dụng một bảng hình chữ nhật, trong đó tin nhắn được viết theo cách thông thường (theo hàng từ trái sang phải). Tin nhắn được viết theo chiều dọc (từ trên xuống dưới), với các cột được chọn theo thứ tự được xác định phím số.
Ví dụ (sắp xếp lại theo chiều dọc)
Hãy mã hóa cụm từ Đây là một ví dụ về mật mã hoán vị dọc, sử dụng hình chữ nhật 6 x 7 và phím số (5,1,4,7,2,6,3).
Lưu ý rằng việc điền vào dòng cuối cùng của hình chữ nhật bằng các chữ cái "không hoạt động" là không phù hợp, vì điều này sẽ cung cấp cho kẻ thù nhận được mật mã này thông tin về độ dài của phím số. Thật vậy, trong trường hợp này, độ dài khóa phải được tìm kiếm trong số các ước số độ dài tin nhắn.
Bây giờ, viết các chữ cái trong các cột theo thứ tự được chỉ định bởi phím số, chúng ta nhận được mật mã sau:
oreekrfiyamaaeotshrnsivevlrvirkpnpitot
Khi giải mã, trước hết bạn cần xác định số cột dài, tức là số chữ cái ở dòng cuối cùng của hình chữ nhật. Để làm điều này, bạn cần chia số chữ cái trong tin nhắn cho độ dài của phím số. Rõ ràng phần dư của phép chia sẽ là số mong muốn. Khi con số này đã được xác định, các chữ cái trong mật mã có thể được đặt vào vị trí thích hợp và tin nhắn sẽ được đọc một cách tự nhiên.
Trong ví dụ của chúng tôi, 38=7x5+3, do đó bảng hoàn chỉnh có 3 cột dài và 4 cột ngắn.
Các hoán vị tuyến đường phức tạp hơn có thể sử dụng các hình dạng hình học khác và các tuyến đường “tinh ranh” hơn, chẳng hạn như khi đi vòng quanh bàn cờ với “nước đi của quân mã”, các đường đi trong mê cung nào đó, v.v. Các tùy chọn khả thi phụ thuộc vào trí tưởng tượng của trình biên dịch hệ thống và tất nhiên là yêu cầu tự nhiên về tính dễ sử dụng.
Mật mã thay thế (thay thế) dựa trên một phép toán đại số gọi là thay thế. Hoán vị là ánh xạ một-một của tập hữu hạn M lên chính nó. Số N phần tử của tập hợp được gọi là độ thay thế. Số n số thực sự được di chuyển bằng phép thay thế được gọi là độ dài của chu trình thay thế.
Mật mã hoán vị là một mật mã, sự chuyển đổi từ đó được thay đổi thứ tự xuất hiện duy nhất các ký tự của văn bản nguồn nhưng không tự thay đổi chúng.
Điểm yếu của mật mã thay thế. Nếu một ký tự nhất định xuất hiện thường xuyên trong một tin nhắn đang mở thì ký tự tương ứng đó sẽ xuất hiện với cùng tần suất trong tin nhắn được mã hóa. Đối với số lượng lớn văn bản, điều này dẫn đến việc phân tích mật mã thành công. Vì vậy, không thể mã hóa các tin nhắn đủ dài bằng một khóa.
Mạng (như một phần tử của mã hóa) - bất kỳ mật mã khối nào cũng là sự kết hợp của hai sơ đồ đầu tiên. Việc sử dụng khái niệm “mạng” trong mã hóa khối liên quan đến việc lặp lại các hoạt động ban đầu nhiều lần (các lần lặp lại là chu kỳ hoặc vòng và bản thân các hoạt động là các lớp). Một số lớp có thể chứa các khóa. Điều này cho phép:
- Làm cho mật mã trở nên dễ phức tạp (bằng cách tăng số vòng)
- Giảm kích thước mã
- Thống nhất công thức mã hóa thuật toán
Mạng Feisil (Feistel) là phương pháp xây dựng chu trình mã hóa theo thuật toán mã hóa lặp dựa trên thanh ghi dịch, có chức năng phản hồi tùy thuộc vào khóa tròn (số vòng tối ưu là từ 8 đến 32)
DES – Tiêu chuẩn mã hóa liên bang Hoa Kỳ (1997-2001).
Kiến trúc là một mạng Faisil cân bằng, cổ điển với các hoán vị bit đầu tiên và cuối cùng có dạng chung. Kích thước khóa là 56 bit. Nó dựa trên tiêu chuẩn quốc tế ISO 8372-87. Thuật toán được thiết kế để mã hóa dữ liệu theo khối 64 bit.
DES là sự kết hợp của hai phương pháp chính:
- Thay thế
- Sắp xếp lại.
Một sự kết hợp duy nhất của hai phương pháp này được áp dụng cho văn bản.
DES có 16 vòng, nghĩa là sự kết hợp các phương pháp tương tự được áp dụng cho bản rõ 16 lần.
Vòng khóa được áp dụng bằng thao tác XOR
Văn bản nguồn=>Hoán vị ban đầu=>Mã hóa * 16(<=Ключ) =>Hoán vị cuối cùng => bản mã
Mục đích của hoán vị ban đầu là phân bố đều các bit liền kề trên các khối.
Chức năng tương tự có thể được sử dụng để mã hóa và giải mã, nhưng các khóa được sử dụng theo thứ tự ngược lại.
DES cung cấp 4 loại công việc:
- Bảng mật mã điện tử ECB. Bản rõ được xử lý theo khối 64 bit, được mã hóa bằng một khóa
- CBC - chuỗi khối. Loại bỏ nhược điểm của chế độ đầu tiên. Giá trị đầu vào của thuật toán mã hóa được đặt bằng chênh lệch XOR giữa khối văn bản gốc hiện tại và khối văn bản mã hóa thu được ở bước trước. Như vậy, tất cả các khối của văn bản gốc đều được kết nối (text=>ciphertext=>XOR=>text=>ciphertext)
- CFB – phản hồi bản mã. Thuật toán được chuyển đổi thành mật mã luồng, nghĩa là mỗi ký tự có thể được mã hóa và truyền ngay lập tức đến người nhận
- OFB – phản hồi đầu ra. Một phần của bản mã được đưa vào thanh ghi dịch. Đối với mỗi phiên mã hóa, trạng thái ban đầu mới của thanh ghi sẽ được sử dụng.
Bốn chế độ được cho là đủ để sử dụng DES trong hầu hết mọi lĩnh vực mà thuật toán phù hợp
Việc triển khai phần cứng của thuật toán trên một chip riêng biệt giúp có thể đạt được tốc độ mã hóa cao với kích thước thiết bị nhỏ.
AES là tiêu chuẩn mã hóa liên bang Hoa Kỳ hiện đang được sử dụng.
AES là một tiêu chuẩn mã hóa tiên tiến.
Yêu cầu:
- Mật mã phải là khối
- Mật mã phải có độ dài khối 128 bit
- Mật mã phải hỗ trợ các khóa có độ dài 128, 192, 256 bit
Thuật toán này là một mật mã khối độc đáo vì nó không sử dụng mạng Feishtel để chuyển đổi mật mã.
Thuật toán biểu thị từng khối dữ liệu được mã hóa dưới dạng mảng byte hai chiều có kích thước 4x4, 4x6 hoặc 4x8, tùy thuộc vào độ dài khối đã đặt.
Thuật toán bao gồm một số vòng nhất định (từ 10 đến 14 - điều này phụ thuộc vào kích thước khối và độ dài khóa).
GOST 28147089 – Tiêu chuẩn của Nga về mã hóa dữ liệu và bảo vệ dữ liệu.
Thuật toán được thiết kế để triển khai phần cứng và phần mềm, đáp ứng các yêu cầu mật mã cần thiết và không áp đặt các hạn chế về mức độ bí mật của thông tin được bảo vệ.
Thuật toán thực hiện mã hóa các khối dữ liệu 64 bit bằng khóa 256 bit bao gồm 8 khóa con 32 bit.
Ở mỗi vòng thứ i, khóa con thứ K được sử dụng.
Thuật toán mã hóa GOST 28147-89 có những ưu điểm của các thuật toán khác dành cho hệ thống đối xứng và vượt trội hơn chúng về khả năng của chúng.
Ở mỗi vòng thứ i của thuật toán GOST, các thao tác sau được thực hiện:
L i =R i -1 , R i =L i -1 (cộng vòng tròn)f(R i -1 , K i)
Sau khi hoàn thành 32 thao tác này, việc thực hiện thuật toán mã hóa sẽ hoàn tất.
Ưu điểm của GOST là có khả năng bảo vệ chống lại việc áp đặt dữ liệu sai (chế độ chèn giả), cũng như chu trình mã hóa giống nhau ở cả 4 chế độ (thuật toán) của GOST.
Độ mạnh mật mã cao được đảm bảo nhờ độ dài khóa lớn (256 bit) và 32 vòng chuyển đổi.
Tiêu chuẩn bao gồm các chế độ (thuật toán):
- Chế độ thay thế dễ dàng
- Chế độ gamma
- Chế độ Gamma có phản hồi
- Chế độ tạo mô phỏng chèn
Thuật toán mã hóa bất đối xứng.
Trong các thuật toán mã hóa bất đối xứng (hoặc mật mã khóa công khai), một khóa (công khai) được sử dụng cho thông tin được mã hóa và một khóa khác (bí mật) được sử dụng để giải mã.
Các khóa này khác nhau và không thể bắt nguồn từ nhau.
Sơ đồ trao đổi thông tin:
- Người nhận tính toán khóa công khai và khóa bí mật, khóa bí mật được giữ bí mật nhưng khóa công khai được cung cấp (thông báo cho người gửi, một nhóm người dùng mạng, công bố)
- Người gửi sử dụng khóa chung của người nhận để mã hóa tin nhắn gửi đến người nhận
- Người nhận nhận được tin nhắn và giải mã nó bằng khóa riêng của mình
Sử dụng phương pháp mã hóa bất đối xứng
Việc sử dụng các mật mã như vậy trở nên khả thi nhờ K. Shannon, người đã đề xuất xây dựng một mật mã theo cách mà giải pháp của nó tương đương với việc giải một bài toán đòi hỏi phải thực hiện khối lượng tính toán vượt quá khả năng của máy tính hiện đại (ví dụ: các phép toán với các số nguyên tố lớn và tích của chúng, tìm giá trị của tích P = x*y)
Hệ thống mã hóa dữ liệu RSA.
Hiện tại, phương pháp bảo vệ thông tin mật mã được phát triển nhất với khóa đã biết là RSA, được đặt tên theo các chữ cái đầu trong tên của những người phát minh ra nó (Rivest, Shamir, Adleman)
Để sử dụng thuật toán RSA, trước tiên bạn phải tạo khóa chung và khóa riêng bằng cách làm theo các bước sau:
- Chọn hai số nguyên tố rất lớn p và q và xác định n là kết quả của phép nhân p với q (n=p*q)
- Chọn một số ngẫu nhiên lớn d. Số này phải nguyên tố cùng nhau với m, là kết quả của phép nhân (p-1)(q-1)
- Xác định một số e mà hệ thức sau đây là đúng (e*d)mod(m)=1 hoặc e=(1mod(m))/d
- Khóa công khai sẽ là các số e,n và khóa bí mật sẽ là các số d,n
Việc tạo khóa được tô sáng màu đỏ.
Hệ thống mật mã bất đối xứng dựa trên các đường cong elip.
Dựa trên các đường cong elip E, có thể thực hiện không chỉ các thuật toán mã hóa để mã hóa bất đối xứng mà còn tạo ra khóa bí mật chung cho mã hóa đối xứng.
Các hệ thống mật mã dựa trên các đường cong elip cho phép sử dụng kích thước khóa nhỏ hơn đáng kể so với các thuật toán mã hóa khác trong khi vẫn duy trì cùng mức độ mạnh của mật mã.
Đối với các triển khai ở trên, các đường cong elip trên trường Galois GF(p) với số hữu hạn p gồm các phần tử thuộc hai loại được sử dụng:
- Đường cong elip trên trường hữu hạn loại E(GF(p)), trong đó p là một số nguyên tố
- Đường cong elip trên trường hữu hạn loại E(GF(2m)), trong đó p=2m
Ví dụ: Thuật toán mã hóa bất đối xứng dựa trên các đường cong elip ECES (Lược đồ mã hóa đường cong Elliptic)
Thuật toán ElGamal.
Hệ thống ElGamal là một hệ thống mật mã khóa công khai dựa trên bài toán logarit. Thuật toán này được sử dụng cho cả mã hóa và chữ ký số.
Tập hợp các tham số hệ thống bao gồm số nguyên tố p và số nguyên g, lũy thừa của modulo p tạo ra một số lượng lớn các phần tử Z p
Các phương pháp thay thế.
Mật mã thay thế thay thế một số ký tự bằng các ký tự khác nhưng vẫn giữ nguyên thứ tự của chúng trong tin nhắn.
4 loại thay thế (thay thế):
- Đơn chữ cái. Công thức = Y i =k 1 X i +k 2 (modN), trong đó Y i là ký tự thứ i của bảng chữ cái, k 1, k 2 là các hằng số, X i là ký tự thứ i của bản rõ, N là ký tự thứ i của bản rõ độ dài của bảng chữ cái được sử dụng.
Ví dụ. Thay thế - bản rõ, Khóa - Khóa
- Thay thế đồng âm - thay thế một ký tự văn bản gốc khớp với một số ký tự văn bản mã hóa. Phương pháp này được sử dụng để làm sai lệch các thuộc tính thống kê của bản mã. Thay thế bảng được sử dụng. Các giá trị được sử dụng lần lượt từ cột.
- Thay thế nhiều bảng chữ cái là việc sử dụng nhiều bảng chữ cái. Bảng chữ cái thay đổi ở mỗi bước mã hóa. Việc thay thế từng bước các chữ cái theo bảng được sử dụng.
- Thay thế đa giác - được hình thành từ một bảng chữ cái bằng các quy tắc đặc biệt. Mật mã được đặt trong một ma trận và bản rõ được chia thành các cặp ký hiệu XiXi+1
Mật mã hoán vị.
Sự khác biệt giữa mật mã hoán vị là chỉ thay đổi thứ tự các ký tự của văn bản tương tự, nhưng bản thân chúng không thay đổi.
Ví dụ. Dòng chữ "Nạp cam vào thùng Anh em Karamazov"
Bản mã “Ptr_aezguionl_byseit_kramchaizryamaak_a__v_____oi”
dọc theo các đường đi khác nhau của một hình hình học.Ví dụ đơn giản nhất về hoán vị là hoán vị với khoảng thời gian cố định d. Trong phương pháp này, thông điệp được chia thành các khối theo d các ký tự và hoán vị tương tự được thực hiện trong mỗi khối. Quy tắc thực hiện hoán vị là một khóa và có thể được xác định bằng một số hoán vị của hoán vị đầu tiên. d số tự nhiên. Kết quả là bản thân các chữ cái của tin nhắn không thay đổi mà được truyền đi theo một thứ tự khác.
Ví dụ: với d=6, bạn có thể lấy 436215 làm khóa hoán vị. Điều này có nghĩa là trong mỗi khối gồm 6 ký tự, ký tự thứ tư lên vị trí đầu tiên, ký tự thứ ba lên vị trí thứ hai, ký tự thứ sáu lên vị trí thứ ba, v.v. Giả sử bạn cần mã hóa văn bản sau:
Số ký tự trong tin nhắn gốc là 24 nên tin nhắn phải được chia thành 4 khối. Kết quả mã hóa bằng hoán vị 436215 sẽ là thông điệp
OETET_TLSKDISHR_YAFNAVOI
Về mặt lý thuyết, nếu một khối bao gồm d ký tự, sau đó là số lượng hoán vị có thể có d!=1*2*...*(d-1)*d . Do đó, trong ví dụ cuối cùng d=6, số hoán vị là 6!=1*2*3*4*5*6=720. Do đó, nếu kẻ tấn công chặn được tin nhắn được mã hóa trong ví dụ trên, anh ta sẽ phải mất không quá 720 lần thử để giải quyết tin nhắn gốc (giả sử đối thủ đã biết kích thước khối).
Để tăng sức mạnh mật mã, hai hoặc nhiều hoán vị với các chu kỳ khác nhau có thể được áp dụng tuần tự cho tin nhắn được mã hóa.
Một ví dụ khác về phương pháp hoán vị là sắp xếp lại bảng. Trong phương pháp này, văn bản nguồn được viết dọc theo các hàng của bảng và đọc dọc theo các cột của cùng một bảng. Trình tự điền hàng và cột đọc có thể là bất kỳ thứ tự nào và được chỉ định bằng một khóa.
Hãy xem một ví dụ. Cho bảng mã hóa có 4 cột và 3 hàng (kích thước khối là 3*4=12 ký tự). Hãy mã hóa văn bản sau:
Số ký tự trong tin nhắn gốc là 24 nên tin nhắn phải được chia thành 2 khối. Hãy viết từng khối vào bảng riêng của nó theo từng dòng (Bảng 2.9).
| 1 khối | |||
|---|---|---|---|
| E | T | VỀ | |
| T | E | ĐẾN | VỚI |
| T | D | L | |
| 2 khối | |||
| TÔI | Sh | VÀ | |
| F | R | VỀ | TRONG |
| MỘT | N | VÀ | TÔI |
Sau đó, chúng ta sẽ đọc từng khối trong bảng một cách tuần tự theo từng cột:
ETTTE OKD SLYAFA RNSHOIVYA
Bạn có thể đọc các cột không tuần tự, nhưng, ví dụ, như thế này: thứ ba, thứ hai, thứ nhất, thứ tư:
OKDTE ETT SLSHOI RNYAFAIVA
Trong trường hợp này, thứ tự đọc các cột sẽ là chìa khóa.
Nếu như kích thước tin nhắn không phải là bội số của kích thước khối, bạn có thể bổ sung tin nhắn bằng bất kỳ ký hiệu nào không ảnh hưởng đến ý nghĩa, ví dụ: dấu cách. Tuy nhiên, điều này không được khuyến khích vì nó cung cấp cho kẻ thù, trong trường hợp chặn mật mã, thông tin về kích thước của bảng hoán vị được sử dụng (độ dài khối). Sau khi xác định độ dài khối, kẻ tấn công có thể tìm thấy độ dài khóa (số cột trong bảng) trong số các ước số độ dài khối.
Hãy xem cách mã hóa và giải mã một tin nhắn không phải là bội số của kích thước của bảng hoán vị. Hãy mã hóa từ
THAY ĐỔI
Số ký tự trong tin nhắn gốc là 9. Hãy viết tin nhắn vào bảng theo từng dòng (Bảng 2.10) và để trống ba ô cuối cùng.
Sau đó chúng ta sẽ đọc tuần tự từ bảng theo cột:
PMAEERNEC
Để giải mã, trước tiên hãy xác định số cột hoàn chỉnh, tức là số ký tự ở dòng cuối cùng. Vì điều này họ chia kích thước tin nhắn(trong ví dụ của chúng tôi – 9) theo số cột hoặc kích thước khóa (trong ví dụ – 4). Phần còn lại của phép chia sẽ là số cột đầy đủ: 9 mod 4 = 1. Do đó, trong ví dụ của chúng tôi có 1 cột đầy đủ và 3 cột ngắn. Bây giờ bạn có thể đặt các chữ cái trong tin nhắn vào đúng vị trí của chúng và giải mã tin nhắn. Vì khóa mã hóa là số 1234 (các cột được đọc tuần tự), nên khi giải mã, ba ký tự đầu tiên (PMA) được ghi vào cột đầu tiên của bảng hoán vị, hai ký tự tiếp theo (EE) - trong cột thứ hai, hai cái tiếp theo (RN) - ở phần thứ ba và hai cái cuối cùng (EK) - ở phần thứ tư. Sau khi điền vào bảng, chúng ta đọc các hàng và nhận được thông báo gốc CHANGE.
Có các phương pháp hoán vị khác có thể được thực hiện trong phần mềm và phần cứng. Ví dụ, khi truyền dữ liệu được ghi ở dạng nhị phân, sẽ thuận tiện hơn khi sử dụng một bộ phận phần cứng để xáo trộn các bit của thông điệp n-bit gốc theo một cách nhất định bằng cách sử dụng hệ thống dây điện thích hợp. Vì vậy, nếu chúng ta lấy kích thước khối là 8 bit, chẳng hạn, chúng ta có thể sử dụng khối hoán vị như
Mã hóa chuyển vị là các ký tự của bản rõ được sắp xếp lại theo một quy tắc nhất định trong một khối nhất định của văn bản này. Hãy xem xét một hoán vị được thiết kế để mã hóa một thông điệp có độ dài N nhân vật. Nó có thể được biểu diễn bằng sử dụng một cái bàn
Ở đâu Tôi 1 – số vị trí của bản mã nơi chữ cái đầu tiên của bản rõ rơi vào trong quá trình chuyển đổi đã chọn, Tôi 2 - số vị trí của chữ cái thứ hai, v.v. Ở dòng trên cùng của bảng là các số từ 1 đến N, và ở phía dưới là những con số giống nhau nhưng theo thứ tự ngẫu nhiên. Bảng này được gọi là hoán vị bậc N.
Biết hoán vị chỉ định phép biến đổi, có thể thực hiện cả mã hóa và giải mã văn bản. Trong trường hợp này, bảng hoán vị chính nó đóng vai trò là khóa mã hóa.
Số các phép biến đổi khác nhau của mật mã hoán vị được thiết kế để mã hóa thông điệp có độ dài N, nhỏ hơn hoặc bằng N! (N yếu tố). Lưu ý rằng con số này cũng bao gồm tùy chọn chuyển đổi để tất cả các ký tự ở đúng vị trí của chúng.
Với số lượng ngày càng tăng N nghĩa N! phát triển rất nhanh. Để sử dụng trong thực tế, mật mã như vậy không thuận tiện vì với các giá trị lớn N Tôi phải làm việc với những chiếc bàn dài. Do đó, các mật mã không sử dụng chính bảng hoán vị mà sử dụng một quy tắc nhất định tạo ra bảng này, đã trở nên phổ biến. Chúng ta hãy xem xét một vài ví dụ về mật mã như vậy.
Mật mã hoán vị Scytala.Được biết, vào thế kỷ thứ 5 trước Công nguyên, những người cai trị Sparta, quốc gia hiếu chiến nhất trong số các quốc gia Hy Lạp, đã có một hệ thống liên lạc quân sự bí mật phát triển tốt và mã hóa tin nhắn của họ bằng cách sử dụng lang thang thiết bị mật mã đơn giản đầu tiên thực hiện phương pháp hoán vị đơn giản.
Mã hóa được thực hiện như sau. Một dải giấy da được quấn theo hình xoắn ốc (quay lại) trên một thanh hình trụ, được gọi là skitala, và một số dòng văn bản thông báo được viết dọc theo thanh đó (Hình 1.2). Sau đó, một dải giấy da có chữ viết được lấy ra khỏi thanh. Các chữ cái trên dải này hóa ra được đặt một cách hỗn loạn.
Cơm. 1.2. Mã Scytala
Có thể đạt được kết quả tương tự nếu các chữ cái của tin nhắn được viết thành một vòng, không phải theo hàng mà thông qua một số vị trí nhất định cho đến khi hết toàn bộ văn bản. Tin nhắn " NÂNG CAO"Khi đặt xung quanh chu vi của thanh, mỗi chữ cái sẽ cho ra bản mã: " NUTAPESA_TY".
Để giải mã một bản mã như vậy, bạn không chỉ cần biết quy tắc mã hóa mà còn phải có khóa ở dạng một thanh có đường kính nhất định. Chỉ biết loại mật mã mà không có chìa khóa, việc giải mã tin nhắn không hề dễ dàng.
Các bảng mã hóa. Kể từ đầu thời kỳ Phục hưng (cuối thế kỷ 14), mật mã bắt đầu hồi sinh. Mật mã hoán vị được phát triển vào thời điểm đó sử dụng các bảng mã hóa, về bản chất, đặt ra các quy tắc cho việc hoán vị các chữ cái trong tin nhắn.
Các khóa được sử dụng trong bảng mã hóa là:
kích thước bàn;
từ hoặc cụm từ chỉ một hoán vị;
đặc điểm của cấu trúc bảng
Một trong những mật mã hoán vị bảng nguyên thủy nhất là hoán vị đơn giản, trong đó khóa là kích thước của bảng. Phương pháp mã hóa này tương tự như mật mã scytal. Ví dụ: tin nhắn " KẾT THÚC ĐẾN VÀO NGÀY THỨ BẢY VÀO NỬA ĐÊM"được ghi vào bảng theo từng cột một. Kết quả điền vào bảng 5 hàng 7 cột như hình 1.3.
Sau khi điền nội dung tin nhắn vào bảng, nội dung của bảng sẽ được đọc từng hàng để tạo thành văn bản mã hóa. Nếu bản mã được viết theo nhóm năm chữ cái thì kết quả là một tin nhắn được mã hóa: " TNPVE GLEAR ADONR TIEV OMOBT MPCHIR YSOOO".
Cơm. 1.3. Điền vào bảng mã hóa với 5 hàng và 7 cột
Đương nhiên, người gửi và người nhận tin nhắn phải đồng ý trước về khóa dùng chung dưới dạng kích thước bảng. Cần lưu ý rằng việc ghép các chữ cái mã hóa thành nhóm 5 chữ cái không có trong khóa mật mã và được thực hiện để thuận tiện cho việc viết văn bản vô nghĩa. Khi giải mã, các bước được thực hiện theo thứ tự ngược lại.
Một phương pháp mã hóa được gọi là hoán vị đơn theo khóa. Phương pháp này khác với phương pháp trước ở chỗ các cột trong bảng được sắp xếp lại theo từ khóa, cụm từ hoặc tập hợp số theo độ dài của hàng trong bảng.
Ví dụ, hãy sử dụng từ " BỒ NÔNG", và hãy lấy văn bản thông báo từ ví dụ trước. Hình 1.4 hiển thị hai bảng chứa văn bản thông báo và một từ khóa, với bảng bên trái tương ứng với việc điền trước khi sắp xếp lại và bảng bên phải để điền sau khi sắp xếp lại.
Cơm. 1.4. Bảng mã hóa chứa đầy từ khóa và văn bản tin nhắn
Hàng trên cùng của bảng bên trái chứa khóa và các số bên dưới các chữ cái chính được xác định theo thứ tự tự nhiên của các chữ cái chính tương ứng trong bảng chữ cái. Nếu có các chữ cái giống nhau trong khóa thì chúng sẽ được đánh số từ trái sang phải. Ở bảng bên phải, các cột được sắp xếp lại theo số thứ tự của các chữ cái chính.
Khi đọc nội dung của bảng bên phải theo từng hàng và viết bản mã theo nhóm năm chữ cái, chúng ta nhận được thông báo được mã hóa: " GNVEP LTOOA DRNEV TEIO RPOTM BCHMOR SOYYI".
Để cung cấp thêm quyền riêng tư, bạn có thể mã hóa lại tin nhắn đã được mã hóa. Phương pháp mã hóa này được gọi là hoán vị kép. Trong trường hợp hoán vị kép của cột và hàng, hoán vị của bảng được xác định riêng cho cột và riêng cho hàng. Đầu tiên, văn bản của tin nhắn được viết vào bảng, sau đó các cột và hàng được sắp xếp lại từng cái một. Khi giải mã, thứ tự hoán vị phải đảo ngược.
Một ví dụ về việc thực hiện mã hóa bằng phương pháp hoán vị kép được hiển thị trong Hình 2. 1.5. Nếu bạn đọc bản mã từ dòng bên phải của bảng theo từng dòng theo khối bốn chữ cái, bạn sẽ nhận được kết quả sau: " TYUAE OOGM RLIP OSV".
Cơm. 1.5. Một ví dụ về thực hiện mã hóa bằng phương pháp hoán vị kép
Chìa khóa của mật mã hoán vị kép là chuỗi số cột và số hàng của bảng nguồn (trong ví dụ của chúng tôi, các chuỗi lần lượt là 4132 và 3142).
Số lượng tùy chọn hoán vị kép tăng nhanh khi kích thước bảng tăng:
đối với bàn 3x3 có 36 lựa chọn;
đối với bảng 4x4 có 576 tùy chọn;
đối với một bảng 5x5 có 14400 tùy chọn.
Mã hóa bằng các ô vuông ma thuật. Vào thời Trung cổ, các ô vuông ma thuật cũng được sử dụng để mã hóa bằng hoán vị. . Hình vuông ma thuậtđược gọi là bảng vuông có các số tự nhiên liên tiếp được ghi trong các ô, bắt đầu từ 1, tổng mỗi cột, mỗi hàng và mỗi đường chéo đều bằng nhau.
Văn bản được mã hóa được nhập vào các ô vuông ma thuật theo cách đánh số các ô của chúng. Sau đó, nếu bạn viết nội dung của bảng đó ra từng dòng một, bạn sẽ nhận được một bản mã được hình thành bằng cách sắp xếp lại các chữ cái của tin nhắn gốc.
Một ví dụ về hình vuông ma thuật và điền thông điệp " TÔI SẼ ĐẾN VÀO NGÀY TÁM" được hiển thị trong Hình 1.6.
Cơm. 1.6. Ví dụ về hình vuông ma thuật 4x4 và điền thông điệp vào đó
Bản mã thu được bằng cách đọc nội dung của bảng bên phải theo từng hàng có vẻ ngoài hoàn toàn bí ẩn: " OIRM EOSYU VTA LGOP".
Số lượng hình vuông ma thuật tăng lên nhanh chóng khi kích thước của hình vuông tăng lên. Chỉ có một hình vuông ma thuật có kích thước 3x3 (nếu bạn không tính đến góc quay của nó). Số lượng ô vuông ma thuật 4x4 đã là 880 và số lượng ô vuông ma thuật 5x5 là khoảng 250.000.
Các bình phương ma thuật có kích thước trung bình và lớn có thể đóng vai trò là cơ sở tốt để đáp ứng nhu cầu mã hóa vào thời điểm đó, vì hầu như không thể tìm kiếm thủ công qua tất cả các tùy chọn cho một mật mã như vậy.
(Xem thêm )
Công trình của nhà toán học người Mỹ Claude Shannon xuất hiện vào giữa thế kỷ 20 đã có ảnh hưởng lớn đến sự phát triển của mật mã. Những công trình này đã đặt nền móng cho lý thuyết thông tin, đồng thời phát triển một bộ máy toán học phục vụ nghiên cứu trong nhiều lĩnh vực khoa học liên quan đến thông tin. Hơn nữa, người ta thường chấp nhận rằng lý thuyết thông tin như một ngành khoa học ra đời vào năm 1948 sau khi xuất bản tác phẩm “Lý thuyết toán học về truyền thông” của K. Shannon.
Trong tác phẩm “Lý thuyết truyền thông trong các hệ thống bí mật”, Claude Shannon đã tóm tắt kinh nghiệm tích lũy trước đó trong quá trình phát triển mật mã. Hóa ra là ngay cả trong những mật mã rất phức tạp như những mật mã đơn giản như mật mã thay thế, mật mã hoán vị hoặc sự kết hợp của chúng.
Đặc điểm chính mà mật mã được phân loại là loại biến đổi được thực hiện trên bản rõ trong quá trình mã hóa. Nếu các đoạn của bản rõ (các chữ cái riêng lẻ hoặc nhóm chữ cái) được thay thế bằng một số phần tương đương của chúng trong bản mã thì mật mã tương ứng thuộc loại mật mã thay thế. Nếu các chữ cái của bản rõ trong quá trình mã hóa chỉ thay đổi vị trí với nhau thì chúng ta đang xử lý mật mã hoán vị. Để tăng độ tin cậy của mã hóa, văn bản mã hóa thu được bằng một mật mã nhất định có thể được mã hóa lại bằng mật mã khác.
Cơm. 6.1.
Tất cả các kết hợp có thể có của các loại mật mã khác nhau đều dẫn đến lớp mật mã thứ ba, thường được gọi là mật mã thành phần. Lưu ý rằng mật mã tổng hợp có thể không được bao gồm trong lớp mật mã thay thế hoặc lớp mật mã hoán vị (Hình 6.1).
6.3 Mật mã hoán vị
Mật mã hoán vị, như tên gọi của nó, biến đổi hoán vị của các chữ cái trong bản rõ. Một ví dụ điển hình của mật mã hoán vị là mật mã Scital. Thông thường, bản rõ được chia thành các đoạn có độ dài bằng nhau và mỗi đoạn được mã hóa độc lập. Ví dụ: giả sử độ dài của các đoạn bằng nhau và là ánh xạ một-một của tập hợp 
vào chính bạn. Sau đó, mật mã hoán vị hoạt động như thế này: một đoạn văn bản gốc được chuyển đổi thành một đoạn văn bản mã hóa.
Một ví dụ kinh điển về mật mã như vậy là hệ thống sử dụng thẻ có lỗ - lưới tản nhiệt, khi dán lên một tờ giấy, chỉ để lại một số phần của nó. Khi được mã hóa, các chữ cái trong tin nhắn sẽ khớp với các lỗ này. Khi được giải mã, thông báo sẽ khớp với sơ đồ có kích thước yêu cầu, sau đó một lưới được xếp chồng lên nhau, sau đó chỉ hiển thị các chữ cái của bản rõ.
Các tùy chọn mật mã hoán vị khác cũng có thể thực hiện được, chẳng hạn như mật mã cột và hoán vị kép.
6.3.1 Mã hóa hoán vị cột
Trong quá trình giải mã, các chữ cái của bản mã được viết thành cột theo chuỗi số khóa, sau đó văn bản gốc được đọc theo hàng. Để dễ nhớ phím hơn, các cột trong bảng được sắp xếp lại theo từ khóa hoặc cụm từ, tất cả các ký tự trong đó đều được gán số được xác định theo thứ tự các chữ cái tương ứng trong bảng chữ cái.
Khi giải các bài toán giải mã các mật mã hoán vị, cần khôi phục lại thứ tự ban đầu của các chữ cái trong văn bản. Để thực hiện việc này, phân tích tính tương thích của ký tự được sử dụng mà bảng tương thích có thể trợ giúp (xem).
| G | VỚI | Bên trái | Ở bên phải | G | VỚI | |
|---|---|---|---|---|---|---|
| 3 | 97 | l, d, k, t, v, r, n | MỘT | l, n, s, t, r, v, k, m | 12 | 88 |
| 80 | 20 | tôi, e, y, tôi, một, o | B | o, s, e, a, r, y | 81 | 19 |
| 68 | 32 | tôi, t, a, e, tôi, o | TRONG | o, a, i, s, s, n, l, r | 60 | 40 |
| 78 | 22 | r, y, a, i, e, o | G | o, a, p, l, tôi, v | 69 | 31 |
| 72 | 28 | r, tôi, y, a, tôi, e, o | D | e, a, i, o, n, y, p, v | 68 | 32 |
| 19 | 81 | m, tôi, l, d, t, r, n | E | n, t, r, s, l, v, m, tôi | 12 | 88 |
| 83 | 17 | r, e, i, a, y, o | VÀ | e, tôi, d, a, n | 71 | 29 |
| 89 | 11 | o, e, a, và | 3 | a, n, c, o, m, d | 51 | 49 |
| 27 | 73 | r, t, m, tôi, o, l, n | VÀ | s, n, c, i, e, m, k, h | 25 | 75 |
| 55 | 45 | b, v, e, o, a, i, s | ĐẾN | o, a, i, p, y, t, l, e | 73 | 27 |
| 77 | 23 | g, v, s, i, e, o, a | L | tôi, e, o, a, b, tôi, yu, y | 75 | 25 |
| 80 | 20 | tôi, s, a, tôi, e, o | M | tôi, e, o, y, a, n, p, s | 73 | 27 |
| 55 | 45 | d, b, n, o, a, tôi, e | N | o, a, i, e, s, n, y | 80 | 20 |
| 11 | 89 | r, p, k, v, t, n | VỀ | c, s, t, r, i, d, n, m | 15 | 85 |
| 65 | 35 | trong, với, y, a, tôi, e, o | P | o, p, e, a, y, tôi, l | 68 | 32 |
| 55 | 45 | tôi, k, t, a, p, o, e | R | a, e, o, tôi, u, tôi, s, n | 80 | 20 |
| 69 | 31 | s, t, v, a, e, i, o | VỚI | t, k, o, i, e, b, s, n | 32 | 68 |
| 57 | 43 | h, y, i, a, e, o, s | T | o, a, e, i, b, v, r, s | 63 | 37 |
| 15 | 85 | p, t, k, d, n, m, r | bạn | t, p, s, d, n, y, w | 16 | 84 |
| 70 | 30 | n, a, e, o, và | F | và, e, o, a, e, o, a | 81 | 19 |
| 90 | 10 | y, e, o, a, s, và | X | o, tôi, s, n, v, p, r | 43 | 57 |
| 69 | 31 | e, yu, n, a, và | C | tôi, e, a, s | 93 | 7 |
| 82 | 18 | e, a, y, tôi, o | H | e, tôi, t, n | 66 | 34 |
| 67 | 33 | b, y, s, e, o, a, i, v | Sh | e, tôi, n, a, o, l | 68 | 32 |
| 84 | 16 | e, b, a, tôi, y | SCH | e, tôi, một | 97 | 3 |
| 0 | 100 | m, r, t, s, b, c, n | Y | L, x, e, m, i, v, s, n | 56 | 44 |
| 0 | 100 | n, s, t, l | b | n, k, v, p, s, e, o và | 24 | 76 |
| 14 | 86 | s, s, m, l, d, t, r, n | E | n, t, r, s, k | 0 | 100 |
| 58 | 42 | b, o, a, tôi, l, y | YU | d, t, sch, c, n, p | 11 | 89 |
| 43 | 57 | o, n, r, l, a, i, s | TÔI | c, s, t, p, d, k, m, l | 16 | 84 |
Khi phân tích tính tương thích của các chữ cái với nhau, cần lưu ý sự phụ thuộc của hình thức của các chữ cái trong văn bản thuần túy vào một số lượng đáng kể các chữ cái đứng trước. Để phân tích các mẫu này, khái niệm xác suất có điều kiện được sử dụng.
Câu hỏi về sự phụ thuộc của các chữ cái trong bảng chữ cái trong bản rõ vào các chữ cái trước đó đã được nhà toán học nổi tiếng người Nga A.A. Markov (1856-1922). Ông đã chứng minh rằng sự xuất hiện của các chữ cái trong bản rõ không thể được coi là độc lập với nhau. Về vấn đề này, A.A. Markov lưu ý một mẫu văn bản mở ổn định khác gắn liền với sự xen kẽ các nguyên âm và phụ âm. Ông đã tính toán tần suất xuất hiện của các nguyên âm lớn ( g, g), nguyên âm phụ âm ( g, s), phụ âm-nguyên âm ( s, g), phụ âm-phụ âm ( s, s) bằng văn bản tiếng Nga có độ dài ký tự. Kết quả tính toán được thể hiện ở bảng sau:
| G | VỚI | Tổng cộng | |
| G | 6588 | 38310 | 44898 |
| VỚI | 38296 | 16806 | 55102 |
Ví dụ 6.2 Bản rõ, giữ khoảng cách giữa các từ, được ghi lại trong một bảng. Bắt đầu ở dòng đầu tiên, văn bản được viết từ trái sang phải, chuyển từ dòng này sang dòng khác, mã hóa bao gồm việc sắp xếp lại các cột. Tìm bản rõ.
Văn bản mật mã:
| D | TRONG | Y | T | ||
| G | VỀ | E | R | VỀ | |
| bạn | b | D | bạn | B | |
| M | M | TÔI | Y | R | P |
Giải pháp. Hãy gán số cho các cột theo thứ tự chúng xuất hiện. Nhiệm vụ của chúng ta là tìm thứ tự các cột trong đó văn bản sẽ có ý nghĩa.
Hãy lập một bảng:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | X | |||||
| 2 | X | |||||
| 3 | X | |||||
| 4 | X | |||||
| 5 | X | |||||
| 6 | X |
Một ô (, ) trong bảng này có nghĩa là số cột theo sau số cột. Chúng tôi đánh dấu những trường hợp không thể thực hiện được bằng dấu "X".
Không thể kết hợp các cột 1, 2 và 5, 2 vì nguyên âm không thể xuất hiện trước dấu mềm. Trình tự các cột 2, 1 và 2, 5 cũng không thể xảy ra. Bây giờ, từ dòng thứ 3, 1, 5 và 5, 1 là không thể, vì УУ là một bigram không đặc trưng cho tiếng Nga. Tiếp theo, hai dấu cách liên tiếp không thể có trong văn bản, nghĩa là chúng ta phải đặt “X” vào các ô 3, 4 và 4, 3. Hãy quay lại dòng thứ ba. Nếu cột 2 theo sau cột 4, từ sẽ bắt đầu bằng dấu mềm. Ta điền dấu “X” vào ô 4, 2. Từ dòng đầu tiên: tổ hợp 4, 5 là không thể, tổ hợp 3, 5 cũng không được. Kết quả suy luận của chúng ta được trình bày trong bảng:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | X | X | X | |||
| 2 | X | X | X | |||
| 3 | X | X | X | |||
| 4 | X | X | X | X | ||
| 5 | X | X | X | |||
| 6 | X |
Vì vậy, sau cột 6 thì nhất thiết phải theo sau cột 5. Nhưng khi ta đánh dấu “X” vào ô 6, 2 thì ta được: cột 2 nối tiếp cột 3. Tiếp theo, ta gạch bỏ 5, 1 và 2, 1, do đó, chúng ta cần kiểm tra các tùy chọn: ..6532... và...65432... . Nhưng (4, 3) đã bị gạch bỏ trước đó. Vì vậy, các tùy chọn còn lại cho việc sắp xếp các cột là:
- 1, 6, 5, 3, 2, 4
- 6, 5, 3, 2, 4, 1
- 4, 1, 6, 5, 3, 2
- 1, 4, 6, 5, 3, 2
Hãy viết 6, 5, 3, 2 cột liên tiếp:
| 6 | 5 | 3 | 2 |
| T | S | - | V. |
| ồ | R | ồ | G |
| b | Tại | d | b |
| P | R | TÔI | tôi |
Cố gắng đặt cột 1 trước cột 6 sẽ dẫn đến MP bigram ở hàng cuối cùng và kết hợp DTY ở hàng đầu tiên. Các lựa chọn còn lại là: 653241, 146532.
Trả lời: 653241 - key, văn bản đơn giản: you\_on\_the road\_be\_stubborn (dòng từ một bài hát nổi tiếng trong những năm 1970).
Hãy đưa ra một ví dụ khác về phân tích mật mã hoán vị cột.
Ví dụ 6.3 Giải mã: SVPOOSLUYYST\_EDPSOKOKAIZO
Giải pháp. Văn bản chứa 25 ký tự, cho phép nó được viết dưới dạng ma trận vuông 5x5. Được biết, việc mã hóa được thực hiện theo từng cột nên việc giải mã phải được thực hiện bằng cách thay đổi thứ tự của các cột.
