Three-pass protocol
Encyclopedia
In cryptography
, the three-pass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute encryption keys
. This message protocol should not be confused with various other algorithms which use 3 passes for authentication
.
It is called the three-pass protocol because the sender and the receiver exchange three encrypted messages. The first three-pass protocol was developed by Adi Shamir
circa 1980, and is described in more detail in a later section. The basic concept of the Three-Pass Protocol is that each party has a private encryption key and a private decryption key. The two parties use their keys independently, first to encrypt the message, and then to decrypt the message.
The protocol uses an encryption function
E and a decryption function D. The encryption function uses an encryption key e to change a plaintext
message m into an encrypted message, or ciphertext
, E(e,m). Corresponding to each encryption key e there is a decryption key d which allows the message to be recovered using the decryption function, D(d,E(e,m))=m. Sometimes the encryption function and decryption function are the same.
In order for the encryption function and decryption function to be suitable for the Three-Pass Protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, D(d,E(k,E(e,m))) = E(k,m). In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is order-independent, i.e. it satisfies E(a,E(b,m))=E(b,E(a,m)) for all encryption keys a and b and all messages m. Commutative encryptions satisfy D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).
The Three-Pass Protocol works as follows:
The receiver can now decrypt the message using the key q, namely D(q,E(r,m))=m the original message.
Notice that all of the operations involving the sender's private keys s and t are performed by the sender, and all of the operations involving the receiver's private keys r and q are performed by the receiver, so that neither party needs to know the other party's keys.
Three-Pass Protocol developed circa 1980. It is also called the Shamir No-Key Protocol because the sender and the receiver do not exchange any keys, however the protocol requires the sender and receiver to have two private keys for encrypting and decrypting messages. The Shamir algorithm uses exponentiation
modulo a large prime
as both the encryption and decryption functions. That is E(e,m) = me mod p and D(d,m) = md mod p where p is a large prime. For any encryption exponent e in the range 1..p-1 with gcd(e,p-1) = 1. The corresponding decryption exponent d is chosen such that de ≡ 1 (mod p-1). It follows from Fermat's Little Theorem
that D(d,E(e,m)) = mde mod p = m.
The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = mab mod p = mba mod p = E(b,E(a,m)).
and Jim K. Omura
in 1982 as a possible improvement over the Shamir protocol. The Massey-Omura method uses exponentiation
in the Galois field
GF(2n) as both the encryption and decryption functions. That is E(e,m)=me and D(d,m)=md where the calculations are carried out in the Galois field. For any encryption exponent e with 0<e<2n-1 and gcd(e,2n-1)=1 the corresponding decryption exponent is d such that de ≡ 1 (mod 2n-1). Since the multiplicative group of the Galois field GF(2n) has order 2n-1 Lagrange's theorem
implies that mde=m for all m in GF(2n)* .
Each element of the Galois field GF(2n) is represented as a binary
vector over a normal basis
in which each basis vector is the square of the preceding one. That is, the basis vectors are v1, v2, v4, v8, ... where v is a field element of maximum order
. By using this representation, exponentiations by powers of 2 can be accomplished by cyclic shifts
. This means that raising m to an arbitrary power can be accomplished with at most n shifts and n multiplications. Moreover, several multiplications can be performed in parallel. This allows faster hardware realizations at the cost of having to implement several multipliers.
For the encryption functions used in the Shamir algorithm and the Massey-Omura algorithm described above, the security relies on the difficulty of computing discrete logarithms
in a finite field. If an attacker could compute discrete logarithms in GF(p) for the Shamir method or GF(2n) for the Massey-Omura method then the protocol could be broken. The key s could be computed from the messages mr and mrs. When s is known, it is easy to compute the decryption exponent t. Then the attacker could compute m by raising the intercepted message ms to the t power. K. Sakurai and H. Shizuya show that under certain assumptions breaking Massey-Omura cryptosystem is equivalent to the Diffie-Hellman assumption.
. Hence, without any additional authentication the protocol is susceptible to a man-in-the-middle attack
if the opponent has the ability to create false messages, or to intercept and replace the genuine transmitted messages.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the three-pass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute encryption keys
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
. This message protocol should not be confused with various other algorithms which use 3 passes for authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
.
It is called the three-pass protocol because the sender and the receiver exchange three encrypted messages. The first three-pass protocol was developed by Adi Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
circa 1980, and is described in more detail in a later section. The basic concept of the Three-Pass Protocol is that each party has a private encryption key and a private decryption key. The two parties use their keys independently, first to encrypt the message, and then to decrypt the message.
The protocol uses an encryption function
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
E and a decryption function D. The encryption function uses an encryption key e to change a plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
message m into an encrypted message, or ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
, E(e,m). Corresponding to each encryption key e there is a decryption key d which allows the message to be recovered using the decryption function, D(d,E(e,m))=m. Sometimes the encryption function and decryption function are the same.
In order for the encryption function and decryption function to be suitable for the Three-Pass Protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, D(d,E(k,E(e,m))) = E(k,m). In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is order-independent, i.e. it satisfies E(a,E(b,m))=E(b,E(a,m)) for all encryption keys a and b and all messages m. Commutative encryptions satisfy D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).
The Three-Pass Protocol works as follows:
- The sender chooses a private encryption key s and a corresponding decryption key t. The sender encrypts the message m with the key s and sends the encrypted message E(s,m) to the receiver.
- The receiver chooses a private encryption key r and a corresponding decryption key q and super-encryptsSuperencryptionMultiple encryption is the process of encrypting an already encrypted message one or more times, either using the same or a different algorithm. The terms cascade encryption, cascade ciphering, multiple encryption, multiple ciphering, and superencipherment are used with the same meaning...
the first message E(s,m) with the key r and sends the doubly encrypted message E(r,E(s,m)) back to the sender. - The sender decrypts the second message with the key t. Because of the commutativity property described above D(t,E(r,E(s,m)))=E(r,m) which is the message encrypted with only the receiver's private key. The sender sends this to the receiver.
The receiver can now decrypt the message using the key q, namely D(q,E(r,m))=m the original message.
Notice that all of the operations involving the sender's private keys s and t are performed by the sender, and all of the operations involving the receiver's private keys r and q are performed by the receiver, so that neither party needs to know the other party's keys.
Shamir three-pass protocol
The first Three-Pass Protocol was the ShamirAdi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
Three-Pass Protocol developed circa 1980. It is also called the Shamir No-Key Protocol because the sender and the receiver do not exchange any keys, however the protocol requires the sender and receiver to have two private keys for encrypting and decrypting messages. The Shamir algorithm uses exponentiation
Exponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
modulo a large prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
as both the encryption and decryption functions. That is E(e,m) = me mod p and D(d,m) = md mod p where p is a large prime. For any encryption exponent e in the range 1..p-1 with gcd(e,p-1) = 1. The corresponding decryption exponent d is chosen such that de ≡ 1 (mod p-1). It follows from Fermat's Little Theorem
Fermat's little theorem
Fermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
that D(d,E(e,m)) = mde mod p = m.
The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = mab mod p = mba mod p = E(b,E(a,m)).
Massey-Omura cryptosystem
The Massey-Omura Cryptosystem was proposed by James MasseyJames Massey
James Lee Massey is an information theorist andcryptographer, Professor Emeritus of Digital Technology at ETH Zurich. His notable work...
and Jim K. Omura
Jim K. Omura
James K. Omura is an electrical engineer and information theorist, currently the technology strategist for the Gordon and Betty Moore Foundation....
in 1982 as a possible improvement over the Shamir protocol. The Massey-Omura method uses exponentiation
Exponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
in the Galois field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
GF(2n) as both the encryption and decryption functions. That is E(e,m)=me and D(d,m)=md where the calculations are carried out in the Galois field. For any encryption exponent e with 0<e<2n-1 and gcd(e,2n-1)=1 the corresponding decryption exponent is d such that de ≡ 1 (mod 2n-1). Since the multiplicative group of the Galois field GF(2n) has order 2n-1 Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
implies that mde=m for all m in GF(2n)* .
Each element of the Galois field GF(2n) is represented as a binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
vector over a normal basis
Normal basis
In mathematics, a normal basis in field theory is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis...
in which each basis vector is the square of the preceding one. That is, the basis vectors are v1, v2, v4, v8, ... where v is a field element of maximum order
Order (group theory)
In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....
. By using this representation, exponentiations by powers of 2 can be accomplished by cyclic shifts
Circular shift
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation...
. This means that raising m to an arbitrary power can be accomplished with at most n shifts and n multiplications. Moreover, several multiplications can be performed in parallel. This allows faster hardware realizations at the cost of having to implement several multipliers.
Security
A necessary condition for a three-pass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages E(s,m), E(r,E(s,m)) and E(r,m).For the encryption functions used in the Shamir algorithm and the Massey-Omura algorithm described above, the security relies on the difficulty of computing discrete logarithms
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
in a finite field. If an attacker could compute discrete logarithms in GF(p) for the Shamir method or GF(2n) for the Massey-Omura method then the protocol could be broken. The key s could be computed from the messages mr and mrs. When s is known, it is easy to compute the decryption exponent t. Then the attacker could compute m by raising the intercepted message ms to the t power. K. Sakurai and H. Shizuya show that under certain assumptions breaking Massey-Omura cryptosystem is equivalent to the Diffie-Hellman assumption.
Authentication
The three-pass protocol as described above does not provide any authenticationAuthentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
. Hence, without any additional authentication the protocol is susceptible to a man-in-the-middle attack
Man-in-the-middle attack
In cryptography, the man-in-the-middle attack , bucket-brigade attack, or sometimes Janus attack, is a form of active eavesdropping in which the attacker makes independent connections with the victims and relays messages between them, making them believe that they are talking directly to each other...
if the opponent has the ability to create false messages, or to intercept and replace the genuine transmitted messages.