Bug with BIG.mod in Java?

[JesusGarciaRodriguez]

Hello, I am using the Java version of the library (in particular, selecting only curve BLS461 for compilation) and I am having trouble with modular arithmetic.

The "mod" operation in BIG crashes (infinte loop) when using it on a "negative" BIG. For example, the following test will not finish:

public void test(){
        BIG b=new BIG(1);
        b.sub(new BIG(20));
        b.mod(new BIG(ROM.CURVE_Order));
}

Using debugger, it seems to be stuck in the loop:

            do {
                m.fshl(1);
                ++k;
            } while(comp(this, m) >= 0);

in mod method of (decompiled) class org\miracl\core\BLS12461\BIG.class

I think this falls within normal use, but in any case getting an infinite loop seems like a weird occurence even if something is wrong.

[mcarrickscott]

Hello Jesus,

The library does not support negative numbers, as in modular arithmetic there is no requirement for them. So subtracting a bigger number from a smaller number will result in undefined behaviour.

Admittedly falling into an infinite loop is probably not the best response..

Mike

On Tue, Feb 9, 2021 at 5:31 PM Jesus notifications@github.com wrote:

Hello, I am using the Java version of the library (in particular, selecting only curve BLS461 for compilation) and I am having trouble with modular arithmetic.

The "mod" operation in BIG crashes (infinte loop) when using it on a "negative" BIG. For example, the following test will not finish:

public void test(){ BIG b=new BIG(1); b.sub(new BIG(20)); b.mod(new BIG(ROM.CURVE_Order)); }

Using debugger, it seems to be stuck in the loop:

        do {
            m.fshl(1);
            ++k;
        } while(comp(this, m) >= 0);

in mod method of (decompiled) class org\miracl\core\BLS12461\BIG.class

I think this falls within normal use, but in any case getting an infinite loop seems like a weird occurence even if something is wrong.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/miracl/core/issues/38, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAU3ZDR5M37W54HIPCBII23S6FWNVANCNFSM4XLM6Y5A .

[JesusGarciaRodriguez]

Hello, thank you for the (really!) quick response! I understand that negative numbers "as is" are not supported, and thought this would probably be a consequence of that. However, I am working on an implementation where we "need" that kind of operation, in the sense of the following example, and that is why we found this.

 If we are considering a modulus p=7, we want 2-5 to give 4 as a result (as -3≡4 (mod 7)). 

This "issue" is easy to get around by ensuring the first element is bigger by adding the modulus p (using BIG.comp to check beforehand) before subtracting. We just wanted to make sure we were not missing anything because of how it crashed.