Приветствую Вас, уважаемые Читатели! Многие со школьных времен помнят, как использовали для общения на и вне уроков некоторые закодированные или зашифрованные сообщения. Кто-то придумывал систему условных знаков по типу "пляшущих человечков", кто-то использовал т.н. шифры замены (Ваши варианты жду в комментариях).
Однако сегодня я расскажу об удивительно простом, основанном только лишь на элементарной алгебре способе передачи сообщений. У негго есть несколько недостатков, но на нём построены и реальные системы передачи данных!
Итак, пусть Петя и Ваня сидят на уроке и заранее условились закодировать буквы русского алфавита по порядку от 1 до 33 : "А-1", "Б-2"..., "Я-33". Задача Пети передать Ване сообщение "ДА". Как ему это сделать?
Вариант с киванием головой не прокатывает)
Петя передает через одноклассников записку, которую несколько раз разворачивают любопытные девчонки, но с недоумением пожимают плечами, потому что в ней содержатся всего лишь два числа:
Но когда записка попадает в руки Ване, он понимает намного больше. Ему (как и Пете) известна секретная комбинация из двух цифр (3;2), которую он использует, чтобы составить систему линейных уравнений:
Теперь, используя предварительно закодированный алфавит, Ваня понимает, что ему отправили сообщение "ДА".
Чтобы зашифровать ответное сообщение, Ване достаточно использовать секретный ключ (3;2), чтобы зашифровать, например, сообщение "ОЙ":
Для дополнительной "криптостойкости" и это сообщение можно закодировать, например, передавая не реальные значения чисел, а их сумму и разность:
Секрет этого простого кода Рида-Соломона начинается с двух основных фактов геометрии. Во-первых, через любые две точки проходит единственная прямая. Во-вторых, для коэффициентов A и B каждая (не вертикальная) линия может быть записана в виде y = Ax + B. Вместе эти два факта гарантируют, что если вы знаете две точки на прямой, вы можете найти A и B, а если вы знаете A и B, вы знаете все точки на прямой.
Теперь подумаем над тем, как передать трехбуквенное слово. На самом деле, ясно, что для это потребуется использовать три секретных числа, да и общедоступное (никто не мешает даже выкрикивать эти цифры в слух) сообщение - так же из трех "символов".
Только теперь используем уже квадратный трехчлен! Тогда на приеме нужно решить систему уравнений:
Итак, в первом примере мы использовали тот факт, что две точки определяют единственную прямую. Во втором, что три точки определяют уникальную квадратный трехчлен. Таким образом, если вы хотите отправить сообщение длиной 10, просто закодируйте сообщение коэффициентами многочлена 9-ой степени! На практике коды Рида-Соломона немного сложнее, но основная идея та же!
Теперь озадачимся вопросом, а что, если одно из озвученных чисел будет принято неправильно? Как придать нашему коду функцию обнаружения или корректировки ошибок?
Конечно, можно пытаться отправлять несколько копий сообщений. Например, в первом случае передать (8,8,8,7,7,7) вместо (8,7). Теперь, если на приеме окажется сообщение (8,8,6,7,7,7), будет ясно, что в третьем символе произошла, скорее всего ошибка, и не потребуется запрашивать сообщение заново.
Однако, это дорогая затея, которая приводит к неэффективному использованию пропускной способности канала связи, обусловленному т.н. избыточностью кода.
Гораздо проще передать третье, проверочное число, заранее условившись о секретном проверочном символе "4".
В таком случае после вычисления переданного сообщения (15,6,20) мы делаем контрольную проверку. Если выдает "284" - значит сообщение принято без ошибок. В обратном случае - нужно запросить его снова.
Однако, можно поступить иначе. Если обнаружена ошибка и получатель не может построить полиномиальную функцию, содержащую сообщение, он может вместо этого построить “наиболее подходящий” полином, используя методы регрессии. В зависимости от структуры сообщения и объема дополнительной информации, которую вы отправляете, этот наиболее подходящий многочлен может помочь вам восстановить правильный многочлен - и, следовательно, правильное сообщение — даже из искаженной информации.
Такая эффективность передачи и корректировки сообщений объясняет, почему НАСА использовало коды Рида-Соломона в своих миссиях на Луну и на Марс. И это даст вам пищу для размышлений, когда вы в следующий раз увидите систему линейных уравнений. Подумайте о силе и элегантности кодов Рида-Соломона и всех секретах, которые может раскрыть ваша система! Спасибо за внимание!