Mybrary.info
mybrary.info » Книги » Научно-образовательная » Математика » Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные книги онлайн без регистрации TXT) 📗

Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные книги онлайн без регистрации TXT) 📗

Тут можно читать бесплатно Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные книги онлайн без регистрации TXT) 📗. Жанр: Математика. Так же Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте mybrary.info (MYBRARY) или прочесть краткое содержание, предисловие (аннотацию), описание и ознакомиться с отзывами (комментариями) о произведении.
Перейти на страницу:

Всем известно, что для обеспечения безопасности кода ключи шифрования должны быть защищены надежнее, чем алгоритм. Тогда возникает проблема: как безопасно распределять ключи. Даже в простых случаях это является серьезной проблемой логистики, например, как распределить тысячи шифровальных книг среди радистов большой армии, или как доставить книги в мобильные центры связи, работающие в экстремальных условиях, такие как станции на подводных лодках или штабы на линии фронта. Какой бы сложной ни была классическая система шифрования, она остается уязвимой, так как соответствующие ключи могут быть перехвачены.

Алгоритм Диффи — Хеллмана

Сама концепция безопасного обмена ключами может показаться противоречивой: как вы можете послать ключ в виде сообщения, которое уже как-то зашифровано?

Ключом, переданным заранее обычным способом? Однако, если ключами действительно несколько раз обменивались, то решение проблемы можно себе представить — по крайней мере, на теоретическом уровне.

Предположим, что отправитель по имени Джеймс шифрует сообщение с помощью своего ключа и посылает результат получателю по имени Питер, который повторно шифрует зашифрованное послание своим ключом и возвращает его отправителю. Джеймс расшифровывает сообщение своим ключом и посылает назад результат, т. е. текст, в данный момент зашифрованный только ключом Питера, который его расшифровывает. Казалось бы, вековая проблема безопасного обмена ключами решена! Неужели это правда? К сожалению, нет. В любом сложном алгоритме шифрования порядок применения ключей имеет решающее значение, а в нашем примере мы видим, что Джеймс расшифровывает сообщение, которое уже зашифровано другим ключом. Когда порядок ключей меняется, результат будет абракадаброй. Вышеизложенный пример не объясняет теории подробно, но он дает подсказку к решению проблемы. В 1976 г. два молодых американских ученых, Уитфилд Диффи и Мартин Хеллман, нашли способ, при котором два человека могут обмениваться зашифрованными сообщениями без всякого обмена секретными ключами. Этот метод использует модульную арифметику, а также свойства простых чисел. Идея заключается в следующем.

* * *

АВТОРЫ АЛГОРИТМА

Уитфилд Диффи родился в 1944 г. в Соединенных Штатах. Получив степень бакалавра математики в Массачусетском технологическом институте (МП), он с 2002 по 2009 гг. работал главой службы безопасности и вице-президентом компании Sun Microsystems (в Калифорнии).

Инженер Мартин Хеллман родился в 1945 г. и работал в IBM и Массачусетском технологическом институте, где сотрудничал с Диффи.

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

Уитфилд Диффи

* * *

1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это число Nj1

2. Питер выбирает другое случайное число, которое он тоже держит в секрете. Мы обозначим это число Np1

3. Затем и Джеймс, и Питер применяют к своим числам функцию вида f(x) = ах (mod р) где р — простое число, известное им обоим.

∙ После этой операции Джеймс получает новое число, Nj2, которое он посылает Питеру.

∙ А Питер посылает Джеймсу свое новое число Np2

4. Джеймс вычисляет NNj1p2 (mod р) и получает новое число Сj.

5. Питер вычисляет NNp1j2 (mod р) и получает новое число Ср.

Хотя это кажется невозможным, но числа Сj и Ср являются одинаковыми. И теперь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией только тогда, когда они выбрали функцию f(x) = ах (mod р) и послали друг другу числа Nj2 и Np2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:

aNj1∙Np1  (mod p).

Важно также учесть, что данная функция имеет одну особенность: она необратима, то есть зная саму функцию и результат ее применения к переменной х, невозможно (или, по крайней мере, очень сложно) найти исходное значение х.

Далее, чтобы пояснить идею, мы повторим процесс с конкретными значениями.

Возьмем следующую функцию:

f(x) = 7х (mod 11).

1. Джеймс выбирает число, NJ1 например, 3, и подставляет в функцию f(3) = 7 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_21
2 (mod 11).

2. Питер выбирает число, Np1 например, 6, и подставляет в функцию f(6) = 76 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_22
4 (mod 11).

3. Джеймс посылает Питеру свой результат, 2, а Питер Джеймсу — свой, 4.

4. Джеймс считает 43 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_23
9 (mod 11).

5. Питер считает 26 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_26
9 (mod 11).

Это число, 9, и будет ключом системы.

Джеймс и Питер обменялись функцией f(х) и числами 2 и 4. Будет ли эта информация полезна злоумышленнику? Допустим, злоумышленник знает и функцию, и числа. Тогда он должен найти Nj1 и Np1 по модулю 11, где Nj1 и Np1 — такие числа, которые и Джеймс, и Питер держат в секрете даже друг от друга. Если шпиону удастся узнать эти числа, он получит ключ, лишь вычислив aNj1∙Np1  по модулю р. Решение уравнения вида у = ах, кстати, в математике называется дискретным логарифмом.

Например, в случае:

f(х) = 3х (mod 17),

зная, что 3х = 15 (mod 17), и пробуя различные значения х, мы получим, что х = 6.

Алгоритмы этого типа и задачи с дискретным логарифмом не получали должного внимания вплоть до начала 1990 гг., и лишь в последнее время эти методы начали разрабатываться. В приведенном выше примере число 6 является дискретным логарифмом числа 15 с основанием 3 по модулю 17.

Особенностью этого типа уравнений, как мы уже говорили, является сложность обратного процесса — они асимметричны. Если р больше 300, а число а больше 100, решение — и, следовательно, взлом ключа — становится крайне сложной задачей.

* * *

ВИРУСЫ И БЭКДОРЫ

Даже самый безопасный шифр с открытым ключом зависит от закрытого ключа, который держится в секрете. Следовательно, если компьютерный вирус заражает компьютер, находит и передает этот закрытый ключ, вся система шифрования сводится на нет. В 1998 г. стало известно, что одна швейцарская компания, лидер в области производства и распространения криптографических продуктов, включала в свои продукты бэкдоры («черные ходы»), которые обнаруживали закрытые ключи пользователей и пересылали их компании. Часть этой информации передавалась правительству Соединенных Штатов, которое, таким образом, могло читать сообщения, посылаемые инфицированными компьютерами.

* * *

Этот алгоритм является основой современной криптографии. Диффи и Хеллман представили свою идею на Национальной компьютерной конференции, на семинаре, который можно назвать поворотным. В полном объеме их работу можно почитать на www.cs.berkeley.edu/~christos/classics/diffiehellman.pdf, статья с названием «Новые направления в криптографии».

Перейти на страницу:

Гомес Жуан читать все книги автора по порядку

Гомес Жуан - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки mybrary.info.


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

Отзывы читателей о книге Математики, шпионы и хакеры. Кодирование и криптография, автор: Гомес Жуан. Читайте комментарии и мнения людей о произведении.


Уважаемые читатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.

  • 1. Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации.
  • 2. Просьба отказаться от оскорблений, угроз и запугиваний.
  • 3. Просьба отказаться от нецензурной лексики.
  • 4. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.

Надеемся на Ваше понимание и благоразумие. С уважением, администратор mybrary.info.


Прокомментировать
Подтвердите что вы не робот:*