Gong-Harn Public-key Cryptosystem (GH-PKC) Software Implementation


With the emergence of the 3G (third-generation) networks for mobile communications, data security becomes even more important. Designing cryptosystems that meet both the power contraints and computing constraints of mobile units is very challenging. The GH-PKC reduces the size of the modulus and speeds up the computations of the same degree of security as existing cryptosystems. Our research focus is on software implementation of the GH-PKC and analysis on its performance over the existing cryptosystems.


The GH Public-key Cryptosystem (GH-PKC) was developed by G. Gong and L. Harn in 1999. This cryptosystem is based on the third-order linear feedback shift register (LFSR) sequences with a particular phase. Such a particular LSFR sequences are called a characteristic sequence. The elements of the sequences are taken from a finite field GF(q). The security of GH-PKS is based on the difficult of the solving discrete logrithm in the extension GF(q3) of GF(q).

The part of the GH Diffie-Hellman (GH-DH) key agreement protocol was published in the proceddings of ChinaCrypto'1998 and the GH-DH together with the GH-RSA type was published in the November 1999 issue of IEEE Transactions on Information Theory.

Two important features of the GH-PKC:

  • GH-PKC has the same modular size as the elliptic curve public-key system while achieving the same 1024 bit security level for q = p2 .
  • GH-PKC can be resistant to power analysis attack and timer analysis attack without increasing cost of computation.

The XTR, presented at Crypto'2000 by Lenstra and Verheul, is a special case of the special type of characteristic sequences when q = p2.

Some papers and slides on the GH-PKCS

  • S. Sin, Software Implementation of Gong-Harn Public-key Cryptosystem and Analysis, Master's Thesis, April 2004, Waterloo, University of Waterloo, supervised by G. Gong, Thesis (PDF) (Appendices are removed).
  • S. Sin, The GH-DSA, RIM-Seminar, October 2003, Slides on GH-DSA (PDF).
  • S.Sin, Gong-Harn Public-key Cryptosystems, Poster (PDF).
  • G. Gong and L. Harn, A new approach for public key distribution, Proceedings of China-Crypto'98, May 1998, Chengdu, China (PS).
  • G. Gong and L. Harn, Public-key cryptosystems based on cubic finite field extensions, IEEE Trans. on Inform. Theory, vol. 45, No.7, November 1999, pp. 2601-2605, PS, Public-key cryptosystems based on cubic finite field extensions (PDF).
  • Slides of the talk on the GH public-key cryptosystems at Queens University [PS], October 2000.
  • G. Gong, L. Harn and H.P. Wu, The GH public-key cryptosystems, the Proceedings of the Eighth Annual Workshop on Selected Areas in Cryptography, Toronto, August 16-18, 2001. CORR 2001-35 [PS, slides].
  • K. J. Giuliani, Generating large instances of the Gong-Harn cryptosystems, to be presented at the Conference on Cryptography and Coding, Dec. 17-19, 2001, Cirencester, UK, [PS].
  • Roy Krischer, An implementation of the Gong-Harn Diffie Hellman key agreement protocol [PS], supervised Undergraduate Research Assistant, Spring 2001, Research Project Report.
Last updated: July 09, 2019