Базова алгебра секретних кодів і космічного зв’язку

Дослідження космосу вимагає надзвичайної точності. Коли ви посадите марсохід на Марсі за 70 мільйонів миль від найближчої станції технічного обслуговування, вам потрібно максимально підвищити ефективність і підготуватися до несподіванок. Це стосується всього, від дизайну космічного корабля до передачі даних: ті повідомлення, які повертаються на Землю як постійний потік 0 і 1, обов’язково містять деякі помилки, тому вам потрібно вміти їх ідентифікувати та виправляти, не витрачаючи дорогоцінний час і енергію.

Ось тут на допомогу приходить математика. Математики винайшли геніальні способи передачі та зберігання інформації. Використовується один напрочуд ефективний метод Коди Ріда-Соломона, які побудовані на тій самій базовій алгебрі, яку учні вивчають у школі. Давайте заглянемо на урок математики, щоб побачити, як коди Ріда-Соломона допомагають передавати та захищати інформацію, одночасно виправляючи будь-які дорогі помилки, що виникають.

Двоє студентів, Арт і Зік, обмінюються секретними повідомленнями на уроці математики пані Аль-Джабр. Арт розгортає останню записку Зіка, щоб побачити числа 57 і 99. Він знає, що повинен надати x-координати 3 і 6 для створення точок (3, 57) і (6, 99). Арт вставляє кожну точку в лінійне рівняння y = Ax + B і створює таку систему рівнянь:

57 = 3A + B

99 = 6A + B

Щоб розшифрувати повідомлення, Арт має розгадати A та B. Він починає з віднімання першого рівняння від другого:

Це усуває B. Ділення обох частин цього нового рівняння на 3 говорить Арту про це A = 14, а потім підставляючи це назад у перше рівняння, 57 = 3 × 14 + B, дає B = 15.

Тепер Арт знає, що лінія, яка проходить через (3, 57) і (6, 99), описується рівнянням y = 14x + 15. Але він також знає, що в коді Ріда-Соломона секретне повідомлення ховається в коефіцієнтах. Він розшифровує повідомлення Зіка, використовуючи їхній простий узгоджений алфавітний шифр: 14 — «N», а 15 — «O», що говорить Арту, що ні, Зік не може грати у відеоігри сьогодні після школи.

Секрет цього простого коду Ріда-Соломона починається з двох основних фактів геометрії. По-перше, через будь-які дві точки проходить єдина пряма. По-друге, для коефіцієнтів A та B, кожен (невертикальний) рядок можна записати у формі y = Ax + B. Разом ці два факти гарантують, що якщо ви знаєте дві точки на прямій, ви можете знайти A та B, і якщо ви знаєте A та B, ви знаєте всі точки на лінії. Коротше кажучи, володіння будь-яким набором інформації еквівалентно знанню лінії.

Коди Ріда-Соломона використовують ці еквівалентні набори інформації. Секретне повідомлення закодовано у вигляді коефіцієнтів A та B, а точки лінії розбиваються на частини, деякі з яких передаються публічно, а деякі залишаються приватними. Щоб розшифрувати повідомлення, ви просто збираєте шматочки та збираєте їх разом. І все, що для цього потрібно, це проста алгебра.

Фрагментами Зіка були номери 57 і 99, які він відправив до Ст. Ці номери є публічною частиною повідомлення. Арт поєднав їх разом зі своїми власними творами, 3 і 6, щоб реконструювати точки (3, 57) і (6, 99). Тут 3 і 6 складають приватну частину повідомлення, про яку Арт і Зік домовилися заздалегідь.

Дві точки лежать на прямій, і щоб розшифрувати повідомлення, вам просто потрібно знайти рівняння цієї лінії. Підключення кожної точки до y = Ax + B дає вам систему двох рівнянь щодо лінії, обидва з яких мають бути істинними. Тепер стратегія проста: розв’яжіть систему, визначте рядок і розшифруйте повідомлення.

На уроці алгебри ви, напевно, навчилися багатьом методам розв’язування систем рівнянь, таким як побудова графіків, вгадування та перевірка та підстановка. Арт використовував елімінацію, метод, за якого ви маніпулюєте рівняннями алгебраїчно, щоб усувати змінні одну за одною. Кожного разу, коли ви усуваєте змінну, систему стає дещо легше вирішити.

