by Noriko Takezaki

As business use of the internet continues to grow, the need for secure and easy-to-use data encryption technologies is becoming more and more critical. Currently, the dominant encryption method being used for information and communications systems is the RSA public key cryptosystem, originally created in the 1970s. Since RSA's patents will expire in the year 2000, however, competitors are now scrambling to develop new encryption systems for the 21st century, each hoping that its system will achieve the lucrative status of becoming the de facto standard for electronic commerce and electronic data exchange.

Several Japanese companies, including Fujitsu, Hitachi, Matsushita, Mitsubishi Electric, NEC, and NTT, have been at the forefront of developing new encryption technologies. But the chances of a Japanese company taking leadership in the cryptosystem development race - a scenario that looked promising until just a couple of years ago - are rapidly fading. Here in Japan, development of encryption technologies has focused primarily on common key cryptosystems, a method whereby a single secret encryption "key" is used for both the encryption and decryption processes. Some of the better known examples of common key cryptosystems include NTT's FEAL, Mitsubishi Electric's MISTY, and Hitachi's Multi2.

In contrast, until recently relatively little research had been conducted in Japan on the development of public key cryptosystems, in spite of the fact that such systems are regarded as more secure than common key cryptosystems. Rather than using a single key for both processes, a public key cryptosystem uses the matching-pair combination of a public key and a private (secret) key for encryption/decryption.

One of the reasons for the lack of research into public key methods in Japan has been the ubiquitousness of the powerful RSA Public Key Cryptosystem, from US-based RSA Data Security. The RSA technology is already widely used worldwide (though hampered by US government-imposed export restrictions) and is the current de facto global encryption standard.

Throwing the market a curve

This isn't to suggest that there has been no public key encryption development in Japan, however. Last year, both Hitachi and Matsushita released security software products that utilize a complex public key encryption technology known as elliptic curve cryptosystem. Toshiba, too, has announced development of an elliptic curve cryptosystem algorithm that uses the Montgomery method to increase processing speed.

Basically, elliptic curve cryptosystem technology uses a so-called elliptic-curve discrete logarithm problem (EDLP) to ensure its security. An EDLP makes calculating the secret key from its public key an extremely difficult and time-consuming procedure, which is why the elliptic curve method is considered the most secure among existing public key cryptosystems. And this makes it the most prominent technology in the race to replace the RSA method.

The elliptic curve cryptosystem was originally developed by Victor S. Miller (IBM) and Neal Koblitz (University of Washington). Their original method, however, was compromised in 1990 by Alfred Menezes (University of Waterloo, Canada; currently, Auburn University, US), Tatsuaki Okamoto (NTT, Japan), and Scott Vanstome (Certicom/University of Waterloo, Canada) through a procedure that reduced the EDLP to a discrete logarithm problem (DLP).

This placed the elliptic curve method in disfavor for a time, but in 1992 Atsuko Miyaji, a researcher at Matsushtia Electric Industrial, developed a new elliptic curve cryptosystem that is immune to reduction to a DLP. By introducing this theory, Miyaji became a pioneer of elliptic curve cryptosystem development in Japan. She has since applied for more than 10 patents in Japan and 5 patents in the US.

"My hope is that elliptic curve cryptosystems can replace RSA some day," says Miyaji, who works at Matsushita's Information and Communications Technology Laboratory in Osaka. "Elliptic curve cryptosystems can make encryption and decryption much faster than the RSA method. Also, even if attacked, they can be flexibly rearranged to prevent the data from being compromised." "The charm of elliptic curve cryptosystem research," Miyaji continues, "lies in its infinite possibilities. The great mathematician Serge Lang once said, 'It is possible to write endlessly on elliptic curves.' For me, elliptic curve cryptosystems are the very basis of my entire scientific research work, and a subject for endless scientific investigation."

A hard code to travel

In Matsushita, research on encryption technologies started in 1985 as a volunteer project by a few researchers. Their research initially focused on the development of common key cryptosystems, just as in many other companies in Japan. Through the participation of Miyaji, however, who had studied elliptic curve theories at the University of Osaka, the group's focus eventually shifted to elliptic curve cryptosystems. Miyaji has conducted much research on cryptosystem theory by herself, but her development of a commercially viable elliptic curve cryptosystem was made jointly with four other researchers on the project team.

Unfortunately for the team members, however, their achievement was not properly appreciated at the time by Matsushita Electric Industrial, a giant home appliance company. In fact, it was not until November 1997 that Matsushita finally got around to commercializing this ground-breaking achievement.

The delay was costly for Matsushita since, inspired by Miyaji's theory, other companies had meanwhile set about developing their own elliptic curve cryptosystems. So by the time Matsushita was finally ready to release its elliptic curve encryption tool kit, MY-ELLTY, Hitachi had already marketed Keymate/Crypto, an encryption library using an elliptic curve cryptosystem, two months earlier.

To make matters worse, after having been shielded from attacks for about six years (while it was shelved), Miyaji's theory was not concertedly attacked until September 1997. Looking back, Miyaji does not hide her resentment - not toward the attackers*, but toward her company for not recognizing the importance of encryption technology and thus shelving her achievement for so long.

"They took too much time," says Miyaji regretfully. "When I first announced my theory, Matsushita was one of just three companies in the world that could have successfully developed this cryptosystem. Now, since many other companies have been announcing their own elliptic curve cryptosystems, Matsushita has became a latecomer in this field." Regarding the actual attack, Miyaji claims that it does not affect reliability of the MY-ELLTY product, since the attack was made on just one of the millions of kinds of elliptic curves that can be generated. Further, she claims, such attacks can be countered by simply rearranging the elliptic curve.

Differences of opinion

However, NEC, which recently announced a new encryption algorithm development, has a different opinion. "Can a cryptosystem that has been openly attacked be successfully promoted in the market?" asks Tomoyuki Fujita, senior manager at NEC's security research laboratory. "Elliptic curve cryptosystems are not secure enough; they use specific features of elliptic curves, which tend to be susceptible to attacks. We, therefore, have developed a new encryption algorithm that uses more general curves for improvement of security."

NEC's algorithm utilizes a one-way function on the Jacobian group of Cab curves that comprise the wide class of algebraic curves to which elliptic curves also belong. Fujita concedes that the NEC algorithm will not be ready for the market for about one year, because the company needs more time to ensure the security of its method. When the cryptosystem is ready, NEC will target applications within financial institutions.

Hitachi, whose Keymate/Crypto is also based on an elliptic curve cryptosystem, refutes NEC's claims. Says Kazuo Takaragi, a senior researcher at Hitachi's System Development Laboratory, "It seems too early to introduce a public key cryptosystem based on a new principle into the market, since it has not yet been exposed to attack. Cryptosystems are improved by experiencing and overcoming several attempted attacks. We therefore believe that, currently, the best thing for us to do is to use general elliptic curve cryptosystems that have been advanced and stabilized by resisting several attacks."

Takaragi adds that Hitachi's elliptic curve cryptosystem, which is being used in its Keymate/Crypto, differs from the Matsushita system in terms of "trace" (curvature). The attack made on Matsushita's algorithm, therefore, does not in any way compromise the security of Hitachi's Keymate/Crypto, he says.

Continue article

Back to the table of contents