Коллектив Авторов - Цифровой журнал «Компьютерра» № 191

В этом году перуанским математиком Харальдом Хельфготтом (Harald Andres Helfgott Seier) была решенаодна из старейших математических проблем — доказана гипотеза Гольдбаха. Она гласит, что любое нечётное число больше пяти можно представить в виде суммы трёх простых чисел.

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

При помощи проекта добровольных распределённых вычислений было найдено самое большое (среди известных на сегодня) простое число. Им оказалось число Мерсенна: 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 бит, поскольку ненадёжные генераторы псевдослучайных чисел продолжают применяться до сих пор в самых ответственных областях.

К оглавлению

Опубликовано17 сентября 2013

Были когда-то автомобили-классики. Не редкой ныне классической схемы (впереди мотор, в середине — кардан, привод на задний мост), а именно классики. Как Данте, Шекспир и Достоевский в литературе. Рождалось их производство до Великой войны, в мире, не знавшем подоходных налогов и социальной справедливости, и продолжалось до 1930-х годов. Наиболее известен воспетый пролетарским поэтом Маяковским Rolls-Royce – «Товарищи, вы видели Ройса? Ройса, который с ветром сросся?» Товарищи, впрочем, Rolls-Royce любили и активно эксплуатировали. Ребёнок, поглядевший в Музее В. И. Ленина в Горках на машину, предпочитаемую вождём пролетариев, на всю жизнь избавлялся от идиотской веры в равенство и братство… Были и менее известные в нашей стране классики — скажем Bucciali и Bugatti.

Огромные, до семи метров длиной. С длиннющими капотами, скрывающими двигатели аж о шестнадцати цилиндрах. У Hispano-Suiza («испано-швейцарской») на капоте был аист, в память об эскадрилье аса первой мировой Гинеме, имевшей эмблемой эту птицу и летавшей на моторах этой фирмы. Модель от Avions Voisin 1935 года звалась «Аэродинамик». Люксовые автопроизводители из Германии также были связаны с авиацией: одна из моделей компании Maybach звалась Maybach Zeppelin, её моторы стояли и на цеппелинах, и на менее известных жёстких дирижаблях от Шютте-Ланц. Так что хайтек индустриальной эпохи широко присутствовал в классиках, собиравшихся вручную, в традициях европейских цехов.

Именно с «классиков» пришли в массовое автомобилестроение электрический стартер, впервые появившийся на кадиллаках, указатели поворота, синхронизаторы в коробке передач. Оценить это может только тот, кому в 70-е приходилось с мотороллера «Тула-200″ показывать намерение повернуть рукой, а потом, чуть позже, «ловить передачи» в коробке «Москвича-400», в девичестве известного как «опель-кадет»; нынче выросло уже целое поколение, не умеющее ездить без «автомата»… Несмотря на консервативность «классиков», изменения в технологиях смежного, авиационного хайтека отображались и на них. У Bugatti колёса сначала имели спицы из рояльной проволоки, шедшей на растяжки аэропланов. Потом, когда крылатым металлом стал дюраль, они обрели диски из лёгких сплавов.

Ну а теперь перенесёмся в наши дни. Посмотрим на продукцию концерна Daimler — и увидим, что его новостив равной мере проходят и по ведомству информационных технологий. Дело в том, что опытный автомобиль Mercedes Benz S 500 Intelligent Drive абсолютно автономно совершил стокилометровую поездку между Мангеймом и Пфорцхаймом. Расстояние небольшое — по сравнению с состоявшимся в 2010 году пробегом от Милана до Шанхая минивэнов Piaggio Porter, оборудованных системами автовождения от пармской компании Vislab. Но там были машины, обвешанные дополнительным оборудованием. Перед каждым роботом ехал человек, прокладывавший ему путь…