Getting wrong results from llModPow
tracked
Logan Elf
Using the following values:
- x = 2386073
- n = 2
- p = 2147483647
The expected value of
xⁿ mod p
is 365213132:2386073 x 2386073 = 5693344361329
⌊ 5693344361329 ÷ 2147483647 ⌋ = 2651
2651 x 2147483647 = 5692979148197
5693344361329 - 5692979148197 = 365213132
however llModPow is incorrectly returning 365210482
Using https://www.emathcalculator.com/en/calculators/algebra/powerMod.php confirmed my long-hand calculation gave the correct result.
These are not the only values that give incorrect results (e.g. x=149120, with same n and p should return 761937930 but llModPow returns 761937910).
It does seem in my limited testing that llModPow gives wrong results when x² is larger than a 32bit integer.
You can check llModPow with the following script:
default
{
state_entry()
{
integer x = 2386073;
integer n = 2;
integer p = 2147483647;
integer expected = 365213132;
integer result = llModPow(x, n, p);
llSay(0, llList2CSV([ "x", x, "n", n, "p", p ]));
llSay(0, llList2CSV([ "expected", expected, "actual", result ]));
}
}
Change x, n, p and expected as appropriate.
ETA: Above details were posted in non-public fields, oops.
Log In
Maestro Linden
tracked
Maestro Linden
under review
Logan Elf
Maestro Linden I've written an implementation of ModPow in LSL (available from https://pastebin.com/DFYLjcQg as canny kept failing to upload it as an attachment, and it exceeds the 2500 character limit for replies) along with a test of 6 values to compute using my function and also using llModPow for comparison.
My UDFs correctly compute all 6 in less than half a second, despite LSL not having 64bit integers, nor unsigned integers and sub-optimally using long division rather than something like Montgomery reduction.
The repeated tests using llModPow all fail and takes over 6 seconds due to the 1s forced delay.
That the LSL version is over 12x faster than llModPow also suggests to me that the 1s forced delay is excessive and/or the implementation is poor.
Maestro Linden
Logan Elf: Okay, talking to the server team, we know we can update the function so that the x^n component of llModPow() is stored as an S64 internally before the modulo operation.
This would address cases in which abs(x^n) is less than 2^63, but one would still see issues for larger values (which could be hit for large x when n>2).
Just to be sure that updating llModPow() is the best path (and that some new/different function in LSL would be better), what are you using the result for? Are you calculating a sort of hash value?
Logan Elf
Maestro Linden I'm doing simple Diffie-Hellman key exchange using xⁿ mod p values (so x, n and p may be very big).
Maestro Linden
Logan Elf: Thanks for the info. The reason I ask is because we're curious if some higher-level LSL function would be more convenient for you (and probably run faster).
Logan Elf
Maestro Linden I guess what I really need is a way for both parties to be able to
randomly
generate the same
256-bit token (could generalise to n-bit). llHMAC can be used to generate big tokens, but you're still stuck with how to pass the random numbers. The beauty of DH is that the random numbers are passed without actually passing the numbers themselves.Leviathan Linden
Logan Elf I have implemented a fix for this. I'm using an algorithm mentioned here:
Which references this page:
I tried a few inputs, including the one you used to prove the old math incorrect and it now appears to be producing correct values. Also the calculation is Much Faster. This fix will probably be in server update codenamed "bacon" which might be released in Dec24 if you're lucky, but maybe not until Jan25.
BTW:
LSL integers are signed, which means for positive numbers you're limited to primes under 2^31. Under the hood I cast the S32 first to U32, then to U64 which means if you're clever you could try to use primes under 2^32 by feeding it negative numbers, but I didn't test it.
For llVerifyRSA() and friends we use the GnuTLS library. This means if you wanted to do proper Diffie-Hellman negotiation using higher level primes it might be possible to add new LSL methods that wrap the GnuTLS API. I considered embarking on that project for this but decided I would much prefer someone else design it. So, if you or someone else decide llModPow() just isn't cutting it then feel free to propose an LSL API that is a thin wrapper for GnuTLS and I will consider implementing it.
Leviathan Linden
Correction: this fix will be in the server update codenamed "Apple Cobbler" which we expect to be delivered Dec24.
Maestro Linden
needs info
Maestro Linden
I can confirm in GNU Octave that the correct result for the original example (x= 2386073 , n=2, p= 2147483647) would be 365213132 when using S64 math:
octave:11> p = cast(2147483647, "int64")
p = 2147483647
octave:12> x = cast(2386073, "int64")
x = 2386073
octave:13> mod(x*x, p)
ans = 365213132
However, LSL doesn't support S64 integers - only S32. Comparing the llModPow() result to a direct calculation in LSL, (script shown below), I get 2 different results, neither of which match the 64-bit math result:
x=2386073, p=2147483647
x*x =-1782273167
(x*x)%p=-1782273167
llModPow(x,2,p)=365210482
Looking back at octave when using S32 math, I see entirely different results, based on different integer overflow behavior:
octave:19> x = cast(2386073, "int32")
x = 2386073
octave:20> p = cast(2147483647, "int32")
p = 2147483647
octave:21> x*x
ans = 2147483647
octave:22> mod(x*x, p)
ans = 0
default
{
state_entry()
{
integer x = 2386073;
integer p = 2147483647;
llSay(0, "x=" + (string)x + ", p=" + (string)p);
llSay(0, "x*x =" + (string)(x*x));
llSay(0, "(x*x)%p=" + (string)((x*x) % p));
llSay(0, "llModPow(x,2,p)=" + (string)llModPow(x, 2, p));
}
}
Given that 64-bit integers aren't supported in LSL, I don't believe that the 'correct' 365213132 result is achievable when x^n is outside the S32 range. With that in mind, what's your "expected" result for this example - should it be the same as what
(x*x)%p
returns (-1782273167) or something else?Logan Elf
Maestro Linden The fact that LSL doesn't support 64bit integers (and your attempt in LSL) shows why we need this function! We don't want the intermediate result (which btw can be larger than 64 bits) we want the result
modulo
a 32 bit number (so by definition the result will always be 32 bits).For LSL, there is an arbitrary precision "bignum" implementation on the LSL wiki https://wiki.secondlife.com/wiki/BigNum which uses strings to represent numbers. When dealing with 32bit numbers, that bignum implementation should be unnecessary as we have llModPow. Except llModPow is
BROKEN
Maestro Linden
under review
Frionil Fang
It gets the wrong result immediately for 65536^2 mod (2^31-1): it should be 2, but gives 0. The internal precision does look like it's limited to (u)int32. Added it to the wiki article on llModPow as a caveat until this is fixed.
Lucia Nightfire
FYI, no one other than you and promoted accounts can see your details. They only see a blank report.
Maybe make a comment that shows your inputs and expected output.
Logan Elf
Lucia Nightfire thanks, i've edited my original post