Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Any public key decryption can be decrypted given enough time and computing power. Is there a metric or term for this? Something like

it would require on average 2^43 1024 bit hashes to find private key 'I' based on public key 'U'?

Is there a term that would sum up this average amount of work?

share|improve this question
add comment

2 Answers 2

There is also big-O notation (aka order notation) for mathematically measuring computational complexity, which is used in cryptography too. Check Wikipedia Big O notation article for details.

share|improve this answer
add comment

There are multiple metrics for work or effort needed:

  • Amount of operations it takes (one operations is, for instance, one invocation of hash function or number of modular multiplication operations)
  • Amount of money it takes
  • Amount of memory it takes
  • Amount of time it takes
  • Strength in bits

Amount of operations

Usually, if amount of operations is large enough so that it cannot be done with all the energy in the solar system even if single operation consumed just one electron, it looks safe enough.

Brute forcing AES-256 bit key is too expensive in amount of operations

Amount of money

If it costs too much to build device for breaking encryption, people assume it cannot be done, or that it is prohibitingly expensive.

Excellent paper of PBKDF algorithms, including cost of breaking a key in a year.

Amount of memory

Sometimes it would be feasible for large organizations to break algorithm according to how long it takes to break it (in number of operations), but it may be that breaking the algorithm takes so much temporary space that it cannot be done, because that temporary space is no where to be found.

Question on duration for attacking Two-Key Triple-DES using all RAM ever built.

Amount of time

Various parties like Prof Arjen Lenstra make estimates how long various kinds of keys take to break, based on the best attacks currently known. These are equations based on algorithm and key length.

These estimates can be found on www.keylength.com, along side other estimates.

Strength in bits

Some parties like NIST estimate algorithm strength in bits. This is: amount of bits symmetric encryption algorithm of equivalent strength against attempt to break would have.

These estimates are based on previous, especially number of operations required.

NIST SP 800-57 Part1: Recommendation for Key Management – Part 1: General contains necessary information to convert various algorithms to bits of strength to make it easier to compare algorithms in apples-to-apples manner.

How strong algorithms we should use then?

Algorithms with strength around 56-64 bits have been typically broken. (Like RSA 768. => Don't use.) Algorithms with strength around 80 bits typically have not been broken, but are "on edge" and therefore their use is no more recommended. (Like RSA 1024. => Avoid.). Algorithms with strength 112 bits (like RSA 2048) or more are considered to be safe (according to NIST), until beyond 2030, as long as they are used properly (single key has life time of about 1-2 years etc.)

More exact estimate on cracking RSA can be found here: How to estimate the time needed to crack RSA encryption?. The amount of time to crack other public key crypto will be different. However, if you use key sizes which are currently recommended, as far as public knowledge on cryptography goes, work required is infeasible.

share|improve this answer
    
Nice answer +1. –  obelia Jan 7 at 0:14
    
And all of the above can basically be summed up into "security level", for a general term that's applicable almost anywhere. –  Reid Jan 7 at 16:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.