Filer: Download challenge files

Writeup: Fibonacci Caesar

Indledende Observationer

Jeg fik udleveret:

  • main.py

  • encryption.txt

Beskrivelsen indikerede en modificeret Caesar-cipher, hvor forskydningen afhænger af Fibonacci-sekvensen.

I main.py fandt jeg følgende logik:

1
2
3
4
5
6
7

a = fib(n)
b = fib(n + 1)

for ch in text:
    k = a % 26
    ...
    a, b = b, a + b

Det betød:

  • Start-shift = Fₙ

  • Næste shift = Fₙ₊₁

  • Derefter klassisk Fibonacci-opdatering pr. bogstav

  • Alle shifts reduceres modulus 26 (alfabetets længde)

Recon / Kortlægning

Krypteringen pr. bogstav er:

1

shift_i = F(n + i) mod 26

Det vil sige, at hele krypteringen foregår modulus 26.

Fibonacci-sekvensen modulo et tal har en periode kaldet Pisano-perioden.

For modulus 26 gælder:

1

Pisano(26) = 84

Det betyder:

1

F(n) mod 26 gentager sig for hver 84

Dermed er:

1

key ≡ key mod 84

Så i stedet for at brute-force uendeligt mange n-værdier, skulle jeg kun teste:

1

n ∈ [0..83]

Analyse

Svagheden i designet er:

  • Hele algoritmen reducerer alt mod 26

  • Fibonacci modulo 26 er periodisk

  • Perioden er lille (84)

Det reducerer nøgle-rummet drastisk.

Angrebet

Jeg skrev et simpelt brute-force script, der:

  1. Beregnede Fibonacci mod 26

  2. Forsøgte dekryptering for n = 0..83

  3. Kiggede efter plaintext der startede med ddc

Dekrypteringslogik:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def decrypt(n, text):
    a = fib_mod(n, 26)
    b = fib_mod(n + 1, 26)

    result = ""
    for ch in text:
        k = a % 26
        result += alphabet[(alphabet.index(ch) - k) % 26]
        a, b = b, (a + b) % 26

    return result

Ved korrekt n fik jeg plaintext:

1

ddc pisano sequence solves fibonacci caesar

Flaget

Ifølge formatet:

1

DDC{...}

Jeg erstattede mellemrum med underscores:

1

DDC{pisano_sequence_solves_fibonacci_caesar}

Konklusion

Udfordringen illustrerede følgende:

  • At Fibonacci mod m altid er periodisk

  • At kryptering baseret på sekvenser modulo alfabet-størrelse ofte kan reduceres kraftigt

  • At Pisano-perioder kan udnyttes direkte til key-reduction

Angrebet var ikke kryptografisk avanceret, men istedet ren matematisk observation og systematisk brute-force over et reduceret key-space.