Стандарты безопасности применяющие RSA

ОБЗОР МЕТОДОВ ВСКРЫТИЯ КРИПТОСИСТЕМЫ RSA

Курсовой проект

                                                     по дисциплине «Компьютерная безопасность»

студента 2 курса

                                                             специальности «Комп. безопасность»

дневной формы обучения

группы 427

Ивацевича Владимира Анатольевича

Научный руководитель:

                                                    старший преподаватель кафедры информатики

Малашук Сергея Фёдоровича

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Криптосистема RSA предложена Ривестом (R. Rivest), Шамиром (A. Shamir), Адлеманом (L. Adleman) в 1977 г. Предназначена как для цифровой подписи, так и для шифрования. Данная криптосистема используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании THALES (Racal). Кроме того,  криптосистема RSA широко применяется в составе  различных стандартов и протоколов Internet, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

ГЛАВА 1 ОБЩИЕ СВЕДЕНИЯ КРИПТОСИСТЕМЫ RSA

1.1 Стандарты безопасности применяющие RSA

Криптосистема RSA – часть многих стандартов. Стандарт ISO 9796 описывает RSA как совместимый криптографический алгоритм, соответствующий стандарту безопасности ITU-T X.509. Кроме этого криптосистема RSA является частью стандартов SWIFT, ANSI X9.31 rDSA и проекта стандарта X9.44 для американских банков. Австралийский стандарт управления ключами AS2805.6.5.3 также включает систему RSA.

Алгоритм RSA используется в Internet, в частности он входит в такие протоколы как S/MIME, IPSEC (Internet Protocol Security) и TLS (которым предполагается заменить SSL), а также в стандарт PKCS, применяемый в важных приложениях. 

Для разработчиков приложений с применением PKCS организация OSI Implementers Workshop (OIW) выпустила соглашение, которое в частности посвящено алгоритму RSA.

Множество других разрабатываемых в настоящее время стандартов включают в себя либо сам алгоритм RSA или его поддержку либо рекомендуют криптосистему RSA для обеспечения секретности и/или установления подлинности (аутентификации). Например, включают в себя систему RSA рекомендации IEEE P1363 и WAP WTLS.

Технологию шифрования RSA BSAFE используют около 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире и это количество имеет явную тенденцию к увеличению по мере роста Internet.

1.2 Описание криптосистемы

RSA многие годы противостоит  интенсивному криптоанализу. Криптостойкость основана на трудоемкости разложения на множители (факторизации) больших чисел. Открытый и секретный ключи являются функциями двух больших (100 ~ 200 двоичных разрядов или даже больше) простых чисел. Предполагается, что задача восстановления открытого текста по шифротексту и открытому ключу эквивалентна задаче факторизации.

Для генерации парных ключей берутся два больших  случайных простых числа p и q. В целях максимальной криптостойкости p и q  выбираются равной длины. Затем  вычисляется их произведение n=pq (n называется модулем). Далее случайным образом выбирается число e (ключ шифрования), удовлетворяющее условию: 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое)    с числом f(n)=(p-1)*(q-1).

Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что ed=1 mod f(n).   Число d  такое,  что    (ed - 1)   делится    на      (p - 1)(q–1).

 Таблица 1.

 Числа d и n  - также взаимно простые числа.

Числа e и n – открытый ключ, а d – секретный.

Два простых числа  p и q хранятся в секрете.

Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q  - 100 разрядные простые числа, то n будет содержать около 20 разрядов и каждый блок сообщения mi  должен иметь такое же число разрядов. Если же нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение с будет состоять из блоков ci той же самой длины. Шифрование сводиться к вычислению

ci =mie mod n.

При дешифровании для каждого зашифрованного блока ci вычисляется

mi = cid mod n

Последнее справедливо, так как

cid = (mie)d = mied = mikf(n)+1 = mi·1 = mi

Все вычисления выполняются по mod n. Сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор. 

1.3 Скорость работы алгоритма RSA

Как при шифровании/дешифровании, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.

