Максимизация границ для малых корней методами линеаризации и применение к RSA с малой секретной экспонентой

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:32, 17 декабря 2015.
Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA
Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA.png
Авторы Mathias Herrmann[@: 1]
Alexander May[@: 2]
Опубликован 2010 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы представляем элементарный метод построения оптимизированных решёток, который используется для нахождения малых корней полиномиальных уравнений. Прежние методы сначала создают некоторую большую решетку универсальным способом из полиномиального и затем оптимизируют её с помощью нахождения меньших по размерам подрешёток. Наш метод, напротив, основывается на оптимизации сперва, что впоследствии приводит к оптимизации меньших по размерам решёток.Используя наш метод, можно построить первое элементарное доказательство атаки Boneh-Durfee для малых значений секрета экспоненты RSA с . Кроме того, мы идентифицируем структуру подрешётки при атаке Jochemsz-May для малых экспонент CRT-RSA . К сожалению, в отличие от атаки Boneh-Durfee, для атаки Jochemsz-May подрешётка не поможет асимптотически улучшить требуемую оценку. Вместо этого на практике мы способны атаковать гораздо большие значения уменьшая с помощью LLL решётки с меньшим размером.
Ключевые слова: линеаризация, малые решётки, малые корни, экспонента с малым значением секрета, RSA, CRT-RSA.

Введение

Криптосистема RSA на текущий момент является наиболее распространённой криптосистемой. Для того, чтобы выполнить расшифровку или генерацию подписей, элемент увеличивается до степени , где это секретный ключ. Чтобы ускорить этот процесс, можно было бы использовать малое значение . Тем не менее, если , Wiener [1] используя метод длительного деления показал, что можно восстановить даже из общих параметров и за полиномиальное время. Этот результат впоследствии был улучшен Boneh и Durfee до, используя метод решёток [2].

Другая возможность увеличить скорость работы процесса расшифровки и генерации подписей была предложена Quisquater и Couvreur [3]. Они использовали знание первой факторизации для вычисления по модулю и по модулю и затем совместили этот результат, используя Китайскую теорему об остатках (CRT). Время работы этого процесса в среднем в 4 раза быстрее, чем при стандартной расшифровке. Чтобы в дальнейшем уменьшить число требуемых операций следует дополнительно использовать малые экспоненты CRT, то есть необходимо выбрать такое, чтобы оба значения и были малы.

На Crypto’07 Jochemsz и May [4] впервые представили атаку на экспоненты CRT, меньшие выполнимую за полиномиальное время. Однако, экспериментальные результаты Jochemsz и May для малоразмерных решёток были гораздо лучше теоретических предположений. К примеру, используя решётку размером 56 теоретически ни одна атака не должна сработать. На практике, решётки с таким размером достаточно для восстановления секретных ключей размером, вплоть до . Такое расхождение между теоретическим предположением и полученными практическими результатами выявляют то, что используемая структура решётки не оптимальна. Это привело Jochemsz и May к предположению о том, что анализ структур подрешётки может привести к теоретически идеальной оценке.

В данной работе мы предлагаем метод, который можно применить в случае атаки на малые экспоненты CRT. Наш новый подход подразумевает меньшие по размеру решётки, чем в атаке Jochemsz и May, и полное объяснение расхождения между практическими результатами Jochemsz и May и их теоретическим анализом. К сожалению, наш анализ показал, что данные решётки асимптотически приводят к той же оценке , как в [4]. Таким образом, ответом на предположение Jochemsz и May стало улучшение оценки снизу.

Хотя мы и не получили асимптотических улучшений, наш новый подход позволяет нам реализовать атаку на большие значения , на практике по сравнению с [4], используя решётки малых размеров. Мы применили наш алгоритм и показали, что, например, для 2000-битного мы можем эффективно восстановить 47-битные , в то время как метод [4] позволяет восстановить только лишь примерно 35-битные за то же время.

