Криптографические примитивы на полупрямых произведениях групп

1.    Схема генерации ключей Диффи–Хеллмана

Пусть две стороны A и B , соединенные каналом связи, хотят стать обладателями секретного ключа K , недоступного какой-либо третьей стороне. Для этого они предварительно выбирают и публикуют большое простое число p и некоторый элемент ξ из мультипликативной группы Z _p ^∗ поля Z _p чисел по модулю p .

Сторона A случайно выбирает большое натуральное l , вычисляет число L = ^¹ и передает его стороне B . Сторона B выбирает случайное r и передает стороне A число R = £ r . По завершении обмена L ^ R стороны получают возможность вычислить общий ключ K :

R = ( £ r ) l = K = ( £ l ) r = L r .

Для того чтобы третья сторона, перехватившая сообщения L = £ l и R = £ r , cмогла вычислить ключ K , она должна найти хотя бы один из случайных показателей l, r , то есть решить задачу вычисления дискретного логарифма l = log ^ L или r = log ^ R .

2.    Полупрямые произведения

Пусть даны две группы N и H и пусть H ^ Aut ( N ) - гомоморфизм группы H в группу автоморфизмов группы N . Иными словами, пусть каждому элементу h Е H поставлен с соответствие автоморфизм ^ h ( n ) : N ^ N , так что ^ һ 1 ( ^ һ ₂ ( n )) = ^ һ 1 h ₂ ( n ). Нейтральному элементу e Е H отвечает при этом тривиальный автоморфизм группы N : ^ _e ( n ) = n .

Полупрямое произведение G = N x _v H , [3], вводится как множество пар ( n,h ) , n Е N,h Е H , с групповой операцией

( n i ,h i )( n 2 ,h 2 ) = ( n 1 ^ һ 1 ( n 2 ) ,h 1 h 2 ) .

Ассоциативность так введенного умножения легко проверяется. Нейтральным элементом группы G = N x _v H является пара ( e, e ) нейтральных элементов N и H . Обратным к ( n, h ) является элемент ( ^ h - i ( n - 1 ) , h - 1 ). Наборы ( n, e ) , n Е N и ( e, h ) , h Е H , образуют подгруппы, изоморфные N и H . Пересечение этих подгрупп состоит из единственного нейтрального элемента ( e, e ). Легко показать, что (е , h )( n, e )( e, h ) ^{- 1} = ( ^ һ ( n ) , e ), так что подгруппа N нормальна в G (инварианта относительно внутренних автоморфизмов), а действие на N внутреннего автоморфизма, отвечающего элементу ( e, h ), совпадает с действием ^ һ .

Если гомоморфизм H ^ Aut ( N ) тривиален - ставит в соответствие всем элементам H тривиальный автоморфизм группы N , полупрямое произведение сводится к декартову произведению G = N х H с операцией

( n 1 , h 1 )( n 2 , h 2 ) = ( n 1 n 2 , h 1 h 2 ) .

В противном случае в G существует нетривиальный внутренний автоморфизм, так что эта группа заведомо некоммутативна.

Группу G = N x^ H называют расширением N посредством группы H. Расширению отвечает точная последовательность морфизмов e ^ N ^ G ^ H ^ e, где левый морфизм – это вложение группы N, образом которого является нормальная подгруппа группы G, а правый морфизм отображает фактор-группу по этой нормальной подгруппе на группу H. В конструкции расширения участвуют три группы (сами группы N,H и группа Aut(N) автоморфизмов N) и один гомоморфизм H ^ Aut(N), который отображает H на некоторую подгруппу Aut(N). Конструкция становится более прозрачной, если в качестве H выбрана непосредственно некоторая подгруппа Aut(N), в частности, вся эта группа: H = Aut(N). Тогда в конструкции оказываются задействованными только N и H С Aut (N).

В любом случае построение полупрямого произведения требует знания группы Aut ( N ) автоморфизмов группы N , избранной для расширения. Проблема описания структуры групп автоморфизмов до конца решена для конечных коммутативных групп. Всякая такая группа является декартовым произведением циклических групп, а описание группы автоморфизмов циклической группы сводится к характеризации набора ее примитивных элементов: всякий автоморфизм переводит примитивный элемент в примитивный, и наоборот, всякое отображение примитивного элемента на примитивный продолжается до автоморфизма порождаемой ими группы.

Изучим структуру операции возведения в степень в полупрямом произведении групп: ( n, h ) ^s , ( n,h ) Е N х _ф H . Имеем

( n, h ) ² = ( n, h )( n, h ) = ( n^ h ( n ) , h ² ) ,

