Toán học và mật mã

52

N. Vilenkin

Matematika
và mật mã

Holmes nói: “Những gì do một người phát minh ra thì người khác có thể hiểu được.

Arthur Conan Doyle.
“Người nhảy múa”

Lá thư vô nghĩa

Mọi người từ lâu đã tìm mọi cách để bảo vệ tin nhắn khỏi những con mắt tò mò. Ví dụ, một vị vua thời xưa đã cạo đầu một sứ giả, viết một thông điệp lên đó và chỉ gửi sứ giả đến đồng minh của mình khi tóc trên đầu ông ta đã mọc lại. Sự phát triển của hóa học đã cung cấp một phương tiện thuận tiện hơn: một loại mực đẹp hơn, chữ viết không thể nhìn thấy được cho đến khi giấy được làm nóng hoặc tạo hình bằng một loại hóa chất nào đó. Trong hầu hết các trường hợp, mật mã được sử dụng để viết bí mật. Chúng được sử dụng bởi các nhà ngoại giao muốn bảo vệ bí mật của các cuộc đàm phán, các nhà lãnh đạo quân sự ẩn náu theo lệnh của kẻ thù, các sĩ quan tình báo, v.v. Và vào thời cổ đại, chúng đã được sử dụng bởi những tên cướp biển, ghi chú vị trí của kho báu, nhà giả kim, thương gia, những kẻ âm mưu, v.v.

Lúc đầu, mật mã rất đơn giản. Ví dụ, các nhà ngoại giao Nga ở thế kỷ 15-16 đã sử dụng cái gọi là “chữ cái vô nghĩa”, trong đó tất cả các nguyên âm không thay đổi và các phụ âm được thay thế bằng nhau theo sơ đồ sau:

b c d j h h k l mn
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
shchts x ft srp

(ở dòng đầu tiên các phụ âm theo thứ tự chung và ở dòng thứ hai chúng theo thứ tự ngược lại). Ví dụ, cùng nhau “Great Sovereign” hóa ra là “She-

53

hãy ngồi cholucham.” Mã này rất đơn giản (thậm chí bạn có thể học cách nói “vô nghĩa”).

Dần dần, việc viết bí mật đã trở nên khả thi, nhưng ngay cả mật mã mà Công chúa Sophia sử dụng vào cuối thế kỷ 17 trong thư từ của cô với Vasily Golitsky cũng rất đơn giản - một trong những bức thư của cô đã được đăng trên tạp chí Khoa học và Đời sống vài năm trước, và nhiều độc giả đã giải mã nó. Kẻ phản bội Mazen cũng sử dụng mật mã. Như A. S. Pushkin viết trong tư thế “Poltava”:

“Trong đêm tối chúng như kẻ trộm,
Tiến hành các cuộc đàm phán của họ
Sự phản bội được coi trọng giữa họ,
Họ làm cho kỹ thuật số trở nên phổ biến…”

Shfr nên là gì?

Khi khắc, phải đáp ứng một số điều kiện nhất định. Đầu tiên, các chữ cái khác nhau phải được thể hiện bằng các dấu hiệu khác nhau - nếu không, người nhận sẽ phải đoán chữ cái nào trong số nhiều chữ cái đại diện cho dấu hiệu nào. Hơn nữa, mã phải khó giải - mã nhẹ chỉ có thể được sử dụng với điều kiện kẻ thù không có thời gian để giải. Cuối cùng, tính bí mật của mã phải được kết hợp với tính đơn giản tương đối của các hoạt động mã hóa và giải mã - nếu không chúng sẽ mất nhiều thời gian đến mức thông tin được truyền đi trở nên mệt mỏi *). Và nếu việc giải mã đòi hỏi quá nhiều nỗ lực, thì bạn có thể thấy mình ở vị trí của người ghi chép huyền thoại, người đã viết những bức thư lấy phí ở một khu chợ phương Đông, nhưng cũng tính phí làm người đưa tin, tuyên bố rằng không ai ngoài chính anh ta có thể hiểu được những gì anh ta viết.

Chữ viết vô nghĩa đề cập đến các chữ viết trong đó mỗi chữ cái được thay thế bằng một dấu hiệu cụ thể - một chữ cái, số hoặc hình ảnh khác. Tương tự như vậy, tên cướp Chicago cuối cùng đã tự lừa dối mình trong truyện “Dancing” của Conan Doyle

*) Tuy nhiên, giờ đây những thao tác này có thể được giao phó cho máy tính.

người" và quyền trong truyện “Con bọ vàng” của Edgar Poe (chỉ các quyền cũng được sử dụng mực thông cảm). Đôi khi, để gây khó khăn cho việc đọc mã, người ta sử dụng các mã thừa - cùng một chữ cái được biểu thị bằng các dấu hiệu khác nhau. Sau đó, ngay cả khi kẻ thù đoán được ý nghĩa của một dấu hiệu, hắn sẽ không thể sử dụng điều này khi giải mã một phần khác của văn bản, vì ở đó, cùng một chữ cái sẽ được chỉ định là inchete.

Tuy nhiên, đôi khi sự dư thừa sẽ phát sinh một cách tự nhiên. Khi các chuyên gia về ngôn ngữ cổ bắt đầu giải mã các dòng chữ được tạo ra từ hàng nghìn năm trước bởi người Carians (một dân tộc sống ở Tiểu Á), họ phát hiện ra rằng số lượng ký tự quá lớn so với bảng chữ cái. Vì vậy, họ quyết định rằng dấu hiệu neokot có nghĩa là các chữ cái riêng lẻ và ký hiệu neokot có nghĩa là âm tiết. Tuy nhiên, những khó khăn không thể vượt qua đã nảy sinh trên con đường này. Và chỉ khi nhà khoa học Liên Xô V.V. Shevoroshkin bắt đầu nhận thấy ở những khu vực nào không có hơn ba chục dấu hiệu khác nhau được tìm thấy, tức là chữ viết vẫn còn là chữ cái. Chỉ ở những nơi khác nhau, các chữ cái neokot mới được mô tả khác nhau, điều này gây khó khăn cho việc giải mã các dòng chữ Carian.

Mật mã và tổ hợp

Vì tập hợp các dấu hiệu được sử dụng trong một mã đã cho là hữu hạn nên các phần tử của nó có thể được sắp xếp lại và số của chúng có thể được sử dụng cùng với chúng. Để đơn giản, chúng ta sẽ xem xét các cuộn trong đó không có dư thừa. Khi đó số lượng ký tự bằng số lượng chữ cái trong bảng chữ cái, cũng như các ký tự như khoảng trắng giữa các từ, dấu chấm, dấu phẩy. Đối với tiếng Nga, bạn có thể sử dụng 35 ký tự: 31 chữ cái (e, é và b, ѫ không khác nhau), dấu cách, dấu chấm, dấu phẩy, kiểu. Nếu số lượng ký tự được sử dụng trong shfro-

54

vani cũng bằng 35, khi đó mỗi shfr như vậy được xác định bằng ánh xạ một-một của một bộ gồm 35 phần tử sang một bộ khác như vậy. Trong tổ hợp, người ta đã chứng minh rằng số lượng ánh xạ như vậy là 35!, tức là tích của các số tự nhiên từ 1 đến 35. Đây là một con số khổng lồ đến mức khó có thể tưởng tượng được - nó xấp xỉ bằng $10^{40}$.

Xử lý các ánh xạ tùy ý $f$ của một tập hợp các chữ cái trong bảng chữ cái và dấu chấm câu $A = \{a_1, a_2, \ldots, a_{35}\}$ lên một tập hợp các dấu hiệu shfra $B = \{b_1, b_2, \ldots, b_{35}\}$ không thuận tiện lắm: rất khó để nhớ cách ánh xạ như vậy và việc mang theo một bảng ánh xạ bên mình - “chìa khóa” của shfra – là điều không mong muốn. Tốt hơn hết bạn nên có một số quy tắc đơn giản cho phép bạn tìm $f(k)$ bằng cách sử dụng $k$. Và các quy tắc cũng được đưa ra bằng các phương pháp toán học - xét cho cùng, không có gì tốt hơn để giải quyết mọi vấn đề phức tạp hơn là sử dụng các phương pháp toán học.

Mật mã và so sánh

