Атаки на поиск ключа

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

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

Хотя статистический поиск ключа может эффективно сузить объём памяти для анализа, всё равно требуется проверять области высокой энтропии на наличие искомого материала. В некоторых случаях, особенно для систем открытых ключей, можно определить паттерны, обязательно встречающиеся в материалах ключа, и ограничить поиск лишь областями, где эти паттерны обнаруживаются.

Шамир и ван Сомерен^[1] показали пример такого аналитического подхода для поиска частных ключей RSA, если известен открытый ключ с малым публичным показателем. В системе RSA открытый ключ представляет собой пару ${\displaystyle (n,e)}$, где ${\displaystyle n=p\cdot q}$, p и q — два больших простых числа. Соответствующий приватный ключ записывается как ${\displaystyle (n,d)}$ (или иногда ${\displaystyle (p,q,d)}$ либо их вариант), где ${\displaystyle e\cdot d\equiv 1{\pmod {\varphi (n)}}}$; то есть, e, умноженное на d, сравнимо с 1 по модулю ${\displaystyle \varphi (n)}$, где φ — функция Эйлера и равна размеру мультипликативной группы по модулю n. В случае с RSA:

${\displaystyle \varphi (n)=(p-1)(q-1)=n-p-q+1}$.

Нахождение значения ${\displaystyle \varphi (n)}$ по n позволяет факторизовать n, и безопасность RSA основана на сложности этой задачи. Таким образом, зная только e и n, нельзя точно вычислить d. Однако атакующий может получить представление о том, как выглядит d, учитывая, что p и q обычно равны по длине (в битах) и оба примерно равны корню из n. Тогда можно приблизительно оценить:

${\displaystyle \varphi (n)\approx \varphi '(n)=n-2{\sqrt {n}}}$.

И обычно в более значащей части битового представления это приближение будет верно. Связь между e и d выражается как:

${\displaystyle d={\frac {1+k\cdot \varphi (n)}{e}}}$,

где точное значение k неизвестно, но ${\displaystyle 0<k<e.}$ Используя это равенство и приближение ${\displaystyle \varphi '(n)}$, атакующий может перебрать возможные значения верхней половины битов d для каждого k. Эту битовую маску можно искать на порядки быстрее, чем выполнять тестовую расшифровку. Более того, в частом случае ${\displaystyle e=3}$ оказывается, что ${\displaystyle k=2,}$ что позволяет определить и напрямую искать старшие биты d.