The NTRU Cryptosystem:Implementation and Comparative AnalysisSemester ProjectECE 646, Fall 2001Professor Kris GajGeorge Mason UniversityAuthor:Rodney D'SouzaAbstractThe NTRU cryptosystem is a relatively new public key cryptographic algorithmthat was first introduced in 1996. The main advantage of this algorithm is that it runsmuch faster than conventional public key algorithms such as RSA. This speed advantageis especially large in key generation, which is often the most important part of public keycryptography. This paper introduces the ideas behind NTRU and presents results from aimplementation in Java. The results include a comparison with RSA in terms of keygeneration, encryption and decryption speeds.1. IntroductionPublic key (PK) cryptography, also known as asymmetric cryptography, is moreoften used today in the areas of key exchange and digital signatures than in encryptionand decryption of large amounts of data. Perhaps the main reason why today’s PKsystems such as RSA are not used for bulk encryption/decryption is that they are ordersof magnitude slower than symmetric key systems. Nonetheless, key exchange and digitalsignature are applications that are very important and are currently best performed by aPublic Key Infrastructure (PKI).Since the introduction of RSA in 1977 it has been the only widely used public keyencryption algorithm. In the mid-to-late 1980s, Elliptic Curve Cryptography (ECC) wasintroduced and has since been slowly gaining acceptance. It has recently also begun to bestandardized. Other algorithms, such as ElGamel and braid systems have also enjoyedlimited success. The subject of this paper, the NTRU algorithm, is a proprietaryalgorithm patented by NTRU Cryptosystems which claims to dramatically reduce one ofthe big problems in PK cryptography, namely speed. For this project, the algorithm wasimplemented in Java and compared to RSA on the basis of speed of three operations: keygeneration, encryption and decryption.The rest of this paper is organized as follows: Section 2 introduces the conceptsbehind the NTRU system and briefly describes the key generation, encryption anddecryption methodologies. Section 3 describes the author’s software implementation ofthe NTRU algorithm for this project. Section 4 compares the NTRU implementation tothe RSA algorithm on the basis of speed and security. Section 5 draws some conclusionsabout NTRU from the results of the implementation and gives some suggestions of howthis project could be expanded upon for further analysis.2. The NTRU Algorithm2.1 Basic AlgorithmThe NTRU algorithm is based on embedding messages in a polynomial ring, R.The ring is defined such that the multiplication operation of the polynomials is wrappedaround the degree (“size”) of the polynomial rather than expanding the degree of thepolynomial. Further, each coefficient of the polynomial is an integer that is reducedmodulo certain parameters, after every math operation. The notation for the ring is givenas :R = Z[X]/(XN-1)where Z represents the set of integers and N is 1 more than the degree of the polynomial.A full mathematical explanation is beyond the scope of this paper and the reader isreferred to the literature for an in depth analysis of NTRU cryptography.NTRU Cryptosystems has published several versions of the NTRU algorithm, ofwhich two basic algorithms were implemented for this project. A detailed explanation ofthe basic algorithm, including an illustrative example and a proof of why it works isgiven in [1]. Next a brief explanation of the algorithm is presented.Key creation is as follows: Bob chooses 2 random polynomials f and g that are inthe defined ring R and that whose inverses exist in the ring modulo key parameters p andq. These inverses are denoted Fp and Fq respectively, and need to be computed for thechosen f. If the inverse of either does not exist another f is chosen and the process isrepeated. Next Bob generates the public key as the polynomial h:h = Fq* g mod qwhere g is also a randomly chosen polynomial in R. Note that f and g are “randomly”chosen in R but have a specific amount of coefficients that are 0, +1 and –1. The privatekey is the polynomial f along with the inverses Fp and Fq. N, p, and q are consideredparameters of the algorithm rather than part of either key.Encryption is as follows: Alice, wishing to send a binary message m to Bob,begins by randomly choosing a polynomial r that is in R. She then performs theencryption by computinge = pr*h + m mod q.Note that scalar multiplication of integer p with polynomial r is simply multiplication ofeach coefficient of r with p. Multiplication of r with h is wrapped around the ring size, asstated above.Decryption is as follows: Bob begins to decrypt the message e by first computinga = f*e mod qand then reducing the coefficients of a to be between –q/2 to q/2. Then he obtains themessage m by computingm = a * Fp,where Fp is part of his private key and is the multiplictive inverse of f mod p, as derivedin the key generation.N The polynomials in the ring R have degree N-1. (Non-secret)q The large modulus to which each coefficient is reduced. (Non-secret)p The small modulus to which each coefficient is reduced. (Non-secret)f A polynomial that is the private key.g A polynomial that is used to generate the public key h from f (Secret butdiscarded after initial use)h The public key, also a polynomialr The random “blinding” polynomial (Secret but discarded after initial use)dff has df coefficients equal to 1 and df-1 coefficients equal to –1dgg has dg coefficients equal to 1 and dg equal to –1drr has dr coefficients equal to 1 and dr equal to –1Table 1. NTRU keys and parametersTable 1 lists the parameters of the basic algorithm along with a brief explanationof each. Table 2 lists parameter values for various levels of security as reported byNTRU Cryptosystems. The NTRU algorithm is actually probabilistic in nature; i.e. thereis a small chance of decryption failure. With the appropriate choice of parameters thedecryption probability can be made to be on the order of 10-25 or less. The values listedin Table 2 yield such small decryption failure rates. These parameters are purported to beused in NTRU Cryptosystems commercial applications. A more detailed explanation ofthe security levels listed in the table is given in Section 4.Nq p dfdg drLow Security 107 64 3 15 12 5Moderate Security 167 128 3 61 20 18High Security
View Full Document
Unlocking...