Кіріспе
криптографияда XTR – ашық кілтпен шифрлау алгоритмі. XTR – «ECSTR» дегенді білдіреді, бұл тиімді және ықшам кіші топтың іздестіру ұсынылымының (Efficient and Compact Subgroup Trace Representation) аббревиатурасы. Бұл шекті өрістің көбейту тобының кіші тобының элементтерін ұсыну әдісі. Ол үшін, XTR кіші топтың элементтерін ұсыну үшін трассаны қолданады. Қауіпсіздік тұрғысынан алғанда, XTR шекті өрістің толық көбейту тобындағы дискретті логарифмге қатысты мәселелерді шешудің қиындығына негізделген. Көптеген криптографиялық протоколдар шекті өрістің толық көбейту тобының генераторына негізделгенінен өзгеше, XTR белгілі бір жай сан ретінің (prime order) кіші тобының генераторын қолданады. Параметрді дұрыс таңдау арқылы, генератор арқылы құрылған топта дискретті логарифмдерді есептеу, жалпы алғанда, оны есептеумен бірдей қиын болады және осылайша XTR-дің криптографиялық қолданыстары қауіпсіздіктің толық деңгейін сақтай отырып, арифметиканы пайдаланады, бұл байланыс және есептеу шығындарының айтарлықтай үнемдеуіне әкеледі. XTR-дің басқа да артықшылықтары – оның жылдам кілт жасауы, кілттің кішкентай көлемі және жылдамдығы.
In cryptography, XTR is an algorithm for public key encryption. XTR stands for 'ECSTR', which is an abbreviation for Efficient and Compact Subgroup Trace Representation. It is a method to represent elements of a subgroup of a multiplicative group of a finite field. To do so, it uses the trace over to represent elements of a subgroup of
From a security point of view, XTR relies on the difficulty of solving Discrete Logarithm related problems in the full multiplicative group of a finite field. Unlike many cryptographic protocols that are based on the generator of the full multiplicative group of a finite field, XTR uses the generator of a relatively small subgroup of some prime order of a subgroup of With the right choice of , computing Discrete Logarithms in the group, generated by , is, in general, as hard as it is in and thus cryptographic applications of XTR use arithmetics while achieving full security leading to substantial savings both in communication and computational overhead without compromising security. Some other advantages of XTR are its fast key generation, small key sizes and speed.
XTR негіздері
XTR элементтері бар шекті өрістің көбейтуші тобының XTR супертобы деп аталатын кіші тобының, әдетте XTR кіші тобы немесе жай ғана XTR тобы деп аталатын кіші тобын пайдаланады. XTR супертобының реті , мұндағы p – жеткілікті үлкен жай сан, ал q – оған бөлінетін жай сан. XTR кіші тобының реті q-ға тең және генераторы g болатын , кіші тобындағы циклдік топ болып табылады. Келесі үш абзацта XTR супертобының элементтерін элементі арқылы, элементінің орнына қалай бейнелеуге болатыны және арифметикалық амалдарды элементінің ішінде, элементінің орнына қалай орындауға болатыны сипатталады.
Криптографиялық схемалар
Бұл бөлімде элементтердің іздерін қолдана отырып, жоғарыда айтылған түсініктерді криптографияға қалай қолдануға болатыны түсіндіріледі. Жалпы алғанда, XTR дискретті логарифм мәселесіне (немесе топтың ішіндегі дискретті логарифм мәселесіне) негізделген кез келген криптожүйеде қолданылуы мүмкін. XTR-дың екі маңызды қолданысы – Diffie-Hellman кілт алмасу протоколы және ElGamal шифрлауы. Біз ең алдымен Diffie-Hellman протоколынан бастаймыз.
XTR-DH кілті туралы келісім
Біз Алиса мен Бобтың екеуінің де XTR ашық кілт деректеріне қол жетімділігі бар және олар ортақ құпия кілт туралы келісуді жоспарлап отыр деп есептейміз. Олар мұны Diffie–Hellman кілт алмасуының келесі XTR нұсқасын қолдану арқылы істей алады:
Алиса кездейсоқ түрде , шартымен таңдайды, 1-алгоритммен есептейді және Бобқа жібереді. Боб Алисадан алады, кездейсоқ түрде , шартымен таңдайды, 1-алгоритмді қолданып есептейді және Алисаға жібереді. Алиса Бобтан алады, 1-алгоритммен есептейді және Бобқа сәйкес келетін шаманы есептейді. Боб да 1-алгоритмді қолданып есептейді және сондай-ақ шаманы есептейді.
Қауіпсіздік
Жоғарыда түсіндірілген XTR шифрлау схемасының қауіпсіздік қасиеттерін бағалау үшін, ең алдымен XTR тобының қауіпсіздігін тексеру керек, яғни онда дискретті логарифм мәселесін шешудің қыйынырақ екенін анықтау қажет. Ал келесі бөлімде XTR тобындағы дискретті логарифм мәселесі мен XTR нұсқасындағы дискретті логарифм мәселесінің арасындағы теңдестік, элементтердің іздерін ғана қолдана отырып, дәлелденеді.
Жалпы дискретті логарифмдер
Енді ретінің көбейту тобы болайық DiffieHellman протоколының қауіпсіздігі есептеудің DiffieHellman (DH) проблемасына негізделген. Біз DH проблемасына байланысты тағы екі проблема бар деп жазамыз. Біріншісі - берілгенді анықтау үшін Диффи Хелман шешімі (DHD) мәселесі, ал екіншісі - берілгенге табу үшін дискретті логарифм (DL) мәселесі. DL мәселесі DH мәселесі сияқты қиын және егер DL мәселесі шешілмейтін болса, онда басқа екеуі де қиын деп есептеледі. DL проблемасының біріншілік факторлануын ескере отырып, PohligHellman алгоритміне байланысты DL проблемасының барлық біріншілік реті бар ішкі топтарында азайтуға болады. Сондықтан оны жай сан деп санауға болады. Кейбір үшін кеңейту өрісінің көбейту тобының бірінші реттік субтобы үшін, жүйеге шабуыл жасаудың екі ықтимал жолы бар. Бір адам бүкіл көбейту тобына немесе кіші топқа назар аударуы мүмкін. Көбейтуші топқа шабуыл жасау үшін ең танымал әдіс - Сандық өріс сырғаның дискретті логарифмдік нұсқасы немесе балама ретінде кіші топта Pollard's rho әдісі сияқты операцияларды қабылдайтын бірнеше әдістердің біреуін қолдануға болады. Екі тәсіл үшін де DL мәселесінің қиындығы in-тің ең кіші қоршаудағы қосалқы өрісінің көлеміне және оның алғашқы реті мөлшеріне байланысты. Егер өзі XTR тобындағы ең кіші қоршаудағы қосалқы өрісі болса және жеткілікті үлкен болса, онда DL мәселесі DL проблемасының жалпы DL проблемасы сияқты қиын болады. XTR параметрлері қазір кіші емес, жеткілікті үлкен және шын қосалқы өріске енбейді.
The DL problem is at least as difficult as the DH problem and it is generally assumed that if the DL problem in is intractable, then so are the other two. Given the prime factorization of the DL problem in can be reduced to the DL problem in all subgroups of with prime order due to the Pohlig–Hellman algorithm. Hence can safely be assumed to be prime. For a subgroup of prime order of the multiplicative group of an extension field of for some , there are now two possible ways to attack the system. One can either focus on the whole multiplicative group or on the subgroup. To attack the multiplicative group the best known method is the Discrete Logarithm variant of the Number Field Sieve or alternatively in the subgroup one can use one of several methods that take operations in , such as Pollard's rho method. For both approaches the difficulty of the DL problem in depends on the size of the minimal surrounding subfield of and on the size of its prime order If itself is the minimal surrounding subfield of and is sufficiently large, then the DL problem in is as hard as the general DL problem in
The XTR parameters are now chosen in such a way that is not small, is sufficiently large and cannot be embedded in a true subfield of , since and is a divisor of , but it does not divide and thus cannot be a subgroup of for It follows that the DL problem in the XTR group may be assumed as hard as the DL problem in .