Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Решение простейших задач шифрования

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

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

Ra = A mod Р = А-[А/Р ? р,

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

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

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

rA = A modр, то (А = rA )modр:

~ для суммы rA + B = (rA + rB)modp-,

~ для разности rA_B = (rA - rB)modp',

~ для произведения гА.в = (гАrB)modp.

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

Задача 5.8

Определить контрольные коды данных чисел, их суммы, разности, произведения по модулю р, если Д = 312«? = 98,/? = 15.

Решение.

Контрольные коды данных чисел равны гЛ = Атодр.

Тогда Ra = 312mod 15 = 12, RB = 98mod 15 = 8.

Учитывая, что Л + ? = 312 + 98 = 410, получим rA+B = 410mod 15 = 5.

Значит, (rA + rs)mod 15 = 5.

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

Значит, (rA - r^mod 15 = 4.

Комментарии. Коды суммы и разности можно находить, применив свойства сравнений:

  • (rA + r5)mod 15 = (12 + 8)mod 15 = 20mod 15 = 5;
  • а - rs)mod 15 = (12 - 8) mod 15 = 4mod 15 = 4.

Сущность цифрового метода заключается в том, что код заданного числа определяется как остаток деления суммы цифр заданного числа на выбранный модуль р. Пусть натуральное число Л задано в некоторой системе счисления Л = (0, а{, а2 ..., ап). Для получения контрольного кода при цифровом методе контроля необходимо разделить сумму цифр числа на модульр.

Задача 5.9

Найти контрольные коды чисел Л = 312 и В = 98, коды их суммы и разности цифровым методом.

Решение.

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

ХА = 3 + + 2 = 6; Хв = 9 + 8 = 17.

Найдем контрольные коды этих чисел:

Ra = 6mod 15 = 6; RB= 17mod 15 = 2.

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

С = Л + В = 410, Хс = 4+ 1 = 0 = 5;

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

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

Rc = 5 mod 15 = 5; R0 = 7 mod 15 = 7.

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

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

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

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

Обозначим через ХА и Хв сумму цифр каждого числа соответственно, а их цифровые коды — через ЯА и Яв. Тогда

КА+в = (Яд + Яв-Щ- 1 )(тос1/0,

где Ь — число переходов в более старший разряд при сложении чисел Ли В.

КА-В = (КА - яв + - 1)(тос1р),

где ? — число заемов в более старшем разряде при вычитании чисел Ли В.

Числа Ь и -51 можно вычислить, используя сумму цифр ХА и Хв данных чисел:

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

Задача 5.10

Найти контрольные коды чисел Л = 32 и В = 98, коды их суммы и разности скорректированным цифровым методом, если модуль р - 15. Решение.

Согласно заданию 9—4 имеем ЯА = 6, Яв = 2, ХА = 6,ХВ = 17.

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

RA+B = (RA + RB-Uq- l)(mod/>) = (6 + 2-2(10- 1 »(mod 15) =

= -10 mod 15 = 5,

Ra-b = (ra~ RB + S(q~ l)(mod/>) = (6-2 + 2(10- l))(modl5) =

= 22mod 15 = 7.

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

Задача 5.11

Найти контрольные коды чисел А = 51 и В - 14, коды их суммы и разности скорректированным цифровым методом, если модуль р = 5.

Решение.

,4mod5 = 2, ?mod5 = 4, + В)mod 5 = 1, (A - Z?)mod3, • Z?)mod3.

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

Для выбора системы счисления необходимо учесть требования, накладываемые на величину модуля р:

• величина модуля р должна быть небольшой, так как рост числа

контролирующих операций усложняет процесс;

• при появлении любой арифметической или логической ошибки

изменять сравнимость контрольных кодов;

• получение контрольного кода осуществлять предельно упрощенными средствами.

Компромиссным вариантом для выбора системы счисления служат системы с основанием q = 2s. Так, восьмеричная и шестнадцатеричная системы счисления легко переводятся в двоичную. Для того чтобы осуществить переход из двоичной системы счисления в q = 2s, необходимо разбить двоичное слово справа на кортежи длиной S, а затем суммировать результат по модулю р = 2s - 1.

Таким образом, при S= 2 вся информация разбивается на пары — диады, при S= 3 — на триады, при S= 4 — на тетрады и т.д. Процесс разбиения кодовой информации на кортежи длиной S и получения контрольного кода называется свертыванием. Такие свертки или свернутые коды получаются в процессе суммирования образовавшихся кортежей длиной S по модулю р.

Вопросы и задания для самопроверки
  • 1. Каковы свойства операции сравнения?
  • 2. Что называется вычетом по модулю т?
  • 3. Является ли число классов вычетов по модулю т конечным?
  • 4. Какими свойствами обладают обратимые вычеты?
  • 5. В каких случаях целое число имеет мультипликативную инверсию?
  • 6. Из каких основных частей состоит любая криптографическая система?
  • 7. Каковы основные недостатки шифра Цезаря?
  • 8. Чему равно число ключей обычного перестановочного шифра, если исходный текст составляет 100 символов?
  • 9. К какому виду шифров относится шифр Вижинера?
  • 10. Каковы преимущества шифра поворотной решетки по сравнению с другими перестановочными шифрами?
 
<<   СОДЕРЖАНИЕ   >>