Montgomery Modulus preparation breaks elliptic curve computation

[sylvainpelissier]

If an elliptic curve is initialiazed and then the function prepare_monty is called then the following elliptic curve computations will be wrong. Here an example of this bug:

int main(void) {

    big x,y,a,p,b, d, order, n0;
    epoint *g,*w;

    mip=mirsys(8/4,16);
    mip->IOBASE=10;

    // Dummy curve
    a = mirvar(1);
    b = mirvar(44);
    p = mirvar(229);
    x = mirvar(5);
    y = mirvar(116);
    order = mirvar(239);
    d=mirvar(4);
    n0 = mirvar(23);

    ecurve_init(a, b, p, MR_PROJECTIVE);  /* initialise curve */
    g = epoint_init();
    w = epoint_init();

    if (!epoint_set(x,y,0,g)) /* initialise point */
    {
        printf("1. Problem - point (x,y) is not on the curve\n");
        return 0;
    }

    // Multiplication
    ecurve_mult(d,g,w);
    epoint_get(w, x, y);
    cotnum(x, stdout);

    // Montgomery Modulus
    prepare_monty(n0);

    // Multiplication again
    ecurve_mult(d,g,w);
    epoint_get(w, x, y);
    cotnum(x, stdout);
    return 0;
}

This programm will output

156
12

if you comment the line containing prepare_monty function it will output:

156
156

[mcarrickscott]

Hello Sylvain,

Yes, this is to be expected. With prepare_monty() you have changed the modulus that applies to the curve from 229 to 23, and so the results will change. Indeed when you change the modulus the point is probably no longer on the curve.

ecurve_init() takes as a parameter a modulus p, and then internally calls prepare_monty(p). You have overwritten this value.

Mike

On Wed, Aug 19, 2015 at 4:25 PM, Sylvain Pelissier <notifications@github.com

wrote:

If an elliptic curve is initialiazed and then the function _preparemonty is called then the following elliptic curve computations will be wrong. Here an example of this bug:

int main(void) {

big x,y,a,p,b, d, order, n0;
epoint *g,*w;

mip=mirsys(8/4,16);
mip->IOBASE=10;

// Dummy curve
a = mirvar(1);
b = mirvar(44);
p = mirvar(229);
x = mirvar(5);
y = mirvar(116);
order = mirvar(239);
d=mirvar(4);
n0 = mirvar(23);

ecurve_init(a, b, p, MR_PROJECTIVE);  /* initialise curve */
g = epoint_init();
w = epoint_init();

if (!epoint_set(x,y,0,g)) /* initialise point */
{
    printf("1. Problem - point (x,y) is not on the curve\n");
    return 0;
}

// Multiplication
ecurve_mult(d,g,w);
epoint_get(w, x, y);
cotnum(x, stdout);

// Montgomery Modulus
prepare_monty(n0);

// Multiplication again
ecurve_mult(d,g,w);
epoint_get(w, x, y);
cotnum(x, stdout);
return 0;

}

This programm will output

156 12

if you comment the line containing _preparemonty function it will output:

156 156

— Reply to this email directly or view it on GitHub https://github.com/CertiVox/MIRACL/issues/15.

Michael Scott Chief Cryptographer CertiVox Ltd Tel (353) 86 3888746

"Those who give up essential security to purchase a slightly better user experience, deserve to get hacked." (with apologies to Benjamin Franklin)

[sylvainpelissier]

Does it mean you cannot make elliptic curve computations and modular arithmetic computation with Montgomery representation in the same program?

[mcarrickscott]

Yes, of course you can. After you call ecurve_init() all internal calculations use Montgomery representation. Unless the modulus is of a form (like a pseudo-mersenne modulus) where Montgomery representation is not optimal.

Mike

On Thu, Aug 20, 2015 at 4:11 PM, Sylvain Pelissier <notifications@github.com

wrote:

Does it mean you cannot make elliptic curve computations and modular arithmetic computation with Montgomery representation in the same program?

— Reply to this email directly or view it on GitHub https://github.com/CertiVox/MIRACL/issues/15#issuecomment-133044445.

Michael Scott Chief Cryptographer CertiVox Ltd Tel (353) 86 3888746

"Those who give up essential security to purchase a slightly better user experience, deserve to get hacked." (with apologies to Benjamin Franklin)

[sylvainpelissier]

Ok thanks for the answer, maybe the documentation should reflect that since it could lead to hard to detect bugs.

[baz1]

Hello,

Although this issue is closed, I would like to bring up a question similar to Sylvain's last one: Would it be possible somehow to make calculations using several different Montgomery moduli?

I explain myself: since elliptic curves use Montomery modulus, then we cannot make calculations over Z/Zn when n is not the modulus used by the elliptic curve. Does there exist any workaround for this?

I tried to have several sets of miracl parameters (i.e. using get_mips and set_mips) to change the modulus that is used, but the fact that there are several "big" variables (pointers) makes it more difficult. I have tried the following:

    miracl *modified_params = get_mip();
    miracl *saved_params = new miracl;
    memcpy(saved_params, modified_params, sizeof(miracl));
    saved_params->modulus = mirvar(0);
    copy(modified_params->modulus, saved_params->modulus);
    prepare_monty(some_other_modulus);

which seemed to work, but when I duplicate the pR variable the same way I did for modulus, I get a segmentation fault, so I guess this is not the right way to do it. Is there any? Thank you

[baz1]

I get that the previous proposition with a memcpy was not very convincing, and I thus tried another with the mirsys function to create a whole new environment. This actually answers my previous question because the following piece of code seems to work as expected:

    miracl *original_params = get_mip();
#ifdef MR_SIMPLE_BASE
    miracl *modified_params=mirsys((MIRACL / 4) * pfc.mod->len(), 16);
#else
    miracl *modified_params=mirsys(pfc.mod->len(), 0);
    modified_params->IOBASE=16;
#endif
    prepare_monty(pfc.ord->getbig()); // other modulus than the previous one (pfc.mod)
    // [...]
    set_mip(original_params);

(reminder: current mip instance can be cleaned with mirexit() )

[mcarrickscott]

Hello Remi,

It is possible to do arithmetic with respect to any modulus at any time, but its not as simple, and not so fast.

You must use functions like modmult(), moddiv(), inverse() and pow() from big.h. For example

w=pow(x,y,n); // calculates w=x^y mod n

This n can be any modulus, not the same as that used by the elliptic curves.

The modulus n must be specified for all these functions.

Mike

On Fri, Jul 1, 2016 at 6:44 PM, Rémi Bazin notifications@github.com wrote:

I get that the previous proposition with a memcpy was not very convincing, and I thus tried another with the mirsys function to create a whole new environment. This actually answers my previous question because the following piece of code seems to work as expected:

miracl *original_params = get_mip();

ifdef MR_SIMPLE_BASE

miracl *modified_params=mirsys((MIRACL / 4) \* pfc.mod->len(), 16);

else

miracl *modified_params=mirsys(pfc.mod->len(), 0);
modified_params->IOBASE=16;

endif

set_mip(modified_params); // Note: Optional it seems
prepare_monty(pfc.ord->getbig());

(reminder: current mip instance can be cleaned with mirexit() )

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/miracl/MIRACL/issues/15#issuecomment-230007229, or mute the thread https://github.com/notifications/unsubscribe/ACm8ju1WZlk3Pizld7MGDuSDS7QSnzEnks5qRVHmgaJpZM4FucMi .