9500 компьютеров, работая вместе в течение четырех месяцев, проверяли новый метод шифрования

Объем вычислений, проделанных нами, больше, чем нужно для взлома системы, защищенной открытым ключом наподобие RSA длиной как минимум 600 разрядов.
Эрьен Ленстра, вице-президент по технологиям подразделения Citibank в Нью-Йорке

Беспрецедентные усилия, затраченные на взлом кода, продемонстрировали достоинства этой системы шифрования, но при этом подчеркнули и ее потенциальные недостатки.

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

Ирландский математик Роберт Харли и трое его коллег из INRIA, в том числе и Рауглаудре, использовав 9500 компьютеров в Internet, сумели реконструировать 109-разрядный ключ, применявшийся для шифрования тестового сообщения. Сообщение было закодировано с помощью метода эллиптической кривой (ECC — elliptic-curve cryptography), принцип которого состоит в том, чтобы вычислить несколько точек на кривой, и эта информация используется для генерации ключа, защищающего данные.

Размер имеет значение

Метод ECC может применяться для защиты мобильных устройств, процессор в которых менее мощный, чем у ПК, поскольку этот алгоритм требует меньших вычислительных ресурсов для кодирования и декодирования данных.

Многие производители программного обеспечения в своих системах защиты используют 1024-разрядный ключ RSA. Однако Рохит Харе, возглавляющий группу 4K Associates, занимающуюся исследованиями, связанными с защитой, отметил, что ключи ECC могут быть созданы в 100 раз быстрее и занимают гораздо меньше места, чем ключи RSA. Он добавил, что ключи ECC, применяемые в цифровых сертификатах для сотовых телефонов, могут позволить использовать эти устройства как защищенные цифровые бумажники, содержащие информацию о кредитных карточках.

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

Исследование, посвященное анализу 109-разрядного ключа, было инициировано канадской компанией Certicom, занимающейся вопросами шифрования, которая хотела привлечь исследователей к тестированию уровня защиты, обеспечиваемого алгоритмом ECC. Эта задача, получившая известность под кодовым наименованием ECC2K.108, была решена с помощью распределенной сети, включающей большое число компьютеров. Тестирование было завершено 4 апреля. В нем приняли участие 1300 человек из 40 стран, перебиравшие всевозможные комбинации ключей до тех пор, пока не был обнаружен искомый. По данным INRIA, две трети вычислений пришлось на долю рабочих станций с операционной системой Unix, а одна треть — на ПК с Windows. На решение такой задачи на одном ПК с процессором Pentium II/450 МГц потребовалось бы примерно 500 лет.

В своем проекте Certicom использовала свободно распространяемое программное обеспечение, которое Харли разработал для вычисления более 215 точек на эллиптической кривой, относящейся к классу кривых Коблитца. Данные о 2 млн. «выделенных» точек были посланы на сервер AlphaServer в INRIA, где участники могли в реальном времени наблюдать за поиском ключа.

«Объем вычислений, проделанных нами, больше, чем нужно для взлома системы, защищенной открытым ключом наподобие RSA длиной как минимум 600 разрядов», — отметил Эрьен Ленстра, вице-президент по технологиям подразделения Citibank в Нью-Йорке, который также принимал участие в проекте.

Достоинства и недостатки ECC

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

«Это свидетельствует об опасности использования некоторых конкретных видов кривых и о необходимости выбирать произвольную кривую без особых характеристик», — отметил Харли.

Ленстра указывает, что RSA все же превосходит ECC, поскольку ключи RSA намного проще генерировать, и такие компании, как Certicom, не хотят делиться информацией о своих кривых: «Многие математики по-прежнему обеспокоены уровнем защиты при шифровании по эллиптической кривой».

Несмотря на эти опасения, мало кто сомневается в достоинствах ECC. Харе подчеркнул, что ECC включен в семейство стандартов Wireless Application Protocol в качестве основы протокола Wireless Transport Layer Security, оптимизированной версии Secure Sockets Layer. Кроме того, он обратил внимание на то, что разработчики ПО для беспроводной связи, такие как компания Phone.com, уже поставляют инструментарий ECC производителям карманных устройств и что их развертывание зависит лишь от заинтересованности операторов.