DOC PREVIEW
MASON ECE 646 - Performance Evaluation of Public Key Cryptosystems

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

I. INTRODUCTIONIII. DESCRIPTION OF XTRPerformance Evaluation of Public KeyCryptosystemsRohan Malewar, Vijay Koneru, Rakesh Malireddy and Vasunandan PeddiAbstract:- NTRU a Public Key Crypto System ( PKCS) which works over a finite ring of polynomials for providing security whereas the XTR can be applied over any system that uses Discrete Logarithm Problem for its security. This papers evaluates the performances of bothXTR and NTRU in terms of time taken for key generation, encryption and decryption at different security levels.I. INTRODUCTIONPublic key cryptography is a form ofcryptography which generally allows users tocommunicate securely without having prioraccess to a shared secret key. The revolutionaryidea was to split the key into two so that eachparty has both a public key (which can be freelydistributed) and a private key (which is knownonly to the party concerned). The key pairs aregenerated in such a way that they have a specificmathematical relationship, but at the same time itis computationally infeasible to generate theprivate key given knowledge of the public key. Public-key cryptography is an integralcomponent of secure communication. Currently,the most widely used public key system is RSA,[3] which was created by Rivest, Shamir andAdelman in 1978 and is based on the difficultyof factoring large numbers. The need formobility has altered existing securityrequirements and public-key systems must nowbe capable of performing at high speed, whilst atthe same time providing robust security. XTRand NTRU are two recently introduced public-key algorithms that were designed withefficiency specifically in mind. In this project weaim to Performance Evaluation of Public keyCryptosystems XTR[1] &NTRU[2].Fig 1.1 Public key cryptosystem example.II. DESCRIPTION OF NTRUNTRU is the first public-key algorithm not basedon either integer factorisation or the discretelogarithm problem to be considered secure bythe cryptographic community. The algorithm wasintroduced in 1998 by Jeffrey Hoffstein, JillPipher and Joseph Silverman and promisesefficient performance combined with robustsecurity, in much the same way as XTR. UnlikeXTR, however, NTRU is a brand newcryptosystem and is capable of encryption in itsown right. The algorithm’s security is based onthe difficulty of finding extremely short vectorsin lattices of very high dimension. NTRU’screators claim that it is resistant to parallelprocessing attacks and that this fact, combinedwith its disposable key technology, considerablyreduces the risk of power attacks, timing attacksand security breaches due to lost or interceptedkeys. Nonetheless, the real area of interest lies inNTRU’s performance and whether or not it issuitable for integration into low-cost and mobiledevices.The mathematics behind NTRU is based on themanipulation of lists of small integers thatrepresent the coefficients of truncatedpolynomials. Let R be the ring of truncatedpolynomials of degree (N – 1) with integercoefficients. Thus, a member of R will take thefollowing form:a = a0 + a1X + a2X2 + … + aN-2XN-2 + aN-1XN-1The polynomials in R may be added together inthe usual way by simply adding theircoefficients, i.e.:a + b = (a0 + b0) + (a1 + b1)X + … + (aN-1 + bN-1)XN-1Multiplication in R is slightly different fromusual in that, after the polynomials have beenmultiplied together, XN is replaced by 1, XN+1 isreplaced by X, XN+2 is replaced by X2, and so on.The general formula for multiplying polynomialsin R is:a * b = c0 + c1X + c2X2 + … + cN-2XN-2 + cN-1XN-1whereck = a0bk + a1bk-1 + … + akb0 + ak+1bN-1 + ak+2bN-2 + …+ aN-1bk+1The list of parameters in NTRU implementationare as follows:N - The polynomials in the truncated polynomialring have degree N-1.N should be prime.q - Large modulus: usually, the coefficients ofthe truncated polynomials will be reduced modq.p - Small modulus. As the final step indecryption, the coefficients of the message arereduced mod p.Relation of p and q: p and q should be selectedin such a way that they are relatively to prime toeach other and q should be large compared to p.I.e. gcd (p, q) =1.A. Key Generation: For the public key, the user must:Choose a secret key which is a randomlygenerated polynomial “f” which belongs to theRing R, with coefficients reduced modulo p. Choose “g” which is also a randomly generatedpolynomial that belongs to the Ring R, withcoefficients reduced modulo p, and compute theinverse polynomial Fq of the secret key f modulo q.Similarly Fp is also computed by taking inverseof the polynomial f with reduced modulo p. Ifinverse of “f” does not exist then the process isrepeated until we get the inverse. The polynomial f has df coefficients equal to +1,(df-1) coefficients equal to -1, and the rest equalto 0. The polynomial g has dg coefficients equal to+1, dg coefficients equal to -1,and the rest equalto 0.Once Fq has been computed, the public key, h, isfound ash = Fq * g (mod q)B. Algorithm for key generation:Before commencing the key generationalgorithm, decide what level of security isrequired and select the appropriate parameter set.1) Randomly generate a polynomial g that hasdg coefficients equal to 1 and dg coefficientsequal to –1.2) Randomly generate a polynomial f that has dfcoefficients equal to 1 and (df – 1) coefficientsequal to –1.3) Compute the value of fp such that:f * fp = 1 (mod p) If fp does not exist then return to step 2.4) Compute the value of fq such that:f * fq = 1 (mod q) If fq does not exist then return to step 2.5) Compute the value of h such that:h = pfq * g (mod q)6) The NTRU private key is (f, fp) and the publickey is h.C. EncryptionIf Bob wants to send Alice a message usingAlice’s public key h he must first express themessage in the form of a polynomial M whosecoefficients are chosen modulo p (say from –p/2to p/2). He can then encrypt M as follows:1) Randomly generate a polynomial r that has drcoefficients equal to 1 and dr coefficients equalto –1.2) Compute the value of the polynomial E suchthat:E = r * h + M (mod q)3) Send E


View Full Document

MASON ECE 646 - Performance Evaluation of Public Key Cryptosystems

Documents in this Course
Load more
Download Performance Evaluation of Public Key Cryptosystems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Performance Evaluation of Public Key Cryptosystems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Performance Evaluation of Public Key Cryptosystems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?