Cryptographic analysis of the generalized ElGamal's cipher over GL(8,F₂₅₁).pdf Введение В работе рассматривается опубликованный в 2017 г. обобщённый протокол Эль-Гамаля [1], который в общем случае строится на группе матриц над конечным полем. Автор [1] предлагает использовать конкретную группу матриц размера 8 х 8 над простым конечным полем f251. Схема формирования ключа в протоколе Хехта является частным случаем схемы из протокола Шпильрайна - Ушакова [2]. В [3] показано, что если протокол Шпильрайна - Ушакова (соответственно - протокол Хехта) построен на линейной группе, то существует эффективная процедура, вычисляющая формируемый общий ключ без знания и без вычисления секретных параметров протокола. Другими словами, показана криптографическая нестойкость протокола при указанном условии. В работе приводится конкретная реализация этой процедуры, которая в данном случае существенно упрощается. 1. Протокол формирования общего секретного ключа Хехта Приведём описание протокола формирования общего секретного ключа из [1]. Предположим, что два корреспондента - Алиса и Боб - договорились о выборе линейной группы GL(8, f251) и двух матриц G и P из GL(8, f251). В процессе получения открытого ключа Алиса выбирает натуральные числа k1,k2 G n и диагональную матрицу da = diag(A1,... , Л8), Aj G f251. Затем она вычисляет матрицы A = pdap-1 и A' = Akl GAk2. Открытым ключом Алисы является матрица A'. Аналогичным образом Боб выбирает диагональную матрицу db = diag(^1,... , ^8), ^ G f251, вычисляет матрицу B = pdb P-1, выбирает натуральные числа r1,r2 G n и вычисляет матрицу B' = Bri GBr2. Открытым ключом Боба является матрица B'. Затем Алиса и Боб обмениваются ключами A' и B'. После обмена ключами Алиса вычисляет сформированный ключ K = Akl B'Ak2, а Боб вычисляет K' = Bri A'Br2. Несложно проверить, что ключи, полученные Алисой и Бобом, одинаковы: K = Akl B 'Ak2 = Akl (Bri GBr2 )Ak2 = Bri (Akl GAk2 )Br2 = Bri A'Br2 = K'. 2. Криптографический анализ протокола Хехта Предположим, что Джон перехватывает все сообщения, которые отправляют между собой Алиса и Боб, знает протокол, с помощью которого Алиса и Боб обмениваются сообщениями, и следующие элементы протокола: P, G,A',B' G GL(8, f251). Матрицы A' и B' Джон может представить следующим образом: A' = Akl GAk2 = (PDAP-1)kl g(pdap-1)k2 = (PD^1 P-1)G(PD^2 P-1), B' = Bri GBr2 = (pdb P-1)ri g(pdb P-1)r2 = (PDB1 P-1)G(PDg P-1). 8 Любую диагональную матрицу D G GL(8, f251) можно представить как D = E AfcE&, fc=1 где Ak G f251; Ek - матрица, в которой k-й элемент на диагонали равен 1 (ekk = 1), а 88 все остальные равны 0. При разложениях D^1 = Е a^E^ и D^2 = Е в,E, матрица A' i=1 j=1 имеет вид A' = (P E ajEjP-1)G(P E в,EP-1) = E (Pa^E^P-1)G(P^jejP-1) = i=1 J=1 i,j=1 = E агв,(PEjP-1)G(PE,P-1 )= E ^(PEjP-1)G(PE,P-1), где = агв,. i,j=1 i,j=1 Значения можно найти как решение соответствующей системы линейных уравнений, например методом Гаусса. После этого, подставив в правую часть вместо матрицы G матрицу B', Джон получит сформированный ключ K и сможет читать все сообщения, которые отправляют Алиса и Боб между собой: Е Sij(PEiP-1 )B'(PEj-P-1)= E 6ij(PEiP-1)(PDBlP-1)G(PDB2P-1)(PEjP-1) = i,j=1 i,j=1 = E (PDgP-1) (6ц(PEiP-1)G(PEjP-1)) (PDgP-1) = i,j=1 = (PD£ P-1) ( E ^(PEiP-1)G(PEjP-1) | (PDgP-1) = = Bri ^ E fiij(PEiP-1)G(PEjP-1)J Br2 = BriA'Br2 = K. Заключение Данная атака основана на методе линейной разложимости [3]. Для её осуществления достаточно, чтобы протокол строился на линейной группе. Необходимые вычисления выполняются методом Гаусса, который квадратичен по числу уравнений и линеен по числу неизвестных. Заметим, что достаточно найти любое частное решение соответствующей системы линейных уравнений. Уравнений в данном случае 64 (число элементов в матрице), неизвестных 64 (коэффициенты в разложении). При атаке «грубой силой» пришлось бы подбирать параметры k1, k2, r1 и r2. Этот перебор может быть ограничен, но ограничение не может быть меньше, чем порядок мультипликативной группы поля для каждого из этих параметров. Кроме того, пришлось бы подбирать ненулевые элементы поля а1,... , а8, в1,... , в8. Размер этого ключевого пространства 25016. Атака методом линейного разложения на рассматриваемый протокол является не только эффективной, но и практически реализуемой. От общей схемы атаки методом линейного разложения на протокол Шпильрайна - Ушакова [3] рассматриваемая атака отличается тем, что для неё нет необходимости строить базисы линейных подпространств, без чего не обойтись в общем случае.

Скачать электронную версию публикации