NEW CRYPTOSYSTEMS ON ELLIPTIC CURVE POINTS BASED ON THE PACKAGE KNAPSACKS DIFFICULTY

Abstract

In the paper we develop a cryptosystem on the points of an elliptic curve, based on the package knapsacks difficulty. To construct a cryptosystem uses the pairing operation of the elliptic curve defined over a finite ring. All arithmetic operations are performed in the residue number system.

Full Text

Введение Современные информационные системы требуют особого подхода к сохранению секретной информации. Это обусловлено развитием технических возможностей потенциальных нарушителей, а также появлением новых алгоритмов криптографии и криптоанализа. Криптосистемы, основанные на использовании вычислительно сложной задачи упаковки рюкзака, обладают высокой скоростью шифрования информации, однако у них есть существенный недостаток. В большинстве случаев такие криптосистемы уязвимы для анализа с помощью алгоритма LLL, который аппроксимирует решение, являющееся кратчайшим вектором, содержащимся в решетке предполагаемых решений. Цель статьи - разработка криптосистемы упаковки рюкзака на точках эллиптической кривой над кольцом вычетов. Билинейное спаривание Для построения криптосистемы введем операцию спаривание на эллиптической кривой аналогичную работе [1]. Для любой точки Рє e{GF{Pi)) выполняется следующие равенство (и, + l)f = О , где О - точка в бесконечности. Обозначим за E[zq} множество точек эллиптической кривой, которая задана уравнением у2 = Xі +ах + Ь, над расширенными полями Для построения спаривания важно знать структуру группы точек эллиптической кривой. Ниже приведена теорема, описывающая структуру группы, когда эллиптическая кривая задана над полем GF(pf), где pt - простое число, k > 1 и порядок группы точек эллиптической кривой выражается формулой #E(GF(p*)=p*+\-t. Теорема 1 [2]. Если t2 - pf ,2pf ,3pf, то группа циклическая. Если t2 =4pf, то группа изоморфна i j в случае t = 2-Jpf или изоморфна z ,_ ® Z і_ в случае t = —2J рк , А/Л-+1 т1р}+ 1 Если t = 0, pf ^3(mod4), то группа циклическая. Если t-0, р\ = 3(mod4), то группа или циклическая, или изоморфна Z t+1 © Z2. 2 Из теоремы 1 следует, что в случае, ког- 2 а к да t =4pi и г - четное число, группа точек e{gf(p*} представляется в виде прямой суммы Z г-г © Z г-г или Z г-г Ф Z г-г . Обоз-VA--1 V Pj —1 Va-+1 vpf+i начим эти группы Е[1;\, где 1; = у[р*-1 или h=^ + l. Так как £'[/,■] представляется в виде прямой суммы циклических групп, то можно зафиксировать некоторую образующую пару точек Gt и Ht таким образом, чтобы любую точку в можно было представить с помощью них. Рассмотрим точки Pi -aX iGi +buHt и Qt -a2iGt + b2iHi, принадлежавшие Е[>,\ Для некоторых зафиксированных целых at>Pt є i°’li -1] определим функцию следующим образом LaitPt :Е[і]хЕ[і]^е[і], ipi’Qi)={ai,Ai-a2,A, iXaiGi+fiHi)’ исключая тривиальный случай, когда at и Д одновременно равны нулю. Пусть Gj, G2 и G3 - три Абелевы группы. Билинейное спаривание является отображением e:G1xG2 ^ G3 среди этих трех групп, и отображение должно удовлетворять свойству билинейности: для «Инфокоммуникационные технологии» Том 10, № 4, 2012 6 Бабенко М.Г., Ляхов П.А., Червяков Н.И. a,p&Gx, y,SeG2, е(а + Р,у) = е(а, у)+e{fi, у), е(а, у + д) = е(а, у)+е(а, S). Следующая теорема показывает, что функция Eat,pt задает билинейное спаривание. Теорема 2 [1]. Функция Еар. обладает следующими свойствами. 1. Тождественность: для всех Pt є E[lt ], Laj д [Р^Р{)= О. 2. Билинейность: для всех P^Q^Rt Є E[lt], La,,p,i^i + Qi>Ri) = La.{Pj,Rj)+La д (Qi,Rt) и A*,,ptІРі>Qi +R-i) = La.tp.{Pi,Qt)+La д {Pt,Rj)■ 3. Антисимметричность: для любых 4. Невырожденность: для всех і? є , кроме того, если La р (P,.Q)=o для всех тогда Pi=0. La >p, называется спариванием, поскольку оно отображает і?[/г]х2?[/г] в е[і{ ] (аналогично традиционным спариваниям Вейля и Тейта). Пусть К,р (л Q) = L є E(zqk) и Lat,д{pi>Qi) = Ц e E(GF[pf )). Зададим спаривания LaB{P,Q) как XL=XLmodpi, YLt = Yl modpt, ZLi = ZL mod pt с помощью множества точек Gj, Ht и целых чисел є [1,..., - 1], где L = (XL:YL:Zl), bi=(xLi:YLi:ZLi),P = (xp:YP:ZP\ Q = (xQ-YQ-ZQ)*Zqk, Pt(xPi :YPi Q(X& :Y& :Z&)sGF(pf), XP^XPmodPi, Yp =Yp mod pt, ZP> = Zp mod pt, XQi s XQ mod Pi, Y& s Yq mod pt, Zq = Zq mod Pi и і = 1 ..s Замечание. Значения XL, YL, ZL представляются в системе остаточных классов числами XL , YLj, ZLj по основаниям pt. Приведем пример построения билинейного спаривания. Пример 1. Пусть задана эллиптическая кривая E(FS): у1 =хг +Ъх +4 и F52 = F5 /(a2 + a +1), тогда #E\Fp2 )= 27 имеет восемь торсионных точек третьего порядка: (-!,+(« +З)), (2,+2), {a,±a), (4a + 4,±(a +1)). Билинейное спаривание можно задать с помощью следующих точек G = (2,2) и H = (a,a), OG + OH = 0; IG + OH = (2,2); 2G + OH = (2,-2); OG + IH = {a,a); \G + \H = {4 + 4a,1 + a); 2G + 1H = (- 1-а - З); 0G + 2H = (a,-a); Ю + 2Н(-1,а + Ъ); 2G + 2H = (4 + 4a,4 + 4a), что изоморфно Zt,®Z3. Из определения следует что e(P,Q) = e{Q,Py. Процесс генерации ключей Пусть Е, заданной уравнением в форме Вейерштрассе у2 =хъ +ах + Ь, над Z , где S ’ a,b^Zq, q-^\pt, Pi - различные простые і=і числа и для всех / = 1,...,,у выполняется следующее условие: 3<Л<106 и q> 21024. Числа Pi выбираются так, чтобы было большое простое число n в 160 бит или более в факторизации на простые числа порядка эллиптической кривой #E\Fq). Далее, мы выбираем случайное число к к є N. Однако следующая супервозрастающая последовательность at=k- 2‘ \ (г = 1,2,3,...,иг), к выбирается так, чтобы удовлетворяла следующему условию y'(fc-2i~1)< П ^. Рациональные точки atP(j. = 1,2,3,...,иг) являются открытым публичным вектором рюкзака. Однако, как описано ниже, расшифровка эффективна, сообщаем каждому шифротексту и сумму г рациональных точек atP. Следовательно, количество at равно иг. Здесь мы имеем иг > 100 , так что шифротексты могут иметь допуск достаточно грубой силы нападения. Затем рациональные точки а^Р, , ашР, эллиптической кривой e(f„), произвольная точка R(^alP,...,aurP)eE{Fp\n] и S = dR, где d sZn случайно взятое публичное открытое. Затем для каждого Cf(i = l,...,u), которое передается в качестве шифротекста, функция расшифровки задается следующим образом. Сначала вычисляется bn=e{P,Qf и вычисляем t\j=i^(P.QfJ (7 = 2,3,...,2r_1). В дальнейшем by вычисляется по схеме: ь2,=кУ ={Up’Qf))2 =[kp’QfY J. «Инфокоммуникационные технологии» Том 10, № 4, 2012 Бабенко М.Г., Ляхов П.А., Червяков Н.И. 7 ь„=(ь„Т =^(е(р,е)*ГJ J --{Ui’-etf), b« = {b,-,,jY =({4г.оїї j(n—l)r \J J Процедура вычислений: сначала определяются bn = bf[u (i = 2,3,...,и), затем by = ьи_гьа (/ = 1,..., и, j = 2,3,..., 2r *). В завершение мы находим многочлен как /(*) = (* “ ) • • • “ biv~l Xх “х) (z‘ = 1.-,и) • Публичный ключ и секретный ключ задаются следующим образом. Публичный ключ: ахР,...,ашР, E(Fp), R, S, г Секретный ключ: d, fy(x), e{P,Q), а0,aur, Q Алгоритм 1. Шифрования для криптосистемы упаковки рюкзака на эллиптической кривой Вход. Двоичный вектор М = (my,m2,...,mut), m, є (0,1), (/ = 1,2,... ,иг), Публичный ключ ахР,...,ашР, E(Fp), R, S, r. Выход. Шифротекст С, с, Сп, С12,...,Си_1Х, Q-1,2 • 1. С = 0 2. Для i = l до иг выполнять следующие действие: 2.1. C = C + mj(aiP). 3. Для / = 0 до м-2 выполнять следующие действие: 3.1 с,=о. 3.2. Для у = 1 до г выполнять следующие действия: См = С, + ты+]{аыР). 4. Генерируются случайно числа ty,t2,...,tu_x. 5. Для 1 = 1 до м-1 выполнять следующие действия: 5.1. Q.i = ’ 5.2. Ci2 = Cx+tyS .. 6. Вывод С, Сц, Cj2, Си_J 2 Алгоритм 2. Дешифрование для криптосистемы упаковки рюкзака на эллиптической кривой. Вход. Шифротекст С, Си, С12, ...,Си_уу, и d, f^x), e(P,Q), а0, ,ах, ..., аиг. Выход. Двоичный вектор Af 1. Для 1 = 1 до и — 1 выполнять следующие действия: Ct - Cl2 - dCiX. 2. y = e(C,Q), 3. Для г = 1 до м-1 выполнять следующие действия: 3.1. x = e{Ci,Q), 3.2. у = у/х. 3.3. Для 7 = 0 до г-1 выполнять следующие действия: 3.3.1.Если /1(х/е(Р,Є^)=0, то mri_,=l, х = х/ ef""'"1, иначе = 0 4. Для 7 = 0 до г-1 выполнять следующие действия: 4.3.1.Если /i(y/^,eh)=0, то 4.3.1.1. rn„r_,=l, 4.3.1.2 x = x/e^~J~1 , иначе mur_j = 0. 5. Вывод М. Действие расшифровки Во-первых, объясним расшифровку Q: пусть Y = e{C„Q)le{P,Qf = = е(щ (оуР)+... + тг (агР), б)/ e(arP, Q) = = е(т1 (оуР)+... + mr (arP) - arP, Q) = = е^туау +... + mrar - ar)Р,Q) = = e{k{mx +... + mr 2Г~1 - 2Г“1 )р, g)= = (e(P,Q)jmi+'+m'2' '~2' 'I Если ml +... + mr2r~l-2r~1 > 0, мы называем это положительное значение спариванием. В противном случае мы называем его отрицательным значением спаривания. В уравнении by=(e(P,eff (7 = 1,2,3,...,2 ) 6^- все зна- , -,-1 И-1 чения различны потому, что k-2 <-< п , и значение спаривания определяется единственным образом. С вида l,2,...,2r_1 «супервозраста-ет», так как 1 + 2 +... + 2r~2 < 2r_1, следовательно, т1+... + тг2г~1 - 2Г~1 <2Г~1. Если тг =1, тогда /j(7) = 0, потому что спаривание имеет положительное значение, равное одному by .. В противном случае /Ду^О, потому что спаривание Y имеет отрицательное значение, не равное любому Ьу/. Повторяя процесс, мы дешифруем С, от тг к щ. Аналогичным образом мы можем расшифровать С,. Пусть y=^cI3q)/4p,q^ = = еЦ,-1)г+1 (а(ы)г+1р)+- + mir {аігр10)! e(aiA в) = = е(^_1)г+1(аМг+1Р)+... + mir(airP)-airP, q) = _е(Ці-і>+!а(г-і>+і +- + mirair-air)p,Q) = е(*Цм)г+12<н> +... + mir2ir~1 -T~1)p,q)= = (е(Р,Є^(‘ «Инфокоммуникационные технологии» Том 10, № 4, 2012 8 Бабенко М.Г., Ляхов П.А., Червяков Н.И. Поскольку by = , то (/ = 1,2,3,...X '). Если mir=l, то /(г) = 0, потому что Y является положительным значением спаривания и равно одному из by. В противном случае у^(у)^0, потому что Y есть отрицательное значение спаривания и не равно любому Ьу. Повторяя этот процесс, дешифруем Cj из mir с ■ В итоге получим х, =4c,Q)/(e(C„Q)..4c^,Q])= = ~ Q — — ^н-1>б) = то есть мы расшифровываем Си аналогичным образом с расшифровкой Ct. Вычислительная сложность Вычислительная сложность спаривания равна logр. В шифровании вычислительная сложность сложения на эллиптической кривой тоже полиномиальная logр. В дешифровании сложность вычисления частного значения спаривания также имеет полиномиальное время, так как они вычисляются по mod р. Хотя мы судим о том, что значение спаривания положительно или отрицательно путем расшифровки функции, оно вычисляется за полиномиальное время, поскольку вычитание и умножение по mod р рассчитывается за константу. Исследования выполнены при поддержке гранта РФФИ 12-07-00482-а. Заключение Рюкзачная криптосистема на эллиптической кривой обладает следующими преимуществами относительно криптосистемы рюкзака над числами. Криптосистема не расшифровывается LLL-алгоритмом за счет использования эллиптической кривой. Шифротексты - это точки эллиптической кривой. Вычислительная сложность расшифровки - полиномиальное время с помощью функции расшифровки. Все арифметические операции с точками эллиптической кривой можно эффективно выполнять в системе остаточных классов с использованием приближенного метода [3].