As the information-processing and telecommunications revolutions now underway will continue to change our life styles in the rest of the 21st century, our personal and economic lives rely more and more on our ability to transact over the electronic medium in a secure way. The privacy, authenticity, and integrity of the information transmitted or stored on networked computers must be maintained at every point of the transaction. Fortunately, cryptography provides algotrithms and techniques for keeping information secret, for determining that the contents of a transaction have not been tampered with, for determining who has really authorized the transaction, and for binding the involved parties with the contents of the transaction. Since we need security on every piece of digital equipment that helps conduct transactions over the internet in the near future, space and time performances of cryptographic algorithms will always remain to be among the most critical aspects of implementing cryptographic functions. A major class of cryptographic algorithms comprises public-key schemes which enable to realize the message integrity and authenticity check, key distribution, digital signature functions etc. An important category of public-key algorithms is that of elliptic curve cryptosystems (ECC). One of the major advantages of elliptic curve cryptosystems is that they utilize much shorter key lengths in comparison to other well known algorithms such as RSA cryptosystems. However, as do the other public-key cryptosystems ECC also requires computationally intensive operations. Although the speed remains to be always the primary concern, other design constraints such as memory might be of significant importance for certain constrained platforms. In this thesis, we are interested in developing space- and time-efficient hardware and software implementations of the elliptic curve cryptosystems. The main focus of this work is to improve and devise algorithms and hardware architectures for arithmetic operations of finite fields used in elliptic curve cryptosystems. / Graduation date: 2001

During the last few years we have seen formidable advances in digital and mobile communication technologies such as cordless and cellular telephones, personal communication systems, Internet connection expansion, etc. The vast majority of digital information used in all these applications is stored and also processed within a computer system, and then transferred between computers via fiber optic, satellite systems, and/or Internet. In all these new scenarios, secure information transmission and storage has a paramount importance in the emerging international information infrastructure, especially, for supporting electronic commerce and other security related services. The techniques for the implementation of secure information handling and management are provided by cryptography, which can be succinctly defined as the study of how to establish secure communication in an adversarial environment. Among the most important applications of cryptography, we can mention data encryption, digital cash, digital signatures, digital voting, network authentication, data distribution and smart cards. The security of currently used cryptosystems is based on the computational complexity of an underlying mathematical problem, such as factoring large numbers or computing discrete logarithms for large numbers. These problems, are believed to be very hard to solve. In the practice, only a small number of mathematical structures could so far be applied to build public-key mechanisms. When an elliptic curve is defined over a finite field, the points on the curve form an Abelian group. In particular, the discrete logarithm problem in this group is believed to be an extremely hard mathematical problem. High performance implementations of elliptic curve cryptography depend heavily on the efficiency in the computation of the finite field arithmetic operations needed for the elliptic curve operations. The main focus of this dissertation is the study and analysis of efficient hardware and software algorithms suitable for the implementation of finite field arithmetic. This focus is crucial for a number of security and efficiency aspects of cryptosystems based on finite field algebra, and specially relevant for elliptic curve cryptosystems. Particularly, we are interested in the problem of how to implement efficiently three of the most common and costly finite field operations: multiplication, squaring, and inversion. / Graduation date: 2001