Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

Опции
К последнему сообщению К первому непрочитанному
Offline OlegCh  
#1 Оставлено : 17 мая 2015 г. 21:46:06(UTC)
OlegCh


Статус: Интересующийся

Группы: Member
Зарегистрирован: 16.03.2009(UTC)
Сообщений: 32
Мужчина
Откуда: Москва

Хотел найти проект по факторизации RSA чисел (RSA challenge), но что-то не нашел. Факторизацией занимается NFS@Home, но какие они там числа факторизуют, не ясно. С RSA числами было бы интереснее...
Опыт - это то, что мы получаем вместо того, что хотели...
Offline AlexA  
#2 Оставлено : 17 мая 2015 г. 21:53:24(UTC)
AlexA


Статус: Administration

Медали: Переводчику: За помощь в создании сайта

Группы: Editors, Member, Administration, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 6,140
Мужчина
Российская Федерация
Откуда: "Russia Team"

Сказал «Спасибо»: 1250 раз
Поблагодарили: 1516 раз в 838 постах
Автор: OlegCh Перейти к цитате
Хотел найти проект по факторизации RSA чисел (RSA challenge), но что-то не нашел. Факторизацией занимается NFS@Home, но какие они там числа факторизуют, не ясно. С RSA числами было бы интереснее...

Для малопосвященных (типа меня) был бы интересен небольшой "ликбез" насчет факторизации и почему "С RSA числами было бы интереснее"
Offline hoarfrost  
#3 Оставлено : 18 мая 2015 г. 9:24:49(UTC)
hoarfrost


Статус: Старожил

Медали: Переводчику: За помощь в создании сайтаРазработчику: За разработку приложения CluBORunДонор: За финансовую помощь сайту

Группы: Editors, Member, Administration, Moderator Crystal Dream, Moderators, Crystal Dream Group
Зарегистрирован: 05.10.2007(UTC)
Сообщений: 8,419
Мужчина
Откуда: Crystal Dream

Сказал «Спасибо»: 1255 раз
Поблагодарили: 1698 раз в 1079 постах
Это старый-престарый ещё "до-BOINC-овский" distributed.net.
UserPostedImage
Offline OlegCh  
#4 Оставлено : 18 мая 2015 г. 11:46:35(UTC)
OlegCh


Статус: Интересующийся

Группы: Member
Зарегистрирован: 16.03.2009(UTC)
Сообщений: 32
Мужчина
Откуда: Москва

Автор: AlexA Перейти к цитате

Для малопосвященных (типа меня) был бы интересен небольшой "ликбез" насчет факторизации и почему "С RSA числами было бы интереснее"