Наш метод основывается на решётках и использует подход открытой линеаризации, представленный Herrmann и May на Asiancrypt’09 [5], который можно рассматривать в качестве гибридного метода обычной линеаризации и метода Коперсмита [6]. Основной идеей открытой линеаризации является выполнение на первом шаге линеаризации на начальном полиноме и сохранение полученных отношений линеаризации. Эти отношения впоследствии используются на втором шаге, где мы выполняем обратную замену для того чтобы устранить некоторые одночлены, тем самым частично открывая первичный шаг линеаризации. Для того чтобы точно вычислить полученные отношения, мы предлагаем использовать базисное вычисления Grobner.

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

Оставшаяся часть нашей работы представлена следующим образом: в разделе 2 мы рассмотрим некоторые основные результаты из теории решёток. Раздел 3 посвящен методу открытой линеаризации для случаев с малым значением экспоненты RSA с доказательством того, что .

Затем мы применим наш метод для атаки на малые значения экспоненты CRT в разделе 4, где мы получим оценку Jochemsz и May для малоразмерных решёток. В разделе 5 мы продемонстрируем, что наши улучшенные решётки приводят к лучшим практическим результатам при атаке на малые значения экспоненты CRT.

Основные понятия

Перед тем как мы объясним детали открытой линеаризации и того как исползовать её для улучшения анализа малых значений экспоненты CRT, мы хотим предоставить некоторую основную информацию о теории решётки и методе Куперсмита, основанном на решётках [6].

Решётка это дискретное дополнительная подгруппа . Что есть для набора линейно независимого базиса векторов , набор

называемый решёткой. Можно описать решётку его базисной матрицей , в которую мы записываем векторы как векторы строк.

Пусть будет решёткой с базисом и пусть будет результатом применения ортогонализации Грамма-Шмидта для базисных векторов. Затем детерминант определяется как . Для полноранговой решётки, то есть , детерминант решётки будет равен абсолютному значению детерминанту решётки базисной матрицы.

Решётки являются очень полезными в криптоанализе в основном из-за эффективного и стойкого алгоритма уменьшения решётки Lenstra, Lenstra и Lovґasz [7]. Это, так называемый, LLL алгоритм выводит приближённое значение наименьшего вектора решётки за полиномиальное время в цепочке битов входных значений базисной матрицы и размерности решётки. Используя LLL алгоритм как блок построения, Coppersmith [8], [9]] разработал строгий алгоритм, который позволяет эффективно вычислить малые корни двумерных полиномов над целыми числами или инвариантными модульными полиномами. К тому же он задал эвристическое расширение мультипликативных полиномов.

Идея Coppersmith заключается в том, чтобы построить при входящих значениях некоторого полинома набор взаимно-простых полиномов, которые содержат одни и те же корни над целыми числами. Затем можно использовать стандартные исключения и методики исключения корней для получения этих корней. Howgrave-Graham[10] простым образом переформулировали метод Coppersmith’а, который определяется следующим условием.

TemplateTheoremIcon.svg Теорема Теорема 1 (Howgrave-Graham)
Пусть есть полином для переменных с одночленами. В дальнейшем пусть будет положительным целым числом.
Доказательство
Предположим, что
  1. ., где и
  2. .
Где нормальное значение определяется как нормальное Эвклидово значение вектора коэффициента. Тогда сохраняется над целыми числами.


Открытая линеаризация и атака Boneh-Durfee

В этом разделе мы покажем применение метода открытой линеаризации, представленного Herrmann и May [5], для атаки на RSA с малым значением секрета экспоненты . Это приведёт к простому доказательству оценки Boneh-Durfee .

В 1999 Boneh и Durfee [2] показали с помощью атаки Куперсмидта, основанной на решётках, что секретные ключи RSA меньше, чем можно восстановить за полиномиальное время. Время атаки зависит от уменьшающей некоторого большого базиса матрицы В, которые зависят от . Оказалось, что связанные решётки состоят из малоразмерных подрешёток , с помощью которых можно показать улучшенную границу .

Идентификация и анализ этой подрешётки , однако, является сложной задачей, из-за того что базис этой решётки не является более треугольным и поэтому вычисления детерминанта решётки необходимо здесь в большей степени. Boneh и Durfee разработали для этого анализа понятие так называемой геометрической прогрессивной матрицы, которая позволяет применять эти нетреугольные базисы решётки. Blomer и May [11] последовали другому предположению и показали, что нет асимптотического влияния на детерминант при исключении некоторых определённых столбцов. Это позволило им перестроить некоторую треугольную структуру базиса матрицы. Оба подхода, однако, являются довольно сложными для оптимизации базисов решётки.

В отличие от методов [2] и [12] наш новый подход не будет оперировать базисом матрицы, а будет работать с основными полиномами, из которых был получен базис этой матрицы. Это напрямую приведёт малоразмерной подрешётке с базисом треугольной структуры, которая будет использоваться для более простого вычисления детерминанты.

Выбранный метод для этой задачи заключается в подходе открытой линеаризации [5]. Однако, перед тем как мы покажем наш метод кратко опишем исходную атаку Boneh-Durfee для того, чтобы проиллюстрировать их сходства и различия. Анализируемый полином берётся из уравнения ключа RSA

Перепишем это как:

И найдём для малых модульных корней полинома

Поэтому мы зафиксируем целое значение m и введём полиномы

и

Базис решётки строится с помощью векторов коэффициента так называемых x-сдвигов для как базис векторов.

Рисунок 1. Базис матрицы Boneh-Durfee для m = 2, t = 1

Значения X и Y определяют верхние границы размерности решений. Помимо этого мы используем так называемые y-сдвиги для , где – некий параметр, который необходимо оптимизировать. На рисунке 1 показан пример таких параметров и . Отметим, что векторы коэффициента этого сдвига полиномов и Записаны как строки вектора.

Улучшенный анализ Boneh и Durfee показал, что можно получить идеальные значения для X и Y, если использовать только подмножество y-сдвигов. В нашем примере это означает исключении и . Следовательно, результирующий базис решётки не будет больше треугольным, поэтому получение закрытой формулы детерминанты для основных значений и сложная задача.

Теперь используем метод открытой линеаризации для построения базиса решётки, которой будет присущ наилучшая на текущее время асимптотическая оценка и которая сохраняет свойства триангулярности.

Первым шагом общего процесса работы будет получение подходящей линеаризации ортогонального полинома. В нашем случае, мы связываем между собой одночлены следующим образом

Это приводит нас к линейному полиному и добавочному отношению ,полученному из этой замены. Хоть метод Куперсмита является конструкционным методом применимым для полиномиальных уравнений и не дающим улучшенной ограниченности в случае линейных уравнений, теперь мы можем построить базис решётки используя в точности те же x-сдвиги, что и в исходной атаке Boneh-Durfee. То есть мы строим полиномы

для

И используем их векторы коэффициента как базис векторов. Очевидно, что это приводит к получению оценки Винера .

Однако, если мы также используем y-сдвиги вида , тогда мы получим некоторое преимущество. Это может показаться странно на первый взгляд, так как одночлен даже не представлен в нашем новом полиноме . Причина улучшения оценки становится понятной, когда мы включаем полученное отношение и используем его для замены каждого существующего на .


Рисунок 2. Решётка Boneh и Durfee для m = 2, t = 1, использующая открытую линеаризацию.


Преимущество можно заметить, сравнив сдвиг из исходного анализа с новым сдвигом . Как было замечено, улучшенный анализ использует только сдвиг ,а не и не . Но вводит три новых одночлена ,, и в базис решётки Boneh и Durfee – поэтому нарушается триангулярная структура.

Давайте сравним полученные результаты с нашим новым подходом открытой линеаризации, который мы изобразили на рисунке 2 для тех же параметров и . Сдвиг вводит одночлены , и . Мы заменили каждый имеющийся на , то есть мы заменили на и на . Но одночлены ,, и уже представлены в базисе решётки. Таким образом, единственным новым одночленом, который мы берём из сдвига , будет . Поэтому сохраняется трангулярная структура.

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

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

Одночлены и появляются в соответственно. В общем виде биномиальное расширение содержит одночлены, которые присутствуют в для

Поэтому сдвиг вводит один новый одночлен для всех сдвигов для и используется для построения базиса решётки. Это соответствует ограничению, которое называют увеличивающимся шаблоном из [11].

Так как y-сдвиги в исходной атаки Boneh-Durfee удовлетворяют этому ограничению увеличивающегося шаблона, как показано в [11], мы берём в нашем анализе y-сдвиги для того же набора индексов , как и в [2] . То есть мы определяем y-сдвиги

