Определить общее количество простых чисел в заданном диапазоне гораздо проще, чем вычислить их ряд до этого предела. Существуют (и разрабатываются новые) также способы эффективного поиска простых чисел отдельных типов и алгоритмы проверки произвольного числа на соответствие критериям простоты.
При помощи проекта добровольных распределённых вычислений было найдено самое большое (среди известных на сегодня) простое число. Им оказалось число Мерсенна: 2 57885161 — 1. Его запись в десятичном виде в формате текстового файла выглядит так: [Осторожно! Браузер может зависнуть при попытке загрузить эту страницу в память.].
Помимо очевидного упрощения задачи взлома систем шифрования с течением времени (в силу развития математики и закона Мура), существует гораздо более серьёзная проблема — снижение стойкости применяемых на практике криптографических средств из-за ошибок в их реализации или намеренного ослабления.
Именно в последнем заключается политика правительства США, Канады, Великобритании и, возможно, других стран в отношении как экспортируемых, так и свободно доступных криптографических продуктов. К примеру, эффективная длина ключа намеренно уменьшалась в системах с блочным алгоритмом DES и поточным алгоритмом шифрования A5.
До недавнего времени считалось, что наиболее популярные варианты реализации RSA сегодня лишены такого явного огрубления, но их стойкость оказалась снижена на другом уровне.
После двух с половиной лет распределённых вычислений группе криптографов под руководством Торстена Клейнюнга (Thorsten Kleinjung) в декабре 2009 года удалось выполнить факторизацию ключа RSA длиной 768 бит методом решета числового поля. После этой работы оценка вычислительной сложности взлома криптосистемы RSA была понижена на несколько порядков.
Последующие работы этого же коллектива выявили другие проблемы с практической реализацией криптосистем на базе RSA. Как и в рассмотренных выше случаях, её корнем стал ненадёжный ГПСЧ. Совпадающие произведения простых чисел были обнаружены у одного процента всех проанализированных ключей с длиной 1 024 бита. Это кажется не столь большим, пока не осознаёшь, что в таком огромном массиве идентичных пар не должно встречаться вовсе. Разложив модуль на произведение двух простых чисел, атакующий может вычислить недостающий секретный компонент и взломать RSA.
Главный специалист подразделения безопасности корпорации EMC и директор лаборатории RSA Ари Джулс (Ari Juels) ознакомился с исследованиями группы Торстена и опубликовал официальный комментарий. На страницах блога он в очередной раз подчёркивает, что теоретическая стойкость алгоритма не эквивалентна надёжности конкретных криптографических систем на его основе. Указанные недостатки касаются не самого алгоритма RSA, а проблем его применения.
Что получается в сухом остатке? На протяжении как минимум последних пяти лет разные группы криптографов указывали на однотипные проблемы в самых распространённых системах, использующих алгоритм RSA. Проанализировав эти отчёты и фактические темпы вскрытия ключей разной длины в конкурсе RSA Challenge, Национальный институт стандартов и технологий США (NIST) рекомендовал устранить выявленные ошибки, а также прекратить использование ключей длиной 1 024 бита и менее не позже начала 2010 года. Однако проблема остаётся актуальной и для ключей длиной 2 048 бит, поскольку ненадёжные генераторы псевдослучайных чисел продолжают применяться до сих пор в самых ответственных областях.
Особый путь Daimler AG к внедрению в свои машины искусственного интеллекта
Михаил Ваннах
Опубликовано 17 сентября 2013
Были когда-то автомобили-классики. Не редкой ныне классической схемы (впереди мотор, в середине — кардан, привод на задний мост), а именно классики. Как Данте, Шекспир и Достоевский в литературе. Рождалось их производство до Великой войны, в мире, не знавшем подоходных налогов и социальной справедливости, и продолжалось до 1930-х годов. Наиболее известен воспетый пролетарским поэтом Маяковским Rolls-Royce – «Товарищи, вы видели Ройса? Ройса, который с ветром сросся?» Товарищи, впрочем, Rolls-Royce любили и активно эксплуатировали. Ребёнок, поглядевший в Музее В. И. Ленина в Горках на машину, предпочитаемую вождём пролетариев, на всю жизнь избавлялся от идиотской веры в равенство и братство… Были и менее известные в нашей стране классики — скажем Bucciali и Bugatti.