На сегодняшний день многие ведущие ученые активно работают над созданием квантовых компьютеров. Корпорация GOOGLE, совместно с NASA и ассоциацией USRA, подписали контракт о производстве квантовых процессоров с компанией D-Wave.
Квантовые компьютеры смогут разрушить криптосистемы, которые широко используются в практике. Конкретно, системы, основанные на задаче факторизации целых чисел – RSA. Данная криптосистема RSA используется в разных продуктах, на разных платформах и в различных сферах.
Технология шифрации RSA BSAFE используется приблизительно 500 миллионами пользователей во всем мире. Так как, в основном, в технологиях шифрования используется RSA алгоритм, то его можно считать одной из самых распространённых криптосистем открытого ключа с тенденцией развития вместе с развитием интернета.
Исходя из этого, разрушение RSA повлечет за собой легкий взлом большинства продуктов, что может перерасти в полный хаос (1).
Одной из альтернатив пост-квантовых систем являются многовариантные крипто-системы открытого ключа(Multivariate Public-Key Cryptosystems-MPKCs).
MPKCs – это криптосистемы открытого ключа, где односторонняя функция с потайным ходом (trapdoor one-way function) принимает форму многовариантного квадратичного полиномиального отображения над конечным полем.
Открытый ключ данной системы обычно задается набором квадратичных многочленов:
P = (p1(w1, . . . , wn), . . . , pm(w1, . . . , wn))
p1(w1, . . . , wn) = z1
…
Pm(w1, . . . , wn) = zm
pi– нелинейные многочлены в (w1, . . . , wn).
Процедура шифрования или оценки происходит с помощью оценки данных многочленов при конкретном значении.
Для построения мультивариантных подписей использовали квадратное уравнение:
m = x12+b x22(mod n), где n=pq, p и q – простые большие числа.
Для подписи сообщения m надо найти одно из многих решений данного уравнения, что просто, если мы знаем факторизацию n.
Полард и Шнор (Pollard, Schnorr) нашли вероятностный алгоритм решения данного уравнения без знания факторизации n, этим сломали данную систему.
Диффи и Фел (Diffie и Fell) пытались создать систему с помощью композиции обратимых линейных отображений и простых отображений вида: M(x1, x2) = (x1 + g(x2), x2).
Данные отображения легко обратить, но трудно расшифровать. Но так как авторы использовали только две переменные, очень трудно построить данную криптосистему, которая является безопасной и имеет открытый ключ практического размера.
Матсумато, Имай, Харашима и Миягавф (Matsumoto, Imai, Harashima, Miyagawa), построили криптосистему, которая использовала квадратичные многочлены в роли открытого ключа. Вскоре данная система была взломана(2).
Шамир (Shamir) предложил треугольную конструкцию – “Birational Permutations”[3]. Треугольные отображения можно очень быстро оценить и обратить. Нужно также учесть, что на малом конце треугольной системы переменная отображается в простые функции от самой себя. На большем из концов одна переменная появляется только в одном уравнении. Остальные уравнения содержат больше переменных.
Запишем квадратичную часть центральных многочленов yi = qi(x) в качестве билинейных форм, возьмем симметричную матрицу, обозначающую симметричный дифференциал центральных многочленов.
qi(x + l) − qi(x) − qi(l) + qi(0) := lT Mix
Ранг Mi монотонно возрастает с увеличением i. Данная система уязвима к ранговым атакам[4], основанным на линейной алгебре. Поэтому треугольные конструкции не могут быть использованы отдельно.
Матсумато и Имай (Matsumoto , Imai) предложили схему C*, они использовали квадратичную систему Q из мономиального преобразования f→ y = f1+q^p, для какого-нибудь p, над расширением F конечного поля K.
F = GF(qn), K = GF(q). f и y из F соответствуют векторам из K. Джакьюз Патарин (Jacques Patarin) осуществил успешную атаку на данную систему[5]. Были предложены разные варианты улучшения C*, например, SFLASH, использующая технику «Plus-Minus». Позже Дубоис, Фоуку, Шамир и Штерн (Dubois, Fouque, Shamir, Stern) осуществили успешную атаку на данную систему.
HFE (Hidden Field Equations) является производной C*. В данной схеме вместо того, чтобы использовать одночлен, используемый C *, мы используем многочленное преобразование:
f→ y = ∑0<=i<=j<=raijfq^i+q^j+ ∑0<=i <=rbijfq^i+c
и строим систему Q , используя явный базис F в K. Работа с закрытым ключом происходит в F, открытый ключ дается в K.
Это отображение не является одним к одному, поэтому также нужно использовать контрольную сумму.
Сложность этой схемы предстовляет O(ne2 log e+e3), e- это максимальная степень Q.
Зафиксированы атаки на данную систему, но когда мы увеличиваем e, данные атаки не работают. Но надо отметить, что при этом эффективность системы очень уменьшается.
Были разработаны системы электронной подписи Unbalanced Oil and Vinegar (UOV).
Система Q задается m квадратичными многочленами в n=m+v переменных,
(w1, … ,wm;wm+1, …,wm+v). Первые m переменных называются «переменные oil» (o), а v остальных переменных – «переменных vinegar» (vin).
Каждый многочлен может содержать квадратичные члены вида: o x vin или v x vin, но не может содержать квадратичные члены вида: o x o. Систему Q легко решить, фиксируя произвольные значения переменных vin и решая полученную систему путем исключения Гаусса. P должен скрывать различие между переменными o и vin. Следует отметить тот факт, что данная схема имеет много эквивалентных ключей, вычисление части закрытых ключей приводит к успешной атаке на данную систему. В случае, когда v=m, Кипнис и Шамир (Kipnis, Shamir) реализовали успешную атаку (6) на данную систему, но когда v>2m, данная атака безуспешна.
В схеме Rainbow мы используем экземпляры UOV итеративно. Первый экземпляр содержит v2-v1 многочленов с v2-v1 переменными o и v1 переменнымиvin. Второй экземпляр содержит v3-v2 многочленов с v3-v2 переменными o и v2 переменнымиvin. Последний экземпляр содержит vt+1-vlмногочленов сvt+1-vlпеременными o и vtпеременнымиvin. Полученная система содержит vt+1- v1 многочленов с vt+1 переменными. Данную систему легко решить рекурсивно, применяя принцип UOV. Берем v1 переменных vin первого экземпляра UOV, решаем этот экземпляр в v2-v1 переменных o, а затем рассматриваем v2 (v1 + v2-v1 ) переменных как переменные vin второго экземпляра UOV и т.д.
Как мы видим, в схеме Rainbow надо решить большее количество систем, чем в случае UOV, но эти системы являются меньшего размера.
TTS – это улучшенная схема Rainbow с разреженными (sparse) коэффициентами. Системы UOV уязвимы к ранговым атакам (rank attacks).
Т.к. TTS имеет структуру Rainbow она уязвима, ко всем ее атакам, а также из за разреженности ее также можно атаковать со стороны линейной алгебры(7).
Стоит отметить, что нужно обеспечить безопасность малой вычислительной техники:
RFID, беспроводных датчиков, PDA и т.д. RSA не может быть использована в данной ситуации из-за сложности вычислений. MPKCs является хорошей альтернативой для этого случая.
Как мы видим, несмотря на то, что многовариантные криптосистемы открытого ключа являются многообещающей альтернативой для пост-квантовой эпохи, на них фиксируется множество атак, и они является недостаточно эффективными.
Очевидно, что исследование MPKC уже представило новые математические проблемы, которые требуют новых математических идей. Для того, чтобы добиться нужных результатов, нужно еще провести огромную работу над данными системами со стороны алгебраической геометрии.
РАБОТА ВЫПОЛНЕНА В РАМКАХ НАУЧНОГО ГРАНТА «НАЦИОНАЛЬНОГО НАУЧНОГО ФОНДА ШОТА РУСТАВЕЛИ» [№ YS15_2.1.2_9].
Библиографический список
- Гагнидзе А.Г., Явич М.П., Иашвили Г.Ю. Пост-квантовые криптосистемы // Современные научные исследования и инновации. 2016. № 5 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2016/05/67264
- Okamoto, E. and Nakamura, K.: Evaluation of public key cryptosystems proposed recently. In Proc 1986’s Symposium of cryptography and information
security, volume D1. 1986 - Shamir, A.: Efficient signature schemes based on birational permutations. In Advances in Cryptology — CRYPTO 1993, volume 773 of Lecture Notes in Computer Science, Douglas R. Stinson, ed., Springer. 1993
- Coppersmith, D., Stern, J., and Vaudenay, S.: The security of the birational permutation signature schemes. Journal of Cryptology. 1997
- Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt’88. In Advances in Cryptology — CRYPTO 1995, volume 963 of Lecture Notes in Computer Science. Don Coppersmith, ed.,
Springer. 1995 - Kipnis, A. and Shamir, A.: Cryptanalysis of the oil and vinegar signature scheme. In Advances in Cryptology — CRYPTO 1998, volume 1462 of Lecture Notes in Computer Science. Hugo Krawczyk, ed., Springer. 1998.
- Ding, J., Schmidt, D., and Yin, Z.: Cryptanalysis of the new tts scheme in ches 2004. Int. J. Inf. Sec., 5(4). 2006
Количество просмотров публикации: Please wait