Đại số cơ bản đằng sau mật mã bí mật và truyền thông không gian

Khám phá không gian đòi hỏi độ chính xác cao. Khi bạn đang hạ cánh một chiếc xe tự hành trên sao Hỏa cách trạm dịch vụ gần nhất 70 triệu dặm, bạn cần tối đa hóa hiệu quả và chuẩn bị cho những điều bất ngờ. Điều này áp dụng cho mọi thứ, từ thiết kế tàu vũ trụ đến truyền dữ liệu: Những thông báo đó quay trở lại Trái đất dưới dạng dòng 0 và 1 ổn định chắc chắn sẽ chứa một số lỗi, vì vậy bạn cần có khả năng xác định và sửa chúng mà không lãng phí thời gian và năng lượng quý báu.

Đó là nơi toán học xuất hiện. Các nhà toán học đã phát minh ra những cách khéo léo để truyền và lưu trữ thông tin. Một phương pháp hiệu quả bất ngờ sử dụng Mã Reed-Solomon, được xây dựng trên cùng một đại số cơ bản mà học sinh học ở trường. Hãy tham gia một lớp học toán để xem mã Reed-Solomon giúp truyền và bảo mật thông tin như thế nào trong khi sửa bất kỳ lỗi tốn kém nào xuất hiện.

Hai học sinh Art và Zeke đang trao đổi những thông điệp bí mật trong lớp toán của cô Al-Jabr. Art mở ghi chú mới nhất của Zeke để tiết lộ các số 57 và 99. Anh ấy biết mình phải cung cấp x-tọa độ 3 và 6 để tạo các điểm (3, 57) và (6, 99). Nghệ thuật cắm từng điểm vào phương trình tuyến tính y = Ax + B và tạo ra hệ phương trình sau:

57 = 3A + B

99 = 6A + B

Để giải mã thông điệp, Art phải giải quyết A và B. Anh ấy bắt đầu bằng cách trừ phương trình thứ nhất từ ​​phương trình thứ hai:

Điều này giúp loại bỏ B. Chia cả hai vế của phương trình mới này cho 3 cho Art biết rằng A = 14, rồi thay giá trị này trở lại phương trình đầu tiên, 57 = 3 × 14 + B, cho B = 15.

Bây giờ Art biết rằng đường thẳng đi qua (3, 57) và (6, 99) được mô tả bởi phương trình y = 14x + 15. Nhưng anh ta cũng biết rằng trong mật mã Reed-Solomon, thông điệp bí mật được ẩn giấu trong các hệ số. Anh ấy giải mã tin nhắn của Zeke bằng cách sử dụng mật mã bảng chữ cái đơn giản theo thỏa thuận của họ: 14 là “N” và 15 là “O”, nói với Art rằng, không, Zeke không thể chơi trò chơi điện tử sau giờ học hôm nay.

Bí mật của mã Reed-Solomon đơn giản này bắt đầu với hai sự kiện cơ bản của hình học. Đầu tiên, qua hai điểm bất kỳ có một đường thẳng duy nhất. Thứ hai, đối với các hệ số A và B, mọi dòng (không thẳng đứng) có thể được viết dưới dạng y = Ax + B. Cùng với nhau, hai sự thật này đảm bảo rằng nếu bạn biết hai điểm trên một đường thẳng, bạn có thể tìm thấy A và B, và nếu bạn biết A và B, bạn biết tất cả các điểm trên đường thẳng. Nói tóm lại, sở hữu một trong hai bộ thông tin tương đương với việc biết dòng.

Mã Reed-Solomon tận dụng các bộ thông tin tương đương này. Thông điệp bí mật được mã hóa dưới dạng các hệ số A và Bvà các điểm của đường dây được chia thành nhiều phần, một số được truyền công khai và một số được giữ kín. Để giải mã thông điệp, bạn chỉ cần thu thập các mảnh và ghép chúng lại với nhau. Và tất cả những gì điều này yêu cầu là một vài phép tính đại số đơn giản.

