Implementing Elliptic curve Menezes-Vanstone cryptosystem based on the OpenSSL API
Hello, dear habrovchane! As I was able to do cryptography for my modest needs, trying to maintain a decent level of data security (I am guided by the levels specified in the ecrypt section here ), I began to be disturbed by a drop in performance when using the RSA cryptographic algorithm.
Unfortunately, this algorithm turned out to be the only one in openssl, which allows encryption / decryption of small data blocks (assumed in the sense of the article - keys for symmetric encryption algorithms) using asymmetric cryptographic algorithms.
Walking around the internet, we found out that:
')
1. El-Gamal can successfully encrypt / decrypt, but these operations are not implemented in openssl (there is an implementation in libgcrypt). In terms of speed, El-Gamal is 3 times faster than RSA
with the same key length and the same cryptographic resistance for 1 key bit.
2. The Elliptic Curve cryptosystem (ECC) was pleasantly surprised by the speed and cryptoresistance of 1 bit of the key, but encryption / decryption operations based on ECC are not implemented in openssl.
The implementation of ECC encryption in libgcrypt is, but very specific. In short, the encrypted message m is mapped to a point on the elliptic curve mG, from which the original message m cannot be received otherwise than by breaking ECC or by enumerating all possible values ​​of m.
3. In the literature [1] described Menezes-Vanstone ECC, but there are notifications about its "vulnerability" [2]
Let us examine this question in more detail.
For simplicity, we will only speak about elliptic curves, whose form is described by the Weierstrass equation over the fields of integers defined as Zp, where Zp is the set of integers less than a certain prime number p and greater than zero.
Then E (p, a, b) - where a, b belong to Zp - an elliptic curve over the field Zp, defined by a prime number p and numbers a, b. Next, you need to define an abstract zero element O (if the coefficient of the Weierstrass equation b is not equal to 0, then you can take the coordinates x = 0, y = 0 as the conditional point O, even if this point is not a solution of the equation) and the operation of adding the curve elements (points) which will give a new point belonging to the same curve.
Naturally, it should turn out that P + Q = Q + P, (P + Q) + R = P + (Q + R), P + O = O + P = P and if there is P (x, y), that is, -P = (x, -y) and P + (- P) = PP = O.
These are all mathematical operations that are defined for a group of points of an elliptic curve.
In the literature [1] one can find mathematical details on how these operations are determined.
You can add different points (P = G + Q) or a point with you (P = Q + Q). The fact that we will speak about “multiplication” is just a way to shorten the record, and not to write P = Q + Q + Q + Q + ... + Q m times, but simply write that P = mQ. In fact, there is no operation “multiplication” and, accordingly, “division”, as well as no “exponentiation” and “taking the logarithm”.
This terminology is often used, but for elliptic curves it means not what is usually meant by this. Summing a point on an elliptic curve with itself m times can be called “multiplication by m” or even “raising to a power of m”. The essence of this does not change, and since the inverse operation, “dividing” or “taking the logarithm” does not exist, getting m from the point m * G, even knowing G is impossible, speaks of the “problem of the discrete logarithm on elliptic curves”. Such is the well-established terminology.
On this curve, we choose (arbitrary) point G (Gx, Gy) which is a generator of a group of points, that is, by specifying different m, we get the result of multiplication mG, which forms a cyclic group of points (since we are in a finite field Zp). The size of this cyclic group is called the order of the generator point G.
Thus, the elliptic group is completely described by the parameters of the curve E (p, a, b), the generator point G (Gx, Gy), and the order of the group ord, and ord * G = O. These are all called elliptic curve parameters, which are usually well-known, and are identified by names, for example secp192k1 or prime256v1.
The user's private key is (secret, random) number 1 <d <ord-1
The public key of the user is the point Q, which is the product of the private key d and the generator of the group G, Q = dG.
Sender side:
1. The encrypted message m is divided into two parts x1 and x2, each of which must be an element of the Zp field, for this it is enough to check their length and compare it with the length of the curve parameter p.
2. The sender chooses (secret, random) number 1 <ks <ord-1.
3. The sender multiplies the generator point G by the number ks, y0 = ks * G
4. The sender calculates the point Z (Zx, Zy), multiplying the recipient's public key Q by the number ks, Z = ks * Q
5. The sender calculates y1 = x1 * Zx (mod p), y2 = x2 * Zy (mod p)
Computational costs of the sender: generation of a random number of the required length, 2 operations of multiplying a point by a number, 2 operations of multiplying modulo p.
The ciphertext is the point y0, the number y1, the number y2. Point contains 2 numbers - x, y coordinates. The total amount of ciphertext is approximately 4 * p, for an ECC key with a length of 192 bits (24 bytes) is approximately 24 * 4 = 96 bytes.
Recipient's side:
1. The recipient checks whether the point y0 belongs to the curve defined by the parameters E (p, a, b), G, ord.
2. The recipient calculates the point Z, multiplying the ciphertext y0 by its private key d, Z = d * y0 = d * ks * G = ks * d * G = ks * Q.
3. The recipient calculates the multiplicative inversion of the components Z (Zx, Zy), e1 = inv (Zx) (mod p), e2 = inv (Zy) (mod p).
4. The receiver recovers x1, x2: x1 = y1 * e1 (mod p), x2 = y2 * e2 (mod p).
Computational costs of the recipient: verification of the point to curve, 1 operation of multiplying a point by a number, 2 operations of calculating the multiplicative inversion modulo p,
2 multiplication operations modulo p.
In 1997, Klaus Kiefer [2] showed that MVC is not a system that uses probabilistic encryption, despite its design. Knowing the ciphertext, knowing the parameters of the curve, it is possible to carry out a "known plaintext attack" (an attack with guessing plaintext).
What it looks like:
The parameters of the curve E (p, a, b), G, ord are known. Known ciphertext y0, y1, y2. We assume that the plaintext is x1, x2.
If the point F (f1, f2) f1 = y1 * (inv (x1)) (mod p), f2 = y2 * (inv (x2)) (mod p) belongs to the curve E (p, a, b), then with the probability of error 1 / p x1, x2 is really the desired plaintext.
What does this mean in practice?
The fact that it is possible to arrange the enumeration of all values ​​x1, x2 with computational cost 2 operations of calculating the multiplicative inversion modulo p, 2 multiplication operations modulo p for each variant x1, x2 and with the probability of error 1 / p find the plaintext corresponding to the encrypted one. A negative test result is always true, a positive one may contain erroneous recognition with a probability of 1 / p. The iteration operation x1, x2 is well distributed, many processes can independently iterate over their non-overlapping ranges of values ​​x1, x2.
For reference: I would like to look at the enumeration (just enumeration, without calculations) of all possible key values ​​of 192 or 256 bits. Yes, even 128-168 bits.
It is clear that the search can only open small pieces of encrypted data, up to 48-64 bits. And this brute force can be arranged without MVC, for the task of finding the key by enumerating all possible values, the use of MVC is not necessary, it is an extra entity.
If you encrypt large enough (128 bit or more) texts, which exclude the possibility of finding them in a reasonable time and reasonable costs to find them through the search, this “vulnerability” does not play any role.
Today, the minimum recommended ECC key length is 192 bits (24 bytes). The length of the encrypted MVC data in this case should not exceed 2 * 24 = 48 bytes, and the strongest AES or GOST key has a length of 256 bits (32 bytes).
But we get crypto-resistant and fairly fast (in my estimation, ECC-224 is 5 times faster than RSA-2048, 3 times faster than ElGamal-2048) asymmetric encryption algorithm.
I believe that the Elliptic curve Menezes-Vanstone cryptosystem is completely undeservedly forgotten.
Trying to fill this gap, I spread the source code in C using the openssl API.
Literature:
1. COMPUTER SECURITY AND CRYPTOGRAPHY, ALAN G. KONHEIM, Published by John Wiley & Sons, Inc., Hoboken, New Jersey, 2007. ISBN-13: 978-0-471-94783-7 ISBN-10: 0-471- 94783-0
2. “A Weakness of Menezes-Vanstone Cryptosystem” , Klaus Kiefer, member of the research group of prof. J. Buchmann, 1997
Thanks for attention!
Unfortunately, this algorithm turned out to be the only one in openssl, which allows encryption / decryption of small data blocks (assumed in the sense of the article - keys for symmetric encryption algorithms) using asymmetric cryptographic algorithms.
Walking around the internet, we found out that:
')
1. El-Gamal can successfully encrypt / decrypt, but these operations are not implemented in openssl (there is an implementation in libgcrypt). In terms of speed, El-Gamal is 3 times faster than RSA
with the same key length and the same cryptographic resistance for 1 key bit.
2. The Elliptic Curve cryptosystem (ECC) was pleasantly surprised by the speed and cryptoresistance of 1 bit of the key, but encryption / decryption operations based on ECC are not implemented in openssl.
The implementation of ECC encryption in libgcrypt is, but very specific. In short, the encrypted message m is mapped to a point on the elliptic curve mG, from which the original message m cannot be received otherwise than by breaking ECC or by enumerating all possible values ​​of m.
3. In the literature [1] described Menezes-Vanstone ECC, but there are notifications about its "vulnerability" [2]
Let us examine this question in more detail.
A bit of math:
For simplicity, we will only speak about elliptic curves, whose form is described by the Weierstrass equation over the fields of integers defined as Zp, where Zp is the set of integers less than a certain prime number p and greater than zero.
Then E (p, a, b) - where a, b belong to Zp - an elliptic curve over the field Zp, defined by a prime number p and numbers a, b. Next, you need to define an abstract zero element O (if the coefficient of the Weierstrass equation b is not equal to 0, then you can take the coordinates x = 0, y = 0 as the conditional point O, even if this point is not a solution of the equation) and the operation of adding the curve elements (points) which will give a new point belonging to the same curve.
Naturally, it should turn out that P + Q = Q + P, (P + Q) + R = P + (Q + R), P + O = O + P = P and if there is P (x, y), that is, -P = (x, -y) and P + (- P) = PP = O.
These are all mathematical operations that are defined for a group of points of an elliptic curve.
In the literature [1] one can find mathematical details on how these operations are determined.
You can add different points (P = G + Q) or a point with you (P = Q + Q). The fact that we will speak about “multiplication” is just a way to shorten the record, and not to write P = Q + Q + Q + Q + ... + Q m times, but simply write that P = mQ. In fact, there is no operation “multiplication” and, accordingly, “division”, as well as no “exponentiation” and “taking the logarithm”.
This terminology is often used, but for elliptic curves it means not what is usually meant by this. Summing a point on an elliptic curve with itself m times can be called “multiplication by m” or even “raising to a power of m”. The essence of this does not change, and since the inverse operation, “dividing” or “taking the logarithm” does not exist, getting m from the point m * G, even knowing G is impossible, speaks of the “problem of the discrete logarithm on elliptic curves”. Such is the well-established terminology.
On this curve, we choose (arbitrary) point G (Gx, Gy) which is a generator of a group of points, that is, by specifying different m, we get the result of multiplication mG, which forms a cyclic group of points (since we are in a finite field Zp). The size of this cyclic group is called the order of the generator point G.
Thus, the elliptic group is completely described by the parameters of the curve E (p, a, b), the generator point G (Gx, Gy), and the order of the group ord, and ord * G = O. These are all called elliptic curve parameters, which are usually well-known, and are identified by names, for example secp192k1 or prime256v1.
The user's private key is (secret, random) number 1 <d <ord-1
The public key of the user is the point Q, which is the product of the private key d and the generator of the group G, Q = dG.
What does Elliptic curve Menezes-Vanstone cryptosystem [1] (MVC) offer?
Sender side:
1. The encrypted message m is divided into two parts x1 and x2, each of which must be an element of the Zp field, for this it is enough to check their length and compare it with the length of the curve parameter p.
2. The sender chooses (secret, random) number 1 <ks <ord-1.
3. The sender multiplies the generator point G by the number ks, y0 = ks * G
4. The sender calculates the point Z (Zx, Zy), multiplying the recipient's public key Q by the number ks, Z = ks * Q
5. The sender calculates y1 = x1 * Zx (mod p), y2 = x2 * Zy (mod p)
Computational costs of the sender: generation of a random number of the required length, 2 operations of multiplying a point by a number, 2 operations of multiplying modulo p.
The ciphertext is the point y0, the number y1, the number y2. Point contains 2 numbers - x, y coordinates. The total amount of ciphertext is approximately 4 * p, for an ECC key with a length of 192 bits (24 bytes) is approximately 24 * 4 = 96 bytes.
Recipient's side:
1. The recipient checks whether the point y0 belongs to the curve defined by the parameters E (p, a, b), G, ord.
2. The recipient calculates the point Z, multiplying the ciphertext y0 by its private key d, Z = d * y0 = d * ks * G = ks * d * G = ks * Q.
3. The recipient calculates the multiplicative inversion of the components Z (Zx, Zy), e1 = inv (Zx) (mod p), e2 = inv (Zy) (mod p).
4. The receiver recovers x1, x2: x1 = y1 * e1 (mod p), x2 = y2 * e2 (mod p).
Computational costs of the recipient: verification of the point to curve, 1 operation of multiplying a point by a number, 2 operations of calculating the multiplicative inversion modulo p,
2 multiplication operations modulo p.
MVC vulnerability or weakness
In 1997, Klaus Kiefer [2] showed that MVC is not a system that uses probabilistic encryption, despite its design. Knowing the ciphertext, knowing the parameters of the curve, it is possible to carry out a "known plaintext attack" (an attack with guessing plaintext).
What it looks like:
The parameters of the curve E (p, a, b), G, ord are known. Known ciphertext y0, y1, y2. We assume that the plaintext is x1, x2.
If the point F (f1, f2) f1 = y1 * (inv (x1)) (mod p), f2 = y2 * (inv (x2)) (mod p) belongs to the curve E (p, a, b), then with the probability of error 1 / p x1, x2 is really the desired plaintext.
What does this mean in practice?
The fact that it is possible to arrange the enumeration of all values ​​x1, x2 with computational cost 2 operations of calculating the multiplicative inversion modulo p, 2 multiplication operations modulo p for each variant x1, x2 and with the probability of error 1 / p find the plaintext corresponding to the encrypted one. A negative test result is always true, a positive one may contain erroneous recognition with a probability of 1 / p. The iteration operation x1, x2 is well distributed, many processes can independently iterate over their non-overlapping ranges of values ​​x1, x2.
For reference: I would like to look at the enumeration (just enumeration, without calculations) of all possible key values ​​of 192 or 256 bits. Yes, even 128-168 bits.
It is clear that the search can only open small pieces of encrypted data, up to 48-64 bits. And this brute force can be arranged without MVC, for the task of finding the key by enumerating all possible values, the use of MVC is not necessary, it is an extra entity.
What do we have in the end?
If you encrypt large enough (128 bit or more) texts, which exclude the possibility of finding them in a reasonable time and reasonable costs to find them through the search, this “vulnerability” does not play any role.
Today, the minimum recommended ECC key length is 192 bits (24 bytes). The length of the encrypted MVC data in this case should not exceed 2 * 24 = 48 bytes, and the strongest AES or GOST key has a length of 256 bits (32 bytes).
But we get crypto-resistant and fairly fast (in my estimation, ECC-224 is 5 times faster than RSA-2048, 3 times faster than ElGamal-2048) asymmetric encryption algorithm.
I believe that the Elliptic curve Menezes-Vanstone cryptosystem is completely undeservedly forgotten.
Trying to fill this gap, I spread the source code in C using the openssl API.
Literature:
1. COMPUTER SECURITY AND CRYPTOGRAPHY, ALAN G. KONHEIM, Published by John Wiley & Sons, Inc., Hoboken, New Jersey, 2007. ISBN-13: 978-0-471-94783-7 ISBN-10: 0-471- 94783-0
2. “A Weakness of Menezes-Vanstone Cryptosystem” , Klaus Kiefer, member of the research group of prof. J. Buchmann, 1997
// // DESCRIPTION 'EC Menezes-Vanstone cryptosystem functions openssl/Linux' // COMPILER 'gcc (GCC) 4.8.2' // FILE 'ecmv.h' // AUTHOR "Nick Korepanov" // Linux-3.10.104, glibc-2.17, OpenSSL 1.0.1u // ECC-192/224/256 // This program is free software; you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation; either version 2 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Author of this program can be contacted by electronic mail // korepanovnd@gmail.com // Copyright (c) 2017 Nick Korepanov. All rights reserved. // This product includes software developed by the OpenSSL Project // for use in the OpenSSL Toolkit. (http://www.openssl.org/) // COMPUTER SECURITY AND CRYPTOGRAPHY, ALAN G. KONHEIM // Published by John Wiley & Sons, Inc., Hoboken, New Jersey, 2007 // Library of Congress Cataloging-in-Publication Data: // Konheim, Alan G., 1934– // Computer security & cryptography / by Alan G. Konheim. // p. cm. // Includes bibliographical references and index. // ISBN-13: 978-0-471-94783-7 // ISBN-10: 0-471-94783-0 // 1. Computer security. 2. Cryptography. I. Title. // QA76.9.A25K638 2007 // 005.8--dc22 2006049338 // 15.9 THE MENEZES–VANSTONE ELLIPTIC CURVE CRYPTOSYSTEM, p. 443 // Another very significant source - "A Weakness of Menezes-Vanstone Cryptosystem", Klaus Kiefer, member of research group of prof. J. Buchmann, 1997 // Shortly, this work show ability of "known plain text attack (KPTA)", with probability O(1/p) of false detection. // What does it mean? If we encrypt 128-bit session key, for success KPTA we must search in 2^128 combinations of session key ... // Known plaintext attack for EC MV cryptosystem // Curve E(p,a,b) known from public key, // y0, y1, y2 - ciphertext // random select 1 < x1 < p and 1< x2 < p // calculate inversion a=inv(x1)(mod p), b=inv(x2)(mod p) // c1=a*y1(mod p), c2=b*y2(mod p) // if C(c1,c2) is point of curve E, x1 and x2 is plaintext with error probability O(1/p) // z=((c1)^3 + a*c1 + b)(mod p) // if (z^((p-1)/2))(mod p) == 1 there are 2 points (c1,+-c2) in curve E(p,a,b) //#include <stdio.h> #include <stdlib.h> #include <string.h> //#include <unistd.h> #include <openssl/rand.h> #define OPENSSL_NO_EC2M #include <openssl/ec.h> #define FORMATBIN 1 #define FORMATHEX 0 struct BinFmt192 // binary format of ECMV encrypted block, EC key = 192 bits { unsigned char y0[1+192/4]; // 2*24 byte BIGNUM + 1 header byte unsigned char z1; unsigned char y1[192/8]; // 24 bytes BIGNUM unsigned char z2; unsigned char y2[192/8]; // 24 bytes BIGNUM unsigned char z3; }; // size = 100 bytes struct BinFmt224 // binary format of ECMV encrypted block, EC key = 224 bits { unsigned char y0[1+224/4]; // 2*28 byte BIGNUM + 1 header byte unsigned char z1; unsigned char y1[224/8]; // 28 bytes BIGNUM unsigned char z2; unsigned char y2[224/8]; // 28 bytes BIGNUM unsigned char z3; }; // size = 116 bytes struct BinFmt256 // binary format of ECMV encrypted block, EC key = 256 bits { unsigned char y0[1+256/4]; // 2*32 byte BIGNUM + 1 header byte unsigned char z1; unsigned char y1[256/8]; // 32 bytes BIGNUM unsigned char z2; unsigned char y2[256/8]; // 32 bytes BIGNUM unsigned char z3; }; // size = 132 bytes // Encrypt plaintext of length len with public EC key pubkey // and store ciphertext in chipher = y0 (point), y1 (bignum), y2 (bignum) // return error code, 0 if all OK // Error codes: /* * 1 // no curve in key? * 2 // wrong plaintext has odd length * 3 // plaintext too long for this key * 8 // binary format of encrypted block not defined for this key length * 4 // internal error: ks is wrong, error in do-while * 5 // internal error: error in EC_POINT_mul y0=ks*g * 6 // internal error: error in EC_POINT_mul z=ks*q * 7 // internal error: error EC_POINT_get_affine_coordinates_GFp * errors 4,5,6,7 lead to memory leak :( * */ // hex format: // Encrypted text consist of 3 hex strings, each is ending with '\n'=0x0A // First string has '04' header and two times longer than second and third // length of encrypted block = 2*4*bits/8 + 5 = bits + 5 bytes, where 'bits' is length of EC key in bits // Plaintext data MUST be of even length in bytes and not longer than 2*bits/8 = bits/4 bytes // bin format: // Encrypted text is binary block consist of 3 binary elements, each is ending with NULL=0x00 byte // First element has 0x04 header and two times longer than second and third // length of encrypted block in binary form = 4*bits/8 + 4 = bits/2 + 4 bytes, where 'bits' is length of EC key in bits // In this example I used 192,224,256 bit EC keys and binary form for other key length don't supported :( int EC_MV_pubkey_encrypt(unsigned char *cipher, EC_KEY* pubkey, unsigned char* plaintext, size_t len, int format); // Decrypt with private EC key privkey ciphertext in cipher = y0 (point), y1 (bignum), y2 (bignum) // and store result in plaintext // return error code, 0 if all OK /* Error codes: * 1 // no curve in key? * 8 // unknown format of ECMV encrypted block * 9 // binary format of encrypted block not defined for this key length * 10 // wrong format of binary encrypted block * 2 // invalid hex point y0 representation * 3,4 // wrong format of HEX encrypted data * 11 // point y0 is not on curve * 6 // internal error: error in EC_POINT_mul z=ks*q * 7 // internal error: error EC_POINT_get_affine_coordinates_GFp * errors 2,3,4,11,6,7 lead to memory leak :( * */ int EC_MV_privkey_decrypt(unsigned char* cipher, EC_KEY *privkey, unsigned char* plaintext); // // DESCRIPTION 'EC Menezes-Vanstone cryptosystem functions openssl/Linux' // COMPILER 'gcc (GCC) 4.8.2' // FILE 'ecmv.c' // AUTHOR "Nick Korepanov" // Linux-3.10.104, glibc-2.17, OpenSSL 1.0.1u // ECC-192/224/256 // This program is free software; you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation; either version 2 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Author of this program can be contacted by electronic mail // korepanovnd@gmail.com // Copyright (c) 2017 Nick Korepanov. All rights reserved. // This product includes software developed by the OpenSSL Project // for use in the OpenSSL Toolkit. (http://www.openssl.org/) #include "ecmv.h" int EC_MV_pubkey_encrypt(unsigned char *cipher, EC_KEY* pubkey, unsigned char* plaintext, size_t len, int format) { const EC_GROUP *curve; // curve, q and g are part of pubkey, it was allocated and free with pubkey const EC_POINT *q; EC_POINT *y0, *z; BIGNUM *p, *a, *b, *ks, *o1, *z1, *z2, *y1, *y2, *x1, *x2, *ord; int bits, i=0, err; unsigned char buffer[250]; //size_t length; BN_CTX *ctx; curve=EC_KEY_get0_group(pubkey); if(curve) bits = EC_GROUP_get_degree(curve); else return 1; // no curve in key? if(len%2) return 2; // wrong plaintext has odd length if(len > 2*bits/8) return 3; // plaintext too long for this key if( !(bits == 192 || bits == 224 || bits == 256) && format) return 8; // binary format of encrypted block not defined for this key length //prepare bignums p=BN_new(); a=BN_new(); b=BN_new(); ks=BN_new(); o1=BN_new(); z1=BN_new(); z2=BN_new(); y1=BN_new(); y2=BN_new(); x1=BN_new(); x2=BN_new(); ord=BN_new(); ctx=BN_CTX_new(); //prepare points //q=EC_POINT_new(curve); g=EC_POINT_new(curve); y0=EC_POINT_new(curve); z=EC_POINT_new(curve); // split plaintext at two parts, and assign it to BIGNUMs BN_bin2bn(plaintext, len/2, x1); BN_bin2bn(plaintext+len/2, len/2, x2); // get public key q q=EC_KEY_get0_public_key(pubkey); // get generator point g //g=EC_GROUP_get0_generator(curve); // get order of g EC_GROUP_get_order(curve, ord, ctx ); // get prime p EC_GROUP_get_curve_GFp(curve, p, a, b, ctx ); BN_sub(o1, ord, BN_value_one()); // o1=ord-1 do { if( i>= 10) break; // make secret session key ks > 1 and ks < (o-1) RAND_bytes(buffer, bits/8); BN_bin2bn(buffer, bits/8, ks); i++; } while( BN_cmp(BN_value_one(), ks) >=0 || BN_cmp(o1,ks) <=0 ); if(i>=10) return 4; // ks is wrong, error in do-while // y0=ks*g err=EC_POINT_mul(curve, y0, ks, NULL, NULL, ctx ); if(err == 0) return 5; // error in EC_POINT_mul y0=ks*g // z=ks*q err=EC_POINT_mul(curve, z, NULL, q, ks, ctx ); if(err == 0) return 6; // error in EC_POINT_mul z=ks*q // get z1,z2 = Z(z1,z2) err=EC_POINT_get_affine_coordinates_GFp(curve, z, z1, z2, ctx ); if(err == 0) return 7; //error EC_POINT_get_affine_coordinates_GFp //y1 = z1*x1(modulo p) //y2 = z2*x2(modulo p) BN_mod_mul(y1, z1, x1, p, ctx); BN_mod_mul(y2, z2, x2, p, ctx); /* if bits=192, 24 bytes per every BIGNUM, point contains 2 Bignum + 1 byte header */ if(format) { // bin format if(bits == 192) { struct BinFmt192 *out; out=(struct BinFmt192 *)cipher; EC_POINT_point2oct(curve, y0, POINT_CONVERSION_UNCOMPRESSED, (unsigned char*)&out->y0, sizeof(out->y0), ctx); BN_bn2bin(y1, (unsigned char*)&out->y1); BN_bn2bin(y2, (unsigned char*)&out->y2); out->z1=out->z2=out->z3=0; } if(bits == 224) { struct BinFmt224 *out; out=(struct BinFmt224 *)cipher; EC_POINT_point2oct(curve, y0, POINT_CONVERSION_UNCOMPRESSED, (unsigned char*)&out->y0, sizeof(out->y0), ctx); BN_bn2bin(y1, (unsigned char*)&out->y1); BN_bn2bin(y2, (unsigned char*)&out->y2); out->z1=out->z2=out->z3=0; } if(bits == 256) { struct BinFmt256 *out; out=(struct BinFmt256 *)cipher; EC_POINT_point2oct(curve, y0, POINT_CONVERSION_UNCOMPRESSED, (unsigned char*)&out->y0, sizeof(out->y0), ctx); BN_bn2bin(y1, (unsigned char*)&out->y1); BN_bn2bin(y2, (unsigned char*)&out->y2); out->z1=out->z2=out->z3=0; } } else { // hex format strcpy((char*)cipher, EC_POINT_point2hex(curve, y0, POINT_CONVERSION_UNCOMPRESSED, ctx)); strcat((char*)cipher, "\n"); strcat((char*)cipher, BN_bn2hex(y1)); strcat((char*)cipher, "\n"); strcat((char*)cipher, BN_bn2hex(y2)); strcat((char*)cipher, "\n"); } // free points //EC_POINT_free(q); EC_POINT_free(g); EC_POINT_free(y0); EC_POINT_clear_free(z); BN_CTX_free(ctx); BN_clear(ks); BN_clear(x1); BN_clear(x2); BN_clear(z1); BN_clear(z2); //free bignums BN_free(p); BN_free(a); BN_free(b); BN_free(ks); BN_free(o1); BN_free(z1); BN_free(z2); BN_free(y1); BN_free(y2); BN_free(x1); BN_free(x2); BN_free(ord); return 0; } int EC_MV_privkey_decrypt(unsigned char* cipher, EC_KEY *privkey, unsigned char* plaintext) { const EC_GROUP *curve; // curve, d are part of privkey, it was allocated and free with privkey const BIGNUM *d; EC_POINT *y0, *z; BIGNUM *p, *a, *b, *z1, *z2, *y1, *y2, *x1, *x2; int err, bits, format; unsigned char *ptr; BN_CTX *ctx; ctx=BN_CTX_new(); curve=EC_KEY_get0_group(privkey); if(!curve) return 1; // no curve in key? bits = EC_GROUP_get_degree(curve); if( cipher[0] == 0x04 ) format=FORMATBIN; if( cipher[0] == 0x30 ) format=FORMATHEX; if(cipher[0] != 0x04 && cipher[0] != 0x30) return 8; // unknown format of ECMV encrypted block if( !(bits == 192 || bits == 224 || bits == 256) && format) return 9; // binary format of encrypted block not defined for this key length if(format && bits == 192 && (cipher[48+1] || cipher[48+1+24+1] || cipher[48+1+24+1+24+1] )) return 10; //wrong format of binary encrypted block if(format && bits == 224 && (cipher[56+1] || cipher[56+1+28+1] || cipher[56+1+28+1+28+1] )) return 10; //wrong format of binary encrypted block if(format && bits == 256 && (cipher[64+1] || cipher[64+1+32+1] || cipher[64+1+32+1+32+1] )) return 10; //wrong format of binary encrypted block //prepare bignums p=BN_new(); a=BN_new(); b=BN_new(); z1=BN_new(); z2=BN_new(); y1=BN_new(); y2=BN_new(); x1=BN_new(); x2=BN_new(); //prepare points y0=EC_POINT_new(curve); z=EC_POINT_new(curve); // get private key d d=EC_KEY_get0_private_key(privkey); // get prime p EC_GROUP_get_curve_GFp(curve, p, a, b, ctx); if(format) { if(bits == 192) { struct BinFmt192 *in; in=(struct BinFmt192 *)cipher; EC_POINT_oct2point(curve, y0, (const unsigned char *)&in->y0, sizeof(in->y0), ctx); BN_bin2bn((const unsigned char *)&in->y1, sizeof(in->y1), y1); BN_bin2bn((const unsigned char *)&in->y2, sizeof(in->y2), y2); } if(bits == 224) { struct BinFmt224 *in; in=(struct BinFmt224 *)cipher; EC_POINT_oct2point(curve, y0, (const unsigned char *)&in->y0, sizeof(in->y0), ctx); BN_bin2bn((const unsigned char *)&in->y1, sizeof(in->y1), y1); BN_bin2bn((const unsigned char *)&in->y2, sizeof(in->y2), y2); } if(bits == 256) { struct BinFmt256 *in; in=(struct BinFmt256 *)cipher; EC_POINT_oct2point(curve, y0, (const unsigned char *)&in->y0, sizeof(in->y0), ctx); BN_bin2bn((const unsigned char *)&in->y1, sizeof(in->y1), y1); BN_bin2bn((const unsigned char *)&in->y2, sizeof(in->y2), y2); } } else { // read y0 ptr=cipher; y0=EC_POINT_hex2point(curve, (const char *)ptr, y0, ctx); if(y0 == NULL) return 2; //invalid hex point representation //read y1,y2 ptr=strchr((const char *)ptr,'\n'); if(ptr == NULL) return 3; //wrong format of encrypted data ptr++; BN_hex2bn(&y1, (const char *)ptr); ptr=strchr((const char *)ptr,'\n'); if(ptr == NULL) return 4; //wrong format of encrypted data ptr++; BN_hex2bn(&y2, (const char *)ptr); } if( !EC_POINT_is_on_curve(curve, (const EC_POINT *)y0, ctx) ) return 11; // point is not on curve // z=d*y0=d*ks*g=ks*q err=EC_POINT_mul(curve, z, NULL, y0, d, ctx ); if(err == 0) return 6; // error in EC_POINT_mul z=ks*q // get z1,z2 = Z(z1,z2) err=EC_POINT_get_affine_coordinates_GFp(curve, z, z1, z2, ctx ); if(err == 0) return 7; //error EC_POINT_get_affine_coordinates_GFp // a=inv(z1)(mod p) BN_mod_inverse(a, z1, p, ctx); // b=inv(z2)(mod p) BN_mod_inverse(b, z2, p, ctx); //x1 = a*y1(modulo p) //x2 = b*y2(modulo p) BN_mod_mul(x1, a, y1, p, ctx); BN_mod_mul(x2, b, y2, p, ctx); // decode plaintext from two parts BN_bn2bin(x1, plaintext); BN_bn2bin(x2, plaintext+BN_num_bytes(x1)); // free points EC_POINT_free(y0); EC_POINT_clear_free(z); BN_CTX_free(ctx); BN_clear(x1); BN_clear(x2); BN_clear(z1); BN_clear(z2); BN_clear(a); BN_clear(b); //free bignums BN_free(p); BN_free(a); BN_free(b); BN_free(z1); BN_free(z2); BN_free(y1); BN_free(y2); BN_free(x1); BN_free(x2); return 0; } Thanks for attention!
Source: https://habr.com/ru/post/332928/
All Articles