Implementation of the Elliptic curve Menezes-Vanstone cryptosystem based on the OpenSSL API
Hello, dear Khabrovites! As I was doing cryptography for my modest needs, trying to maintain a decent level of data security (I focus on the levels listed in the ecrypt section here ), I began to worry about performance degradation when using the RSA crypto algorithm.
Unfortunately, this algorithm turned out to be the only one in openssl that allows encryption / decryption of small data blocks (assumed by the meaning of the article - keys for symmetric encryption algorithms) using asymmetric cryptographic algorithms.
Walking through the Internet, I managed to find 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 performance, El-Gamal is 3 times faster than RSA
with the same key length and the same cryptographic strength per 1 bit of the key.
2. Elliptic Curve cryptosystem (ECC) was pleasantly surprised by the speed and cryptographic strength of 1 bit 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 of the elliptic curve mG, from which the original message m cannot be obtained otherwise than by hacking the ECC or enumerating all possible values of m.
3. The literature [1] describes the Menezes-Vanstone ECC, but there are notifications of its “vulnerability” [2]
Let us examine this question in more detail.
For simplicity, we will only talk about elliptic curves, the form of which is described by the Weierstrass equation y 2 = x 3 + a x + b over the fields of integers defined as Zp, where Zp is the set of integers smaller than some prime p and greater than zero.
Then E (p, a, b) - where a, b belong to Zp - is an elliptic curve over the field Zp defined by a prime number p and numbers a, b. Next, you need to determine the abstract zero element O (if the coefficient of the Weierstrass equation b is not equal to 0, then for the conditional point O you can take the coordinates x = 0, y = 0 even if this point is not a solution to the equation) and the operation of adding the elements of the curve (points) which will give a new point that belongs 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 of how these operations are determined.
You can add different points (P = G + Q) or a point with you (P = Q + Q). What we will talk about “multiplication” is just a way to shorten the record and not 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", just as there is no "raising to a power" and "taking the logarithm."
This terminology is often used, but for elliptic curves it does not mean what is usually understood 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 there is no reverse operation, “division” or “taking the logarithm”, it is impossible to get m from the point m * G, even knowing G, they say “the problem of the discrete logarithm on elliptic curves”. Such is the established terminology.
On this curve, a (arbitrary) point G (Gx, Gy) is selected which is a generator of a group of points, that is, by setting different m, we obtain 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 point of the generator G.
Thus, the elliptic group is completely described by the parameters of the curve E (p, a, b), the point of the generator G (Gx, Gy), and the order of the group ord, with ord * G = O. This is all called the elliptic curve parameters, which are usually well known, and are identified by their names, for example secp192k1 or prime256v1.
The user's private key is the (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 with the length of the curve parameter p.
2. The sender selects (secret, random) the 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) by multiplying the public key of the recipient Q by the number ks, Z = ks * Q
5. The sender calculates y1 = x1 * Zx (mod p), y2 = x2 * Zy (mod p)
Computing costs of the sender: generating a random number of the desired 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. The point contains 2 numbers - the x, y coordinates. The total amount of ciphertext is approximately 4 * p; for an ECC key of 192 bits (24 bytes) in length, approximately 24 * 4 = 96 bytes.
Recipient side:
1. The recipient checks that the point y0 belongs to the curve specified by the parameters E (p, a, b), G, ord.
2. The recipient calculates the point Z, multiplying the ciphertext y0 by his private key d, Z = d * y0 = d * ks * G = ks * d * G = ks * Q.
3. The receiver 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).
Recipient's computational costs: checking the point belongs to the curve, 1 operation of multiplying the point by a number, 2 operations of calculating the multiplicative inversion modulo p,
2 operations of multiplication modulo p.
In 1997, Klaus Kiefer [2] showed that MVC is not a system using probabilistic encryption, contrary to 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 plain text).
What it looks like:
Known parameters of the curve E (p, a, b), G, ord. The ciphertext y0, y1, y2 is known. We assume that 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 error probability 1 / p x1, x2 really is the desired plaintext.
What does this mean in practice?
That it is possible to sort out all the values x1, x2 with computational costs 2 operations of calculating the multiplicative inversion modulo p, 2 operations of multiplying modulo p by each variant x1, x2 and with a probability of error 1 / p to find plaintext that corresponds 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 search operation x1, x2 is well parallelized, many processes can independently iterate over their non-overlapping ranges of values x1, x2.
For reference: I would like to look at enumeration (just enumeration, without calculations) of all possible key values of 192 or 256 bits. Yes, even 128-168 bits.
It is clear that busting can reveal only small pieces of encrypted data, up to 48-64 bits. And this enumeration can be arranged without MVC, for the task of finding the key by enumerating all possible values, the use of MVC is not necessary, this is an unnecessary entity.
If you encrypt large enough (128 bits and more) texts that exclude the possibility of finding them by brute force within a reasonable time and reasonable costs, this “vulnerability” does not play any role.
To date, 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 a cryptographic and fast enough (according to my estimates, 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 C sources using the openssl API.
References:
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 research group of prof. J. Buchmann 1997
Thanks for attention!
Unfortunately, this algorithm turned out to be the only one in openssl that allows encryption / decryption of small data blocks (assumed by the meaning of the article - keys for symmetric encryption algorithms) using asymmetric cryptographic algorithms.
Walking through the Internet, I managed to find 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 performance, El-Gamal is 3 times faster than RSA
with the same key length and the same cryptographic strength per 1 bit of the key.
2. Elliptic Curve cryptosystem (ECC) was pleasantly surprised by the speed and cryptographic strength of 1 bit 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 of the elliptic curve mG, from which the original message m cannot be obtained otherwise than by hacking the ECC or enumerating all possible values of m.
3. The literature [1] describes the Menezes-Vanstone ECC, but there are notifications of its “vulnerability” [2]
Let us examine this question in more detail.
A bit of math:
For simplicity, we will only talk about elliptic curves, the form of which is described by the Weierstrass equation y 2 = x 3 + a x + b over the fields of integers defined as Zp, where Zp is the set of integers smaller than some prime p and greater than zero.
Then E (p, a, b) - where a, b belong to Zp - is an elliptic curve over the field Zp defined by a prime number p and numbers a, b. Next, you need to determine the abstract zero element O (if the coefficient of the Weierstrass equation b is not equal to 0, then for the conditional point O you can take the coordinates x = 0, y = 0 even if this point is not a solution to the equation) and the operation of adding the elements of the curve (points) which will give a new point that belongs 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 of how these operations are determined.
You can add different points (P = G + Q) or a point with you (P = Q + Q). What we will talk about “multiplication” is just a way to shorten the record and not 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", just as there is no "raising to a power" and "taking the logarithm."
This terminology is often used, but for elliptic curves it does not mean what is usually understood 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 there is no reverse operation, “division” or “taking the logarithm”, it is impossible to get m from the point m * G, even knowing G, they say “the problem of the discrete logarithm on elliptic curves”. Such is the established terminology.
On this curve, a (arbitrary) point G (Gx, Gy) is selected which is a generator of a group of points, that is, by setting different m, we obtain 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 point of the generator G.
Thus, the elliptic group is completely described by the parameters of the curve E (p, a, b), the point of the generator G (Gx, Gy), and the order of the group ord, with ord * G = O. This is all called the elliptic curve parameters, which are usually well known, and are identified by their names, for example secp192k1 or prime256v1.
The user's private key is the (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 the 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 with the length of the curve parameter p.
2. The sender selects (secret, random) the 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) by multiplying the public key of the recipient Q by the number ks, Z = ks * Q
5. The sender calculates y1 = x1 * Zx (mod p), y2 = x2 * Zy (mod p)
Computing costs of the sender: generating a random number of the desired 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. The point contains 2 numbers - the x, y coordinates. The total amount of ciphertext is approximately 4 * p; for an ECC key of 192 bits (24 bytes) in length, approximately 24 * 4 = 96 bytes.
Recipient side:
1. The recipient checks that the point y0 belongs to the curve specified by the parameters E (p, a, b), G, ord.
2. The recipient calculates the point Z, multiplying the ciphertext y0 by his private key d, Z = d * y0 = d * ks * G = ks * d * G = ks * Q.
3. The receiver 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).
Recipient's computational costs: checking the point belongs to the curve, 1 operation of multiplying the point by a number, 2 operations of calculating the multiplicative inversion modulo p,
2 operations of multiplication modulo p.
Vulnerability or Weakness of MVC
In 1997, Klaus Kiefer [2] showed that MVC is not a system using probabilistic encryption, contrary to 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 plain text).
What it looks like:
Known parameters of the curve E (p, a, b), G, ord. The ciphertext y0, y1, y2 is known. We assume that 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 error probability 1 / p x1, x2 really is the desired plaintext.
What does this mean in practice?
That it is possible to sort out all the values x1, x2 with computational costs 2 operations of calculating the multiplicative inversion modulo p, 2 operations of multiplying modulo p by each variant x1, x2 and with a probability of error 1 / p to find plaintext that corresponds 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 search operation x1, x2 is well parallelized, many processes can independently iterate over their non-overlapping ranges of values x1, x2.
For reference: I would like to look at enumeration (just enumeration, without calculations) of all possible key values of 192 or 256 bits. Yes, even 128-168 bits.
It is clear that busting can reveal only small pieces of encrypted data, up to 48-64 bits. And this enumeration can be arranged without MVC, for the task of finding the key by enumerating all possible values, the use of MVC is not necessary, this is an unnecessary entity.
What do we have in the end?
If you encrypt large enough (128 bits and more) texts that exclude the possibility of finding them by brute force within a reasonable time and reasonable costs, this “vulnerability” does not play any role.
To date, 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 a cryptographic and fast enough (according to my estimates, 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 C sources using the openssl API.
References:
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 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// [email protected]// 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 0structBinFmt192 // binaryformatofECMVencryptedblock, ECkey = 192 bits
{unsignedchar y0[1+192/4]; // 2*24 byte BIGNUM + 1 header byteunsignedchar z1;
unsignedchar y1[192/8]; // 24 bytes BIGNUMunsignedchar z2;
unsignedchar y2[192/8]; // 24 bytes BIGNUMunsignedchar z3;
}; // size = 100 bytesstructBinFmt224 // binaryformatofECMVencryptedblock, ECkey = 224 bits
{unsignedchar y0[1+224/4]; // 2*28 byte BIGNUM + 1 header byteunsignedchar z1;
unsignedchar y1[224/8]; // 28 bytes BIGNUMunsignedchar z2;
unsignedchar y2[224/8]; // 28 bytes BIGNUMunsignedchar z3;
}; // size = 116 bytesstructBinFmt256 // binaryformatofECMVencryptedblock, ECkey = 256 bits
{unsignedchar y0[1+256/4]; // 2*32 byte BIGNUM + 1 header byteunsignedchar z1;
unsignedchar y1[256/8]; // 32 bytes BIGNUMunsignedchar z2;
unsignedchar y2[256/8]; // 32 bytes BIGNUMunsignedchar 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 :( intEC_MV_pubkey_encrypt(unsignedchar *cipher, EC_KEY* pubkey, unsignedchar* 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 :(
* */intEC_MV_privkey_decrypt(unsignedchar* cipher, EC_KEY *privkey, unsignedchar* 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// [email protected]// 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"intEC_MV_pubkey_encrypt(unsignedchar *cipher, EC_KEY* pubkey, unsignedchar* 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;
unsignedchar buffer[250];
//size_t length;
BN_CTX *ctx;
curve=EC_KEY_get0_group(pubkey);
if(curve)
bits = EC_GROUP_get_degree(curve);
elsereturn1; // no curve in key?if(len%2)
return2; // wrong plaintext has odd lengthif(len > 2*bits/8)
return3; // plaintext too long for this keyif( !(bits == 192 || bits == 224 || bits == 256) && format)
return8; // 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-1do
{
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)
return4; // ks is wrong, error in do-while// y0=ks*g
err=EC_POINT_mul(curve, y0, ks, NULL, NULL, ctx );
if(err == 0)
return5; // error in EC_POINT_mul y0=ks*g// z=ks*q
err=EC_POINT_mul(curve, z, NULL, q, ks, ctx );
if(err == 0)
return6; // 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)
return7; //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 formatif(bits == 192)
{
structBinFmt192 *out;
out=(struct BinFmt192 *)cipher;
EC_POINT_point2oct(curve, y0, POINT_CONVERSION_UNCOMPRESSED, (unsignedchar*)&out->y0, sizeof(out->y0), ctx);
BN_bn2bin(y1, (unsignedchar*)&out->y1);
BN_bn2bin(y2, (unsignedchar*)&out->y2);
out->z1=out->z2=out->z3=0;
}
if(bits == 224)
{
structBinFmt224 *out;
out=(struct BinFmt224 *)cipher;
EC_POINT_point2oct(curve, y0, POINT_CONVERSION_UNCOMPRESSED, (unsignedchar*)&out->y0, sizeof(out->y0), ctx);
BN_bn2bin(y1, (unsignedchar*)&out->y1);
BN_bn2bin(y2, (unsignedchar*)&out->y2);
out->z1=out->z2=out->z3=0;
}
if(bits == 256)
{
structBinFmt256 *out;
out=(struct BinFmt256 *)cipher;
EC_POINT_point2oct(curve, y0, POINT_CONVERSION_UNCOMPRESSED, (unsignedchar*)&out->y0, sizeof(out->y0), ctx);
BN_bn2bin(y1, (unsignedchar*)&out->y1);
BN_bn2bin(y2, (unsignedchar*)&out->y2);
out->z1=out->z2=out->z3=0;
}
}
else
{ // hex formatstrcpy((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);
return0;
}
intEC_MV_privkey_decrypt(unsignedchar* cipher, EC_KEY *privkey, unsignedchar* 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;
unsignedchar *ptr;
BN_CTX *ctx;
ctx=BN_CTX_new();
curve=EC_KEY_get0_group(privkey);
if(!curve)
return1; // 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)
return8; // unknown format of ECMV encrypted block if( !(bits == 192 || bits == 224 || bits == 256) && format)
return9; // binary format of encrypted block not defined for this key lengthif(format && bits == 192 && (cipher[48+1] || cipher[48+1+24+1] || cipher[48+1+24+1+24+1] ))
return10; //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] ))
return10; //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] ))
return10; //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)
{
structBinFmt192 *in;
in=(struct BinFmt192 *)cipher;
EC_POINT_oct2point(curve, y0, (constunsignedchar *)&in->y0, sizeof(in->y0), ctx);
BN_bin2bn((constunsignedchar *)&in->y1, sizeof(in->y1), y1);
BN_bin2bn((constunsignedchar *)&in->y2, sizeof(in->y2), y2);
}
if(bits == 224)
{
structBinFmt224 *in;
in=(struct BinFmt224 *)cipher;
EC_POINT_oct2point(curve, y0, (constunsignedchar *)&in->y0, sizeof(in->y0), ctx);
BN_bin2bn((constunsignedchar *)&in->y1, sizeof(in->y1), y1);
BN_bin2bn((constunsignedchar *)&in->y2, sizeof(in->y2), y2);
}
if(bits == 256)
{
structBinFmt256 *in;
in=(struct BinFmt256 *)cipher;
EC_POINT_oct2point(curve, y0, (constunsignedchar *)&in->y0, sizeof(in->y0), ctx);
BN_bin2bn((constunsignedchar *)&in->y1, sizeof(in->y1), y1);
BN_bin2bn((constunsignedchar *)&in->y2, sizeof(in->y2), y2);
}
}
else
{
// read y0
ptr=cipher;
y0=EC_POINT_hex2point(curve, (constchar *)ptr, y0, ctx);
if(y0 == NULL)
return2; //invalid hex point representation//read y1,y2
ptr=strchr((constchar *)ptr,'\n');
if(ptr == NULL)
return3; //wrong format of encrypted data
ptr++;
BN_hex2bn(&y1, (constchar *)ptr);
ptr=strchr((constchar *)ptr,'\n');
if(ptr == NULL)
return4; //wrong format of encrypted data
ptr++;
BN_hex2bn(&y2, (constchar *)ptr);
}
if( !EC_POINT_is_on_curve(curve, (const EC_POINT *)y0, ctx) )
return11; // 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)
return6; // 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)
return7; //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);
return0;
}
Thanks for attention!