Як і в інших схемах шифрування, це розумне поєднання публічної та приватної інформації, яке забезпечує безпеку повідомлень. Зік міг би кричати свої номери 57 і 99 по всій кімнаті, і це не загрожувало б безпеці його повідомлення Арту (хоча це могло б створити для нього проблеми з пані Аль-Джабр). Це тому, що без відповідної приватної інформації — x-координати 3 і 6 — неможливо ідентифікувати рівняння прямої. Поки вони зберігають ці цінності при собі, вони можуть безпечно передавати свої таємні повідомлення публічно.

Лінія y = 14x + 15 підходить для передачі слова з двох букв «ні», але що, якщо учні хочуть поділитися більшим секретом? Ось де реалізується вся потужність алгебри, геометрії та систем лінійних рівнянь.

Припустімо, Зік хоче знати, як Арт думає, що він впорається із завтрашнім тестом з англійської. Арт перетворює свою відповідь із трьох літер на числа 14, 59 і 82 і передає їх Зіку. Студенти заздалегідь домовилися, що при використанні кодів Ріда-Соломона довжиною 3 їхніми приватними числами є 2, 5 і 6, тому Зік збирає частини разом, щоб реконструювати точки (2, 14), (5, 59) і (6, 82).

Тепер не існує лінійної функції, яка б проходила через ці три точки. Але існує унікальна квадратична функція, яка це робить. А оскільки кожну квадратичну функцію можна записати у вигляді y = Ax² + Bx + C, можна застосувати той самий загальний метод. Єдина відмінність полягає в розмірі системи.

Підключення кожної точки до y = Ax² + Bx + C дає одне рівняння, тому три точки дають таку систему з трьох рівнянь:

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

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

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

Розв’язування системи з трьох рівнянь із трьома невідомими вимагає трохи більше роботи, ніж система з двох рівнянь із двома невідомими, але мета та сама: вміло об’єднати пари рівнянь, щоб усунути змінні.

Наприклад, якщо ви віднімете перше рівняння від другого, ви отримаєте нове рівняння 45 = 21A + 3B. Так само, якщо ви віднімете друге рівняння від третього, ви отримаєте 23 = 11A + B. Ці алгебраїчні маніпуляції створюють нову систему:

45 = 21A + 3B

23 = 11A + B

Тепер у вас є система «два на два»: два рівняння з двома невідомими. Щоб її розв’язати, ви можете помножити друге рівняння на −3 і додати його до першого рівняння:

Зверніть увагу, як повторне виключення перетворило вихідну систему з трьох рівнянь на одне рівняння, яке можна легко розв’язати: A = 2. Працюючи назад, ви можете підключити A = 2 в одне з рівнянь у системі два на два, щоб знайти B = 1, а потім підключіть обидва значення до одного з вихідних рівнянь, щоб отримати C = 4. Після використання простого алфавітного шифру на 2, 1 і 4 Зік знає, що Арт збирається поставити «ПОГАНО» на завтрашньому тесті з англійської мови. Принаймні він отримує багато практики з алгебри.

Завдяки особливому факту про поліноміальні функції, ви можете передати повідомлення будь-якої довжини за допомогою кодів Ріда-Соломона. Ключ ось у чому: враховуючи будь-які n точки на площині з різн x-координат, існує єдиний поліном “ступеня” n − 1, що проходить через них. Степінь полінома – це найвищий ступінь змінної у виразі, тому квадратична функція, як Ax² + Bx + C має ступінь 2, оскільки найвища потужність x дорівнює 2. А лінійна функція має ступінь 1, оскільки в рівнянні y = Ax + B, найвища потужність x є 1.

У першому прикладі ми використали той факт, що дві точки визначають унікальний лінійний поліном або ступінь 1. У другому випадку ми покладалися на той факт, що три точки визначають унікальний поліном ступеня 2, або квадратичний. І якщо ви хочете надіслати повідомлення довжиною 10, просто закодуйте повідомлення як 10 коефіцієнтів поліноміальної функції ступеня 9. Отримавши функцію, обчисліть 10 public y-значення шляхом оцінки функції за попередньо узгодженим 10 приватним x-цінності. Як тільки ви це зробите, ви можете спокійно пройти їх y-публічні координати для декодування вашим приймачем. На практиці коди Ріда-Соломона є дещо складнішими, ніж цей, вони використовують більш складні типи коефіцієнтів і схем перекладу, але фундаментальна ідея та сама.

