Теорема Копперсмита

15.12.2020

Теорема Копперсмита (метод Копперсмита) — теорема, позволяющая эффективно найти все нули нормированных многочленов по определённому модулю.

Теорема используется в основном для атак на криптосистему RSA. Этот метод является эффективным, если экспонента кодирования имеет достаточно малое значение, либо когда известна часть секретного ключа. Теорема также связана с LLL-алгоритмом.

Описание

Введение

Теорема предлагает алгоритм эффективного нахождения корней нормированного многочлена f {displaystyle f} по модулю N {displaystyle N} , которые меньше чем X = N 1 / d {displaystyle X=N^{1/d}} . Если X {displaystyle X} будет малым, то алгоритм будет работать быстрее. Преимущество теоремы это возможность находить малые корни многочлена по составному модулю N {displaystyle N} . Если же модуль — простое число, то нет смысла использовать теорему Копперсмита. Намного эффективнее будет использовать другие способы нахождения корней многочлена.

Маленькая экспонента кодирования

Чтобы уменьшить время шифрования или проверки подписи, желательно использовать маленькое e { extstyle e} (экспонента кодирования). Наименьшее возможное значение — 3 {displaystyle 3} , однако рекомендуется использовать e = 2 16 + 1 = 65537 {displaystyle e=2^{16}+1=65537} (для защиты от некоторых атак). При использовании значения 2 16 + 1 {displaystyle 2^{16}+1} на проверку подписи требуется 17 умножений ( ∀ e ⩽ ϕ ( N ) {displaystyle forall eleqslant phi (N)} , где ϕ ( N ) {displaystyle phi (N)} — порядок мультипликативной группы Z N {displaystyle mathbb {Z} _{N}} , возможно около 1000). Атаки ориентированные на использование маленького e { extstyle e} не всегда действенны.

Самые мощные атаки на маленькую экспоненту кодирования основываются на теореме Копперсмита, которая имеет много приложений, одно из которых атака Хастеда (Hasted).

Атака Хастеда

Предположим один отправитель отправляет одно и то же сообщение M {displaystyle M} в зашифрованном виде определённому количеству людей P 1 ; P 2 ; . . . ; P k {displaystyle P_{1};P_{2};...;P_{k}} , каждый из которых использует одну и ту же маленькую экспоненту кодирования e { extstyle e} , скажем e = 3 {displaystyle e=3} , и различные пары ⟨ N i , e ⟩ {displaystyle leftlangle N_{i},e ight angle } , причем M < N i , ∀ i {displaystyle M<N_{i},forall i} . Отправитель зашифровывает сообщение, используя поочередно открытый ключ каждого пользователя, и отсылает его соответствующему адресату. Тогда, если противник прослушает канал передачи и соберет k ⩾ 3 {displaystyle kgeqslant 3} переданных шифротекстов, то он сможет восстановить сообщение M {displaystyle M} .

Доказательство

◻ {displaystyle Box } Предположим противник перехватил C 1 , C 2 {displaystyle C_{1},C_{2}} и C 3 {displaystyle C_{3}} , где C i = M 3 mod N i {displaystyle C_{i}=M^{3}{mod {N}}_{i}} . Мы предполагаем, что N 1 , N 2 , N 3 {displaystyle N_{1},N_{2},N_{3}} взаимно просты, иначе наибольший общий делитель отличный от единицы означал нахождение делителя одного из n {displaystyle n} . Применяя китайскую теорему об остатках к C 1 , C 2 {displaystyle C_{1},C_{2}} и C 3 {displaystyle C_{3}} получим C ∈ Z N 1 , N 2 , N 3 {displaystyle Cin mathbb {Z} _{N_{1},N_{2},N_{3}}} , такое что C i ≡ C mod N i {displaystyle C_{i}equiv C{mod {N}}_{i}} , которое имеет значение C = M 3 mod N 1 N 2 N 3 {displaystyle C=M^{3}{mod {N}}_{1}N_{2}N_{3}} . Однако, зная что M < N i , ∀ i {displaystyle M<N_{i},forall i} , получаем M 3 < N 1 N 2 N 3 {displaystyle M^{3}<N_{1}N_{2}N_{3}} . Поэтому C = M 3 {displaystyle C=M^{3}} , то есть противник может расшифровать сообщение M {displaystyle M} взяв корень кубический от C {displaystyle C} .

Для восстановления сообщения M {displaystyle M} с любым значением открытой экспоненты кодирования e { extstyle e} , необходимо противнику перехватить k ⩾ e {displaystyle kgeqslant e} шифротекстов. ◼ {displaystyle lacksquare }

Формулировка

