Researcher Claims to Crack RSA-2048 With Quantum Computer

[digaran]

Can you come up with a crypto system that has no solvable problem? If you don't have the parameters then you can't solve it, having no parameters also means you can't verify anything, I'm specifically talking about public key crypto systems. So if there is no problem to solve, you can't build a system to verify the authenticity of any data.

Just like finger prints, if there is no fingerprint, how can you identify someone by a fingerprint scanner?
If someone figures out a way to fake/forge the fingerprint, you go build a retina scanner etc.
My point is, the knowledge of forging/ faking fingerprints and retina scan already exist, knowledge has no age, it has existed outside the time space dimension, so it's only the matter of time before someone accesses such knowledge.

Now we live in a modern world, if there is advanced crypto systems, there will be advanced algos to break it.
For instance, you would never expect people from 1000 years ago to build a nuke, because there was no infrastructure in place to persuade them in seeking the required knowledge  to build it.

When the said infrastructure was founded and how long after that we managed to build a nuke? When was crypto systems currently in use were invented or founded? And how long has it been since?

[1715457679]

1715457679

[1715457679]

1715457679

[1715457679]

1715457679

[jvanname]

At this point in time, it is much more plausible that someone breaks RSA-2048 (or any other public key cryptographic algorithm) by discovering a classical algorithm that breaks RSA than if someone made a functional quantum computer that breaks RSA-2048. Yes. This means that Bitcoin is in danger and that people must be vigilant to developments in public key cryptanalysis. In order for Bitcoin to be safe against classical and quantum attacks, Bitcoin should use hash based signatures.

-Joseph Van Name Ph.D.

[larry_vw_1955]

At this point in time, it is much more plausible that someone breaks RSA-2048 (or any other public key cryptographic algorithm) by discovering a classical algorithm that breaks RSA than if someone made a functional quantum computer that breaks RSA-2048.

history doesn't bear that out though. it was invented in 1977. Researchers have had almost 50 years to break RSA and they still havent done it. The reason for that is simply that no classical algorithm likely exists. So it is more likely that a new technology like quantum computers will have to suffice.

Yes. This means that Bitcoin is in danger and that people must be vigilant to developments in public key cryptanalysis. In order for Bitcoin to be safe against classical and quantum attacks, Bitcoin should use hash based signatures.

if it was that simple they would have already done it. hash based signatures have drawbacks. one of which i think is they take up alot of space. that's like saying lets perform all our encryption using a one-time pad. sure, that's secure but it's inefficient too.

[jvanname]

I see that we are willing to sacrifice the safety that comes from hash based signatures with the efficiency of ECDSA. That is fine, but it is still a risk that needs to be acknowledged. New mathematics is being developed every day, and ECDSA may be taken down overnight by a simple but undiscovered algorithm. A dishonest mathematician may want to keep the algorithm a secret for as long as possible in order to steal lots of Bitcoins and wreak havoc. I do not think that this situation is likely, and even if ECDSA does get taken down, it will probably not be taken down overnight. It will probably take years to take ECDSA down using a classical computer (if ECDSA suffers from such classical weaknesses at all), but an overnight takedown of ECDSA from an unknown entity is something that the Bitcoin developers should have prepared for (I do not know how well they have prepared for this). There are several things that the cryptocurrency community can do about this:

1. The cryptocurrency community of course can get more educated about the possibility of ECDSA being broken by a classical mathematical attack either overnight or over the course of some time.

2. Bitcoin users should at least have the option of using hash based signatures if they want to. Not many people will do this since the fees for hash based signatures may be really high.

3. In the case of a successful attack against ECDSA, Bitcoin and all Bitcoin wallets should have a backup. This means that each private key needs to not just be associated with an ECDSA public key, but each private key needs to be also associated with other secret information that can be used to recover the lost or stolen coins in case that Bitcoin needs to replace its digital signature algorithm due to a mathematical break. In particular, each private key needs to be of the form H(p) where p is a backup public key and H is a cryptographic hash function. The Bitcoin developers also need to have a drop-in replacement for ECDSA ready along with the code that allows the Bitcoiners to agree upon an updated blockchain. I do not know how well this will work in practice.

