Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
On 20 December 2013 09:09, Patrick McCorry [hidden email] wrote: Thanks Guys, At the moment I'm trying to distinguish if n p, as the x co-ordinate does not wrap around n (so x = r in all cases) - to verify if this is always the case n can be greater than p, e.g. see the definition of secp112r1 in http://www.secg.org/collateral/sec2_final.pdf: p = DB7C 2ABF62E3 5E668076 BEAD208B n = DB7C 2ABF62E3 5E7628DF AC6561C5 Or n can be less than p, e.g. see the definition of secp112r2 p = DB7C 2ABF62E3 5E668076 BEAD208B n = 36DF 0AAFD8B8 D7597CA1 0520D04B Matt My understanding is that k . G = (x,y) And under the hood, 0 = x = p and 0 = y = p. Then the next step I believe is r = x mod n and NOT r = x mod p So in this case, because p n - then x will wrap around the modulus from time to time? Otherwise, if it is r = x mod p, then x will never actually wrap around p? such that r = x always. -- View this message in context: http://openssl.6102.n7.nabble.com/ECDSA-OpenSSL-Implementation-using-the-modulus-N-instead-of-field-size-q-tp47743p48648.html Sent from the OpenSSL - User mailing list archive at Nabble.com. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
On 28 February 2014 17:07, Paddy stonecold...@gmail.com wrote: On 20 December 2013 09:09, Patrick McCorry [hidden email] wrote: Thanks Guys, At the moment I'm trying to distinguish if n p, as the x co-ordinate does not wrap around n (so x = r in all cases) - to verify if this is always the case n can be greater than p, e.g. see the definition of secp112r1 in http://www.secg.org/collateral/sec2_final.pdf: p = DB7C 2ABF62E3 5E668076 BEAD208B n = DB7C 2ABF62E3 5E7628DF AC6561C5 Or n can be less than p, e.g. see the definition of secp112r2 p = DB7C 2ABF62E3 5E668076 BEAD208B n = 36DF 0AAFD8B8 D7597CA1 0520D04B Matt My understanding is that k . G = (x,y) And under the hood, 0 = x = p and 0 = y = p. Then the next step I believe is r = x mod n and NOT r = x mod p Correct So in this case, because p n - then x will wrap around the modulus from time to time? As per my previous answer p may be greater than n or it may not be. It depends on the curve. *If* p is greater than n, then yes, x may also be greater than n from time to time. Matt __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
My understanding is that k . G = (x,y) And under the hood, 0 = x = p and 0 = y = p. Then the next step I believe is r = x mod n and NOT r = x mod p So in this case, because p n - then x will wrap around the modulus from time to time? Otherwise, if it is r = x mod p, then x will never actually wrap around p? such that r = x always. -- View this message in context: http://openssl.6102.n7.nabble.com/ECDSA-OpenSSL-Implementation-using-the-modulus-N-instead-of-field-size-q-tp47743p48647.html Sent from the OpenSSL - User mailing list archive at Nabble.com. __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
Thanks Guys, At the moment I'm trying to distinguish if n p, as the x co-ordinate does not wrap around n (so x = r in all cases) - to verify if this is always the case Sent from my iPad On 20 Dec 2013, at 04:16, Billy Brumley bbrum...@gmail.com wrote: ... yet it seems you are free to use it as you please (like the rest of the library does) internally, so it depends on what you are doing. (Modifying the library or creating an application -- since you posted code snippets I assumed the former, Matt points out the proper way externally.) BBB On Fri, Dec 20, 2013 at 12:44 AM, Matt Caswell fr...@baggins.org wrote: On 19 December 2013 18:52, Billy Brumley bbrum...@gmail.com wrote: It's in the EC_GROUP structure: group-field. Check crypto/ec/ec_lcl.h. BBB Anything in the *lcl.h header files does not form part of the public API and you shouldn't really rely on it as it may change. Better is to use: int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); or int EC_GROUP_get_curve_GF2m(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); as appropriate dependent on the type of curve that you have. On Thu, Dec 19, 2013 at 9:54 AM, Patrick McCorry stonecold...@gmail.com wrote: From what I can see in the implementation (ecs_ossl.c) when using ecdsa_sign_setup - the 'q' field size is never used! /* * Does the multiplciation of G (generator) * k to produce curve point (x,y) */ EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx) What you call 'q' (called 'p' within openssl) is used in this operation. It is a parameter of the group and is required to do the point multiplication. Matt __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
On 20 December 2013 09:09, Patrick McCorry stonecold...@gmail.com wrote: Thanks Guys, At the moment I'm trying to distinguish if n p, as the x co-ordinate does not wrap around n (so x = r in all cases) - to verify if this is always the case n can be greater than p, e.g. see the definition of secp112r1 in http://www.secg.org/collateral/sec2_final.pdf: p = DB7C 2ABF62E3 5E668076 BEAD208B n = DB7C 2ABF62E3 5E7628DF AC6561C5 Or n can be less than p, e.g. see the definition of secp112r2 p = DB7C 2ABF62E3 5E668076 BEAD208B n = 36DF 0AAFD8B8 D7597CA1 0520D04B Matt __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
Hi,
From my understanding ECDSA has a modulus N and a field size of q.
When generating the co-ordinates (x,y) using the generator and random value
k - g * k = (x,y) - the x and y values should be restricted to the range x =
[1, ... , q-1] and y = [1, ... , q -1].
Then of course to get r we do:
r = x mod N
From what I can see in the implementation (ecs_ossl.c) when using
ecdsa_sign_setup - the 'q' field size is never used!
/*
* Does the multiplciation of G (generator) * k to produce curve point (x,y)
*/
EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx)
/*
* Retrieve BIGNUM for X value (don't need y)
*/
if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
NID_X9_62_prime_field)
{
if (!EC_POINT_get_affine_coordinates_GFp(group,
tmp_point, X, NULL, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
goto err;
}
}
/*
* Get r value by doing r = x mod N
*/
if (!BN_nnmod(r, X, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
goto err;
}
As well, in the verification of a signature 'q' should be used - but from
the implementation in the do_verify method, when 'mod q' should be executed
- it is actually doing it on the order N:
/* u1 = m * tmp mod order */
if (!BN_mod_mul(u1, m, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
/* u2 = r * w mod q */
if (!BN_mod_mul(u2, sig-r, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
To sum up - when does the field size 'q' get used (as depicted in the
algorithm description)? As it makes the r = x mod N operation pointless?
--
View this message in context:
http://openssl.6102.n7.nabble.com/ECDSA-OpenSSL-Implementation-using-the-modulus-N-instead-of-field-size-q-tp47743.html
Sent from the OpenSSL - User mailing list archive at Nabble.com.
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
order in the code you pasted = n in the wiki = N in your mail.
The code you pasted refers to GFp so the points (x,y) satisfy 0 = x
p and 0 = y p. That's probably what you mean by q. Anyway, it's
used in the underlying elliptic curve operations but is not
necessarily needed at the ECDSA level -- all that needs is the outputs
from scalar multiplication (i.e., p is used under the hood in
EC_POINT_mul and EC_POINT_get_affine_coordinates_GFp).
BBB
On Thu, Dec 19, 2013 at 2:52 AM, Paddy stonecold...@gmail.com wrote:
Hi,
From my understanding ECDSA has a modulus N and a field size of q.
When generating the co-ordinates (x,y) using the generator and random value
k - g * k = (x,y) - the x and y values should be restricted to the range x =
[1, ... , q-1] and y = [1, ... , q -1].
Then of course to get r we do:
r = x mod N
From what I can see in the implementation (ecs_ossl.c) when using
ecdsa_sign_setup - the 'q' field size is never used!
/*
* Does the multiplciation of G (generator) * k to produce curve point (x,y)
*/
EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx)
/*
* Retrieve BIGNUM for X value (don't need y)
*/
if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
NID_X9_62_prime_field)
{
if (!EC_POINT_get_affine_coordinates_GFp(group,
tmp_point, X, NULL, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
goto err;
}
}
/*
* Get r value by doing r = x mod N
*/
if (!BN_nnmod(r, X, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
goto err;
}
As well, in the verification of a signature 'q' should be used - but from
the implementation in the do_verify method, when 'mod q' should be executed
- it is actually doing it on the order N:
/* u1 = m * tmp mod order */
if (!BN_mod_mul(u1, m, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
/* u2 = r * w mod q */
if (!BN_mod_mul(u2, sig-r, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
To sum up - when does the field size 'q' get used (as depicted in the
algorithm description)? As it makes the r = x mod N operation pointless?
--
View this message in context:
http://openssl.6102.n7.nabble.com/ECDSA-OpenSSL-Implementation-using-the-modulus-N-instead-of-field-size-q-tp47743.html
Sent from the OpenSSL - User mailing list archive at Nabble.com.
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
Thank you Billy for the clarification - is there a way to retrieve the value
for p that is used under the hood? I assume the p value does not change
(unless the curve is changed).
Sent from my iPhone
On 19 Dec 2013, at 17:35, Billy Brumley bbrum...@gmail.com wrote:
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
order in the code you pasted = n in the wiki = N in your mail.
The code you pasted refers to GFp so the points (x,y) satisfy 0 = x
p and 0 = y p. That's probably what you mean by q. Anyway, it's
used in the underlying elliptic curve operations but is not
necessarily needed at the ECDSA level -- all that needs is the outputs
from scalar multiplication (i.e., p is used under the hood in
EC_POINT_mul and EC_POINT_get_affine_coordinates_GFp).
BBB
On Thu, Dec 19, 2013 at 2:52 AM, Paddy stonecold...@gmail.com wrote:
Hi,
From my understanding ECDSA has a modulus N and a field size of q.
When generating the co-ordinates (x,y) using the generator and random value
k - g * k = (x,y) - the x and y values should be restricted to the range x =
[1, ... , q-1] and y = [1, ... , q -1].
Then of course to get r we do:
r = x mod N
From what I can see in the implementation (ecs_ossl.c) when using
ecdsa_sign_setup - the 'q' field size is never used!
/*
* Does the multiplciation of G (generator) * k to produce curve point (x,y)
*/
EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx)
/*
* Retrieve BIGNUM for X value (don't need y)
*/
if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
NID_X9_62_prime_field)
{
if (!EC_POINT_get_affine_coordinates_GFp(group,
tmp_point, X, NULL, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
goto err;
}
}
/*
* Get r value by doing r = x mod N
*/
if (!BN_nnmod(r, X, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
goto err;
}
As well, in the verification of a signature 'q' should be used - but from
the implementation in the do_verify method, when 'mod q' should be executed
- it is actually doing it on the order N:
/* u1 = m * tmp mod order */
if (!BN_mod_mul(u1, m, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
/* u2 = r * w mod q */
if (!BN_mod_mul(u2, sig-r, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
To sum up - when does the field size 'q' get used (as depicted in the
algorithm description)? As it makes the r = x mod N operation pointless?
--
View this message in context:
http://openssl.6102.n7.nabble.com/ECDSA-OpenSSL-Implementation-using-the-modulus-N-instead-of-field-size-q-tp47743.html
Sent from the OpenSSL - User mailing list archive at Nabble.com.
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
It's in the EC_GROUP structure: group-field. Check crypto/ec/ec_lcl.h. BBB
On Thu, Dec 19, 2013 at 9:54 AM, Patrick McCorry stonecold...@gmail.com wrote:
Thank you Billy for the clarification - is there a way to retrieve the value
for p that is used under the hood? I assume the p value does not change
(unless the curve is changed).
Sent from my iPhone
On 19 Dec 2013, at 17:35, Billy Brumley bbrum...@gmail.com wrote:
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
order in the code you pasted = n in the wiki = N in your mail.
The code you pasted refers to GFp so the points (x,y) satisfy 0 = x
p and 0 = y p. That's probably what you mean by q. Anyway, it's
used in the underlying elliptic curve operations but is not
necessarily needed at the ECDSA level -- all that needs is the outputs
from scalar multiplication (i.e., p is used under the hood in
EC_POINT_mul and EC_POINT_get_affine_coordinates_GFp).
BBB
On Thu, Dec 19, 2013 at 2:52 AM, Paddy stonecold...@gmail.com wrote:
Hi,
From my understanding ECDSA has a modulus N and a field size of q.
When generating the co-ordinates (x,y) using the generator and random value
k - g * k = (x,y) - the x and y values should be restricted to the range x =
[1, ... , q-1] and y = [1, ... , q -1].
Then of course to get r we do:
r = x mod N
From what I can see in the implementation (ecs_ossl.c) when using
ecdsa_sign_setup - the 'q' field size is never used!
/*
* Does the multiplciation of G (generator) * k to produce curve point (x,y)
*/
EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx)
/*
* Retrieve BIGNUM for X value (don't need y)
*/
if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
NID_X9_62_prime_field)
{
if (!EC_POINT_get_affine_coordinates_GFp(group,
tmp_point, X, NULL, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,ERR_R_EC_LIB);
goto err;
}
}
/*
* Get r value by doing r = x mod N
*/
if (!BN_nnmod(r, X, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
goto err;
}
As well, in the verification of a signature 'q' should be used - but from
the implementation in the do_verify method, when 'mod q' should be executed
- it is actually doing it on the order N:
/* u1 = m * tmp mod order */
if (!BN_mod_mul(u1, m, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
/* u2 = r * w mod q */
if (!BN_mod_mul(u2, sig-r, u2, order, ctx))
{
ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB);
goto err;
}
To sum up - when does the field size 'q' get used (as depicted in the
algorithm description)? As it makes the r = x mod N operation pointless?
--
View this message in context:
http://openssl.6102.n7.nabble.com/ECDSA-OpenSSL-Implementation-using-the-modulus-N-instead-of-field-size-q-tp47743.html
Sent from the OpenSSL - User mailing list archive at Nabble.com.
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
__
OpenSSL Project http://www.openssl.org
User Support Mailing Listopenssl-users@openssl.org
Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
On 19 December 2013 18:52, Billy Brumley bbrum...@gmail.com wrote: It's in the EC_GROUP structure: group-field. Check crypto/ec/ec_lcl.h. BBB Anything in the *lcl.h header files does not form part of the public API and you shouldn't really rely on it as it may change. Better is to use: int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); or int EC_GROUP_get_curve_GF2m(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); as appropriate dependent on the type of curve that you have. On Thu, Dec 19, 2013 at 9:54 AM, Patrick McCorry stonecold...@gmail.com wrote: From what I can see in the implementation (ecs_ossl.c) when using ecdsa_sign_setup - the 'q' field size is never used! /* * Does the multiplciation of G (generator) * k to produce curve point (x,y) */ EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx) What you call 'q' (called 'p' within openssl) is used in this operation. It is a parameter of the group and is required to do the point multiplication. Matt __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?
... yet it seems you are free to use it as you please (like the rest of the library does) internally, so it depends on what you are doing. (Modifying the library or creating an application -- since you posted code snippets I assumed the former, Matt points out the proper way externally.) BBB On Fri, Dec 20, 2013 at 12:44 AM, Matt Caswell fr...@baggins.org wrote: On 19 December 2013 18:52, Billy Brumley bbrum...@gmail.com wrote: It's in the EC_GROUP structure: group-field. Check crypto/ec/ec_lcl.h. BBB Anything in the *lcl.h header files does not form part of the public API and you shouldn't really rely on it as it may change. Better is to use: int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); or int EC_GROUP_get_curve_GF2m(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx); as appropriate dependent on the type of curve that you have. On Thu, Dec 19, 2013 at 9:54 AM, Patrick McCorry stonecold...@gmail.com wrote: From what I can see in the implementation (ecs_ossl.c) when using ecdsa_sign_setup - the 'q' field size is never used! /* * Does the multiplciation of G (generator) * k to produce curve point (x,y) */ EC_POINT_mul(group, temp_point, k, NULL, NULL, ctx) What you call 'q' (called 'p' within openssl) is used in this operation. It is a parameter of the group and is required to do the point multiplication. Matt __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org __ OpenSSL Project http://www.openssl.org User Support Mailing Listopenssl-users@openssl.org Automated List Manager majord...@openssl.org
