Bitcoin Forum
May 04, 2024, 01:54:24 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Claus P. Schnorr, claims .. “destroys the RSA cryptosystem”  (Read 209 times)
eddie13 (OP)
Legendary
*
Offline Offline

Activity: 2296
Merit: 2262


BTC or BUST


View Profile
March 04, 2021, 04:53:19 PM
Merited by ABCbits (1), NotATether (1)
 #1

“ A recent paper, “Fast Factoring Integers by SVP Algorithms” by Claus P. Schnorr, claims significant improvements in factoring that “destroys the RSA cryptosystem”.”
https://sweis.medium.com/did-schnorr-destroy-rsa-show-me-the-factors-dcb1bb980ab0

“ Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct?”
https://crypto.stackexchange.com/questions/88582/does-schnorrs-2021-factoring-method-show-that-the-rsa-cryptosystem-is-not-secur


From what I am seeing this could be big if true/correct.. I’m not seeing any mention of it here yet..
I assume this is the same “Schnorr” as in “Schnorr signatures”?


Does this mean anything to Bitcoin or other coins that use different algorithms?
A laymen’s explanation could also be very helpful to many here (including me)..

Chancellor on Brink of Second Bailout for Banks
1714787664
Hero Member
*
Offline Offline

Posts: 1714787664

View Profile Personal Message (Offline)

Ignore
1714787664
Reply with quote  #2

1714787664
Report to moderator
1714787664
Hero Member
*
Offline Offline

Posts: 1714787664

View Profile Personal Message (Offline)

Ignore
1714787664
Reply with quote  #2

1714787664
Report to moderator
1714787664
Hero Member
*
Offline Offline

Posts: 1714787664

View Profile Personal Message (Offline)

Ignore
1714787664
Reply with quote  #2

1714787664
Report to moderator
"You Asked For Change, We Gave You Coins" -- casascius
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1714787664
Hero Member
*
Offline Offline

Posts: 1714787664

View Profile Personal Message (Offline)

Ignore
1714787664
Reply with quote  #2

1714787664
Report to moderator
1714787664
Hero Member
*
Offline Offline

Posts: 1714787664

View Profile Personal Message (Offline)

Ignore
1714787664
Reply with quote  #2

1714787664
Report to moderator
odolvlobo
Legendary
*
Offline Offline

Activity: 4298
Merit: 3214



View Profile
March 04, 2021, 05:36:59 PM
 #2

As far as I know, nothing in Bitcoin depends on RSA or is susceptible to integer factoring.

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
eddie13 (OP)
Legendary
*
Offline Offline

Activity: 2296
Merit: 2262


BTC or BUST


View Profile
March 05, 2021, 11:12:43 PM
Last edit: March 05, 2021, 11:31:37 PM by eddie13
 #3

As far as I know, nothing in Bitcoin depends on RSA or is susceptible to integer factoring.

I saw some FUD saying it was going to kill Bitcoin..
I’m not very learned on cryptography but I did some reading, and I thought it was interesting that cloudfare specifically cited Bitcoin a couple times..
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

From what I understand Bitcoin uses ECC instead of RSA because it takes up a lot less space/data to achieve the same or more security.. And also uses SHA which is not based on factoring either..


But I do read...

“ cryptocurrencies have shunned RSA in favor of  signatures based on elliptic curves, initially ECDSA and later moving towards pairing-based cryptography. Ethereum is the lone exception, having added native RSA support with EIP-198. “
https://www.google.com/amp/s/randomoracle.wordpress.com/2019/07/14/ethereum-mixing-with-rsa-getting-by-without-zero-knowledge-proofs/amp/

So maybe it will kill ETH..
Maybe I’ll throw a topic in altcoins and ask about that.. https://bitcointalk.org/index.php?topic=5321945.0

Chancellor on Brink of Second Bailout for Banks
NotATether
Legendary
*
Offline Offline

Activity: 1596
Merit: 6727


bitcoincleanup.com / bitmixlist.org


View Profile WWW
March 09, 2021, 05:30:03 PM
 #4

I meant to answer this but life happened and I somehow forgot this thread. Even though it doesn't really affect Bitcoin I'll give this a shot anyway.

I assume this is the same “Schnorr” as in “Schnorr signatures”?

Yes.



I think he only found a fast method for special cases. Just from the abstract you can see that he had to use a certain number n to make the factorization work, and even then it only works for particular numbers. I mean come on, he literally used 2400 and 2800 as examples [OK, numbers *close* to, but the point still stands - they are handpicked examples].

I could not fully digest the algorithms but as the Medium article said, for this discovery to be significant, it has to work on RSA numbers, which have exactly two factors. You'd have to find an n that factors it correctly so it's not very useful, given that there is no formula that can guess the right n if it even exists.

.
.BLACKJACK ♠ FUN.
█████████
██████████████
████████████
█████████████████
████████████████▄▄
░█████████████▀░▀▀
██████████████████
░██████████████
████████████████
░██████████████
████████████
███████████████░██
██████████
CRYPTO CASINO &
SPORTS BETTING
▄▄███████▄▄
▄███████████████▄
███████████████████
█████████████████████
███████████████████████
█████████████████████████
█████████████████████████
█████████████████████████
███████████████████████
█████████████████████
███████████████████
▀███████████████▀
█████████
.
aliashraf
Legendary
*
Offline Offline

Activity: 1456
Merit: 1174

Always remember the cause!


View Profile WWW
March 09, 2021, 09:33:27 PM
Last edit: March 09, 2021, 10:09:01 PM by aliashraf
Merited by Welsh (2), ABCbits (2), vapourminer (1), NeuroticFish (1)
 #5

Claus P. Schnorr is a big name in cryptography, no doubts, but I'd not take this work of him as a serious one for many reasons:

1- It falls on its own because of an irrational conclusion it has made about 800 bits RSA keys being breakable by just 4.8*1010 arithmetic operations. It is literally nothing, like few seconds for a modern cpu, and there are many 800 bits challenges out there waiting for a champ with a brilliant algorithm to overcome in real time.

2- SVP and lattice based methods in general terms, are not new technologies, they have been around for quite a while, and it is very unlikely to disrupt the integer factorization problem by applying improved versions of such methods.

3- In this paper, Schnorr, again uses his suggested pruning technique from the 1990s, which is not established as being rigorous enough.

4- Even in its first stages of getting peer reviewed, the paper has received strong backlash from cryptanalysts.

Conclusion
No, RSA, the way it is used in the industry with very long keys, is not close to a break point, even for 800 bits long keys which are obsolete anyway, state-of-the-art algorithms can not do the job by utilizing less than two thousands CPU-core*years.

No need to remind that the whole story has nothing to do with bitcoin as RSA is not employed here.

 
EDIT:
In spite of the last point I made above being absolutely valid, it is also true that such a hypothetical breakthrough in the integer factorization would be somehow unpleasant news for Bitcoin because it suggests the feasibility of similar developments in the discrete logarithm problem field which ECDSA is based on it.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!