Skip to main content
Software Engineering

Return to Question

Tweeted twitter.com/StackSoftEng/status/1367172982662197256
expanded it a bit
Source Link
Anon
Anon
  • 3.6k
  • 3
  • 30
  • 49

Is it possible to store N bits of unique combinations, in N-1 bits, guaranteeing with apodictic certainty that no collisions would occur? If not; why does MD5 get reprimanded for collissions?

Regarding cryptography and the issue of collisions, I posed a question as to whether it was ever possible to store every single possible combination of a bit array of a particular size, in a bit array that was at least one bit smaller, with apodictic certainty that no collision would occur.

The answer given to me by one fellow was no, and he used the following example:

Given 4 bits
0000
It has 16 possible combinations
Try storing 16 possible combinations in 3 bits:
000

As an aside, I imagined that if "Qubits" ever took off, that this could perhaps be done.

In any case, whileWhile this was seemingly obvious on the smaller scale, I wonder that if you scaled up, whether this would remain true, given that more bits will offer far more flexibility and options ( and yet conversely you requiring more combinations to account for ). I have a hard time imagining it NOT remaining true, however perhaps there is something I am overlooking.

So againWorking under the presumption that this is not possible; Why is it that md5 is reprimanded for generating collisions: https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities

Is it possible to store N bits of unique combinationsWhen frankly given the principle, in N-1 bits? Unique meaning that you guarantee with apodictic certainty that literally no collision is possiblehash should be immune to this problem?

Thanks.

Is it possible to store N bits of unique combinations, in N-1 bits, guaranteeing with apodictic certainty that no collisions would occur?

Regarding cryptography and the issue of collisions, I posed a question as to whether it was ever possible to store every single possible combination of a bit array of a particular size, in a bit array that was at least one bit smaller, with apodictic certainty that no collision would occur.

The answer given to me by one fellow was no, and he used the following example:

Given 4 bits
0000
It has 16 possible combinations
Try storing 16 possible combinations in 3 bits:
000

As an aside, I imagined that if "Qubits" ever took off, that this could perhaps be done.

In any case, while this was seemingly obvious on the smaller scale, I wonder that if you scaled up, whether this would remain true, given that more bits will offer far more flexibility and options ( and yet conversely you requiring more combinations to account for ). I have a hard time imagining it NOT remaining true, however perhaps there is something I am overlooking.

So again:

Is it possible to store N bits of unique combinations, in N-1 bits? Unique meaning that you guarantee with apodictic certainty that no collision is possible?

Thanks.

Is it possible to store N bits of unique combinations, in N-1 bits? If not; why does MD5 get reprimanded for collissions?

Regarding cryptography and the issue of collisions, I posed a question as to whether it was ever possible to store every single possible combination of a bit array of a particular size, in a bit array that was at least one bit smaller, with apodictic certainty that no collision would occur.

The answer given to me by one fellow was no, and he used the following example:

Given 4 bits
0000
It has 16 possible combinations
Try storing 16 possible combinations in 3 bits:
000

While this was seemingly obvious on the smaller scale, I wonder that if you scaled up, whether this would remain true, given that more bits will offer far more flexibility and options ( and yet conversely you requiring more combinations to account for ). I have a hard time imagining it NOT remaining true, however perhaps there is something I am overlooking.

Working under the presumption that this is not possible; Why is it that md5 is reprimanded for generating collisions: https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities

When frankly given the principle, that literally no hash should be immune to this problem?

Source Link
Anon
Anon
  • 3.6k
  • 3
  • 30
  • 49

Is it possible to store N bits of unique combinations, in N-1 bits, guaranteeing with apodictic certainty that no collisions would occur?

Regarding cryptography and the issue of collisions, I posed a question as to whether it was ever possible to store every single possible combination of a bit array of a particular size, in a bit array that was at least one bit smaller, with apodictic certainty that no collision would occur.

The answer given to me by one fellow was no, and he used the following example:

Given 4 bits
0000
It has 16 possible combinations
Try storing 16 possible combinations in 3 bits:
000

As an aside, I imagined that if "Qubits" ever took off, that this could perhaps be done.

In any case, while this was seemingly obvious on the smaller scale, I wonder that if you scaled up, whether this would remain true, given that more bits will offer far more flexibility and options ( and yet conversely you requiring more combinations to account for ). I have a hard time imagining it NOT remaining true, however perhaps there is something I am overlooking.

So again:

Is it possible to store N bits of unique combinations, in N-1 bits? Unique meaning that you guarantee with apodictic certainty that no collision is possible?

Thanks.