Polynomial Multiplier and Inverter for NTRUMotivationNTRU BackgroundNTRU AlgorithmNTRU AlgorithmNTRU AlgorithmPolynomial MultiplierProcessing UnitLing Adder for MultiplierPolynomial InverterAlgorithm: Polynomial InversionAlgorithm: Polynomial InversionPolynomial Inverter: Block DiagramImplementation EnvironmentResultsProcessing Unit : Functional SimulationProcessing Row: Functional SimulationInverter Execution Unit: Functional SimulationProblems & ConclusionsThank YouPolynomial Multiplier and Inverter for NTRUSanjay PuttarajuECE 645Prof. GajMotivation NTRU is faster than its major competitor, RSA. Other features include easy generation of keys, high speed and low memory requirements. Finds extensive application in the embedded market. Attempted to develop a multiplier and hardware that computes inverse of a polynomial. These independent units find their application in the NTRU algorithm.NTRU Background NTRU is a new Public Key Cryptosystem (PKCS). Founded in 1996 as NTRU Cryptosystem Inc by four Brown University Mathematicians. NTRU is short for N-th degree truncated polynomial ring.NTRU Algorithm NTRU Parameters:N = Polynomials in the truncated polynomial ring have degree N-1.(e.g. 167, 251,347, 503)q = large modulus (e.g. 128, 256)p = small modulus (e.g. 3)f, g = small polynomials in the ring.NTRU Algorithm Key Generation:h = pfq*g (modulo q)Public Key = hPrivate key = polynomials f and fp Encryption:e = r*h + m (modulo q)m = message; r = blinding valueNTRU Algorithm Decryption:a = f*e (modulo q)b = a (modulo p)c = fp*b (modulo p)c = mPolynomial MultiplierProcessing UnitLing Adder for MultiplierPolynomial Inverter Inverse of a polynomial is obtained by performing Extended Euclidean Algorithm on f(x) and a(x).Remainder Quotient Auxiliaryf(x)=X8+X6+X5+X+1 0a(x)=X4+1 1X2X4+X2+X+1 X4+X2+X+11X2X6+X4+X3+X2+1Algorithm: Polynomial InversionAlgorithm: Polynomial InversionPolynomial Inverter: Block DiagramModulo 2 to q conversionExtended EuclideanAlgorithmPolynomial Multiplierfg,GF2^nInverseFqPolynomial Inverter – Basic Execution Unit>>+fgdeg(f)<deg(g)f[0]Implementation Environment Simulation is carried out in the Active HDL environment, particularly version 6.2 on a machine working on Windows XP Platform. Implementation targets Xilinx Spartan family of devices, specifically Spartan- III Xilinx FPGAs.Results Overall status:Written in 85%Verified through functional simulation in 80%Verified through timing simulation in 70%Analyzed in 40% Status of major functional units:Processing Row for multiplier written in 100%, verified through simulation in 100%Execution Unit for Inverter written in 90%, verified through simulation in 80%Processing Unit : Functional SimulationProcessing Row: Functional SimulationInverter Execution Unit: Functional SimulationProblems & Conclusions Encountered problems with synchronization of input/output between different independent blocks. Inverter could be made generic for parameters N, p and q. Extend the operation of the hardware to perform key generation, encryption and decryption for NTRU.Thank
View Full Document
Unlocking...