Later this year I will have text published in the Nordic Yearbook on Law Informatics (Nordisk Årsbok i Rättsinformatik): "A Paradigm Shift in Electronic Surveillance Law".
I wrote a section about cryptanalysis but later came to the conclusion that the section should be excluded. Considering that the work is done I do not want it to be vasted. After participating in a discussion on Rick Falkvinge's blog which, inter alia, concerned cryptanalysis I decided to publish the section here. It is written for a law journal which explains why it is quite rudimentary. The purpose of this section was to explain why law enforcement and intelligence agencies focus more on traffic analysis and less on content analysis. My explanation is that there is a tendency that with increasing processing power of computers the efficiency between encryption and attacking a crypto (cryptanalysis) is growing, to the detriment of the later. Thus, traffic analysis is becoming more important.
All comments are welcome. Please have some understanding that I am lawyer and not a mathematician.
Encryption and Cryptanalysis
With increasing processing power of computers the efficiency between encryption and attacking a crypto (cryptanalysis) is growing, to the detriment of the later.1) I will use the example of the RSA algorithm to explain why there is such a tendency. The RSA is an algorithm used for public-key cryptography and it was invented by Ronald L. Rivest, Adi Shamir, and Leonard Adleman in 1977, the letters RSA are the initials of their surnames. The RSA cryptosystem is based on the use of prime numbers and factoring.2)
Prime numbers are numbers that are not evenly divisible by any smaller number, except 1, for example 2, 3, 5, 7, 11, and 13. A non-prime, or composite number, is the product of smaller primes, known as its prime factors. 391, for example is the product of the primes 17 and 23. A number is factored when all of its prime factors are identified. As the size of the composite number increases, the difficulty of factoring and cryptanalysis increases rapidly.3) I will explain why.
RSA involves a public key for encryption and a private key for decryption. The private key corresponds to the public key, because both are based on the same modulus, n, which in turn is based on prime numbers.4) In the example above n is 391. One method of cryptanalysis is for attacker to discover the private key corresponding to a given public key. This is done by factoring the public modulus, n, into its prime factors, in the example above 17 and 23. From the prime factors and the public key exponent e, the attacker can easily get the private key exponent d. The difficulty lies in factoring n. The encryptor can use larger prime factors increasing the difficulty to factor.5) As indicated above, increasing processing power of computers allows the use of larger prime factors which will increase the difference in efficiency between encryption and cryptanalysis, to the detriment of the later.
The resources needed to add a digit when encrypting is linear while the resources needed to attack such a crypto a crypto is exponential. See the chart below.6)
I will attempt to explain this through the use of practical example. Assume that you have four digit entry code to your house with the numbers 0-9. This will generate 10 000 combinations (10*10*10*10). It will take you seconds to enter the code. For an intruder it would probably take several hours if he or she randomly enters different combinations. However, if somebody constructs a robot that can enter 1 000 combinations in a minute, you will have a problem because the code will be broken within ten minutes. This can be solved by adding a fifth digit, generating 100 000 combinations (10*10*10*10*10). It would take you a mere extra second to enter the code, while it could require the robot to work more than an extra hour. The same logics apply to cryptos using large prime factors generating a private key with many digits.
However, there is a danger that an attacker in the future may use faster machines and better factoring algorithms than are currently available, which may be used to attack RSA cryptosystem keys generated in the past.7) Moreover, I am making a general observation which does not exclude the possibility that specific encryption techniques already may be subject to successful attacks that use currently available technology and algorithms.
It is easy to factor 100-digit numbers with today's hardware and algorithms. There is no public information which indicates that numbers of more than 200 digits have been successfully factored. For example, RSA modulus RSA-2048, has a length of 2048 bits (617 decimal digits). RSA laboratories expect RSA-2048 to stand for decades, assuming that there will be no fundamental algorithmic or computing advances.8) Such advances may include the discovery of a new factoring method which factoring researchers consider has a remote possibility, or the development of a quantum computer which involves significant practical difficulties.9)
1) FRA, 14 March 2007, Sveriges Television (Publ.), Frågor & svar, (16 November 2008), Question & Answer 5; Klamberg, Mark, Nilsson, Mikael, Petersson, Anna, Seipel, Peter, Flyghed, Janne, Magnusson Sjöberg, Cecilia, Karlgren, Jussi, Bylund, Markus, Palmås, Karl, Ström, Pär, Thorburn, Daniel & Westerholm, Johan, FRA-lagen medför massiv kartläggning av oskyldiga Dagens Nyheter, 3 September 2008
2) RSA Laboratories (Publ.), RSA Algorithm, "http://www.rsa.com/rsalabs/node.asp?id=2146", (27 November 2008)
3) RSA Laboratories (Publ.), The RSA Factoring Challenge FAQ, "http://www.rsa.com/rsalabs/node.asp?id=2094#HowWereTheNumbersGenerated", (27 November 2008)
4) RSA Laboratories (Publ.), Crypto FAQ, "http://www.rsa.com/rsalabs/node.asp?id=2152", (27 November 2008), section 3.1.1 What is the RSA cryptosystem?
5) ibid, section 3.1.3 What would it take to break the RSA cryptosystem?; section 2.3.3 What is the factoring problem?
6) I have made the following assumptions concerning the relation between resources (y) and digits used (x) with k as the potential combinations for a digit. In the example with the entry code to the house there is 10 potential combinations (0-9). This generates the following to functions. Resources to encrypt (y1)=x*10; resources to attack (y2)=e x
7) ibid, section 2.3.5 What improvements are likely in factoring capability?
8) The RSA Factoring Challenge FAQ
9) Crypto FAQ, section 2.3.3 What is the factoring problem?; section 2.3.5 What improvements are likely in factoring capability?; section 2.4.3 What is exhaustive key search?; section 7.17 What is quantum computing?