Implementation of NTRUEncrypt in Software and HardwareBySanjay Puttaraju& Vineel Kumar SahiniKris GajECE 646ContentsIntroduction to NTRUNTRU: A Ring based PKCSPublic Key CryptosystemNTRU AlgorithmKey GenerationEncryption/DecryptionWhy it works?SoftwareNTRU SecurityResultsHardware ImplementationNTRU MultiplierNTRU MultiplierNTRU MultiplierProcessing UnitProcessing Unit8 by 2 bit Coefficient MultiplierMultiplier4 bit Ling AdderLing AdderLing AdderCLAProcessing RowProcessing RowConclusionImplementation of NTRUEncrypt in Software and HardwareBySanjay Puttaraju&Vineel Kumar SahiniKris GajECE 646Contents1 Introduction to NTRUEncrypt2 Software Implementation3 Hardware Implementation4 ConclusionIntroduction to NTRU• Founded as NTRU Cryptosystems in 1996 by four Brown University mathematicians. NTRU is only a stones throw from the Bay State's leader in computer security, RSA Systems. NTRU is competing with RSA as it has the advantage of speed in the operations of key generation, encryption and decryption. • NTRUEncrypt is currently being considered by the members of the P1363 working group, they develop standard specifications for public key cryptography• NTRUEncrypt is extremely fast as its underlying operation can be performed much more rapidly than the underlying operations required by other public key cryptosystems such as RSA, El Gamal, and ECC.NTRU: A Ring based PKCS• NTRUEncrypt is a Encryption Algorithm• NTRU features reasonably short, easily created keys, high speed and low memory requirements.• The security of the NTRU cryptosystem comes from the interaction of the polynomial mixing system with the independence of reduction modulo two relatively prime integers p and q.Public Key CryptosystemPlain TextPlain TextPlain TextPlain TextEncryptionAlgorithmDecryptionAlgorithmCipher TextPublic key Private KeyNTRU Algorithm• The NTRU algorithm is based on a polynomial Ring R that consists of truncated polynomials of the following typea = a0+ a1X + a2X2+ a3X3 + . . . + aN-2XN-2+ aN-1XN-1R = Z[X]/ (XN-1)• N - The polynomials in the truncated polynomial ring have degree N-1. N should be prime.• q - Large modulus: The coefficients of the truncated polynomials will be reduced mod q.• p - Small modulus. As the final step in decryption, the coefficients of the message are reduced mod p.• Relation of p and q: gcd (p, q) =1.Key GenerationKEY GENERATION• A random polynomial ’ f ’ is generated with specified number of ones and negative ones.• Polynomial Fq , an inverse of ‘f’ with modulo q.• Polynomial Fp ,an inverse of ‘f’ with modulo p.• Public key : h = pf*g mod q• Private Key : (f, Fp) .Encryption/DecryptionENCRYPTION• Alice uses, Bob’s public key to encrypt the message “m”, using the randomly chosen polynomial r.• e = pr *h + m (mod q)DECRYPTION• a = f *e (mod q) shift coefficients of “a” to the range (-q/2, q/2)d = Fp *a (mod p).• Polynomial “d” is the Alice’s original messageWhy it works?• a = f*e (modulo q) = f*(r*h + m) (modulo q) [since e = r*h + m (modulo q)] = f*(r*pfq*g + m) (modulo q) [since h = pfq*g (modulo q)] = pr*g + f*m (modulo q) [since f*fq = 1(modulo q)] p , r , g , f , m are already in the (–q/2,q/2) range. So ‘a’ reducing again to ‘q’ wont effect anything.• b = f*m (modulo p).• So Bob’s final step is to multiply b by fp and use the fact that fp*f = 1 (modulo p) to compute• d = fp* b = fp* f*m = m (modulo p),• This allows him to recover Alice’s message m.SoftwareWe implemented the NTRU Cryptosystem in software using the C Language. Initially, the code was designed for p = 3 and q= 128 and later extended. The user was allowed to specify the integer parameters N, q, and the number of ones and negative ones that would make up the random polynomials f, g, and r, respectively. The details and the purpose of these functions are explained in more detail below :RandPoly ( ):• Its function is to generate a random polynomial using the variables r [ ], Degree N, Numones, NumNegOnes.• r [ ]: This is the resulting random polynomial generated.• N – Degree of the polynomial to be generated.• NumOnes – Number of ones to be there in the polynomial.• NumNegOnes – Number of negative Ones to be present in the polynomial .• StarMultiply ( ) : Its function is to star multiply 2 polynomials using the following variables a [ ] , b [ ] - Polynomials to get star multipliedc [ ] - Resulting polynomial with reduced modulo M . • Inverse_poly_Fq ( ) :Its function is to find the inverse of the polynomial ‘f’ with reduced modulo ‘q’.• Inverse_poly_Fp( ) :Its function is to find the inverse of the polynomial ‘f ‘with reduced modulo ‘p ‘.• CreateKey ( ) : Its function is to generate the public and private keys.f, Fp ,Fq forms the private key‘h ‘forms the public key• Encode ( ) :It s function is to encode the given message ‘m ‘using the public key ‘h ‘ generated in the CreateKey function.• Decode ( ) : Its function is to decode the encrypted message using the Private Key generated by the CreateKey function.• NTRUEncodeDecode ( ):This is a test function which calls all the above functions for generating keys, encoding the given message, decoding the message in a single functionNTRU SecuritySecurityNpq dfdgdrdmLow 107 3 128 10 09 03 10Medium251 3 128 71 31 15 10High 503 3 256 201 61 30 10ResultsHardware Implementation• Here we have attempted to implement a scalable hardware design that can perform polynomial multiplication for NTRU.• The parameters p and q are fixed to 3 and 256 respectively.• However, this design supports arbitrary polynomial lengths including N = 503.NTRU MultiplierNTRU Multiplier• The NTRU multiplier consists of three major components• The control unit, the registers and a row of processing units.• The control unit orchestrates the computation of polynomial multiplication and also interacts with memory.NTRU Multiplier• There are four major registers for the multiplier : two u * 8 bit shift registers,a 2 * 2 bit shift register and a u * 8 bit register.• The number of units that make up the Processing row is configured by the user.Processing UnitProcessing Unit• The Processing Unit is responsible for the following operation• c(k) = a(0)b(k) + a(1)b(k-1) + . . . + a(k)b(0) + a(k+1)b(N-1) + a(k+1)b(N-2) + . . . a(N-1)b(k+1).8 by 2 bit Coefficient MultiplierMultiplier• The Eight by Two
View Full Document
Unlocking...