Toán học từ lâu đã được sử dụng trong lý thuyết shfrov. Trở lại cuối thế kỷ 16, một trong những người sáng tạo ra đại số hiện đại, France Viète, đang giải mã thư từ giữa các đối thủ của vua Pháp Henry III. Và những kẻ âm mưu theo chủ nghĩa quân chủ Anh vào thế kỷ 17 đã rất ngạc nhiên trước tốc độ Cromwell thâm nhập vào kế hoạch của họ. Họ nghĩ rằng những bí mật mà họ sử dụng là không thể làm sáng tỏ và tin rằng chìa khóa của chúng đã được đưa ra bởi ai đó đang nghiên cứu âm mưu. Chỉ sau sự sụp đổ của Resurblika và sự gia nhập của Charles II, ông mới biết rằng tất cả những bí mật này đã được giải đáp bởi một trong những nhà toán học giỏi nhất thời bấy giờ, giáo sư Wallis của Đại học Oxford, người tự coi mình là người sáng lập ra một ngành khoa học mới - hình thái học phê phán.

Một phương pháp mã hóa như sau. Hãy chia chiếc nhẫn thành 35 phần bằng nhau, đánh số chúng và đánh dấu mỗi phần bằng một chữ cái hoặc dấu chấm câu (xem hình). Bây giờ, hãy chọn một số $a$ (“số phím” của shfra) và xoay vòng quanh tâm theo chiều kim đồng hồ để mỗi bộ phận di chuyển $a$ bước. Điều này xác định shfr—sự ánh xạ của tập hợp $A = \{a_1, a_2, \ldots, a_{35}\}$ lên tập hợp các dấu hiệu shfra $B = \{01, 02, \ldots, 35\}$ (trước các số có một chữ số, bạn phải viết 0, nếu không thì không rõ 15 là gì - “mười lăm” hay “một”, “năm”).

Ví dụ: nếu $a = 11$ thì phần được đánh dấu bằng số 01 sẽ đi vào phần được đánh dấu bằng số 12, nghĩa là chữ “A” khi được mã hóa sẽ tương ứng với số 12. Tương tự như vậy, chữ “B” tương ứng với số 14, v.v.

Kết quả là kết quả sau, trong đó mỗi chữ cái hoặc ký hiệu được viết dưới dạng hai số. Để giải mã địa chỉ, bạn cần chia chuỗi số kết quả thành các số gồm hai phần, trừ số khóa ở mỗi phần và thay thế số kết quả $k$ - số ký tự $a_k$ - bằng một chữ cái trong bảng chữ cái hoặc dấu chấm câu.

Tuy nhiên, trên thực tế, các quy tắc mã hóa và giải mã không đơn giản như vậy - nếu $k$ lớn hơn 24 thì tổng $k + 11$ lớn hơn 35 và trong tập $B$ số lớn nhất là 35. Nhưng ở đây chúng ta phải nhớ rằng chúng ta đã viết các số không phải trên một đường thẳng mà trên một vòng, và như bạn biết, một vòng không có đầu và không có kết thúc - sau số 35 là 1. Trong nói cách khác, sau số 35 mọi thứ lại lặp lại. Điều này có nghĩa là khi nhận được số tiền vượt quá 35, bạn cần trừ đi 35 từ số tiền đó.

55

ity và sẽ hiển thị số $a_k$ đi tới. Ví dụ: $a_{27}$ (chữ cái “ы”) không phải là số 38 mà là 03, $a_{32}$ (“dấu cách”) - thành 08, v.v. Như vậy,

$$f(a_k) = \begin{cases} k + 11, & \text{ если } k \leq 24, \\ k - 24, & \text{ если } 25 \leq k \leq 35. \end{cases}$$

Và việc giải mã được thực hiện theo công thức sau:

$$g(n) = \begin{cases} a_{n-11}, & \text{ если } 12 \leq n \leq 35, \\ a_{n+24}, & \text{ если } 1 \leq n \leq 11. \end{cases}$$

Quy tắc mã hóa có thể được viết gọn hơn nếu phép cộng được hiểu theo nghĩa đặc biệt.

