Золотой ключик

В конце сентября сайт Distributed.net объявил об успешном завершении проекта распределенных вычислений RC5-64 (известного также под названием "Bovine" - "Бык").

Восстановление текстового сообщения, зашифрованного с использованием криптографического алгоритма RC5 с 64-битным ключом, заняло в общей сложности 1757 дней. За это время к проекту подключились 330 тысяч энтузиастов, на чьих компьютерах и шла основная работа: взлом велся методом простого перебора всевозможных кодовых комбинаций. Ключ к раскрытию фразы «The unknown message is: some things are better left unread» («Неизвестное сообщение таково: некоторые вещи лучше оставлять непрочтенными») был сгенерирован компьютером пожелавшего остаться неназванным участника из Японии. Главный вывод, сделанный организаторами проекта: 64-битные ключи уже не годятся для закрытия информации, актуальность которой сохраняется в течение нескольких лет.

Конечно же, не обошлось без накладок. Нужный ключ был сгенерирован еще 14 июля, однако из-за ошибки в серверном программном обеспечении администраторы проекта узнали об этом лишь 12 августа. Еще около месяца ушло на отсылку и проверку ключа в RSA Labs - компанию, владеющую правами на алгоритм RC5, предоставившую зашифрованную фразу и учредившую призовой фонд в 10 тысяч долларов.

По статистике, в самые удачные дни участниками проекта обрабатывалось до 0,12% от всего объема поставленной задачи (комбинационное пространство составляло более 18 квинтиллионов вариантов). Однако из-за того, что на ранних этапах проекта число участников было значительно меньше, нежели к моменту его завершения (когда вычислительная мощность сети RC5-64 оценивалась в 160 тысяч усредненных персоналок на PII 266 МГц), а также из-за возникавших технических проблем, решение задачи заняло почти пять лет. За это время было проверено около 85% всех возможных ключей.

Приз, учрежденный RSA Labs, разделят между участником, чей компьютер сгенерировал искомый ключ (тысяча долларов), его командой (еще одна тысяча), некоммерческой организацией, которую определят общим голосованием (6 тыс. долларов), и сайтом, организовавшим проект (2 тысячи).

Впереди же - новые свершения: в настоящее время программа-клиент уже модифицирована, и ведутся последние настройки серверного ПО, необходимого для запуска RC5-72, в ходе которого планируется взломать уже 72-битный ключ. Точно определить необходимое для этого время пока нельзя, но сделать примерную оценку можно, основываясь на статистике прошлых проектов: взлом 56-битного ключа в свое время потребовал 250 дней, на взлом же в 256 раз более сложного 64-битного ушло всего 1757 дней - что стало результатом как увеличения числа участников, так и роста вычислительной мощности их машин. Таким образом, восхождение на очередную ступень может потребовать лет 30-40.