Friday, February 11, 2011

Combination Locks

A usual combination lock that I used in high school had digits going from 0 to 39, a total of 40 digits. It was circular in shape. It required a three digit combination to open it. If someone had to break open the lock and do so by brute force then they would need to try 40 * 40 *40 possible combinations: 64000 combinations ... that's a lot.
But I wondered how accurate the lock really is, I took the combination for my lock, let's say it was 10-20-30 and then tried combinations that were just 1 digit away:
  • One digit difference in any one of the three digits from the 10-20-30 combination code.
    9-20-30
    11-20-30
    10-19-30
    10-21-30
    10-20-29
    10-20-31
  • One digit difference in any two of the three digits from the 10-20-30 combination code.
    9-19-30
    11-21-30
    10-21-31
  • One digit difference in any three of the three digits from the 10-20-30 combination code.
    9-19-29
    11-21-31
Every single one of them managed to open my lock!

Two digits away didn't work though *phew*

So I wondered what is the real chance that someone has at cracking the code? Its definitely not as high as 64000.

Let's say I start at 0-0-0 and it doesn't work then neither will these:
[39|0|1]-[39|0|1]-[39|0|1]
Ok then I move on to 3-0-0 and it doesn't work then neither will these:
[2|3|4]-[39|0|1]-[39|0|1]
...
Eventually I should be close to finishing the 1st round of testing by the time I'm trying 36-0-0, which rules out:
[35|36|37]-[39|0|1]-[39|0|1]
And the last thing to test would be only 38 for the 1st position for the 1st round:
38-0-0 I admit there's some overlap cause it will rule out some things that we already tested but nothing we can do about that, just haven't tried 38 yet so got to test it.

Damn there should be a formula by now, can't think of anything yet.

All right let's simplify, what if the lock was only a 6 digit circular lock? Then 0 would cover [5|0|1] and 3 would cover [2|3|4] and that's all the digits. So if I tried out: 000, 003, 030, 033, 300, 303, 330, 333 ... I would have broken the code somewhere with that because (overlap or not) that just made sure that all the unique combinations are covered. And that looks an awful like a binary sequence. Since with 0 and 3, I covered all the digits that were one higher or one lower in the 6 digit lock ... it seems I only needed to think of 0 and 3 as the only symbols available to me ... so given 6/3 = 2 base and three place to fill that's like: 2^2 * 2^1 * 2^0 = 8 and that is exactly how many combinations I had to try to break a 6 digit circular lock.

Does that mean for a 9 digit lock I would end up with a 9/3 = 3 base and the # of combis to try to fill in 3 places will be 3^2 * 3^1 * 3^0 = 27. Yeah I guess that works! "Guess" being the operating word here.

So now what about 40 digits?
Lets make it a little simpler again. Try with 39 digits, which means 39/3 = 13 base and that means we would have 13^2 * 13^1 * 39^0 = 2197 combis to try.

What would the additional 40th digit add to the mix?
Here's a screwy guess:
(40th-Symbol)-(base-13-symbols)-(base-13-symbols)
1^0 * 13^1 * 13 ^ 0 = 13

So I'd say 2197 + 13 = 2210 combis to try is a whole lot less than 64000 :)

2 comments:

  1. Dude. There are articles on how to crack open older model combination locks. I opened a lock that I forgot the combination to in 30 minutes. It didn't take that many tries.

    ReplyDelete
  2. I just wanted to solve it from a probability perspective that is all. The math is what intrigued me.

    ReplyDelete