Об использовании свойства коммутирования символа степенного вычета в схемах открытого распределения ключа тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 511 2, 511 51

Назаров Вадим Владиславович

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

01.01.06 — математическая логика, алгебра и теория

чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□Q3D64824

Москва, 2007

/

Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М В. Ломоносова

Научный руководитель: кандидат физико-математических

наук, доцент М.А Черепнев

Официальные оппоненты: доктор физико-математических

наук, профессор С А Степанов, кандидат физико-математических наук, доцент А В Устинов

Ведущая организация:

Московский физико-технический институт (государственный университет)

Защита диссертации состоится 2 марта 2007 г в 16 ч 15 мин на заседании диссертационного совета Д 501 001 84 в Московском государственном университете им. M В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, ауд 14-08

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (главное здание МГУ, 14 этаж)

Автореферат разослан 2 февраля 2007 г

Д.501 001 84 в МГУ профессор

Ученый секретарь диссертационного совета

В H Чубариков

Общая характеристика работы

Актуальность темы. В 1976 Диффи и Хеллман1 предложили первую схему открытого распределения ключа, использующую возведение в степень по модулю большого простого числа Стойкость схемы основана на вере в то, что задача Диффи-Хеллмана является вычислительно сложной, возможно, столь же сложной, как и задача дискретного логарифмирования. Схема Диффи-Хеллмана обобщается на любую полугруппу с эффективно вычислимой операцией, в которой задача дискретного логарифмирования вычислительно сложна В частности, были рассмотрены кольца матриц над конечными полями?, группа единиц кольца Z/nZ, где п - произведение двух различных простых3, группа точек эллиптической кривой4, группа классов мнимого квадратичного поля5. Шэйдлер6 построил модификацию схемы Диффи-Хеллмана, использующую структуру полугруппы на идеалах вещественного квадратичного поля Схемы типа Диффи-Хеллмана в различных группах являются на данный момент наиболее широко используемыми на практике схемами открытого распределения ключа

В 1995 году В М Сидельниковым7 была предложена новая схема открытого распределения ключа на основе некоммутативной ассоциативной группы G Пусть Gi,G2 С G - коммутативные подгруппы, с -элемент <&, не лежащий в Gi, G2 схема С

А В

Шаг 1 Выбирает Ог е G,, г = 1,2, Шаг 1 Выбирает Ьг 6 Сг, г— 1,2, вычисляет ¿а = * с * аг, отправ- вычисляет dg = bi * с * Ь%, отправляет ¿а абоненту В ляет йв абоненту А

1Diffie W , Hellman М Е , New directions in cryptography IEEE Transactions on Information Theory, 22 (1976), pp 644-654

2Odom R.W К , Varadharajan V , Saunders P W , Public-key distribution m matrix rings Electr Letters, 20 (1984), pp 386-387

3MeCurley К S , A key distribution scheme based on factoring Journ Cryptology, 1 (1988), pp 95-105

4Koblits N Elliptic curve cryptosystems Math Comp, 48 (1987), pp 203-209

sBuchmann J A , Williams H С A key-exchange system based on imaginary quadratic fields Journ Cryptology, 1 (1988), pp 107-118

'Jacobson M J , Jr , Scheidler R, Williams H С The efficiency and security of a Real Quadratic Field Based Key Exchange Protocol Public-Key Cryptography and Computational Number Theory (Warsaw, Poland), de Gruyter, 2001, pp 89-112, Scheidler R, Buchmann J A , Wilhams H С a key-exchange protocol using real quadratic fields Journ Cryptology, 7 (1994), pp 171-199

7Сиделыгаков В M , Черепнёв М А , Ященко В В Системы открытого распределения ключа на основе некоммутативных полугрупп Доклады РАН, 332 (1993), Выи 5, стр 566-567

Шаг 2 Получает dв и вычисляет Шаг 2 Получает ¿а и вычисляет К = Kyi = а\ * с1в * a<i К = = Ъ\ * йд *

Кроме общей схемы рассматривались два ее частных случая, определяемые специальным выбором параметров схема С1, в которой с £ Gi = G2, и схема С2, в которой с — 1 В качестве группы была рассмотрена группа GL„(Fp), но при таком выборе схема оказалась нестойкой Позднее В М Сидельниковым был изучен? усовершенствованный вариант схемы на основе "экспоненциальной}" представления группы

М А Черепнев предложил9 использовать некоммутативную операцию в полугруппе или в множестве, не имющем алгебраической структуры Искомая операция была построена с использованием умножения в кольце целых чисел и символа Лежандра

(1)

