соотношению е∙d — 1 = 0 (mod ф(n)) то есть существует целое значение k, такое, что е∙d — 1 = k∙ф(n) или е∙d = k∙ф(n) + 1. Используя это и формулу Эйлера, получим:
(me)d = med = m kф(n)+1= m kф(n)∙m = (m ф(n))k∙m 1km (mod n) = m (mod n).
Это и есть нужный нам результат.
2. Если НОД (m,n) 1 и n = р∙q, тот содержит или только множитель р, или только q, или оба одновременно.
Пусть m содержит только множитель р. Тогда, во-первых, m кратно р, то есть существует целое число r, такое, что m = rр. Поэтому mde 0 (mod р) или mde = m (mod р), другими словами, существует значение А, такое, что:
mde — m = Ар. (1)
Во-вторых, мы имеем:
(me)d = med = mk ф(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).
Подставим это в предыдущее выражение.
(me)d = med = mk ф(n)+1 = m k ф(n)∙m = (mф(n))k∙m = (m(q-1))k(p-1)∙m 1k (р-1)∙m m (mod q).
Откуда мы заключаем, что существует значение В, такое что:
mde — m = Вq. (2)
Из (1) и (2) следует, что разность (mde — m) делится на n = рq, поэтому
mde — m 0 (mod n).
Аналогично это доказывается для случая, когда m содержит только множитель q.
В случае, когда m кратно и р, и q одновременно, результат тривиален. Следовательно,
(mе)d m (mod n).
Таким образом, мы продемонстрировали математическую основу алгоритма RSA.
Для заказа пропущенных книг и по всем вопросам, касающимся информации о коллекции, заходите на сайт 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)
Список литературы
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)