7 ms·

none of it is "brute force", GNFS is a process that rapidly excludes numbers from the search space that cannot be the answer, in principle similar to the way th

none of it is "brute force", GNFS is a process that rapidly excludes numbers from the search space that cannot be the answer, in principle similar to the way they broke enigma. numberphile has a great video on that one https://www.youtube.com/watch?v=V4V2bpZlqx8 https://www.youtube.com/watch?v=V4V2bpZlqx8 Also, taking the OP as a "worse case", afaik: 512bit = $8 so 1024 = 8^2 = $64 2048 = 8^2^2 = $4,096 4096 = 8^2^2 = $16,777,216 noting $8 for 512 seems very expensive to me.

deleted 2y ago
[deleted]
btdmaster 2y ago
That's not correct. Consider, for example, a processor that can handle 2^31 computations per second. 2^32 operations can be computed in 2 time units, whereas 2^64 operations will take 2^33 time units. search_space(n: number_of_bits) = 2^n * k so search_space(1024)/search_space(512)=2^512, not 2^2. Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2. This would give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits. [0] https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve
- DarkmSparks 2y ago
  Pretty sure the search cost of GNFS is (bits)^2, the search cost of brute force is 2^(bits), if it was 2^(bits) GNFS would be no better than brute force. ->but only on the order of e^(cbrt(512 * 64/9)) e^(log(n)) = n
  - cryptizard 2y ago
    [dead]
littlestymaar 2y ago
Come on! Not only your math is ridiculous (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) but believing that RSA-2048 is factorizable in $4k is hilarious. > none of it is "brute force" It's not exhaustive search like it would be for symmetric encryption, but it's still somewhat brute-force (especially since RSA keys are inflated in size compared to symmetric encryption to accommodate for their vulnerabilities), put more clearly what I meant was “not without theoretical breakthrough unknown to the public”. BTW, it's not a very good idea to lecture people with actual crypto knowledge (even though mine is quite rusty now for I have not done any serious stuff for 15 years) when your own comes from ill-understood YouTube vulgarization videos.
- DarkmSparks 2y ago
  I personally factored 512 bit numbers in 2007 for a lot less than $8, so tbh I'm going to say your overestimation of your knowledge of cryptology is far more hilarious than my paranoia about the potential truth of claims made by people claiming to be experts in cryoptology. Your claim that factoring a 256bit number would cost fractions of a cent rather than my claim of roughly $3 is also very easily verifiable. Further I'll note you sound exactly like the kind of person insisting diffie hillman was a good key exchange mechanism prior to Snowdens disclosures. good luck with that.
  - littlestymaar 2y ago
    I'm charitably sharing this to you: https://news.ycombinator.com/item?id=42645216 https://news.ycombinator.com/item?id=42645216 because someone actually interested in learning things asked the right question. May you sleep less ignorant tonight. > Further I'll note you sound exactly like the kind of person insisting diffie hillman was a good key exchange mechanism prior to Snowdens disclosures. good luck with that. Before or after Snowden, Diffie-Hellman (it's Martin Hellman with an “e”) is a good key exchange mechanism! When using it on Z/pZ as field it's not the most practical one nowadays because you need big keys to get the desired security level (exactly the same problem as RSA), but you if you use an elliptic curves instead you can use shorter keys again (and this is exactly what ECDH is doing: it litterally means Elliptic Curve Diffie Hellman! Diffie-Hellman went nowhere).

deleted 2y ago

[deleted]

btdmaster 2y ago

That's not correct. Consider, for example, a processor that can handle 2^31 computations per second. 2^32 operations can be computed in 2 time units, whereas 2^64 operations will take 2^33 time units. search_space(n: number_of_bits) = 2^n * k so search_space(1024)/search_space(512)=2^512, not 2^2. Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2. This would give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits. [0] https://en.wikipedia.org/wiki/General_number_field_sieve https://en.wikipedia.org/wiki/General_number_field_sieve

DarkmSparks 2y ago
Pretty sure the search cost of GNFS is (bits)^2, the search cost of brute force is 2^(bits), if it was 2^(bits) GNFS would be no better than brute force. ->but only on the order of e^(cbrt(512 * 64/9)) e^(log(n)) = n
- cryptizard 2y ago
  [dead]

littlestymaar 2y ago

Come on! Not only your math is ridiculous (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) but believing that RSA-2048 is factorizable in $4k is hilarious. > none of it is "brute force" It's not exhaustive search like it would be for symmetric encryption, but it's still somewhat brute-force (especially since RSA keys are inflated in size compared to symmetric encryption to accommodate for their vulnerabilities), put more clearly what I meant was “not without theoretical breakthrough unknown to the public”. BTW, it's not a very good idea to lecture people with actual crypto knowledge (even though mine is quite rusty now for I have not done any serious stuff for 15 years) when your own comes from ill-understood YouTube vulgarization videos.

DarkmSparks 2y ago
I personally factored 512 bit numbers in 2007 for a lot less than $8, so tbh I'm going to say your overestimation of your knowledge of cryptology is far more hilarious than my paranoia about the potential truth of claims made by people claiming to be experts in cryoptology. Your claim that factoring a 256bit number would cost fractions of a cent rather than my claim of roughly $3 is also very easily verifiable. Further I'll note you sound exactly like the kind of person insisting diffie hillman was a good key exchange mechanism prior to Snowdens disclosures. good luck with that.
- littlestymaar 2y ago
  I'm charitably sharing this to you: https://news.ycombinator.com/item?id=42645216 https://news.ycombinator.com/item?id=42645216 because someone actually interested in learning things asked the right question. May you sleep less ignorant tonight. > Further I'll note you sound exactly like the kind of person insisting diffie hillman was a good key exchange mechanism prior to Snowdens disclosures. good luck with that. Before or after Snowden, Diffie-Hellman (it's Martin Hellman with an “e”) is a good key exchange mechanism! When using it on Z/pZ as field it's not the most practical one nowadays because you need big keys to get the desired security level (exactly the same problem as RSA), but you if you use an elliptic curves instead you can use shorter keys again (and this is exactly what ECDH is doing: it litterally means Elliptic Curve Diffie Hellman! Diffie-Hellman went nowhere).