I do not know if the Bitcoin developers have worked on Problem 3 yet.

-Joseph Van Name Ph.D.

[larry_vw_1955]

It will probably take years to take ECDSA down using a classical computer (if ECDSA suffers from such classical weaknesses at all), but an overnight takedown of ECDSA from an unknown entity is something that the Bitcoin developers should have prepared for (I do not know how well they have prepared for this).

there is no contingency plan in place right now. other than rolling back the blockchain prior to when it got hacked and introducing some new signature algorithm. of course that would be a total disaster for the entire bitcoin ecosystem and bitcoin might not survive. or it might take a huge plunge in price.

2. Bitcoin users should at least have the option of using hash based signatures if they want to. Not many people will do this since the fees for hash based signatures may be really high.

agreed. but for someone storing their wealth for long term savings and not doing frequent transactions, the fee might be worth the piece of mind.

3. In the case of a successful attack against ECDSA, Bitcoin and all Bitcoin wallets should have a backup. This means that each private key needs to not just be associated with an ECDSA public key, but each private key needs to be also associated with other secret information that can be used to recover the lost or stolen coins in case that Bitcoin needs to replace its digital signature algorithm due to a mathematical break. In particular, each private key needs to be of the form H(p) where p is a backup public key and H is a cryptographic hash function.

there's nothing stopping someone from creating a private key that way right now using sha256 for example. the thing is, p has no meaning to the blockchain currently. it's called a "brainwallet". i'm not sure how you would allow p to recover the lost or stolen coins. because that would or could require rolling back a potentially large number of transactions thus destroying peoples' trust in bitcoin.

The Bitcoin developers also need to have a drop-in replacement for ECDSA ready along with the code that allows the Bitcoiners to agree upon an updated blockchain. I do not know how well this will work in practice.

bitcoin developers are too busy working on lightning network and taproot and "important things" than to waste time worrying about these larger issues. i don't think there's anything they can do about them or will do about them until quantum computers force their hand. if something happens sooner than that, it might just mean the end of bitcoin.

[jvanname]

Maybe if the Bitcoin community did not spend so much of their energy shaming and hating mathematicians, they would attract more mathematicians (and yes, mathematicians behave just as badly because they are at universities and universities lack professionalism). There is no excuse for this. Cryptography is one of the primary applications of abstract algebra, number theory, and many other areas of mathematics, so there is no reason for why mathematicians would be disinterested in Bitcoin. If the Bitcoin community attracted instead of repelled mathematicians, the Bitcoin community would have made better progress of solving problems such as a backup in case ECDSA was broken.

I gave the people on this site an opportunity to improve their social skills so that they would not repel mathematicians any more, but they rejected this opportunity since they are unaware of their own lack of social skills.

And maybe Bitcoin would attract mathematicians if it had a mining algorithm that was actually designed to advance science.

-Joseph Van Name Ph.D.

[larry_vw_1955]

Maybe if the Bitcoin community did not spend so much of their energy shaming and hating mathematicians, they would attract more mathematicians (and yes, mathematicians behave just as badly because they are at universities and universities lack professionalism). There is no excuse for this. Cryptography is one of the primary applications of abstract algebra, number theory, and many other areas of mathematics, so there is no reason for why mathematicians would be disinterested in Bitcoin. If the Bitcoin community attracted instead of repelled mathematicians, the Bitcoin community would have made better progress of solving problems such as a backup in case ECDSA was broken.

bitcoin is not really a good example of pure mathematics since it uses magical hash functions that are not really very well understood. anytime it needs a bit of magic, it just pulls out a hash out of the hat like a magician pulls out a rabbit and voila everything is peachy. at some point you have to think that's going to become a problem. but i guess it hasn't happened yet.

I gave the people on this site an opportunity to improve their social skills so that they would not repel mathematicians any more, but they rejected this opportunity since they are unaware of their own lack of social skills.

i'm trying to improve my social skills towards mathematicians like you because i think bitcoin needs more of them to help it have a better design someday. so i'm glad you are here on the forum your thoughts are always very interesting and informing. clearly you know alot about pure mathematics and that's really amazing. to have someone like that here.

[jvanname]

