Key and Lock Re-matching Logic

Problem Introduction

Picture a hotel with N rooms. Each room has a unique lock, and there is exactly one key that opens that lock. Now imagine a security breach. A guest's key card was cloned, or a master key was stolen. The hotel manager decides to completely re-match the keys to the locks—but here is the critical rule: no key should open its originally matched lock.

Why? Because if an intruder has already compromised the original key-lock mapping, keeping any key-lock pair unchanged would leave a security vulnerability. The manager needs a total scrambling: every key must be reassigned to a different lock.

In how many ways can this be done? For a small hotel with 4 rooms, there are 9 valid re-matchings. For a large hotel with 20 rooms, there are over 895 quadrillion possibilities.

This is not just a puzzle—it is a real-world security protocol used in physical access control, cryptographic key rotation, and even voting machine logic.

Looking to master dynamic programming for security systems? Check out our  Tutoring Page  for personalized 1-on-1 coaching.

Why It Matters

Key and lock re-matching logic is a derangement problem with high-stakes security applications:

• Hotel key card systems: After a data breach, hotels re-encode key cards so no card opens its previously assigned room. The number of possible re-encodings must be large enough to prevent brute-force attacks.

• Cryptographic key rotation: In symmetric encryption, rotating keys so no key maps to its previous cipher ensures forward secrecy.

• Physical security (locksmithing): When re-pinning locks, locksmiths ensure no key fits its original lock. The number of possible re-pinnings determines the system's security margin.

• Voting machine logic: Some electronic voting systems use derangements to randomize ballot order, ensuring no candidate appears in the same position twice.

Unlike the gift exchange or seating rearrangement problems, key-lock re-matching has a security twist: the number of valid configurations directly impacts how difficult it is for an attacker to guess the new mapping. If there are too few possibilities, an attacker could brute-force all of them.

For N = 10 locks, there are 1,334,961 valid re-matchings. For N = 20, there are 895,014,631,192,902,121—about 8.95 × 10^17. That is roughly the number of grains of sand on Earth. A brute-force attacker would need billions of years to try all possibilities.

Step-by-Step Breakdown

Step 1: Understanding the Security Constraint

Let L₁, L₂, ..., Lₙ be the locks, and K₁, K₂, ..., Kₙ be the keys that originally matched them. After the breach, we need a new mapping f such that:

• f is a bijection (each key goes to exactly one lock, each lock gets exactly one key)

• f(Kᵢ) ≠ Lᵢ for all i (no key opens its original lock)

This is a derangement of N items, but the security context adds an extra layer: the attacker knows the original mapping. Their goal is to guess the new mapping. The number of possibilities is the derangement number !N.

Step 2: Visualizing the Re-matching as a Security Graph

In this diagram:

• Solid arrows show the original (compromised) mapping that the attacker knows

• Dashed arrows show a valid re-matching (a 4-cycle: Key1→Lock2, Key2→Lock3, Key3→Lock4, Key4→Lock1)

• Red dashed arrow shows an invalid re-matching where Key1 still opens Lock1 (a fixed point)

The attacker's knowledge of the original mapping is useless because the new mapping has no fixed points. They must guess from scratch.

Step 3: Building Intuition with Security Examples

Let R(N) be the number of valid key-lock re-matchings.

N = 1 (single room): The only possible mapping is Key1 → Lock1. This is a fixed point, so it is invalid. R(1) = 0. Security implication: A single-room hotel cannot rotate keys securely. You must replace the lock entirely.

N = 2 (two rooms): Valid re-matchings:

• Key1 → Lock2, Key2 → Lock1 (swap)

• That is the only possibility. R(2) = 1. Security implication: Only one possible re-matching. An attacker could guess it with 100% certainty. Not secure.

N = 3 (three rooms): Valid re-matchings:

• (Key1→Lock2, Key2→Lock3, Key3→Lock1)

• (Key1→Lock3, Key2→Lock1, Key3→Lock2)

• R(3) = 2. Security implication: Two possibilities. An attacker guessing randomly has a 50% chance. Still not secure.

N = 4: R(4) = 9. Attacker success probability: 1/9 ≈ 11.1%. Getting better.

N = 10: R(10) = 1,334,961. Attacker success probability: ~7.5 × 10^-7 (less than one in a million). Secure for most practical purposes.

