Спирина, М.С. Дискретная математика

Процесс разбиения кодовой информации на кортежи длины S и получения контрольного кода называется свертыванием. Такие свертки или свернутые коды получаются в процессе сум­ мирования образовавшихся кортежей длины 5 по модулю р. Частные случаи образования сверток: 1. Контроль по модулю 3, т.е. р = 3 (при S = 2). 2. Контроль по модулю 7, т.е. р = 7 (при S = 3). Цифровая подпись. Для организации многосторонней секрет­ ной связи используется шифр с открытым ключом. Кодирование сообщения А заключается в преобразовании F: А - » //(m od /?), где пара ( d , р) называется ключом. Получатель сигнала декодирует его таким же преобразованием с помощью ключа (/, р). Очевидно, что получатель принципиально сможет получить исходное А толь­ ко если А < р, поэтому если надо закодировать много информа­ ции (большое слово), его надо разбить на кортежи длиной, мень­ шей р. Очевидно, операции кодирования и декодирования информа­ ции, по сути, тождественны и отличаются друг от друга лишь показателями степени, поэтому для них выполняется перемести­ тельный закон: А -> (/( '/(mod/?) = //'(mod /?) = //'(mod /?) = ( //) '(m od /?) <- А. В практике кодирования используются различные приемы, объ­ единенные названием цифровая или электронная подпись. Отправитель кодирует сообщение А закрытым ключом С = = //(mod/?) и посылает получателю информацию, т.е. пару ( d , /?) в виде подписанного сообщения. Получатель, получив это сооб­ щение, декодирует подпись сообщения открытым ключом (/, /?), т.е. находит А' = C'(mod/?). Если А =А', то письмо дошло правильно и без помех или оно было отправлено в нешифрованном виде. Если А ф А \ т о сообще­ ние при передаче было искажено, т.е. произошла потеря инфор­ мации. В теории вычетов доказывается, что при отсутствии помех и выполнения некоторых условий (взаимной простоты чисел d, I, р) результат А - А' достигается всегда. Рассмотрим пример. Зашифруем сообщение А = (4, 3, 2) ключом (5, 7) и пошлем его получателю: 4 -» 4 5 (mod7) = 1024(mod7) = 2, 3 -> 3 5 (mod7) = 243(mod7) = 5, 2 -> 2 5 (mod7) = 32(mod7) = 4. Итого C = F(A) = (2,5,4). Получатель без труда раскодирует его ключом (11, 7): 2 -» 2“ (mod7) = 2048(mod7) - 4, 5 -> 5u (mod7) = 48828 125(mod7) = 3, 4 -> 4 u (mod7) = 4 194304(mod7) = 2. Получили A ’ = F~l(C) = = (4, 3, 2> = A. Сообщение дошло до получателя без искажений. Однако кроме математических проблем могут возникнуть нрав­ ственные, например перехват сообщения и замена ключа, а также 333