Числовой метод контроля
Сущность числового метода заключается в том, что код заданного числа определяется как остаток деления числа на выбранный модуль р:
RA = A mod P = А — [А/P] · р,
где А — контролируемое число, в скобках — целая часть от деления числа A на P..
Качество контроля во многом зависит от величины модуля р. Если р = q, где q - основание системы счисления, в которой выражено число, то контроль осуществляется только над младшим разрядом числа. Если р = qт, то контролируются все разряды числа, но не фиксируются ошибки в т старших разрядах.
Применение метода числового контроля требует получения остатка с помощью операции деления, следовательно, сопровождается большими затратами машинного времени.
Остаток от деления числа на модуль р сравним с самим числом по модулю р, т.е. если
rA = A mod p, то А = rA mod p).
~ для суммы А + В = (rA +rB)( mod p),
~ для разности rа+в = (га — rB )(mod p),
~ для произведения rа-в = (га · rb)(mod p).
Если для разности получается отрицательный результат, то к нему надо прибавлять модуль до первого положительного числа.
Задание 11-2. Определить контрольные коды данных чисел их суммы, разности, произведения по модулю р.
1. А = 312 и В = 98, р = 15
Решение. Контрольные коды данных чисел равны га = A mod p.
Тогда RA= 312 mod 15= 12, RB = 98 mod 15 = 8.
Учитывая, что А + В= 312 + 98 = 410, получим га+в = 410 mod 15 = 5.
Значит (rA + rs)mod 15 =5
Учитывая, что А - В= 312 — 98 = 214, получим га-в = 214 mod 15 = 4.
Значит (rA - rs)mod 15 =4
Комментарии. Коды суммы и разности можно находить, применив свойства сравнений: (rA + rs)mod 15 =(12+8) mod 15 =20 mod 15=5
(rA — rs)mod 15 =(12-8) mod 15 =4 mod 15=4
2. А = 57 и В = 14, р = 5
Ответ Amod5=2, Bmod5=4, (A+B)mod5=1, (A-B)mod 3, (A·B)mod3
2.2. Цифровой метод контроля.
Сущность цифрового метода заключается в том, что код заданного числа определяется как остаток деления суммы цифр заданного на выбранный модуль р:
Пусть натуральное число А задано в некоторой системе счисления А = (о,, аъ …, а„). Для получения контрольного кода при цифровом методе контроля необходимо разделить сумму цифр числа на модуль р
Задание 11-3. Найти контрольные коды чисел А = 312 и В = 98, коды их суммы и разности цифровым методом.
Найдем суммы цифр чисел А и В:
Xa =3 + l + 2 = 6; Xb =9 + 8 = 17.
Найдем контрольные коды этих чисел: RА = 6 mod 15 = 6, RB = 17 mod 15 = 2.
Найдем суммы цифр для суммы и разности чисел А и В:
С = А + В = 410, Xc =4 + 1 = 0 = 5;
D = A- B=214, XD=2+1 + 4 = 7.
Контрольные коды суммы и разности чисел С и D:
RС =5mod 15 = 5; RD = 7mod 15 = 7.
Сравнив коды суммы и разности чисел, полученные числовым и цифровым методом, установим, что они разные. Ведь, результат контроля должен быть определен однозначно.
Оказывается, цифровой метод контроля не всегда дает точный результат. Это связано с тем, что:
1. При выполнении арифметических действий над числами нарушаются свойства сравнений из-за переносов единиц из одного разряда на другой. В результате каждого переноса q единиц при сложении из младшего разряда в очередной старший разряд, число единиц старшего разряда первого компонента увеличивается на 1, а сумма цифр получаемого результата уменьшается на 1. При вычитании едет заем единицы старшего разряда и прибавление q единиц к младшему разряду, поэтому сумма цифр результата увеличивается. В десятичной системе q=10; 100; 100 и т.д.
2. Сумма цифр зависит от системы счисления.
С учетом этих замечаний формулы кодов суммы и разности чисел, полученные цифровым методом, имеют уточненный(скорректированный) вид
Пусть даны числа A и B, записанные в десятичной системе счисления
Обозначим через XA и XB сумму цифр каждого числа соответственно, а их цифровые коды через RА и RB. Тогда:
RA+B = (RА + RB – L(q-1)(mod p), где L-число переходов в более старший разряд при сложении чисел A и B.
RA-B = (RА — RB +S(q-1)(mod p), еде S-число заёмов в более старшем разряде при вычитании чисел A и B.
Числа L и S можно вычислить, используя сумму цифр XA и XB данных чисел:
и — где число 10 есть основание десятичной системы счисления, а скобки обозначают целую часть числа.
Задание 11-4. Найти контрольные коды чисел А = 312 и В = 98, коды их суммы и разности скорректированным цифровым методом, если модуль p=15.
Решение. Согласно заданию 9-4 имеем RА = 6, RB = 2. Xa =6; Xb = 17.
=[(6+17):10]=[2,3]=2; = [(6-17):10]=[-1,1]=2
RA+B = (RА + RB – L(q-1)(mod p)=(6+2-2(10-1))(mod15)= -10 mod15= 5
RA-B = (RА — RB +S(q-1)(mod p)= (6-2+2(10-1))(mod15)=22mod15=7
Полученные результаты полностью совпадают с вычисленным ранее, т.е. с помощью новых формул ошибки цифрового метода удалось избежать.
Задание 11-5. Найти контрольные коды чисел А = 57 и В = 14, коды их суммы и разности скорректированным цифровым методом, если модуль р = 5
Ответ Amod5=2, Bmod5=4, (A+B)mod5=1, (A-B)mod 3, (A·B)mod3
2.3. Выбор модуля для контроля.Числовой метод контроля имеет весомое преимущество над иными методами. Он использует свойства сравнений, имеющие достоверный, а не вероятностный характер. Однозначность полученных ответов облегчает осуществление контроля выполнения арифметических операций, сокращает затраты времени.
Для выбора системы счисления необходимо учесть требования, накладываемые на величину модуля р:
~ величина модуля р должна быть небольшой, так как рост числа контролирующих операций усложняет процесс;
~ при появлении любой арифметической или логической ошибки изменять сравнимость контрольных кодов;
~ получение контрольного кода осуществлять предельно упрощенными средствами.
Компромиссным вариантом для выбора системы счисления служат системы с основанием q = 2s. Так, восьмеричная и шестнадцатеричная системы счисления легко переводятся в двоичную. Для того чтобы осуществить переход из двоичной системы счисления в q = 2s, необходимо разбить двоичное слово справа на кортежи длины S, а затем суммировать результат по модулю р = 2s - 1.
Таким образом, при S = 2 вся информация разбивается на пары — диады, при S= 3 — на триады, при S= 4 — на тетрады и т.д.
Процесс разбиения кодовой информации на кортежи длины S и получения контрольного кода называется свертыванием.
Такие свертки или свернутые коды получаются в процессе суммирования образовавшихся кортежей длины 5 по модулю р.
Цифровая подпись.
Для организации многосторонней секретной связи используется шифр с открытым ключом.
Кодирование сообщения А заключается в преобразовании F: A®Ad(mod p),где пара (d, р) называется ключом.
Получатель декодирует его таким же преобразованием с помощью ключа (k, р). Очевидно, что получатель принципиально сможет получить исходное А только если А < р, поэтому если надо закодировать много информации (большое слово), его надо разбить на кортежи длиной, меньшей р.
Очевидно, операции кодирования и декодирования информации, по сути, тождественны и отличаются друг от друга лишь показателями степени, поэтому для них выполняется переместительный закон:
А ®(Ak) d(mod p) = Akd(mod p) = Adk(mod p) = (Ad)k(mod p),
поэтому A®.(Ad)k(mod p)
В практике кодирования используются различные приемы, объединенные названием цифровая или электронная подпись.
Отправитель кодирует сообщение А закрытым ключом С= Ad(mod p) и посылает получателю информацию, т.е. пару (d, р) в виде подписанного сообщения. Получатель, получив это сообщение, декодирует подпись сообщения открытым ключом (k р), т.е. находит А’ = C‘(mod p).
Если А = А‘, то письмо дошло правильно и без помех или оно было отправлено в нешифрованном виде.
Если А¹А’, то сообщение при передаче было искажено, т.е. произошла потеря информации.
В теории вычетов доказывается, что при отсутствии помех и выполнения условия взаимной простоты чисел d,k, р, результат А = А’ достигается всегда.
Задание 11-6. Зашифруйте сообщение А = (4, 3, 2) ключом (5, 7), а затем дешифруйте его ключом (11,7).
1. Зашифруем. сообщение ключом (5, 7):
4 ® 45(mod 7) = 1024(mod7) = 2,
3 ® 35(mod 7) = 243(mod7) = 5,
2 ®25(rnod7) = 32(mod7) = 4.
Итого, С= F(A) = (2,5,4) – получись зашифрованное сообщение вместо А = (4, 3, 2).
2. Дешифруем сообщение ключом (11,7).
2 ®2l1(rnod7) = 2048(mod7) =4,
5 ®511mod7) = 48828 125(mod7) = 3,
4 ® 411(mod7) = 4194304(mod7) = 2.
Получили A’ = F—1(C) = {4, 3, 2} = A.
Замечание. Сообщение шифровалось ключом (5, 7), а дешифровалось ключом (11,7). Числа 5,11,7 – взаимно простые числа, алгоритм выбора таких чисел не рассматривается в данном курсе математики.
Сообщение дошло до получателя без искажений. Однако кроме математических проблем могут возникнуть нравственные, например перехват сообщения и замена ключа, а также подмена сообщений неким злоумышленником. Цифровая подпись лишь констатирует факт, что сообщение пришло от того же отправителя, что и открытый ключ.
В современных информационных системах стало популярным шифрование с открытым ключом, которое осуществляется на основе математических знаний, например, таких разделов, как разложения чисел на простые множители, вычисление логарифмов чисел, решение алгебраических уравнений.
На основании теоремы Рабина доказано, что разложение на простые множители двух больших чисел эквивалентно раскрытию ключа для шифра и практически невозможно в реальном времени с учетом возможностей современных ЭВМ.
Шифры с открытым ключом достаточно просты в обращении, практичны и обладают высокой криптостойкостью.
И хотя сравнительно просто найти пару больших взаимно простых чисел, к настоящему времени не разработаны эффективные алгоритмы разложения чисел на простые множители. Так, разложение на множители числа в 200 и более цифр займет сотни лет работы компьютера. А так как при употреблении шифра с открытым ключом используются очень большие простые числа, содержащие сотни цифр в десятичной системе счисления, то вскрыть такие шифры весьма сложно.
Поэтому поиск простых чисел и их общей формулы в настоящее время представляет не только теоретический, но и практический интерес.
Получив сообщение, получатель сначала расшифровывает его закрытым ключом, а затем проверяет его подлинность. Для этого он сравнивает дешифрованный текст с тем, который был получен с помощью открытого ключа.
Алгоритмы кодирования и декодирования на самом деле весьма сложны. Основные идеи специальных кодов изложены в соответствующей литературе и защищены от злоумышленников на различных уровнях, включая юридическую защиту.
Задание 11-7. Придумать один из шифров замены и перестановки.