для и

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

Т.к. это набор y-сдвигов, мы знаем что и поэтому . Для с другой стороны, у нас есть. Наши условия выполняются в случае

Мы можем переписать это как что выполняется, если .

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

Мы способны точно вычислить их влияние на сдвиг полиномов из (1) и (2). Здесь мы определяем с помощью воздействие на детерминант.


Используя эти значения вместе с верхними границами, для переменных в обычных условиях мы получим оптимизированное значение и наконец выявим желаемую границу Boneh-Durfee.

Отметим, что наш выбор выполняет наши предыдущие ограничение .В заключение, этот метод открытой линеаризации предоставляет простой и изящный способ получения структуры подрешётки при атаке Boneh-Durfee. В следующем разделе мы используем тот же метод для восстановления скрытой структуры подрешётки при атаке Jochemsz-May при малых значениях CRT-RSA. Такие подрешётки ранее не были известны и стали ключевым моментом в улучшении оценки атак CRT-RSA.

Экспоненты CRT

Задача атак малых значений экспонент CRT впервые упоминается Винером [1]. На PKC’06 Bleichenbacher и May [12] показали атаку, работающую в случае, когда значительно меньше . Они начали с CRT-RSA уравнений и определили простой полином для неизвестных , указав, что и исключив :

Это уравнение может быть линеаризовано

С неизвестными

Для мы получим и . (4) точно приведёт к атаке на решётки в случае если , где . Однако, для полноразмерных , то есть , эта атака не работает.

В 2007 году Jochemsz и May [4] улучшили анализ с помощью использования полной алгебраической структуры . (3) с атакой Коперсмидта. Для случая они показали, что возможно нахождение малого решения, если . Однако, в своих экспериментах они отметили большую разницу между теоретически предполагаемой оценкой и экспериментально полученной. А именно экспериментальная была намного лучше теоретически ожидаемой, выявляя возможность наличия лучшей оценки.

Например, используя их анализ, решётки размером 56 не достаточно для реализации атаки на малые значения экспонент CRT, в то время как на практике эта задача разрешима при . Jochemsz и May выяснили, что наименьший вектор взятый из подрешётки и определяющий, что идентификация стуктуры подрешётки улучшит оценку – аналогично случаю атаки Boneh-Durfee, когда подрешётка увеличивает значение оценки с до .

В этом разделе мы показали, что это предположение ложно. Используя метод открытой линеаризации, мы получим структуру подрешётки при выполнении атаки Jochemsz-May. Это полностью объясняет экспериментальные данные в [4] и, тем самым, устраняя разрыв между практикой и теорией.

В результате, мы строим решётки более меньшего размера чем в [4], теоретический анализ которых в точности совпадает с экспериментальным, представленным нами в последующем разделе.

Разочаровывает то, что с точки зрения криптоанализа размеры CRT экспонент , для которых мы могли реализовать атаку за полиномиальное время сходится для увеличивающей размерности решётки к той же оценке , как и в [4]. Таким образом, асимптотически мы не можем улучшить оценку, пусть даже при полном использовании структуры подрешётки. Однако, мы думаем, что наш метод представляет интерес и докажет свою эффективность для реализации других атак, так как он прост и приводит к простому анализу.

Позвольте нам объяснить процесс атаки в деталях. Сначала рассмотрим полиномиальное уравнение (3). Мы поступаем также, как и в [12] и проводим практически идентичную линеаризацию.

(5)

Теперь мы используем метод открытой линеаризации с линейным полиномом , где . На следующем шаге мы строим решётку, следуя расширенному методу из [13]. Это означает, что мы используем одночлены как сдвиги и, кроме этого, вводим дополнительные сдвиги в переменные и для некоторого параметра , которым мы должны оптимизировать позже.

Преимущество открытой линеаризации заключается в том, что переменные связаны. А именно, мы получим:

Это неочевидное отношение можно вычислить просто с помощью вычислительного базиса Гробнера. Вспомним уравнения, заданные линеаризацией. Существует 5 уравнений линеаризации для 9 неизвестных, так что мы можем исключить посредством вычислительного базиса Гробнера 4 переменных и получить . (6) только для неизвестных . Это уравнение теперь используется на шаге обратной замены открытой линеаризации, где мы заменяем каждое встречающееся на одночлены и .

