РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

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

Атака на шифр была основа не на мощной машине, а на мощной математике

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

От Диофанта до SIKE

Эрнст Кани занимается математическими исследованиями с конца 1970-х годов. Он начал в Гейдельбергском университете в Германии, а затем в 1986 году перешел в Королевский университет (Queen's University at Kingston). 

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

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

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

Пончики и эллиптические кривые

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

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

РЕКЛАМА – ПРОДОЛЖЕНИЕ НИЖЕ

«Наша задача не имела ничего общего с криптографией, поэтому я был удивлен, когда услышал об атаке на алгоритм. Это было почти гениально!», — говорит доктор Кани. 

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

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

Загрузка статьи...