Несмотря на довольно большое число различных криптосистем с открытым ключом, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Ривеста, Шамира и Эйдельмана.
Ривест, Шамир и Эйдельман воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.
Пустьn=p*q, где p и q - различные простые числа, и e и d удовлетворяют уравнению
e*d (mod (p-1)*(q-1))= 1
Если p и q - достаточно большие простые числа, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.
{e,n} образует открытый ключ, а {d,n} - закрытый (можно взять и наоборот).
Открытый ключ публикуется и доступен каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования, сообщение невозможно раскрыть с помощью открытого ключа. Владелец же закрытого ключа без труда может расшифровать принятое сообщение.
Шифрование осуществляется по формуле: Sшифр = Se mod N
Шифрование осуществляется по формуле: S = Sdшифрmod N
Где S – исходный текст, Sшифр– преобразованный текст, при этом S < N
Группа известных специалистов-криптографов, созданная под эгидой Альянса производителей программного обеспечения для бизнеса (промышленной организации, препятствующей незаконному использованию программного обеспечения), пришла к выводу, что необходимая длина ключа в настоящее время должна быть не менее 75 битов с дальнейшим увеличением в течение последующих 20 лет до 90 битов. Проверим данное утверждение.
Проблема поиска ключей симметричной криптосистемы путем перебора всех возможных ключей относится к классу задач, допускающих распараллеливание. Применение распределенных вычислений для организации перебора таких ключей позволяет эффективно решать трудоемкие задачи в этой области. Экспоненциальная динамика роста с течением времени производительности вычислительных систем (10 раз за 5 лет) оказывает еще более существенное влияние на рост производительности системы в целом. Таким образом, прогресс в этой области возможен за счет:
1) использования достижений научно-технического прогресса и применения технологических новинок для увеличения производительности отдельного устройства;
2) увеличения количества таких устройств в системе.
C физической точки зрения тот тип транзистора, который является основой современной интегральной схемы, может быть уменьшен еще примерно в 10 раз, до размера 0,03 мк. За этой гранью процесс включения/выключения микроскопических переключателей станет практически невозможным. Таким образом максимальное быстродействие составит - 1016 операций/секунду, а предел роста наступит приблизительно в 2030 г.
Других способов повышения вычислительной мощности нет. Таким образом, с точки зрения защиты информации криптографическими методами, анализ потенциальных возможностей метода распределенных вычислений представляет как для криптоаналитиков, так и для разработчиков криптографических систем значительный интерес. Попробуем, поэтому, проанализировать предельные значения двух указанных тенденций.
Из списка, появившегося летом 1999 года, следует, что по быстродействию суперкомпьютеры распределились следующим образом:
с мощностью порядка 1012 FLOPS 3 экз.;
с мощностью порядка 1011 FLOPS 54 экз.;
с мощностью порядка 1010 FLOPS 428 экз.;
с мощностью порядка 109 FLOPS 251 экз.
Десять самых мощных суперкомпьютеров в мире по состоянию на июль 1999 г.
| Рейтинг | Наименование машины | Страна-обладатель | Фирма-производитель | Количество процессоров | Мощность (GFLOPS) |
| 1 | Intel ASCI Red | США | Intel (США) | 9125 | 1333 |
| 2 | Hitachi/TsukubaCP-PACS | Япония | Hitachi/Tsukuba (Япония) | 2048 | 368 |
| 3 | SGI/Cray T3E | Великобритания | Cray (США) | 696 | 265 |
| 4 | Fujitsu Numerical Wind Tunnel | Япония | Fujitsu (Япония) | 167 | 230 |
| 5 | Hitachi SR2201 | Япония | Hitachi (Япония) | 1024 | 220 |
| 6 | SGI/Cray T3E | Германия | Cray (США) | 512 | 176 |
| 7 | SGI/Cray T3E | США | Cray (США) | 512 | 176 |
| 8 | SGI/Cray T3E | Германия | Cray (США) | 512 | 176 |
| 9 | SGI/Cray T3E | США | Cray (США) | 512 | 176 |
| 10 | SGI/Cray T3E | США | Cray (США) | 512 | 176 |
Первое место в мире по количеству суперкомпьютеров занимают США 254 (51%). За ними следуют Япония 87 (17,5%), Германия 45 (9%), Великобритания 24 (4,8%), Франция 18 (3,6%), Корея 8 (1,6%), Канада 7 (1,4%), Швеция, Швейцария и Норвегия по 6 (1,2%). Россия упомянута в этом списке лишь один раз: на 156-ом месте находится компьютер HPC Ultra 10000 (пиковая производительность 16600 MFLOPS), произведенный фирмой SUN и установленный в Национальном Резервном Банке России. Интересная деталь: в США отсутствуют компьютеры иностранного производства американцы работают только на отечественных машинах и к тому же снабжают ими весь остальной мир.
Количество установок суперкомпьютеров возрастает год от года в геометрической прогрессии, причем основной объем опять же приходится на США. Статистика по годам сложилась следующая:
1999 786 установок
1998 638 установок
1997 207 установок
1996 168 установок
1995 52 установки
1994 45 установок
1993 16 установок
1992 10 установок
Допустим, что рассматриваемые нами алгоритмы шифрования идеальны, то есть оптимальным методом их взлома будет прямой перебор всех возможных ключей данного алгоритма. Очевидно, что в этом случае стойкость криптосистем будет определяться длиной ключа. При проведении данного исследования предполагалось, что криптоаналитик противной стороны обладает всей информацией относительно алгоритма шифрования, за исключением данных о секретном ключе, и ему доступен для анализа шифрованный текст сообщения. По определению предполагается, что идеальный алгоритм лишен каких-либо недостатков, снижающих его криптостойкость. Для шифров ГОСТ-28147-89 и IDEA существенных недостатков в настоящее время не выявленно.
Предположим также, что генерация ключа компьютером происходит за один такт его работы, а операция дешифрования мгновенно. Определив отношение количества ключей к быстродействию самого мощного компьютера, мы получим нижнюю оценку сложности дешифрования сообщения для идеального алгоритма.
Время, необходимое в настоящий момент самым мощным суперкомпьютерам для полного перебора ключей
| Наименованиемашины | Мощность (FLOPS) | 56 бит7.2*Е16 | 64 бита1.8*E19 | 70 бит1.18*Е21 | 75 бит3.78*Е22 | 128 бит3.4*E38 | 256 бит1.15*Е77 |
| Intel ASCI Red | 1.333*Е12 | 14 часов | 5 мес. | 28 лет | 899 года | 8.09*Е18 | 2.72*Е57 |
| Hitachi/Tsukuba CP-PACS | 3.68*Е11 | 52 часа | 18 мес. | 102 года | 3257 лет | 2.93*Е19 | 9.9*Е57 |
| SGI/Cray T3E | 2.65*Е11 | 69 часов | 51 мес. | 141 года | 4523 года | 4.07*Е19 | 1.37*Е58 |
| Fujitsu Numerical Wind Tunnel | 2.3*Е11 | 171 час | 60 мес. | 162 года | 5211 года | 4.69*Е19 | 1.58*Е58 |
| Hitachi SR2201 | 2.2*Е11 | 178 часов | 61 мес. | 170 лет | 5448 лет | 4.9*Е19 | 1.66*Е58 |
Таким образом с помощью указанной рабочей модели можно оценивать надежность проектируемых и эксплуатируемых систем шифрования. Алгоритм ГОСТ 28147-89 использует таблицу подстановок размером 512 бит. Общее число возможных таблиц составляет 1.33*Е36 и полное время перебора составляет 3.162*Е16 лет. Для алгоритма IDEA длина ключа составляет 128 бит и полное время перебора составляет 8.09*Е18 лет. Даже если будет использован суперкомпьютер состоящий из ста тысяч процессоров с максимально возможной скоростью в 1016 операций/секунду для расшифровки ГОСТа понадобится 4.21*Е7 лет, а для IDEA - 1.08*Е10 лет. Очевидно, что даже применение нескольких сотен суперкомпьютеров Intel ASCI Red, стоимостью по 55 миллионов долларов каждый, не в стоянии кардинально улучшить ситуацию.
алгоритм RSA
Оценки трудоемкости разложения простых чисел (1994 год)
| N | Число операций | Длина | Примечания |
| E50 | 1.4*1010 | 166 бит | Раскрываем на суперкомпьютерах |
| E100 | 2.3*1015 | 332 бит | На пределе современных технологий |
| E200 | 1.2*1023 | 664 бит | За пределами современных технологий |
| E300 | 2.7*1034 | 996 бит | Требует существенных изменений в технологии |
| E500 | 1.3*1051 | 1660 бит | Не раскрываем |
Оценки трудоемкости разложения простых чисел (2000 год)
| N | Число операций | Длина | Максимальное время дешифровки на суперкомпьютере Intel ASCI Red |
| E50 | 1.4*1010 | 166 бит | 0.01 сек. |
| E100 | 2.3*1015 | 332 бит | 29 сек. |
| E200 | 1.2*1023 | 664 бит | 2854 года |
| E300 | 2.7*1034 | 996 бит | 6.425*Е14 лет |
| E500 | 1.3*1051 | 1660 бит | 3.092*Е31 лет |
В конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью сети Интернет было задействовано 1600 компьютеров. Сами авторы RSA рекомендуют использовать следующие размеры модуля N: