Элементы теории сравнений

Утверждение 1. Если аcравнима сbпо модулюpи еслиасравнима сbпо модулюqиpиq- взаимно просты, тоасравнимаbпо модулюpq, т.е.ab mod p иab mod q  ab mod pq. F.e. a=343, b=223, тогдаab mod 6 p=2 q=3 и ab mod 20 и ab mod 120. Утверждение 2. Еслиab mod m и cd mod m, тоacbd mod m. Cледствие.ab mod m  a^sb^s mod m. F.e. a=343, b=223, m=6, c=17, d=11, m=6, тогдаacbd mod 6 (5) и58312453 mod 6 (5). Утверждение 3. Еслиab mod m иcd mod m, тоa+cb+d mod m. F.e. a=343, b=223, c=17, d=11, m=6  a+cb+d mod 6. Из утверждений 2 и 3 следует, что в любом арифметическом выражении из переменных или постоянных, связанных операциями «+» или «», можно ставить другую величину с ней сравнимую. Утверждение 4. Обе части сравнения можно делить на числоrесли: 1) в обеих частях сравнения после деления останутся целые числа; 2)mиrвзаимно простые. Док-во:crdr mod m  m cr-dr  m r(c-d). В силу 2):m c-d, cd mod. Конец док-ва. Малая теорема Ферма: Еслиm- простое число иа- произвольное целое число, не делящееся наm, то можно записатьa^m-11 mod m. F.e. a=17, m=13, то 17¹²1 mod 13. Док-во: Рассмотрим числаа, 2а, 3а,...,ma. Никакие 2 из этих чисел не дают при делении наmодинаковых остатков, поэтому при делении наmчислаа, 2а, 3а,...,maдают остатки 0, 1, 2,...,m-1 в каком-то порядке, где 0 получается при деленииma на m. Опускаем 0, имеемa^m-1(m-1)!(m-1)! mod m. Вычитаем правую часть из левой, получаемa^m-1(m-1)! - (m-1)!0 mod m, откуда (a^m-1-1)(m-1)!делится наm. Т.к.mне делит(m-1)!, тоmделит (a^m-1-1). Конец док-ва.

Выработка секретного ключа по Диффи и Хеллману

Из математических операций нас интересуют две: 1) легкая операция - перемножить два больших числа N=pq; трудная операция - разложитьmна множители (факторизация). 2) легкая операция - возвести основаниеав степень р и взять остаток по модулюm: La^p mod m; трудная операция - найти р, знаяL, a и m. Обе трудные задачи решаются перебором по р и след-но практически не решаются, если р - очень большое число. Пусть известныаи модульmи они могут быть переданы по сети открытым текстом. Рассмотрим схему выработки секретного ключа по Диффи-Хеллману:

Этапы	Отправитель	Враг	Получатель
Этап 1 Этап 2	Вырабатывает случайное число х, причем 1<x<m. ВычисляетLia^x mod m и передаетLiполучателю. ПолучаетLj. Вычисляет Kia^yx mod m= Lj^x.		Li, вырабатывает случайное числоy,1<y<m. ВычисляетLja^y mod m и передаетLj отправителю. Вычисляет Kj= Lj^ya^xy mod m.

Системы rsa

Rivest, Shamir, Aldeman. Основаны на трудности разложения очень больших целых чисел на простые сомножители.

Отправитель выбирает 2 очень больших числа p иqи вычисляетn=pqиk=(p‑1)(q-1);

Затем он выбирает случ. целое число d, взаимно простое сkи выбирает случ. целое числоeтакое, чтоde≡1 mod k;

После этого он публикует d иn как свой открытый ключ шифрования, сохраняяe как закрытый ключ;

Если S – сообщение, то его можно представить кодом, то 1≤S<n. ЕслиS>n, то разбиваемS на куски. Сообщ-еS превращается в шифровку возведением в степеньd по модулюn и отправл-ся получателю: S'=S^d mod n;

Получатель сообщ-я расшифровывает его, возводя в степень eпо модулюn: S=S'^e mod n=S^de mod n.

Теорема. Если n=pq иed≡1 mod (p-1)(q-1), то 1<m<n, гдеm иn – взаимно простые, то (m^e)^d=m^ed≡m mod n. □ По малой т-ме Фермаm^p-1≡1 mod p. Возводим обе части в степень(q-1):

m^(p-1)(q-1)k≡1 mod (pq=n). m≡m mod n  m^{(p-1)(q-1)k+1}m mod n. С другой стороныed1 mod (p-1)(q-1)  (p-1)(q-1)|ed-1  ed-1=k(p-1)(q-1)  ed=(p-1)(q-1)k+1  m^ed=m mod n ■

Пример:p=211, q=223, n=47053, m=46620 d=16813, e=19837 RSA: R-18, S-19, A-1. На представление каждой буквы отведём по 5 бит:S=((1∙32)+19)∙32+18=1650. 1’10011’10010. Получаем шифровку:S’=S^d mod n=1650¹⁶⁸¹³ mod 47053=3071. S=S’^e mod n=3071¹⁹⁸³⁷ mod 47053=1650.