Cryptography may not guarantee absolute security for communications but it creates very high hurdles for spying programmes. Oldenburg mathematicians Florian Heß and Andreas Stein discuss a field of research that is in high demand – and not just since the revelations of whistleblower Edward Snowden.
Do you write emails? Do you save data to the Cloud? Do you download software updates or apps from the Internet? In view of the public debate about the secret services and their spying programmes you will no doubt have wondered how data espionage or the installation of fake software that is actually used for spying purposes can be prevented or at least impeded. Cryptography provides solutions to this and many other security-related problems in the digital world.
Cryptography's most obvious task is encryption. It can be used to render a message, a piece of data for example, indecipherable before sending, so that it can be reconstructed and read only by its intended recipient. Less obvious but equally important is data integrity and authenticity. This is often taken care of by a digital signature. Its aim is to ensure that the message is not corrupted on its way from sender to receiver and that it actually stems from the sender and not from some sinister source. Cyptography's field of application is broad and ranges from the use of electronic voting to electronic money. In e-commerce and e-government it is indispensable for the data security of businesses and states.
The statements made by NSA whistleblower Edward Snowden, whose revelations shed light on the scale of the operations and practices of the secret services, have confirmed cryptography's importance. As current media reportage shows, the spying attacks are aimed primarily at the endpoints of cryptographic communication and the insertion of backdoors. These attacks pose major hurdles and risks for the attacker. Thus in practice, the use of cryptography may not guarantee absolute communication security, but generally speaking the level of security provided is high.
Curve-Based Cryptography
Cryptography's mathematical and algorithmic foundations are one of the key areas of research at the University of Oldenburg's Institute of Mathematics. Methods from number theory, arithmetic geometry and computer algebra all play an important role here. Modern cryptographic algorithms require computational problems that are “easy” to set but “difficult” to solve. One example: among the nonnegative integers a prime number is a number larger than one which is divisible only by one and itself with no remainder, such as 2, 3, 5, 7 and so on. Using a computer it is possible to calculate two random prime numbers with 300 decimal digits as well as their product in a matter of seconds. The reverse calculation of the prime numbers starting from the product, on the other hand, would take several years at the current level of research. Computational problems for prime factor decomposition are therefore “easy” to set and “difficult” to solve. This allows encryptions and digital signatures to be quickly generated and categorized as secure for extended periods of time.
In Oldenburg the research focus on cryptography's mathematical and algorithmic foundations deals primarily with curve-based cryptography. As is the case with prime factor decomposition, computational problems from the field of number theory are also applied here, albeit for elliptic curves, and more generally for algebraic curves over finite fields. The emphasis here is on efficiency and security, potential applications, as well as related questions from number theory and arithmetic geometry. The relationship between efficiency and security in cryptographic algorithms is much more favourable using elliptic curves than in the example involving prime factor decomposition. And there are also new applications such as pairing-based cryptography. All these aspects make elliptic curves particularly interesting for cryptography. In Germany they are used, among other things, in passports and identity cards. Elliptic curves are much more structured, complex number theoretic objects than prime numbers. This makes them particularly interesting for mathematicians, but virtually unintelligible for non-mathematicians.
Key constituents of the underlying mathematical theory were developed in the 1930s and 40s by the German number theorists Helmut Hasse and Max Deuring as part of their research in pure mathematics, without a view to practical applications. Seventy years later their findings represent a central component of applied cryptography. Beyond cryptography, elliptic curves play an important role in number theory and arithmetic geometry. This can be seen, for instance, in Pierre de Fermat's Last Theorem and its proof, or in the Birch and Swinnerton-Dyer conjecture – one of the greatest unsolved mathematical problems and one of the so-called Millennium Prize Problems. Cryptography is therefore also an interesting field of activity for number theorists with an interest in algorithms outside the “ivory tower of pure mathematics”.
Cryptography as Science
Cryptography has a long history that stretches back to ancient times. It was not until the 20th century, however, that it gained scientific status. The increasingly technological nature of communication and the invention of computers, driven in part by the demands of cryptography itself, gave a considerable boost to the development by Alan Turing and Claude Shannon of information theory as the mathematical-computational basis of cryptography. These developments during and shortly after the end of World War II are intricately bound up with the fascinating story of the Enigma encoding machine, which the German military used to encrypt its communications. Bestselling novels and spy films have made it famous the world over.
In their 1976 paper “New Directions in Cryptography”, Whitfield Diffie and Martin Hellman layed the foundation of public-key cryptography, which forms an essential part of today's cryptographic technology. What was so groundbreaking about their work? If you imagine an encryption algorithm as a strongbox and the encryption process as encasing the message in the strongbox, up to that point in time sender and receiver needed the same secret key to lock and unlock the strongbox. This meant that the sender and the receiver had to have safely exchanged the key in advance. Diffie and Hellman introduced a new method with which sender and receiver – and only them – could calculate the secret key by exchanging publicly visible information. It was not long after this innovation that Ron Rivest, Adi Shamir and Leonard Adleman invented the RSA encryption algorithm that was named after them. It allowed the strongbox to be locked with a public key – but only opened again using a secret key. This brought enormous advantages for the exchange of keys and reduced the number of keys needed. The key innovation of both procedures was the introduction of computational problems from the field of number theory into cryptography. The RSA algorithm is based on the prime factor decomposition outlined above and is one of the most commonly applied encryption algorithms to date. As the opening of a secret archive at the end of the 1990s revealed, the British secret service had developed similar algorithms a number of years previously, without however making them public. In the mid-1980s Victor Miller and Neal Koblitz then introduced elliptic curves over finite fields into cryptography. Other relevant and contemporary number theoretical computational problems result from using lattices and linear codes.
The security of public key cryptographic algorithms is based, as explained, on the fact that certain calculations are easy “forwards” and extremely difficult “backwards”, with security increasing proportionally to difficulty. So far, however, high difficulty levels have remained unprovable. Such a proof would in fact solve another Millennium Prize Problem known as “P ? NP” at the same time. The security levels of cryptographic algorithms thus only reflect the current state of research as regards the estimated minimum effort required to solve the aforementioned calculations “backwards”.
Private and Public Keys
Of course calculations can be performed quicker by building better computers. The increase in computer performance has to date proven to be relatively easy to predict, making it possible to design computational problems that are sufficiently difficult and thus estimate security levels for a specific number of years. The spectre haunting applied cryptography, however, is the quantum computer. This is a theoretical computer model which would use quantum effects to perform certain calculations at a far faster rate than ordinary computers. A computer like this would render a large part of contemporary cryptography redundant, as Peter Shor demonstrated in the mid-1990s. It is however – fortunately perhaps – highly questionable whether such a computer could ever be built. If this were the case, however, at least in principle cryptographic methods exist that would be capable of resisting even a quantum computer.
Research Landscape
Cryptography is a highly interdisciplinary field that spans areas of mathematics, computer science, electrical engineering and physics. The key mathematical aspects have already been outlined. As regards computer science, the research largely revolves around the application of mathematical computational problems to specific cryptographic tasks and the development of appropriate cryptographic communication protocols. In electrical engineering the issue is how to efficiently realize cryptographic calculations in computer hardware and guarantee that stored secret keys remain secret, even if the hardware is subjected to every possible physical scrutiny. This is relevant for chips in bank cards, for example, or SIM cards in mobile phones.
Oldenburg's research focus on the mathematical and algorithmic foundations of cryptography is embedded in the regional research landscape for safety-critical IT technology, that is in projects that are based primarily at the University's Department of Computer Science and the OFFIS Computer Science Institute. An interdisciplinary network of cryptography-related research in Oldenburg and Emden with a broad spectrum of research areas is currently under construction.
Prof. Dr. Florian Heß
Florian Heß is full professor for mathematics and is the head of the research group Computational and Discrete Mathematics at the University of Oldenburg. After his PhD in 1999 at TU Berlin he worked as a postdoc in Sydney and Bristol and as professor in Berlin and Magdeburg from 2003 on. Heß joined the University of Oldenburg in 2010. His research interests are in cryptography, number theory, algebraic geometry and computer algebra.
Prof. Dr. Andreas Stein
Andreas Stein is a full professor of Mathematics and is the head of the research group in Algebra/Geometry at the University of Oldenburg. After his Ph.D. in 1997 at the University of Saarland he worked as a post doctoral fellow in Canada at the universities in Winnipeg and Waterloo. Before he came to Oldenburg in 2008 he was a professor at the University of Illinois at Urbana-Champaign and at the University of Wyoming, both USA. His research interests include computational arithmetic geometry and cryptography.