где ?7 и ц — мультипликативные функции из Z в Z такие, что т](—1) = 1) = 1 О.Н Василенко заметил, что по аналогии можно рассматривать и некоммутативную операцию в кольце целых чисел простого кругового поля на основе умножения в кольце и символа р-степенного вычета

где т? и (j, — мультипликативные функции из ЩСр] в р] такие1 что

r?(<Zp) = м(Ср) = 1

При исследовании схем данного типа возникают три основные задачи, а именно, построение эффективно вычислимой ассоциативной некоммутативной операции, построение или описание коммутирующих подмножеств, анализ стойкости схемы

Для описания коммутирующих подмножеств при использовании операций на основе символа степенного вычета возникает необходимость описать максимальные подмножества Щ(р], для любых элементов которых (ж, у)х — 1 Эта задача в некотором смысле является усилением

'Сидельников В М Системы распределения ключей на основе экспоненциального представления линейной группы GLn(Fp) www cryptography ru

9 Черепнев M А Схемы открытого распределения ключа на основе некоммутативной группы Дискретная математика Т15 (2003), Выл 2 , 47-51

\tiv)J

задачи нахождения кондуктора10 элемента х € ЩС,Р) (х = 1 (mod Л)), то есть нахождения числа и € N, такого что (х , у)х = 1 для всех у = 1 (mod Xй)

При решении задач эффективного вычисления и анализа стойкости для операций на основе символа степенного вычета необходимо уметь оценивать сложность вычисления символов степенного и норменного вычетов в простых круговых полях для аргументов общего и специального вида Для вычисления символа степенного вычета от аргументов произвольного вида были предложены два алгоритма - один из них вероятностный,11 а второй детерминированный.12 Оба алгоритма имеют полиномиальную сложность, если в качестве параметра рассматривать длину записи входа Однако, если взять в качестве растущего параметра степень расширения поля, то сложность этих алгоритмов растет как минимум экспоненциально. Более того, если р и q - большие простые числа, такие, что р делит q — 1, а <Е Z, Q - один из простых идеалов Z[£p], лежащих над q, то сложность вычисления символа р-степенного вычета эквивалентена13 сложности вычисления индексов в подгруппе порядка р группы (Z/(q — 1)Z)*

Аналогичную (полиномиальную от длины входа и экспоненциальную от степени расширения поля) сложность имеют и известные алгоритмы вычисления символа норменного вычета, основанный на К -теории14 и использующий закон взаимности Артина-Хассе 9

Для операций на основе символа степенного вычета M А Черепнёв придумал алгоритм построения коммутирующих элементов "экспериментальным путем" и привёл пример элементов, для которых вычисление символа степенного вычета сводится к вычислению символа Якоби.® В диссертации изучается свойство коммутирования символа степенного вычета и свойства символа норменного вычета в простых круговых полях, а также возможности использования указанных символов в схемах открытого распределения ключа на основе некоммутативной операции

Цель работы. Целью работы явлется описание коммутирующих

10Shanfy R Т Minimal conductors of Kummer extensions by roots of unity elements Journ Ramanujan Math Soc 16 (2001), № 2, pp 101-117 и ссылки из указанной работы

11Horowits J Applications ofCayiey graphs, bilmeanty and higher-order residues to cryptology Staford Umvercity, PhD Theas, 2004

12Squirell D Computing power residue symbol Reed College, Undergraduate Thesis, 1997

13AdelmanLM., Pomerance С , Rumeîy R.S On distinguishing prime numbers from composite numbers Annals of Mathematics, 117 (1983), pp 173-206

14Daberkow M , On computations in Kummer extensions Journ Symbolic Computations 31 (2001), pp 113-131

множеств и анализ стойкости схемы при использовании операций на основе символа степенного вычета, а также исследование возможности применения в схеме операций на основе символа норменного вычета

Методы исследования. Работа опирается на исследования в теории алгебраических чисел и алгоритмической алгебраической теории чисел Для исследования свойств символов степенного и норменного вычета применяются методы алгебраической теории чисел, для оценки сложностей предложенных алгоритмов и стойкости схем - методы теории сложности вычислений

Научная новизна. Полученные результаты работы являются новыми и получены автором самостоятельно Основными из них являются следующие

Доказана теорема о критерии вскрытия схемы открытого распределения ключа на основе некоммутативной операции, построенной с использованием некоторой двуместной мультипликативной функции С помощью теоремы впервые показано принципиальное различие между стой-костями схем С1 и С2

Доказана нестойкость схемы при использовании класса операций на основе логарифмических функций, подобных предложенной ранее15

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

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

Построен новый алгоритм вычисления символа норменного вычета от аргументов общего вида, построенный на основе разложения по мультипликативному базису элементов мультипликативной группы некоторого фактор-кольца кольца целых чисел простого кругового поля и дана оценка сложности его работы

