Вступ в криптоаналіз RSA криптосистем, страница 2

Число десяткових знаків	Приблизне число бітів	Дата вирішення	Необхідне число MIPS-літ	Використаний алгоритм
100	332	Квітень 1991 р.	7	Квадратичне решето
110	365	Квітень 1992 р.	75	Квадратичне решето
120	398	Червень 1993 р.	830	Квадратичне решето
129	428	Квітень 1994 р.	5000	Квадратичне решето
130	431	Квітень 1996 р.	500	Загальне решето числового поля
140	464	Лютий 1999 р.		Загальне решето числового поля
150	498	Відкритий	Відкликаний
155	514	Серпень 1999 р.		Загальне решето числового поля
160	531	Квітень 2003 р.		Загальне решето числового поля
174	576	Грудень 2003 р.		Загальне решето числового поля
193	640	Відкритий
212	704	Відкритий
232	768	Відкритий
270	896	Відкритий
309	1024	Відкритий
463	1536	Відкритий
617	2048	Відкритий

До 1994 року для розкладання на множники застосовувався підхід, відомий за назвою методу квадратичного решета. Для криптоаналізу RSA-130, RSA-140, RSA-155, RSA-160, RSA-576 використовувався новий алгоритм, названий методом решета в полі чисел загального виду, що дозволило скоротити обсяг обчислювальних зусиль майже на 10% у порівнянні з тими, що були потрібні раніше для аналізу RSA-129.

Погроза ключам великої довжини тут подвійна: безупинне зростання обчислювальної потужності сучасних комп'ютерів і безупинне удосконалення алгоритмів розкладання на множники.

3.2.3 Двійкове решето

Базується на знаходженні двох випадкових чисел Х і Y, але таких, що:

1) ;

2) ;

3) ;

4).

У випадках 3, 4 просте число може буде знайдено, як:

НСД;

НСД.

Сутність методу двійкового решета:

1. Будується база двійкового решета:

 (добуток простих чисел)

2. .

Приклад

Нехай необхідно факторизувати число .

Будуємо базу:

Розрахунок зводиться в табл. 3.2.1

Таблиця 3.2.1

і			Р1	Р2	...	Р3
1	225	16	4			+
2	256	47	-			-
3	17	80	4		1	+
4
l

і – номери дослідів

Необхідно одержати позитивних результатів не менше числа в базі

НСД = НСД=11

11·19 = 209.

3.2.4 Сутність методу ρ-Поларда

Метод ρ-Поларда є попередником методу двійкового решета. Його розв’язок полягає у знаходженні Х і Y, які порівнюються за  

Сутність методу: за допомогою деякої функції  будується послідовність точок (крива ρ-Поларда):

Точка Х повинна збігтися з точкою Y.

НСД.

Додаток А

1.13 Криптоаналіз RSA та дискретних логарифмiв методом -Поларда. Приклади розв’язку задач та задачі для самостійного розв’язання

1.13.1 Приклади розв'язку задач