Здравствуйте всем!
Видел статью о изменении прошивки процессоров Pentium. Хотел бы уточнить у того, кто знает: возможно ли ее хотя бы теоретически изменить, наваяв пару собственных команд вместо имеющихся (вопрос скорее конкретный, чем эмпирический - если это возможно, интересно, удастся ли туда впихнуть операцию модулярной экспоненциации, т.е возведения в степень по модулю?). В принципе, если такое возможно (пусть даже до ближайшей перезагрузки), можно существенно ускорить известные ранее реализации алгоритмов целочисленной факторизации (основная операция - модулярное возведение в степень и проверка на точный квадрат). Ron Rivest, создатель RSA заявил, что за $1000000 и год времени он может создать чип для целочисленной факторизации, сделанный по технологии 0.13 микрон и работающий на тактовой частоте 1ГГц. Если применить это к Pentium и предположить, что такого рода модификация возможна, можно за существенно меньшие деньги сделать более быстрый процессор с более широкими возможностями. По его (Rivest'a) заявлениям, его чип может факторизовать модуль RSA 512 бит за несколько минут, а на RSA 1024 уйдет около года. Но, если с помощью модифицированного процессора можно будет факторизовать за приемлемое время модуль RSA в 640 бит, за него в RSA Labs платят $20000 (http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html# RSA640). Да, и в самой криптографии его можно будет применять с бОльшим успехом, чем любые, существующие сейчас реализации (как программные, так и на отдельных чипах).
Есть у кого-нибудь идеи?
PS Алгоритмов для реализации мод. возведения в степень масса, памяти они много не требуют.

Ищи по форуму. Тема уже поднималась.

ECk: по-моему задача не особо реальная в наше время . У меня как-то была тоже конкретная задача - сломать RSA 2048. Пообщавшись с специалистами по криптографии, максимум что я мог предложить - распараллеливание вычислений на 3 миллиона компьютеров. Но время все равно было нереальное. А использование микрокода процессора не позволит повысить производительность в 3 миллиона раз.

С процессором выйдет лучше, т.к если это внутри процессора, скорость вычислений будет отталкиваться от тактовой частоты процессора, а не от частоты шины и частоты памяти. В принципе, если возведение в степень по модулю выполнимо за ln(N) битовых операций, оптимизация должна быть более чем нормальная. В настоящее время, используя GMP 4.12 за секунду удается сделать не более 10000 возведений в степень 640-битного числа, т.е. 10000*(~640)=~6400000 битовых операций такого рода. Потом, объединять для распределенных вычислений сети - не выход, т.к (естественно, для факторизации через тривиальное деление, понадобится огромные затраты MIPS, но существуют другие алгоритмы - быстрее GNFS, MPQS и SIQS). Для их реализации и предполагается использовать процессор. К тому же, даже объединение в сеть 3 миллионов компьютеров не помогло бы, т.к. практически в любом современном алгоритме (решето числового поля, квадратичное решето) с помощью сети из огромного числа компьютеров проверяются всевозможные зависимости, конгруэнтные единице (GNFS) или точному квадрату (SIQS, MPQS). Но этого недостаточно - после получения достаточного числа зависимостей получают матрицу, которую решают с помощью метода исключений Гаусса. Но такие вычисления для RSA 512 бит заняли 32 Гб памяти и недели работы суперкомпьютера Cray. С увеличением числа бит на один, размер памяти для решения матрицы вырастает вдвое.
Но есть другие алгоритмы, не требующие решения матричных уравнений. Для них и предполагается использовать процессор.

ECk
[ за секунду удается сделать не более 10000 возведений в степень 640-битного числа,
т.е. 10000*(~640)=~6400000 битовых операций такого рода. ]

А что, "возведение в степень" это однобитовая операция ?
И еще ты так и не сказал, для какого алгоритма факторизации
тебе нужна модулярная экспоненциация... ;)

К тому же, даже объединение в сеть 3 миллионов компьютеров не помогло бы, т.к. практически в любом современном алгоритме

Я вообще привел грубое сравнение с увеличением производительности. Т.к. можно разработать алгоритм, который позволяет достаточно быстро работать на распределенной системе. НО. Если у тебя время вычисления ключа 10^9 лет, то разделив на 3*10^5 (т.е. распараллелив на 3 миллиона компов), мы получаем 333 года на вычисления. Это тоже неприемлемо. Согласен? И опять, же повторюсь - что бы ты не делал, какой-бы микрокод не писал - ты _НЕ_ПОЛУЧИШЬ_ такой прирост производительности на простом процессоре, как при использовании распределенной системы.
Кстати - application кластера не просто так активно используют согласен?.

ECk: а вообще - стукнись в аську, поговорим о том-о сем.