В практических приложениях для открытого ключа обычно выбирается относительно небольшой показатель, а зачастую группы пользователей используют один и тот же открытый показатель, но каждый с различным модулем. (Если открытый показатель неизменен, вводятся некоторые ограничения на главные делители (факторы) модуля.) При этом шифрование данных идет быстрее, чем расшифровка, а проверка подписи – быстрее, чем подписание. Если k – количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым ключом пропорционально второй степени k, количество шагов для операций частного ключа – третьей степени k, количество шагов для операции создания ключей – четвертой степени k.

Методы "быстрого умножения" – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования, реализующих алгоритм RSA быстро увеличиваются.

Алгоритм RSA намного медленнее, чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее, по крайней мере, в 100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благодаря ведущимся разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блочного шифрования.

1.4 Криптостойкость RSA

Предполагается, что криптостойкость RSA  зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно n разложить на множители. Чтобы восстановить  m по с и e. Не  исключено, что может быть открыт совсем иной способ криптоанализа  RSA. Однако, если этот новый способ позволит криптоаналитику получить d , он также может быть использован для разложения на множители больших чисел. Также можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения nна множители. При использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрование всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования  d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже  менее эффективна, чем попытка разложения n на множители. В 1993 г. был предложен метод криптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее  разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых  чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.

ГЛАВА 2 МЕТОДЫ ВСКРЫТИЯ КРИПТОСИСТЕМЫ RSA

Существует несколько способов взлома RSA.