Чтобы проиллюстрировать наш метод используем параметры и . Это наименьшие значения, для которых Jochemsz и May [4] получили положительные экспериментальные результаты. Очевидно то, что мы не получаем положительных результатов для малых параметров из-за открытой линеаризации. Для того, чтобы улучшить оценку Bleichenbacher и May [12], нам необходимо воспользоваться отношением (6). Однако, параметры решётки и являются наименьшими, для которых возможно наличие одночленов .

Базис решётки для представлен на рисунке 3. Мы используем здесь обозначения из исходного метода Куперсмидта над целыми числами – в противопоставление модульному подходу, имеющему место в разделе 3. То есть мы строим базис решётки с коэффициентами векторов сдвигов полиномов в качестве столбцов(см. [6] для деталей). Для простоты мы опустим левую и правую части базиса матрицы, которые состоят из инверсии соответствующих верхних оценок одночленов на её диагонали. Входные значении, которые поступают при замене на рисунке 3 выделены полужирным шрифтом.

Для реализации атаки на решётку нам необходимо ввести условие, где (см. [6]). В нашем примере вычисление детерминанты базиса матрицы будет выглядеть следующим образом:


Рисунок 3. Матрица открытой линеаризации полинома для m = 2, t = 1

Мы получили верхние границы для неизвестных , соответственно. Таким образом, при условие уменьшается до . Это в точности соответствует экспериментальным результатам Jochemsz и May для параметров .

Теперь выполним асимптотический анализ и начнём с анализа простейших случаем без каких-либо дополнительных сдвигов. То есть сдвиг мы используем только в одночленах , но нам необходимо исключить все одночлены, которые делятся на , так как их можно записать как линейную комбинацию . (6).

Для вычисления значения детерминанта мы начнём с подсчёта числа сдвигов полиномов, каждый из которых взаимосвязан по фактору А с детерминантом. Число сдвигов полиномов эквивалентно числу одночленов множества.

Их число можно получить путём

Пусть определение размера первого набора будет зависеть от этого подсчёта. Запишем для некоторой резервной переменной для преобразования неравенства в равенство. Если мы установим и , то число наборов для выполнения равенства

с

Будет точным числом упорядоченных разделением на частей. Запишем , затем получаем искомую 6-ю часть выбирая 5 из знаков, как точки разрыва для части. Вероятность этого будет .

Размер второго набора получен в простом виде, при этом нам необходимо, чтобы . В таком случае число наборов будет . В заключение, мы получаем для данного числа сдвигов

Второй частью определения деерминанты будет нахождение одночлена в базисе решётки. Это будет произведение диагональных значений на входе в субматрицу слева на рисунке 3, которую можно опустить. Как упоминалось ранее, диагональные входные значения состоят из инверсий верхней оценки одночлена соответствующей строки. Конкретное вычисление приводится в приложении А, а здесь мы запишем только результат.

Напомним, что установленным условием для атаки на решётку является . С предыдущими полученными значениями и пренебрежением малозначащими значениями, такими как , мы можем записать детерминант как

Если мы используем верхние оценки для ограничения размера переменных мы получим условия