Крім захисту вашого повідомлення, коди Ріда-Соломона також пропонують прості та ефективні способи виявлення та навіть виправлення помилок. Це важливо щоразу, коли дані передаються або зберігаються, оскільки завжди існує ймовірність, що частину інформації буде втрачено або пошкоджено.

Одним із рішень цієї проблеми було б просто надіслати додаткові копії даних. Наприклад, Zeke може надіслати повідомлення [14, 14, 14, 15, 15, 15] замість [14, 15]. Поки Арт знає, що кожна частина повідомлення надіслана в трьох примірниках, він може розшифрувати повідомлення та перевірити наявність помилок. Фактично, якщо він знайде якісь помилки, у нього є хороші шанси їх виправити. Якщо Арт отримує [14, 14, 24, 15, 15, 15], той факт, що перші три числа різні, попереджає його про помилку, а оскільки два з них дорівнюють 14, він може припустити, що 24, ймовірно, має бути 14 також. Замість того, щоб просити повторно надіслати повідомлення, Арт може продовжити розшифровку. Це ефективна, але дорога стратегія. Незалежно від часу, енергії та зусиль, необхідних для відправки n інформації, для цього потрібно втричі більше.

Але математика, що лежить в основі кодів Ріда-Соломона, пропонує ефективну альтернативу. Замість того, щоб надсилати кілька копій кожного фрагмента даних, ви можете просто надіслати один додатковий бал! Якщо ця додаткова точка відповідає вашому поліному, то інформація правильна. Якщо ні, виникла помилка.

Щоб побачити, як це працює, припустімо, що ви хочете перевірити повідомлення «НІ» в першому прикладі. Зік може просто надіслати додаткове y-координата 155. Припустимо, що він і Арт домовилися про третє приватне x-попередньо узгоджувати, мовляв x = 10, Арт може перевірити цю третю точку на розшифрованому рядку. Коли він пробки x = 10 в y = 14x + 15 і бачить, що результат 155, він знає, що помилок у передачі не було.

Це працює не лише для ліній. Щоб дозволити Зіку перевірити «ПОГАНО» у другому прикладі, Арт може надіслати y = 25. Якщо вони погодилися, що 3 є додатковим приватним x-координація, Зік може підключити x = 3 у його квадратичну функцію y = 2x² + x + 4 і переконайтеся, що точка (3, 25) підходить, ще раз підтверджуючи безпомилкову передачу ще однією точкою.

І ця додаткова точка потенційно також може виправити помилки. Якщо виявлено помилку й одержувач не може побудувати поліноміальну функцію, яка містить повідомлення, замість цього він може побудувати «найкращий» поліном за допомогою методів регресії. Подібно до лінії найкращого підходу в статистичному класі, це поліноміальна функція, яка математично визначена так, щоб найбільше відповідати заданим точкам, навіть якщо вона не проходить через усі з них. Залежно від структури повідомлення та кількості додаткової інформації, яку ви надсилаєте, цей найкращий поліном може допомогти вам відновити правильний поліном — і, отже, правильне повідомлення — навіть із пошкодженої інформації.

Така ефективність передачі та корекції зв’язку пояснює, чому НАСА використовувало коди Ріда-Соломона під час своїх місій на Місяць і Марс. І це дає вам над чим поміркувати, коли ви вирішуєте наступну систему рівнянь. Коли ви здогадуєтеся, перевіряєте або усуваєте свій шлях до рішення, подумайте про потужність і елегантність кодів Ріда-Соломона та про всі секрети, які може відкрити ваша система.

Вправи

1. Використовуючи ту саму схему, яку вони використовували в класі, Арт публікує публічні номери 33 і 57, щоб Зік їх розшифрував. Яке повідомлення?

2. Як Арт і Зік можуть бути впевнені, що система рівнянь, яка є результатом їхніх приватних чисел x = 3 і x = 6 завжди матиме розв’язок?

3. У відповідь на повідомлення Арта «BAD» про іспит з англійської Зік надсилає назад [90, 387, 534]. Якщо припустити, що вони використовують ту саму схему, яку використовували в класі, яке його послання?

4. Лола надсилає вам повідомлення з двох букв плюс один номер перевірки помилок, використовуючи код Ріда-Соломона та той самий простий алфавітний шифр, який використовували Арт і Зік. Ви таємно домовилися про x-координати 1, 3 і 10 заздалегідь, а Лола передає публічні номери [27, 43, 90]. Чи містить повідомлення помилку?