DID SATOSHI NAKAMOTO PLAN THE DEATH OF BITCOIN? — CHAPTER II: “MODULAR MATHEMATICS AND RSA”
February 30, 2023, 12:00 CET — The news is spreading like wildfire. Threads are multiplying on Twitter to present on-chain evidence of the night’s events. Crypto-experts are unanimous and present no doubt. Satoshi Nakamoto’s wallet is empty.
More alarmingly, he is not the only one. Other movements have just been detected on wallets from the Satoshi era. Notably a certain wallet belonging to the late cypherpunk Hal Finney, known for receiving the first bitcoin transaction in history. Panic grips the market, Bitcoin’s volatility explodes and exchanges post $14,000. Internet users start to consider the worst. If the wallet of our late Hal Finney has also been emptied, there can only be two explanations. Either Nakamoto had access to his private key. Or we are witnessing an event of unprecedented proportions, not only announcing the death of Bitcoin.
TABLE OF CONTENTS
- Clock and modular mathematics
— Forget everything you know, from now on, 12 = 0
— What are the advantages for cryptography? - RSA encryption
— The construction of public and private keys
— How to transform mathematics into an electronic signature
— Robustness and property of RSA encryption
In my previous article, I introduced you to the principle of electronic signature and the basic conditions it must meet to allow your authentication on the blockchain as well as the Diffie-Hellman key exchange laying the foundations of asymmetric cryptography. Today, we’re going to dive into the first cryptographic protocol that enables robust electronic signatures, RSA encryption.
But before that, remember, I gave you a slight reprieve on modular mathematics. “This time, you won’t escape” — I said in a Machiavellian voice from behind my keyboard. But don’t worry, it’s quite simple to understand, you do it every day without knowing it!
Clock and modular mathematics
Forget everything you know, from now on, 12 = 0
Last week, I told you about the modular mathematics that was used in the Diffie-Hellman key exchange to simplify the calculations that our two interlocutors Alice and Bob have to do. However, its implication in RSA encryption is much more important, because it intervenes directly in the encryption and decryption of the messages between our two speakers, so I will try to explain it to you.
What would happen if we discovered that 12 ≡ 0?
(I use the triple equal sign here for mathematical rigor. And yes, this is not the symbol of Ethereum although it is very close, understand here simply 12 = 0. The triple equals sign will be used as soon as we talk about an equality in a modular system).
Spoiler, this would upset our way of calculating, but you already experience it every day!
For the more mathematical among us, this should remind you of the trigonometric circle. On this circle 2π is equal to 0, the same for 4π, 6π, etc. The same is true for our clocks, 17 hours is also equal to 5 hours (unlike the English-speaking country, we use 17 hours for 5pm). Modular mathematics amounts to wrapping the line of all numbers around a circle in a predefined cycle. 12 in the example of our clocks. We say that we are in a mathematics modulo 12.
What are the advantages for cryptography?
“Ok Foudres, that’s very good, but what application in cryptography? I still don’t see the connection” you might ask.
Patience, I’m coming to that! In the Diffie-Hellman key exchange, we were doing calculations with powers of a gigantic number, here is what happens when we apply a modulo 12 mathematics.
Do you see what this will do? Modulo 12 mathematics allows us to simplify 5² by 1. From this calculation, we can simplify any power of 5:
- For any even power: 5^(even number) will equal 1,
- For any odd power: 5^(odd number) will be equal to 5.
It is this little mathematical trick that allows to use power functions with cryptographically large numbers. A little test to see if you understand the logic:
In modulo 12 math, what is the result of 5⁹⁷⁴⁸⁹⁶²³² ?
We will write the result like this: 5⁹⁷⁴⁸⁹⁶²³² ≡ 1 (mod 12) — with mod for modulo.
Easy, right? (Yes, I’m totally trying to convince myself that my explanations were clear.) Now that modular math is no longer a dirty word to you, we can move on to RSA encryption. Hang on, because this will be the most complex part of my series on cryptography!
RSA encryption
The construction of public and private keys
RSA encryption, named after the initials of its three inventors, Ronald Rivest, Adi Shamir and Leonard Adleman, uses asymmetric cryptography based on the work of Diffie-Hellman. Where Diffie-Hellman key exchange only allows the creation of an encryption key without a prior unencrypted agreement, the RSA protocol goes further by directly allowing the exchange of information via public key encryption. The RSA protocol introduces trapdoor functions.
They have the same properties as the one-way functions explained in my previous article, except that they have what is called a “trapdoor”, a number allowing the reversibility of the encryption function.
Alice and Bob, still them, want to exchange and sign a document and have never interacted in the past. Alice will create a key pair, a private key that will be used by Alice to sign Bob’s document, and a public key, which will be used to verify that the signature is from Alice.
(In advance, don’t bother too much with the mathematical details in red if you have trouble understanding them. Just remember the logic).
So Alice has three numbers in her possession. The public number “N”, her public key “d” and her private key “e”. These last ones are all calculated thanks to the numbers “p” and “q” that she must absolutely destroy in order not to compromise her private key!
How to transform mathematics into an electronic signature
This is where the modular mathematics explained above will work its magic:
- Bob wants to make Alice sign a document “M”. Bob sends her the number 4 which is the hash of the document, its digital fingerprint.
- Alice performs the calculation: C = M^e (mod N) and sends the result C, which represents her signature, and the number “N” to Bob.
- Bob performs the calculation: C^d (mod N) or M^e^d (mod N). If thanks to this calculation Bob finds the digital fingerprint of the document “M” as he sent it to Alice. This means that Alice has signed it with her private key.
Thanks to our modular mathematics, we have in summary, an encryption by Alice’s private key and a decryption by her public key:
Document ^ (Alice’s private key) ^ (Alice’s public key) = Document
If you remember the “power functions” property introduced last time, the reverse is totally possible. Bob can send an encrypted message to Alice using her public key that only Alice can decrypt. But this is not equivalent, because nothing will allow Alice to be sure that it is Bob who has sent her the encrypted message, since it is with his public key. This is called the “man-in-the-middle” attack.
To address this problem, Bob will also have to sign the message with his own private key before encrypting it with Alice’s public key. Then Alice will be able to verify its origin with Bob’s public key, and decrypt it with her private key.
Robustness and property of RSA encryption
The robustness of this encryption comes from the impossibility for a third party to retrieve Alice’s private key using only the public numbers “N”, “C” and “d” in a reasonable time. This comes from the complexity, and the unreasonably long computation time, needed to perform the prime factor decomposition of the public number “N” in order to find “p” and “q”. Numbers that would allow to easily find Alice’s private key by brute force.
Today, we know how to find this decomposition by “brute force” with numbers of 795 bits. But the commonly used RSA keys are of 2048 bits, which still leaves us some margin. However, there are some doubts because of a quantum algorithm that can break RSA relatively easily, the Shor algorithm.
To come back to the electronic signature, here, Bob challenges Alice to sign the hash of the document “M” with his private key, if the latter does not find this hash identically via the verification with Alice’s public key. This is because it is not Alice who signed the document!
The signature thus meets all the criteria mentioned in the previous article, namely :
Authenticity : Alice is authenticated by her private key that only she has.
Forgery-proof: Alice’s private key is mathematically forgery-proof, because it is protected by the impossibility of performing a prime factor decomposition.
Non-reusability : the C-signature is unique, because it is derived from the document and from Alice’s private key.
Unalterability: the C-signature serves as a proof as it is derived from the document itself. If the document is modified, Alice will only have to sign it again and show that her signature is different from the previous one.
Irrevocability: Since the above rules are respected, Alice cannot deny her signature.
That’s enough convoluted formulas for today, I can feel your eyes getting heavy after all these mathematical pirouettes. Next time, we’ll dig into Bitcoin and the big boss of encryption protocols, the ECDSA protocol, and then we’ll finish on hashing and its role in proof of work!
_________________________________________________________________
February 30, 2023, 4:00 pm CET — With sweaty hands and sweat on their foreheads, cryptographic experts are working hard to try to get to the bottom of the situation. They review all the mathematical concepts and protocols of cryptography in search of a flaw, a detail, that would have gone unnoticed for more than fifty years. While the answer must lie right there in front of them, the lack of understanding leads to increasing accusations that Google and China have used their quantum computers to send Bitcoin to the grave. The grip is tightening, but this enigma is still unfathomable for the time being. Its resolution is unfortunately not yet within our grasp.
This article is a translation of my article originally posted on Journalducoin ! Thanks to them for allowing its publication in English ⚡
https://journalducoin.com/bitcoin/mouvement-wallet-satoshi-mort-bitcoin/
