IEEE P1363a: Additional number-theoretic algorithms

A new aspect of dual basis for efficient field arithmetic
Chang-Hyi Lee and Jong-In Lim, August 1998.

In this manuscript we consider the special type of dual basis for finite fields, GF(2^m), where the varients of m are presented in the following contents. Here we introduce our field representing method for its efficient arithmetic (of field multiplication and field inversion). It revealed a very effective role for both software and VLSI implementations, but the aspect of hardware design for its structure is out of this manuscript and so, here, we deal only the case of its software implementation (the efficiency of hardware implementation is appeared in another article submitted to IEEE Transactions on Computers). A brief description of this advantageous characteristic is that

1. the field multiplication can be constructed only by k(<=m/2) rotations and the same amount of vector XOR processes,
2. there is needed no additional work load as basis changing (from standard to the dual basis or from the dual basis to standard basis as the conventional dual based arithmetic does),
3. the field squaring is only bit-by-bit permutation and it has a good regularity for its implementation, and
4. the field inversion process is available for both cases of its implementation using Fermat's Theorem and of its implementation using almost inverse algorithm [14], especially the case of using the almost inverse algorithm has an additional advantage in finding (computing) its complete inverse element.

PostScript File (447K)
Zipped Postscript File (102K)
Adobe Acrobat (.pdf) File (257K)

Technique for Generating Provable Primes
Preda Mihailescu, May 1998.

We suggest a technique for generating provable primes for cryptographical use, for the P1363 standard. The method not only provides a certificate for the primes generated, it is also faster than similar probabilistic generation algorithms. The security concerns are also covered. Detailed descriptions and analysis may be found in [Mi], [Mi1].

PostScript File (200K)
Zipped PostScript File (44K)
Adobe Acrobat (.pdf) File (110K)

Efficient Finite Field Basis Conversion Techniques
Burt Kaliski, Moses Liskov and Yiqun Lisa Yin, April 1999.

This summary of finite field basis conversion techniques is proposed for inclusion in IEEE P1363 Annex A. Included are some conventional basis conversion techniques, as well as some new storage-efficient basis conversion techniques.

PostScript File (358K)
Zipped Postscript File (148K)
Adobe Acrobat (.pdf) File (25K)
MS Word for Windows File (224K)

Usage of Optimal Extension Fields for Elliptic Curve Cryptosystems
Tetsutaro Kobayashi, Kazumaro Aoki, Fumitaka Hoshino, Kunio Kobayashi and Hikaru Morita, August 1999. Presented at the August 1999 and October 1999 meetings.

In IEEE P1363, two kinds of finite fields, ``Prime Finite Fields'' and ``Characteristic Two Finite Fields'' have been standardized. We propose ``Optimal Extension Fields (OEF)'' in addition to the two fields. OEF is efficient to compute [1-3].

PostScript File (166K)
Zipped PostScript File (77K)
Adobe Acrobat (.pdf) File (58K)

PostScript File (253K)
Zipped PostScript File (54K)
Adobe Acrobat (.pdf) File (155K)

PostScript File (253K)
Zipped PostScript File (54K)
Adobe Acrobat (.pdf) File (155K)

PostScript File (218K)
Zipped PostScript File (32K)
Adobe Acrobat (.pdf) File (35K)

Proposing the Use of Non-Conventional Basis of Finite Fields
Jong In Lim, Ok Yeon Yi, Joong Chul Yoon, Sang Ho Oh, Seak Hie Hong, Dong Hyun Cheon, Sung Jae Lee, Hee Jin Kim, and Chang Han Kim, March 1999.

Finite field arithmetic is becoming increasingly important in cryptographic applications. In particular cryptographic primitives based on the discrete logarithm problem over elliptic curve groups are accomplished essentially by arithmetic in finite fields. It is well known that the efficiency of finite field arithmetic depends strongly on the particular way in which the field elements are represented. The finite field representation can be classified according to the choice of basis - a polynomial basis in software implementation and a normal basis in hardware implementation conventionally. The big problems of the communication between one Elliptic Curve Cryptosystem (ECC) in software implementation and another ECC in hardware implementation result from the difference in the choice of basis. In this paper we discuss the cost of the communication between such cryptosystems and propose the use of a non-conventional basis representation providing the improved communicaton.

Short proposal:

• Postscript File (236K)
• Zipped Postscript File (50K)
• Adobe Acrobat (.pdf) File (114K)

• Postscript File (502K)
• Zipped Postscript File (105K)
• Adobe Acrobat (.pdf) File (208K)

IEEE Home Page	IEEE Standards	P1363 Home Page