Современные системы шифрования (Лабораторная работа № 1), страница 4

Эти результаты были достигнуты группами исследователей из Нидерландов, Австралии, Франции, Великобритании и США под руководством Германа Дж. Дж. те Риля (Herman J. J. te Riele) из Национального научно-исследовательского института математики и информатики CWI (Centrum voor Wiskunde en Informatica) в Нидерландах. Числа RSA-130 и RSA-140 взяты из списка 42 модулей RSA, опубликованного в 1991 г. компанией RSA Data Security, Inc. в помощь исследователям в области криптографии. Вычисления по разложению RSA-130 и RSA-140 были распределены между большим числом рабочих станций, затем результаты были сопоставлены. Разложение числа RSA-130 заняло около 1000 MIPS-лет, RSA-140 – 2000 MIPS-лет.

MIPS = mega instruction per second (миллион инструкций в секунду) – единица измерения быстродействия компьютера. Считается, что со скоростью 1 MIPS работает компьютер, выполняющий 700 000 сложений и 300 000 умножений в секунду.

Вскоре после этого, в конце августа 1999 года, мир был поражен известием о разложении числа RSA-155. Работы опять проводились интернациональной командой под руководством Германа те Риля и заняли около 8000 MIPS-лет. С разложением числа

RSA-155 = 10941738641570527421809707322040357612003732945

44920599091384213147634998428893478471799725789

12673324976257528997818337970765372440271467435

31593354333897

на два 78-разрядных множителя

RSA-155 = 10263959282974110577205419657399167590071656780

8038066803341933521790711307779

×

10660348838016845482092722036001287867920795857

5989291522270608237193062808643

был пересечен магический рубеж в 512 бит – ключи такой двоичной длины долгие годы считались надежными. Факторизация числа RSA-155, потребовала:

-  использования 160 рабочих станций SGI и Sun (175–400 МГц);

-  8 процессоров SGI Origin 2000 (250 МГц);

-  120 персональных компьютеров Pentium II (300–450 МГц);

-  4 кластеров Digital\Compaq (500 МГц);

-  9 недель для настройки параметров GNFS;

-  5,2 месяца для сбора пар ;

-  3,2 Гб оперативной памяти, 224 часа вычислений на Cray C916 для обработки матрицы  размером 66991916711336 с 417132631 ненулевыми элементами.

В 2003 и 2005 годах были сделаны новые успехи в факторизации: разложение чисел RSA-576 и RSA-640 (теперь номер означает количество битовых знаков: RSA-576 эквивалентно старому RSA-176, а RSA-640 эквивалентно старому RSA-193). Эти события делают ситуацию в мире телекоммуникационных систем непредсказуемой, поскольку множество коммерческих систем могут быть взломаны за очень короткий период времени. Общая ситуация в мире факторизации (информация RSA Security Labs от 4.09.2006) выглядит следующим образом:

Число	Приз (USD)	Статус	Дата представления	Представлено
RSA-576	$10,000	факторизовано	3 декабря 2003 г	J. Franke и др.
RSA-640	$20,000	факторизовано	2 ноября 2005 г	F. Bahr и др.
RSA-704	$30,000	не факторизовано
RSA-768	$50,000	не факторизовано
RSA-896	$75,000	не факторизовано
RSA-1024	$100,000	не факторизовано
RSA-1536	$150,000	не факторизовано
RSA-2048	$200,000	не факторизовано

RSA-576 (Десятичных знаков: 176)

RSA-576 = 18819881292060796383869723946165043980716356337941

73827007633564229888597152346654853190606065047430

45317388011303396716199692321205734031879550656996

221305168759307650257059