by ARJEN K. LENSTRA

This note reviews the most popular mathematical primitives that are used in current attempts to build secure networks.

1. Introduction

2. Background

3. Factoring

4. Discrete Logarithms

5. Conclusion

Notes

Corporations worldwide suddenly regard the Internet, once the almost exclusive playground of the global community of computer nerds, as an immense business opportunity. Until recently phrases such as "consult our homepage athttp://www.digicrime.com" made sense to only a few; now they belong to our everyday vocabulary. This is all part of the explosive growth of what has been called theGlobal Information Infrastructure. It is a development that cannot be stopped and probably should be welcomed.Nevertheless, corporations are beginning to see that venturing out on the Internet may expose them to enormous risks. The purpose of "putting your homepage on the web" is to increase visibility and to draw attention. Unfortunately the audience includes not only potential customers but also virtually

allhackers worldwide. At least some of them will, intentionally or not, cause trouble.Solutions to the resulting security problems are not hard to find on the net, since many software vendors now advertise "secure" versions of their products. This makes using the net really risky, because users might mistakenly believe they are well protected. The widely publishized and rather frequent news stories about network break-ins and imperfections in security software should dispel such illusions. It seems that our competence to secure the net cannot keep up with our desire to use it.

Despite the confusing array of security solutions, there are only a few mathematical primitives on which they are based. Even in faulty security products, the soundness of the underlying mathematics is hardly ever in question; it is the way it is used that causes the vulnerabilities. In this note I discuss the mathematical primitives--not the many slippery ways in which they are employed. I concentrate on the primitives themselves and the assumption of their soundness and will show that this is one of the most important reasons that

computational number theoryhas become so fashionable, even at industrial labs. This popularity, based entirely on our incompetence of efficiently solving a few basic number theoretic problems, is hardly something of which to be proud. Purists who object to the vulgarization of number theory should find comfort in the prospect that as soon as efficient solutions have been found, number theory will again be the immaculately impractical Queen of Mathematics--its status before "security applications" came along.This note is written for an undergraduate mathematics audience that is not familiar with the mathematical notions involved in many popular security products. In section 2 I sketch a possible security application on the Internet. Of course, much more is involved in practice than I am able to mention here, but I show some of the basic concepts and set the stage for the mathematical primitives that are presented in Sections 3 and 4. No attempts are made to formalize notions such as "infeasible", "hard" or "efficient". For further background refer to [1] (Section 2) and [2] (Sections 3 and 4).

The following naive scenario, though grossly oversimplified, shows some of the key issues of communication security. Suppose that two parties who have never met want to exchange confidential information over some untrusted but reliable network. "Untrusted" here means that all messages are accessible to eavesdroppers; "reliable" means that no bits are dropped or changed. The Internet is a reasonable example of such a network.If the two parties share a random string

sof secret bits that is as long as the messagem, then the problem can easily be solved: send thebitwise exclusive orofsandm. Sincesis random, leaks no information. Furthermore, it is easy to derivemfrom because . This would solve the problem, except that we cannot assume that any two parties have a secret string of random bits in common. A further disadvantage is that, using this simple approach, eachscan be used only once (since and reveal information about ).The latter problem can be overcome by using, for instance, DES--the U.S. government's Data Encryption Standard. DES is an example of a

block cipher. It can be used to construct a functionfsuch that it is sufficiently hard to derivemfromf(s,m) (for any number of messagesmof any length), such thatm=f(s,f(s,m)), and such thatfcan very efficiently be computed. Heresis a 56-bit string, or a 168-bit string if higher security is needed (triple-DES); this string is referred to as thekey. Thus, if both parties had a common keysthat was unknown to any other party, any messagemcould be encrypted asf(s,m), sent to the other party using an untrusted channel, and decrypted asm=f(s,f(s,m)). This can be repeated back and forth, for any reasonable number of messages.A description of DES is beyond the scope of this note; it does a lot of seemingly arbitrary bit-fiddling that aims to, among other things,

