- 26,074
- 46
- 8 Ноя 2022
Банки, мессенджеры, покупки — всё держится на этой формуле.
В октябре 1942 года британские эсминцы загнали немецкую подлодку у дельты Нила и начали забрасывать глубинными бомбами. Повреждённая лодка всплыла и стала быстро тонуть. В этот момент трое британцев перепрыгнули с корабля на вражеское судно и спустились внутрь, хотя экипаж уже покидал отсек за отсеком. Лейтенант Энтони Фассон, матрос Колин Грейзер и шестнадцатилетний помощник буфетчика Томми Браун искали не оружие и не пленных. А их целью были книги с кодами настройки немецкой шифровальной машины.
Речь о документах для системы «Энигма». В них содержались параметры, по которым немецкие военные настраивали шифрование сообщений. Чернила в этих книгах растворялись в воде, поэтому счёт шёл на минуты. Двое из трёх участников операции погибли, выбраться удалось только подростку. Уже через несколько недель британские криптоаналитики, включая команду Алан Тьюринг, использовали добытые материалы, чтобы читать немецкие сообщения. Историки оценивают вклад расшифровки как фактор, который сократил войну примерно на два года.
История с подлодкой показывает, насколько сложной задачей оставалась криптография. Чтобы передать секретное сообщение, стороны должны заранее договориться о способе шифрования. Без этого даже зашифрованный текст окажется бесполезным для получателя. Возникает замкнутый круг. Если отправитель передаст ключ тем же каналом, что и сообщение, перехватчик получит всё сразу. Эта проблема получила название задачи распределения ключей. По сути, для безопасной связи сначала нужна уже существующая безопасная связь.
Долгое время задачу решали не математикой, а организацией. Использовали личные встречи, курьеров, тайники и операции вроде захвата документов с тонущих кораблей. Ситуация изменилась в 1976 году, когда исследователи Стэнфордского университета Уитфилд Диффи и Мартин Хеллман предложили способ договориться о секрете по открытому каналу. Их метод позволил двум незнакомым участникам получить общий ключ, даже если весь обмен данными проходит под наблюдением.
<!--'start_frame_cache_Zg1Ab0'--><div class="banner-detailed"><div class="banner-detailed__shell"><div class="banner-detailed__title">Не спрашивайте почему мы в MAX. <span>Мы и сами не гордимся</span><div class="banner-detailed__arrow"><svg viewBox="0 0 40 40" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M20.5375 34.4392L22.465 31.7392C22.5739 31.5872 22.7145 31.4607 22.8772 31.3684C23.0399 31.2762 23.2207 31.2205 23.407 31.2052C23.5934 31.1898 23.7809 31.2152 23.9564 31.2796C24.132 31.344 24.2915 31.4458 24.4237 31.578L29.6025 36.758C30.0787 37.2333 30.724 37.5002 31.3969 37.5002C32.0697 37.5002 32.715 37.2333 33.1912 36.758L36.7575 33.1917C37.2328 32.7155 37.4998 32.0702 37.4998 31.3973C37.4998 30.7245 37.2328 30.0792 36.7575 29.603L31.5775 24.4242C31.4453 24.2919 31.3435 24.1325 31.2791 23.9569C31.2147 23.7814 31.1893 23.5939 31.2047 23.4075C31.22 23.2211 31.2757 23.0404 31.368 22.8777C31.4602 22.715 31.5867 22.5743 31.7387 22.4655L34.4387 20.538C34.6405 20.3939 34.7965 20.1947 34.8878 19.9641C34.9791 19.7336 35.0018 19.4816 34.9534 19.2385C34.9049 18.9953 34.7873 18.7713 34.6146 18.5934C34.442 18.4155 34.2216 18.2912 33.98 18.2355L13.5112 13.5117L18.235 33.9805C18.2907 34.2221 18.415 34.4425 18.5929 34.6151C18.7708 34.7878 18.9948 34.9054 19.238 34.9539C19.4812 35.0023 19.7331 34.9795 19.9637 34.8882C20.1942 34.7969 20.3934 34.641 20.5375 34.4392Z" fill="#FFD98C"></path><path d="M34.0751 37.6413C33.3582 38.3389 32.3973 38.7293 31.397 38.7293C30.3966 38.7293 29.4358 38.3389 28.7189 37.6413L23.4826 32.4663L21.5539 35.165C21.2699 35.5626 20.8773 35.8698 20.423 36.0497C19.9688 36.2295 19.4723 36.2744 18.9931 36.179C18.514 36.0836 18.0726 35.8518 17.7219 35.5117C17.3713 35.1715 17.1263 34.7373 17.0164 34.2613L12.2926 13.7925C12.2447 13.5858 12.2502 13.3702 12.3086 13.1662C12.367 12.9622 12.4764 12.7764 12.6264 12.6263C12.7765 12.4763 12.9623 12.3669 13.1663 12.3085C13.3703 12.2501 13.5859 12.2446 13.7926 12.2925L34.2614 17.0175C34.7374 17.1271 35.1717 17.3719 35.512 17.7225C35.8523 18.073 36.0841 18.5144 36.1795 18.9935C36.275 19.4726 36.23 19.9691 36.0501 20.4233C35.8701 20.8775 35.5628 21.27 35.1651 21.5538L32.4614 23.54L37.6414 28.7188C38.3498 29.43 38.7476 30.393 38.7476 31.3969C38.7476 32.4008 38.3498 33.3637 37.6414 34.075L34.0751 37.6413ZM35.8751 30.4863L30.6951 25.3075C30.4344 25.047 30.2336 24.7328 30.1068 24.3868C29.9799 24.0407 29.9299 23.6712 29.9604 23.3039C29.9908 22.9366 30.101 22.5804 30.2831 22.26C30.4653 21.9396 30.7151 21.6628 31.0151 21.4488L33.6989 19.4488L15.1851 15.1763L19.5001 33.7275L19.5139 33.7113L21.4414 31.0125C21.6555 30.7124 21.9325 30.4626 22.253 30.2805C22.5735 30.0983 22.9298 29.9882 23.2972 29.9577C23.6646 29.9272 24.0342 29.9772 24.3803 30.1041C24.7264 30.231 25.0407 30.4318 25.3014 30.6925L30.4864 35.875C30.728 36.1163 31.0555 36.2518 31.397 36.2518C31.7385 36.2518 32.066 36.1163 32.3076 35.875L35.8751 32.3075C36.1161 32.0657 36.2514 31.7383 36.2514 31.3969C36.2514 31.0555 36.1161 30.728 35.8751 30.4863ZM8.14636 9.385C7.98292 9.38706 7.82069 9.35675 7.66901 9.29583C7.51733 9.2349 7.37921 9.14455 7.26261 9.03L4.58011 6.3475C4.35242 6.11175 4.22643 5.796 4.22927 5.46825C4.23212 5.1405 4.36358 4.82699 4.59534 4.59523C4.8271 4.36347 5.14062 4.23201 5.46836 4.22916C5.79611 4.22631 6.11186 4.3523 6.34761 4.58L9.03012 7.2625C9.20107 7.43787 9.31674 7.65959 9.36277 7.90013C9.4088 8.14068 9.38315 8.38944 9.28901 8.61553C9.19487 8.84162 9.03639 9.03508 8.83325 9.17188C8.63011 9.30867 8.39126 9.38278 8.14636 9.385ZM17.9726 9.03C17.7362 9.26044 17.419 9.3894 17.0889 9.3894C16.7587 9.3894 16.4416 9.26044 16.2051 9.03C15.9708 8.79559 15.8391 8.47771 15.8391 8.14625C15.8391 7.8148 15.9708 7.49691 16.2051 7.2625L18.8876 4.58C19.0029 4.46061 19.1409 4.36538 19.2934 4.29987C19.4459 4.23436 19.6099 4.19988 19.7759 4.19844C19.9418 4.197 20.1064 4.22862 20.2601 4.29147C20.4137 4.35432 20.5532 4.44714 20.6706 4.56451C20.788 4.68187 20.8808 4.82144 20.9436 4.97506C21.0065 5.12868 21.0381 5.29328 21.0367 5.45925C21.0352 5.62523 21.0008 5.78925 20.9352 5.94176C20.8697 6.09426 20.7745 6.23219 20.6551 6.3475L17.9726 9.03ZM6.34761 20.655C6.11146 20.886 5.79423 21.0154 5.46386 21.0154C5.1335 21.0154 4.81627 20.886 4.58011 20.655C4.34578 20.4206 4.21413 20.1027 4.21413 19.7713C4.21413 19.4398 4.34578 19.1219 4.58011 18.8875L7.26261 16.205C7.37792 16.0856 7.51585 15.9904 7.66836 15.9249C7.82086 15.8594 7.98489 15.8249 8.15086 15.8234C8.31684 15.822 8.48144 15.8536 8.63506 15.9165C8.78868 15.9793 8.92824 16.0721 9.04561 16.1895C9.16297 16.3069 9.25579 16.4464 9.31864 16.6001C9.38149 16.7537 9.41312 16.9183 9.41168 17.0843C9.41024 17.2502 9.37575 17.4143 9.31024 17.5668C9.24473 17.7193 9.1495 17.8572 9.03012 17.9725L6.34761 20.655ZM12.6176 7.54375C12.2861 7.54375 11.9682 7.41205 11.7337 7.17763C11.4993 6.94321 11.3676 6.62527 11.3676 6.29375V2.5C11.3676 2.16848 11.4993 1.85054 11.7337 1.61612C11.9682 1.3817 12.2861 1.25 12.6176 1.25C12.9491 1.25 13.2671 1.3817 13.5015 1.61612C13.7359 1.85054 13.8676 2.16848 13.8676 2.5V6.29375C13.8676 6.62527 13.7359 6.94321 13.5015 7.17763C13.2671 7.41205 12.9491 7.54375 12.6176 7.54375ZM2.50011 11.3675H6.29387C6.62539 11.3675 6.94333 11.4992 7.17775 11.7336C7.41217 11.968 7.54387 12.286 7.54387 12.6175C7.54387 12.949 7.41217 13.267 7.17775 13.5014C6.94333 13.7358 6.62539 13.8675 6.29387 13.8675H2.50011C2.16859 13.8675 1.85065 13.7358 1.61623 13.5014C1.38181 13.267 1.25011 12.949 1.25011 12.6175C1.25011 12.286 1.38181 11.968 1.61623 11.7336C1.85065 11.4992 2.16859 11.3675 2.50011 11.3675Z" fill="#272727"></path></svg> <!--'end_frame_cache_Zg1Ab0'--> Идея Диффи-Хеллмана легла в основу протокола обмена ключами, который сегодня используют повсеместно. Проверка банковского счёта, покупки в интернете, защищённые сайты с адресом https, сообщения в мессенджерах — все эти действия опираются на варианты того же принципа. Задача осталась прежней: обе стороны должны получить одно и то же большое случайное число, которое станет секретным ключом .
Чтобы понять логику метода, удобно представить бытовую аналогию. Две стороны заранее договариваются о какой-то базовой единице — например (если рассуждать образно), о рецепте химической смеси, известном всем, включая наблюдателя. Затем каждая сторона добавляет в эту основу свой секретный ингредиент и отправляет результат собеседнику. Получатель снова добавляет свой скрытый компонент к уже полученной формуле. В итоге обе стороны получают одинаковый состав, хотя ни разу не передавали секретные ингредиенты напрямую. Перехватчик видит только промежуточные смеси, но не может точно восстановить рецепт.
Конечно, компьютеры вместо жидкостей используют числа и операции над ними. Участники выбирают общее базовое число и большое простое число. Затем каждый берёт собственное секретное значение и выполняет возведение в степень с последующим вычислением остатка от деления. Результаты передаются по открытому каналу. После этого каждая сторона повторяет операцию, используя полученное число и свой секрет. В обоих случаях получается одинаковый итог — общее число, известное только участникам.
Ключевая деталь здесь — так называемая односторонняя функция. Вычислить результат просто, а восстановить исходные данные по этому результату крайне сложно. В обычной арифметике возведение в степень легко обратить через логарифм. Но в арифметике по модулю, где результат постоянно «заворачивается» по кругу, ситуация меняется. Значения начинают вести себя непредсказуемо. Например, при обычном возведении в степень результат растёт по понятному правилу. В арифметике по модулю те же операции дают последовательность, которая выглядит почти случайной.
Попытка восстановить секретное число по известным параметрам приводит к задаче дискретного логарифма. Для больших чисел, которые используют на практике, задача становится неподъёмной с точки зрения вычислений. Секретные значения могут содержать десятки цифр, а используемые простые числа — сотни. Даже самые быстрые известные алгоритмы потребуют астрономического времени на подбор решения.
При этом строгого доказательства сложности такой задачи до сих пор нет. Современная безопасность интернета держится на предположении, что быстрого способа решения попросту не существует. За десятилетия ни одна спецслужба и ни одна хакерская группа не продемонстрировали рабочий обход, хотя через такие схемы проходят банковские операции и государственные данные на триллионы долларов.
Слабое место у системы всё же есть. В 1994 году математик Питер Шор показал, что квантовый компьютер может решить задачу дискретного логарифма за часы. Алгоритм Шора использует свойства квантовой механики и в теории ломает существующие схемы шифрования. Но проблема упирается в железо: подходящего квантового компьютера пока не существует. Инженеры работают над такими системами, а криптографы параллельно разрабатывают постквантовые алгоритмы. До их массового внедрения обмен ключами по Диффи – Хеллману продолжает защищать большую часть цифровых коммуникаций.
В октябре 1942 года британские эсминцы загнали немецкую подлодку у дельты Нила и начали забрасывать глубинными бомбами. Повреждённая лодка всплыла и стала быстро тонуть. В этот момент трое британцев перепрыгнули с корабля на вражеское судно и спустились внутрь, хотя экипаж уже покидал отсек за отсеком. Лейтенант Энтони Фассон, матрос Колин Грейзер и шестнадцатилетний помощник буфетчика Томми Браун искали не оружие и не пленных. А их целью были книги с кодами настройки немецкой шифровальной машины.
Речь о документах для системы «Энигма». В них содержались параметры, по которым немецкие военные настраивали шифрование сообщений. Чернила в этих книгах растворялись в воде, поэтому счёт шёл на минуты. Двое из трёх участников операции погибли, выбраться удалось только подростку. Уже через несколько недель британские криптоаналитики, включая команду Алан Тьюринг, использовали добытые материалы, чтобы читать немецкие сообщения. Историки оценивают вклад расшифровки как фактор, который сократил войну примерно на два года.
История с подлодкой показывает, насколько сложной задачей оставалась криптография. Чтобы передать секретное сообщение, стороны должны заранее договориться о способе шифрования. Без этого даже зашифрованный текст окажется бесполезным для получателя. Возникает замкнутый круг. Если отправитель передаст ключ тем же каналом, что и сообщение, перехватчик получит всё сразу. Эта проблема получила название задачи распределения ключей. По сути, для безопасной связи сначала нужна уже существующая безопасная связь.
Долгое время задачу решали не математикой, а организацией. Использовали личные встречи, курьеров, тайники и операции вроде захвата документов с тонущих кораблей. Ситуация изменилась в 1976 году, когда исследователи Стэнфордского университета Уитфилд Диффи и Мартин Хеллман предложили способ договориться о секрете по открытому каналу. Их метод позволил двум незнакомым участникам получить общий ключ, даже если весь обмен данными проходит под наблюдением.
<!--'start_frame_cache_Zg1Ab0'--><div class="banner-detailed"><div class="banner-detailed__shell"><div class="banner-detailed__title">Не спрашивайте почему мы в MAX. <span>Мы и сами не гордимся</span><div class="banner-detailed__arrow"><svg viewBox="0 0 40 40" fill="none" xmlns="http://www.w3.org/2000/svg"><path d="M20.5375 34.4392L22.465 31.7392C22.5739 31.5872 22.7145 31.4607 22.8772 31.3684C23.0399 31.2762 23.2207 31.2205 23.407 31.2052C23.5934 31.1898 23.7809 31.2152 23.9564 31.2796C24.132 31.344 24.2915 31.4458 24.4237 31.578L29.6025 36.758C30.0787 37.2333 30.724 37.5002 31.3969 37.5002C32.0697 37.5002 32.715 37.2333 33.1912 36.758L36.7575 33.1917C37.2328 32.7155 37.4998 32.0702 37.4998 31.3973C37.4998 30.7245 37.2328 30.0792 36.7575 29.603L31.5775 24.4242C31.4453 24.2919 31.3435 24.1325 31.2791 23.9569C31.2147 23.7814 31.1893 23.5939 31.2047 23.4075C31.22 23.2211 31.2757 23.0404 31.368 22.8777C31.4602 22.715 31.5867 22.5743 31.7387 22.4655L34.4387 20.538C34.6405 20.3939 34.7965 20.1947 34.8878 19.9641C34.9791 19.7336 35.0018 19.4816 34.9534 19.2385C34.9049 18.9953 34.7873 18.7713 34.6146 18.5934C34.442 18.4155 34.2216 18.2912 33.98 18.2355L13.5112 13.5117L18.235 33.9805C18.2907 34.2221 18.415 34.4425 18.5929 34.6151C18.7708 34.7878 18.9948 34.9054 19.238 34.9539C19.4812 35.0023 19.7331 34.9795 19.9637 34.8882C20.1942 34.7969 20.3934 34.641 20.5375 34.4392Z" fill="#FFD98C"></path><path d="M34.0751 37.6413C33.3582 38.3389 32.3973 38.7293 31.397 38.7293C30.3966 38.7293 29.4358 38.3389 28.7189 37.6413L23.4826 32.4663L21.5539 35.165C21.2699 35.5626 20.8773 35.8698 20.423 36.0497C19.9688 36.2295 19.4723 36.2744 18.9931 36.179C18.514 36.0836 18.0726 35.8518 17.7219 35.5117C17.3713 35.1715 17.1263 34.7373 17.0164 34.2613L12.2926 13.7925C12.2447 13.5858 12.2502 13.3702 12.3086 13.1662C12.367 12.9622 12.4764 12.7764 12.6264 12.6263C12.7765 12.4763 12.9623 12.3669 13.1663 12.3085C13.3703 12.2501 13.5859 12.2446 13.7926 12.2925L34.2614 17.0175C34.7374 17.1271 35.1717 17.3719 35.512 17.7225C35.8523 18.073 36.0841 18.5144 36.1795 18.9935C36.275 19.4726 36.23 19.9691 36.0501 20.4233C35.8701 20.8775 35.5628 21.27 35.1651 21.5538L32.4614 23.54L37.6414 28.7188C38.3498 29.43 38.7476 30.393 38.7476 31.3969C38.7476 32.4008 38.3498 33.3637 37.6414 34.075L34.0751 37.6413ZM35.8751 30.4863L30.6951 25.3075C30.4344 25.047 30.2336 24.7328 30.1068 24.3868C29.9799 24.0407 29.9299 23.6712 29.9604 23.3039C29.9908 22.9366 30.101 22.5804 30.2831 22.26C30.4653 21.9396 30.7151 21.6628 31.0151 21.4488L33.6989 19.4488L15.1851 15.1763L19.5001 33.7275L19.5139 33.7113L21.4414 31.0125C21.6555 30.7124 21.9325 30.4626 22.253 30.2805C22.5735 30.0983 22.9298 29.9882 23.2972 29.9577C23.6646 29.9272 24.0342 29.9772 24.3803 30.1041C24.7264 30.231 25.0407 30.4318 25.3014 30.6925L30.4864 35.875C30.728 36.1163 31.0555 36.2518 31.397 36.2518C31.7385 36.2518 32.066 36.1163 32.3076 35.875L35.8751 32.3075C36.1161 32.0657 36.2514 31.7383 36.2514 31.3969C36.2514 31.0555 36.1161 30.728 35.8751 30.4863ZM8.14636 9.385C7.98292 9.38706 7.82069 9.35675 7.66901 9.29583C7.51733 9.2349 7.37921 9.14455 7.26261 9.03L4.58011 6.3475C4.35242 6.11175 4.22643 5.796 4.22927 5.46825C4.23212 5.1405 4.36358 4.82699 4.59534 4.59523C4.8271 4.36347 5.14062 4.23201 5.46836 4.22916C5.79611 4.22631 6.11186 4.3523 6.34761 4.58L9.03012 7.2625C9.20107 7.43787 9.31674 7.65959 9.36277 7.90013C9.4088 8.14068 9.38315 8.38944 9.28901 8.61553C9.19487 8.84162 9.03639 9.03508 8.83325 9.17188C8.63011 9.30867 8.39126 9.38278 8.14636 9.385ZM17.9726 9.03C17.7362 9.26044 17.419 9.3894 17.0889 9.3894C16.7587 9.3894 16.4416 9.26044 16.2051 9.03C15.9708 8.79559 15.8391 8.47771 15.8391 8.14625C15.8391 7.8148 15.9708 7.49691 16.2051 7.2625L18.8876 4.58C19.0029 4.46061 19.1409 4.36538 19.2934 4.29987C19.4459 4.23436 19.6099 4.19988 19.7759 4.19844C19.9418 4.197 20.1064 4.22862 20.2601 4.29147C20.4137 4.35432 20.5532 4.44714 20.6706 4.56451C20.788 4.68187 20.8808 4.82144 20.9436 4.97506C21.0065 5.12868 21.0381 5.29328 21.0367 5.45925C21.0352 5.62523 21.0008 5.78925 20.9352 5.94176C20.8697 6.09426 20.7745 6.23219 20.6551 6.3475L17.9726 9.03ZM6.34761 20.655C6.11146 20.886 5.79423 21.0154 5.46386 21.0154C5.1335 21.0154 4.81627 20.886 4.58011 20.655C4.34578 20.4206 4.21413 20.1027 4.21413 19.7713C4.21413 19.4398 4.34578 19.1219 4.58011 18.8875L7.26261 16.205C7.37792 16.0856 7.51585 15.9904 7.66836 15.9249C7.82086 15.8594 7.98489 15.8249 8.15086 15.8234C8.31684 15.822 8.48144 15.8536 8.63506 15.9165C8.78868 15.9793 8.92824 16.0721 9.04561 16.1895C9.16297 16.3069 9.25579 16.4464 9.31864 16.6001C9.38149 16.7537 9.41312 16.9183 9.41168 17.0843C9.41024 17.2502 9.37575 17.4143 9.31024 17.5668C9.24473 17.7193 9.1495 17.8572 9.03012 17.9725L6.34761 20.655ZM12.6176 7.54375C12.2861 7.54375 11.9682 7.41205 11.7337 7.17763C11.4993 6.94321 11.3676 6.62527 11.3676 6.29375V2.5C11.3676 2.16848 11.4993 1.85054 11.7337 1.61612C11.9682 1.3817 12.2861 1.25 12.6176 1.25C12.9491 1.25 13.2671 1.3817 13.5015 1.61612C13.7359 1.85054 13.8676 2.16848 13.8676 2.5V6.29375C13.8676 6.62527 13.7359 6.94321 13.5015 7.17763C13.2671 7.41205 12.9491 7.54375 12.6176 7.54375ZM2.50011 11.3675H6.29387C6.62539 11.3675 6.94333 11.4992 7.17775 11.7336C7.41217 11.968 7.54387 12.286 7.54387 12.6175C7.54387 12.949 7.41217 13.267 7.17775 13.5014C6.94333 13.7358 6.62539 13.8675 6.29387 13.8675H2.50011C2.16859 13.8675 1.85065 13.7358 1.61623 13.5014C1.38181 13.267 1.25011 12.949 1.25011 12.6175C1.25011 12.286 1.38181 11.968 1.61623 11.7336C1.85065 11.4992 2.16859 11.3675 2.50011 11.3675Z" fill="#272727"></path></svg> <!--'end_frame_cache_Zg1Ab0'--> Идея Диффи-Хеллмана легла в основу протокола обмена ключами, который сегодня используют повсеместно. Проверка банковского счёта, покупки в интернете, защищённые сайты с адресом https, сообщения в мессенджерах — все эти действия опираются на варианты того же принципа. Задача осталась прежней: обе стороны должны получить одно и то же большое случайное число, которое станет секретным ключом .
Чтобы понять логику метода, удобно представить бытовую аналогию. Две стороны заранее договариваются о какой-то базовой единице — например (если рассуждать образно), о рецепте химической смеси, известном всем, включая наблюдателя. Затем каждая сторона добавляет в эту основу свой секретный ингредиент и отправляет результат собеседнику. Получатель снова добавляет свой скрытый компонент к уже полученной формуле. В итоге обе стороны получают одинаковый состав, хотя ни разу не передавали секретные ингредиенты напрямую. Перехватчик видит только промежуточные смеси, но не может точно восстановить рецепт.
Конечно, компьютеры вместо жидкостей используют числа и операции над ними. Участники выбирают общее базовое число и большое простое число. Затем каждый берёт собственное секретное значение и выполняет возведение в степень с последующим вычислением остатка от деления. Результаты передаются по открытому каналу. После этого каждая сторона повторяет операцию, используя полученное число и свой секрет. В обоих случаях получается одинаковый итог — общее число, известное только участникам.
Ключевая деталь здесь — так называемая односторонняя функция. Вычислить результат просто, а восстановить исходные данные по этому результату крайне сложно. В обычной арифметике возведение в степень легко обратить через логарифм. Но в арифметике по модулю, где результат постоянно «заворачивается» по кругу, ситуация меняется. Значения начинают вести себя непредсказуемо. Например, при обычном возведении в степень результат растёт по понятному правилу. В арифметике по модулю те же операции дают последовательность, которая выглядит почти случайной.
Попытка восстановить секретное число по известным параметрам приводит к задаче дискретного логарифма. Для больших чисел, которые используют на практике, задача становится неподъёмной с точки зрения вычислений. Секретные значения могут содержать десятки цифр, а используемые простые числа — сотни. Даже самые быстрые известные алгоритмы потребуют астрономического времени на подбор решения.
При этом строгого доказательства сложности такой задачи до сих пор нет. Современная безопасность интернета держится на предположении, что быстрого способа решения попросту не существует. За десятилетия ни одна спецслужба и ни одна хакерская группа не продемонстрировали рабочий обход, хотя через такие схемы проходят банковские операции и государственные данные на триллионы долларов.
Слабое место у системы всё же есть. В 1994 году математик Питер Шор показал, что квантовый компьютер может решить задачу дискретного логарифма за часы. Алгоритм Шора использует свойства квантовой механики и в теории ломает существующие схемы шифрования. Но проблема упирается в железо: подходящего квантового компьютера пока не существует. Инженеры работают над такими системами, а криптографы параллельно разрабатывают постквантовые алгоритмы. До их массового внедрения обмен ключами по Диффи – Хеллману продолжает защищать большую часть цифровых коммуникаций.
- Источник новости
- www.securitylab.ru
