Using volunteer computation to solve cryptographic problems.pdf Добровольные вычисления - это распределённые вычисления, в которых исполь-зуются вычислительные ресурсы, предоставляемые т. н. «добровольцами» (волонтё-рами). В роли добровольцев обычно выступают частные лица, располагающие соб-ственными персональными компьютерами (ПК), ресурсы которых они предоставляютдля решения разнообразных научных задач. Компьютеры добровольцев (вообще го-воря, находящиеся в географически удалённых друг от друга точках) объединяютсяв грид под управлением некоторой среды. Такие грид-системы создаются под конкрет-ные задачи, на решение которых могут уходить месяцы и даже годы, и называютсяпроектами добровольных вычислений.Сегодня функционируют более 70 проектов добровольных вычислений, в ко-торых решаются задачи поиска новых космических объектов (Einstein@home,Milkyway@home), новых лекарств от пока неизлечимых болезней (World CommunityGrid, Rosetta@home), а также задачи из многих других областей. Несколько проек-тов направлены на решение криптографических задач. Исторически первым крипто-графическим проектом стал distributed.net, запущенный в 1997 г. С тех пор в данномпроекте решены несколько задач криптоанализа различных модификаций шифра RC5с использованием метода «грубой силы». В настоящий момент в distributed.net ре-шается задача криптоанализа шифра RC5 с 72-битным секретным ключом. ПроектDistrRTgen, запущенный в 2008 г., направлен на построение rainbow-таблиц, предна-значенных для криптоанализа хэш-функций. В DistrRTgen разработана версия расчёт-ного приложения для видеокарт, благодаря чему производительность проекта достигла1,2 пентафлопс.В 2007 г. запущен проект Enigma@home, направленный на криптоанализ трёх сооб-щений, закодированных криптографической машиной Энигма и перехваченных в се-верной Атлантике в 1942 г. Криптоанализ двух сообщений был успешно осуществлёнв первые несколько месяцев работы проекта, и с тех пор решается задача криптоана-лиза третьего сообщения, которое было принято с помехами. При разработке подавля-ющего большинства действующих проектов добровольных вычислений использованапрограммная платформа BOINC [1], прототипом которой стали технологии, приме-нённые при создании одного из самых крупных проектов добровольных вычисленийSETI@home. Эта платформа стала свободно распространяться в 2004 г. Из всех пере-численных проектов только distributed.net не использует платформу BOINC.В докладе представлено описание проекта добровольных вычислений SAT@home [2],созданного ИДСТУ СО РАН и ИСА РАН и предназначенного для распределённого ре-шения задачи о булевой выполнимости (SAT). Проект был запущен 29 сентября 2011 г.При его создании была использована платформа BOINC [1] и библиотека DC-API [3].Распределённое приложение проекта состоит из управляющей и расчётной частей.Управляющая часть отвечает за создание заданий в базе данных проекта, а также заобработку результатов выполнения заданий, присылаемых с ПК участников. Отправ-кой заданий на ПК участников и получением результатов занимаются стандартные1 Работа выполнена при поддержке РФФИ (гранты № 11-07-00377-a и № 10-07-00301-a) и СедьмойРамочной программы Европейского Союза (FP7/2007-2013), грант №261561 (DEGISCO).службы BOINC. Основу расчётной части составляют SAT-решатели minisat-1.14.1 иminisat-2.0, модифицированные с учётом особенностей КНФ, кодирующих задачи об-ращения дискретных функций [4]. Исполняемые файлы расчётной части взаимодей-ствуют с BOINC-клиентом при помощи функций библиотеки DC-API, что позволяет,в частности, реализовать периодическое сохранение промежуточных данных вычис-лений в виде контрольных точек. На момент написания данной работы в проектеSAT@home принимает участие более тысячи активных добровольцев и задействованоболее двух тысяч активно работающих ПК. Средняя производительность проекта завесь период работы составляет 1,7 терафлопс.В декабре 2011 г. в SAT@home был запущен эксперимент по решению задачи крип-тоанализа генератора ключевого потока A5/1. На сегодняшний день наиболее эф-фективным методом криптонализа данного генератора является «rainbow-метод» [5].Однако доступные rainbow-таблицы [5] покрывают ключевое пространство примернона 88% (при «реалистичных» ограничениях на условия криптоанализа). Нами бы-ли сгенерированы 10 тестов, не поддающихся криптоанализу с использованием этихrainbow-таблиц. На момент написания данной работы в проекте SAT@home успеш-но решены 9 из них (в среднем на решение каждого теста уходило 2 недели работыпроекта).

Скачать электронную версию публикации