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

    Одна из фундаментальных проблем криптографии – безопасное общение по прослушиваемому каналу. Сообщения нужно зашифровывать и расшифровывать, но для этого обеим сторонам нужно иметь общий ключ. Если этот ключ передавать по тому же каналу, то прослушивающая сторона тоже получит его, и смысл шифрования исчезнет.

    Алгоритм Диффи — Хеллмана позволяет двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Полученный ключ можно использовать для обмена сообщениями с помощью симметричного шифрования.

    Предлагаю ознакомиться с принципом работы алгоритма Диффи – Хеллмана в замечательном видео от Art of the Problem в моем переводе.

    Метки:
    Поделиться публикацией
    Похожие публикации
    Комментарии 33
    • +5
      Мы сегодня многое поняли! (с) South Park
      • +31
        Если без шуток, то аналогия с красками — блестящая.
        • +1
          А мне наоборот с красками непонятным пример показался, а с цифрами намного понятней, кому как опять же
          • 0
            Я вот сейчас читаю «Прикладную криптографию». Не то, чтобы мне это было нужно или интересно. Просто использую как замену спреям в туалете. Так вот недавно как раз читал раздел с этими модулями. Конкретно, реализация вот такого алгоритма ускользнула от моего понимания после прочитаного там. Теперь все стало на свои места :)
      • +2
        Немного странная смесь. Понятно, что видео для начинающих, но мне всё равно кажется, что людям, которым нужно объяснение остатка по модулю, дальше этого объяснения будет непонятно.
        А за перевод спасибо.
        • 0
          Аудитория клипа — недавние школьники или первокурсники, которые вполне помнят что такое и логарифм, и модуль. Ну и другие граждане, которые так же это помнят. Так что это вполне удачный клип.
          • 0
            Так я о том же. Для такой аудитории ведь не нужно объяснять, что такое модуль, но на видео это занимает ощутимый кусок времени.
          • +1
            Если людям нужно объяснение остатка по модулю, то им в этом клипе будет непонятно практически всё.
            • +1
              Если я ничего не путаю, то в школе остаток от деления проходят раньше, чем десятичную или обыкновенную дробь.
            • +2
              Спасибо за перевод, раньше на хабре видел версию этого видео на английском.
              • +3
                Видео интересное, раньше не видел. Но увы алгоритм Диффи-Хеллмана подвержен MITM и не способен это проконтролировать.
                • +1
                  Пользуясь случаем, есть ли алгоритмы, которые защищены не только от прослушивания, но и от подмены, при передаче по открытому каналу? Или эти вопросы решает сертификаты и других вариантов нет?
                  • +4
                    Вопросы решаются только заранее переданной ключевой информацией по надёжному каналу.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +4
                        Их дофига и больше. Например, разновидность DH для авторизации, я о ней ниже писал.

                        Тут общий архитектурный вопрос — мы можем защититься от подмены только в том случае, если мы знаем с кем общаемся. Например, мы общаемся с сервером, на сервере локально зада пароль, мы знаем этот же пароль. Испольуем разновидность DH для авторизации, получаем общий ключ шифрования, используем его для шифрования траффика по какому-нибудь AES-256. Сертификаты используются для той же цели — получаем от сервера сертификат, проверям его встроенным в OS сертификатом что он действительно выдан на это доменное имя, после чего шифруем случайное число записанным в сертификате публичным ключем — сервер его расшифрует своим приватным и можно это число использовать дальше для шифрования траффика.

                        Если же мы не знаем с кем общаемся — то с нашей точки зрения, как клиента — не может быть разницы общаемся ли мы с Васей — или же со злобным хакером Петей, который выдает себя за Васю, а с Васей общается параллельно, выдавая себя за нас. Чтобы палить такие ситуации, нам нужно хотя бы знать, как выглядит Вася :).
                        • +2
                          >Чтобы палить такие ситуации, нам нужно хотя бы знать, как выглядит Вася

                          другими словами, нужно предварительное согласование аутентификационных данных (либо ключ (симметричный или открытый), либо сертификат доверенной третьей стороны)
                          • 0
                            Можно и не предварительное, а в рантайме — так сертификаты делают. Но для согласования в рантайме нужна третья сторона (в данном случае это Certificate Authority и сертификат с публичным ключем, заранее известный операционке).
                            • +1
                              иногда полезно бывает перед ответом прочитать комментарий целиком
                      • 0
                        Насколько я помню, DH подвержен MITM только в том случае, если оба участника ничего не знают друг о друге. Это не недостаток протокола — это суровая реальность жизни. Если мы не знаем заранее с кем общаемся, то мы в принципе не можем на уровне протокола определить — общаемся мы с Васей, или же со сзлобным хакером Петей, который выдает себя за Васю — а с Васей общается параллельно, выдавая себя за нас. Если же мы используем протокол для, к примеру, проверки логина/пароля, то можно использовать разновидность с известным обоим общим секретом, к примеру STS.
                        • 0
                          Не совсем корректно говорить, что _алгоритм_ подвержен MITM. В данном случае MITM подвержен _процесс_ обмена ключами _при_условии_ отсутствия взаимной аутентификации корреспондентов перед началом сеанса обмена ключами. А вот надежного способа аутентификации для _двух_ незнакомых людей без участия _доверенной_третьей_ стороны, увы, придумать невозможно…
                        • 0
                          Хм. А не этот ли способ заложен в начале общения истребителей по системе «свой-чужой»? Очень похоже.
                          • +2
                            Вряд-ли у истребителей есть необходимость на лету (во всех смыслах) обмениваться ключами. Им нужно лишь четко знать, кто «свой», а для этого вполне подойдет обычная аутентификация на основе сертификатов наподобие той, которая используется браузерами.

                            «Срок действия сертификата приближающегося истребителя истек, или еще не наступил.
                            <Игнорировать><Добавить исключение><Открыть огонь!!!>»
                          • –3
                            Примеры напомнили книгу Криптография. Официальное руководство RSA Security. Даже имена участников теже :)
                            • +16
                              Имена Alice, Bob и Eve стали классическим стандартом в криптографии :)
                            • +7
                              Всё бы ничего, но на 4:37 и 4:52 автор ролика так смело играет числами, и заменяет остаток на число до деления, как-будто это всем известный факт, что (x^n mod k)^m mod k = x^(n*m) mod k. А вообще, да, хороший пример про смешивание цветов для объяснения принципа «на пальцах».
                              • 0
                                В этом видео с шестой минуты идет немного более детальное объяснение.
                                • 0
                                  Да, детальнее, но упомянутая мною замена так и не объясняется. Здесь эта замена тоже делается «просто так» на 7:34 и 7:50
                              • +15
                                Доступно объяснить сложное знание — это очень большой талант. Видео на 5+
                                • 0
                                  Ха, с радостью вспомнил свою дипломную на тему взлома дискретного логарифма.
                                  • 0
                                    расскажите
                                    • 0
                                      Нечего рассказывать, всё есть в интернете. Одной из штук, которой я уделил большой кусок времени была работа с алгоритмом Сильвера-Полига-Хеллмана. В практической части я генерировал большое гладкое простое число (особое «плохое» число) размером в 650 десятичных знаков в качестве ключа и взламывал за два часа. Причем самой интересной деталью для меня было то, что я это всё делал на Яваскрипте :)
                                  • 0
                                    На моменте видео 3:13 говорится о том, что результат по модулю 17 может быть любым числом от 1 до 16. А разве 0 не может быть? Это ошибка или сказано намерено?
                                    • 0

                                      Это не ошибка. В общем случае x % 17 может быть 0, но там речь о 3x % 17. Так как 3 и 17 взаимно просты, то 3 в любой степени никогда не кратно 17.

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.