Пусть N ∈ Z {displaystyle Nin mathbb {Z} } и f ( x ) ∈ Z [ x ] − {displaystyle f(x)in mathbb {Z[x]} -} нормированный многочлен степени d {displaystyle d} . Пусть X = N 1 d − ε {displaystyle X=N^{{ frac {1}{d}}-varepsilon }} , ε ⩾ 0 {displaystyle varepsilon geqslant 0} . Тогда по паре ⟨ N , f ⟩ {displaystyle leftlangle N,f ight angle } атакующий эффективно найдет все целые числа | x 0 | < | X | {displaystyle leftvert x_{0} ightvert <leftvert X ightvert } , удовлетворяющие f ( x 0 ) ≡ 0 mod N {displaystyle f(x_{0})equiv 0{mod {N}}} . Время выполнения определяется выполнением LLL-алгоритма на решетке размерности O ( ω ) {displaystyle O(omega )} , где ω = min { 1 ε , log 2 ⁡ N } {displaystyle omega =min left{{ frac {1}{varepsilon }},log _{2}{N} ight}} .

Доказательство

◻ {displaystyle Box } Пусть m > 1 {displaystyle m>1} натуральное число, которое мы определим позже. Определим

g i , k ( x ) = x i ( f ( x ) / M ) k {displaystyle g_{i,k}(x)=x^{i}(f(x)/M)^{k}}

Мы используем в качестве основы для нашей решетки L {displaystyle L} полиномы g i , k ( x X ) {displaystyle g_{i,k}(xX)} для i = 0 , . . . , d − 1 {displaystyle i=0,...,d-1} и k = 0 , . . . , m − 1 {displaystyle k=0,...,m-1} . Например, когда d = 3 {displaystyle d=3} и m = 3 {displaystyle m=3} мы получаем матрицу решетки, натянутую на строки:

[ 1 X X 2 − − − X 3 M − 1 − − − X 4 M − 1 − − − X 5 M − 1 − − − − − − X 6 M − 2 − − − − − − X 7 M − 2 − − − − − − X 8 M − 2 ] {displaystyle {egin{bmatrix}1&X&&X^{2}-&-&-&X^{3}M^{-1}&-&-&-&X^{4}M^{-1}&&-&-&-&X^{5}M^{-1}-&-&-&-&-&-&X^{6}M^{-2}&-&-&-&-&-&-&X^{7}M^{-2}&&-&-&-&-&-&-&X^{8}M^{-2}end{bmatrix}}} ,

где «—» обозначает ненулевые недиагональные элементы, значение которых не влияет на определитель. Размер этой решетки равен ω = m d {displaystyle omega =md} , а её определитель считается так:

det ( L ) = X ω ( ω − 1 ) / 2 M − ω ( m − 1 ) / 2 {displaystyle det(L)=X^{omega (omega -1)/2}M^{-omega (m-1)/2}}

Потребуем, чтобы det ( L ) < 2 − ω ( ω − 1 ) / 4 ω − ω / 2 {displaystyle det(L)<2^{-omega (omega -1)/4}omega ^{-omega /2}} . Отсюда следует

X < M ( m − 1 ) / ( ω − 1 ) 2 − 1 / 2 ω − 1 / ( ω − 1 ) {displaystyle X<M^{(m-1)/(omega -1)}2^{-1/2}omega ^{-1/(omega -1)}}

что можно упростить до

X < γ ω ⋅ M 1 d − ε {displaystyle X<gamma _{omega }centerdot M^{{ frac {1}{d}}-varepsilon }} ,

где ε = d − 1 d ( ω − 1 ) {displaystyle varepsilon ={ frac {d-1}{d(omega -1)}}} и 1 2 2 ⩽ γ ω < 1 2 {displaystyle { frac {1}{2{sqrt {2}}}}leqslant gamma _{omega }<{ frac {1}{sqrt {2}}}} для всех ω {displaystyle omega } . Если мы возьмем m → ∞ {displaystyle m ightarrow infty } , то получим ω → ∞ {displaystyle omega ightarrow infty } а, следовательно, и ε → 0 {displaystyle varepsilon ightarrow 0} . В частности, если мы хотим решить X < M 1 d − ε 0 {displaystyle X<M^{{ frac {1}{d}}-varepsilon _{0}}} для произвольного ε 0 {displaystyle varepsilon _{0}} , достаточно взять m = O ( k / d ) {displaystyle m=O(k/d)} , где k = min { 1 ε , log 2 ⁡ N } {displaystyle k=min left{{ frac {1}{varepsilon }},log _{2}{N} ight}} . ◼ {displaystyle lacksquare }



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2020
При цитировании и использовании любых материалов ссылка на сайт обязательна