Security of cryptographic hash functions: Difference between revisions

Revision as of 09:20, 15 May 2014

Revision as of 19:25, 4 June 2014

Line 14:

The basic question is the meaning of "'''hard'''". There are two approaches to answer this question. First is the intuitive/practical approach: "hard means that it is almost certainly beyond the reach of any adversary who must be prevented from breaking the system for as long as the security of the system is deemed important."

The second approach is theoretical and is based on the [[computational complexity theory]]. If problem A is hard, there exists a formal [[Reduction (complexity)|security reduction]] from a problem which is widely supposed to beconsidered unsolvable in [[polynomial time]], such as [[integer factorization]] problem or [[discrete logarithm]] problem.

However, non-existence of a polynomial time algorithm does not automatically ensure that the system is secure. It is equally important to choose the parameters sensibly (e.g. a length of the numbers that the system works with). For instance, factoring 21 is easy although in general [[integer factorization]] is considered a hard problem.