Comments (4)
You don't need to brute force any bits for this challenge, you've got enough bits to solve it. If you want to debug whether it would work or not, you can do the following:
import logging
logging.basicConfig(format='%(asctime)s.%(msecs)03d %(levelname)s {%(module)s} [%(funcName)s] %(message)s', datefmt='%Y-%m-%d,%H:%M:%S', level=logging.DEBUG)
from shared import small_roots
small_roots.DEBUG_ROOTS = [0x777ee137, 0x890f7324, 0x65e8bb1cff] # Note the order is reversed here
You'll then get an output similar to this:
2022-02-11,19:00:34.016 INFO {coppersmith} [factorize_p] Trying m = 5, t = 1...
2022-02-11,19:00:34.023 DEBUG {herrmann_may_multivariate} [modular_multivariate] Generating shifts...
2022-02-11,19:00:34.025 DEBUG {__init__} [fill_lattice] Filling the lattice (56 x 56)...
2022-02-11,19:00:34.269 DEBUG {__init__} [reduce] Executing the LLL algorithm...
2022-02-11,19:00:52.405 DEBUG {__init__} [reconstruct_polynomials] Reconstructing polynomials...
2022-02-11,19:00:52.418 DEBUG {__init__} [reconstruct_polynomials] Original polynomial divides reconstructed polynomial at row 0, dividing...
2022-02-11,19:00:52.418 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 0 is constant, ignoring...
2022-02-11,19:00:52.425 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 1 roots check: 0
2022-02-11,19:00:52.432 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 2 roots check: 0
2022-02-11,19:00:52.438 DEBUG {__init__} [reconstruct_polynomials] Polynomial at row 3 roots check: 0
...
This tells you which reconstructed polynomials have integer roots in the provided roots. If all of them are non-zero, then you should select a higher m
value (or maybe a higher t
value, but this works rarely). If most of them (excluding the couple last ones) are 0, then the Groebner basis method will automatically find the roots. If most of them are 0, but there are a couple of non-zero ones first, you can manually pick the right polynomials and perform the Groebner basis reduction yourself. However, this requires a lot of hacking in the code.
Once you can solve it for the example values (without brute forcing here), it shouldn't be too hard to solve the actual challenge
from crypto-attacks.
Wow! after debugging I realized all I needed to do was change m
from 5 to 6, for whatever reason 5 takes much much longer than 6 on the actual values I need (and example values too), like it should still work with 5 based on my testing, but it's so much slower it's unbelievable (contrary to what I expected).
Challenged solved now, but care to explain why it might work much faster on m=6
than m=5
?
(at least with both values I provided, example values and challenge values)
from crypto-attacks.
Never mind after some more debugging I noticed that when m=5
another sneaky number besides the last few was non zero, I get why it failed.
from crypto-attacks.
Never mind after some more debugging I noticed that when
m=5
another sneaky number besides the last few was non zero, I get why it failed.
Right, the issue is that the root finding method can't know that without also knowing the roots. Heuristically, the first ones should always be zero, but sometimes it's not the case.
from crypto-attacks.
Related Issues (16)
- Any C/C++ implementation HOT 1
- Frey ruck attack test HOT 1
- something wrong when I run the code:rsa/wiener_attack_common_rsa_prime.py HOT 2
- AMM method function rth_roots() get same roots HOT 1
- A faster function to solve the DLP question in ecc's singular_curve.py HOT 5
- Generate Anomalous Curve with Given order HOT 4
- shared.ecc.generate_with_order speed up HOT 2
- how to use HOT 7
- memory usage in hencel lift HOT 2
- Short Nonces in ECDSA HOT 3
- SyntaxError: invalid syntax HOT 21
- Extended partial key exposure attacks on RSA: Improvement up to full size decryption exponents HOT 3
- adding aes cpa and dpa attacks HOT 2
- how to use "Branch and prune for the case with p, q, and d bits known"? HOT 1
- TypeError in Example code rsa/boneh_durfee.py HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from crypto-attacks.