LargeInteger constructor using (sign, value) might lead to incorrect values

[thofer-os]

Hi,

While running some tests on this library, I've stumbled across an issue in the implementation of the multiple-precision addition.

Adding 1 to 0x1fffffff erroneously results in 0x30000000, as can be verified here: https://jsfiddle.net/j8qoL5g4/35/
This stems from an error with the bitwise shift right operation in https://github.com/verificatum/verificatum-vjsc/blob/master/src/js/verificatum/arithm/li.js#L620
Indeed, since the max value for a word is having all M4_WORDSIZE bits set, the modulus should be 1 << (M4_WORDSIZE+1).
Therefore, the carry value is doubled.

[verificatum]

Tomas, Thank you for testing and improving the library. Could you please have a look at the fiddle again. I have edited it to use the routines as intended, and then things work correctly(?!). Please forgive me if I use this fiddle-thing improperly by editing it directly. I am not a coder and have not encountered it before. There is clearly a bug somewhere, but oddly I do not think this is a bug in the arithmetic routines. It seems rather to be in the initialization of LargeInteger instances from arrays of number the way you do it. Could you please have another look and see if you can help me figure this out? Please also send me an email. I am interested in the tests/analysis you do.

…

On 2022-01-11 16:58, Thomas Hofer wrote: Hi, While running some tests on this library, I've stumbled across an issue in the implementation of the multiple-precision addition. Adding 1 to 0x1fffffff erroneously results in 0x30000000, as can be verified here: https://jsfiddle.net/j8qoL5g4/30/ <https://jsfiddle.net/j8qoL5g4/30/> This stems from an error with the bitwise shift right operation in https://github.com/verificatum/verificatum-vjsc/blob/master/src/js/verificatum/arithm/li.js#L620 <https://github.com/verificatum/verificatum-vjsc/blob/master/src/js/verificatum/arithm/li.js#L620> Indeed, since the max value for a word is having all M4_WORDSIZE bits set, the modulus should be 1 << (M4_WORDSIZE+1). Therefore, the carry value is doubled. — Reply to this email directly, view it on GitHub <#3>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC33R4DL4K776POF54IPPXDUVRHRTANCNFSM5LWVUVIQ>. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[thofer-os]

Hi Douglas,

Thank you for the discussion via email!

I'll attempt to document it here for anyone who might have a similar issue.
To summarize, there is no issue in the implementation of the multi-precision addition (HAC 14.7), contrary to what I incorrectly deduced from the sample code above.

Using the hexstring constructor, the results match the expectations.
There is an issue in the (sign: number, value: number[]) constructo however, which accepts numbers >= 2**28, while the rest of the code assumes each number in the value array is < 2**28 leading to incorrect behaviour.

This can be seen in https://jsfiddle.net/szn4hd7j/73/

Therefore, I'll update the title of this issue and as discussed, I'll try and offer a patch to make the constructor more misuse-resistant.

Thanks again!