Получены условия, необходимые для стойкости схемы при использовании операций с символами степенного и норменного вычетов Показано, что эти условия будут выполнены, если вычисления в схеме осу-

15Черепнев М А Схемы открытого распределены ключа на основе некоммутативной операции. Тезисы докладов ХШ Международной конференции "Проблемы теоретической кибернетики" Казань 27-31 мая 2002 г етр 190

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

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

Апробация работы. Результаты настоящей диссертации неоднократно докладывались на научно-исследовательском семинаре по теории чисел под руководством Ю В Нестеренко и Н Г Мощевитина (механико-математический факультет МГУ) и на семинаре "Теоретико-числовые вопросы криптографии" под руководством М А Черепнева и Ю В Нестеренко (там же) в 2002-06 гг Кроме того, часть результатов диссертации была доложена на конференции "Математика и безопасность информационных технологий" (МГУ, октябрь 2003 г)

Публикации. Результаты диссертации опубликованы в работах [1-4], список которых приводится в конце автореферата

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

Содержание работы

В главе 2 предложен метод построения некоммутативной ассоциативной операции на основе коммутативной полугруппы С и мультипликативной функции С помощью предложенного метода получается в том числе и операция (2) Пусть функция Р1 С х <5 —> С мультипликативна по обоим аргументам на своей области определения Пусть также для всех 91,52,23 € О, таких, что Г определена на парах (51,52), (52,5з), (-Р(5ъ5г), 5з), (5ь Р'(д2,53)), выполнены равенства

^(51,52),5З) = 1,^(51,^(52,53)) = 1

Тогда операция *, заданная соотношением

91*92 = 91 92 Р{дъд2), (3)

будет ассоциативной, а в случае, если F не симметрична, то и некоммутативной Поэтому множество G с операцией типа (3) может применяться в схеме С

В работе показано, что в полугруппе (G, •) элементы ¿д и dв делятся на с, элемент (с^/с) * с делится на d^, а элемент ((¿в/с) * с делится на 4в Кроме того доказано, что параметры схемы С связаны соотношениями

Лемма 1.

(1) Пусть существует г\ € G такой, что т% ■ F(by, 0,2) == F{a%,b\) , тогда

— * ¿¿з = К Tj (4) с dA

(2) Пусть существует т2 € <G такой, что Т2 F(ai, 62) = F(b2, ai) ; тогда

dB , -г ^f* с

— * = К • r2 • ~— (5) с ав

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

Теорема 1. Пусть для г € {1,2} существует т,еС с указанными в лемме свойствами. Тогда задача нахождения общего секретного ключа К по открытой информации в схеме С с использованием операции (3) эквивалента задаче находждения элемента тг по открытой информации

При рассмотрении схемы С1 очевидно получаем, что тг = 1, поэтому схема нестойка

В главе 3 изучаются схемы на основе функций из ЩСр] в Z, обладающих логарифмическим свойством по модулю р В работе15 М А. Черепнёв привел пример операции на основе символа степенного вычета, которая является частным случаем операции (3) Пусть а € Z, взаимно прост с р ,

ар-1 _ 1 Ф„(в) - —-- (mod р)

частное Ферма по модулю р. Пусть J - фиксированный идеал Z[£p], тогда

Шх)\

X * у = х у J (6)

является некоммутативной ассоциативной операцией, определенной на элементах, чьи главные идеалы взаимно просты с J и (Л)

В диссертации показано, что операция (6) является частным случаем операции

х*у = х-у Ср{х) Ш (7)

где функции /г Z[Ср] —> Z обладают свойствами Мху) = /г(ж) + /г(у) (mod р); /г(Ср) = 0 (mod р) для г = 1,2

Обозначим через Е - подмножество Z[£p], на котором определена операция (7) и рассмотрим следующие подмножества Е Но,о = {х € Е! Мх) = f2(x) = 0 (mod р)}, Ио = {х € Е | /г(х) = 0; Л(х) ф 0 (mod р)}, Ир = {х € Е | Мх) ф 0, /2(х) = 0 (mod р)}, Шг = {ж G Е | /i(rr) Мх)"1 = г (mod р)}, г = 1 .р-1 В работе доказана следующая теорема о коммутирующих множествах

Теорема 2. Для любого коммутирущего множества М относительно операции (7) существует г 0 < г < р, такое что М является подмножеством, собственным или несобственным, множества Hq^UHj .

На основе этой теоремы, а также соотношений из леммы 1, в работе построен эффективный алгоритм нахождения общего секретного ключа по открытой информации Из его существования следует

Теорема 3. При использовании операции типа (7) схема С является нестойкой.

В главе 4 изучается схема С, использующая операцию (2) в случае, когда функции ß и Г) совпадают В первом разделе главы изучаются коммутирующие множества относительно данной операции, а во втором - строится алгоритм атаки на схему, из которого выводятся условия, необходимые для ее стойкости

При изучении свойства коммутирования элементов основополагающим является следствие из степенного закона взаимности-16 элементы х и у коммутируют тогда и только тогда, когда (г)(х), г](у))х — 1

"Artin Е , Täte J Claas field theory Notes of a Seminar at Pnnceton, 1951/52 Harvard Umversity, Mathematics Department, 1961

Обозначим через Z подмножество Z[CP], состоящее из элементов, взаимно простых с Л Так как идеал (А) - простой, то Z является полугруппой относительно умножения

Определение 1. Максимальным тривиальным подмножеством символа норменного вычета назовем подмножество Л4 С Z, удовлетворяющее двум условиям

(1) для любых х, у € Л4 выполнено*(х, у)х — 1,

(2) если z € Z таков, что для любого х 6 М. выполнено (г, я)Л = 1, то z £ Л4

Замечание В силу мультипликативности символа норменного вычета по обоим аргументам, любое максимальное тривиальное подмножество будет полугруппой по умножению Поэтому будем говорить о максимальных тривиальных полугруппах символа норменного вычета

В диссертации доказано, что на Z символ норменного вычета имеет аддитивный период, равный \р

Теорема 4. Пусть х, у, z € Z, х = z (mod Ар), тогда (х,у)х = У)(У. ®)д = (tf> «)а

Принимая во внимание теорему 4, при изучении свойств символа норменного вычета можно рассматривать не сами аргументы символа, а содержащие их классы фактор кольца Z[£P]/(Хр) Так как символ норменного вычета мультипликативен по обоим аргументам, то при описании его максимальных тривиальных полугрупп можно использовать мультипликативную структуру группы (Z[CP]/(AP))* Пусть шг = 1 — Аг для натуральных г. В книге16 показано, что любой элемент мультипликативной группы Q*(Cp) поля Qp(Cp) единственным образом представляется в виде произведения

00 г—1

где g - произвольный корень из 1 степени р — 1, лежащий в Qp(Cp), 7А целое, 7г целые неотрицательные. Для группы (Z[£P]/(AP))* в диссертации доказана

Теорема 5. Любой х € Щ(р], взаимно простой с (А), единственным образом представим в виде

х = 9о™ ■ (mod (Ар)), (8)

где да € Ъ - произвольный фиксированный первообразный корень по модулю р2, 0 < 7о < р — 2, О < 7г < р — 1 <?лл г = 1, — 1

Из теорем 4 и 5 выводится основной результат о структуре максимальных тривиальных полугрупп

Теорема 6. Любая максимальная тривиальная полугруппа символа норменного вычета имеет вид

