Ученые, работающие в отделе информатики и прикладной математики Вайсмановского научного института (Израиль) разработали проект вычислительного устройства, способного с высокой скоростью раскладывать большие числа на простые множители. Как известно, именно принцип вычислительной трудности факторизации (разложения на множители) больших чисел положен в основу многих современных криптографических алгоритмов.

До сих пор наиболее эффективным алгоритмом факторизации считался алгоритм NFS (number field sieve - сито числового поля). С его помощью в 1999 году был взломан алгоритм RSA c ключом длиной 512 бит. Процесс взлома занял много месяцев и потребовал огромных вычислительных ресурсов. Стойкости 1024-разрядного шифра RSA, по мнению большинства экспертов достаточно для надежной защиты информации в течение ближайших 15-20 лет.

Однако Ади Шамир (один из соавторов алгоритма RSA) и Эран Тромер полагают, что это не так. Двое исследователей разработали новое вычислительное устройство, способное факторизовать числа в несколько раз быстрее всех предыдущих разработок такого рода. В результате, взлом стойких шифров значительно облегчается.

До последнего времени наиболее совершенным устройством для быстрого разложения чисел на множители была оптоэлектронная система TWINKLE. Она состояла из подложки, разбитой на множество вычислительных ячеек, каждая из которых работала с собственной числовой последовательностью. TWINKLE последовательно перебирает различные области числового сита в соответствии с сигналами от тактового генератора. Поскольку в TWINKLE применяются оптические компоненты, полупроводниковой основой устройства служит дорогой арсенид галлия.

Устройство TWIRL, разработанное Шамиром и Тромером, использует близкий к TWINKLE подход к реализации алгоритма разложения чисел на множители. Однако новое устройство может параллельно рассматривать тысячи участков числового сита, а схема устройства не содержит оптических элементов. По сути, TWIRL представляет собой специализированную сверхбольшую интегральную схему (СБИС), работающую на частоте 1 ГГц, выполненную по 0,13-микронной технологии.

Пока исследователи разработали лишь схему TWIRL и не реализовали ее на практике, хотя предварительная оценка показывает, что с помощью TWIRL взлом шифров с ключами длиннее 512 бит становится возможным. Например, для вскрытия 1024-битного шифра понадобится специальный компьютер на основе TWIRL стоимостью около 10 млн. долл. США. Для взлома шифра такой машине понадобится около года. 512-битный шифр RSA TWIRL-компьютер стоимостью в 10000 долларов США вскроет менее чем за десять минут.

По итогам своих исследований израильские ученые готовятся опубликовать статью. С ее предварительным вариантом в формате PDF можно ознакомиться здесь (размер файла 324 кб).