Performance Evaluation of Public Key Cryptosystems Advisor: Dr.Jens Peter KapsIntroduction to NTRUWhat is NTRU?NTRU Key GenerationNTRU Encryption & DecryptionCalculating Inverse of a PolynomialImplementationHow NTRU works?XTRSelection of ‘q’Selection of ‘p’Computation of Trace GroupSlide 13LiDIA LibraryResultsObservationsObservationsSlide 18Problems FacedQUERIES ???PowerPoint PresentationPerformance Evaluation of Public Key CryptosystemsAdvisor: Dr.Jens Peter KapsProject Team:Rakesh MalireddyRohan MalewarVasunandan PeddiVijay KoneruIntroduction to NTRUIntroduced in 1998 by Jeffrey Hoffstein, Jill Pipher and Joseph SilvermanFirst public-key algorithm not based on either integer factorization or the discrete logarithm problemIt promises efficient performance combined with robust securityNTRU’s creators claim that it is resistant to parallel processing attacks and that this fact, combined with its disposable key technology, considerably reduces the risk of power attacks, timing attacks and security breaches due to lost or intercepted keysWhat is NTRU?NTRU is nth degree truncation.A public key algorithm where a key pair(public and private key) is generated using complicated mathematical functions.The concept of NTRU lies in the ring of truncated polynomials of degree N-1 with integer coefficients. So, instead of using prime numbers we use a polynomial rings such as a = a0 + a1 X + a2 X2 + … + aN-2 XN-2 + aN-1 XN-1NTRU Key GenerationCompute a random polynomial ‘f’ that has ‘p1’ co-effecients equal to 1 and ‘m1’ co-effecients equal to –1 (p1 and m1 are inputs from the user)Compute the inverse of ‘f’ with mod p (fp) such that f * fp = 1 (mod p)If fp does not exist then perform the above step again.Compute the inverse of ‘f’ with mod q (fq) such that: f * fq = 1 (mod q)If fq does not exist then return to step 2.Compute the value of h such that: h = pfq * g (mod q)The NTRU private key is (f, fp) and the public key is h. where, N - Polynomials in ring R have degree equal to N-1 p - The small modulus q - The large modulusNTRU Encryption & DecryptionEncryption: The message to be sent must first be expressed in the form of a polynomial whose co-effecients are chosen modulo p.The message can then be encrypted as follows:Generate a random polynomial ‘r’ that has ‘dr’ co-effecients equal to 1 and ‘dr-1’ coeffecients equal to -1 Compute polynomial E such that E=r*h + M(mod q) E is the encrypted messageDecryption: The original message can be recovered by : Compute a such that a=f*E(mod q) Compute b such that b= a mod p Compute M such that M=fp*b (mod p)Calculating Inverse of a PolynomialTo compute the inverse of a (mod m): Let d = a, u = 1, v1 = 0, v3 = XN – 1 While v3 ≠ 0, iterate the following: Compute q and t3 such that d = v3 * q + t3 (mod p) and the degree of t3 is less than the degree of v3. (This is polynomial long division, a complex algorithm in itself.) t1 = u – q * v1 u = v1 d = v3 v1 = t1 v3 = t3If the degree of d is greater than 0, the inversion has failed (i.e. a is not invertible (mod p) or (mod m)) EXITLet c = d0-1u (mod p) (where d0 is the constant term in the polynomial d).If r > 1: Let q = p.While q < m, iterate the following: x = c * c (mod m) x = a * x (mod m) c = 2c – x (mod m) q = q2Return c (mod m).ImplementationThe code to implement NTRU is written using the C language.Different functions were written to implement the different functionalities.Polynomial multiplication When calculating the cipher text, E=r*h+M(mod q), we pass the polynomials that we have to multiply as arguments to the function and the result is the product of the two polynomials Polynomial division This function is used to calculate q and t3 when a and b are known in the equation a=b*q+t3 (mod p)Polynomial Inverse This function determines whether or not the inverse of the polynomial can be computed or notKey CreationKey EncryptionKey DecryptionHow NTRU works? a = f*e (mod q) = f*(r*h + m) (mod q) [since e = r*h + m (mod q)] = f*(r*pfq*g + m) (mod q) [since h = pfq*g (mod q)] = pr*g + f*m (mod q) [since f*fq= 1(mod q)]p , r , g , f , m are already in the (–q/2,q/2) range. So 'a' reducing again to 'q' would not effect anything b = f*m (mod p)So Bob's final step is to multiply b by fp and use the fact that fp*f = 1 (mod p) to computed = fp* b = fp* f*m = m (mod p)This allows him to recover Alice's message ‘m’XTRXTR can be used in any cryptosystem that relies on discrete logarithm problemXTR public key Data is ( P,Q,Tr(g))Selection of ‘q’ int generate_q( bigint &q, bigint &r, const int q_bit_length, const int n_prime_tests){int cnt;bigint r_max;cnt=0;power(r_max,2,q_bit_length/2+1);do{r.randomize(r_max);q=r*r-r+1;cnt++;}while(q.bit_length()!=q_bit_length ||! is_prime(q,n_prime_tests));return cntSelection of ‘p’ int generate_p( bigint &p, const bigint &q, const bigint &r, const int n_prime_tests){ int kk=0;p=r;do{k++p+=q;}while(remainder(p,3)!=2 || ! is_prime(p,n_prime_tests));return k;}Computation of Trace GroupTr(h) = h +h p2+hp4 Trace belongs to GF(p2)The trace group is represented by SnComputation of Trace GroupSn(c) = (cn−1, cn, cn+1) belongs to GF(p2)3Sn(Tr(g)) = (Tr(gn−1), Tr(gn), Tr(gn+1))LiDIA LibraryMathematical library used in XTR programbigintbigmodResultsLevel of Security NTRU XTRStandard 167 bits 85 bitsHigh 263 bits 170 bitsHighest 503 bits 340 bitsObservations Key Generation:XTR outperforms NTRU marginally at Standard security level At High security level XTR outperforms NTRU approximately by a factor of 1.5ObservationsEncryption:NTRU outperforms XTR by a large factor due to exponentiation function in the XTROn going for higher security levels, the above factor reduces marginallyObservationsDecryption:NTRU outperforms XTR XTR has same encryption as NTRU on a high level security and on a platform with limited resources like PCProblems FacedNTRU:Performing long division method while calculating inversePerforming mod function when p=3XTR:Implementation of Library routine Implementation of
View Full Document
Unlocking...