Математическая теорема, используемая для взлома алгоритма шифрования правительства США

Прочитано: 107 раз(а)


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

В июле Национальный институт стандартов и технологий США (NIST) выбрал четыре алгоритма шифрования и поставил несколько сложных задач для проверки их безопасности, предложив вознаграждение в размере 50 000 долларов тому, кто сумеет их взломать. Это произошло менее чем за час: один из многообещающих кандидатов на алгоритм по имени SIKE был взломан с помощью одного персонального компьютера. Атака основывалась не на мощной машине, а на мощной математике, основанной на теореме, разработанной Королевским профессором несколько десятилетий назад.

Эрнст Кани занимается исследованиями и преподает с конца 1970-х годов — сначала в Гейдельбергском университете в Германии, а затем в Королевском университете, где в 1986 году он поступил на факультет математики и статистики. математика, использующая методы алгебраической геометрии для решения задач теории чисел.

Проблемы, над решением которых работает доктор Кани, восходят к древним временам. Его конкретная область исследований была начата Диофантом Александрийским около 1800 лет назад и представляет собой набор проблем, известных как диофантовы вопросы. Одним из самых известных вопросов в этой области является Великая теорема Ферма , поставленная Пьером Ферма в 1637 году и на доказательство которой математическому сообществу потребовалось 350 лет — достижение профессора Принстона Эндрю Уайлса в 1994 году. Уайлз получил множество призов и наград за эту работу. , включая звание почетного доктора Королевы в 1997 году.

Ни Диофант, ни Ферма не мечтали о квантовых компьютерах, но работа доктора Кани над диофантовыми вопросами всплыла на поверхность во время раунда испытаний NIST. Успешные хакеры — Воутер Кастрик и Томас Декру, оба исследователи из Католического университета Лёвена в Бельгии — основывали свою работу на теореме «склеить и разделить», разработанной королевским математиком в 1997 году.

На самом деле доктор Кани не беспокоился о криптографических алгоритмах, когда разрабатывал теорему. Эта работа началась в 1980-х годах в сотрудничестве с другим немецким математиком Герхардом Фреем, чья работа сыграла решающую роль в решении последней теоремы Ферма. доктора Кани и Фрей хотели продвинуть исследования эллиптических кривых, особого вида уравнений, которые позже будут использоваться в криптографических целях.

Цели обоих исследователей в то время были чисто теоретическими. Им было интересно манипулировать математическими объектами , чтобы узнать больше об их собственных свойствах. «Занятия чистой математикой — это самоцель, поэтому мы не думаем о реальных приложениях», — объясняет доктор Кани. «Но позже многие из этих исследований пригодятся для разных целей. Когда Ферма предложил свою теорему сотни лет назад, его намерением было получить возможность разлагать на множители определенные большие числа. Приложение к криптографии появилось гораздо позже, в 1978 году. все методы, которые мы используем сегодня для шифрования данных, основаны на математике».

Пончики и кривые

Математики часто называют математику прекрасной вещью. Для тех, кто не работает в полевых условиях, может быть сложно увидеть эту красоту или даже понять на высоком уровне, что представляют собой эти исследовательские проекты — это требует некоторого воображения.

Представьте себе объект в форме пончика с дыркой посередине: это визуальная модель эллиптической кривой , также известной как кривая рода один. доктора Кани и Фрей хотели объединить две кривые рода один, чтобы сформировать новый объект — кривую рода два, что-то, что мы можем представить себе как два пончика, плотно склеенных бок о бок. Они стремились использовать некоторые свойства построенной кривой рода два, чтобы вывести определенные свойства двух исходных кривых рода один, которые были «склеены» вместе.

В своей статье 1997 года д-р Кани обобщил первоначальную конструкцию, соединив вместе произвольную пару эллиптических кривых. Но в этом случае конструкция иногда терпит неудачу — она может построить объект, в котором два пончика касаются друг друга только в одной точке. В статье анализируются точные условия, когда это происходит (т. е. когда конструкция выходит из строя или «раскалывается»). Кастрик и Декру использовали эту характеристику отказа в своем методе атаки на предложенную схему шифрования SIKE.

«Наша проблема не имела ничего общего с криптографией, поэтому я был удивлен, когда услышал об атаке на алгоритм. Это было довольно гениально, то, что они там сделали!» говорит доктор Кани. «Один из соавторов алгоритма SIKE выразил удивление по поводу того, что кривые рода два можно использовать для получения информации об эллиптических кривых. Но именно это и было нашей первоначальной стратегией в 1980-х и 1990-х (и впоследствии)».

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

«Криптография использует много сложной математики, особенно арифметическую геометрию. Специалисты по информатике и математики должны работать вместе, чтобы продвигать эту область», — говорит д-р Кани, который продолжает преподавать на курсах бакалавриата и магистратуры и работать в области арифметической геометрии, особенно в задачи, связанные с кривыми рода два и эллиптическими кривыми.

Математическая теорема, используемая для взлома алгоритма шифрования правительства США



Новости партнеров