М = {хе2\х = д0Р"° б^^ + ^р А'}, (9)

где до - первообразный корень по модулю р2, , - мультипли-

кативно независимые в (Ж[СР]/(АР))* элементы порядка р, такие что (& > а — !>' ^о = 0, ,р — 2, уг — 0, ,р - 1 для г = 1, , ,

1/р е й[Ср].

Обратно, пусть £1,. >£е=1 произвольные мультипликативно независимые в (2[£Р]/(АР))* элементы порядка р, такие что (£,, = 1, до € Ъ произвольный первообразный корень по модулю р2, тогда множество вида

М = {дГ° + хр},

где щ = 0, ,р - 2; г/г — 0, ,р - 1 для г = 1, , ^; ир € 2[СР] будет являться максимальной тривиальной полугруппой символа норменного вычета.

Определение 2. Элементы £1, . , из (9) назовем основными образующими максимальной тривиальной полугруппы

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

Каждое из коммутирующих подмножеств, используемых в схеме, будет являться подмножеством полного прообраза какой-либо максимальной тривиальной полугруппы ©1 С ^(Мг), Сг С г]~1{М.2) где М\ и М.2 имеют вид (9) В предположении, что для и М.ч известны какие-либо наборы основных образующих, построена атака, позволяющая находить по открытой информации общий секретный ключ К Для реализации алгоритма атаки необходимо осуществить 0(р3) арифметических операций в Ъ/рХ, 0(р2) вычислений символа норменного вычета

и 0(1) вычислений символа степенного вычета Сложность работы этого алгоритма, обозначаим через Тд(р).

Обозначим через Т(р) сложность вычисления по протоколу схемы, через Tj(p) - сложность нахождения основных образующих максимальных тривиальных полугрупп М.\ и М.2 по открытому описанию коммутирующих подмножеств используемых в схеме Тогда общая сложность предложенной атаки на схему равна Tj(p) +Тд(р) - сначала находятся основные образующие по открытой информации, а потом реализуется алгоритм атаки Поэтому для обеспечения стойкости схемы необходимо, хотя, возможно, и не достаточно, чтобы функция Т(р) имела бы полиномиально меньший порядок роста, чем Та(р) + Tj{p) (под полиномиально меньшим порядком роста имеем ввиду то, что функция U(p) является полиномом от некоторого параметра, a V(p) растет по крайней мере субэкспоненциально от того же параметра, и обозначаем такое отношение. U(p) <С V(p)) В результате, для стойкости схемы необходимо выполнить хотя бы одно из двух условий

Условие 1. Коммутирующие подмножества Gi и G2 заданы так, что Г(р) < Tj{p)

Условие 2. Легальные абоненты используют при вычислениях только те элементы, для которых Т(р) <С

Отметим, что при известных основных образующих и при использовании для вычислений символов степенного и норменного вычета стандартных алгоритмов (от произвольных аргументов) ни одно из этих условий не выполнено Главным членом как в Т(р), так ив Tj (р) + ТА(р) будет сложность алгоритма вычисления символа р-степенного вычета

С другой стороны, оба эти условия выполнены, если вычисления по протоколу схемы осуществимы за время, полиномиальное от logp Действительно, во-первых, число основных образующих каждой из максимальных тривиальных полугрупп равно ^, поэтому Tj(p) растет не медленнее, чем р, и следовательно выполнено условие 1 Во-вторых, Та(р) растёт не медленнее, чем 0(р3), поэтому выполнено условие 2.

Как уже было отмечено выше, известные алгоритмы вычисления символа норменного вычета (х, у)х от произвольных аргументов х, у имеют сложность, растущую, как полином от длины записи х и у, и быстрее, чем полином от logp Однако, ни в статье М Даберкова9, ни в статье М А Черепнёва 14 не даны точные оценки сложности предложенных алгоритмов в зависимости от степени расширения поля

В третьем разделе четвертой главы диссертации построен альтернативный алгоритм вычисления символа норменного вычета в кольце целых чисел Z[CP] простого кругового поля для элементов из Z Алгоритм работает за 0{рг) проверок сравнимости с 0 по модулю натурального числа, не превосходящего р в Z и за 0(р3) арифметических операций в Z/pZ Вычисление символа норменного вычета сводится к вычислению семейства функций из Z[(p] в Z, обладающих логарифмическим свойством по модулю р Пусть идеал (ж) взаимно прост с (Л). Тогда разложение (8) для хр~г имеет вид

хр~г = a>i-71 {тоАр) . {modp) (mod (У)) (10)

Рассмотрим для г = 1, ,р— 1 функции ег(х) = (mod р) (оператор (mod р) означает взятие наименьшего положительного вычета по модулю р).

ег Z —► Z/pZ

В силу свойств показателей и того, что порядок шг в (Z[CP]/(AP))* равен р, ег(х) обладают логарифмическим свойством по модулю р . Кроме того, для всех % ф \ &i(CP) = 0 В диссертации показано, что функции е,(х) для различных г связаны соотношениями

Теорема 7. Пусть Х0 = х^1 (mod р), х' — 1+XiXq\-{- +жр_2-ХоАр~2 , тогда для к = 1, . ,р — 1 выполнено

1 + ек(х)Хк == х'хо(р-1)2иле^ (mod (Xм)) (11)

На основе этой теоремы построен алгоритм, вычисляющей по х € Z набор значений £(х) = (ei(x), , ер-г(х)) за 0(р3) операций в ZjpTL и за 0(р) операций нахождения остатка от деления на р в Z

В главе 5 изучаются свойства символа норменного вычета и возможность применения этого символа для построения некоммутативной операции в Z[CP]

По аналогии с операцией (2) в качестве примера операции (3) можно взять следующую операцию в Z

х*у = х у (ц(х), v(.y))\ > (12)

где (J.,r) - мультипликативные функции, такие что //(СР) = т?(Ср) = 1-Так как символ норменного вычета имеет на Z аддитивный период Ар, то для обеспечения ассоциативности операции (12) достаточно взять

функции /л и 77 с указанными выше свойствами, но действующие не из Щ(р] в Z[CP], а из ЩСр] в (Z[CP]/(AP))* В частности, можно использовать функции Цг,3(х) — (mod (Ар)) для г = 2,. , j = 1,. ,

где ал, и е2(ж) определены выше Опять рассматриваем операцию в случае, когда функции /лиг) совпадают

х*у = х у {г){х), г){у))х . (13)

