ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Paddy
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?
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Billy Brumley
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 <[hidden email]> 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 List                    [hidden email]
> Automated List Manager                           [hidden email]
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Paddy
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 <[hidden email]> 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 <[hidden email]> 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 List                    [hidden email]
>> Automated List Manager                           [hidden email]
> ______________________________________________________________________
> OpenSSL Project                                 http://www.openssl.org
> User Support Mailing List                    [hidden email]
> Automated List Manager                           [hidden email]
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Billy Brumley
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 <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> 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 List                    [hidden email]
>>> Automated List Manager                           [hidden email]
>> ______________________________________________________________________
>> OpenSSL Project                                 http://www.openssl.org
>> User Support Mailing List                    [hidden email]
>> Automated List Manager                           [hidden email]
> ______________________________________________________________________
> OpenSSL Project                                 http://www.openssl.org
> User Support Mailing List                    [hidden email]
> Automated List Manager                           [hidden email]
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Matt Caswell (frodo@baggins.org)
On 19 December 2013 18:52, Billy Brumley <[hidden email]> 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 <[hidden email]> 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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Billy Brumley
... 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 <[hidden email]> wrote:

> On 19 December 2013 18:52, Billy Brumley <[hidden email]> 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 <[hidden email]> 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 List                    [hidden email]
> Automated List Manager                           [hidden email]
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Paddy
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 <[hidden email]> 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 <[hidden email]> wrote:
>>> On 19 December 2013 18:52, Billy Brumley <[hidden email]> 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 <[hidden email]> 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 List                    [hidden email]
>> Automated List Manager                           [hidden email]
> ______________________________________________________________________
> OpenSSL Project                                 http://www.openssl.org
> User Support Mailing List                    [hidden email]
> Automated List Manager                           [hidden email]
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Matt Caswell (frodo@baggins.org)
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
______________________________________________________________________
OpenSSL Project                                 http://www.openssl.org
User Support Mailing List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Paddy
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 List                    [hidden email]
Automated List Manager                           [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Paddy
In reply to this post by Matt Caswell (frodo@baggins.org)
>>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.
Reply | Threaded
Open this post in threaded view
|

Re: ECDSA - OpenSSL Implementation using the modulus (N) instead of field size (q)?

Matt Caswell (frodo@baggins.org)
On 28 February 2014 17:07, Paddy <[hidden email]> 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 List                    [hidden email]
Automated List Manager                           [hidden email]