Французским ученым удалось взломать самый сложный криптографический алгоритм на сегодняшний день. Для этого им понадобилась сеть из компьютеров, распределенных по всему миру.
Хоть решенный алгоритм и слабее практический криптографии, которую в наши дни используют для обеспечения безопасности данных, однако даже такое достижение стало для современной вычислительной техники весьма выдающимся. В общей сложности системе потребовались 35 000 000 вычислительных часов, которые удалось сжать в приемлемый временной промежуток благодаря обширной сети.
Криптография – это, по сути, математическая и компьютерная гонка на сообразительность. Метод шифрования, который ученые использовали для создания задачи, называется алгоритмом RSA. В этом алгоритме две стороны шифруют информацию, используя невероятно большое число, полученное умножением двух простых чисел.
Как многие знают, в математике существуют простые трюки, которые позволят вам сразу сказать, делится ли число на 9 или 11. Но как узнать, делится ли оно на 17? А на 19? Какие простые числа надо перемножить, чтобы получить 667? Согласитесь, чем больше число – тем менее очевидным становится ответ.
Другая особенность шифрования простых чисел заключается в том, что их произведение образует уникальный класс т.н. «полупростых» чисел. Сами по себе они уже не «простые» (поскольку являются результатом умножения двух факторов), но при этом не делятся ни как какие составные числа. У составных чисел есть зацепки и подсказки, которые позволяют делить их на части, а у больших нечетных полупростых чисел такой зацепки попросту нет.
Попробуйте разбить 667 на два простых числа. Прежде чем вы дойдете до единственно верного варианта (23 и 29), вы должны перепробовать все однозначные числа, а затем 11, 13, 17 и 19. Однако числа, которые исследователи использовали для взлома глобальных многопоточных вычислений, были длиной до 240 цифр!
Компьютеры решают подобные головоломки методом автоподбора, и чем выше вычислительная мощность – тем быстрее будет выполняться операция. Проблема в том, что каждая добавленная к результату цифра увеличивает общий пул возможных вариантов на порядок (то есть в 10 раз), что существенно усложняет работу.
В итоге французские ученые побили предыдущий рекорд как по сложности, так и по времени, решив задачу из 240 цифр за меньшее время, чем другая команда решила ее для 232 цифр. Однако даже это гигантское число с криптографическим ключом длиной 795 бит составляет чуть более трети от 2048-битного шифрования, используемого большинством компьютеров. Впрочем, легко понять, почему криптография — это гонка, позволяющая опередить те самые компьютеры, которые могут запускать эти алгоритмы и взламывать их при наличии достаточного времени.