(n, h)3 = (n^h(n), h2)(n, h) = (n^h(n)^һ2 (n), h3), и так далее до

( n, h ) S = ( n^h ( n ) ^h 2 (n ) ...^һ (s-1) (n) ,hs) = (n(s) ,hs), где n (s) = n^h (n ) ^h 2 (n ) . ,.^h (s- 1) ( n ) .

Видно, что при возведении в степень элемента ( n,h ) Е N х ^ H его компоненты n Е N и h Е H преобразуются по-разному. Компонент h просто возводится с степень s , как и в кольце Z n . А вот степень n ⁽ s ) компонента n вычисляется как произведение элементов группы N , входящих в орбиту элемента n относительно последовательного действия отображения ^ y ( n ). Число элементов в этой орбите в общем случае равно периоду элемента ^ һ в группе Aut ( N ). Если этот период велик, то степень y = n ⁽ s ) оказывается произведением s различных элементов группы N , так что задача вычисления дискретного логарифма s = log n ( y ) существенно усложняется. Это и дает основание предполагать, что адекватный выбор структуры полупрямого произведения позволит предложить односторонние функции, более стойкие по сравнению с обычным дискретным логарифмом в модульном кольце.

3.    Генерация ключей на полупрямых произведениях

Пусть в публичном доступе находится элемент ( n, h ) полупрямого произведения G = N x _v H . Как и ранее, сторона A выбирает случайное l и вычисляет ( n, h ) ^l = ( n ^{( l} ) , h^l ) = ( L, h^l ), где

L = n ^{( l} ) = n^ h ( n ) ^ һ 2 ( n ) . ..^ _h ( i — i) ( n ) .

Элемент L передается стороне B . Сторона B выбирает случайное r , вычисляет ( n,h ) r = ( n ⁽ r ) ,h r ) = ( R,h ),

R = n ⁽ r ) = n^ h ( n ) ^ _h 2 ( n ) ... ^ _h ( r — i) ( n )

и передает R стороне A . Теперь стороны A и B оказываются в состоянии вычислить общий ключ K . На стороне A вычисление проводится по схеме

(n, h)l+r = (n, h)l (n, h) r = (L, h)(R,...) = (L^hi (R),...) = (K,...), а на стороне B несколько иначе:

( n, h ) r ^{+ 1} = ( n, h ) r ( n, h ) ^l = ( R, h r )( L,... ) = ( R^ h r ( L ) ,... ) = ( K,... ) .

Существенно, что недостающие на сторонах элементы h ^r ,h ^l в вычислениях не используются. Общим для двух сторон ключом становится элемент K = L^ y ( R ) = R^ y ( L )•

Чтобы вычислить ключ K по результатам перехвата L , R , необходимо знать хотя бы один из показателей l, r , а их нахождение по известным n ^{( l} ) , n ⁽ r ) эквивалентно вычислению дискретного логарифма в полупрямом произведении.

4.    Простой пример

Выберем в качестве N циклическую мультипликативную группу Z _p ^∗ поля Z _p и пусть ξ – ее примитивный элемент с периодом p — 1. Набор примитивных элементов Z p исчерпывается степенями ^ k с показателями к , взаимно простыми с ( p — 1). Каждому такому к отвечает автоморфизм ^ k ( x ) = x k , который переводит элемент ^ в ^ k . В качестве H возьмем циклическую подгруппу Aut ( Z p ), порожденную автоморфизмом ^ k ( x ). Степень ( n, k ) s элемента ( n,k ) , n Е Z p ,^ k Е Aut ( Z p ) имеет вид: ( n ⁽ s ) , ^ k s ), где

2        (ss - 1) ks ^{- 1}

y = n ^{( s} ) = nn k n ^k .. .n = n ^{k - 1} .

Видно, что для вычисления дискретного логарифма s = log _n ( y ) требуется не только найти показатель m , такой что y = n ^m , но и найти затем число s , такое что m = k— 1 . А это эквивалентно двукратному решению задачи вычисления дискретного логарифма.

5.    Некоммутативная группа порядка p3

Существуют в точности две некоммутативные группы порядка p ³ [3]. Одна из них является полупрямым произведением циклической группы N = C _p 2 порядка p ² на циклическую группу H = C p порядка p . Вторая получается как полупрямое произведение группы N = C p х C p - декартова произведения двух групп C p на ту же группу H = C p . Более предпочтительной с позиций криптографии представляется первая группа, содержащая элементы периода p ² . Периоды всех элементов второй группы составляют p .

