Кіріспе
Жасырын өрістер теңдеулері (HFE), сонымен қатар HFE тұзақ функциясы деп те аталады, 1996 жылы Eurocrypt конференциясында ұсынылған және Мацумото мен Имаи жүйесінің идеясына негізделген Жак Патарин ұсынған ашық кілт криптожүйесі. Ол жеке кілт пен ашық кілт арасындағы байланысты жасыру үшін әртүрлі өлшемдегі шекті өрістердегі көпмүшелерге негізделген. HFE – бұл HFE негізгі және HFE комбинаторлық түрлерінен тұратын отбасы. HFE криптожүйелерінің отбасы көп айнымалы квадраттық теңдеулер жүйесінің (MQ проблемасы деп аталады) шешімін табудың қиындығына негізделген, себебі ол кеңейту өрісі мен жеке көпмүшелерді жасыру үшін жеке аффиндік түрлендірулерді пайдаланады. Жасырын өрістер теңдеулері сондай-ақ цифрлық қолтаңба схемаларын құру үшін қолданылған, мысалы, Quartz және Sflash.
Hidden Fields Equations (HFE), also known as HFE trapdoor function, is a public key cryptosystem which was introduced at Eurocrypt in 1996 and proposed by Jacques Patarin following the idea of the Matsumoto and Imai system. It is based on polynomials over finite fields of different size to disguise the relationship between the private key and public key. HFE is in fact a family which consists of basic HFE and combinatorial versions of HFE. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate quadratic equations (the so called MQ problem) since it uses private affine transformations to hide the extension field and the private polynomials. Hidden Field Equations also have been used to construct digital signature schemes, e. g. Quartz and Sflash.
Математикалық білімі
Жасырын өріс теңдеулерінің қалай жұмыс істейтінін түсіну үшін негізгі ұғымдардың бірі – бірдей базалық өріс үстіндегі екі кеңейту өрісі үшін, айнымалылар арқылы берілген көпөлшемді көпмүшелер жүйесін функция ретінде қарастыру мүмкіндігі. Шамамен барлық қолданыстарда көпмүшелер квадраттық, яғни 2-дәрежелі болады. Біз ең қарапайым көпмүшелерден, атап айтқанда мономиалдардан бастаймыз және олардың квадраттық теңдеулер жүйесіне қалай алып келетінін көрсетеміз. 2-нің дәрежесіндегі шекті өріс және оның кеңейту өрісін қарастырайық. gcd шарты, картаның бір-бірге сәйкес болуын талап етуге тең, ал оның керісі – картаның көбейтуге кері шамасы болып табылады. Кездейсоқ элементті таңдап, анықтаймыз:
Take a random element Define by
Let to be a basis of as an vector space. We represent with respect to the basis as and Let be the matrix of the linear transformation with respect to the basis , i. e. such that
for Additionally, write all products of basis elements in terms of the basis, i. e.:
for each The system of equations which is explicit in the and quadratic in the can be obtained by expanding (1) and equating to zero the coefficients of the
Choose two secret affine transformations and , i. e. two invertible matrices and with entries in and two vectors and of length over and define and via:
By using the affine relations in (2) to replace the with , the system of equations is linear in the and of degree 2 in the Applying linear algebra it will give explicit equations, one for each as polynomials of degree 2 in the .
-ны векторлық кеңістік ретінде қарастырайық. -ны негізге қатысты түрлендіріп жазайық және -ны негізге қатысты сызықтық түрлендірудің матрицасы деп белгілейік, яғни:
Take a random element Define by
Let to be a basis of as an vector space. We represent with respect to the basis as and Let be the matrix of the linear transformation with respect to the basis , i. e. such that
for Additionally, write all products of basis elements in terms of the basis, i. e.:
for each The system of equations which is explicit in the and quadratic in the can be obtained by expanding (1) and equating to zero the coefficients of the
Choose two secret affine transformations and , i. e. two invertible matrices and with entries in and two vectors and of length over and define and via:
By using the affine relations in (2) to replace the with , the system of equations is linear in the and of degree 2 in the Applying linear algebra it will give explicit equations, one for each as polynomials of degree 2 in the .
барлық үшін. Сонымен қатар, негіз элементтерінің барлық көбейтінділерін негіз арқылы жазайық, яғни:
Take a random element Define by
Let to be a basis of as an vector space. We represent with respect to the basis as and Let be the matrix of the linear transformation with respect to the basis , i. e. such that
for Additionally, write all products of basis elements in terms of the basis, i. e.:
for each The system of equations which is explicit in the and quadratic in the can be obtained by expanding (1) and equating to zero the coefficients of the
Choose two secret affine transformations and , i. e. two invertible matrices and with entries in and two vectors and of length over and define and via:
By using the affine relations in (2) to replace the with , the system of equations is linear in the and of degree 2 in the Applying linear algebra it will give explicit equations, one for each as polynomials of degree 2 in the .
әрқайсысы үшін. (1) теңдеуін кеңейту және коэффициенттерді нөлге теңеу арқылы, -қа қатысты екі құпия аффиндік түрлендіру, яғни, -дегі жазбалары бар екі инвертирленетін матрица және -дегі ұзындығы бар екі векторды анықтаймыз:
Take a random element Define by
Let to be a basis of as an vector space. We represent with respect to the basis as and Let be the matrix of the linear transformation with respect to the basis , i. e. such that
for Additionally, write all products of basis elements in terms of the basis, i. e.:
for each The system of equations which is explicit in the and quadratic in the can be obtained by expanding (1) and equating to zero the coefficients of the
Choose two secret affine transformations and , i. e. two invertible matrices and with entries in and two vectors and of length over and define and via:
By using the affine relations in (2) to replace the with , the system of equations is linear in the and of degree 2 in the Applying linear algebra it will give explicit equations, one for each as polynomials of degree 2 in the .
(2) аффиндік қатынастарды пайдаланып -ты -мен алмастырсақ, теңдеулер жүйесі -ға қатысты сызықтық және -ға қатысты 2-дәрежелі болады. Сызықтық алгебраны қолдану арқылы, біз әрқайсысы үшін 2-дәрежелі көпмүше ретінде -ға қатысты нақты теңдеулер аламыз.
Take a random element Define by
Let to be a basis of as an vector space. We represent with respect to the basis as and Let be the matrix of the linear transformation with respect to the basis , i. e. such that
for Additionally, write all products of basis elements in terms of the basis, i. e.:
for each The system of equations which is explicit in the and quadratic in the can be obtained by expanding (1) and equating to zero the coefficients of the
Choose two secret affine transformations and , i. e. two invertible matrices and with entries in and two vectors and of length over and define and via:
By using the affine relations in (2) to replace the with , the system of equations is linear in the and of degree 2 in the Applying linear algebra it will give explicit equations, one for each as polynomials of degree 2 in the .
Көпвариантты криптожүйе
HFE отбасының негізгі идеясы – осыны көпөлшемді криптожүйе ретінде пайдалану, құпия кілтті белгілі бір шекті өрістегі бір белгісізі бар полиномнан бастау (әдетте мәні қолданылады). Бұл полиномды арқылы оңай кері аударуға болады, яғни, егер шешім болса, теңдеудің кез келген шешімін табу мүмкін. Құпия түрлендіру – шифрды ашу және/немесе қолтаңба – осы кері аударуға негізделген. Жоғарыда түсіндірілгендей, тұрақты негізді пайдалана отырып, теңдеулер жүйесімен көрсетуге болады. Криптожүйе құру үшін полиномды оның бастапқы құрылымын жасырып, кері аударудың алдын тоқтату үшін өзгерту қажет. Бұл шекті өрістерді векторлық кеңістік ретінде қарастыру және екі сызықтық аффиндік түрлендіруді таңдау арқылы жасалады және . Осы үштік жеке кілтті құрайды. Жеке полином арқылы анықталады. Ал ашық кілт – . HFE-дегі MQ тұзақ есігінің схемасы төменде көрсетілген:
HFE полиномы
Жеке полиномиал дәрежесі бар және сақинасынан алынған элементі болып табылады. Егер полиномиалдың мүшелері ең көп дегенде квадраттық мүшелерден тұрса, онда ол қоғамдық полиномиалды кішкентай ұстап тұрады.
Шифрлау және шифрлауды шешу
Ашық кілт көпөлшемді полиномдар арқылы беріледі. Сондықтан, оны шифрлеу үшін хабарламадан мәліметтерді жіберу қажет, яғни біз вектор деп есептейміз. Хабарламаны шифрлеу үшін біз әрбір мәнді есептейміз. Шифртекст келесідей: . Шифрлеуді түсіну үшін шифрлеуді түсіндірейік. Бұл мәліметтер жіберушіге қолжетімді емес. Хабарламадағы мәнді есептеу арқылы бірінші кезекте қолданамыз, нәтижесінде біз аламыз. Осы сәтте мәліметтерден жіберіледі, сондықтан біз жеке полиномды қолдана аламыз, ол және бұл нәтиже деп белгіленеді. Тағы бір рет векторға жіберіледі және трансформация қолданылады, содан кейін соңғы нәтиже шығарылады. Шифрды ашу үшін жоғарыдағы қадамдар кері тәртіппен орындалады. Бұл жеке кілт белгілі болса ғана мүмкін. Шифрді ашудағы маңызды қадам - және инверсиясы емес, керісінше, шешімін есептеу. егер қажетті емес болса, осы инверсияға бірнеше шешімдер болуы мүмкін (барлық шешімдердің саны d-ден аспайды, себебі - d дәрежелі полином). Артық ақпарат деп белгіленген артықшылық, дұрыс шешімді таңдау үшін хабарламаның бірінші қадамында қосылады. Төмендегі схема шифрлеу үшін негізгі HFE-ді көрсетеді.
To understand decryption let us express encryption in terms of Note that these are not available to the sender. By evaluating the at the message we first apply , resulting in At this point is transferred from so we can apply the private polynomial which is over and this result is denoted by Once again, is transferred to the vector and the transformation is applied and the final output is produced from
To decrypt , the above steps are done in reverse order. This is possible if the private key is known. The crucial step in the deciphering is not the inversion of and but rather the computations of the solution of Since is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions since is a polynomial of degree d). The redundancy denoted as is added at the first step to the message in order to select the right from the set of solutions The diagram below shows the basic HFE for encryption.
HFE ауытқулары
Жасырын өріс теңдеулерінің төрт негізгі түрі бар, атап айтқанда +, , v және f, оларды әртүрлі жолдармен үйлестіруге болады. Негізгі принцип мынадай:
01. + белгісі – жария теңдеулерді кейбір кездейсоқ теңдеулермен сызықтық араластырудан тұрады. 02. Белгі Ади Шамирге тиесілі және жария теңдеулердің артық "r" мүшесін жоюға арналған. 03. f белгісі жария кілттің кейбір кіріс айнымалыларын бекітуден тұрады. 04. v белгісі – құрылым ретінде анықталған және кейде өте күрделі, функцияның керісін тек "сірке су" деп аталатын v айнымалыларының бірі бекітілген жағдайда ғана табуға болады. Бұл идея Жаку Патаринге қатысты. Жоғарыда аталған операциялар функцияның құпия кілт арқылы шешілу мүмкіндігін белгілі бір деңгейде сақтайды. HFE және HFEv қолтаңба схемаларында өте пайдалы, себебі олар қолтаңба жасау процесін баяулатудан сақтайды және HFE-нің жалпы қауіпсіздігін арттырады. Ал шифрлау үшін HFE және HFEv екеуі де шифрлау процесін баяулатады, сондықтан көптеген теңдеулерді жоюға (HFE) немесе тым көп айнымалыларды қосуға (HFEv) болмайды. HFE және HFEv екеуі де Quartz алу үшін қолданылды. Шифрлау үшін жағдай HFE+ арқылы жақсырақ, себебі шифрлау процесінің уақыты өзгермейді, бірақ жария кілтте айнымалылардан гөрі теңдеулер көп болады.