Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография

(m e) d= m ed= m kф(n)+1= m kф(n)∙m= (m ф(n)) k∙m 1 km (mod n)= m (mod n).

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

2. Если НОД ( m, n) 1 и n= р∙ q, тот содержит или только множитель р, или только q, или оба одновременно.

Пусть mсодержит только множитель р. Тогда, во-первых, mкратно р, то есть существует целое число r, такое, что m= rр. Поэтому m de 0 (mod р)или m de= m (mod р), другими словами, существует значение А, такое, что:

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) 1 (mod q).

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

(m e) d= m ed= m k ф(n)+1= m k ф(n)∙m = (m ф(n)) k∙ m= (m (q-1)) k(p-1)∙ m 1 k (р-1)∙ m m (mod q).

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

m de— m= Вq. (2)

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

m de— m 0 (mod n).

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

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

(m е) d m (mod n).

Таким образом, мы продемонстрировали математическую основу алгоритма 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

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

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

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

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

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

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

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

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

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ru , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России:

© 8-800-200-02-01

Телефон горячей линии для читателей Москвы:

© 8-495-660-02-02

Адрес для писем читателей:

Россия, 170100, г. Тверь, Почтамт, а/я 245,

«Де Агостини», «Мир математики»

Пожалуйста, указывайте в письмах свои контактные данные для обратной связи (телефон или e-mail).

Распространение:

ООО «Бурда Дистрибьюшен Сервисиз»

УКРАИНА

Издатель и учредитель:

ООО «Де Агостини Паблишинг» Украина

Юридический адрес: 01032, Украина,

г. Киев, ул. Саксаганского, 119

Генеральный директор: Екатерина Клименко

Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт www.deagostini.ua , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в Украине:

© 0-800-500-8-40

Адрес для писем читателей:

Украина, 01033, г. Киев, a/я «Де Агостiнi»,

«Мир математики»

Украïна, 01033, м. Кiев, а/с «Де Агостiнi»

БЕЛАРУСЬ

Импортер и дистрибьютор в РБ:

ООО «Росчерк», 220037, г. Минск,

ул. Авангардная, 48а, литер 8/к,

тел./факс: +375 17 331 94 27

Телефон «горячей линии» в РБ:

© + 375 17 279-87-87 (пн-пт, 9.00–21.00)

Адрес для писем читателей:

Республика Беларусь, 220040, г. Минск,

а/я 224, ООО «Росчерк», «Де Агостини»,

«Мир математики»

КАЗАХСТАН

Распространение:

ТОО «КГП «Бурда-Алатау Пресс»

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

Отпечатано в соответствии с предоставленными материалами в типографии:

Grafica Veneta S.p.A Via Malcanton 2

35010 Trebaseleghe (PD) Italy

Подписано в печать: 31.07.2013

Дата поступления в продажу на территории России: 28.01.2014

Формат 70 х 100 / 16. Гарнитура «Academy».

Печать офсетная. Бумага офсетная. Печ. л. 4,5.

Уел. печ. л. 5,832.

Тираж: 200 000 экз.

© Joan Gomez, 2010 (текст)

© RBA Collecionables S.A., 2010

© ООО «Де Агостини», 2014

ISBN 978-5-9774-0682-6

ISBN 978-5-9774-0639-0 (т. 2)