Các mảnh của Zeke là số 57 và 99, mà anh ấy đã gửi cho Art. Những con số này là phần công khai của tin nhắn. Art ghép chúng lại với nhau bằng các mảnh của riêng mình, 3 và 6, để tái tạo lại các điểm (3, 57) và (6, 99). Ở đây, số 3 và số 6 tạo thành phần riêng tư của thông điệp mà Art và Zeke đã thỏa thuận trước.

Hai điểm nằm trên một đường thẳng và để giải mã thông điệp, bạn chỉ cần tìm phương trình của đường thẳng đó. Cắm từng điểm vào y = Ax + B cung cấp cho bạn một hệ hai phương trình về đường thẳng mà cả hai đều phải đúng. Bây giờ chiến lược rất đơn giản: Giải quyết hệ thống, xác định dòng và giải mã thông báo.

Trong lớp đại số, có lẽ bạn đã học nhiều phương pháp giải hệ phương trình, chẳng hạn như vẽ đồ thị, đoán và kiểm tra, và thay thế. Nghệ thuật đã sử dụng phép loại trừ, một phương pháp trong đó bạn thao tác các phương trình theo phương pháp đại số để loại bỏ từng biến một. Mỗi khi bạn loại bỏ một biến, hệ thống sẽ trở nên dễ giải quyết hơn một chút.

Cũng như các chương trình mã hóa khác, chính sự kết hợp thông minh giữa thông tin công khai và thông tin cá nhân giúp giữ an toàn cho các thông điệp. Zeke có thể hét số 57 và 99 của mình khắp lớp học và điều đó sẽ không gây nguy hiểm cho tính bảo mật của tin nhắn của anh ấy với Art (mặc dù điều đó có thể khiến anh ấy gặp rắc rối với cô Al-Jabr). Đó là bởi vì không có thông tin cá nhân tương ứng — x-tọa độ 3 và 6 — không thể xác định phương trình của đường thẳng. Miễn là họ giữ những giá trị đó cho riêng mình, họ có thể gửi thông điệp bí mật của mình một cách an toàn ở nơi công cộng.

Dòng y = 14x + 15 là tốt để truyền từ hai chữ cái “không”, nhưng nếu học sinh muốn chia sẻ một bí mật dài hơn thì sao? Đây là nơi toàn bộ sức mạnh của đại số, hình học và hệ phương trình tuyến tính phát huy tác dụng.

Giả sử Zeke muốn biết Art nghĩ anh ấy sẽ làm bài kiểm tra tiếng Anh ngày mai như thế nào. Art chuyển câu trả lời gồm ba chữ cái của mình thành các số 14, 59 và 82 rồi chuyển chúng cho Zeke. Các sinh viên đã đồng ý trước rằng khi sử dụng mã Reed-Solomon có độ dài 3, các số riêng của họ là 2, 5 và 6, vì vậy Zeke ghép các mảnh lại với nhau để tái tạo lại các điểm (2, 14), (5, 59) và (6, 82).

Bây giờ, không có hàm tuyến tính nào đi qua ba điểm này. Nhưng có một hàm bậc hai duy nhất làm được điều đó. Và vì mọi hàm bậc hai có thể được viết dưới dạng y = Ax² + Bx + C, cùng một phương pháp chung có thể được áp dụng. Sự khác biệt duy nhất là kích thước của hệ thống.

Cắm từng điểm vào y = Ax² + Bx + C mang lại một phương trình, vì vậy ba điểm tạo ra hệ thống ba phương trình sau:

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

Một hệ gồm ba phương trình với ba ẩn số đòi hỏi phải giải nhiều hơn một chút so với hệ hai phương trình với hai ẩn số, nhưng mục tiêu là như nhau: Khéo léo kết hợp các cặp phương trình để khử biến.

Ví dụ: nếu bạn trừ phương trình thứ nhất cho phương trình thứ hai, bạn sẽ nhận được phương trình mới 45 = 21A + 3B. Tương tự như vậy, nếu bạn trừ phương trình thứ hai từ phương trình thứ ba, bạn sẽ nhận được 23 = 11A + B. Những thao tác đại số này tạo ra một hệ thống mới:

45 = 21A + 3B

23 = 11A + B

Bây giờ bạn có một hệ thống “hai nhân hai”: hai phương trình với hai ẩn số. Để giải nó, bạn có thể nhân phương trình thứ hai với −3 và cộng nó vào phương trình thứ nhất:

Lưu ý cách loại bỏ nhiều lần đã biến hệ ba phương trình ban đầu thành một phương trình duy nhất có thể giải dễ dàng: A = 2. Làm ngược thì cắm được A = 2 vào một trong các phương trình trong hệ hai nhân hai để tìm B = 1, rồi thế cả hai giá trị vào một trong các phương trình ban đầu để có C = 4. Sau khi sử dụng mật mã bảng chữ cái đơn giản cho 2, 1 và 4, Zeke biết rằng Art sẽ làm bài “BAD” trong bài kiểm tra tiếng Anh ngày mai. Ít nhất thì anh ấy cũng được thực hành nhiều về đại số.

Nhờ một thực tế đặc biệt về các hàm đa thức, bạn có thể truyền một thông điệp có độ dài bất kỳ bằng cách sử dụng mã Reed-Solomon. Mấu chốt là thế này: Với bất kỳ n điểm trong mặt phẳng với các điểm khác nhau x-tọa độ, có một đa thức duy nhất của "bậc" n − 1 đi qua chúng. Bậc của một đa thức là lũy thừa cao nhất của một biến trong biểu thức, vì vậy một hàm bậc hai như Ax² + Bx + C có bậc 2, vì lũy thừa cao nhất của x là 2. Và một hàm tuyến tính có bậc 1, vì trong phương trình y = Ax + B, công suất cao nhất của x là 1.

Trong ví dụ đầu tiên, chúng tôi đã sử dụng thực tế là hai điểm xác định một đa thức tuyến tính hoặc bậc 1 duy nhất. Trong trường hợp thứ hai, chúng ta dựa vào thực tế là ba điểm xác định một đa thức bậc 2, hay bậc hai, duy nhất. Và nếu bạn muốn gửi một tin nhắn có độ dài 10, chỉ cần mã hóa tin nhắn dưới dạng 10 hệ số của hàm đa thức bậc 9. Khi bạn có chức năng của mình, hãy tính 10 công khai y-giá trị bằng cách đánh giá hàm ở 10 giá trị riêng đã thỏa thuận trước đó x-giá trị. Khi bạn làm điều đó, bạn có thể vượt qua chúng một cách an toàn y-tọa độ công khai để người nhận của bạn giải mã. Trong thực tế, mã Reed-Solomon phức tạp hơn mã này một chút, sử dụng các loại hệ số và lược đồ dịch phức tạp hơn, nhưng ý tưởng cơ bản là giống nhau.

Ngoài việc giữ an toàn cho tin nhắn của bạn, mã Reed-Solomon còn cung cấp những cách đơn giản và hiệu quả để phát hiện và thậm chí sửa lỗi. Điều này rất quan trọng bất cứ khi nào dữ liệu được truyền hoặc lưu trữ, vì luôn có khả năng một số thông tin sẽ bị mất hoặc bị hỏng.

Một giải pháp cho vấn đề này là chỉ cần gửi thêm các bản sao dữ liệu. Ví dụ: Zeke có thể gửi tin nhắn [14, 14, 14, 15, 15, 15] thay vì [14, 15]. Miễn là Art biết rằng mọi phần của tin nhắn được gửi ba lần, anh ta có thể giải mã tin nhắn và kiểm tra lỗi. Trên thực tế, nếu anh ấy tìm thấy bất kỳ lỗi nào, anh ấy có cơ hội tốt để sửa chúng. Nếu Art nhận được [14, 14, 24, 15, 15, 15], thì thực tế là ba số đầu tiên khác nhau sẽ cảnh báo anh ta về một lỗi và vì hai trong số đó là 14, anh ta có thể đoán rằng 24 có lẽ phải là một 14 cũng vậy. Thay vì yêu cầu gửi lại tin nhắn, Art có thể tiếp tục giải mã. Đây là một chiến lược hiệu quả nhưng tốn kém. Bất kể thời gian, năng lượng và nỗ lực được yêu cầu để gửi n mẩu thông tin, điều này đòi hỏi nhiều gấp ba lần.