Cryptographic hash functions and encryption functions are designed to be understood as much as possible while still efficiently mixing things up very well, and a good way to ensure the understandability of encryption functions and hash functions is to make these functions as mathematical as possible. I am not too familiar with techniques that one can use to analyze SHA-256 (it is harder for me to analyze SHA-256 since SHA-256 uses 32 bit blocks while AES uses 8 bit blocks), but I can attest to the mathematical nature of AES.

0. The non-linear portion of the AES S-box is simply inversion (and where we set 0^(-1)=0 to make inversion bijective) in the finite field F_{256} with 256 elements. Inversion over this finite field has very good mathematical properties. Just the other day, I computed the second largest eigenvalues in magnitude of the doubly stochastic matrix associated with the mapping {x,y}-->{a+x^(-1),a+y^(-1)} where a is an random element in F_{256}, and I got 18/256=9/126. This quantity is low and is much better than what we can get if we used a random S-box. If we used the full S-box with its non-linear portions, we would get a spectral radius of 16.41493572768185/256 which is closer to an ideal value of 16/256. I can analyze AES mathematically, so other people should be able to do this as well. The AES S-box was selected for other mathematical properties as well.

1. The group generated by the round functions of AES is the alternating group as it should be. This shows that not only does AES mix things up well, but AES also behaves mathematically enough to be analyzed. This is mostly due to AES being an SP-network.

2. I have been able to show that for good SP-networks, a lot of the structure (such as the partition of the message into S-boxes) is definable from the block cipher round function and only the block cipher round function.

3. For cryptography, one needs non-linearity. But there are mathematical ways to quantify the non-linearity of a cryptographic function, and mathematicians have studied maximally non-linear functions otherwise known as bent functions.

If anything, encryption functions and hash functions need to be studied more mathematically because we need to analyze and standardize alternatives to AES,SHA-2,SHA-3 for reasons that I have explained elsewhere (these functions have weaknesses). Of course, after the cryptographic function has been standardized, most people who use these functions will not analyze their cryptographic security and experience the mathematical nature of these functions. And I do not even need to mention how mathematical elliptic curve cryptography is.

-Joseph Van Name Ph.D.

[Wind_FURY]

Off-topic, but still a valid question.

If quantum computers actually start gaining the ability to crack Bitcoin's encryption, how fast will the Core Developers code a patch, have it merged, have it deployed? Fast enough?

If that wouldn't be a problem, how fast will full nodes run the new software? That I believe would be more "complicated".

[digaran]

Off-topic, but still a valid question.

If quantum computers actually start gaining the ability to crack Bitcoin's encryption, how fast will the Core Developers code a patch, have it merged, have it deployed? Fast enough?

If that wouldn't be a problem, how fast will full nodes run the new software? That I believe would be more "complicated".

What is a Bitcoin encryption? Public key cryptography is not encryption. But to answer your question, how do you know it hasn't been cracked already? Because if it's cracked, people wouldn't go after obvious coins, they do it another way.
But since there are no signs of it happening, devs see no reason to cause panic by saying it might happen soon so we need to be prepared, instead we are saying it, as experimental scientists.
EC being broken, we'll need another system on top of it, maybe we could even start implementing a new system right now and store the second proof of ownership on another database, something similar to 2fa authentication, when you want to transact, the other database/chain would first validate your 2fa token/password and generate a ticket for you to be accepted for entering the main chain mempool. This is just one idea.

[jvanname]

Wind_FURY-The post-quantum digital signature algorithms are well on their way to being standardized by NIST. Unfortunately, NIST somehow thinks it is important and awesome to standardize post-quantum algorithms without standardizing reversible counterparts to AES,SHA-256,SHA-3. To make things worse, one of the digital signature algorithms selected by NIST is a stateless hash-based signature algorithm. Yes. That is right. NIST thinks it is a good idea to standardize hash-based signatures to be safe against the quantum computers of the future, but they are too inept to notice that maybe they should first have the hash functions that are designed for the energy efficient reversible computers of the future. Well, since NIST thinks reversibility is unimportant, should work on better hash-based signature algorithms that incorporate partial reversibility by ourselves because NIST does not believe that this is important.

A typical Bitcoin digital signature is 71 bytes long. Let's look at the signature algorithms that are being standardized by the NIST.

Dilithium2-"Dilithium is a digital signature scheme that is strongly secure under chosen message attacks based on the hardness of lattice problems over module lattices." according to their website.

public key 1312 bytes
signature size 2420 bytes
signature verification 118412 cycles on the Skylake CPU with an optimized implementation.

SPHINCS+ is a stateless hash-based signature scheme, which was submitted to the NIST post-quantum crypto project. Stateless hashes will bloat up the blockchain with signatures. SPHINCS+ signatures will take 15 KB space if one just optimizes for signature size without optimizing for anything else, and we should expect longer signatures in practice. That is not going to work very well.

Dilithium2 could almost work. Bitcoin needs to seriously code up protocol that will allow for a drop-in replacement for ECDSA for elliptic curves. And all private keys need to be generated from a backup private-public key pair in case ECDSA gets broken. And there needs to be an automatic procedure for updating the blockchain in case ECDSA is broken. For example, if a whole bunch of long lost coins are being found, then the automatic system can kick in and tell everyone to join the new chain. We need a system that is hard coded in so that a backup blockchain can be implemented quickly and so that everyone can agree on the right blockchain in case ECDSA is broken. Yes. People will lose their coins and Bitcoin will lose value, but not everything will be lost.


-Joseph Van Name Ph.D.

[larry_vw_1955]

Off-topic, but still a valid question.

If quantum computers actually start gaining the ability to crack Bitcoin's encryption, how fast will the Core Developers code a patch, have it merged, have it deployed? Fast enough?

today? they would be caught with their pants pulled down. in 10 years maybe they wouldn't be.

SPHINCS+ is a stateless hash-based signature scheme, which was submitted to the NIST post-quantum crypto project. Stateless hashes will bloat up the blockchain with signatures. SPHINCS+ signatures will take 15 KB space if one just optimizes for signature size without optimizing for anything else, and we should expect longer signatures in practice. That is not going to work very well.

Dilithium2 could almost work. Bitcoin needs to seriously code up protocol that will allow for a drop-in replacement for ECDSA for elliptic curves. And all private keys need to be generated from a backup private-public key pair in case ECDSA gets broken. And there needs to be an automatic procedure for updating the blockchain in case ECDSA is broken. For example, if a whole bunch of long lost coins are being found, then the automatic system can kick in and tell everyone to join the new chain. We need a system that is hard coded in so that a backup blockchain can be implemented quickly and so that everyone can agree on the right blockchain in case ECDSA is broken. Yes. People will lose their coins and Bitcoin will lose value, but not everything will be lost.

I appreciate you bringing up these things. Your ideas sound very reasonable. The only thing that concerns me is how these NIST candidates some of them have been weeded out because they had serious flaws which LUCKILY got discovered before they branded them as standards. it seems like it's not so easy to come up with something that doesn't have holes in it. If we've learned anything from this NIST post quantum crypto standardization endeavor it would have to be that.

I'm sure you already heard: https://spectrum.ieee.org/quantum-safe-encryption-hacked but some people might not have.

[ecdsa123]

Cryptographic hash functions and encryption functions are designed to be understood as much as possible while still efficiently mixing things up very well, and a good way to ensure the understandability of encryption functions and hash functions is to make these functions as mathematical as possible. I am not too familiar with techniques that one can use to analyze SHA-256 (it is harder for me to analyze SHA-256 since SHA-256 uses 32 bit blocks while AES uses 8 bit blocks), but I can attest to the mathematical nature of AES.

0. The non-linear portion of the AES S-box is simply inversion (and where we set 0^(-1)=0 to make inversion bijective) in the finite field F_{256} with 256 elements. Inversion over this finite field has very good mathematical properties. Just the other day, I computed the second largest eigenvalues in magnitude of the doubly stochastic matrix associated with the mapping {x,y}-->{a+x^(-1),a+y^(-1)} where a is an random element in F_{256}, and I got 18/256=9/126. This quantity is low and is much better than what we can get if we used a random S-box. If we used the full S-box with its non-linear portions, we would get a spectral radius of 16.41493572768185/256 which is closer to an ideal value of 16/256. I can analyze AES mathematically, so other people should be able to do this as well. The AES S-box was selected for other mathematical properties as well.