Ну, не претендуя на "просвещенность" в этом вопросе (наткнулся на это, в общем-то, случайно), в двух словах:
Что такое факторизация, думаю, все знают - это просто разложение числа на простые множители. Для небольших чисел это не представляет проблем. Проблемы начинаются для чисел с числом цифр от 100 и больше. До сих пор нет эффективного алгоритма нахождения простых сомножителей для таких больших чисел, даже если известно, что число получено перемножением всего двух простых чисел. Для чего это вообще нужно? Это основа современных методов кодирования информации, так называемого RSA шифрования. Есть такая лаборатория RSA laboratory (по первым буквам трех ее основателей), которая запатентовала метод шифрования информации, основанный в двух словах на том, что передающая информацию сторона шифрует свою информацию путем "возведения ее в степень е по модулю n", где n - некоторое большое число, полученное перемножением двух больших простых чисел (это число n формируется принимающей стороной, так же как и степень е, в которую будет происходить возведение, и передается отправляющей стороне по любому открытому каналу перед тем как отправляющая сторона начнет шифровать свое сообщение (пара (n,e) называется "открытым ключом" ). Проделав эту операцию, передающая сторона отправляет результат возведения в степень по модулю n принимающей стороне, где она проделывает обратную операцию и получает исходное сообщение. Фишка состоит в том, что эта обратная операция использует простые множители, из которых состоит n и представляет собой колоссальную трудность, если эти простые множители неизвестны. Поэтому главная задача перехвата информации заключается в получении открытого ключа (что несложно, так как он и передаётся практически открыто) и факторизации числа n, что как раз и представляет основную проблему.
Ну так вот. Нам-то, собственно, всё это не очень интересно, а интересно следующее. Когда эта лаборатория RSA образовалась и всё это придумала (ну, придумала, конечно, не она, а головастые товарищи ещё до неё, она это только всё реализовала для практического применения), она решила устроить такой типа открытый конкурс. Взяв два больших простых числа они их перемножили и получили число, состоящее из 129 цифр, при помощи которого зашифровали короткую фразу и под авторством Мартина Гарднера в августе 1977 году в журнале Scientific American предложили эту фразу расшифровать. То есть фактически надо было просто найти два исходных простых числа (само 129-значное число было приведено). За расшифровку полагался приз - 100 долларов. Если верить легенде, то эта задача была решена лишь в апреле 1994 года путем использования распределенных вычислений силами 1600 компьютеров, принадлежащих 600 волонтерам, которые в течение полугода пересылали свои промежуточные вычисления по электронной почте и даже, страшно сказать, по факсу группе организаторов этого мероприятия - Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul Leyland, которые все это обрабатывали и финализировали. Для нахождения этих двух простых чисел решалась система линейных уравнений с полумиллионом неизвестных. Как заявлял в 1977 году один из основателей RSA Ривест, для факторизации числа потребуется более 40 квадриллионов лет. Однако ж уже в 1994 году справились за полгода. Чего только за 100 долларов не сделаешь!
В марте 1991 года RSA, не дождавшись (пока ещё) факторизации 129-разрядного числа, запустила новый большой конкурс, получивший название RSA challenge. Были представлены для факторизации всем желающим 42 числа с числом цифр от 100 до 500 с шагом в 10 цифр и с призовым фондом от 1000 до 200000 долларов. Каждое число состояло из произведения двух простых. После генерации этих чисел на компьютере, изолированном от внешних сетей, его жесткий диск был уничтожен.
Первое из этих чисел (100-разрядное) было факторизовано меньше чем за месяц, к 1 апреля 1991 г., за что Arjen K. Lenstra и получил свои честно заработанные 1000 баксов. К сентябрю 2013 было факторизовано... там-парабам-пам-пам!... 18 чисел! (из 54 на самом деле - к изначальным 42 потом добавили еще несколько). Максимально длинное факторизованное число состояло из 232 разрядов (декабрь 2009 года) и принесло лауреату 50000 долларов. Интересно, что в 2010 году и наши ребята из МГУ засветились, факторизовав числа длиной 180 и 190 разрядов (но денег это им, похоже, не принесло )).

Ну вот, собственно, из-за этой длинной истории мне и кажется, что факторизовать RSA числа было бы интереснее, хотя сама RSA, по некоторым данным, в 2007 году лавочку закрыла (я думаю, из-за жадности, выплатив в 2005 году обещанные 20000 баксов).

Источники:
О проекте RSA challenge: http://en.wikipedia.org/.../RSA_Factoring_Challenge
Сами RSA числа: http://en.wikipedia.org/wiki/RSA_numbers#RSA-129
Опыт - это то, что мы получаем вместо того, что хотели...
Offline Disel  
#5 Оставлено : 18 мая 2015 г. 15:31:56(UTC)
Disel


Статус: Старожил

Медали: Первооткрывателю: Нахождение пар ОДЛК в RakeSearch! Донор: За финансовую помощь сайту

Группы: Member, Russia Team Group
Зарегистрирован: 08.07.2013(UTC)
Сообщений: 3,603
Мужчина
Российская Федерация

Сказал «Спасибо»: 520 раз
Поблагодарили: 427 раз в 327 постах
Интересен не только RSA, но и другие аналогичные алгоритмы. На самом деле, на мой взгляд, больший интерес представляют исследования в области поиска методов "быстрого взлома" (или постепенного приближения к таким методам). Нет аксиомы или доказательства, что такого метода не существует. Возможно этим отчасти занимается NFS, но точно не знаю, нужно читать на их сайте. Успехи в факторизации чисел с увеличением их длины на какую-то небольшую величину лишь показывает возможности растущих вычислительных мощностей, но не приводят к прорыву. Достаточно существенно увеличить размер ключа шифрования, что совсем не сложно, и все самые крутые современные супер-ЭВМ становятся бесполезны, ведь зависимость сложности от длины ключа нелинейна. Например, если говорить о симметричных алгоритмах, увеличение длины ключа со 128 до 256 бит приводит к усложнению задачи не в 2 раза, а в 2^(256-128)=2^128 раз. Хотя с другой стороны вышеназванные конкурсы то же полезны, поскольку способствуют обсуждению вопроса и попыткам поиска решений в "широким массах" специалистов.
Ubuntu Linux 18.04 LTS - 64 bit / Boinc 7.9.3(х64) / Core 2 DUO E6300 1.8 Ггц / GeForce GT-630
Пользователи, просматривающие эту тему
Guest
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2018, Yet Another Forum.NET
Страница сгенерирована за 0.117 секунды.