Чтение онлайн

на главную - закладки

Жанры

Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:

(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 =. Поэтому mde 

0 (mod р) или mde = m (mod р), другими словами, существует значение А, такое, что:

mde m = Ар. (1)

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

(me)d = med = mk ф(n)+1 = m k ф(n)m = (mф(n))km = (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))km = (m(q-1))k(p-1)m

 1k (р-1)m 
m (mod q).

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

mde m = Вq. (2)

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

mde 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 , по остальным вопросам обращайтесь по телефону бесплатной горячей линии в России:

Поделиться:
Популярные книги

Протокол "Наследник"

Лисина Александра
1. Гибрид
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Протокол Наследник

Сердце Дракона. Том 9

Клеванский Кирилл Сергеевич
9. Сердце дракона
Фантастика:
фэнтези
героическая фантастика
боевая фантастика
7.69
рейтинг книги
Сердце Дракона. Том 9

Дайте поспать! Том II

Матисов Павел
2. Вечный Сон
Фантастика:
фэнтези
постапокалипсис
рпг
5.00
рейтинг книги
Дайте поспать! Том II

Драконий подарок

Суббота Светлана
1. Королевская академия Драко
Любовные романы:
любовно-фантастические романы
7.30
рейтинг книги
Драконий подарок

Сумеречный Стрелок 3

Карелин Сергей Витальевич
3. Сумеречный стрелок
Фантастика:
городское фэнтези
попаданцы
аниме
5.00
рейтинг книги
Сумеречный Стрелок 3

Возвращение

Кораблев Родион
5. Другая сторона
Фантастика:
боевая фантастика
6.23
рейтинг книги
Возвращение

Восход. Солнцев. Книга VIII

Скабер Артемий
8. Голос Бога
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Восход. Солнцев. Книга VIII

Идеальный мир для Лекаря

Сапфир Олег
1. Лекарь
Фантастика:
фэнтези
юмористическое фэнтези
аниме
5.00
рейтинг книги
Идеальный мир для Лекаря

На границе империй. Том 7

INDIGO
7. Фортуна дама переменчивая
Фантастика:
боевая фантастика
космическая фантастика
попаданцы
6.75
рейтинг книги
На границе империй. Том 7

Кодекс Крови. Книга V

Борзых М.
5. РОС: Кодекс Крови
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Кодекс Крови. Книга V

Адмирал южных морей

Каменистый Артем
4. Девятый
Фантастика:
фэнтези
8.96
рейтинг книги
Адмирал южных морей

Возвышение Меркурия. Книга 15

Кронос Александр
15. Меркурий
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Возвышение Меркурия. Книга 15

Измена

Рей Полина
Любовные романы:
современные любовные романы
5.38
рейтинг книги
Измена

Эффект Фостера

Аллен Селина
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Эффект Фостера