A 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 accepted to call a hybrid cryptosystem a way to transfer a large amount of encrypted data, in which data is encrypted with a secret key using a symmetric algorithm (for example, AES or DES), and the key itself is transmitted by an encrypted asymmetric cipher (like, say, RSA). This method is widely used for the fact that it incorporates the advantages of both symmetric and asymmetric cryptography. A large data block is encrypted with a very fast symmetric algorithm (and this eliminates the serious time costs), and the encryption key is transmitted securely encrypted using an asymmetric algorithm (and this solves the key distribution problem inherent in symmetric methods only). All this is widely known, and therefore we proceed to the most important, namely, implementation issues. And here begins a lot of interesting things.
At first glance, the most optimal solution is the combination of RSA + block cipher. However, this method is not devoid of a certain number of pitfalls.
The most obvious among them is the semantic weakness of the RSA algorithm. Therefore, it is possible to apply the RSA algorithm only using an add-on scheme, such as RSA-OAEP (which you can read about here ). Let me briefly remind you that RSA-OAEP uses two cryptographically secure hash functions as well as methods such as adding a certain number of zero bits to a message line. What makes the RSA-OAEP scheme not the most efficient from an implementation point of view, is an asymmetric algorithm. 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 a non-asymmetric cipher; nevertheless, RSA-OAEP perfectly copes with the task of checking the integrity of the received data. Now we are talking directly about the block algorithm.
I want to tell about this trouble in more detail. As is well known, all block ciphers support several modes of operation. The most widespread modes are ECB and CBC. In ECB mode, the source data is divided into blocks of M 1 , M 2 , ..., M n of a certain size. A cryptotext consists of C 1 , C 2 , ..., C n blocks, where C i = E (M i ), and E (M i ) is an encryption function applied to the M i block. Actually, the lack of such a regime immediately catches the eye. An attacker can freely replace any C i block with a C o block. So if one key is used several times while transmitting data, then the attacker may, having intercepted a new message, replace some data with older ones, and the legitimate recipient will not notice the trick.
CBC mode, according to many, is able to eliminate this lack of block ciphers, but in fact it is not. In CBC mode, encryption occurs as follows. The source data is divided into blocks of M 1 , M 2 , M n a certain size. And the cryptotext consists of blocks 1 , 2 , n , where i = E (M i ⊕ C i-1 ). With this method, the illusion is created that all ciphertext blocks are connected and replacing one block will lead to the loss of the rest. In fact, it is not. Replacing a single block will affect the decoding of only one (!) Block following it. Therefore, an attacker can successfully replace several blocks, and the legitimate recipient receiving this data and noticing that only one block was received incorrectly may well not give it a meaning.
Therefore, speaking of hybrid encryption, it is necessary to understand that the information transmitted in this way should consist not 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 the key K, data M, MAC K (M) - authentication code of the message M, obtained using the key K.
And in this regard, there is another small inconvenience associated with the use of asymmetric cryptosystems like RSA in hybrid schemes. This is redundant data. In order to send the message M, we need to add an extra line of MAC K (M) bits to the cryptotext. In addition to this, RSA, due to the large size of the encryption module (currently 2048 bits is recommended), increases the initial size of the encrypted key at times. Of course, redundancy is noncritical of only 2048 bits (considering the MAC function), but along with the implementation difficulties behind RSA-OAEP, this all gives reason to look for another method of hybrid encryption, and there is such a way. And it is 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 that Alice wants to send a message encrypted by a symmetric algorithm to Bob 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 conforms to DSA and GOST R 34.10-2001 standards (this is important because it eliminates the need to generate an additional pair of keys).
To send a message, Alice performs the following actions:
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 pair of keys (K1, K2) = H (V || U). Using the K2 key, it checks the integrity of the received cipher T = MAC K2 (C) and, if the result is correct, decrypts the text using the K1 key, M = D K1 (C).
The advantages of the DHIES scheme are the simplicity of asymmetric encryption. So, in order to obtain a securely encrypted symmetric key and transfer it, you only need two exponentiations. While using RSA-like systems, it will still be necessary to take care of the add-on schemes.
Secondly, the scheme is based on the discrete logarithm problem, and therefore it can be easily transferred to elliptic curves. The only caveat to using DHIES on elliptic curves is that calculating G x actually means finding the point x * G, and everything else remains the same. It is known that elliptic cryptography works on spaces with a much smaller size (for example, 256 bits instead of 2048). And thus, applying the EC-DHIES scheme, we get rid of excess bits (here we are, of course, not talking about saving traffic, just reducing redundancy a little is a matter of honor).
But in the third there is no need to create an additional pair of public / private key to transfer encrypted data. If the recipient uses a digital signature with the DSA or GOST R 34.10-2001 algorithm, then the public key used to verify the signature can be used to send the message.
')
And finally, a small class for performing mathematical operations on elliptic curve points, with which you can implement EC-DHIES.
Of course, everyone should choose the method that personally seems to him the most convenient, but the knowledge of one more option is never superfluous. I hope this article was useful to you and helped me to learn another method (in my opinion, optimally combining convenience and reliability) of keeping your data secret. And to apply this method or choose something else to decide, of course, only you.
So, it is accepted to call a hybrid cryptosystem a way to transfer a large amount of encrypted data, in which data is encrypted with a secret key using a symmetric algorithm (for example, AES or DES), and the key itself is transmitted by an encrypted asymmetric cipher (like, say, RSA). This method is widely used for the fact that it incorporates the advantages of both symmetric and asymmetric cryptography. A large data block is encrypted with a very fast symmetric algorithm (and this eliminates the serious time costs), and the encryption key is transmitted securely encrypted using an asymmetric algorithm (and this solves the key distribution problem inherent in symmetric methods only). All this is widely known, and therefore we proceed to the most important, namely, implementation issues. And here begins a lot of interesting things.
Little about general
At first glance, the most optimal solution is the combination of RSA + block cipher. However, this method is not devoid of a certain number of pitfalls.
The most obvious among them is the semantic weakness of the RSA algorithm. Therefore, it is possible to apply the RSA algorithm only using an add-on scheme, such as RSA-OAEP (which you can read about here ). Let me briefly remind you that RSA-OAEP uses two cryptographically secure hash functions as well as methods such as adding a certain number of zero bits to a message line. What makes the RSA-OAEP scheme not the most efficient from an implementation point of view, is an asymmetric algorithm. 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 a non-asymmetric cipher; nevertheless, RSA-OAEP perfectly copes with the task of checking the integrity of the received data. Now we are talking directly about the block algorithm.
I want to tell about this trouble in more detail. As is well known, all block ciphers support several modes of operation. The most widespread modes are ECB and CBC. In ECB mode, the source data is divided into blocks of M 1 , M 2 , ..., M n of a certain size. A cryptotext consists of C 1 , C 2 , ..., C n blocks, where C i = E (M i ), and E (M i ) is an encryption function applied to the M i block. Actually, the lack of such a regime immediately catches the eye. An attacker can freely replace any C i block with a C o block. So if one key is used several times while transmitting data, then the attacker may, having intercepted a new message, replace some data with older ones, and the legitimate recipient will not notice the trick.
CBC mode, according to many, is able to eliminate this lack of block ciphers, but in fact it is not. In CBC mode, encryption occurs as follows. The source data is divided into blocks of M 1 , M 2 , M n a certain size. And the cryptotext consists of blocks 1 , 2 , n , where i = E (M i ⊕ C i-1 ). With this method, the illusion is created that all ciphertext blocks are connected and replacing one block will lead to the loss of the rest. In fact, it is not. Replacing a single block will affect the decoding of only one (!) Block following it. Therefore, an attacker can successfully replace several blocks, and the legitimate recipient receiving this data and noticing that only one block was received incorrectly may well not give it a meaning.
Therefore, speaking of hybrid encryption, it is necessary to understand that the information transmitted in this way should consist not 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 the key K, data M, MAC K (M) - authentication code of the message M, obtained using the key K.
And in this regard, there is another small inconvenience associated with the use of asymmetric cryptosystems like RSA in hybrid schemes. This is redundant data. In order to send the message M, we need to add an extra line of MAC K (M) bits to the cryptotext. In addition to this, RSA, due to the large size of the encryption module (currently 2048 bits is recommended), increases the initial size of the encrypted key at times. Of course, redundancy is noncritical of only 2048 bits (considering the MAC function), but along with the implementation difficulties behind RSA-OAEP, this all gives reason to look for another method of hybrid encryption, and there is such a way. And it is 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 that Alice wants to send a message encrypted by a symmetric algorithm to Bob 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 conforms to DSA and GOST R 34.10-2001 standards (this is important because it eliminates the need to generate an additional pair of keys).
To send a message, Alice performs the following actions:
- Generates a random large number k.
- Calculates 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 pair of keys (K1, K2) = H (V || U). Using the K2 key, it checks the integrity of the received cipher T = MAC K2 (C) and, if the result is correct, decrypts the text using the K1 key, M = D K1 (C).
The advantages of the DHIES scheme are the simplicity of asymmetric encryption. So, in order to obtain a securely encrypted symmetric key and transfer it, you only need two exponentiations. While using RSA-like systems, it will still be necessary to take care of the add-on schemes.
Secondly, the scheme is based on the discrete logarithm problem, and therefore it can be easily transferred to elliptic curves. The only caveat to using DHIES on elliptic curves is that calculating G x actually means finding the point x * G, and everything else remains the same. It is known that elliptic cryptography works on spaces with a much smaller size (for example, 256 bits instead of 2048). And thus, applying the EC-DHIES scheme, we get rid of excess bits (here we are, of course, not talking about saving traffic, just reducing redundancy a little is a matter of honor).
But in the third there is no need to create an additional pair of public / private key to transfer encrypted data. If the recipient uses a digital signature with the DSA or GOST R 34.10-2001 algorithm, then the public key used to verify the signature can be used to send the message.
')
And quite a bit of code
And finally, a small class for performing mathematical operations on elliptic curve points, 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 = px;
y = py;
a = pa;
b = pb;
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 = pa;
p2.b = pb;
p2.FieldChar = p.FieldChar;
BigInteger dy = 3 * px * px + pa;
BigInteger dx = 2 * py;
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 - px - px) % p.FieldChar;
p2.y = (m * (px - p2.x) - py) % 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==px)||(temp.y==py))
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 the knowledge of one more option is never superfluous. I hope this article was useful to you and helped me to learn another method (in my opinion, optimally combining convenience and reliability) of keeping your data secret. And to apply this method or choose something else to decide, of course, only you.
Links
- Description of the DHIES method (pdf) .
- The BigInteger Library can be downloaded here .
- A list of recommended elliptic curves .
Source: https://habr.com/ru/post/106057/
All Articles