Группа автоморфизмов C p 2 изоморфна декартову произведению C p х C p- 1 и содержит подгруппу, изоморфную C p . Так что вложение группы H = C p в группу автоморфизмов группы N = C p 2 конструируется естественным образом.

Циклическую группу C _p 2 можно реализовать как подгруппу мультипликативной группы Z p 3 кольца Z _p 3 . Группа Z p 3 циклическая порядка p ² ( p — 1). В ней существует подгруппа порядка p ² , порожденная степенями некоторого элемента Е Е Z p 3 порядка p ² . Итак, пусть

N = { 1 = Е ⁰ ,Е ¹ ,Е ² , . . . Е^р 2 ^{- 1} ,Е^Р 2 = Е ⁰ = 1 } , Е е Z _p 3 , E ^p 2 = 1 .

В этом представлении отображение аддитивной группы H = C _p в группу автоморфизмов группы N = C _p 2 строится элементарно: элементу h Е C _p поставим в соответствие автоморфизм V h ( E n ) = E n ^{(1+ p}h ) . Это соответствие действительно является гомоморфизмом, поскольку

V h 2 ( V h 1 ( E n )) = E n ^{(1+ ph 1 )(1+ ph 2 )} = E n ^{(1+ p ( h 1 + h 2 ))} = V h 1 + h 2 ( E n ) .

Степень s элемента ( E,n ) в G = C _p 2 x _p C _p вычисляется как

( E,h ) ^s = ( EE ^{1+ hp} E ^{1+2 hp} ...E ^{1+ h (} s- 1) ^p ,sn ) = ( E s ^{+ hp}      ,ns ) = ( E ⁽ s ) ,ns ) .

Результатом становится следующая схема генерации ключей: публикуемые данные – простое p , элемент E Е Z _p 3 порядка p ² , число n Е Z _p .

Сторона A выбирает случайное l , вычисляет L = E ⁽ l ) и передает L на сторону B . Сторона B выбирает случайное r , вычисляет R = E ⁽ r ) и передает R на сторону A .

Стороны вычисляют общий секретный ключ по схеме

K = LR ^{(1+ npl} ) = RL ^{(1+ npr} ) .

Для нахождения секретного ключа K по перехваченным L, R злоумышленнику придется решить уравнение у = e(s) = Es+hp S2

относительно показателя s в кольце Z _p 3 . Для этого требуется вначале решить задачу вычисления дискретного логарифма m = log ^ ( y ) в кольце Z _p 3 , а затем решить уравнение m = s + hp s ⁽ s 2 1) по модулю p ² относительно показателя s . Сложность создает здесь как добавление второго этапа, так и то, что вычисление дискретного логарифма производится в подгруппе порядка p ² группы Z p 3 .

6.    Заключение

Анализ полученных результатов показывает, что даже в случае рассмотренных здесь элементарных реализаций схема генерации ключей на полупрямых произведениях групп обеспечивает более высокую стойкость по отношению к атакам по сравнению со схемой Диффи–Хеллмана. Становится понятными также и слабое место предложенного подхода. Оно состоит в том, что при вычислении степени

n ⁽ s ) = nV h ( n ) V h 2 ( n ) ... V h ( s - 1) ( n )

на самом деле используется лишь циклическая подгруппа группы Aut ( N ), порожденная степенями ^ h k = ^ Һ базового автоморфизма ^ һ , а сам этот автоморфизм в обоих примерах обладает простой структурой, что позволяет привести выражение для степени n ⁽ s ) к форме n F ^{( s} ) с относительно простой функцией F ( s ). Это усложняет атаку вычислением показателя s ровно на сложность обращения функции F ( s ). Такое усложнение вряд ли достаточно радикально, чтобы мотивировать решительный отказ от простой классической схемы.

Достижения большей стойкости требует усложнения структуры формулы степени n ^{( s} ) . В этой связи интерес представляют расширения групп N , обладающих мощными группами автоморфизмов Aut ( N ), содержащими нетривиально вычисляемые отображения ^ һ , произведение степеней которых не удается привести к компактному виду.

Альтернативный путь может дать переход от вычисления степени ( n, h ) ^s к вычислению произведения ( n,h i )( n,h 2 ) ... ( n,h _s ) с s различными элементами группы H . При этом в формуле для n ^{( s} ) окажутся задействованными автоморфизмы, не являющиеся степенями базового. Возможность получения простой формулы для F ( s ) этим практически исключается, а вычисление общего ключа по схеме K = L^ h ( R ) = R^ h r ( L ) знания последовательности элементов, использованных удаленной стороной, не требует.