N = 20: R(20) ≈ 8.95 × 10^17. Attacker success probability: ~1.1 × 10^-18. That is like winning the Powerball lottery multiple times in a row.

Step 4: Deriving the Recurrence Relation (Security Version)

Let R(N) be the number of valid key-lock re-matchings for N rooms.

Step A: Where does Key 1 go? Key 1 cannot go to Lock 1. So it goes to Lock k, where k ∈ {2, 3, ..., N}. That is (N - 1) possibilities.

Step B: Analyze Key k's destination.
Now consider Key k (the key that originally opened Lock k). Two scenarios:

Scenario 1: Key k goes to Lock 1 (a swap)

• Key1 → Lockk, Keyk → Lock1

• These two keys have swapped locks

• The remaining (N - 2) keys must form a valid re-matching among themselves

• Number of ways: R(N - 2)

Scenario 2: Key k does NOT go to Lock 1

• Key1 → Lockk

• Keyk cannot go to Lock1 (by this scenario) and also cannot go to Lockk (original lock)

• This is equivalent to finding a valid re-matching for the remaining (N - 1) keys, with Lock1 now forbidden for Keyk

• Number of ways: R(N - 1)

Step C: Combine
For each of the (N - 1) choices for Key1's lock:

R(N) = (N - 1) × [R(N - 1) + R(N - 2)]

Base cases: R(1) = 0, R(2) = 1.

Step 5: Security Analysis Table

Let's analyze the security strength of key-lock re-matching for different hotel sizes:

For a typical hotel with 50 rooms, the number of valid re-matchings has over 60 digits. An attacker has effectively zero chance of guessing correctly.

Step 6: Naive Recursive Implementation (Security Simulation)

def key_lock_recursive(rooms: int) -> int:
    """
    Naive recursive solution for key-lock re-matching.
    
    Time: O(2^N) - Exponential, only usable for N <= 30
    Space: O(N) - Recursion stack depth
    
    This is useful for security simulations where N is small,
    but fails for real hotels with many rooms.
    """
    if rooms == 1:
        return 0
    if rooms == 2:
        return 1
    
    return (rooms - 1) * (
        key_lock_recursive(rooms - 1) + 
        key_lock_recursive(rooms - 2)
    )

# Simulate a small hotel
for n in range(1, 11):
    valid = key_lock_recursive(n)
    total = math.factorial(n)
    probability = valid / total if total > 0 else 0
    print(f"N={n:2d}: {valid:>12,} valid re-matchings out of {total:>12,} total")
    print(f"       Attacker success probability: {probability:.8f}")
    print()

Output shows the security progression from N=1 (impossible) to N=10 (very strong).

Step 7: Top-Down DP with Memoization (Security Caching)

def key_lock_top_down(rooms: int, memo: dict = None) -> int:
    """
    Top-down dynamic programming with memoization.
    
    Time: O(N) - Each N computed once
    Space: O(N) - Memo dictionary + recursion stack
    
    This approach is suitable for computing R(N) for a single
    hotel size, even up to N=1000.
    """
    if memo is None:
        memo = {}
    
    if rooms == 1:
        return 0
    if rooms == 2:
        return 1
    if rooms in memo:
        return memo[rooms]
    
    memo[rooms] = (rooms - 1) * (
        key_lock_top_down(rooms - 1, memo) + 
        key_lock_top_down(rooms - 2, memo)
    )
    return memo[rooms]

# Security analysis for a large hotel chain
# A chain with 25 rooms per hotel
r_25 = key_lock_top_down(25)
print(f"R(25) = {r_25}")
print(f"Number of digits: {len(str(r_25))}")
print(f"Attacker success probability: 1/{r_25:.2e}")

Security insight: Even if an attacker could try one billion guesses per second, they would need more than the age of the universe to guess the correct re-matching for N=25.

Ready to implement secure key rotation for your system?

 

Visit our Order Page  now to grab our exclusive Dynamic Programming bootcamp courses!

Step 8: Bottom-Up DP with Tabulation (Audit Trail)

