Сравнения и вычеты

- соотношение между целыми числами а и и вида a=b+mk, означающее, что их разность а-b делится на заданное целое положительное число т, наз. модулем сравнения; при этом аназ. вычетом целого числа bпо модулю т. Для выражения сравнимости чисел аи bпо модулю тупотребляется символ

Если разность а-b не делится на т, то a и bназ. несравнимыми по модулю ти для выражения несравнимости аи bупотребляется символ

Наличие С. эквивалентно тому, что аи b имеют одинаковые остатки при делении на т.
Отношение сравнимости по фиксированному модулю m является отношением эквивалентности: оно рефлексивно, т. к. симметрично, т. к. из следует и транзитивно, т. к. из и следует, что Тем самым отношение разбивает множество всех целых чисел на непересекающиеся классы эквивалентности А, В, С,... Два целых числа лежат в одном и том же классе тогда и только тогда, когда они сравнимы по модулю т. Эти классы наз. классами вычетов по модулю т. Каждое целое число сравнимо по модулю тлишь с одним из чисел 0, 1,..., т -1; числа 0, 1,..., т- 1 лежат в различных классах, поэтому имеется в точности. классов вычетов, а числа 0, 1,..., т-1 образуют множество представителей этих классов. Любое множество из тцелых чисел, взятых по одному из каждого класса вычетов, наз. полной системой вычетов по модулю т.
С. с одним и тем же модулем можно складывать, вычитать и перемножать подобно обычным равенствам, т. е. из

и
следует, что

и

Обе части С. можно умножить на одно и то же целое число, обе части С. можно разделить на их общий делитель, если последний взаимно прост с модулем С. Если же общий делитель числа, на к-рое делятся обе части С., и модуля С. тесть d, то после деления на dполучается С. по модулю m/ d.
Операции сложения, вычитания и умножения С. индуцируют подобные же операции над классами вычетов. Так, если. и bпроизвольные элементы из классов вычетов Аи В соответственно, то а+b всегда лежит в одном и том же классе вычетов, наз. суммой А+В классов Аи В. Аналогично определяется разность А-В и произведение Ах В двух классов вычетов Аи В. Классы вычетов по модулю тобразуют по сложению абелеву группу порядка т. Нулевым элементом этой группы является класс, состоящий из всех целых чисел, кратных числу т;обратным к классу Аявляется класс А, состоящий из всех элементов класса А, взятых со знаком минус. Более того, классы вычетов по модулю тобразуют кольцо относительно определенных выше операций сложения, вычитания и умножения.
Пусть F(x₁, x ₂,..., х _п) - многочлен от ппеременных с целыми коэффициентами. Выражение вида

наз. алгебраическим сравнением. Решением сравнения (*) наз. всякий набор а ₁, а ₂,..., а _n целых значений неизвестных x₁, x ₂,..., х _п такой, что число F(a₁, а ₂,..., а _п)сравнимо с нулем по модулю т. Если а _i, лежат соответственно в классах вычетов X_i по модулю т, то любой другой набор где также будет решением С. Поэтому принято наз. решением С. (*) также сам набор классов вычетов, представителями к-рых являются a₁, a₂,..., а _п. т. е. решение алгебраического уравнения F(x₁, x ₂,..., х _п) = 0вкольце классов вычетов по модулю т. При таком соглашении С. (*) будет иметь столько решений, сколько наборов классов вычетов полной системы по модулю тудовлетворяют уравнению. (x₁, x ₂,..., х _п)=0. Аналогично определяется число решений С. более общего вида, а также систем С. С. 1-й степени

если авзаимно просто с т(что обозначается (а, т)=1), имеет единственное решение. Классы вычетов по модулю т, элементы к-рых взаимно просты с т, образуют абелеву группу по умножению.

8. Режимы работы алгоритма DES.

электронный шифроблокнот (Electronic Codebook) - ECB;

цепочка цифровых блоков (Cipher Block Chaining) - CBC;

цифровая обратная связь (Cipher Feedback) - CFB;

внешняя обратная связь (Output Feedback) - OFB.

DES-ECB

В этом режиме исходный файл M разбивается на 64-битовые блоки (по 8 байтов): M = M(1)M(2)...M(n). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования (рис.5). Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.

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

В то же время следует признать, что этот режим в силу своей простой реализации наиболее популярен среди любительских разработок.

DES-CBC

В этом режиме исходный файл M также, как и в режиме ECB, разбивается на 64-битовые блоки: M = M(1)M(2)...M(n). Первый блок M(1) складывается по модулю 2 с 64-битовым начальным вектором IV, который меняется ежедневно и держится в секрете. Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый блок шифртекста C(1) складывается по модулю 2 со вторым блоком исходного текста, результат шифруется и получается второй 64-битовый блок шифртекста C(2) и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки исходного текста

DES-CFB

В этом режиме размер блока может отличаться от 64. Исходный файл M считывается последовательными t-битовыми блоками (t <= 64): M = M(1)M(2)...M(n) (остаток дописывается нулями или пробелами).

64-битовый сдвиговый регистр (входной блок) вначале содержит вектор инициализации IV, выравненный по правому краю. Для каждого сеанса шифрования используется новый IV.

Для всех i = 1...n блок шифртекста C(i) определяется следующим образом:

C(i) = M(i) xor P(i-1),

где P(i-1) - старшие t битов операции DES(С(i-1)), причем C(0)=IV.

Обновление сдвигового регистра осуществляется путем удаления его старших t битов и дописывания справа C(i).

Восстановление зашифрованных данных также не представляет труда: P(i-1) и C(i) вычисляются аналогичным образом и

M(i) = C(i) xor P(i-1).

Блок-схема режима CFB приведена на рис.7.

Рис.7. Работа алгоритма DES в режиме CFB

DES-OFB

Режим OFB очень похож на режим CFB.

Отличие от режима CFB состоит только в методе обновления сдвигового регистра. В данном случае это осуществляется путем удаления его старших t битов и дописывания справа P(i-1) (рис.8).

Рис.8. Блок-схема алгоритма DES в режиме OFB

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

Режим ECB хорошо подходит для шифрования ключей. Режимы CBC и CFB пригодны для аутентификации данных. Режим CFB, кроме того, предназначен для шифрования отдельных символов. Режим OFB нередко используется в спутниковых системах связи.