[Next] [Up] [Previous] [Index]

Other Public-Key Methods

The most important alternative public-key method is elliptic curve public-key cryptography.

One of several possible ways to perform it is a variation of Diffie-Hellman. Instead of performing Diffie-Hellman on numbers modulo a prime, perform it on polynomials modulo a polynomial, with the coefficients also being numbers modulo a prime which can even be 2. However, with elliptic curves, multiplication modulo the polynomial rather than exponentiation can also be used.

A proposal by Dr. Adi Shamir, called the Shamir three-pass protocol, requires ciphers that can be applied to a message in either order to produce the same final enciphered result; that is, ciphers that commute with each other.

With such ciphers, the following can be done:

A wishes to send a message to B. So, A takes the message, and enciphers it in cipher A, sending the result to B.

B enciphers it in cipher B, sending it back.

A can still decipher in cipher A, and does so, leaving behind the message only enciphered in cipher B. This is sent back to B.

B reads the message, since it's only enciphered in his cipher.

It was hoped that this method might make public-key cryptography easier, in that it might be more possible to design ciphers that commute and that are secure in this protocol. Like public-key cryptography, it allows secure communications without prior exchange of a shared secret key in a secure manner. However, there is no public "key" in this protocol, and therefore it is considered to be distinct from public-key cryptography by some authorities.

However, only the Massey-Omura cryptosystem (and perhaps other essentially similar ones) is a secure method based on this protocol.

Given an agreed-upon prime modulus M, A sends a message to B by first raising it to the power A modulo M.

B then raises it to the power B, and sends it back.

A, knowing the value of A, can easily find the corresponding decryption exponent that takes the A-th root modulo M, and sends back the message, now only raised to the B-th power.

B then finds the B-th root, using his decryption exponent.

Since the modulus is a prime, finding the decryption exponent from the encryption exponent is easy for both parties; but the algorithm is secure because neither exponent can be found from the messages, because the discrete logarithm problem is hard.

A mathematics book once suggested using multiplication by a large prime as the method of encryption, where the message itself must be a large prime. Since factoring is hard, the individual messages can't be cracked. However, the three messages in the system are AM, ABM, and BM, from which M can be found by the simple operation of division.

Many conventional cryptosystems can be made to commute. For example, if A performed simple substitution, and B performed transposition, the two operations would commute with each other. However, those methods aren't secure either: they basically reduce to A and B each separately encrypting half the message, leaving the other half alone.

Thus, it appears for now that the Shamir three-pass protocol is only effective when used with operations such as exponentiation, which are also suitable for use in public-key ciphers of the conventional type.

I examined this problem more closely some time ago in a USENET post, in which I stated the following:

Shamir's Three-Pass Protocol works as follows:

Two parties, F and G, each have a transformation, f() and g() respectively, the inverses of which, at least, are kept secret, and which commute.

A message, M, is transferred from F to G in the following steps:

F applies f to M, and transmits f(M) to G.

G applies g to f(M), and transmits g(f(M)) to F.

F applies the inverse of f to g(f(M)), and obtains g(M) because f and g commute, and therefore g(f(M)) equals f(g(M)), and transmits g(M) to G.

G applies the inverse of g to g(M), and obtains M.

Diffie-Hellman key establishment works as follows:

Two parties, F and G, agree on a prime number p such that this prime number minus one has large prime factors, so that discrete logs modulo the prime are hard to find.

Also, they agree on a common value A.

F calculates A^f modulo p, and transmits this to G.

G calculates A^g modulo p, and transmits this to F.

F calculates A^(fg) by calculating (A^g)^f.

G calculates A^(fg) by calculating (A^f)^g.

The principle of Diffie-Hellman key establishment can be generalized by substituting f(A) for some function f for A^f modulo p. If we do so, generalized Diffie-Hellman key establishment proceeds as follows:

F transmits f(A) to G.

G transmits g(A) to F.

F calculates f(g(A)).

G calculates g(f(A)); if g(f(A)) is to equal f(g(A)), then f and g must commute.

The fact that f() and g() are required to commute suggests a relationship to the Shamir three-pass protocol.

The favored attacks against insecure variants of the three-pass protocol are based on the principle that an attacker, having both f(M) and g(f(M)), can use these to deduce g or at least that part of g applicable to the message, and then directly obtain the part of the inverse transformation of g applicable to the message.

These attacks would become infeasible under two conditions.

One is if it would be infeasible to determine the inverse transformation of g knowing g.

In that case, g could be used as the public key for a full-fledged public-key cryptosystem operating analogously to the well-known Rivest-Shamir-Adleman cryptosystem.

Another is if it would be infeasible to determine g given both f(M) and g(f(M)). This is true for the Massey-Omura cryptosystem because of the difficulty of the discrete logarithm problem for suitable prime moduli.

In the case of generalized Diffie-Hellman key establishment described above, an eavesdropper has access to A (a portion of the public key), f(A), and g(A). If the attacker could determine g given A and g(A), then the attacker could compute g(f(A)), the key established by the procedure.

Hence, the properties required of transformations in order for them to serve as the basis for a secure variant of the Shamir three-pass protocol, and for them to serve as the basis for a secure variant of generalized Diffie-Hellman key establishment, are closely related.

For the Shamir three-pass protocol:

a) f and g must commute.

b) At least one of the following must be true: given x and f(x) (and, similarly, x and g(x)) it must be difficult to determine f, or, given f, it must be difficult to determine the inverse of f (but F is still in possession of the inverse of f, due to having more information than f itself).

For generalized Diffie-Hellman key establishment:

a) f and g must commute.

b) Given x and f(x) (and, similarly, x and g(x)) it must be difficult to determine f.

For a classic public-key cryptosystem:

a) Given f, it must be difficult to determine the inverse of f, but it must still be possible for F to produce both f and its inverse for his own use.

As these are simply necessary conditions, it is still not proven that there are no f and g that would work for the three-pass protocol but not either for a classical public-key encryption or for generalized Diffie-Hellman.

However, this does indicate that any functions f and g that would be useful for the Shamir three-pass protocol would also be useful for either generalized Diffie-Hellman key exchange or for a classic public-key cryptosystem.

In addition, for Shamir's three-pass protocol, f and g must satisfy more restrictive conditions.

Compared to generalized Diffie-Hellman key exchange, f and g must have inverses.

Compared to a classic public-key cryptosystem, f must commute with a g such that g and its inverse could be produced by someone who does not share a secret with F.

Hence, it appears that the Shamir three-pass protocol should not be considered as offering a route to communications without a shared secret that is broader than that offered by existing public-key techniques. Furthermore, the Shamir three-pass protocol should be regarded as intimately related to public-key encryption, and not as belonging to a separate branch of study.

A public-key system that has been found to be unsafe, and which is therefore of primarily historical interest today, is the knapsack method. Unlike RSA and Diffie-Hellman, this system was based on a mathematical problem which was known to be NP-complete, and thus one that was tougher to crack than either factoring or the discrete logarithm problem.

The knapsack problem is this: given a set of numbers, and another larger number which may be the total of some of them, determine if it is such a total, and if so, of which of the numbers in the set.

This problem is very hard in general. But if the set of numbers was such that every number is greater than the sum of all the ones smaller than itself in the set, then solving the knapsack problem becomes fundamentally no harder (it just requires a tiny bit of extra arithmetic) than converting a number decimal notation to binary notation.

The knapsack cipher worked as follows: start with a superincreasing knapsack composed of many large numbers. Then, disguise the knapsack by multiplying all the numbers in it by some quantity, modulo a limit which must be larger than the sum of all the numbers in the knapsack.

Then, a message can be sent to you in the form of the sum of selected elements of the knapsack. (Note that a message needs to have a significant number of both 1 and 0 bits in it to be secure.)

You then convert the message to be in terms of the undisguised knapsack, by multiplying it, modulo the limit, by the inverse of the quantity used to disguise the knapsack. Note that the modulus does not need to be revealed as part of the public key. Also, it may be noted that while this system only involves addition for sending a message, it is significantly more cumbersome than most other public key systems, since the public key, instead of being just one or two very large numbers, might consist of over 200 such numbers.

Because the knapsack cipher was based on disguising such a set of numbers, called a superincreasing knapsack as an ordinary knapsack, although solving the general knapsack problem had been proven to be an NP-complete problem, someone attacking a knapsack cipher had one piece of information that someone trying to solve the general knapsack problem did not: that the knapsack to be solved was a disguised version of a superincreasing knapsack. Thus, the flaw was that the security of the cipher depended not only on the difficulty of the knapsack problem, but on the security of the disguise.

Of course, there are ways to improve the knapsack cipher, but they have been broken too. A knapsack could be disguised twice, modulo two different primes; but the iterated knapsack was broken too. Instead of starting with a true superincreasing knapsack, one could start with one that was 'close' to superincreasing, one which involved one small knapsack problem (or perhaps several) that had to be solved the hard way; this wouldn't be too impractical, since it is only as an NP-complete problem becomes large that the time required to solve it becomes excessive; and this would presumably make an attack more difficult, because the properties of the knapsack under the disguise would not be as straightforward. Doubtless, though, this too is not secure.

[Next] [Up] [Previous] [Index]

Chapter Start
Table of Contents
Home Page