1. The group generated by the round functions of AES is the alternating group as it should be. This shows that not only does AES mix things up well, but AES also behaves mathematically enough to be analyzed. This is mostly due to AES being an SP-network.

2. I have been able to show that for good SP-networks, a lot of the structure (such as the partition of the message into S-boxes) is definable from the block cipher round function and only the block cipher round function.

3. For cryptography, one needs non-linearity. But there are mathematical ways to quantify the non-linearity of a cryptographic function, and mathematicians have studied maximally non-linear functions otherwise known as bent functions.

If anything, encryption functions and hash functions need to be studied more mathematically because we need to analyze and standardize alternatives to AES,SHA-2,SHA-3 for reasons that I have explained elsewhere (these functions have weaknesses). Of course, after the cryptographic function has been standardized, most people who use these functions will not analyze their cryptographic security and experience the mathematical nature of these functions. And I do not even need to mention how mathematical elliptic curve cryptography is.

-Joseph Van Name Ph.D.

according this part:

0. The non-linear portion of the AES S-box is simply inversion (and where we set 0^(-1)=0 to make inversion bijective) in the finite field F_{256} with 256 elements. Inversion over this finite field has very good mathematical properties. Just the other day, I computed the second largest eigenvalues in magnitude of the doubly stochastic matrix associated with the mapping {x,y}-->{a+x^(-1),a+y^(-1)} where a is an random element in F_{256}, and I got 18/256=9/126. This quantity is low and is much better than what we can get if we used a random S-box. If we used the full S-box with its non-linear portions, we would get a spectral radius of 16.41493572768185/256 which is closer to an ideal value of 16/256. I can analyze AES mathematically, so other people should be able to do this as well. The AES S-box was selected for other mathematical properties as well.


can you explain in code what are you talking about? I do not uderstand anything.

please show step by step on real example values

[jvanname]

It seems like NIST really just wants to justify spending a lot of resources with its post-quantum cryptography competition. This is not good for cryptography, since I would rather use a more classically secure and more efficient digital signature algorithm than a sketchy digital signature algorithm. The NIST standardization gives people a false sense of security for cryptographic algorithms (except for hash-based signatures which actually are secure). And the NIST has fallen into the entire quantum hype while completely ignoring reversible computation with this cryptographic contest. Don't give into hype.

