Mr Luke Maurtis

Honours thesis

Public key cryptography using discrete logarithms in finite fields: algorithms, efficient implementation and attacks

The field of cryptography (from the Greek kryptos, meaning ''hidden'' and graphein, meaning ''to write'') is concerned with problems related to the security of information, such as: ensuring that information transmitted over a public channel cannot be understood by an eavesdropper; verifying that received information has indeed been sent by the party claiming to have sent it; and ensuring that the information has not been tampered with by unauthorised parties in transit. These problems have been of interest to humanity since ancient times, historically in connection with military and diplomatic affairs. The ''shift cipher'' of Julius Caesar and the cipher rods of the Spartan military are well known historical examples of cryptography. More recently, the efforts of the Allied forces in breaking the Nazi ''Enigma'' code have been credited with having shortened World War II by up to two years. Since the advent and subsequent widespread adoption of the digital computer, the range of applications for cryptography has exploded and the field has matured from what was once arguably an art into a definite science of the highest mathematical sophistication. Today, cryptography is used to provide security to a host of daily activities, including but not limited to: the electronic transfer of money via ATMs, EFTPOS or internet banking and purchase systems; the transmission of voice, photo and video data over mobile telephone networks; the transmission and storage of electoral votes cast using electronic voting machines; and the use of email, instant messaging and other computer communication for confidential business discussion or collaboration, ''whistle- blowing'', transmission of sensitive data such as police or hospital records and private personal communications. Perhaps the most important change cryptography has undergone in its long history has been the revolutionary discovery of public-key cryptography, an idea both first proposed and accomplished in 1976 by Whitfield Diffie and Martin Hellman. All previous means of secure communication had required that the participating parties agree on a secret key beforehand. The security of any subsequent communication relied upon this key being agreed upon in perfect secrecy and remaining undiscovered by any third parties. This posed a major practical difficulty, especially when secure communication over long distances or between parties with no prior acquaintance was desired. Public-key cryptography removes this requirement and allows secure communication between two parties with no prior secret exchange of keys. This represented a major paradigm shift in the world of cryptography, one which enabled many of the applications of cryptography in wide use today.