这是indexloc提供的服务,不要输入任何密码
Skip to content

Some concerns regarding the overflows in modL function #187

@valerini

Description

@valerini

Hey Dmitry,

I have some troubles convincing myself that the modL function won't suffer from overflows. If you have any references to a more detailed description of modL that would be really helpful! In particular I am concerned with its use here:

modL(sm.subarray(32), x);

Two arrays h and d get multiplied to produce x.

Both h and d are Uint8Array(64) with elements at most 8 bits each and only the first 32 elements non-zero, both elements were reduced mod L.

The resulting x is of type Float64Array(64).

I believe, that the number of bits in each element of the array x is maxed at the following values:
[16, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 18, 18, 17, 16, 0], i.e. the bit length |x[0]| <= 16, |x[1]| <= 17, etc.

Now, the modL function is called on x. And in this line

x[j] += carry - 16 * x[i] * L[j - (i - 32)];
it can happen that |x[j]| > 32, since |16 * x[i] * L[j - (i - 32)]| <= 4 + 21 + 8 = 33.
But during the bit operation on the next line:
carry = (x[j] + 128) >> 8;

(x[j] + 128) will get converted to a 32-bits signed integer (according to https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators, Section Bitwise shift operators). This will act as expected only if the length of the number being shifted is at most 32 bits, but why now will it be the case?

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions