Cryptographic applications of Brahmagupta-Bha/spl tilde/skara equation

Abstract

The Brahmagupta-Bha/spl tilde/skara (BB) equation is a quadratic Diophantine equation of the form NX/sup 2/+k=Y/sup 2/, where k is an integer (positive or negative) and N is a positive integer such that /spl radic/N is irrational. A particular case of the BB equation with k=1 is also known as Pell equation in literature. This equation in the Galois Field GF(p), where p is an odd prime has some practically useful properties. Application of these properties in two different fields of cryptography, namely, digital encryption and user authentication are discussed in this paper. For those applications, where software computation of the roots of the BB equation is unacceptable for being too slow, a hardware architecture for using the BB equation in GF(p) is given that is useful for implementation in VLSI form.