Nhưng toán học đằng sau mã Reed-Solomon cung cấp một giải pháp thay thế hiệu quả. Thay vì gửi nhiều bản sao của mỗi phần dữ liệu, bạn chỉ cần gửi thêm một điểm! Nếu điểm bổ sung đó phù hợp với đa thức của bạn, thì thông tin đó là chính xác. Nếu không, đã xảy ra lỗi.

Để xem điều này hoạt động như thế nào, giả sử bạn muốn kiểm tra thông báo “KHÔNG” trong ví dụ đầu tiên. Zeke chỉ có thể gửi thêm y-phối hợp 155. Giả sử anh ta và Art đồng ý về một tư nhân thứ ba x-phối hợp trước, nói x = 10, Art có thể kiểm tra điểm thứ ba này so với dòng mà anh ấy đã giải mã. Khi anh cắm x = 10 vào y = 14x + 15 thấy kết quả là 155 thì biết đường truyền không có lỗi.

Điều này không chỉ làm việc cho các dòng. Để cho phép Zeke kiểm tra “BAD” trong ví dụ thứ hai, Art có thể gửi y = 25. Nếu họ đồng ý rằng 3 là số riêng tư bổ sung x-phối hợp, Zeke có thể cắm x = 3 vào hàm bậc hai của mình y = 2x² + x + 4 và xác minh rằng điểm (3, 25) phù hợp, một lần nữa xác nhận đường truyền không có lỗi chỉ với một điểm nữa.

Và điểm bổ sung đó cũng có khả năng sửa lỗi. Nếu một lỗi được phát hiện và người nhận không thể xây dựng hàm đa thức chứa thông báo, thay vào đó, họ có thể xây dựng đa thức “phù hợp nhất” bằng kỹ thuật hồi quy. Giống như một đường thẳng phù hợp nhất trong lớp thống kê, đây là hàm đa thức được xác định bằng toán học để khớp gần nhất với các điểm đã cho, ngay cả khi nó không đi qua tất cả các điểm đó. Tùy thuộc vào cấu trúc của thông báo và lượng thông tin bổ sung mà bạn gửi, đa thức phù hợp nhất này có thể giúp bạn xây dựng lại đa thức chính xác — và do đó là thông báo chính xác — ngay cả từ thông tin bị hỏng.

Hiệu quả trong việc truyền và sửa thông tin liên lạc này giải thích tại sao NASA đã sử dụng mã Reed-Solomon trong các sứ mệnh của mình lên mặt trăng và sao Hỏa. Và nó cung cấp cho bạn điều gì đó để suy ngẫm khi bạn giải hệ phương trình tiếp theo của mình. Khi bạn đoán, kiểm tra hoặc loại bỏ theo cách của bạn để tìm ra giải pháp, hãy nghĩ đến sức mạnh và sự sang trọng của mã Reed-Solomon và tất cả những bí mật mà hệ thống của bạn có thể tiết lộ.

Các bài tập

1. Sử dụng cùng một sơ đồ mà họ đã sử dụng trong lớp, Art đăng các số công khai 33 và 57 để Zeke giải mã. Thông điệp là gì?

2. Làm thế nào Art và Zeke có thể chắc chắn rằng hệ phương trình xuất phát từ các số riêng của họ x = 3 và x = 6 sẽ luôn có nghiệm?

3. Đáp lại tin nhắn “BAD” của Art về bài kiểm tra tiếng Anh, Zeke gửi lại [90, 387, 534]. Giả sử họ sử dụng cùng một sơ đồ mà họ đã sử dụng trong lớp, thông điệp của anh ấy là gì?

4. Lola gửi cho bạn một tin nhắn gồm hai chữ cái cùng với một số kiểm tra lỗi bằng cách sử dụng mã Reed-Solomon và cùng một mật mã bảng chữ cái đơn giản được sử dụng bởi Art và Zeke. Bạn đã bí mật đồng ý về x-đặt trước tọa độ 1, 3 và 10 và Lola truyền các số công khai [27, 43, 90]. Tin nhắn có lỗi không?