confuse and diffusethe bits of the keysand the messagem. There are many other ciphers that can be used to construct functions that have properties similar tof. For our purposes the problem that remains to be considered is how the two parties perform thekey exchangefor a relatively short key (of, say, 56 bits), in such a way that the key that is exchanged remains hidden to an eavesdropper.Note that the simple approach where the (trusted) provider of the communication services assigns a unique random key to each pair of possible parties is not feasible: each party would need an enormous data base of keys, which would not only be hard to keep updated (for new subscribers) but would also have to be safeguarded very carefully. An elegant solution to the problem of key exchange is given in Section 4. It only requires a small amount of public information that is accessible to the entire network. While using it, however, all parties involved need to sign all their messages.

This requires

digital signaturesto convince each of the communicating parties that the messages they receive come from the party they intend to communicate with. This can be realized usingpublic key cryptography, as explained in the next sections. In public key cryptography all parties have asecret keyand a correspondingpublic key. In signature applications the secret key is used by its owner to generate a signature; the corresponding public key can be used by anyone to check the validity of the signature.Thus, all secret keys are kept hidden by their owners, but all parties have access to each other's public keys, just as telephone numbers are (mostly) public information. Alternatively, parties that wish to communicate can exchange their public keys first; this in turn leads to the problem of authenticating public keys and related issues, which can also all be solved using public key cryptography (and which may, in certain circumstances, require a trusted third party). In practice many other problems have to be addressed as well. The purpose of our simpleminded example is only to introduce the basic principles as a background for the mathematical primitives that are presented below.

A cryptographic technique that is often used for digital signatures in conjunction with public key cryptography is

