Merkle-Hellman vs. RSA
1
Term Paper On Information Security and Privacy
Topic: Theory of Computation Running head: Merkle-Hellman vs. RSA Cryptosystems
Submitted To: Submitted To: Tajinder Kaur
Rohit Nagpal Roll No. B43 11000720
Theory of Computation
Merkle-Hellman vs. RSA
2
Abstract
I chose to compare the unbreakable RSA against the breakable Merkle-Hellman cryptosystems because the Merkle-Hellman cryptosystem was the first knapsack cryptosystem and many post cryptosystem were based off that particular notion. One of the author’s of the RSA cryptosystem, Adi Shamir, broke the Merkle-Hellman cryptosystem so we deemed it necessary to investigate his approach.
Theory of Computation
Merkle-Hellman vs. RSA
3
Introduction
Cryptology or cryptography is the study and process of encoding and decoding plain text messages so that they cannot be read by anyone without a guide or key (Ellis-Christensen, WiseGeek). Crypto is the Greek root for secret or hidden (Wright, 1999). In order for data to be secured for storage or transmission, it must be transformed in such a manner that it would be difficult for an unauthorized individual to be able to discover its true meaning. To do this, certain mathematical equations are used, which are very difficult to solve unless certain strict criteria are met. The level of difficulty of solving a given equation is known as its intractability. These types of equations form the basis of cryptography (Pawliw, August 2003).
Modern cryptology is based on the following standards:
The Discrete Logarithm Problem: This problem forms the basis for a number of public key infrastructure algorithms, such as Diffie-Hellman and EIGamal. This problem has been studied for many years and cryptography based on it has withstood many forms of attacks (Conrad, 2007). The Integer Factorization Problem: This problem is one of the most fundamental of all mathematical concepts. It has been studied intensely for the past 20 years and the consensus seems to be that there is some unproven or undiscovered law of mathematics that forbids any shortcuts. That said, the mere fact that it is being studied intensely leads many others to worry that, somehow, a breakthrough may be discovered (Conrad, 2007). The Elliptic Curve Discrete Logarithm Problem: This is a new cryptographic protocol based upon a reasonably well-known mathematical problem. The properties of elliptic curves have been well known for centuries, but it is only recently that their application to the field of cryptography has been undertaken (Conrad, 2007).
Theory of Computation
Merkle-Hellman vs. RSA
4
Types of Cryptosystems
There are three (3) types of cryptosystems namely: 1. Symmetric key 2. Asymmetric key 3. Hash Functions.
Symmetric Cryptosystem (Secret Key Cryptosystem): Symmetric key (also called private key or secret key) cryptography uses the same key to encrypt and decrypt. The name "private key" derives from the need to keep the key private. A major challenge associated with symmetric key cryptosystems is the secure distribution of keys (Conrad, 2007).
Fig.1 (Symmetric Key Cryptosystem) The above diagram illustrates an exchange of messages using a symmetric key. Alice must first transmit the symmetric key "XYZZY" to Bob via a secure channel. After the key is received, Alice can then encrypt the plaintext with the same key and transmit the ciphertext to Bob, who can then decrypt the ciphertext using the same key (Conrad, 2007). Asymmetric Cryptosystem (Public Key Cryptosystem): Asymmetric key encryption (also called public key encryption) uses two keys: a public and a private key. Data encrypted with one key can be decrypted only with the other key (Conrad, 2007).
Theory of Computation
Merkle-Hellman vs. RSA
5
Hash Functions: Hash functions are also called one-way encryption. A hash function transforms plaintext into a fixed length string which is called a message digest (or simply a hash). It is called one-way encryption because there is no way to convert the message digest back into plaintext.
Fig. 2(Cryptosystem Hash Function – SHA-1)
Most cryptographic hash functions are designed to take a string of any length as input and produce a fixed-length hash value (Wikipedia, March 3, 2009).
Theory of Computation
Merkle-Hellman vs. RSA
6
Merkle-Hellman Cryptosystem
Introduction
Let us first begin by briefly defining what the Merkle-Hellman cryptosystem is. Merkle-Hellman is a cryptosystem that was invented by Ralph Merkle and Martin Hellman in 1978. This cryptosystem was based on the subset sum problem which is a special case of the more popular, knapsack problem. The Merkle-Hellman cryptosystem is an asymmetric cryptosystem, meaning for communication, two keys are required: a public key and a private key. The public key is used only for encryption and the private key is used only for decryption. The public key is an ordered list of sizes, which is really a super increasing set that has been disguised and needs to be converted back to the original super increasing set and solve the simple problem. Adi Shamir (the ‘S’ in RSA) broke the Merkle-Hellman cryptosystem within seven years of its publication. He used Lenstra's fast linear programming algorithm to reveal the super increasing set. Shamir’s proved through his method of breaking the cryptosystem that one does not need to find the original knapsack, or even the original multiplier or modulus, but could possibly find a different multiplier and modulus which exhibit the same proportionality (W/M) with respect to the elements of the original super increasing sequence.
Complexity of the Algorithm
The Merkle-Hellman cryptosystem is based on a special case of the knapsack problem called the subset problem. The knapsack rose as a public key crypto system because of its computational complexity and efficiency (Esfahbod, December 2001). The knapsack problem is known to be NP-complete. According to Brassard, if breaking a cryptosystem is NP-hard, then NP = Co-NP, that is a surprising complexity theory result, because if NP Co-NP, then breaking the Merkle-Hellman cryptosystem cannot be NPhard, and so is likely to be easier than solving the general knapsack problem.
Theory of Computation
Merkle-Hellman vs. RSA
7
Previously Tried Methods
Ronald L. Rivest, Adi Shamir and Leonard M. Adleman invented the first public-key cryptosystem, which is based on integer factorization (Rivest, Shamir, Adleman, February 1978). Diffie and Hellman invented the idea of public key cryptography and proposed the fundamental technique of key agreement using the discrete log problem. That notion bred influence into the idea of a trap-door one-way function and the potential use of the knapsack problem for cryptographic purposes (Lai, 2001). RSA this cryptosystem was published several months before the publication of the Merkle-Hellman cryptosystem. The cryptosystem was developed by Ronald L. Rivest, Adi Shamir and Leonard M. Adleman 1978 (Morain, 1997). RSA was the only cryptosystem before the Merkle-Hellman’s.
Solving the Problem
The Merkle-Hellman problem was solved firstly by Shamir in 1982 (Shamir, 1982). Shamir discovered an attack on the system and proposed prevention. Shamir’s attack was too narrow and modifications were later announced to prevent the original scheme from attacks (Lai, 2001). Those attacks were on one variation of the Merkle-Hellman system called the singley-iterated version. In the summer of 1984, Ernest F. Brickell solved the multiply-iterated version of the Merkle-Hellman cryptosystem problem. The Merkle-Hellman cryptosystem was solved/ broken by Shamir and Brickwell but before them, a number of people investigated it and proposed solutions for its eventual solution.
These people are:
? Giles Brassard
Theory of Computation
Merkle-Hellman vs. RSA ? ? ? ? ? ? ? Tore Herlestam Adi Shamir Hamid R. Amirazizi, E. D. Karnin, and J. M. Reyneri Adi Shamir and Richard E. Zippel Ingemar Ingemarsson Richard Eier and H. Lagger Yvo G. Desmedt, Joos Vandewalle and René Govaerts
8
How it Works
Key generation
In Merkle-Hellman, the keys are comprised of knapsacks. The public key is a 'hard' knapsack, and the private key is an 'easy', or super-increasing, knapsack, combined with two additional numbers, a multiplier and a modulus, which were used to convert the super-increasing knapsack into the hard knapsack. These same numbers are used to transform the sum of the subset of the hard knapsack into the sum of the subset of the easy knapsack, which is solvable in polynomial time.
Encryption
To encrypt a message, a subset of the hard knapsack is chosen by comparing it with a set of bits (the plaintext), equal in length to the key, and making each term in the public key that corresponds to a 1 in the plaintext an element of the subset, while ignoring the terms corresponding to 0 terms in the plaintext. The elements of this subset are added together, and the resulting sum is the ciphertext.
Theory of Computation
Merkle-Hellman vs. RSA
9
Decryption
Decryption is possible because the multiplier and modulus used to transform the easy, super-increasing knapsack into the public key can also be used to transform the number representing the ciphertext into the sum of the corresponding elements of the super-increasing knapsack. Then, using a simple greedy algorithm, the easy knapsack can be solved using 0
arithmetic operations, which decrypts the message.
Comparisons
Merkle-Hellman vs. RSA (Esfahbod, 2001)
?
MH is about 100 times faster than RSA (MH: n ~ 100, RSA: m ~ 500bits) MH needs twice communication capacity, RSA needs same capacity as the input MH’s public key is of size 2.n^2 = 20,000 RSA’s is 2.m = 1000 MH assumes P NP, while RSA assumes factorization is in NP ( P)
?
?
?
What will happen if the problem is solved?
Just like most other knapsack cryptosystems, the Merkle-Hellman cryptosystem has been solved. The question is what is the future like for the cryptosystem? The IEEE, which is the community which has the authority to set standards governing the specifications of public key cryptography systems, published in the year 2000 the P1363: Standard Specifications for Public Key Cryptography, which defined categories for developing cryptosystems. The publication omitted the knapsack method. Researchers seem to focus their efforts on cryptosystems that are developed on the basis of integer factorization, discrete log and elliptic curves.
Theory of Computation
Merkle-Hellman vs. RSA
10
Reason being, there have not been clear directions as to how a knapsack cryptosystem should be constructed to avoid known attacks so far, they are too vulnerable and the number of unbroken knapsack cryptosystems are too few to generate the interest of researchers’ efforts. However, knapsack cryptosystems such as Merkle-Hellman are still of much importance to be studied of one is conducting research in the area of cryptosystems.
Introduction to RSA
The RSA cryptosystem was invented by Ron Rivest, Adi Shamir, and Len Adleman, and was first publicized in the August 1977 issue of Scientific American. RSA stands for the first letter in each of the developers’ last name. The cryptosystem was most commonly used for providing privacy and ensuring authenticity of digital data, however it is now deployed in many commercial systems. RSA has been used by the web servers and browsers to secure traffic, and ensure that privacy is maintained. It is used in the following; authentication of email, secure remote login sessions, eCommerce, and electronic credit-card payment systems. Since the inception of the RSA cryptosystem, it has undergone over 20 years of research which has led to a number attacks, however up to this day it has never been cracked.
Functionality of the RSA Cryptosystem
RSA is a type of encryption known as public key encryption. That is anyone can access the specific public key and therefore encrypt. That key will be able to encrypt (hide), but unable to decrypt (reveal), as that key is asymmetric. Decryption can only be performed with the private key.
Theory of Computation
Merkle-Hellman vs. RSA The RSA algorithm works as follows: Step1: take two large primes, p and q, and compute their product n = p*q; n is called the modulus.
11
Step2: Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means e and (p-1)(q-1) have no common factors except 1. Step3: Find another number d such that ((e*d) - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key. It is currently difficult to obtain the private key d from the public key (n, e). However if one could factor n into p and q, then one could obtain the private key d. An attempt to find p and q for the number 35 is relatively easy, as we all should know that the primes would be 7 and 5. however if the end number (which is 35 here) is the product of two prime numbers which are at least 210 bits (1024 bits), then we would have to do some real time consuming factorization to attain the two primes p and q. The security of the RSA system is exclusively based on the assumption that the factorization process is difficult and time consuming. It is estimated it would take all the computers connected together more than the lifetime of the universe to find the primes that create just one key! It is because factoring is such a slow process and the fact that RSA is an asymmetric encryption process that makes it such an innovative and potent encryption system.
Theory of Computation
Merkle-Hellman vs. RSA
12
RSA Encryption
In the RSA encryption method, texts are translated into sequences of integers. This can be achieved be giving a numerical representation for each letter within the text, which when grouped together these integers will form a large integer, which we will denote as ‘M’. The encryption process is done by converting ‘M’ to an integer ‘C’ (‘C’ represents the encrypted message), by applying the formula; C = Me mod n, recall that n = p*q. Example: We select 2 primes, p = 43 & q = 59 so that n = 43 · 59 = 2537, and with e = 13. gcd (e, (p-1)(q-1) = gcd(13,42.58) = 1 (gcd = greatest common divisor) Let’s take the hypothetical message STOP, first we'll convert the letters into their numerical equivalents (position in the alphabet-1) and then group those numbers into blocks of 4. 1819 1415 = ST OP We encrypt each block using the mapping: C = M13 mod 2537 Computations using modular multiplication show that 181913 mod 2537 = 2081, and 141513 mod 2537 = 2182. The encrypted message is thus 2081 2182.
Theory of Computation
Merkle-Hellman vs. RSA
13
RSA Decryption
The plaintext message can be quickly recovered when the decryption key d, an inverse of e modulo (p-1) (q-1) is known. (Such an inverse exists since gcd (e, (p-1) (q-1)) =1). To see this, note that if d e ? 1 (mod (p-1) (q-1)), there is an integer k such that d e = 1 + k (p-1) (q-1). It follows that. Cd = (Me) d = Mde = M1+k (p-1) (q-1). By Fermat's theorem (assuming that gcd (M, p) = gcd (M, q) = 1, which holds except in rare cases, it follows that Mp-1 ? 1 (mod p) and Mq-1 ? 1 (mod q), consequently. Cd = M · (Mp-1) k (q-1) ? M · 1 ? M (mod p) and:- Cd = M · (Mq-1) k (p-1) ? M · 1 ? M (mod q) Example: Since gcd (p,q) = 1, it follows that:- Cd ? M (mod pq) Using the simple cipher above we receive the message 0981 0461, lets go about decrypting it. n = 43 · 59 and e (exponent) = 13, we can work out that d = 937 is an inverse of 13 modulo 42 · 58 = 2436. We therefore use 937 as our decryption exponent, therefore. P = C937 mod 2537 Using fast modular exponentiation (an algorithm) we compute 0981937 mod 2537, = 0704 and 0461937 mod 2537 = 1115. Quick translation reveals that this message was HELP.
Theory of Computation
Merkle-Hellman vs. RSA
14
Glossary
Cipher text - The plaintext message after being modified or obscured to an unreadable format. Cryptographic algorithm - This is the mathematical operation used for converting plaintext to cipher text. There are two ways in which plaintext can be processed to form the cipher text such as stream cipher and block cipher. Decryption - is the process of converting encrypted data back into its original form, so it can be understood. Encryption - Encryption is the conversion of data into a form, called a cipher text that cannot be easily understood by unauthorized people. IEEE - Institute of Electrical and Electronics Engineers Key - This is a key used to encrypt and/or decrypt the message. Different keys transform the same plaintext into different cipher texts. Only people who know the correct key can decrypt the cipher text accurately. Plaintext - This is the original message in a readable format. Public Key - In cryptography, a public key is a value provided by some designated authority as an encryption key Private Key - In cryptography, a private or secret key is an encryption/decryption key known only to the party or parties that exchange secret messages. Trapdoor problem - is a problem that asks us to reverse the basic mathematical construction of the trapdoor
Theory of Computation
Merkle-Hellman vs. RSA
15
References
Adi Shamir. A Polynomial-time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 145-152. Ronald L. Rivest, Adi Shamir and Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, vol. 21, no. 2, February 1978, pp. 120-126 Bill Cherowitzo, Knapsack Cryptosystems, 21 February 2006, accessed: 9 March 2009, available at:http://www-math.cudenver.edu/~wcherowi/courses/m5410/knap.pdf Behdad Esfahbod, Knapsack Cryptosystems, December 2001, accessed: 9 March 2009, available at:http://74.125.113.132/search? q=cache:bkX0TybvsdEJ:behdad.org/download/Presentations/knapsack/knapsack.ppt+complexity+of+mer kle-hellman+cryptosystem&hl=en&ct=clnk&cd=3&client=firefox-a Ming Kin Lai, Knapsack Cryptosystems: The Past and the Future, March 2001, accessed: 9 March 2009, available at:http://www.ics.uci.edu/~mingl/knapsack.html François Morain, A History of Cryptology, 21 April 1997, accessed: 9 March 2009, available at:http://algo.inria.fr/seminars/sem96-97/morain.html Tricia Ellis-Christensen, What is Cryptology?, accessed: 9 March 2009, available at:
http://www.wisegeek.com/what-is-cryptology.htm David J. Wright, What is Cryptology?, 19 November 1999, accessed: 9 March 2009, available at:http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node2.html Borys Pawliw, What is Cryptology?, 14 August 2003, accessed: 9 March 2009, available at:http://searchsecurity.techtarget.com/sDefinition/0,,sid14_gci214532,00.html#
Theory of Computation
Merkle-Hellman vs. RSA
16
Eric Conrad, Explanation of the Three Types of Cryptosystems, 6 February 2007. Accessed: 9 March 2009, available at:http://www.giac.org/resources/whitepaper/cryptography/52.php Wikipedia, Cryptographic hash function,3 March 2009. Accessed: 9 March 2009, available at:http://en.wikipedia.org/wiki/Cryptographic_hash_function
Theory of Computation
doc_899550637.doc
1
Term Paper On Information Security and Privacy
Topic: Theory of Computation Running head: Merkle-Hellman vs. RSA Cryptosystems
Submitted To: Submitted To: Tajinder Kaur
Rohit Nagpal Roll No. B43 11000720
Theory of Computation
Merkle-Hellman vs. RSA
2
Abstract
I chose to compare the unbreakable RSA against the breakable Merkle-Hellman cryptosystems because the Merkle-Hellman cryptosystem was the first knapsack cryptosystem and many post cryptosystem were based off that particular notion. One of the author’s of the RSA cryptosystem, Adi Shamir, broke the Merkle-Hellman cryptosystem so we deemed it necessary to investigate his approach.
Theory of Computation
Merkle-Hellman vs. RSA
3
Introduction
Cryptology or cryptography is the study and process of encoding and decoding plain text messages so that they cannot be read by anyone without a guide or key (Ellis-Christensen, WiseGeek). Crypto is the Greek root for secret or hidden (Wright, 1999). In order for data to be secured for storage or transmission, it must be transformed in such a manner that it would be difficult for an unauthorized individual to be able to discover its true meaning. To do this, certain mathematical equations are used, which are very difficult to solve unless certain strict criteria are met. The level of difficulty of solving a given equation is known as its intractability. These types of equations form the basis of cryptography (Pawliw, August 2003).
Modern cryptology is based on the following standards:
The Discrete Logarithm Problem: This problem forms the basis for a number of public key infrastructure algorithms, such as Diffie-Hellman and EIGamal. This problem has been studied for many years and cryptography based on it has withstood many forms of attacks (Conrad, 2007). The Integer Factorization Problem: This problem is one of the most fundamental of all mathematical concepts. It has been studied intensely for the past 20 years and the consensus seems to be that there is some unproven or undiscovered law of mathematics that forbids any shortcuts. That said, the mere fact that it is being studied intensely leads many others to worry that, somehow, a breakthrough may be discovered (Conrad, 2007). The Elliptic Curve Discrete Logarithm Problem: This is a new cryptographic protocol based upon a reasonably well-known mathematical problem. The properties of elliptic curves have been well known for centuries, but it is only recently that their application to the field of cryptography has been undertaken (Conrad, 2007).
Theory of Computation
Merkle-Hellman vs. RSA
4
Types of Cryptosystems
There are three (3) types of cryptosystems namely: 1. Symmetric key 2. Asymmetric key 3. Hash Functions.
Symmetric Cryptosystem (Secret Key Cryptosystem): Symmetric key (also called private key or secret key) cryptography uses the same key to encrypt and decrypt. The name "private key" derives from the need to keep the key private. A major challenge associated with symmetric key cryptosystems is the secure distribution of keys (Conrad, 2007).
Fig.1 (Symmetric Key Cryptosystem) The above diagram illustrates an exchange of messages using a symmetric key. Alice must first transmit the symmetric key "XYZZY" to Bob via a secure channel. After the key is received, Alice can then encrypt the plaintext with the same key and transmit the ciphertext to Bob, who can then decrypt the ciphertext using the same key (Conrad, 2007). Asymmetric Cryptosystem (Public Key Cryptosystem): Asymmetric key encryption (also called public key encryption) uses two keys: a public and a private key. Data encrypted with one key can be decrypted only with the other key (Conrad, 2007).
Theory of Computation
Merkle-Hellman vs. RSA
5
Hash Functions: Hash functions are also called one-way encryption. A hash function transforms plaintext into a fixed length string which is called a message digest (or simply a hash). It is called one-way encryption because there is no way to convert the message digest back into plaintext.
Fig. 2(Cryptosystem Hash Function – SHA-1)
Most cryptographic hash functions are designed to take a string of any length as input and produce a fixed-length hash value (Wikipedia, March 3, 2009).
Theory of Computation
Merkle-Hellman vs. RSA
6
Merkle-Hellman Cryptosystem
Introduction
Let us first begin by briefly defining what the Merkle-Hellman cryptosystem is. Merkle-Hellman is a cryptosystem that was invented by Ralph Merkle and Martin Hellman in 1978. This cryptosystem was based on the subset sum problem which is a special case of the more popular, knapsack problem. The Merkle-Hellman cryptosystem is an asymmetric cryptosystem, meaning for communication, two keys are required: a public key and a private key. The public key is used only for encryption and the private key is used only for decryption. The public key is an ordered list of sizes, which is really a super increasing set that has been disguised and needs to be converted back to the original super increasing set and solve the simple problem. Adi Shamir (the ‘S’ in RSA) broke the Merkle-Hellman cryptosystem within seven years of its publication. He used Lenstra's fast linear programming algorithm to reveal the super increasing set. Shamir’s proved through his method of breaking the cryptosystem that one does not need to find the original knapsack, or even the original multiplier or modulus, but could possibly find a different multiplier and modulus which exhibit the same proportionality (W/M) with respect to the elements of the original super increasing sequence.
Complexity of the Algorithm
The Merkle-Hellman cryptosystem is based on a special case of the knapsack problem called the subset problem. The knapsack rose as a public key crypto system because of its computational complexity and efficiency (Esfahbod, December 2001). The knapsack problem is known to be NP-complete. According to Brassard, if breaking a cryptosystem is NP-hard, then NP = Co-NP, that is a surprising complexity theory result, because if NP Co-NP, then breaking the Merkle-Hellman cryptosystem cannot be NPhard, and so is likely to be easier than solving the general knapsack problem.
Theory of Computation
Merkle-Hellman vs. RSA
7
Previously Tried Methods
Ronald L. Rivest, Adi Shamir and Leonard M. Adleman invented the first public-key cryptosystem, which is based on integer factorization (Rivest, Shamir, Adleman, February 1978). Diffie and Hellman invented the idea of public key cryptography and proposed the fundamental technique of key agreement using the discrete log problem. That notion bred influence into the idea of a trap-door one-way function and the potential use of the knapsack problem for cryptographic purposes (Lai, 2001). RSA this cryptosystem was published several months before the publication of the Merkle-Hellman cryptosystem. The cryptosystem was developed by Ronald L. Rivest, Adi Shamir and Leonard M. Adleman 1978 (Morain, 1997). RSA was the only cryptosystem before the Merkle-Hellman’s.
Solving the Problem
The Merkle-Hellman problem was solved firstly by Shamir in 1982 (Shamir, 1982). Shamir discovered an attack on the system and proposed prevention. Shamir’s attack was too narrow and modifications were later announced to prevent the original scheme from attacks (Lai, 2001). Those attacks were on one variation of the Merkle-Hellman system called the singley-iterated version. In the summer of 1984, Ernest F. Brickell solved the multiply-iterated version of the Merkle-Hellman cryptosystem problem. The Merkle-Hellman cryptosystem was solved/ broken by Shamir and Brickwell but before them, a number of people investigated it and proposed solutions for its eventual solution.
These people are:
? Giles Brassard
Theory of Computation
Merkle-Hellman vs. RSA ? ? ? ? ? ? ? Tore Herlestam Adi Shamir Hamid R. Amirazizi, E. D. Karnin, and J. M. Reyneri Adi Shamir and Richard E. Zippel Ingemar Ingemarsson Richard Eier and H. Lagger Yvo G. Desmedt, Joos Vandewalle and René Govaerts
8
How it Works
Key generation
In Merkle-Hellman, the keys are comprised of knapsacks. The public key is a 'hard' knapsack, and the private key is an 'easy', or super-increasing, knapsack, combined with two additional numbers, a multiplier and a modulus, which were used to convert the super-increasing knapsack into the hard knapsack. These same numbers are used to transform the sum of the subset of the hard knapsack into the sum of the subset of the easy knapsack, which is solvable in polynomial time.
Encryption
To encrypt a message, a subset of the hard knapsack is chosen by comparing it with a set of bits (the plaintext), equal in length to the key, and making each term in the public key that corresponds to a 1 in the plaintext an element of the subset, while ignoring the terms corresponding to 0 terms in the plaintext. The elements of this subset are added together, and the resulting sum is the ciphertext.
Theory of Computation
Merkle-Hellman vs. RSA
9
Decryption
Decryption is possible because the multiplier and modulus used to transform the easy, super-increasing knapsack into the public key can also be used to transform the number representing the ciphertext into the sum of the corresponding elements of the super-increasing knapsack. Then, using a simple greedy algorithm, the easy knapsack can be solved using 0
arithmetic operations, which decrypts the message.Comparisons
Merkle-Hellman vs. RSA (Esfahbod, 2001)
?
MH is about 100 times faster than RSA (MH: n ~ 100, RSA: m ~ 500bits) MH needs twice communication capacity, RSA needs same capacity as the input MH’s public key is of size 2.n^2 = 20,000 RSA’s is 2.m = 1000 MH assumes P NP, while RSA assumes factorization is in NP ( P)
?
?
?
What will happen if the problem is solved?
Just like most other knapsack cryptosystems, the Merkle-Hellman cryptosystem has been solved. The question is what is the future like for the cryptosystem? The IEEE, which is the community which has the authority to set standards governing the specifications of public key cryptography systems, published in the year 2000 the P1363: Standard Specifications for Public Key Cryptography, which defined categories for developing cryptosystems. The publication omitted the knapsack method. Researchers seem to focus their efforts on cryptosystems that are developed on the basis of integer factorization, discrete log and elliptic curves.
Theory of Computation
Merkle-Hellman vs. RSA
10
Reason being, there have not been clear directions as to how a knapsack cryptosystem should be constructed to avoid known attacks so far, they are too vulnerable and the number of unbroken knapsack cryptosystems are too few to generate the interest of researchers’ efforts. However, knapsack cryptosystems such as Merkle-Hellman are still of much importance to be studied of one is conducting research in the area of cryptosystems.
Introduction to RSA
The RSA cryptosystem was invented by Ron Rivest, Adi Shamir, and Len Adleman, and was first publicized in the August 1977 issue of Scientific American. RSA stands for the first letter in each of the developers’ last name. The cryptosystem was most commonly used for providing privacy and ensuring authenticity of digital data, however it is now deployed in many commercial systems. RSA has been used by the web servers and browsers to secure traffic, and ensure that privacy is maintained. It is used in the following; authentication of email, secure remote login sessions, eCommerce, and electronic credit-card payment systems. Since the inception of the RSA cryptosystem, it has undergone over 20 years of research which has led to a number attacks, however up to this day it has never been cracked.
Functionality of the RSA Cryptosystem
RSA is a type of encryption known as public key encryption. That is anyone can access the specific public key and therefore encrypt. That key will be able to encrypt (hide), but unable to decrypt (reveal), as that key is asymmetric. Decryption can only be performed with the private key.
Theory of Computation
Merkle-Hellman vs. RSA The RSA algorithm works as follows: Step1: take two large primes, p and q, and compute their product n = p*q; n is called the modulus.
11
Step2: Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means e and (p-1)(q-1) have no common factors except 1. Step3: Find another number d such that ((e*d) - 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key. It is currently difficult to obtain the private key d from the public key (n, e). However if one could factor n into p and q, then one could obtain the private key d. An attempt to find p and q for the number 35 is relatively easy, as we all should know that the primes would be 7 and 5. however if the end number (which is 35 here) is the product of two prime numbers which are at least 210 bits (1024 bits), then we would have to do some real time consuming factorization to attain the two primes p and q. The security of the RSA system is exclusively based on the assumption that the factorization process is difficult and time consuming. It is estimated it would take all the computers connected together more than the lifetime of the universe to find the primes that create just one key! It is because factoring is such a slow process and the fact that RSA is an asymmetric encryption process that makes it such an innovative and potent encryption system.
Theory of Computation
Merkle-Hellman vs. RSA
12
RSA Encryption
In the RSA encryption method, texts are translated into sequences of integers. This can be achieved be giving a numerical representation for each letter within the text, which when grouped together these integers will form a large integer, which we will denote as ‘M’. The encryption process is done by converting ‘M’ to an integer ‘C’ (‘C’ represents the encrypted message), by applying the formula; C = Me mod n, recall that n = p*q. Example: We select 2 primes, p = 43 & q = 59 so that n = 43 · 59 = 2537, and with e = 13. gcd (e, (p-1)(q-1) = gcd(13,42.58) = 1 (gcd = greatest common divisor) Let’s take the hypothetical message STOP, first we'll convert the letters into their numerical equivalents (position in the alphabet-1) and then group those numbers into blocks of 4. 1819 1415 = ST OP We encrypt each block using the mapping: C = M13 mod 2537 Computations using modular multiplication show that 181913 mod 2537 = 2081, and 141513 mod 2537 = 2182. The encrypted message is thus 2081 2182.
Theory of Computation
Merkle-Hellman vs. RSA
13
RSA Decryption
The plaintext message can be quickly recovered when the decryption key d, an inverse of e modulo (p-1) (q-1) is known. (Such an inverse exists since gcd (e, (p-1) (q-1)) =1). To see this, note that if d e ? 1 (mod (p-1) (q-1)), there is an integer k such that d e = 1 + k (p-1) (q-1). It follows that. Cd = (Me) d = Mde = M1+k (p-1) (q-1). By Fermat's theorem (assuming that gcd (M, p) = gcd (M, q) = 1, which holds except in rare cases, it follows that Mp-1 ? 1 (mod p) and Mq-1 ? 1 (mod q), consequently. Cd = M · (Mp-1) k (q-1) ? M · 1 ? M (mod p) and:- Cd = M · (Mq-1) k (p-1) ? M · 1 ? M (mod q) Example: Since gcd (p,q) = 1, it follows that:- Cd ? M (mod pq) Using the simple cipher above we receive the message 0981 0461, lets go about decrypting it. n = 43 · 59 and e (exponent) = 13, we can work out that d = 937 is an inverse of 13 modulo 42 · 58 = 2436. We therefore use 937 as our decryption exponent, therefore. P = C937 mod 2537 Using fast modular exponentiation (an algorithm) we compute 0981937 mod 2537, = 0704 and 0461937 mod 2537 = 1115. Quick translation reveals that this message was HELP.
Theory of Computation
Merkle-Hellman vs. RSA
14
Glossary
Cipher text - The plaintext message after being modified or obscured to an unreadable format. Cryptographic algorithm - This is the mathematical operation used for converting plaintext to cipher text. There are two ways in which plaintext can be processed to form the cipher text such as stream cipher and block cipher. Decryption - is the process of converting encrypted data back into its original form, so it can be understood. Encryption - Encryption is the conversion of data into a form, called a cipher text that cannot be easily understood by unauthorized people. IEEE - Institute of Electrical and Electronics Engineers Key - This is a key used to encrypt and/or decrypt the message. Different keys transform the same plaintext into different cipher texts. Only people who know the correct key can decrypt the cipher text accurately. Plaintext - This is the original message in a readable format. Public Key - In cryptography, a public key is a value provided by some designated authority as an encryption key Private Key - In cryptography, a private or secret key is an encryption/decryption key known only to the party or parties that exchange secret messages. Trapdoor problem - is a problem that asks us to reverse the basic mathematical construction of the trapdoor
Theory of Computation
Merkle-Hellman vs. RSA
15
References
Adi Shamir. A Polynomial-time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 145-152. Ronald L. Rivest, Adi Shamir and Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, vol. 21, no. 2, February 1978, pp. 120-126 Bill Cherowitzo, Knapsack Cryptosystems, 21 February 2006, accessed: 9 March 2009, available at:http://www-math.cudenver.edu/~wcherowi/courses/m5410/knap.pdf Behdad Esfahbod, Knapsack Cryptosystems, December 2001, accessed: 9 March 2009, available at:http://74.125.113.132/search? q=cache:bkX0TybvsdEJ:behdad.org/download/Presentations/knapsack/knapsack.ppt+complexity+of+mer kle-hellman+cryptosystem&hl=en&ct=clnk&cd=3&client=firefox-a Ming Kin Lai, Knapsack Cryptosystems: The Past and the Future, March 2001, accessed: 9 March 2009, available at:http://www.ics.uci.edu/~mingl/knapsack.html François Morain, A History of Cryptology, 21 April 1997, accessed: 9 March 2009, available at:http://algo.inria.fr/seminars/sem96-97/morain.html Tricia Ellis-Christensen, What is Cryptology?, accessed: 9 March 2009, available at:
http://www.wisegeek.com/what-is-cryptology.htm David J. Wright, What is Cryptology?, 19 November 1999, accessed: 9 March 2009, available at:http://www.math.okstate.edu/~wrightd/crypt/crypt-intro/node2.html Borys Pawliw, What is Cryptology?, 14 August 2003, accessed: 9 March 2009, available at:http://searchsecurity.techtarget.com/sDefinition/0,,sid14_gci214532,00.html#
Theory of Computation
Merkle-Hellman vs. RSA
16
Eric Conrad, Explanation of the Three Types of Cryptosystems, 6 February 2007. Accessed: 9 March 2009, available at:http://www.giac.org/resources/whitepaper/cryptography/52.php Wikipedia, Cryptographic hash function,3 March 2009. Accessed: 9 March 2009, available at:http://en.wikipedia.org/wiki/Cryptographic_hash_function
Theory of Computation
doc_899550637.doc