def key_lock_bottom_up(rooms: int) -> int:
    """
    Bottom-up dynamic programming using tabulation.
    
    Time: O(N)
    Space: O(N) - Full DP array
    
    This approach is useful when you need to audit or log
    the number of re-matchings for all room counts up to N.
    """
    if rooms == 1:
        return 0
    if rooms == 2:
        return 1
    
    # dp[i] = number of valid re-matchings for i rooms
    dp = [0] * (rooms + 1)
    dp[1] = 0
    dp[2] = 1
    
    for i in range(3, rooms + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
    
    return dp[rooms]

# Security audit: How many re-matchings for each floor size?
print("Security Audit: Valid Re-matchings by Floor Size")
print("Floor (rooms)\tValid Re-matchings\tSecurity Grade")
for floor_size in [2, 3, 4, 5, 6, 7, 8, 9, 10]:
    valid = key_lock_bottom_up(floor_size)
    if valid <= 10:
        grade = "FAIL - Redesign required"
    elif valid <= 100:
        grade = "WEAK - Not recommended"
    elif valid <= 10000:
        grade = "ACCEPTABLE - For low-security only"
    elif valid <= 1000000:
        grade = "GOOD - Standard security"
    else:
        grade = "EXCELLENT - High security"
    print(f"{floor_size}\t\t{valid:>15,}\t{grade}")

Step 9: Space-Optimized Solution (Embedded Security Systems)

def key_lock_optimized(rooms: int) -> int:
    """
    Space-optimized bottom-up solution.
    
    Time: O(N)
    Space: O(1) - Only two variables
    
    This is ideal for embedded security systems (e.g., smart locks,
    hotel key card encoders) where memory is limited.
    """
    if rooms == 1:
        return 0
    if rooms == 2:
        return 1
    
    # prev2 = R(i-2), prev1 = R(i-1)
    prev2 = 0  # R(1)
    prev1 = 1  # R(2)
    
    for i in range(3, rooms + 1):
        current = (i - 1) * (prev1 + prev2)
        prev2 = prev1
        prev1 = current
    
    return prev1

# Embedded system example: Smart lock key rotation
def generate_rotation_map(rooms: int) -> list:
    """
    Generate a single valid key-lock rotation map.
    
    This is a simplified example using the "cyclic shift" method.
    For true security, use a cryptographically secure random derangement.
    """
    if rooms <= 1:
        raise ValueError("Cannot generate rotation for 1 room")
    if rooms == 2:
        return [1, 0]  # Swap
    
    # Simple cyclic shift: Key i -> Lock (i+1) mod rooms
    # This is a derangement for all rooms (a single N-cycle)
    return [(i + 1) % rooms for i in range(rooms)]

# Example for a 5-room hotel
hotel_rooms = 5
rotation = generate_rotation_map(hotel_rooms)
print(f"Key rotation map: {rotation}")
print(f"Interpretation: Key {0} opens Lock {rotation[0]}")
print(f"               Key {1} opens Lock {rotation[1]}")
# ... etc.

Real-world security note: The cyclic shift (i+1) mod N is a derangement, but it is predictable. An attacker who knows the algorithm (cyclic shift) can guess the mapping instantly. In practice, use a cryptographically secure random derangement generator that selects uniformly from all R(N) possibilities.

Step 10: Cryptographic Random Derangement Generator

import random
import secrets

def random_derangement_cryptographic(n: int) -> list:
    """
    Generate a cryptographically secure random derangement.
    
    Uses rejection sampling: generate random permutation,
    check if it's a derangement, repeat if not.
    
    Expected number of trials: 1/(1/e) ≈ 2.718
    """
    if n == 1:
        raise ValueError("No derangement exists for n=1")
    if n == 2:
        return [1, 0]
    
    while True:
        # Generate random permutation using secrets (cryptographically secure)
        perm = list(range(n))
        for i in range(n - 1, 0, -1):
            j = secrets.randbelow(i + 1)
            perm[i], perm[j] = perm[j], perm[i]
        
        # Check if it's a derangement (no fixed points)
        if all(perm[i] != i for i in range(n)):
            return perm

# Generate a secure rotation for a 10-room hotel
secure_rotation = random_derangement_cryptographic(10)
print(f"Secure random rotation: {secure_rotation}")
print(f"Verification: No key opens its original lock: {all(secure_rotation[i] != i for i in range(10))}")

Common Mistakes (Security Edition)

Mistake 1: Using a Predictable Rotation Pattern

Many hotels use simple cyclic shifts (Key1→Lock2, Key2→Lock3, ..., KeyN→Lock1). While this is a derangement, it is completely predictable. An attacker who knows the algorithm can determine the new mapping instantly. Always use cryptographic randomness.

Mistake 2: Forgetting That R(1) = 0

A single-room hotel cannot perform key rotation. The only possible mapping is Key1→Lock1, which is invalid. Security protocol: For N=1, you must replace the lock entirely, not just re-match keys.

Mistake 3: Assuming All Derangements Are Equally Secure

From a counting perspective, all derangements are equally valid. But from a security perspective, some derangements are weaker because they have small cycles (e.g., a 2-cycle swap). An attacker who compromises two rooms can deduce the swap. Ideally, use derangements with only large cycles (N-cycle or combinations of cycles of length ≥ 3).

Mistake 4: Implementing Key Rotation Without Verifying No Fixed Points

A naive shuffle might accidentally produce a permutation with fixed points. Always verify that the generated mapping is a derangement before deploying it:

def is_valid_remapping(mapping: list) -> bool:
    """Verify that no key opens its original lock."""
    return all(mapping[i] != i for i in range(len(mapping))

Mistake 5: Ignoring Side-Channel Attacks

Even if the number of derangements is huge, an attacker might use side channels (timing, power consumption, electromagnetic radiation) to deduce the mapping. In high-security environments, use constant-time algorithms for generating and applying derangements.

Frequently Asked Questions

Q1: How does key-lock re-matching differ from the Secret Santa problem?

A: Mathematically, they are identical (both count derangements). The difference is security context. In Secret Santa, the goal is fairness and fun. In key-lock re-matching, the goal is to make it computationally infeasible for an attacker to guess the new mapping. This adds requirements: cryptographic randomness, resistance to side-channel attacks, and avoidance of small cycles.

Q2: What is the minimum N for secure key rotation?

A: For N=10, an attacker has a 1 in 1.3 million chance of guessing correctly. That is acceptable for low-security applications. For high-security (military, financial), use N ≥ 20, where the attacker's success probability is less than 1 in 10^17.

Q3: Can this be used for cryptographic key rotation in software?

A: Yes. Many encryption systems rotate keys periodically using derangements. The old key schedule is a permutation, and the new schedule must have no fixed points to ensure forward secrecy (compromising the old key does not reveal the new key).

Q4: What is the time complexity of generating a random derangement?

A: Using rejection sampling (generate random permutation, check for fixed points, repeat), the expected time is O(N) per trial with 2.718 expected trials. So O(N) expected time. For large N (≥ 1000), there are more efficient algorithms (e.g., the Sattolo algorithm for cyclic permutations).

Q5: How does this apply to physical locksmithing?

A: When re-pinning a set of locks, a locksmith can reassign keys to locks in any derangement. The number of possible re-pinnings is R(N). For a small building with 10 locks, there are over a million possibilities—too many for an attacker to try physically.

Conclusion

Key and lock re-matching logic transforms a simple combinatorial problem into a practical security protocol. You have learned:

• How to model key rotation as a derangement of N items

• Why R(N) grows super-exponentially, making brute-force attacks infeasible for N ≥ 10

• How to implement the recurrence in four ways, from naive recursion to O(1) space optimization

• How to generate cryptographically secure random derangements for real-world deployment

• Common security mistakes (predictable patterns, small cycles, side-channel vulnerabilities)

The next time you check into a hotel and receive a re-encoded key card, you will understand the mathematics that protects your room. And if you are designing a security system, you now have the tools to implement key rotation correctly.

Ready to implement secure key rotation for your system?

Want to master Advanced Dynamic Programming for security applications? Our platform has everything you need.

👉 Visit Our Tutoring Page  to book a session today.

👉 Check Our Order Page  for direct access to our full DP coursework!

Where to Go Next

If you found this guide helpful, you might also enjoy these related resources:

• Return to the anchor article: Counting Derangements: Main Guide – For a complete overview of derangement theory, including base cases, the full recurrence derivation, and a comparison of all four DP approaches (recursive, top-down, bottom-up, optimized).

• General Gift Exchange Combinatorics – Learn how the same derangement logic applies to department-level gift exchanges, supply chain inter-trading, and economic network modeling.

• Network Node Routing Preventing Immediate Return – Discover how telecom companies use derangements to prevent micro-loops in packet routing, ensuring data never returns to the same node.

• Cryptographically Secure Random Number Generation – Read our blog post on generating unpredictable permutations for security applications.

• Physical Security Protocols for Hotels – Explore best practices for key card rotation and access control systems.