Наиболее эффективная атака: найти частный (private) ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудноразрешимой задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления частного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку c = me(mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако, в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

Существуют и другие типы атак, позволяющие, однако, вскрыть только одно сообщение и не позволяющие нападающему вскрыть прочие сообщения, зашифрованные тем же ключом.

Самое простое нападение на единственное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, например, "Нападение на рассвете", затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака единственного сообщения применяется в том случае, если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M. Такую атаку можно предотвратить, вводя в сообщение перед каждым шифрованием несколько случайных бит. Также существуют несколько атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение.

Разумеется, существуют и атаки нацеленные не на криптосистему непосредственно, а на уязвимые места всей системы коммуникаций в целом; такие атаки не могут рассматриваться как взлом RSA, так как говорят не о слабости алгоритма RSA, а скорее об уязвимости его конкретной реализации. Например, нападающий может завладеть частным ключом, если тот хранится без должных предосторожностей. Необходимо подчеркнуть, что для полной защиты недостаточно защитить выполнение алгоритма RSA и принять меры вычислительной безопасности, то есть использовать ключ достаточной длины.

2.1 Атака на основе выборочного шифротекста

Некоторые атаки используют уязвимость криптографического протокола. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности системы. Рассмотрим несколько сценариев.

Сценарий 1.

Злоумышленнику удалось перехватить сообщение c, зашифрованное с помощью открытого RSA-ключа Алисы. Он хочет прочитать сообщение. Для раскрытия m = сd он сначала выбирает первое случайное число r, меньшее n, и затем, воспользовавшись открытым ключом Алисы е, вычисляет

x = re mod n,

y = xc mod n,

t = r-1 mod n.

Если х = re mod n , то r= xdmod n

Далее злоумышленник вынуждает Алису подписать сообщение y. Таким образом, процедура вычисления подписи на секретном ключе соответствует процедуре дешифрования сообщения y. (Отметим, что Алиса должна подписать сообщение, а не значение хэш-функции.) Такой обман вполне реален, так как Алиса никогда раньше не видела y. Алиса посылает злоумышленнику

u = yd mod n

Теперь злоумышленник раскрывает m, вычисляя

tu mod n =r-1yd mod n = r-1 xdcd mod n =cd mod n = m

Сценарий 2.

Если Алиса хочет заверить документ, она посылает его нотариусу. Нотариус подписывает его цифровой подписью и отправляет обратно. (Хеш-функции не используются, нотариус шифрует все сообщение на своем секретном ключе.) Злоумышленник хочет, чтобы нотариус подписал такое сообщение, которое в обычном случае тот никогда не подпишет. Это может быть фальшивая временная метка, либо автором этого сообщения может являться другое лицо. Какой бы ни была причина, нотариус никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение т'. Сначала злоумышленник выбирает произвольное значение х и вычисляет у = xе mod п. Параметр e он может получить без труда — это открытый ключ нотариуса, и должен быть опубликован для проверки подписи последнего. Теперь злоумышленник вычисляет m = ym mod n   и посылает m нотариусу на подпись. Нотариус возвращает md mod n. 

Далее злоумышленник вычисляет    (md mod n)x-1 mod n, которое равно m¢ d mod n и является подписью m'. На самом деле у злоумышленника есть множество различных способов решения подобной задачи. Описанная атака основана на сохранении мультипликативной структуры арифметической операции возведения в степень:

(хт)d  mod п =xdmd  тоd п.

Сценарий 3.

Злоумышленник хочет, чтобы Алиса подписала некое сообщение m3. Для этого он создает два сообщения, m1 и m2, такие, что m3 = m1m2 mod n. Если злоумышленник заставит Алису подписатьm1 и m2, то сможет вычислить подпись для m3:

m3d = (m1d mod n)(m2d mod n).

Отсюда вывод — никогда нельзя использовать RSA для подписи случайных документов. Применение хэш-функции в технологии RSA-подписи строго обязательно. Отметим, что специальный формат блоков стандарта ISO 9796 предотвращает подобную атаку.

2.2 Атака на основе общего RSA-модуля

При реализации RSA можно попробовать раздать всем абонентам криптосети одинаковый модуль n, но каждому — свои значения показателей степени e и d. При этом наиболее очевидная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (при фиксированном модуле) и эти два показателя — взаимно-простые числа (как обычно и бывает), то открытый текст может быть раскрыт даже при неизвестных ключах дешифрования. Пусть заданы: m — открытый текст, e1 и e2 — два ключа шифрования, n — общий модуль. Шифротекстами сообщения являются:

c1 = me1 mod n,

c2 = me2 mod n,

Криптоаналитик знает n, e1, e2, c1 и c2. Так как e1 и e2 — взаимно-простые числа, то, воспользовавшись расширенным алгоритмом Евклида, можно найти такие числа r и s, что

re1 + se2 = 1.

Полагая r отрицательным (или r, или s должно быть отрицательным), можно снова воспользоваться расширенным алгоритмом Евклида для вычисления c1-1. Тогда

(c1-1)-rc2s = m mod n.

Существует два других, более тонких метода раскрытия подобного типа. Один использует вероятностный метод для разложения n на множители. Другой — детерминированный алгоритм вычисления какого-нибудь секретного ключа без разложения модуля на множители. Таким образом, использование общего для группы пользователей параметра n может отрицательно сказаться на уровне безопасности криптосети.

2.3 Атака «шифрование коротких сообщений»

Известно, что криптосистема RSA обладает низкой криптостойкостью при зашифрованном на малом e коротком сообщении. Действительно, при c = me < n открытый текст m может быть восстановлен по шифротексту c при помощи процедуры извлечения корня. Фактически подобная атака возможна и тогда, когда в процессе возведения в степень выполнялось некоторое количество приведений по модулю. При c > n  трудоемкость такой атаки ниже трудоемкости исчерпывающего перебора для m. Однако меры противодействия также очевидны, — либо открытый ключ e должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи. Таким образом, разумный подход заключается в искусственном наращивании коротких открытых текстов («набивки»). При этом необходимо следить за тем, чтобы удлиненный открытый текст при числовом отображении не превращался в набор множителей некоторого известного числа P, например  P = 2l, что происходит при дополнении открытого текста последовательностью нулей справа (со стороны младших разрядов).  

2.4 Раскрытие малого показателя…

Шифрования

Хэстед (J. Hasted) продемонстрировал уязвимость RSA при условии, если криптоаналитик  может получить множество шифротекстов фиксированного сообщения m, зашифрованного при помощи криптосистемы RSA с различными секретными параметрами  p и q, но при использовании фиксированного открытого ключа e. При соблюдении сформулированных условий можно раскрыть сообщение m. 

Известен частный случай, когда при заданных l различных результатах шифрования me mod n1,…,me mod nl можно раскрыть m при помощи Китайской теоремы об остатках. В общем случае, при заданных t результатах шифрования

(a1m +b1)e mod n1,…,(atm + bt)e mod nt,

где ai и bi, заданы и  t >е(е+1)/2, можно раскрыть сообщение т, воспользовавшись известным математическим методом.

Еще раз отметим, что данная атака возможна только при условии, что исходные сообщения получены известным криптоаналитику способом.

Дешифрования

Другая атака позволяет раскрывать d, когда d не превышает четверти размера n, а e < n  . При случайном выборе e и d, это маловероятно и никогда не произойдет, если значение e мало. Значение d, должно быть большим.

2.5 Атака на протокол

При использовании RSA можно атаковать протокол, в котором сообщение шифруется, а затем подписывается. Предположим, Алиса желает послать сообщение Бобу. Сначала она шифрует сообщение на открытом ключе Боба, а затем подписывает на своем секретном ключе. Зашифрованное и подписанное сообщение выглядит следующим образом:      

(meB mod nB)dA mod nA

Однако Боб может доказать, что Алиса послала ему m', а не m. Так как Бобу известно разложение на множители nB (это его собственный модуль), он может вычислить дискретные логарифмы по основанию nB. Следовательно, ему остается найти x, для которого

m¢x = m mod nB

Если он может опубликовать xeB в качестве своего нового открытого показателя степени и сохранить свой прежний модуль nB, он сможет утверждать, что Алиса послала ему сообщение m', зашифрованное на xeB. Применение хэш-функции не позволяет решить проблему. Однако ее можно решить путем использования фиксированного показателя шифрования для каждого пользователя криптосети.

ГЛАВА 3 КРИПТОСТОЙКОСТЬ RSA НА ПРАКТИКЕ

Известно, что практическая криптостойкость RSA зависит от вычислительной трудоемкости задачи факторизации — разложения двусоставного модуля (произведение двух простых чисел) на сомножители. Факторизация модуля позволяет раскрыть секретный ключ и, как следствие, дешифровать любое сообщение, подделать цифровую подпись. Чем больше число, тем выше вычислительная трудоемкость факторизации. Необходимо отметить, что повышение производительности компьютеров положительно сказалось на успехах в области факторизации, но криптостойкость RSA при этом также возросла. Эффект объясняется различиями в вычислительной трудоемкости процедур факторизации и шифрования/дешифрования: в результате очередного скачка производительности число, поддающееся факторизации, увеличивается на два разряда, тогда как RSA-модуль, без потери вычислительной эффективности, — на двенадцать разрядов. Однако факторизация возможна в случае, если рост производительности не учитывается при периодичности смены ключей.

Каким должен быть модуль RSA? Точный ответ вряд ли возможен — развитие методов целочисленной факторизации с трудом поддается прогнозированию. При этом нельзя полностью исключить возможность атак на основе иных, отличных от факторизации методов. Кроме того, вычислительная трудоемкость модульного возведения в степень (основной операции при шифровании/дешифровании) возрастает с увеличением разрядности модуля. Основная задача при выборе модуля К5А — одновременное обеспечение криптостойкости и вычислительной эффективности процедуры шифрования/дешифрования. Таким образом, при выборе модуля необходимо исходить из реальных оценок роста производительности компьютеров и достижений в области вычислительной теории чисел. Согласно оценкам, для обеспечения адекватного уровня практической криптостойкости разрядность модуля RSA должна быть увеличена в ущерб вычислительной эффективности. Однако идея разбалансированной RSA, предложенная Шамиром, позволяет этого избежать.

В настоящее время криптосистема RSA с модулем 512 бит, реализованная во многих криптографических приложениях, не гарантирует объявленной криптостойкости. Отметим, что в отличие от строгого обоснования низкой криптостойкости RSA с модулем 512 бит прогнозы на будущее менее конкретны; пока анализируются лишь тенденции роста производительности компьютеров и возможные пути развития вычислительной теории чисел. Оценки опираются на предположение о последовательной природе криптографических алгоритмов и использовании стандартной технологии СБИС при их реализации. Ситуация может резко измениться, если исследования в области квантовых и молекулярных вычислений перейдут в практическую фазу.

В большинстве работ при оценке производительности используется единица MY (Mips/Year). Данная единица измерения может быть истолкована следующим образом; компьютер с производительностью один миллион целочисленных инструкций в секунду (million instructions per second = mips) эквивалентен DEC VAX 11/780, тогда 1 MY — год работы VAX11/780. Для разрядности десятичных чисел введем обозначение число_десятичных_ разрядовD. Например, 43D — целое число из 43 десятичных разрядов.

Задача факторизации всегда привлекала внимание математиков. Фундаментальность проблемы впервые была отмечена Гауссом. Одна из первых попыток (1874г.) ее практической постановки и оценки трудоемкости принадлежит английскому экономисту и логику Джевонсу (W.S. Jevons) , предполагавшему, что никому, кроме него, не удастся разложить на множители число 8 616 460 799 (10D). Однако в 1925 г. число было факторизовано:

8 616 460 799 = 96079 х 89681.

В 1967 г. факторизация числа 25D считалась практически нереализуемой. В 1970 году новый метод факторизации Моррисона-Бриллхарта (Morrison-Brillhart) позволил разложить седьмое число Ферма F7 = 2128 + 1 (39D). Барьер 80D, установленный в 1976 г. , был преодолен через пару лет. В 1977 г. профессор Ривест из Массачусетского технологического университета привел убедительные аргументы в пользу выбора в качестве RSA-модуля числа 129D. Ривест предполагал, что для факторизации понадобится более 40 квадрильонов (4 х 1016) лет работы самого быстрого компьютера. Однако факторизация числа была выполнена в 1994 г. по алгоритму квадратичного решета (КР).

В целях развития математических методов факторизации корпорация RSA Data Security, Inc. объявила открытый конкурс на факторизацию RSA-модулей и учредила специальную денежную премию. В 1996 г. число RSA-130 (130D) было факторизовано при помощи алгоритма обобщенного числового решета (ОЧР). За счет применения алгоритма ОЧР эффективность факторизации RSA-130 возросла на порядок по сравнению с факторизацией числа RSA-129. Проект RSA-130 был коллективным.

К моменту факторизации RSA-130 четыре из объявленных ранее модулей были факторизованы при помощи алгоритма КР . Таким образом, возможность успешной атаки на криптосистемуRSA с 512-битным модулем (» 160D) подтверждается результатами:  

 Таблица 1.

В настоящее время рекомендуемая минимальная длина RSA-модуля — 768 бит (w 230D). Исходя из оценки трудоемкости проекта RSA-130, производительность компьютера для эффективной факторизации числа 230D должна быть не меньше 108 MY.

В феврале 1999 г. методом ОЧР был факторизован модуль RSA-140. Данный проект, также как и RSA-130.

Суммарная производительность проекта RSA-140 достигла 2000MY, а объем оперативной памяти (на одной рабочей станции) при реализации ключевого этапа алгоритма ОЧР составил 800 Мбайт.

Данные о трудоемкости проекта RSA-140 позволяют построить прогноз относительно количества ресурсов, необходимых для факторизации модулей с разрядностью 512, 768, 1024 бит: 

В следующей таблице приведены сведения о достижениях в области целочисленной факторизации за последние тридцать лет, а также указана производительность компьютера, достаточная для успешной факторизации чисел заданной разрядности. 

Отметим, что для эффективной факторизации RSA-129 по алгоритму ОЧР потребуется 1000 MY вместо 5000 MY при факторизации по алгоритму КР.

Существенный скачок в производительности компьютеров в период между 1984 и 1994 годами обусловлен интенсивным развитием компьютерных сетей и, как следствие, практической реализацией метода распределенных вычислений. Идея использования свободного времени рабочих станций сети для факторизации принадлежит Силверману        (В. Silverman). (К сожалению, более ранняя попытка Шреппеля (R. Schroeppel) использовать сетевые ресурсы для факторизации восьмого числа Ферма F8 = 2256 + 1 не привлекла внимания специалистов.) Дальнейшее развитие идея распределенных вычислений получила в исследованиях Ленстры (A. Lenstra) и Мэнэсса (М. Manasse). В проекте RSA-129 было задействовано около 1600 рабочих станций в течение восьми месяцев. В отличие от традиционного подхода, когда для эффективной силовой атаки необходимо построить специальный компьютер, атака на основе идеи распределенных вычислений не требует значительных инвестиций и технических ресурсов.