hashing. A hash functionh, when applied to a messagemof arbitrary length, results in a fixed length hashh(m) ofm; for MD5 (`Message Digest') the resulting length is 128 bits, for SHS (the U.S. government's `Secure Hash Standard') it is 160 bits. For a good hash function it should be infeasible to compute anmsuch thath(m) is equal to any prescribed value. Also, it should be infeasible to find different and such that . Like DES, the currently popular hash functions are based on very efficient seemingly random bit manipulations, and not on clear-cut mathematical ideas as most public key cryptosystems are (even though those ideas might turn out to be incorrect). It is an open problem how to design a very efficient hash function that is provably as hard to break as one of the public key cryptosystems described below. It is also becoming an urgent problem: on May 2, 1996, Hans Dobbertin of the German Information Security Agency, who was responsible for breaking MD4 in 1995, announced a new cryptanalysis of MD5 that `might be reason enough to substitute MD5 in future applications'. The life expectancy of SHS is uncertain, since its design is very similar to that of MD5.

Factoring a composite integernmeans finding integerspandq, both >1, such that . This is, in its generality, believed to be a hard problem, even though there is no firm mathematical ground on which this assumption can be based: the only evidence is our failure to find an efficient factoring method.The supposed difficulty of factoring is crucial for the security of the RSA public key cryptosystem, which was invented in 1977 by Rivest, Shamir, and Adleman. Each user of RSA has its own modulus , where

pandqare two large primes, and two integerseanddsuch that . The valuesnandeare made public as that user's public key, butdis kept secret (along withpandq) and is the user's secret key. Since large primes can efficiently be generated, and becausedcan quickly be found using the extended Euclidean algorithm givene,p, andq(for properly chosene), suchn,e, anddcan easily be found for each user of RSA.To send a message to the owner of public key (

n,e), one computes and transmits the encrypted messageE(m). The owner of (n,e), upon receipt ofE(m), retrieves the unencrypted messagemby computing (cf. Fermat's little theorem). Both the encryption and the decryption can efficiently be done using the `repeated square and multiply' method. This is, however, considerably slower than, for instance, DES. RSA can also be used to sign a messagemas ; the validity of the signature can be checked by verifying that .It has not been proved that factoring

nis necessary to break RSA (i.e., to decryptE(m) knowingn,e, andE(m) but without knowing the properd), but it is obviously sufficient. There exist several variations of RSA that replace the multiplicative group by some other group that depends on a composite modulus, and in which the operations are carried out. None of them, however, seems to have any substantial advantages over RSA (despite claims to the contrary), and all of them can be broken by factoring the modulus.Since the invention of RSA considerable progress has been made towards more efficient factoring methods. Trial division and Pollard's rho method (1975) find the smallest prime factor

pofnin exponential time:O(p) and , respectively. The elliptic curve method (ecm, 1985) can be expected, on loose heuristic grounds, to take time , for . Note that this is subexponential inp. These are examples ofspecial purposefactoring methods, since their run time depends on the factors to be found. The largest factor found by any of these methods (ecm) so far has 47 decimal digits. None of them is a threat to RSA, if the primes in the modulus have at least, say, 75 decimal digits.The run time of

general purposefactoring methods depends solely on the size of the number to be factored. The most important ones are the Continued Fraction method (CFRAC, 1970), Quadratic Sieve (QS, 1981), and the Number Field Sieve (NFS, 1989). The first two have heuristic expected run time for , though QS is in practice much to be preferred to CFRAC. They share this run time with many other factoring algorithms, among others the worst case of ecm. NFS was the first algorithm to substantially improve upon this time, with heuristic expected run time for andcsome constant between (for `nice' numbers like ) and (for general numbers). NFS is currently considered to be more efficient than QS for numbers that have more than, say, 110 decimal digits.The largest number factored with QS, in 1994, is the famous 129-digit `RSA-challenge' that appeared in the August 1977 issue of Scientific American. Rivest estimated, in 1977, that this factorization would require 40 quadrillion years. With QS it took 8 months, using the idle cycles of computers worldwide. The total run time of this factoring effort has been estimated as 5000 mips years, (i.e., 5000 years on a VAX 780). The largest number factored with NFS, in 1996, is a 130-digit RSA-modulus, with total run time estimated as 550 mips years. Using this figure and the asymptotic run time of NFS (omitting the

o(1) for convenience), one can get an impression of the effort required to factor 512-bit (155-digit) RSA moduli, and conclude that such moduli are on the verge of being breakable. With a moderate amount of progress in factoring, 768-bit keys (a size that is becoming more popular lately) could become vulnerable as well. A polynomial-time factoring algorithm would most likely render RSA useless.

The most common discrete logarithm problem is the following. Given some primep, a generatorgof , and , find such that . Like factoring, this is in its generality believed to be a hard problem, and, again like factoring, the only evidence that it is hard is that we have not yet been able to solve it efficiently.The supposed difficulty of discrete logarithms is the basis for the security of the Diffie-Hellman key exchange protocol (1976). A prime

pand generatorgare publicly known. PartyApicks a random , computes and sends it to partyB. PartyBpicks a random , computes and sends it toA. Both parties can now compute the common key . As mentioned earlier, this key exchange protocol should be used with care, since otherwise it is susceptible to aman in the middle attack.It has not been proved that computing discrete logarithms is necessary to break the Diffie-Hellman protocol (i.e., to compute given

p,g, , and ), but it is obviously sufficient. Many other public key cryptosystems have been proposed that can be broken if discrete logarithms can be computed efficiently. However, unlike factoring based systems which are more or less equally hard to break, here the situation is a bit more complicated.It does not seem to be possible to reduce factoring to discrete logarithms, or vice versa. Nevertheless, there is a strong similarity between the solution methods for the two problems: with a few exceptions (such as ecm), the ideas behind most factoring algorithms can be used to solve discrete logarithms as well. Examples are linear search for

xand Pollard rho, which findxin timeO(x) and operations in , respectively. The `Gaussian integers' method findsxin time , for , and is based on ideas similar to the ones that led to QS. And then there is a Number Field Sieve based method that findsxin time for . Although a `live' cryptosystem using a 60-digit prime was broken in 1991, practical experience with discrete logarithm algorithms is limited. Efforts are underway to change this situation.An important distinction between the exponential and subexponential time discrete logarithm methods is that in the former the group can be replaced by any group, but in the latter, arithmetic properties of the set (which is used to represent ) are crucial. This has several interesting consequences, of which I mention a few.

If

ggenerates only a subgroup of orderq<p-1 of , and , thenxcan still be found in operations in (using Pollard's rho method, or using Shanks' `baby-step-giant-step' method), or in time subexponential inpusing any of the subexponential methods. But a method that runs in time subexponential inqis not known. Ifggenerates the group of points of some elliptic curve modulop, thenxcan again be found in operations in the elliptic curve group. But no method is known that runs in time subexponential in the order ofgor even inp. If, on the other hand,ggenerates or a subgroup thereof, for some fixed integerm>1, thenxcan be found in time subexponential in . The latter is a consequence of the fact that the relevant arithmetic properties of the set of polynomials modulopof degree <mare similar to those of the set .This apparent lack of discrete logarithm algorithms that run in time subexponential in the order of a subgroup or of an entirely different group that cannot be represented in the way the subexponential algorithms require, is exploited in the design of several public key systems. In DSS (the U.S. government's Digital Signature Standard) an order

qsubgroup of is used to improve the speed of the cryptosystem, while at the same time reducing the size of the resulting signatures, without, hopefully, compromising the security: breaking it requires time either or , both of which are supposedly infeasible for the specified sizes and (the Russian variant of DSS requires ). Elliptic curve based cryptosystems achieve the same objectives simply by choosingpsmall, but large enough to make attacks infeasible.Since is fixed at 159 and the increase of processor speed has not leveled off yet, it is conceivable that a moderate amount of progress in exponential time discrete logarithm algorithms could make DSS vulnerable within the foreseeable future. Also, some specialists find it too early to give up hope for better than exponential time attacks on elliptic curve based systems.

We have seen that the factoring and discrete logarithm problems are remarkably similar: both are easy to formulate, believed to be hard purely based on our lack of success solving them efficiently, suitable for the design of public key cryptosystems, and, most remarkably, they seem to be susceptible to very similar solution methods. The last point is quite worrisome: even though not all factoring methods can be turned into discrete logarithm methods (ecm is the most notable exception), most can. Thus, it is conceivable that a newly invented factoring method that wipes out all factoring based cryptosystems, would have the same effect on discrete logarithm based cryptosystems. Obviously, there is a strong need for diversification in the design of public key cryptosystems.These issues, though crucial for the design of secure networks, are actually the least of our current worries. It is not unlikely that instead of enjoying the fruits of our number theoretic incompetence we will soon be harvesting the rotten fruits of our incompetence at properly implementing or using the much needed security measures. As soon as we leave the realm of mathematics, security considerations become much more confused and complicated: human factors, compatibility issues, trust management, key management, key escrow, export restrictions, to mention only a few, are crucial issues that have an enormous potential to be exploited by a worldwide army of hackers that cannot necessarily distinguish a prime from a composite. This is not to say that security on the net cannot be achieved, but the subject requires study of much more than the mathematical issues alone.

Arjen K. Lenstra

Citibank, N.A.

4 Sylvan Way

Parsippany, N. J. 07054

U.S.A.e-mail: arjen.lenstra@citicorp.com

1. A.K. Lenstra, H.W. Lenstra, Jr.,Algorithms in number theory, Chapter 12 in: J. van Leeuwen (ed.),Handbook of theoretical computer science, Volume A,Algorithms and complexity, Elsevier, Amsterdam, 1990.2. D.R. Stinson,

Cryptography, theory and practice, CRC Press, Boca Raton, London, Tokyo, 1995.

Copyright © 1996,

First MondaySecuring the net-the fruits of incompetence by Arjen K. Lenstra.

First Monday, Volume 1, Number 4 - 7 October 1996

http://firstmonday.org/ojs/index.php/fm/article/view/486/407

A Great Cities Initiative of the University of Illinois at Chicago University Library.

© *First Monday*, 1995-2017. ISSN 1396-0466.