Общи понятия и дефиниции - IT1406 Информационна сигурност

Нека m е някакво естествено число. Не всички естествени числа се делят на m. Възможните остатъци от делението са 1, 2, . m - 1, 0 (последното при разделяне на цяло число). По модул m всяко естествено число се приема като остатък от деленето на това число на m: $$25\,mod\,3 = 1, \\ 9\,mod\,7=2, \\ 100\,mod\,26=22, \\ 100\,mod\,32=4$$ и т.н.

Две числа a и b се наричат ​​сравними по модул m, ако дават еднакъв остатък, когато са разделени на m, т.е. ако %%a\,mod\,m=b\,mod \,m%%.

В този случай напишете %%a≡b (mod\,m)%% ("a е сравнимо с %%b%% по модул %%m%%"). Така, например, $$5\equiv11(mod\,3),\\ 25\equiv0(mod\,5), \\ 48\equiv6(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+_21=1+_20=1%%. Нека направим таблица за добавяне по модул 3:

%%+_3%%	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Както можете да видите, %%2+_32 = (2+2)mod\,3 = 4\,mod\,3 = 1%%.

При изваждане по модул m за съответните числа се извършва обичайното изваждане и ако резултатът е отрицателно число, към него се добавя m. Например по модул 5 имаме: %%1 –_5\,4 = -3\,mod\,5 = 2%%.

Ако дадена азбука има кардиналност m (т.е. има m букви), тогава събирането и изваждането по модул m може да се тълкува като събиране и изваждане на букви със съответните числа. И така, за m=32 (българска азбука) имаме: $$Ы - Ц = 10 -_ 23 = -13\,mod\,32= 19 = T,$$ $$T + T = 19 +_ 19= 38\,mod\,32=6=E $$ и т.н.

С тази интерпретация на модулните операции събиране и изваждане, криптирането на Vigenère е добавяне на блок от обикновен текст с ключ по модула на кардиналността на азбуката. Например, нека шифроваме обикновения текст с шифъра на Vigenère, използвайки проблемния ключ. Дължината на блоковете (и ключа) е 6. Текстът е разделен на два блока:

всяка от които се добавя буква по буква към ключа:

$$(cipherwi) + (проблем) = (25,9,21,17,3,9) +_ (8,1,5,1,24,1) =\\ (33,10,26,18,27,10)mod\,32 = (1,10,26,18,27,10) = AISCH,$$

$$(генеричен) + (проблем) = (7,6,14,6,17,1) +_ (8,1,5,1,24,1) =\\ (15,7,19,7,9,2)=OJTJOB$$

Крайна криптограма: AISCHSJOZHTZHIB.

По време на дешифрирането ключът се изважда буква по буква от блока на криптограмата. И така, знаейки, че криптограмата LAGZJEUUXRTJE е получена на p r o b l e m („задача“) на ключа на Vigenère, можем лесно да възстановим обикновения текст. Първо изваждаме ключа буква по буква от първия блок на криптограмата:

$$LAVGZJE – ПРОБЛЕМ = (12,1,22,7,26,10,5) –_ (16,18,15,2,12,5,13) = \\ (-4, -17,7,5,14,5,-8)mod\, 26 = (22,9,7,5,14,5,18) = vigener$$

тогава ключът се изважда буква по буква от втория блок на криптограмата:

$$UUXRTJE - ПРОБЛЕМ = (21,21,24,18,20,10,5) -_(16,18,15,2,12,5,13) =\\ (5,3,9,16,8,5,-8)mod \,26=(5,3,9,16,8,5,18)= шифър.$$

Ясен текст: шифър на Вигенере.

В бъдеще ще се нуждаем и от умножение по модул 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%%, и двата фактора са различни от нула и произведението им е равно на нула.

---