Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Group overflow in EscalarMulFix #27

Open
khovratovich opened this issue Nov 20, 2019 · 0 comments
Open

Group overflow in EscalarMulFix #27

khovratovich opened this issue Nov 20, 2019 · 0 comments

Comments

@khovratovich
Copy link

The template SegmentMulFix() computes in Montgomery form the point V*base where V = (3*nWindows-bit input_value) + 2^(3*nWindows+1)+2^(3*nWindows-3)+2^(3*nWindows-6)+..+1. Therefore, for nWindows>82 we can have input_value as big as 2^(249)-1 and the value of V exceeding 2^(250)+2^(249)+2^(246), which is bigger than the prime subgroup order, possibly causing an overflow and infinity point computation in Montgomery. For such inputs the template is satisfied for some invalid input-output tuples and thus is flawed. Thus the nWindow value should not exceed 82. Currently it is set to 83 for many inputs in EscalarMulFix.

The simplest way to fix it is to use at most 246-bit segments and thus at most 82 windows.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant