The biggest problem in symmetric encryption is that of key management. For
communication to take place in an encrypted mode, each party must have the
same encryption/decryption key. But how can the key be communicated to the
other party in a secure fashion except by some type of public key encryption?
Adi Shamir (he is the S in RSA) devised a protocol called the Three-Pass Key Exchange Protocol. This was never published, because it has only limited security; this will be discussed in detail later. The protocol depends on a commutative cipher, where the decryption may take place either in the same or the opposite order of the encryption. Here is the protocol:
1.) Alice chooses a key K that she wishes to exchange with Bob. She encrypts it with some key A, which only she knows, and sends Bob A(K).
2.) Bob re-encrypts this message with some key B which only he knows, and sends Alice B(A(K)).
3.) Here is where the commutative property of the cipher comes into play. Alice decrypts with A, getting -A(B(A(K))) where -A represents a decryption. If the cipher is commutative, this results in B(K), which she sends back to Bob, who can decrypt it with -B.
The need for a commutative cipher is explained by the fact that the decryption is done in the SAME order as the encryption instead of REVERSE order.
A commutative cipher is one in which the order of encryption and decryption is interchangeable, just as the order of multiplication is interchangeable; i.e., A*B*C=A*C*B=C*B*A. A simple XOR with a the individual keys is such a commutative cipher.
The attack that makes this protocol less than optionally secure when XOR is the cipher requires the attacker to capture all three messages, and to know the algorithm that is being used to encrypt; not too difficult a task for NSA, for example, and quite possibly others. If the algorithm is XOR, as suggested above for example, it is only necessary to XOR the first message with the second to get B, which then can be used to XOR the third message to get K. Also, XORing the second and third messages will yield A. Having A and B intercepted is of no great consequence; they can be discarded after the exchange of K. But K is supposed to be secure, and the protocol is weak in this respect. BE WARNED, then, and use at your own discretion. Suggestions might include use of different channels of communication for the three messages, and breaking K into parts which must be recombined in a certain order, giving rise to more than three messages.
In his definitive work on cryptography, Applied Cryptography 2nd Edition, Bruce Schneier makes a brief reference to a system devised separately by Shamir and Omura for a commutative cipher. The parties agree and communicate a large prime modulus P such that P-1 has a large prime factor. (In my work I have required that (P-1)/2 be prime, making the prime factor as large as possible). I have given this technique the name PUBLIC MODULUS ENCRYPTION.
Next Alice picks an encryption key EA and a decryption key DA such that DA*EA mod (P-1) = 1. Neither of these keys is communicated to anyone else. There is a requirement that EA (and by inference DA) be relatively prime to P-1 or else there would not exist the proper multiplicative inverse. With P-1 defined as a prime number * 2 any odd number will suffice to meet this requirement.
Bob also picks an encryption key EB and calculates the inverse DB. He does not communicate these to anyone else. The parties then perform the Shamir Three-Pass Protocol using the encryption and decryption formulas:
C = M^E mod P M = C^D mod Pwhere C is the ciphertext and M the message text, E and D the encryption and decryption keys, and P the prime public modulus.
The fact that this cipher is commutative can be seen from an analysis of the encryption formulas. Successive encryption by EA and EB would result in a result of (M^EA)^EB which can be reduced to M^EA*EB which is the same as (M^EB)^EA or M^EB*EA.
Certain limitations are evident here. P must be greater than the message to be transmitted, or else the message will be mapped into the smaller P field and garbled. Using 32-bit operations means that P should be in the range of 2^31 to 2^32. This puts a limitation on the message that the first character be less than ASCII 128, or at least less than the high order 8 bits of P.
Theory states that there are approximately 93*10^6 primes between 2^31 and 2^32. Using my own implementation of the Miller-Rabin probabalistic prime test, I have extracted 7.46*10^6 primes which meet the requirement that (P-1)/2 is also prime. These are stored in 375 files of 200,000 bytes each, and are ZIPped in groups of 10, having a size of about 598 kb. Three of these files are on one of 13 disks, along with PKUNZIP and TECHEDIT, the only editor that I know of that will read a 200,000 byte file. (Note: I format floppies to 1.91 mb, using 2M30).
People have indicated their opinions that this system is of the same complexity to break as 32-bit RSA by factoring the modulus. I strongly disagree here. The modulus is a prime, and has no factors, unlike RSA where the modulus is the product of two primes. In RSA the modulus is P*Q, and the encryption and decryption keys are multiplicative inverse modulo (P-1)*(Q-1). The modulus and encryption key (Usualy 3 or 11h) are available, and if the modulus can be factored the decryption key is available for computation. But there is not enough information available to the attacker in the Shamir-Omura system to the interceptor to compute the key for decryption.
Here only the prime modulus is transmitted. Of course, P-1 is known, but since EA is known only to Alice, only Alice has the information from which to compute DA. Assuming that the message to be transmitted is not a dictionary word or other message which would give an indication of when the proper decryption key is found, the only way that I can see to break this system is a brute force comparison of trial decryptions of Pass 1 and Pass 3 with all possible keys. Assuming only odd keys, that means 2^31 * 2^31 tries to check all possibilities, or 2^62 decryptions. Probability is that each will be reached in half the trials, or 2^60 tries for an average level of work.
I believe (can someone prove or disprove?) that this system is a group; that when the message has been double-encrypted, there is a single key in the field of the modulus that will decrypt it. So that would reduce the work level to 2^31 tries. But if the message contains non-alphanumeric characters, such as can be produced by ALT-KEYPAD entries, knowledge of when the decryption has been completed is lacking.
I have put this system into a DOS file which I call 3PASS. The .ZIP file contains the .ASM, .COM and .LST files. There is a solicitation for the modulus which allows the use of a known modulus, or extraction of a random modulus from one of the disks mentioned above; next there is the solicitation of the direction of action; i.e., encryption or decryption. If it is encryption, a pseudo-random key is generated, and displayed for retention. If decryption, the user is asked to enter that retained key, and the inverse is computed. Next comes a solicitation of the message, which can be either in hexadecimal or ASCII format (ASCII requires a prefix of ") and the encrypted output is printed in hexadecimal and ASCII formats. I invite the cooperation of any ASM programmers out there who have an interest in this matter. You can download the file by clicking here. There is also a sample file of primes meeting the above criterion, which you can download by clicking here. A couple of primes which I have used for testing are (in hexadecimal) 8000771F and FF00FF17.
I realize that the 3PASS instructions may be a bit vague. Here is a better look at it. First, you choose your 'key' to be transmitted. This can not be more than 4 bytes, but can include 'Alt-Pad' values such as . (This character was produced by holding down ALT and typing 241 on the numeric pad). Second, you must choose a strong prime between 2^31 and 2^32 for your modulus. Or just use the one that I used for demonstration, 8000771Fh. Then just run the program taking note of 1) your modulus, and 2) your encryption key. For example:
===============
ENCRYPTION
N:\>3pass
Enter modulus or ESC for a new modulus: 8000771f
Enter E to encrypt, any other to decrypt: e
Strike any key at random
Strike any key at random
Record the random encryption key as: 0DDA1455
Enter message, [HEX] or [ASCII preceded by "] : "AbZ
The encrypted message is (in HEX): 0B338FE9 or in ASCII, 3
As you can see, the encryption key is chosen at random, and forced to
an odd number by an OR AL,1 instruction. The randomness is generated from the
time and date functions, as well as the keys struck. The ESC response to the
first message will expect one or more of the PRIMES files in your directory,
and choose a modulus from that.
DECRYPTION
N:\>3pass
Enter modulus or ESC for a new modulus: 8000771f
Enter E to encrypt, any other to decrypt: d
Enter the former encryption key (in HEX): 0dda1455
Enter message, [HEX] or [ASCII preceded by "] : 0b338fe9
The decrypted message is (in HEX): 4162F15A or in ASCII, AbZ
===========
This just shows that you can encrypt and then decrypt. To use it as a key exchange, you would encrypt and send it to me; I would encrypt with a different key but THE SAME MODULUS! So you must communicate the modulus as well as the key. I send the doubly encrypted key back to you and you decrypt. This decryption leaves it encrypted with my key only, so when I get that one back I can decrypt to get the original key that you sent me.
afn21533@afn.org afn21533@my-deja.com afn21533@yahoo.com Robert G. Durnal
-----BEGIN PGP SIGNATURE----- Version: PGP 2.6.3ia-c Charset: cp850 Comment: GET AES cipher program from www.afn.org/~afn21533/tinyaes.zip iQB1AwUBOxD3mIeSoGA2Tbg9AQEjHgL6A8m8kBbKAASeOj0o4obNaUcnqitgFBNU 9aRm/qlsUlG9cqWN7Fd50ooRjiOYQpPeVAFfP2sFHoQeVtkbXwuyuwBK0v1ywzj9 woEYT4xLcS4XmxpiuF0JmUgzJw/xxqTQ =Ka66 -----END PGP SIGNATURE-----