Hmm. It looks like I have done more to develop tests for the cryptographic security of functions than the entire Bitcoin community has (I am a @#$%coiner who only values worthless @#$%coins, so I do not count as a part of the Bitcoin community; I will let you think about that).

ecdsa123-Ok. I will try to explain finite fields and doubly stochastic matrices, but if one really wants to understand everything, one should learn about abstract algebra, linear algebra, probability, and stochastic processes. That should not be too hard since your name is ECDSA.

Abstract algebra:

A group is a set G along with a binary operation * along with a constant e and a unary inversion operation ^(-1) that satisfies the following identities.

0. (Closure) The expressions x*y only makes sense if x,y belong to G. And if x,y belong to G, then so do x*y,x^(-1).

1. (Associativity) (x*y)*z=x*(y*z)

2. (Identity) x*e=e*x=x.

3. (Inverses) x*x^(-1)=x^(-1)*x=e (x^(-1) is the inverse of x).

A group is said to be abelian if it satisfies the identity x*y=y*x. In an abelian group, we typically write + instead of * and we typically write -x instead of x^(-1).

For example, the set of all integers with the operation + forms an abelian group. Don't think about the axioms too much. Whenever someone says "abelian group" you should think of "an operation on a set that resembles the integers with addition and subtraction".

A ring is an algebraic structure (R,+,0,-,*) where (R,+,0,-) is an abelian group with identity 0 and * is an associative operation that satisfies the distributivity identities (x+y)*z=x*z+y*z,x*(y+z)=x*y+x*z. A ring is said to have a unit 1 if it satisfies the identity x*1=1*x=x.

A ring is said to be commutative if it satisfies the identity x*y=y*x. Do not think about the axioms too hard. When someone talks about commutative rings with unity, just think about the integers where +,* are your standard addition and multiplication.

A field is a commutative ring with unity such that if x is not 0, then there is some y with xy=yx=1; in this case, y is the inverse of x, and we usually denote the inverse of x by x^(-1). In other words, a field is a commutative ring where you can always divide two elements as long as you don't divide by zero. Examples of fields include the field of rational numbers, real numbers, complex numbers, rational functions (or meromorphic functions).

Finite fields: Suppose that p is a prime number. Then the collection of integers {0,1,2,3,...,p-2,p-1} forms a field that we denote by F_p. Here, addition and multiplication are taken modulo p. For example, if p=13, then
6+8=14=1 mod p, so we would say that 6+8=1. Furthermore, 6*8=48=9 mod 13, so we would say that 6*8=9.

We can now take polynomials over a finite field, but we will consider two polynomials to be distinct if they have different expressions even if they represent the same function. For example, the polynomials x^p and x represent the same function in the finite field {0,1,2,...,p-1} of integers modulo p. We say that a polynomial over some field is irreducible if it cannot be factored as a product of two smaller polynomials.

Now suppose that p=2. Now the field F_2 of integers modulo 2 is just the collection {0,1} where + represents the XOR operation and * represents the AND operation. We can extend this field to a field with 256 elements. Consider the polynomial f(x)=x^8+x^4+x^3+x+1. This is the Rijndael finite field. Then the collection of polynomials of degree at most 7 over the field F_2 itself forms a field. The sum of two polynomials of degree at most 7 has degree at most 7, so addition makes sense. If r(x),s(x) are polynomials of degree at most 7, then r(x)*s(x)=f(x)a(x)+b(x) where b(x) has degree at most 7. Here b(x) is the remainder that you get when you divide r(x)*s(x) by 7. In this case, we would just say r(x)*s(x)=b(x) in the Rijndael finite field.

Everything that I did not explain properly will be explained in a proper abstract algebra text.

I am tired of typing, so I will only explain doubly stochastic matrices after the Rijndael finite field is properly understood. I will give a link to the code after the Rijndael finite field and stochastic processes are understood.

-Joseph Van Name Ph.D.

[larry_vw_1955]

It seems like NIST really just wants to justify spending a lot of resources with its post-quantum cryptography competition. This is not good for cryptography, since I would rather use a more classically secure and more efficient digital signature algorithm than a sketchy digital signature algorithm. The NIST standardization gives people a false sense of security for cryptographic algorithms (except for hash-based signatures which actually are secure). And the NIST has fallen into the entire quantum hype while completely ignoring reversible computation with this cryptographic contest. Don't give into hype.

yeah at first i thought maybe they would come up with something special but as time has gone on, it's become painfully clear that they really are clueless. they don't know what they're doing and that's dangerous! that's my opinion of course. NIST did an ok job in selecting AES but that hasn't translated over too  well in picking a PQC encryption signature thing. not at all. I guess they thought it would be just as easy. I guess not! Plus it's taking forever and you just know that whatever they end up choosing will be out of date by the time quantum computers arrive on the scene anyway and it will need to be revamped probably   of course that is assuming QC ever do arrive on the scene, I know you're skeptical about that happening. But IBM was in the news lately: https://arstechnica.com/science/2023/12/ibm-adds-error-correction-to-updated-quantum-computing-roadmap/

I think IBM is going to eventually get a usable QC out the door. No doubt about that. All these other companies I wouldn't know but IBM when they commit to something they usually see it through.

The method most commonly tested today (called a "surface code") can require up to 4,000 hardware qubits to host 12 logical qubits; the scheme described in the manuscript can do so using only 288 hardware qubits.

If IBM can get it down to only 288 then maybe there's hope. But it can't be taking 1000 qubits to form a single logical qubit. That's way too many.


Compare when IBM invented the Deep Blue chess computer. nothing like that had ever beaten a world champion before and it destroyed Gary Kasparov at the chess board. ushering in a new era in chess computing which today there are far more powerful chess computers. even on your phone. but IBM was the first. proving it could be done. They'll do the same thing with Quantum.