Это аналогичная асимптотическая оценка той, которая была получена Jochemsz и May [4] без учёта дополнительных сдвигов. Так, к сожалению, наша новая решётка не улучшает асимптотическую оценку [[4]. Но, в отличие от [4] нашему подходу треуется меньшие по размеру решётки. Асимптотически [4] нуждается в LLL уменьшении размера решётки , в то время как нашему подходу необходимы только половина этого значения . Рисунок 4 показывает сравнение двух методов в значении размерности которые могут быть атакованы.


Рисунок 4.Сравнение достижимой границы, зависящей от размерности решетки


Так как наш подход позволяет реализовать атаку на большее значение CRT экспонент на практике мы также хотим подчеркнуть тот факт, что в отличие от [4] экспериментальное поведение нашей атаки может быть полностью описано нашим теоретическим анализом – таким образом также объясняя экспериментальные результаты [4]. Мы покажем это в следующем разделе.

Если мы также будем использовать так называемые дополнительные сдвиги, то тогда мы лишимся улучшенной оценки как в [4]. Анализ можно выполнить тем же способом, что и в случае с дополнительными сдвигами. Мы приводим данные вычисления в приложении В.

Эксперименты

Существует 2 причины для проведения различных экспериментов по атаке на CRT-RSA. Во-первых, мы хотели показать, что наш анализ из раздела 4 является оптимальным. То есть, экспериментальное поведение может быть в точности предсказано анализом, и нет возможности улучшить оценку с помощью этого подхода. Во-вторых, так как наш метод, основанный на решётках, является эвристическим, мы должны проверять, будут ли получаемые нами полиномы после уменьшения решётки взаимно-простыми, и таким образом выявление существование возможности восстановления их корней.

Таблица 1. Экспериментальные результаты



параметры решетки
dim
LLL - время
LLL - время(s)
1000 bit
1000 bit
1000 bit
1000 bit
1000 bit
11 bit
18 bit
22 bit
24 bit
29 bit
0.0096
0.0178
0.0226
0.0244
0.0291
m=2, t=1, dim=30
m=3, t=1, dim=60
m=3, t=2, dim=93
m=4, t=1, dim=105
m=4, t=2, dim=154
56
115
-
-
-
14
6100
-
-
-
2
258
3393
7572
61298
2000 bit
2000 bit
2000 bit
2000 bit
21 bit
35 bit
45 bit
47 bit
0.0096
0.0178
0.0226
0.0244
m=2, t=1, dim=30
m=3, t=1, dim=60
m=3, t=2, dim=93
m=4, t=1, dim=105
56
115
-
-
40
20700
-
-
4
613
13516
34305
5000 bit
5000 bit
5000 bit
48 bit
89 bit
113 bit
0.0096
0.0178
0.0226
m=2, t=1, dim=30
m=3, t=1, dim=60
m=3, t=2, dim=93
56
-
-
379
-
-
39
5783
74417
10000 bit
10000 bit
96 bit
179 bit
0.0096
0.0178
m=2, t=1, dim=30
m=3, t=1, dim=60
56
-
2500
-
360
31226

Мы повторно осуществляем атаку [4] и используем в экспериментах те же модульные размерности и параметры решётки, что и в [4]. Таблица 1 ясно показывает увеличение скорости при уменьшенном LLL. К примеру, с параметрами и наш метод в 20-30 раз быстрее его аналога, предложенного Jochemsz и May. Как упоминалось ранее, это происходит из-за уменьшенной размерности решётки. В то время как методу Jochemsz и May требуется уменьшение размерности решётки до 115, нашей решётке 60. Из-за меньшей размерности решётки мы можем производить эксперименты при наборе параметров, которые не рассматривались ранее.

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

Мы проводили наши эксперименты, используя 4.1.1. и алгоритм уменьшения Нгуена и Стехеля [13]. Вычисления проводились на процессоре Quad Core Intel Xeon с тактовой частотой 2.66 GHz.

(Приложение A) Подсчет (Приложение A) Подсчет ♯ u , ♯ v , ♯ w , ♯ x {\displaystyle \sharp u,\sharp v,\sharp w,\sharp x}

Одночлены, относящиеся к определителю, являются конкретными одночленами , которые не содержат переменную . Обозначим такой одночлен . Чтобы посчитать число , относящихся к определителю, мы поступим следующим образом.

Пусть . Имеем , , которые трансформируются в для слабой переменной и .

Число таких наборов – это просто число 4-частных , которые являются . Из этих наборов мы должны удалить те, для из-за замены . Число таких наборов - . Для поступаем аналогично и получаем . Мы проделываем это для всех и заканчиваем при, где получим .

Теперь мы знаем число появления для каждого . Для того, чтобы подсчитать общее число u, мы вычисляем взвешенную сумму следующим образом.

Используя тождества и , в конечном счете получим:

Таким образом,

Подсчет числа появлений и может быть выполнен аналогичным путем и мы получим:

(Приложение B) Улучшение границ с использованием экстра сдвигов

Далее мы покажем, что возможно улучшить границу с до , используя так называемые экстра сдвиги. В этом случае мы используем набор сдвигов:

одночлен для

Чтобы оценить число сдвигов, можно использовать комбинаторное доказательство, как в разделе 4, и посчитать число всех одночленов минус число одночленов, имеющих . Однако, мы хотим использовать вычислительный подход, так что просто оценим серию сумм.

Сдвиг одночленов можно охарактеризовать множеством , где – множество всех сдвигов, а – сдвиги, которые должны быть удалены из-за замены .

Заменяя , итоговое число сдвигов будет равно:

Аналогичным образом получаем показатели переменных , относящиеся к определителю матрицы. Например, чтобы посчитать число появлений , мы вычисляем:

Для других значений получаем:

Мы используем эти значения вместе с верхними границами для вычисления определителя матрицы. После этого, мы можем решить условие для и оптимизировать значение для максимизации . Мы получаем , что в конечном итоге приводит к границе .

Контакты авторов материала

  1. Horst G¨ortz Institute for IT-Security Faculty of Mathematics Ruhr University Bochum, Germany E-mail: [1]
  2. Horst G¨ortz Institute for IT-Security Faculty of Mathematics Ruhr University Bochum, Germany E-mail: [2]

Литература

  1. 1,0 1,1 [Wie90] Wiener, M.J.: Cryptanalysis of Short RSA Secret Exponents. IEEE Transactions on Information Theory 36(3), 553–558 (1990)
  2. 2,0 2,1 2,2 2,3 [BD99] Boneh, D., Durfee, G.: Cryptanalysis of RSA with Private Key d Less than N 0.292. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 1–11. Springer, Heidelberg (1999)
  3. [QC82] Quisquater, J.J., Couvreur, C.: Fast Decipherment Algorithm for RSA Public-key Cryptosystem. Electronics Letters 18, 905 (1982)
  4. 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 4,11 4,12 4,13 4,14 4,15 4,16 4,17 [JM07]Jochemsz, E., May, A.: A Polynomial Time Attack on RSA with Private CRT-Exponents Smaller Than N 0.073. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 395–411. Springer, Heidelberg (2007)
  5. 5,0 5,1 5,2 [HM09] Herrmann, M., May, A.: Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much? In: Matsui, M. (ed.)ASIACRYPT 2009. LNCS, vol. 5912, pp. 487–504. Springer, Heidelberg(2009)
  6. 6,0 6,1 6,2 6,3 [Cop97] Coppersmith, D.: Small Solutions to Polynomial Equations, and Low ExponentRSA Vulnerabilities. J. Cryptology 10(4), 233–260 (1997)
  7. [LLL82] Lenstra, A.K., Lenstra, H.W., Lov´asz, L.: Factoring Polynomials with Rational Coefficients. Mathematische Annalen 261(4), 515–534 (1982)
  8. [Cop96a] Coppersmith, D.: Finding a Small Root of a Bivariate Integer Equation;Factoring with High Bits Known. In: Maurer [Mau96], pp. 178–189 (1996)
  9. [Cop96b] Coppersmith, D.: Finding a Small Root of a Univariate Modular Equation.In: Maurer [Mau96], pp. 155–165 (1996)
  10. [HG97] Howgrave-Graham, N.: Finding Small Roots of Univariate Modular Equations Revisited. In: Darnell, M.J. (ed.) Cryptography and Coding 1997.LNCS, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
  11. 11,0 11,1 11,2 [BM01] Blomer, J., May, A.: Low Secret Exponent RSA Revisited. In: Silverman, J.H.(ed.) CaLC 2001. LNCS, vol. 2146, pp. 4–19. Springer, Heidelberg (2001)
  12. 12,0 12,1 12,2 12,3 [BM06] Bleichenbacher, D., May, A.: New Attacks on RSA with Small Secret CRT-Exponents. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.)PKC 2006. LNCS, vol. 3958, pp. 1–13. Springer, Heidelberg (2006)
  13. 13,0 13,1 [JM06] Jochemsz, E., May, A.: A Strategy for Finding Roots of Multivariate Poly- nomials with New Applications in Attacking RSA Variants. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 267–282. Springer, Heidelberg (2006)

14.[Mau96] Maurer, U.M. (ed.): EUROCRYPT 1996. LNCS, vol. 1070. Springer, Heidelberg (1996)