Кіріспе
Торға негіделген ашық кілт криптожүйесі
The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is an NTRU lattice based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice (which is not known to be breakable using quantum computers). It relies on the presumed difficulty of factoring certain polynomials in a truncated polynomial ring into a quotient of two polynomials having very small coefficients. Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices. Careful choice of parameters is necessary to thwart some published attacks. Since both encryption and decryption use only simple polynomial multiplication, these operations are very fast compared to other asymmetric encryption schemes, such as RSA, ElGamal and elliptic curve cryptography. However, NTRUEncrypt has not yet undergone a comparable amount of cryptographic analysis in deployed form. A related algorithm is the NTRUSign digital signature algorithm. Specifically, NTRU operations are based on objects in a truncated polynomial ring with convolution multiplication and all polynomials in the ring have integer coefficients and degree at most N 1:
That in this ring has the effect that multiplying a polynomial by rotates the coefficients of the polynomial. A map of the form for a fixed thus produces a new polynomial where every coefficient depends on as many coefficients from as there are nonzero coefficients in
NTRU has three integer parameters (N, p, q), where N is the polynomial degree bound, p is called the small modulus, and q is called the large modulus; it is assumed that N is prime, q is always (much) larger than p, and p and q are coprime. Plaintext messages are polynomials modulo p but ciphertext messages are polynomials modulo q. Concretely the ciphertext consists of the plaintext message plus a randomly chosen multiple of the public key, but the public key may itself be regarded as a multiple of the small modulus p, which allows the holder of the private key to extract the plaintext from the ciphertext.
NTRUEncrypt ашық кілт криптожүйесі, сондай-ақ NTRU шифрлау алгоритмі деп аталады, RSA және эллиптік қисық криптографиясына (ECC) NTRU торға негіделген баламасы болып табылады және ол тордағы ең қысқа вектор проблемасына негізделген (кванттық компьютерлерді пайдалану арқылы бұзу мүмкін емес деп белгілі). Ол қысқартылған полиномдық сақинадағы белгілі бір полиномдарды өте кішкентай коэффициенттері бар екі полиномның бөліндісіне жіктеудің күрделі екендігіне негізделген. Криптожүйені бұзу, белгілі бір торларда торды азайтудың алгоритмдік мәселесімен тығыз байланысты, бірақ эквивалентті емес. Кейбір жарияланған шабуылдарды болдырмау үшін параметрлерді мұқият таңдау қажет. Шифрлау және шифрлауды шешуде тек қарапайым полиномдық көбейту қолданылатындықтан, бұл операциялар RSA, ElGamal және эллиптік қисық криптографиясы сияқты басқа асимметриялық шифрлау схемаларымен салыстырғанда өте жылдам. Дегенмен, NTRUEncrypt әлі де қолданылған түрінде криптографиялық талдаудың салыстырмалы көлеміне ұшырамады. Осыған байланысты алгоритм – NTRUSign цифрлық қолтаңба алгоритмі. Нақтырақ айтқанда, NTRU операциялары конволюциялық көбейтумен қысқартылған полиномдық сақинадағы объектілерге негізделген және сақинадағы барлық полиномдардың бүтін сандық коэффициенттері және ең көп дегенде N-1 дәрежесі бар: Бұл сақинада полиномды көбейту полиномның коэффициенттерін жылжытады. Сондықтан, тұрақты формадағы карта жаңа полиномды жасайды, онда әрбір коэффициентте нөлдік емес коэффициенттердің санына тең коэффициенттерге тәуелділік бар. NTRU үш бүтін параметрге ие (N, p, q), мұнда N – полиномдық дәреже шегі, p – кіші модуль, ал q – үлкен модуль деп аталады; N – жай сан, q әрқашан p-ден (әлдеқайда) үлкен, ал p және q өзара жай. Ашық мәтіндік хабарламалар p модулі бойынша полиномдар, ал шифрланған мәтіндік хабарламалар q модулі бойынша полиномдар болып табылады. Нақтырақ айтқанда, шифрланған мәтін ашық мәтіндік хабарламадан және ашық кілттің кездейсоқ таңдалған еселігінен тұрады, бірақ ашық кілттің өзі кіші модульдің еселігі ретінде қарастырылуы мүмкін, бұл жеке кілттің иесіне шифрланған мәтіннен ашық мәтінді алуға мүмкіндік береді.
The NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is an NTRU lattice based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice (which is not known to be breakable using quantum computers). It relies on the presumed difficulty of factoring certain polynomials in a truncated polynomial ring into a quotient of two polynomials having very small coefficients. Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices. Careful choice of parameters is necessary to thwart some published attacks. Since both encryption and decryption use only simple polynomial multiplication, these operations are very fast compared to other asymmetric encryption schemes, such as RSA, ElGamal and elliptic curve cryptography. However, NTRUEncrypt has not yet undergone a comparable amount of cryptographic analysis in deployed form. A related algorithm is the NTRUSign digital signature algorithm. Specifically, NTRU operations are based on objects in a truncated polynomial ring with convolution multiplication and all polynomials in the ring have integer coefficients and degree at most N 1:
That in this ring has the effect that multiplying a polynomial by rotates the coefficients of the polynomial. A map of the form for a fixed thus produces a new polynomial where every coefficient depends on as many coefficients from as there are nonzero coefficients in
NTRU has three integer parameters (N, p, q), where N is the polynomial degree bound, p is called the small modulus, and q is called the large modulus; it is assumed that N is prime, q is always (much) larger than p, and p and q are coprime. Plaintext messages are polynomials modulo p but ciphertext messages are polynomials modulo q. Concretely the ciphertext consists of the plaintext message plus a randomly chosen multiple of the public key, but the public key may itself be regarded as a multiple of the small modulus p, which allows the holder of the private key to extract the plaintext from the ciphertext.
Тарих
NTRUEncrypt Public Key Cryptosystem салыстырмалы түрде жаңа криптожүйе болып табылады. Жүйенің алғашқы нұсқасы, жай ғана NTRU деп аталған, 1996 жылы үш математик (Джеффри Хоффштейн, Джилл Пифер және Джозеф Х. Сильверман) әзірледі. 1996 жылы осы математиктер Дэниел Лиманмен бірге NTRU Cryptosystems, Inc. компаниясын құрды және криптожүйеге патент (қазір мерзімі бітті) алды. Соңғы он жыл ішінде адамдар криптожүйені жетілдіру жұмыстарын жүргізіп келеді. Криптожүйенің алғашқы таныстырылысынан бері, жүйенің өнімділігі мен қауіпсіздігін жақсарту үшін бірнеше өзгерістер енгізілді. Көптеген өнімділікті жақсартулар процестерді жылдамдатуға бағытталған. 2005 жылға дейін NTRUEncrypt шифрлаудың сәтсіздіктерін сипаттайтын әдебиеттер кездеседі. Қауіпсіздікке қатысты, NTRUEncrypt-тің алғашқы нұсқасынан бастап, қазіргі кездегі барлық белгілі шабуылдарға және есептеу қуатының артуына қатысты қауіпсіз болып көрінетін жаңа параметрлер енгізілді. Қазір жүйе IEEE P1363 стандарттарына, торлы негіздегі ашық кілт криптографиясы (IEEE P1363.1) бойынша толыққанды сәйкес келеді. NTRUEncrypt Public Key Cryptosystem-ның жылдамдығының арқасында (http://bench.cr.yp.to сайтындағы сынақ нәтижелерін қараңыз) және оның аз жадты пайдалануы (төменде қараңыз) оны мобильді құрылғылар және смарт-карталар сияқты қолдануларда пайдалануға болады. 2011 жылдың сәуір айында NTRUEncrypt қаржылық қызметтер саласында қолдану үшін X9.98 стандарты ретінде қабылданды.