В диссертации доказаны критерии коммутирования относительно операции (13) и стойкости схемы С при использовании этой операции

Теорема 8. (критерий коммутирования) х * у — у * х тогда и только тогда, когда

(Ф). Ф))х = 1

Теорема 9. (критерий стойкости)

Задача нахождения общего секретного ключа К по открытой информации эквивалентна задачам нахождения по открытой информации символов норменного вычета

п' = (^(а2), q(bi))A и т2' = (??(Ь2), 77(ах))д

Критерии коммутирования и стойкости совпадают с соответствующими критериями при использовании операции (2) с совпадающими функциями ¡j. и т] Значит, совпадает структура коммутирующих множеств, а следовательно алгоритм нахождения общего секретного ключа по открытой информации из главы 4 диссертации применим и в данном случае Поэтому если, как и ранее, будем обозначать через Тд(р) сложность алгоритма атаки, через Т/(р) сложность получения набора основных образующих максимальных тривиальных полугрупп Л4г по открытому описанию коммутирующих множеств Gt, а через Т(р) сложность вычислений по протоколу схемы С, то для достижения стойкости схемы необходимо, хотя, возможно, не достаточно, выполнить одно из условий 1 или 2. Для быстрых вычислений может быть использована доказанная в диссертации теорема, связывающая символ норменного вычета с классическими частными Ферма по модулю р

Теорема 10. Пусть a,b,c,d,a € Z, р не делит ас, а > 1, Д = ad — be Тогда

1) Если а > 2, то (а + ЬХа, с + d\a)x = 1

2) Если а = 1, то

если bd ф О, Д ф 0, то (а + Ь\, с + d,X)x = ф(Ь)' ~*p(d)'+Ф'(Л) "

если bd ф О, А = О, то (а + ЬХ,с + dX)x = <рр(а)«_ф"(с) •

если Ь = 0, d ф О, то (а + ЬХ , с + dX)x = фр(а) г

если Ъ ф О, d = О, то (а + ЬХ , с + dX)x = Ср Фр(с) 5 • если Ь = d — О, mo (а + 6А, с + d\)x = 1

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

Замечание Техника, используемая в доказательстве теоремы, позволяет получить формулы и для символа норменного вычета от элементов другого вида (тоже специального)

Используя полученные формулы, можно вычислять символ норменного вычета вида (а + ЬХа, с + dXa)x за время, полиномальное от logp В диссертации доказана следующая теорема о сложности вычислений по протоколу схемы

Теорема 11. Пусть функция г) и множества Gj, G2 таковы, что в каждом Сг есть подмножество G/, элементы которого удовлетворяют свойствам.

(1) Элементы G/ записываются целочисленной линейной комбинацией элементов 1, £, , Qp~i, содержащей полиномиальное от logp число ненулевых коэффициентов,

(2) Выбор случайного элемента из G/ по открытому описанию Сг осуществляется за время, полиномиальное от log р;

(3) Входом для функции г] является линейная комбинация элементов , . , (р~1 Она возвращает значения в виде разложения по X-базису В случае, если поданная на вход комбинация имеет полиномиальное от logp число ненулевых коэффициентов, значение вычисляется за время, полиномиальное от log р;

(4) Значением г](дг) для любого дг & G/ будет элемент вида u+vX, где u,v & Ъ, причем (г£, р) = 1

Тогда Т(р) растет, как полином от logp При р — 3 (mod 4) вычисления по протоколу схемы реализуются с помощью детерминированного алгоритма, а при р = 1 (mod 4) - с помощью вероятностного алгоритма

При доказательстве теоремы используется разработанная автором диссертации техника проведения арифметических операций над "короткими" элементами круговых полей, за время, полиномиальное от logp

Если удастся построить множества Сг и функцию г), удовлетворяющие условиям теоремы 11, то полученная схема будет стойкой относительно предложенного в диссертации алгоритма атаки Однако пока построить примеры таких множеств и такой функции не удалось

Автор глубоко благодарен своему научному руководителю кандидату физико-математических наук, доценту Михаилу Алексеевичу Черепневу за привитый интерес к области исследования, полезные советы и постоянное внимание к работе

Работы автора по теме диссертации

[1] В В Назаров Об использовании символа степенного вычета в схемах открытого распределения ключа Вестник Московского Университета, сер 1, Математика, Механика №3 (2005), стр 9-13

[2] В.В Назаров Схемы открытого распределения ключа на основе некоммутативной операции Дискретная математика Т18 (2006), Вып. 4, стр. 149 - 156

[3] В В Назаров О некоторых вычислительных свойствах символа норменного вычета в простых круговых полях Депонировано в ВИНИТИ 31 10 2006, № 1289-В2006, 24 стр

[4] В В Назаров Схемы открытого распределения ключа на основе некоммутативной операции Использование в схемах данного типа символа степенного вычета Математика и безопасность информационных технологий Материалы конференции в МГУ 23-24 октября 2003 г М , изд-во МЦНМО, 2004, стр 179 - 182

1 Введение

1.1 Описание основных результатов диссертации.

1.2 Схемы открытого распределения ключа.б

1.3 Схема на основе символа степенного вычета

1.4 Основные результаты диссертации.

2 Общие свойства схемы

2.1 Общие свойства схемы.

2.2 Построение некоммутативной операции.

2.2.1 Построение операции на основе коммутативной полугруппы и мультипликативной функции.

2.2.2 Свойства схемы при использовании операции на основе мультипликативных функций.

3 Схема на основе логарифмических функций

3.1 Построение и свойства некоммутативной операции.

3.2 Описание коммутирующих множеств

3.3 Криптоанализ схемы.

4 Схема на основе символа степенного вычета.

Случай^) = //()

4.1 Описание коммутирующих множеств

4.1.1 Аддитивный период символа норменного вычета

4.1.2 Структура группы {Z[Q/(\v))*.

4.1.3 Переход к векторному пространству.

4.1.4 Оценка размерности максимальных тривиальных подпространств формы ф.

4.2 Оценка стойкости схемы.

4.3 Алгоритм вычисления символа норменного вычета.

4.3.1 Логарифмические функции из Z[(p] в Z/pZ.

4.3.2 Вычисление логарифмических функций из Z[£p] в Z/pZ.

4.3.3 Алгоритм вычисления символа норменного вычета

5 Схема на основе символа норменного вычета.

Случай 77() =

5.1 Быстрое вычисление символов (а + ЬХа , с + d\a)x.

5.2 Применение быстрых вычислений в схеме С2.

1.1 Описание основных результатов диссертации

В.М. Сидельников в работе [13] предложил схему открытого распределения ключа на основе некоммутативной группы. Пусть G - некоммутативная группа с ассоциативной эффективно вычислимой операцией *; Gi,G2 коммутативные подгруппы G; с - элемент G, не лежащий в Gi,G2. Схема С

А В

Шаг 1. Шаг 1.

Выбирает сч G Gj, г = 1,2; вычис- Выбирает bi £ Gi, г = 1,2; вычисляет с1д = а\ * с * а,2", отправляет dа ляет ds = h * с * 62; отправляет de абоненту В абоненту А

Шаг 2. Шаг 2.

Получает и вычисляет Получает ^ и вычисляет

К = Ка = а,\ * ds * а2 К = Кв = Ъ\ * * 62

Помимо общей схемы рассматривались два её частных случая: С1, в которой Gi = G2, и С2, в которой с = 1. М.А. Черепнёв в работе [16] предложил использовать для аналогичной схемы некоммутативную ассоциативную операцию в кольце целых чисел простого кругового поля. Пусть г)(),»0 - мультипликативные функции, такие что rj((p) = fi((p) = 1, ft J - символ степенного вычета тогда р

Ф)\ . х*у=хуШР {г)

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

Рассмотрен класс некоммутативных ассоциативных операций на основе коммутативной полугруппы (G, •) и двуместной мультипликативной функции F(, ) такой, что F(F(x, y),z) — F(x, F(y, z)) = 1: x * у = x ■ у ■ F(x,y) (ii)

Операция (г) имеет такой вид. При использовании в схеме С произвольной операции вида (гг), получен критерий вскрытия схемы, такой же, как и при использовании операции (г).

В случае совпадения функций г)() и ji() в операции (г) дано описание максимальных коммутирующих подмножеств и на его основе реализован алгоритм атаки на схему. Вычислительная сложность алгоритма атаки эквивалента сложности протокола схемы при использовании известных алгоритмов вычисления символов степенного и норменного вычета для элементов общего вида.

По аналогии с операцией (г) рассмотрена операция вида (гг), использующая символ норменного вычета: х*у = ху(ф),?](у))А (Иг)

Для схемы С на основе операции (Иг) также проведено построение коммутирующих множеств и указан алгоритм атаки. При использовании операции вида (Hi) получены условия на функцию rj() и подгруппы Gj, выполнение которых приводит к экспоненциальному росту количества арифметических операций, необходимых для реализации упомянутого алгоритма атаки, при полиномиальном росте количества операций, необходимых для реализации протокола схемы С.

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

1. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел, Москва, Мир, 1987

2. Боревич З.И., Шафаревич И.Р. Теория Чисел, Москва, Наука, Главная редакция физ-мат литературы, 1985.

3. Василенко О.Н., Теоретико-числовые алгоритмы в криптографии, Москва, МЦМНО, 2003.

4. Вейль Г., Алгебраическая Теория Чисел, Москва, УРСС, 2003.

5. Винберг Э.Б. Курс Алгебры, Москва, Факториал-Пресс, 2001.

6. Виноградов И.М. Основы теории чисел, Москва, Ленинград, Государственное издательство технико-теоретической литературы, 1952.

7. Алгебраическая теория чисел, под ред. Касселс Дж., Фрёлих А. Москва, Мир, 1969

8. Черепнёв М.А. Криптографические протоколы, Москва, Центр прикладных исследований при механико-математическом факультете МГУ, 2006

9. Artin Е., Tate J. Class field theory Notes of a Seminar at Princeton, 1951/52. Harvard University, Mathematics Department, 1961.

10. Cohen H. A Course in Computational Algebraic Number Theory, 3 corr. print, Springer, Berlin-Heidelberg-New York, 1996И. LemmermeyerF. Reciprocity Laws From Euler to Eisenstein. Berlin, Springer, 2000

11. Washington L.C. Introduction to Cyclotomic Fields, Springer, New York-Heidelberg-Berlin, 1982

12. Сидельников B.M., Черепнёв M.A., Ященко В.В., Системы открытого распределения ключа на основе некоммутативных полугрупп. Доклады РАН, 332 (1993), Вып. 5, стр. 566-567.

13. Сидельников В.М. Системы распределения ключей на основе экспоненциального представления линейной группы GLn(Fp).

14. Черепнёв М.А. Схемы открытого распределения ключа на основе некоммутативной операции. Тезисы докладов XIII Международной конференции "Проблемы теоретической кибернетики". Казань 27-31 мая 2002 г. стр. 190

15. Черепнёв М.А. Схемы открытого распределения ключа на основе некоммутативной группы. Дискретная математика Т. 15 (2003), Вып. 2, стр. 47-51

16. Назаров В.В. Об использовании символа степенного вычета в схемах открытого распределения ключа. Вестник Московского Университета, сер.1, Математика, Механика. №3 (2005), стр. 9-13.

17. Назаров В.В. Схемы открытого распределения ключа на основе некоммутативной операции. Дискретная математика Т. 18 (2006), Вып. 4, стр. 149-156

18. Назаров В.В. О некоторых вычислительных свойствах символа норменного вычета в простых круговых полях. Депонировано в ВИНИТИ 31.10.2006, № 1289-В2006, 24 стр

19. AdelmanL.M., PomeranceC.,RumelyR.S. On distinguishing prime numbers from composite numbers. Annals of Mathematics, 117 (1983), pp. 173-206

20. Buchmann J.A., Williams H.C. A key-exchange system based on imaginary quadratic fields. Journ. Cryptology, 1 (1988), pp. 107-118

21. Daberkow M. On computations in Kummer extensions Journ. Symbolic Computations 31 (2001), pp. 113-131

22. Diffie W., Hellman M.E., New directions in criptography, IEEE Transactions on Information Theory, 22 (1976), pp. 644-654

23. Helou C. Power Reciprocity for Binomial Cyclotomic Integers. Journal of Number Theory, 71 (1998), pp. 245-256

24. Horowits J. Applications of Cayley graphs, bilinearity and higher-order residues to cryptology Staford Univercity, PhD. Thesis, 2004

25. Jacobson M.J., Jr., Scheidler R., Williams H.C. The efficiency and security of a Real Quadratic Field Based Key Exchange Protocol. In Public-Key Cryptography and Computational Number Theory (Warsaw, Poland), de Gruyter, 2001, pp. 89-112

26. Koblits N., Elliptic curve cryptosystems, Math. Comp, 48 (1987), pp. 203209

27. McCurley K.S., A key distribution scheme based on factoring, Journ. Cryptology, 1 (1988), pp. 95-105

28. Miller V., Use of elliptic curves in cryptography. In Advances in Cryptology -ProceedingsofCRYPTO'85, LNCS, 218 (1986), Springer (New York), pp. 417-426

29. Odoni R.W.K., Varadharajan V., Saunders P.W., Public-key distribution in matrix rings, Electr. Letters, 20 (1984), pp. 386-387

30. Scheidler R., Buchmann J.A., Williams H.C. A key-exchange protocol using real quadratic fields. Journ. Cryptology, 7 (1994), pp. 171-199

31. Squirell D. Computing power residue symbol. Reed College, Undergraduate Thesis, 1997