Chúng ta hãy chia tất cả các số nguyên thành các lớp, gán cho một lớp những số có cùng số dư khi chia cho 35. Ví dụ: các số 32,3,38,73 sẽ thuộc cùng một lớp, vì tất cả chúng khi chia cho 35 đều có số dư là 3. Dạng tổng quát của các số trong lớp này là $3+35k$, trong đó $k$ là một số nguyên. Chúng ta hãy biểu thị bằng $Z_{35}$ tập hợp các lớp như vậy. Số lớp khác nhau là 35 (khi chia cho 35 thì số dư là 0, 1, 2, …, 34) và chúng có thể được ký hiệu bằng các số giống như số dư tương ứng, chỉ có dấu gạch ngang ở trên. Ví dụ: 5 không có nghĩa là số 5 mà là lớp chứa số này, tức là tập hợp các số {…, - 30, 5, 40, 75, …}. Cụ thể, 0 nghĩa là lớp chứa số 35.

Bây giờ chúng ta có thể viết rằng $27 + 11 = 3$, tức là bằng cách thêm 11 vào các số của lớp $27$, chúng ta sẽ có được các số từ lớp 3. Điều này có nghĩa là nếu các lớp từ $Z_{35}$ được coi là số các chữ cái được mã hóa và các ký hiệu của mã, thì công thức mã hóa và giải mã có thể được viết như sau:

$$f(a_k) = \bar{k} + 11,$$
$$g(n) = a_{n-11}.$$

Kiểu “số học” số dư này rất hữu ích trong nhiều vấn đề khác. Ví dụ: bây giờ hãy để kim phút chỉ 25 phút. Vị trí của nó sẽ như thế nào sau 176 phút? Để trả lời câu hỏi này, chỉ cần lưu ý rằng cứ sau 60 phút mũi tên lại trở về vị trí ban đầu. Do đó, ta cần tìm số dư của phép chia tổng 25 + 176 = 201 cho 60. Ta tìm được số dư này bằng 21. Điều này có nghĩa là ván bài sẽ chỉ 21 phút.

Để thuận tiện cho việc cộng trừ số dư khi chia cho $m$ trong số học, các bạn cần tạo bảng cộng. Để làm điều này, hãy lấy một bảng cộng tổng quát và thay thế mỗi số bằng số dư của nó khi chia cho $m$.

Số học như vậy thường được gọi là modulo số học $m$ và các số có số dư giống nhau khi chia cho $m$ được gọi là modulo so sánh được $m$. Nếu $a$ và $b$ có thể so sánh được theo modulo $m$, thì hãy viết

$$a \equiv b \pmod{m}.$$

Ví dụ,

$$215 \equiv 40 \pmod{7},$$

vì $k$ và 215 và 40 khi chia cho 7 dư 5.

Nếu người ta đã biết rằng mã nhận được bằng cách thêm cùng một số vào các số của chữ cái, thì có thể giải quyết vấn đề đó bằng cách đoán ý nghĩa của ít nhất một chữ cái, hoặc thậm chí tốt hơn là một vài chữ cái. Ví dụ: nếu biết rằng bức thư nói về Moscow và sự kết hợp “UHSHSYZ” thường được tìm thấy trong đó, thì rất dễ đoán rằng khi khắc số lượng mỗi chữ cái sẽ tăng thêm 7.

Một mã phức tạp hơn sẽ thu được nếu bạn thay thế phép cộng bằng phép nhân. Ví dụ: chúng ta sẽ nhân số của tất cả các chữ cái với 2. Tất nhiên, nếu kết quả lớn hơn 35 thì chúng ta phải thay thế bằng phần dư của phép chia cho 35. Ví dụ, chữ “CH” sẽ nhận được số 13 khi khắc, vì số của chữ “CH” là 24 và khi chia 24 2 = 48 cho 35 thì số dư là 13. Phép biến đổi này dễ gây nhầm lẫn hơn là phép cộng và người ta có thể sợ rằng các chữ cái khác nhau sẽ được mã hóa sẽ đi đến cùng một chữ cái. Nhưng may mắn thay, điều này sẽ không xảy ra trong trường hợp này - mã không có tính biểu cảm. Bằng chứng của khẳng định này dựa trên thực tế là tích của hai số chỉ chia hết cho 2 nếu một trong các thừa số là số chẵn. Và nếu chúng ta cố nhân các số chữ cái không phải với 2 mà với 5 (ước số là 35), chúng ta sẽ nhận được một mã suy biến (bạn hãy tự kiểm tra!). Các mã thú vị thu được khi phép nhân được thay thế bằng phép nhân trong st.