История о том, как шифр, выбранный правительством США, взломали за один час: а все благодаря математической теореме!
Атака на шифр была основана не на мощной машине, а на мощной математике
В цифровую эпоху защита данных от хакерских атак является одной из самых больших проблем, над решением которой работают эксперты, правительства и отрасли во всем мире.
Национальный институт стандартов и технологий США (NIST) выбрал четыре алгоритма шифрования и и предложил вознаграждение в размере 50 000 долларов тому, кто сумеет их взломать. К всеобщему удивлению оказалось, что один из самых надежных (так думали разработчики) алгоритмов, получивший название SIKE, можно взломать всего за час работы одного персонального компьютера. Атака основывалась не на мощной машине, а на мощной математике, — на теореме, доказанной четверть века назад.
От Диофанта до SIKE
Эрнст Кани занимается математическими исследованиями с конца 1970-х годов. Он начал в Гейдельбергском университете в Германии, а затем в 1986 году перешел в Королевский университет (Queen's University at Kingston).
Проблемы, над решением которых работает доктор Кани, восходят к идеям Диофанта Александрийского. Он около 1800 лет назад заниматься классом неопределенных уравнений, которые в его честь стали называться диофантовыми. Одним из самых известных диофантовых уравнений является Великая теорема Ферма, поставленная Пьером Ферма в 1637 году. На ее доказательство математическому сообществу потребовалось 350 лет (Ее доказал Эндрю Уайлс в 1994 году).
Ни Диофант, ни Ферма, конечно, не думали о шифрах или о квантовых компьютерах, но работа доктора Кани над диофантовыми уравнениями очень помогла во время испытаний, проводимых NIST. Программисты Воутер Кастрик и Томас Декру из Католического университета Лёвена в Бельгии оказались достаточно компетентными математиками и основывали программу взлома на теореме доктора Кани.
Эту работу он начал в 1980-х годах в сотрудничестве с другим немецким математиком Герхардом Фреем, чья другая работа сыграла решающую роль в доказательстве Великой теоремы Ферма. Именно работа Фрея показала путь, по которому до конца прошел Эндрю Уайлс. Кани и Фрей занимались исследованиями эллиптических кривых, задаваемых особым видом уравнений, которые позднее стали использоваться в криптографии.
Цели исследователей были чисто теоретическими. «Занятия чистой математикой — это самоцель, поэтому мы не думаем о реальных приложениях», — объясняет доктор Кани. — «Но многие из этих исследований могут пригодиться для прикладных целей. Когда Ферма предложил свою теорему сотни лет назад, его цели тоже были чисто теоретическими. Приложение к криптографии появилось гораздо позже, в 1978 году. Все методы, которые мы используем сегодня для шифрования данных, основаны на математике».
Пончики и эллиптические кривые
Представьте себе объект в форме пончика (математики называют его тором): это визуальная модель эллиптической кривой первого рода. Кани и Фрей хотели объединить две кривые первого рода, чтобы получить новый объект — кривую второго рода, что-то, что мы можем представить себе как два пончика, плотно склеенных бок о бок. Математики стремились использовать некоторые свойства кривой второго рода, чтобы вывести определенные свойства двух исходных кривых первого рода.
В своей статье 1997 года доктор Кани обобщил первоначальную конструкцию, соединив вместе произвольную пару эллиптических кривых. Но в этом случае конструкция иногда «раскалывается», и два пончика не склеиваются, а только касаются друг друга. В своей статье Кани анализирует точные условия, когда это происходит. Кастрик и Декру спустя 25 лет использовали этот особый случай при атаке на схему шифрования SIKE.
«Наша задача не имела ничего общего с криптографией, поэтому я был удивлен, когда услышал об атаке на алгоритм. Это было почти гениально!», — говорит доктор Кани.
К сожалению, профессиональные криптографы и программисты не всегда хорошо разбираются в мощных методах чистой математики, а она может предложить множество методов шифрования, хранения и передачи данных.
«Криптография использует много сложной математики. Специалисты по информатике и чистые математики должны работать вместе, чтобы продвигать эту область», — говорит доктор Кани.