# Cracking the system

Months of preparation and coding has led you to this day. Slowly but surely you worked your way into the security of the most secure system in the world: the computer override for the vault containing the Coca-Cola secret formula. You have one last security protocol to bypass, and you are in.

Ready and able, you fire up your terminal. You slowly work through the series of backdoors and wormholes you put in place to get to the final gate. When you try to access the program to unlock the vaults.

You are met with a familiar message.

Greetings. Please input the key associated with lock #55476

You are prepared for this. You have come to this block numerous times. Every day the lock changes. Every day a new key, but now you know the algorithm to get the key and open the lock.

In prior attempts, you have received a number of locks. You brute forced your way to the key, but by the time you had the correct value, the system had reset for the day and you were met with the message

I'm sorry, but lock #XXXXX is no longer active. Please enter the key for lock #YYYYY

It took you a while, but you realized that XXXXX and YYYYY were the old lock and new lock respectively. This system only popped up the message when you put in the correct key for the old lock.

So, you collected locks and keys. You had the following table:

 LOCK    |    KEY
66453   |    25916670
12345   |     4777515
33200   |    14342400
55475   |    20137425
43256   |    16913096
73553   |    28759223
34875   |    13113000
99858   |    36348312


Using this table, you calculated the algorithm to generate any key for any lock.You quickly enter the key and you are in. Congratulations, you now own the Coca-Cola secret formula!

There is a small degree of computer knowledge potentially needed here, although it is possible to create the solution without any computer knowledge.

HINT 1:

Each digit is important in its own right, as is the number as a whole.

HINT 2:

EDIT

I added more keys to the table to try and eliminate any false positives on the algorithm.

• I'm so close to the answer, yet so far! I know how to crack the password with a dozen of attempts, but that's not enough for a general solution! – leoll2 May 21 '15 at 16:54

The first thing to notice is that each of the keys is divisible by the corresponding lock. Thus, we have:

LOCK x MULT =   KEY
---------------------
66453 x 390 = 25916670
12345 x 387 = 04777515
33200 x 432 = 14342400
55475 x 363 = 20137425
43256 x 391 = 16913096
73553 x 391 = 28759223
34875 x 376 = 13113000
99858 x 364 = 36348312


Based on the hints, the multiplier probably depends on the ASCII codepoints of the digits of the lock. We can tell that:

• Since the multiplier is greater than 255, it's not a bitwise combination of the characters.

• The multiplier is not a linear function of the digits (the system would be inconsistent).

I started operating under the assumption that the function was a sum of a single function applied to each digit. We then have ten function values to determine, and 8 equations (lock/key pairs).

I then noted that, on average, the value of the function would have to be somewhere in the mid 70s. That would put the function values right in the range of uppercase ASCII letters. Restricting ourselves to the integer codepoints in the range 65 to 90, we can solve for the possible values of the function using the following Mathematica snippet (with pairs being a matrix of the locks and keys):

Grid[x /@ Range[0, 9] /.
FindInstance[
Join[Total[x /@ IntegerDigits[#1, 10, 5]] == #2/#1 & @@@ pairs,
Thread[65 <= (x /@ Range[0, 9]) <= 90]], x /@ Range[0, 9],
Integers, 10000]] /. {i_Integer :> FromCharacterCode[i, "ASCII"]}


The possible values are:

0 1 2 3 4 5 6 7 8 9
-------------------
Y I N X J J M C I H
Y I N X L H M G E M
Y I N X N F M K A R
Z O T T B J S K M D
Z O T T D H S O I I
Z O T T F F S S E N
Z O T T H D S W A S


One of the possible solutions (#6, second-to-last) has a curious relation to the digits:

d  f[d]
----------
0  Z(ero)
1  O(ne)
2  T(wo)
3  T(hree)
4  F(our)
5  F(ive)
6  S(ix)
7  S(even)
8  E(ight)
9  N(ine)


Thus, the key for lock 55476 is simply:

5 > F(ive)  > 70
5 > F(ive)  > 70
4 > F(our)  > 70
7 > S(even) > 83
6 > S(ix)   > 83
----------------
376
x 55476
----------------
20858976

• ... The vault swings open! But wait, it's a decoy! This is the formula for New Coke! – elf337 May 27 '15 at 7:56

20137788

My algorithm works for the first 5 data blocks, but then I lose it for the last three. Are you sure you used the right numbers for the last three? ;)

Edit: My attempt at the algorithm:

Let L1, L2...L5 be the 1st, 2nd... 5th digits of the lock code, and let K be the key:

K = L * (-148*L1 + 239*L2 - 212*L3 + 5*L4)/3

Probably not the right direction, but it did work perfectly for the first 5 keys.

Edit 2: Under the same logic, you could use regression to find something close for all of the provided lock numbers. The closest equation I could find for all 8 locks is:

K = L * (390.8 + 15.68*L1 - 9.007*L2 + 16.32*L3 - 13.51*L4 + 2.452*L5 + 1.174*L1*L2 - 3.674*L1*L3)

The result is one of two key (rounding the equation up or down before multiplying by L),assuming the actual algorithm uses a whole number before multiplying by L.

Two possible codes result:

20248740 or 20304216

If neither of those are right, it's probably time to quit :)

• Completely sure. Would you mind posting your algorithm? – tfitzger May 21 '15 at 19:37
• You are correct that each digit needs to be processed individually. – tfitzger May 21 '15 at 19:59
• Excellent job determining that K involved a multiplication by L, that led me to my solution; thank you! – 2012rcampion May 27 '15 at 3:21

The key associated with lock #55476 is:

21635640

It seems to be too simple (at least for the Coca Cola recipe), but at least with the small example data set provided, the key k for each lock l can be computed with the following source code (C/Java/C# syntax):

k = l*(376+((l&2)==0?10:0)+((l&6)==0?1:0)+((l&192)==0?0:4));

• How do you know at this point there are no other potential additions? The question seems to infer after those 5 keys, any other key is determined for sure. – Quark May 21 '15 at 18:11
• That is not the correct answer. As I said, some minor computer knowledge is good, but not necessary. You don't need to be able to program to solve the answer. – tfitzger May 21 '15 at 18:19
• @Quark I realized that I gave too small a sample set. I added some more keys to be able to try to remove false positives on the algorithm – tfitzger May 21 '15 at 18:28
• @tfitzger As I indicated, I did even assume that the answer is not correct. I just wanted to show that based on a small number of examples, there are probably lots of ways to get from the lock number to the key. Is Quark's assumption correct, that the locks and keys in the example list build a sequence, or can each key be computed from the lock without knowing the sequence of the previous locks/keys? – jarnbjo May 21 '15 at 18:56
• The keys can be calculated independently of each other. – tfitzger May 21 '15 at 19:12