Математики, шпионы и хакеры. Кодирование и криптография | страница 73

∙m = (m ^>ф(n))^>k∙m 

Это и есть нужный нам результат.

2. Если НОД (m,n)

Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m = rр. Поэтому m^>de 

m^>de — m = Ар. (1)

Во-вторых, мы имеем:

(m^>e)^>d= m^>ed= m^{>k ф(n)+1} = m ^{>k ф(n)}∙m = (m^>ф(n))^>k∙m = (m^>(q-1))^>k(p-1)∙m.

Так как НОД (m, n) = р, НОД (m, q) = 1, то по теореме Ферма m^>(q-1) 

Подставим это в предыдущее выражение.

(m^>e)^>d = m^>ed = m^{>k ф(n)+1} = m ^{>k ф(n)}∙m = (m^>ф(n))^>k∙m = (m^>(q-1))^>k(p-1)∙m

Откуда мы заключаем, что существует значение В, такое что:

m^>de — m = Вq. (2)

Из (1) и (2) следует, что разность (m^>de — m) делится на n = рq, поэтому

m^>de — m 

Аналогично это доказывается для случая, когда m содержит только множитель q.

В случае, когда m кратно и р, и q одновременно, результат тривиален. Следовательно,

(m^>е)^>d 

Таким образом, мы продемонстрировали математическую основу алгоритма RSA.

Fernandez, S., Classical Cryptography. Sigma Review No. 24, April 2004.

Garfunkel, S., Mathematics in Daily Life, Madrid, COMAP, Addison-Wesley, UAM, 1998.

Gomez, J., From the Teaching to the Practice of Mathematics Barcelona, Paidos, 2002.

Kahn, D., The Codebreakers: The Story of Secret Writing, New York, Scribner, 1996.

Издание на русском языке: Кан Д. Взломщики кодов. — М.: Центрполиграф, 2000.

Singh, S., The Secret Codes, Madrid, Editorial Debate, 2000.

Tocci, R., Digital Systems: Principles and Applications, Prentice Hall, 2003.

Издание на русском языке: Тончи Р. Цифровые системы. Теория и практика. — М.: Вильямс, 2004.

_{>Научно-популярное издание}

_{>Выходит в свет отдельными томами с 2014 года}

_{>Мир математики}

_{>Том 2}

_{>Жуан Гомес}

_{>Математики, шпионы и хакеры.}

_{>Кодирование и криптография.}

_{>РОССИЯ}

_{>Издатель, учредитель, редакция:}

_{>ООО «Де Агостини», Россия}

_{>Юридический адрес: Россия, 105066,}

_{>г. Москва, ул. Александра Лукьянова, д. 3, стр. 1}

_{>Письма читателей по данному адресу не принимаются.}

_{>Генеральный директор: Николаос Скилакис}

_{>Главный редактор: Анастасия Жаркова}

_{>Старший редактор: Дарья Клинг}

_{>Финансовый директор: Наталия Василенко}

_{>Коммерческий директор: Александр Якутов}

_{>Менеджер по маркетингу: Михаил Ткачук}

_{>Менеджер по продукту: Яна Чухиль}

_{>Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт}