модулю m, если при делении на m они дают одинаковые остатки, т.е. если
a
mod m
=b
mod m
. В этом случае пишут a≡b (mod m) («a сравнимо с b по модулю
m»). Так, например, 5≡11(mod 3), 25≡0(mod 5), 48≡6(mod 7).
На множестве чисел 1, 2, …, m – 1, 0 вводится сложение по модулю m:
в качестве результата берется остаток от деления обычной суммы слагаемых
на модуль m, т.е. a+
m
b=(a+b)
mod m
. Например, при сложении по модулю 2
получаем 0+
2
0=1+
2
1=0 и 0+
2
1=1+
2
0=1. Составим таблицу сложения по
модулю 3:
+
3
0 1 2
0 0 1 2
1 1 2 0
2
2 0 1
Как видим, 2+
3
2 = (2+2)
mod 3
= 4
mod 3
= 1.
При вычитании по модулю m для соответствующих чисел
осуществляют обычное вычитание и, если в результате получится
отрицательное число, к нему прибавляют m. Например, по модулю 5 имеем:
1 –
5
4 = -3
mod 5
= 2.
По модулю 32 вычислите разности 10-23, 3-31, 26-31. По модулю 26 найдите 2-17,
20-25, 15-19.
Если некоторый алфавит имеет мощность m (т.е. в нем m букв), то
сложение и вычитание по модулю m можно истолковывать как сложение и
вычитание букв с соответствующими номерами. Так, при m=32 (русский
алфавит) имеем: Й-Ц=10-
32
23=-13
mod32
=19=Т, Т+Т=19+
32
19=38
mod32
=6=Е и т.п.
При таком истолковании модульных операций сложения и вычитания,
шифрование по Виженеру – это сложение блока открытого текста с ключом
16
по модулю мощности алфавита. Например, зашифруем открытый текст шифр
Виженера на ключе з а д а ч а. Длина блоков (и ключа) равна 6. Текст
разбивается на два блока: (шифрви)(женера), каждый из которых побуквенно
складывается с ключом: (шифрви)+(задача)=(25,9,21,17,3,9)+
32
(8,1,5,1,24,1) =
= (33,10,26,18,27,10)
mod32
=(1,10,26,18,27,10) = АЙЩСЪЙ,
(женера)+(задача)=(7,6,14,6,17,1)+
32
(8,1,5,1,24,1)=(15,7,19,7,9,2)=ОЖТЖИБ.
Итоговая криптограмма: АЙЩСЪЙОЖТЖИБ.
При дешифровании из блока криптограммы побуквенно вычитается
ключ. Так, зная, что криптограмма LAGZJEUUXRTJE получена на ключе
Виженера p r o b l e m («задача»), легко восстанавливаем открытый текст.
Сначала из первого блока криптограммы побуквенно вычитаем ключ:
LAVGZJE – PROBLEM = (12,1,22,7,26,10,5) –
26
(16,18,15,2,12,5,13) = (-4,
-17,7,5,14,5,-8)
mod26
=
(22,9,7,5,14,5,18) = vigener, затем ключ побуквенно
вычитается из второго блока криптограммы:
UUXRTJE-PROBLEM=(21,21,24,18,20,10,5)-
26
(16,18,15,2,12,5,13) =
=(5,3,9,16,8,5,-8)
mod26
=(5,3,9,16,8,5,18)=ecipher. Открытый текст: Vigenere
cipher (шифр Виженера).
В дальнейшем понадобится и умножение по модулю m: оно
выполняется аналогично сложению – в качестве результата берется остаток
от деления на m обычного произведения сомножителей. Например, для
умножения по модулю 4 получаем следующую таблицу:
×
4
0 1 2 3
0
0 0 0 0
1
0 1 2 3
2
0 2 0 2
3
0 3 2 1
Отметим необычное равенство 2×
4
2=0, оба сомножителя отличны от
нуля, а их произведение равно нулю.
Составьте таблицы сложения и умножения по модулям 5 и 6. По модулю 6 для
каждого из чисел 1, 2, 3, 4, 5, 0 укажите противоположное. Например, -2
mod 6
=4.
17
Тема 6. ПОТОЧНЫЕ ШИФРЫ.
В шифре Виженера длина ключа может оказаться равной длине
открытого текста. Шифры, обладающие этим свойством, называют
Достарыңызбен бөлісу: |