Skip to main content
2 of 2
explanation of math added

It will be significantly less. I would just set up a recurrence relation for this like so:

A(n) = A(n-1) - C * 2 ^ (N-1) and A(0) = size of keyspace, say 62^12

lets set C = 3.0*10^12 for hashes computed the first year and assume computing power doubles every year.

Plugging this into wolfram alpha yields this function solution for the recurrence relation:

recurrence relation...

f(x) ~= 3.22627x10^21 - 3.0x10^12 * 2^x

Solve f(x) = 0 for x:

x = lg (3.22627x10^21 / 3.0x10^12) where lg is log base 2

x ~= 30.00226 years

Cracked in 30 years, but that's a lot of silicon, no wasted work, and you would need a method to seemlessly integrate new hardware into the running program without stopping it.


Explanation:

So we have the original key space size: 62^12 and a hypothetical machine capable of incorporating Moore's Law, somehow.

My original math was off a bit. For some reason I did 3.0 x 10^9 * 1000 = 3.0 x 10^12 for calculations in a year, but it should be 3.0 x 10^9 * 3600 (seconds / hour) * 24 (hours / day) * 365 ( days / year). Anyways, that's our initial speed, which according to Moore's law will double every year. I'm going to keep the original mistake for consistency in explanation.

So in the first year, we perform 3.0x10^12 hashes of the 1.0x62^12 maximum hashes needed (assuming worst case scenario). In the second year, Moore's law applies and now we do 6.0x10^12 hashes in the second year, which gives us cumulatively 9.0x10^12 hashes calculated so far. The hashes we have left to do are found via subtraction from the whole number of hashes. We'll run the program until there are no more hashes to find.

A(N) = A(N-1) - C * 2^(N-1)

A(N) is the number of hashes remaining after this year

A(N-1) was the number of hashes previously remaining before this year

C is the initial speed

N is the number of the year (first, second, third, etc).

So every year the speed doubles, which is the 2^(N-1) part of the equation. C is the initial speed for the first year, so we have C * 2 ^ 0 = C * 1 = C. In the second year, the speed has doubled once, so we have 2 * C. In the third year, speed has the doubled from initial twice, so we have 2 * 2 * C = 2^2 * C = 2^(N-1) * C since N is 3. This forms a recurrence relation for the number of hashes left to compute.

Using a combinatorics book, you can transform a recurrence relation into a generating function. Or wolfram alpha can do it for you, if you're like me and remember generating functions can be found but have forgotten how to find them since that math class seven years ago.

Anyways, you get a function of x where x is still the year being iterated. f(x) is how many hashes are left to compute. We're done when there are 0 left. So we solve f(x) for x when f(x) = 0. The last part is algebra.

I might be off base here, but it makes sense to me :)