Числовой метод контроля

Сущность числового метода заключается в том, что код задан­ного числа определяется как остаток деления числа на выбран­ный модуль р:

R_A = A mod P = А — [А/P] · р,

где А — контролируемое число, в скобках — целая часть от деления числа A на P..

Качество контроля во многом зависит от величины модуля р. Если р = q, где q - основание системы счисления, в которой выражено число, то контроль осуществляется только над млад­шим разрядом числа. Если р = q^т, то контролируются все разряды числа, но не фиксируются ошибки в т старших разрядах.

Применение метода числового контроля требует получения остатка с помощью операции деления, следовательно, сопровож­дается большими затратами машинного времени.

Остаток от деления числа на модуль р сравним с самим чис­лом по модулю р, т.е. если

r_A = A mod p, то А = r_A mod p).

~ для суммы А + В = (r_A +r_B)( mod p),

~ для разности r_а+в = (г_а — r_B )(mod p),

~ для произведения r_а-в = (г_а · r_b)(mod p).

Если для разности получается отрицательный результат, то к нему надо прибавлять модуль до первого положительного числа.

Задание 11-2. Определить контрольные коды данных чисел их суммы, разности, произведения по модулю р.

1. А = 312 и В = 98, р = 15

Решение. Контрольные коды данных чисел равны г_а = A mod p.

Тогда R_A= 312 mod 15= 12, R_B = 98 mod 15 = 8.

Учитывая, что А + В= 312 + 98 = 410, получим г_а+в = 410 mod 15 = 5.

Значит (r_A + r_s)mod 15 =5

Учитывая, что А - В= 312 — 98 = 214, получим г_а-в = 214 mod 15 = 4.

Значит (r_A - r_s)mod 15 =4

Комментарии. Коды суммы и разности можно находить, применив свойства сравнений: (r_A + r_s)mod 15 =(12+8) mod 15 =20 mod 15=5

(r_A — r_s)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, коды их суммы и разности цифровым методом.

Найдем суммы цифр чисел А и В:

X_a =3 + l + 2 = 6; X_b =9 + 8 = 17.

Найдем контрольные коды этих чисел: R_А = 6 mod 15 = 6, R_B = 17 mod 15 = 2.

Найдем суммы цифр для суммы и разности чисел А и В:

С = А + В = 410, X_c =4 + 1 = 0 = 5;

D = A- B=214, X_D=2+1 + 4 = 7.

Контрольные коды суммы и разности чисел С и D:

R_С =5mod 15 = 5; R_D = 7mod 15 = 7.

Сравнив коды суммы и разности чисел, полученные числовым и цифровым методом, установим, что они разные. Ведь, результат контроля должен быть определен одно­значно.

Оказывается, цифровой метод контроля не всегда дает точный результат. Это связано с тем, что:

1. При выпол­нении арифметических действий над числами нарушаются свойства сравнений из-за переносов единиц из одного разряда на другой. В результате каждого переноса q единиц при сложении из младшего разряда в очередной старший разряд, число единиц старшего разряда первого компонента увеличивается на 1, а сумма цифр получаемого результата уменьшается на 1. При вычитании едет заем единицы старшего разряда и прибавление q единиц к младшему разряду, поэтому сумма цифр результата увеличивается. В десятичной системе q=10; 100; 100 и т.д.

2. Сумма цифр зависит от системы счисления.

С учетом этих замечаний формулы кодов суммы и разности чисел, полученные цифровым методом, имеют уточненный(скорректированный) вид

Пусть даны числа A и B, записанные в десятичной системе счисления

Обозначим через X_A и X_B сумму цифр каждого числа соответственно, а их цифровые коды через R_А и R_B. Тогда:

R_A+B = (R_А + R_B – L(q-1)(mod p), где L-число переходов в более старший разряд при сложении чисел A и B.

R_A-B = (R_А — R_B +S(q-1)(mod p), еде S-число заёмов в более старшем разряде при вычитании чисел A и B.

Числа L и S можно вычислить, используя сумму цифр X_A и X_B данных чисел:

и — где число 10 есть основание десятичной системы счисления, а скобки обозначают целую часть числа.

Задание 11-4. Найти контрольные коды чисел А = 312 и В = 98, коды их суммы и разности скорректированным цифровым методом, если модуль p=15.

Решение. Согласно заданию 9-4 имеем R_А = 6, R_B = 2. X_a =6; X_b = 17.

=[(6+17):10]=[2,3]=2; = [(6-17):10]=[-1,1]=2

R_A+B = (R_А + R_B – L(q-1)(mod p)=(6+2-2(10-1))(mod15)= -10 mod15= 5

R_A-B = (R_А — R_B +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 = 2^s. Так, восьмеричная и шестнадцатеричная системы счисления легко переводятся в двоичную. Для того чтобы осуществить переход из двоичной си­стемы счисления в q = 2^s, необходимо разбить двоичное слово справа на кортежи длины S, а затем суммировать результат по модулю р = 2^s - 1.

Таким образом, при S = 2 вся информация разбивается на пары — диады, при S= 3 — на триады, при S= 4 — на тетрады и т.д.

Процесс разбиения кодовой информации на кортежи длины S и получения контрольного кода называется свертыванием.

Такие свертки или свернутые коды получаются в процессе сум­мирования образовавшихся кортежей длины 5 по модулю р.

Цифровая подпись.

Для организации многосторонней секрет­ной связи используется шифр с открытым ключом.

Кодирование сообщения А заключается в преобразовании F: A®A^d(mod p),где пара (d, р) называется ключом.

Получатель декодирует его таким же преобразованием с помощью ключа (k, р). Очевидно, что получатель принципиально сможет получить исходное А толь­ко если А < р, поэтому если надо закодировать много информа­ции (большое слово), его надо разбить на кортежи длиной, мень­шей р.

Очевидно, операции кодирования и декодирования информа­ции, по сути, тождественны и отличаются друг от друга лишь показателями степени, поэтому для них выполняется переместительный закон:

А ®(A^k) ^d(mod p) = A^kd(mod p) = A^dk(mod p) = (A^d)^k(mod p),

поэтому A®.(A^d)^k(mod p)

В практике кодирования используются различные приемы, объ­единенные названием цифровая или электронная подпись.

Отправитель кодирует сообщение А закрытым ключом С= A^d(mod p) и посылает получателю информацию, т.е. пару (d, р) в виде подписанного сообщения. Получатель, получив это сооб­щение, декодирует подпись сообщения открытым ключом (k р), т.е. находит А’ = C‘(mod p).

Если А = А^‘, то письмо дошло правильно и без помех или оно было отправлено в нешифрованном виде.

Если А¹А’, то сообще­ние при передаче было искажено, т.е. произошла потеря инфор­мации.

В теории вычетов доказывается, что при отсутствии помех и выполнения условия взаимной простоты чисел d,k, р, результат А = А’ достигается всегда.

Задание 11-6. Зашифруйте сообщение А = (4, 3, 2) ключом (5, 7), а затем дешифруйте его ключом (11,7).

1. Зашифруем. сообщение ключом (5, 7):

4 ® 4⁵(mod 7) = 1024(mod7) = 2,

3 ® 3⁵(mod 7) = 243(mod7) = 5,

2 ®2⁵(rnod7) = 32(mod7) = 4.

Итого, С= F(A) = (2,5,4) – получись зашифрованное сообщение вместо А = (4, 3, 2).

2. Дешифруем сообщение ключом (11,7).

2 ®2^l1(rnod7) = 2048(mod7) =4,

5 ®5¹¹mod7) = 48828 125(mod7) = 3,

4 ® 4¹¹(mod7) = 4194304(mod7) = 2.

Получили A’ = F^—1(C) = {4, 3, 2} = A.

Замечание. Сообщение шифровалось ключом (5, 7), а дешифровалось ключом (11,7). Числа 5,11,7 – взаимно простые числа, алгоритм выбора таких чисел не рассматривается в данном курсе математики.

Сообщение дошло до получателя без искажений. Однако кроме математических проблем могут возникнуть нрав­ственные, например перехват сообщения и замена ключа, а также подмена сообщений неким злоумышленником. Цифровая подпись лишь констатирует факт, что сообщение пришло от того же от­правителя, что и открытый ключ.

В современных информационных систе­мах стало популярным шифрование с открытым ключом, которое осуществляется на основе математических знаний, например, та­ких разделов, как разложения чисел на простые множители, вы­числение логарифмов чисел, решение алгебраических уравнений.

На основании теоремы Рабина доказано, что разложение на простые множители двух больших чисел эквивалентно раскры­тию ключа для шифра и практически невозможно в реаль­ном времени с учетом возможностей современных ЭВМ.

Шифры с открытым ключом достаточно просты в обращении, практичны и обладают высокой криптостойкостью.

И хотя срав­нительно просто найти пару больших взаимно простых чисел, к настоящему времени не разработаны эффективные алгоритмы разложения чисел на простые множители. Так, разложение на множители числа в 200 и более цифр займет сотни лет работы компьютера. А так как при употреблении шифра с открытым клю­чом используются очень большие простые числа, содержащие сотни цифр в десятичной системе счисления, то вскрыть такие шифры весьма сложно.

Поэтому поиск простых чисел и их общей формулы в настоя­щее время представляет не только теоретический, но и практи­ческий интерес.

Получив сообщение, получатель сначала расшифровывает его закрытым ключом, а затем проверяет его подлинность. Для этого он сравнивает дешифрованный текст с тем, который был полу­чен с помощью открытого ключа.

Алгоритмы кодирования и декодирования на самом деле весь­ма сложны. Основные идеи специальных кодов изложены в соот­ветствующей литературе и защищены от злоумышленников на раз­личных уровнях, включая юридическую защиту.

Задание 11-7. Придумать один из шифров замены и перестановки.