Breaking Enigma with Index of Coincidence on a Commodore 64
a day ago
- #enigma-machine
- #historical-computing
- #cryptanalysis
- The Index of Coincidence (IC) measures the probability that two randomly chosen letters from a text are the same, based on letter frequencies.
- For English, the IC is about 0.0667, while for random text it's 0.0385; this difference allows attacks on Enigma without known plaintext.
- IC is invariant to the Enigma plugboard, as it only depends on letter frequency distribution, not which letters are frequent.
- A BASIC implementation on a Commodore 64 computes IC sums without floating-point, using thresholds to filter candidates from 17,576 rotor positions.
- An assembly version searches all 336 rotor orderings and 17,576 positions each, taking 82 hours on a C64 but faster on modern hardware.
- With a 60-character ciphertext, IC produces false positives due to random letter distributions; human review is needed to identify readable German.
- The attack decrypts the entire message for each candidate, requiring 60 encryptions per candidate, making it slower but more general than crib-based attacks.
- On modern hardware like an Apple M4 GPU, the same search completes in 39 milliseconds, showcasing advances in computational power.