CRYPTOGRAPHY MATH PROBLEM
When my dad was understanding the basics of cryptography, he came across an intriguing problem. Not only was the problem about cryptography but there was math required and my dad thought that this would be a great problem to discuss with me.
“There are 2 32-digit hexadecimal (base 16) numbers. What is the probability that the last 20 digits of both numbers collide (same) irrespective of whether the first 12 digits are the same or different.”
My dad had to do some explaining before the problem could make sense to me. But after all confusion was cleared, I thought that this would make a simple probability question.
In probability, the denominator represents the total number of possible outcomes, while the numerator represents the number of favorable outcomes. In this case, the total number of possible outcomes is
16³²*16³²
This is the total number of outcomes due to the fact that each 32-digit number has 16 cases for each digit because the number is in base 16 meaning that the first digit has outcomes
0, 1, 2, 3 ,4 ,5, 6 ,7, 8, 9, A, B, C, D, E, and F.
There are 16 cases for each favorable outcome for the first digit. Meaning there are 16² cases for the first 2 digits. This applies to the very last digit. Meaning that the total outcome would be 16³² for both numbers. Also for each 32-digit hexadecimal number, there are 16³² cases, thus proving that in total there are 16³²*16³² cases.
The denominator is found. All that is left is to find the numerator.
In order to find the numerator, the favorable cases have to be found. The problem asks us to find the probability that the last 20 digits of both numbers are the same. Now to find this, let’s say that we have our first number(16³² cases). In order to find the second number that fits the problem’s criteria we have to find the cases where the second number has exactly the same last 20 digits. The number of cases of that happening is:
16³²*16¹².
The 16³² is just the probability for the first number meaning that the favorable cases for the second number is 16¹².
Why?
The first 12 digits have 16 cases for the second number for each digit because they don’t have a given criteria that determines whether they have to be the same or different from the first number, meaning that they are free. But for the last 20 digits of the second number, they must be the same as the last 20 digits of the first number meaning that there is only one case for each of the last 20 digits of the second number. The computation would look like this:
16*16*16*16*16*16*16*16*16*16*16*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1=16¹²*1²⁰=16¹²
To finally recap, the denominator is 16³²*16³², and the numerator is 16³²*12¹².
The final probability is : (16³²*16¹²)/(16³²*16³²). Simplify and the answer comes down to 16¹²/16³²=1/16²⁰
Get Akshaj Narayan’s stories in your inbox
Join Medium for free to get updates from this writer.
Even though the mathematical answer to the question has been found, the title of this write-up is “Cryptography math problem”.
Where has any cryptography been involved in this question?
The problem given was:
“There are 2 32-digit hexadecimal (base 16) numbers. What is the probability that the last 20 digits of both numbers collide (same) irrespective of whether the first 12 digits are the same or different.”
This directly connects to cryptography because public-key cryptography uses a pair of keys: a public key and a private key. In Bitcoin, the private key is 32 bytes (256 bits, or 64 hexadecimal digits). The public key is derived from the private key using elliptic-curve mathematics.
The private key is kept secret, while the public key can be shared with others. The public key can be derived mathematically can be derived from the private key using a specific formula.
Public Key=Private Key*G
What the “G” stands for here is the generator (or base point) of the elliptic curve. It is a specific point on the curve that is fixed by the cryptographic system. In simple terms, “G” it is a known constant on the elliptic curve.
So you can think of it as:
Public key (Q) = Private key (d)*G
Here, dG means elliptic-curve scalar multiplication.
For example, if d=5, then conceptually:
5G=G+G+G+G+G
using the special addition rules for points on the elliptic curve.
So G is basically the fixed “starting point” that the private key operates on to produce the public key.
On the other hand the public key cannot be derived into a private key. Private key to public key is a strict one-way mathematical formula.
In real life, think of this as ice-cream. When ice-cream melts it turns into liquid. It cannot go back to its original form: the frozen ice-cream.
This is a great security system but there is one major problem to it: quantum computers. These computers have extremely fast computations far faster than a regular computer.
With more and more of these computers the cryptography system can eventually break. But still it will take millions of years because of the extraordinarily small chance it will take to find a private key.
In general, this simple probability question about matching hexadecimal digits into large numbers, can illustrate an important idea in cryptography: in theoretical terms there is a chance that the cryptographic security system fails, but in practical terms it is almost impossible for the system to break.
