Тема 11. Криптографические шифры

Теоретические сведения

Понятие вычета.

Вычетом числа a по модулю m называется остаток от деления a на m

Из определения видно, что вычеты связаны с делением с остатком.

Разделить натуральное число a на нату­ральное число b с остатком означает yнайти неотрицательные числа два числа q и г, причем г < b такие, что выполняется равенство

а = q·b + г

Так для чисел 187 и 12 соответствуют два числа 15 и 7, такие, что 187= 15·12+7. Это равенство часто записывается в виде 187:12 = 15(ост. 7).

Напишем названия компонентов деления с остатком:

а – делимое, b- делитель, q- частное, r – остаток.

Рассмотрим еще примеры:

а = - 12, b = 8 ® -12 = (- 2) · 8 + 4, q= -2, r=4

а = - 324, b = - 15 ® — 324 = 22 · (- 15) + 6 q=22, r=6

a = 4, b=10 ® 4=0·10+4 q=0, r=4

a = 12, b = 4 ® 12=4·3+0 q=4, r=0

Число a делится нацело на b, если остаток r = 0 или, а = qb. .Причем отношение «делиться на цело» обозначается .

Теорема. Если а и b делятся на с, то при любых целых k и j сумма ka + jb делится на с.

Задание 9-1.Найти такое число d ¹ 1, на которое делятся чис­ла 6п + 5 и 9л + 2. При каком значении п. это деление возможно?

Решение. Если числа 6п + 5 и 9п + 2 делятся на d, то на d делится и разность

3(6n + 5) - 2(9п + 2) = 15 - 4 = 11

Число 11 — простое число, значит d= 11.

Не трудно установить, что п = …- 21, — 10, 1, 12, 23…

Сравнение по модулю.

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

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

R = A mod B, где A-делимое, B- делитель, R-остаток.

Получаемое в процессе деления частное в данном случае не рассматривается.

Например, 5=15 mod 10, 3= 45 mod 7 и т.д.

При делении n («nÎZ) на g все целые числа разбиваются на g подмножеств, которые соответствуют числу, полученному в остатке. Остатки при этом будут равны:

n mod g ={0,1,2,…g-1}

Причем, каждому остатку можно поставить в соответствие множество чисел вида:

0 ® n mod g =0 n=k g

1 ® n mod g =1 n=kg+1

2 ® n mod g =2 n=kg+2

3 ® n mod g =3 n=kg+3

g-1 ® n mod g =g-1 n=k(g-1)

Очевидно, что любое целое число а принадлежит одному из этих g подмножеств. Причем разность любых двух чисел одного под­множества делится на g, а разность чисел из разных множеств не должна делиться на g.

Два целых числа называются сравнимыми по модулю g (g ³ 2), если их разность кратна натуральному числу, т.е. (а — b) g,.

Запишем это определение символами:

а º b (mod g), если $ kÎ Z (а — b= kg).,

Это значит, что числа а и b сравнимы по модулю g тогда и только тогда, когда они принадлежат одному подмножеству, т.е. дают одинаковые остатки при делении на g..

Например: 36 º I6 (mod l0) – числа 36 и 16 сравнимы по модулю 10

24 º 4 (mod 6) - число 24 сравнимо по модулю 6 с число 4

-26º 6 (mod 30)

Отметим разницу в записях: записей:

1. аº b (mod g ) или (а= b) (mod g ) означает сравнимость чисел по модулю (сравнение)

2. а= b (mod g ) - означает равенство числа a остатку от деления b на g

Отношение сравнимости рефлексивно, симметрично, транзитивно. Следовательно, оно является отношением эквивалентности.

Вычетами по модулю р называют отдельные классы эквивалентности для отношения сравнимо­сти (по модулю p)) и обозначают Z_p,

Раздел математики, изучающий вычеты по модулю, называется ал­геброй вычетов (теорией вычетов, модулярной арифметикой).

Свойства сравнимости

1. Два числа, сравнимые с третьим по одному модулю, сравни­мы между собой:

2. Сравнения можно складывать и вычитать:

(а º b(mod p); cºd(mod p)) => (а ± с) º (b ± d)(mod p).

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

3. Сравнения можно перемножать:

(a º b(mod p), с º d(mod p)) => (ас º bd(mod p)).

4. Обе части сравнения можно умножить на одно и то же целое число k:

(а º 6(mod p}) => (ak º bk(mod p)).

5. Обе части сравнения и модуль можно умножить на одно и то же число:

(а º b (mod p)) => (akºbk(mod pk)).

6. Обе части сравнения можно возвести в степень (следствие свойства 3):

(а º b (mod p)) => (аⁿ = bⁿ (mod p)).

Понятие сравнения ввел К.Ф.Гаусс в работе «Ариф­метические исследования» (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторя­ющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через пе­риод 2к, и т.д.

Алгебра вычетов — один из тех разделов математики, которые рождались как некоторые формальные рассуждения и только спустя годы нашли свое практи­ческое применение.

Задание 9-2. Для степени y=2ⁿ (n–натуральное число) установить классы сравнимости. Установить зависимость последней цифры этой степени от ее показателя.

Решение и комментарии.

Как известно, натуральные степени числа 2 оканчиваются циф­рами {2, 4, 8, 6}. См. таблицу нескольких степеней числа 2.

Опреде­лим функцию, которая ставит в соответствие каждому натуральному числу п последнюю цифру числа 2^я:

n	2n	Последняя цифра 2т

f: N®{2, 4, 8, 6},

Эта функция f(n) периодична с периодом 4. Это значит, что для целого числа k: f(n)=f(n+4)= f(n+4k),.

Причем справедливы так же равенства: f(n)=f(n-4)= f(n-4k)

Последнее равенство означают, что для любого п нужно найти минимальное натуральное т, такое, что f(m) = f(m + 4k) = f(n).

Но это задача на делении с остатком числа n на 4:

n=4k+m, k-частное, т — остаток.

Очевидно, последняя цифра числа 2″ зависит от остатка, полученного при делении показателя n степени 2 ⁿ на 4.

Отразим этот факт в записи функции: f(n)= f(n mod 4)

Из этой формулы можно установить, если f(n mod 4)=0, то

При делении чисел на 4 «nÎN, останки могут быть: 0,1,2,3. Таким образом, в частности, множество всех возможных показателей степени 2 ⁿ для любого n состоит из четырех подмножеств: 4k, 4k+ 1, 4k+ 2, 4k+3.

Задание 9-3.Установить последнюю цифру степени y=2 ²⁰⁰⁷

Решение. Имеем 2007=501·4+3, значит f (2007)=f (3)=2³=8. Ответ 8.

Тема 11. Криптографические шифры

План.

1. Защита информации, понятие шифра и шифрования

2. Простейшие криптографические шифры

Цель. Знакомство с понятием шифр и некоторыми криптографическими шифрами.