October 13, 2010 at 11:23A Few Words About Hybrid Encryption and Elliptic Curves
Hello dear readers. As a preface, let me remind you what hybrid cryptosystems are and why they are so widespread.
So, it is customary to call a hybrid cryptosystem a method of transmitting a large amount of encrypted data, in which the data is encrypted with a secret key using a symmetric algorithm (for example, AES or DES), and the key itself is transmitted with an encrypted asymmetric cipher (like, say, RSA). This method has become widespread because it incorporates the advantages of both symmetric and asymmetric cryptography. A large block of data is encrypted with a very fast symmetric algorithm (and this eliminates serious time costs), and the encryption key is transmitted reliably encrypted using an asymmetric algorithm (and this solves the key distribution problem that is characteristic only of symmetric methods). All this is quite widely known, and therefore we will move on to the most important thing, namely, implementation issues.
At first glance, the most optimal solution is a combination of RSA + block cipher. However, this method is not without some pitfalls.
The most obvious among them is the semantic weakness of the RSA algorithm. Therefore, the RSA algorithm can only be applied using an add-on scheme such as RSA-OAEP (which can be read about here ). I’ll briefly recall that RSA-OAEP uses two cryptographically strong hash functions as well as methods such as adding a certain number of zero bits to a message line. Which makes the RSA-OAEP scheme not the most efficient asymmetric algorithm in terms of implementation. Because of this limitation, the use of RSA as the simplest option loses all its appeal.
Another disadvantage of sharing RSA and block cipher is the lack of integrity control of the transmitted data. And this is already a stone in the garden of an asymmetric cipher; nevertheless, RSA-OAEP copes with the task of checking the integrity of the received data. Now we are talking directly about the block algorithm.
I want to talk more about this trouble. As you know, all block ciphers support several modes of operation. The most common modes were ECB and CBC. In ECB mode, the source data is divided into blocks M 1 , M 2 , ..., M n of a certain size. And cryptotext consists of blocks C 1 , C 2 , ..., C n , where C i = E (Mi ), and E (M i ) is the encryption function applied to the block M i . Actually, the disadvantage of such a regime is immediately evident. An attacker can freely replace any block C i with block C o . T.O. if during data transmission one key is used several times, then the attacker may intercept a new message and replace some data with older ones, and the legitimate recipient will not notice a catch.
CBC mode, according to many, is able to eliminate this drawback of block ciphers, but in fact it is not. In CBC mode, encryption is as follows. The source data is divided into blocks M 1 , M 2 , M na certain size. And cryptotext consists of blocks C 1 , C 2 , C n , where C i = E (M i ⊕ C i-1 ). With this method, the illusion is created that all ciphertext blocks are connected and the replacement of one block will lead to the loss of the rest. This is actually not the case. Replacing a single block will affect the decryption of only one (!) Block following it. Therefore, an attacker can successfully replace several blocks, and the legitimate recipient, having received this data and noticing that only one block is received incorrectly, may not attach any importance to this.
Therefore, speaking about hybrid encryption, it is necessary to understand that the information transmitted in this way should not consist of two blocks, but of three E asy (K) || E sym (M) || MAC K (M), where E asy (K) -key encrypted with an asymmetric algorithm, E sym (M) -encrypted with a symmetric algorithm, using key K, data M, MAC K (M) is an authentication code for message M received using key K.
And in this connection, another small the inconvenience of using an asymmetric cryptosystem like RSA in hybrid circuits. This is redundant data. To send message M, we need to add an extra string of MAC K bits to crypto text(M). And besides this, RSA also, due to the large size of the encryption module (2048 bits are currently recommended), increases the original size of the encrypted key by several times. Of course, redundancy is uncritical of only 2048 bits (taking into account the MAC function), but along with the implementation difficulties behind RSA-OAEP, this all gives reason to look for another hybrid encryption method, and there is such a method. And it's called DHIES.
The DHIES Hybrid Encryption Scheme (Diffie-Hellman Integrated Encryption Scheme) was proposed by three authors Michel Abdalla, Mihir Bellare and Phillip Rogaway in 2001. The idea underlying the scheme is based on the difficulty of solving the discrete logarithm problem. The encryption scheme itself is as follows.
Suppose Alice wants to send Bob a message encrypted with a symmetric algorithm and a key to this message. Let Bob have a public / private key pair (x, G, P, Y = G x mod P), where G, P, Y are public data and Bob's x-secret key. Those. Bob's key set complies with DSA and GOST R 34.10-2001 standards (this is important because it eliminates the need to generate an additional key pair).
To send a message, Alice does the following:
After receiving a message from Alice, Bob using his secret key x, can calculate V = U x . Knowing V and U, Bob is able to get a key pair (K1, K2) = H (V || U). Using the key K2, he checks the integrity of the received cipher T = MAC K2 (C) and, if the result is correct, decrypts the text using the key K1, M = D K1 (C).
An advantage of the DHIES scheme is the ease of implementation of asymmetric encryption. So, to get a securely encrypted symmetric key and pass it, you need only two exponents. While using RSA-like systems it will still be necessary to take care of supplement schemes.
Secondly, the scheme is based on the discrete logarithm problem, and therefore it can easily be transferred to elliptic curves. The only nuance of using DHIES on elliptic curves is that calculating G x actually means finding the point x * G, but everything else remains the same. Elliptic cryptography is known to work on spaces with a much smaller size (for example, 256 bits instead of 2048). And thus, using the EC-DHIES scheme, we get rid of redundant bits (here, of course, we are not talking about saving traffic, just reducing redundancy a bit is a matter of honor).
Well, thirdly, there is no need to create an additional public / private key pair for encrypted data transmission. If the recipient uses a digital signature with the DSA algorithm or GOST R 34.10-2001, then you can use the public key used to verify the signature to send the message.
And finally, a small class for performing mathematical operations on points of elliptic curves, with which you can implement EC-DHIES.
Of course, everyone should choose the method that personally seems to him the most convenient, but knowledge of another option is never superfluous. I hope this article was useful to you and helped to find out another method (in my opinion the best combination of convenience and reliability) of keeping your data a secret. And to apply this method or choose something else is up to you to decide.
So, it is customary to call a hybrid cryptosystem a method of transmitting a large amount of encrypted data, in which the data is encrypted with a secret key using a symmetric algorithm (for example, AES or DES), and the key itself is transmitted with an encrypted asymmetric cipher (like, say, RSA). This method has become widespread because it incorporates the advantages of both symmetric and asymmetric cryptography. A large block of data is encrypted with a very fast symmetric algorithm (and this eliminates serious time costs), and the encryption key is transmitted reliably encrypted using an asymmetric algorithm (and this solves the key distribution problem that is characteristic only of symmetric methods). All this is quite widely known, and therefore we will move on to the most important thing, namely, implementation issues.
A little bit about the general
At first glance, the most optimal solution is a combination of RSA + block cipher. However, this method is not without some pitfalls.
The most obvious among them is the semantic weakness of the RSA algorithm. Therefore, the RSA algorithm can only be applied using an add-on scheme such as RSA-OAEP (which can be read about here ). I’ll briefly recall that RSA-OAEP uses two cryptographically strong hash functions as well as methods such as adding a certain number of zero bits to a message line. Which makes the RSA-OAEP scheme not the most efficient asymmetric algorithm in terms of implementation. Because of this limitation, the use of RSA as the simplest option loses all its appeal.
Another disadvantage of sharing RSA and block cipher is the lack of integrity control of the transmitted data. And this is already a stone in the garden of an asymmetric cipher; nevertheless, RSA-OAEP copes with the task of checking the integrity of the received data. Now we are talking directly about the block algorithm.
I want to talk more about this trouble. As you know, all block ciphers support several modes of operation. The most common modes were ECB and CBC. In ECB mode, the source data is divided into blocks M 1 , M 2 , ..., M n of a certain size. And cryptotext consists of blocks C 1 , C 2 , ..., C n , where C i = E (Mi ), and E (M i ) is the encryption function applied to the block M i . Actually, the disadvantage of such a regime is immediately evident. An attacker can freely replace any block C i with block C o . T.O. if during data transmission one key is used several times, then the attacker may intercept a new message and replace some data with older ones, and the legitimate recipient will not notice a catch.
CBC mode, according to many, is able to eliminate this drawback of block ciphers, but in fact it is not. In CBC mode, encryption is as follows. The source data is divided into blocks M 1 , M 2 , M na certain size. And cryptotext consists of blocks C 1 , C 2 , C n , where C i = E (M i ⊕ C i-1 ). With this method, the illusion is created that all ciphertext blocks are connected and the replacement of one block will lead to the loss of the rest. This is actually not the case. Replacing a single block will affect the decryption of only one (!) Block following it. Therefore, an attacker can successfully replace several blocks, and the legitimate recipient, having received this data and noticing that only one block is received incorrectly, may not attach any importance to this.
Therefore, speaking about hybrid encryption, it is necessary to understand that the information transmitted in this way should not consist of two blocks, but of three E asy (K) || E sym (M) || MAC K (M), where E asy (K) -key encrypted with an asymmetric algorithm, E sym (M) -encrypted with a symmetric algorithm, using key K, data M, MAC K (M) is an authentication code for message M received using key K.
And in this connection, another small the inconvenience of using an asymmetric cryptosystem like RSA in hybrid circuits. This is redundant data. To send message M, we need to add an extra string of MAC K bits to crypto text(M). And besides this, RSA also, due to the large size of the encryption module (2048 bits are currently recommended), increases the original size of the encrypted key by several times. Of course, redundancy is uncritical of only 2048 bits (taking into account the MAC function), but along with the implementation difficulties behind RSA-OAEP, this all gives reason to look for another hybrid encryption method, and there is such a method. And it's called DHIES.
Briefly about the main thing
The DHIES Hybrid Encryption Scheme (Diffie-Hellman Integrated Encryption Scheme) was proposed by three authors Michel Abdalla, Mihir Bellare and Phillip Rogaway in 2001. The idea underlying the scheme is based on the difficulty of solving the discrete logarithm problem. The encryption scheme itself is as follows.
Suppose Alice wants to send Bob a message encrypted with a symmetric algorithm and a key to this message. Let Bob have a public / private key pair (x, G, P, Y = G x mod P), where G, P, Y are public data and Bob's x-secret key. Those. Bob's key set complies with DSA and GOST R 34.10-2001 standards (this is important because it eliminates the need to generate an additional key pair).
To send a message, Alice does the following:
- Generates a random large number k.
- Computes U = G k and V = Y k = G kx .
- Defines a pair (K1, K2) = H (V || U), where H () is a cryptographically strong hash function.
- Finds C = E K1 (M) and T = MAC K2 (C)
- Sends Bob a message of the form U || C || T.
After receiving a message from Alice, Bob using his secret key x, can calculate V = U x . Knowing V and U, Bob is able to get a key pair (K1, K2) = H (V || U). Using the key K2, he checks the integrity of the received cipher T = MAC K2 (C) and, if the result is correct, decrypts the text using the key K1, M = D K1 (C).
An advantage of the DHIES scheme is the ease of implementation of asymmetric encryption. So, to get a securely encrypted symmetric key and pass it, you need only two exponents. While using RSA-like systems it will still be necessary to take care of supplement schemes.
Secondly, the scheme is based on the discrete logarithm problem, and therefore it can easily be transferred to elliptic curves. The only nuance of using DHIES on elliptic curves is that calculating G x actually means finding the point x * G, but everything else remains the same. Elliptic cryptography is known to work on spaces with a much smaller size (for example, 256 bits instead of 2048). And thus, using the EC-DHIES scheme, we get rid of redundant bits (here, of course, we are not talking about saving traffic, just reducing redundancy a bit is a matter of honor).
Well, thirdly, there is no need to create an additional public / private key pair for encrypted data transmission. If the recipient uses a digital signature with the DSA algorithm or GOST R 34.10-2001, then you can use the public key used to verify the signature to send the message.
And just a little bit of code
And finally, a small class for performing mathematical operations on points of elliptic curves, with which you can implement EC-DHIES.
//класс для умножения точек эллиптической кривой
public class ECPoint
{
public BigInteger x;
public BigInteger y;
public BigInteger a;
public BigInteger b;
public BigInteger FieldChar;
public ECPoint(ECPoint p)
{
x = p.x;
y = p.y;
a = p.a;
b = p.b;
FieldChar = p.FieldChar;
}
public ECPoint()
{
x = new BigInteger();
y = new BigInteger();
a = new BigInteger();
b = new BigInteger();
FieldChar = new BigInteger();
}
//сложение двух точек P1 и P2
public static ECPoint operator +(ECPoint p1, ECPoint p2)
{
ECPoint p3 = new ECPoint();
p3.a = p1.a;
p3.b = p1.b;
p3.FieldChar = p1.FieldChar;
BigInteger dy = p2.y - p1.y;
BigInteger dx = p2.x - p1.x;
if (dx < 0)
dx += p1.FieldChar;
if (dy < 0)
dy += p1.FieldChar;
BigInteger m = (dy * dx.modInverse(p1.FieldChar)) % p1.FieldChar;
if (m < 0)
m += p1.FieldChar;
p3.x = (m * m - p1.x - p2.x) % p1.FieldChar;
p3.y = (m * (p1.x - p3.x) - p1.y) % p1.FieldChar;
if (p3.x < 0)
p3.x += p1.FieldChar;
if (p3.y < 0)
p3.y += p1.FieldChar;
return p3;
}
//сложение точки P c собой же
public static ECPoint Double(ECPoint p)
{
ECPoint p2 = new ECPoint();
p2.a = p.a;
p2.b = p.b;
p2.FieldChar = p.FieldChar;
BigInteger dy = 3 * p.x * p.x + p.a;
BigInteger dx = 2 * p.y;
if (dx < 0)
dx += p.FieldChar;
if (dy < 0)
dy += p.FieldChar;
BigInteger m = (dy * dx.modInverse(p.FieldChar)) % p.FieldChar;
p2.x = (m * m - p.x - p.x) % p.FieldChar;
p2.y = (m * (p.x - p2.x) - p.y) % p.FieldChar;
if (p2.x < 0)
p2.x += p.FieldChar;
if (p2.y < 0)
p2.y += p.FieldChar;
return p2;
}
//умножение точки на число x, по сути своей представляет x сложений точки самой с собой
public static ECPoint multiply(BigInteger x, ECPoint p)
{
ECPoint temp = p;
while (x != 0)
{
if ((x % 2) != 0)
{
if((temp.x==p.x)||(temp.y==p.y))
temp=Double(temp);
else
temp = temp + p;
x = x - 1;
}
x = x / 2;
p = Double(p);
}
return temp;
}
}
* This source code was highlighted with Source Code Highlighter.Conclusion
Of course, everyone should choose the method that personally seems to him the most convenient, but knowledge of another option is never superfluous. I hope this article was useful to you and helped to find out another method (in my opinion the best combination of convenience and reliability) of keeping your data a secret. And to apply this method or choose something else is up to you to decide.
References
- Description of the DHIES method (pdf) .
- The BigInteger library can be downloaded here .
- List of recommended elliptical curves .