Max Home IndustryВ презентации на конференции по безопасности Black Hat этого года приводятся веские аргументы в пользу нынешней основы нашей криптосистемы с открытым ключом, срок службы которой составляет около пяти лет. Его основной посыл заключается в том, что мы должны разрабатывать более гибкие криптосистемы.
В настоящее время наши криптографические системы с открытым ключом основаны на одной из двух связанных математических задач — целочисленной факторизации или дискретном логарифме. Эти проблемы используются для создания функций «лазейки», которые трудно отменить, если у вас нет дополнительной информации — закрытого ключа. Вся безопасность криптографии основана на том простом факте, что нет быстрого способа решить любую проблему.
Целочисленную факторизацию легко понять: если у вас есть значение d, которое является произведением двух больших простых чисел, p и q, то поиск простого деления занимает много времени. Однако, если я дам вам одно из простых чисел, найти другое будет очень быстро.
Задача дискретного логарифмирования немного сложнее для понимания, но в простейшем случае она сводится к «найти x так, чтобы h = gx при заданных h и g».
В настоящее время как целочисленная факторизация, так и дискретный логарифм не имеют алгоритмических решений с полиномиальным временем. Причина, по которой важно, чтобы решение не было полиномиальным по времени, заключается в том, что если кто-то изобретает более быстрый компьютер или алгоритм, то, пока он не полиномиальный, вы можете вывести свою проблему за пределы ее досягаемости, увеличив размер проблемы — т.е. увеличение количества бит в простых числах или ключах.
Долгое время предполагалось, что если любая проблема будет решена путем создания алгоритма полиномиального времени, это будет внезапным и, возможно, в основном секретным делом. Какой-нибудь правительственный криптограф внезапно докажет глубокий результат, который позволит читать весь зашифрованный трафик, или квантовый компьютер будет построен секретно и с огромной стоимостью, и весь код снова станет читаемым. В любом случае это не окажет большого влияния на коммерческую криптосистему — до тех пор, пока новости не просочатся.
Однако теперь в презентации iSECpartners под названием «Факторинг мертвых — подготовка к криптопокалипсису» предлагается, что падение может произойти в виде медленных и устойчивых публичных шагов в направлении улучшения алгоритмов, разработанных рядом исследователей со всего мира. Новые алгоритмы могут быть даже не полиномиальными, просто достаточно быстрыми, чтобы увеличить размер ключа до чего-то неприемлемого. Тревожные исследования направлены на решение проблемы дискретного логарифмирования, но, как уже упоминалось, проблема целочисленной факторизации связана с ней. За последние шесть месяцев были созданы новые алгоритмы, которые работают за полиномиальное время для решения ограниченных типов задач. Если ограничения могут быть сняты, то криптография, основанная на проблеме дискретного логарифмирования, такая как Диффи-Хеллмана, DSA и Эль-Гамаля, больше не будет полезна. Если алгоритм можно адаптировать к целочисленной факторизации, то RSA тоже падает.
Далее в презентации указывается, что существует долгосрочная альтернатива использованию шифрования, основанная на целочисленной факторизации или проблеме дискретного логарифмирования — криптография на основе эллиптических кривых (ECC).
Эллиптическая кривая — это многочлен типа y2 = x3 + ax + b, а набор точек, удовлетворяющих уравнению, образует группу при операции, которая ведет себя как сложение. Основа ECC заключается в том, что вам даны две точки P и Q на кривой, и вы должны найти целое число n такое, что Q = nP (где nP означает прибавление P к самому себе n раз). Это проблема, которая требует экспоненциального времени и является основой функции люка.
ECC — более сложная проблема, чем факторинг, и дискретный логарифм и размер ключа могут быть меньше. Также маловероятно, что на него повлияют какие-либо прорывы в решении задач дискретного логарифмирования, поэтому это идеальная альтернатива. К сожалению, имеющаяся у нас криптографическая система недостаточно гибкая, чтобы вместить гораздо большие ключи, не говоря уже о новой форме шифрования. Также существует небольшая проблема, заключающаяся в том, что Blackberry владеет важными патентами на технологию и обеспечивает соблюдение своих прав. Это привело к медленному освоению технологии.
Презентация обращает внимание не на то, что наша текущая криптосистема была взломана, а на то, что в противном случае было бы сложно отреагировать на любые изменения и продолжить работу. Задача состоит в том, чтобы сделать структуру более способной изменять и использовать различные размеры ключей и криптографические принципы. Следующим шагом может быть ECC, но со временем его тоже нужно будет заменить.