-
Notifications
You must be signed in to change notification settings - Fork 16
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
LSB 0 bit bias #3
Comments
If you know your nonce k = 2^z k' where z is the number of zero least significant bits and k' which is small, then you can multiply your signature relation (sk = h+xr mod n) by 2^{-z} on both sides, and obtain a new relation written in terms of k'. I don't think you'll be able to use our code as a black box to solve this without going into the internals of the code. You can probably get the lattice basis to contain the desired solution by multiplying the r and h in the signature input data by 2^{-z}. But then this will cause the check for the correct solution (which verifies that the x coordinate of kG on the curve for the candidate k coming from the lattice vector is r) to fail. So you will need to write a new predicate function that inputs a candidate k' from the lattice, multiplies it by 2^z to get a candidate k, and checks whether the x coordinate of the value kG on the curve matches the original r. |
Wow that was fast. Checking the formula and trying to calculate the new relation k' I get: putting this into my matrix for 8bit shift like so: t=-(modular_inv(sigs[i][1], order)*sigs[i][0]snrn_inv) then reversing the shift like this: potential_nonce = row[0] This should work right? It does not for me. Maybe I am just missing something else... Also in your code checking the predicate function I see the check:
But where is the output of the lattice where the first row should be my k' values? I would then just shift k' back and the check should work again right? Thanks again for the help. -e |
The predicate function takes in a vector v and in this case is checking the value of the first coordinate to see if it matches the r value from the first signature. The multiplication and unshifting in the code are a bit confusing because we precompute the scalar multiplications on the curve to speed up the predicate check. I'm not going to be able to debug your code for you. Your best bet is to go through and verify your values on a known test example at every step. |
Hello, thank you for the help so far. I was able to implement the LSB Shift into my own code and it is working. Looking at the matrix generation in your code I can see that it is not as easy to implement. But I will try to see if I can get it to work and post an update. Best Wishes |
Hello Martin,
after some work with WSL and Debian I was able to get sage and g6k working.
Some of your instructions did not work for me. I had to try different routes but succeeded at the end.
Your scripts works great. Thank you for that. (Docker image does not work for me).
Reading through the paper of de Micheli and Heniger et al. I expected that the LSB bias HNP would be as easy as the MSB bias.
They state that a bitshift is everything that is needed to use the LSB bias in the MSB bias matrix. I tested every possible way to try this but I did not succeed in getting this to work.
Maybe you have a hint for me.
Danke dir.
Best wishes
-e
The text was updated successfully, but these errors were encountered: