Encryption scales to fit smaller RF ID tags

Encryption scales to fit smaller RF ID tags
By Chappell Brown, EE Times
April 9, 2002 (8:42 a.m. EST)
URL: http://www.eetimes.com/story/OEG20020408S0058

BURLINGTON, Mass. — Armed with a simplified mathematical approach to public-key encryption, NTRU Cryptosystems Inc. here is introducing intellectual property that can add security to virtually any circuit. The most recent product based on the approach is a circuit block that can be added to small wireless products such as smart cards and point-of-sale ID tags. NTRU claims the approach is as secure as the popular RSA public-key encryption system but is computationally much simpler.

"Public-key cryptography is necessary in systems of high scale or high security. Their primary advantage is that they allow for encryption keys to be widely distributed without fear of compromise," said Scott Crenshaw, chief executive officer of NTRU. "NTRU's core technology solves a fundamental problem for public-key cryptography." Until now, Crenshaw said, "public-key systems required very large numbers of gates — 50,000 ga tes, 100,000 gates — or in software, it required a Pentium-class machine. NTRU's system, on the other hand, fits into a very small number of gates and can run on a low-end microcontroller."

Two approaches

The company's product line, GenuID, is segmented into two areas: software running on low-end microcontrollers and a processor core that can be inserted into designs. "We run the software implementation faster than RSA can run on a Pentium," claimed Crenshaw, referring to the most popular form of public-key encryption, RSA (named for its inventors: Ron Rivest, Adi Shamir and Leonard Adleman). Tool kits both for implementing readers and for the back-end system are also available.

RSA's contactless smart cards sell for $3 to $5, Crenshaw said, while GenuID chips sell for 50 cents to $1. "This is significant for manufacturers — it opens up new application areas that require security," he said.

The different approach to encryption began with a group of math professors at Bro wn University. They realized that a more computationally efficient version would open a huge market for low-end security. Jeffrey Hoffstein, Joseph Silverman, Jill Pipher and Daniel Lieman — who co-founded NTRU — studied the conventional approach and realized that the basic strategy, based on integer arithmetic, took a toll computationally. While integer math is well-understood and relatively easy to implement in software, the underlying computer models are complex in terms of the conventional structure of digital CPUs.

Modular math

The RSA uses numbers with 1,024 bits. In contrast, the NTRU algorithm is based on byte boundaries that even an 8-bit microprocessor can handle. The algorithm is based on modular arithmetic, which operates on arrays of bytes.

Public-key cryptography depends on an algorithm that is easy to run in one direction only. For example, multiplying two large prime numbers is easier computationally than finding the two prime factors of some number that has been generated in this way. Thus, if an encryption system is based on prime-number computational asymmetry, it will be tough for a code cracker to take a brute-force approach to deducing the original two numbers. Using known benchmarks for computer systems, a cryptologist simply needs to determine two prime numbers that are large enough to make the prime factoring algorithm impossible to execute in a reasonable amount of time. Other hard-to-solve mathematical problems have also been used to create computationally asymmetrical algorithms.

With the NTRU approach, the basic computational context goes from integer arithmetic to polynomial algebra.

Rather than encode information as digits representing numbers, NTRU uses sequences of integers that form the coefficients of a polynomial. That simplifies computation. "The NTRU system only uses adds and shifts, which are easier to perform than full integer arithmetic," Crenshaw said. The security algorithms are 2,000 times faster and 50 times smaller than other public-key methods, he said.

The system can attach a secure digital "signature" to a document that can be verified as valid using only a public key. The private key is represented by two small polynomials, which generate a very large system of polynomials. The public key is derived from the two private-key polynomials using convolution and is able to generate the same set of polynomials as the two private-key polynomials. A digital message is then hashed and encoded as a pair of polynomials that are essentially random.

A pair of polynomials in the set generated by the private keys is computed from the private key so that they are within a predetermined, close bound to the hashed message. One of the nearest-neighbor polynomials then becomes the digital signature. The original message is sent along with the signature, and the recipient, after using the same hashing algorithm, is able to verify that the resulting polynomial pair is within the predetermined distance from the polynomials representi ng the digital signature.

No brute force

The security of the system is ensured by the difficulty of finding close polynomials in a large collection of polynomials. Someone attempting to fake the digital signature might be able to find a pair of polynomials close enough to the hashed document to pass the verification step, but doing that by brute force becomes computationally impossible with only moderately long key sequences. In fact, the key sequences can be as short as 1,024 bits, conforming to the size of keys used by RSA encryption. The underlying polynomial operations are computationally very easy, however, which is what makes the method easy to implement in digital systems.

The high speed and small computational requirements are ideal for radio-frequency applications that need some type of security. A current example is Mobile Corp.'s Speed Pass, which allows motorists to purchase gas simply by holding a small RF tag near an antenna on a gas pump. The system verifies the driver' s ID and credits the purchase to the driver's account. In this case, the details of the purchase and the public key need not be secure, but a digital signature is required to verify that the purchase was made by the owner of the account.

NTRU has received $38 million in financing from a variety of investors, including Texas Instruments Inc. and Sony Corp.