A Tiny Bombe on the Commodore 64
By Michael Doornbos
- 32 minutes read - 6683 wordsThe brute-force cracker searched 5.9 million candidates in 22 minutes. That was fine without ring settings. Add ring settings and the search space explodes to 103.9 billion. At the same speed, that’s roughly 270 days. On one C64. Without stopping.
Turing didn’t try to build a faster brute-force machine. He built a machine that asked a different question. Instead of “does this setting produce the right output?”, the Bombe asked “does this setting contradict itself?” Most settings do. The Bombe found them in microseconds and threw them away, leaving only a handful of candidates for human verification.
We’re going to build a simplified version on the C64. It uses the same core idea as the real machine: find a loop in the crib, try every plugboard assumption, and throw away everything that contradicts itself.
Menus and Loops
The Bombe isn’t a cipher-breaking machine in the Hollywood sense. It can’t take a pile of ciphertext and spit out the answer. It needs a crib: a stretch of plaintext that you already know (or can guess) matches part of the intercepted message. Without a crib, there’s no attack.
Bletchley Park got cribs from predictable German message formats. Weather reports started with WETTER (“weather”). Operators re-sent messages when recipients asked for repeats. Some stations sent formulaic openings like KEINE BESONDEREN EREIGNISSE (“nothing to report”). Lazy operators were the best source of all. The cryptanalysts didn’t need to guess the entire message, just enough characters to build what they called a menu.
We’ve been using the same crib throughout this series: the plaintext WETTERVORHERSAGEBISKAYA against ciphertext YDMAOIGMPQZPFVRCIGIIKJV. At Bletchley Park, the mapping between known plaintext and ciphertext was the menu.
Each position in the crib pairs a plaintext letter with a ciphertext letter. Here’s the full menu:
pos plain cipher
0 W Y
1 E D
2 T M
3 T A
4 E O
5 R I
6 V G
7 O M
8 R P
9 H Q
10 E Z
11 R P
12 S F
13 A V
14 G R
15 E C
16 B I
17 I G
18 S I
19 K I
20 A K
21 Y J
22 A V
Think of this as a graph. Each position creates an edge between two letters. Position 5 connects R and I. Position 17 connects I and G. Position 14 connects G and R. Those three edges form a closed cycle: R - I - G - R.
That’s a loop, and it’s the key to the whole machine.
Why Loops Matter
A loop creates a closed chain where you can check self-consistency without knowing anything about the plugboard. Here’s the logic:
Start with letter R (value 17). Encrypt it at position 5. If the rotor settings are correct, you get I (value 8), because position 5 maps plaintext R to ciphertext I. Now take that result and encrypt it at position 17. If the settings are correct, you get G (value 6), because position 17 maps plaintext I to ciphertext G. Finally, encrypt that at position 14. Position 14 maps plaintext G to ciphertext R, so you should get back to R (value 17).
If you don’t get back to R, the rotor settings are wrong. No need to test all 23 crib characters. No need to guess the plugboard. Three encryptions and you know.
For wrong settings, the chain doesn’t close. Encrypt R at position 5 and you get some arbitrary letter X. Encrypt X at position 17 and you get Y. Encrypt Y at position 14 and you get Z. Z won’t equal R. The setting contradicts the loop, so it’s impossible.
This is what the real Bombe did, scaled up. It tested loops electrically, checking thousands of settings per second, discarding everything that contradicted the loop constraints. The settings that survived (called stops) were sent to human checkers for verification.
The Loop Test in Pseudocode
To encrypt a character at a specific position in the message, we need the rotors in the state they’d be in after processing all the characters before that position. In our encrypt routine, the rotors step before each encryption. So to get the encryption at position P (0-indexed), we step P times first, then call encrypt (which steps once more and encrypts).
test_loop(left, mid, right, lpos, mpos, rpos):
save starting positions
leg 1: step 5 times, encrypt R(17)
result = encrypt(17) -- steps once more (6 total), encrypts at position 5
save result
restore starting positions
leg 2: step 17 times, encrypt result
result = encrypt(saved result) -- steps once more (18 total), encrypts at position 17
save result
restore starting positions
leg 3: step 14 times, encrypt result
result = encrypt(saved result) -- steps once more (15 total), encrypts at position 14
return result == 17 -- did we get back to R?
Each leg resets the rotors to the starting position and steps forward to the right spot. Three encryptions, three sets of position resets. If the final result matches our starting letter, the setting is a stop.
Stops and Verification
The loop test is a filter, not a final answer. With a 3-letter loop, about 1 in 26 candidates will pass by chance (the closure constraint has roughly a 1/26 probability of being satisfied by a random setting). That means around 227,000 stops out of 5.9 million candidates.
The real Bombe handled this the same way: stops were sent to a checking machine that tried to decrypt the message and see if it made sense. On the C64, we can do this automatically. When a candidate passes the loop test, we verify it by running the full 6-character crib test from the cracker. If the crib also matches, we have our answer.
for each rotor ordering:
for each starting position:
if test_loop passes: -- fast filter: 3 encryptions
if test_crib passes: -- verify: up to 6 encryptions
FOUND
This two-phase approach mirrors the historical workflow. The Bombe was fast but imprecise. The checking machine was slow but definitive. Together, they cracked messages that brute force couldn’t touch.
BASIC Version
The BASIC version searches all 17,576 starting positions for a single rotor ordering, the same structure as the cracker. The difference is in the test subroutine: we run the loop test first, and only verify with the crib if the loop test passes.
The rotor wiring, stepping, and encryption subroutines are identical to the cracker. The new code is the loop test and the step_n subroutine that steps the rotors a specific number of times.
5 PRINT CHR$(5)
10 PRINT CHR$(147);" ENIGMA BOMBE"
20 PRINT " LOOP TEST SEARCH":PRINT
100 DIM RF(7,25),RI(7,25),RE(25)
110 FOR R=0 TO 7:FOR I=0 TO 25
120 READ RF(R,I):NEXT I,R
200 DATA 4,10,12,5,11,6,3,16,21,25
210 DATA 13,19,14,22,24,7,23,20,18,15
220 DATA 0,8,1,17,2,9
230 DATA 0,9,3,10,18,8,17,20,23,1
240 DATA 11,7,22,19,12,2,16,6,25,13
250 DATA 15,24,5,21,14,4
260 DATA 1,3,5,7,9,11,2,15,17,19
270 DATA 23,21,25,13,24,4,8,22,6,0
280 DATA 10,12,20,18,16,14
290 DATA 4,18,14,21,15,25,9,0,24,16
300 DATA 20,8,17,7,23,11,13,5,19,6
310 DATA 10,3,2,12,22,1
320 DATA 21,25,1,17,6,8,19,24,20,15
330 DATA 18,3,13,7,11,23,0,22,12,9
340 DATA 16,14,5,4,2,10
350 DATA 9,15,6,21,14,20,12,5,24,16
360 DATA 1,4,13,7,25,17,3,10,0,18
370 DATA 23,11,8,2,19,22
380 DATA 13,25,9,7,6,17,2,23,12,24
390 DATA 18,22,1,14,20,5,0,8,21,11
395 DATA 15,4,10,16,3,19
400 DATA 5,10,16,7,19,11,23,14,2,1
410 DATA 9,18,15,3,25,17,0,12,4,22
420 DATA 13,8,20,24,6,21
450 REM COMPUTE INVERSE TABLES
460 FOR R=0 TO 7:FOR I=0 TO 25
470 RI(R,RF(R,I))=I
480 NEXT I,R
500 REM REFLECTOR UKW-B
510 FOR I=0 TO 25:READ RE(I):NEXT
520 DATA 24,17,20,7,16,18,11,3,15,23
530 DATA 13,6,14,10,12,8,4,1,5,25
540 DATA 2,22,21,9,0,19
600 REM NOTCH POSITIONS (TWO PER ROTOR)
610 DIM NO(7,1)
620 NO(0,0)=16:NO(0,1)=-1
630 NO(1,0)=4:NO(1,1)=-1
640 NO(2,0)=21:NO(2,1)=-1
650 NO(3,0)=9:NO(3,1)=-1
660 NO(4,0)=25:NO(4,1)=-1
670 NO(5,0)=25:NO(5,1)=12
680 NO(6,0)=25:NO(6,1)=12
690 NO(7,0)=25:NO(7,1)=12
700 REM CRIB AND TARGET DATA
710 DIM CR(5),TG(5)
720 CR(0)=22:CR(1)=4:CR(2)=19
730 CR(3)=19:CR(4)=4:CR(5)=17
740 TG(0)=24:TG(1)=3:TG(2)=12
750 TG(3)=0:TG(4)=14:TG(5)=8
760 CL=6
770 CT$="YDMAOIGMPQZPFVRCIGIIKJV"
800 PRINT "SELECT 3 ROTORS (1-8)"
810 INPUT "LEFT ROTOR";RL
820 INPUT "MIDDLE ROTOR";RM
830 INPUT "RIGHT ROTOR";RR
840 RL=RL-1:RM=RM-1:RR=RR-1
850 PRINT:PRINT "SEARCHING 17,576 POSITIONS"
860 PRINT "FOR ROTORS";RL+1;"-";RM+1;"-";RR+1
870 PRINT:TI$="000000":SC=0
900 FOR L0=0 TO 25
910 PRINT CHR$(L0+65);" ";
920 FOR M0=0 TO 25:FOR R0=0 TO 25
930 GOSUB 6000
940 IF F=1 THEN 1100
950 NEXT R0,M0,L0
960 PRINT:PRINT
970 PRINT "NOT FOUND"
975 PRINT SC;"STOPS (";INT(TI/60);"SEC)"
980 END
1100 PRINT:PRINT
1110 PRINT "FOUND!"
1120 PRINT "POSITION: ";CHR$(L0+65);"-";
1125 PRINT CHR$(M0+65);"-";CHR$(R0+65)
1130 PRINT SC;"STOPS"
1135 PRINT "TIME:";INT(TI/60);"SECONDS"
1150 PRINT:PRINT "DECRYPTED:"
1160 LP=L0:MP=M0:RP=R0
1170 FOR I=1 TO LEN(CT$)
1180 GOSUB 2000
1190 C=ASC(MID$(CT$,I,1))-65
1200 GOSUB 3000
1210 PRINT CHR$(C+65);
1220 NEXT
1230 PRINT:END
2000 REM STEP ROTORS
2010 IF MP<>NO(RM,0)ANDMP<>NO(RM,1) THEN 2040
2020 LP=LP+1:LP=LP-INT(LP/26)*26
2030 MP=MP+1:MP=MP-INT(MP/26)*26
2040 IF RP<>NO(RR,0)ANDRP<>NO(RR,1) THEN 2060
2050 MP=MP+1:MP=MP-INT(MP/26)*26
2060 RP=RP+1:RP=RP-INT(RP/26)*26
2070 RETURN
3000 REM ENCRYPT (FORWARD)
3010 E=(C+RP):E=E-INT(E/26)*26
3020 C=RF(RR,E)
3030 C=(C-RP+26):C=C-INT(C/26)*26
3040 E=(C+MP):E=E-INT(E/26)*26
3050 C=RF(RM,E)
3060 C=(C-MP+26):C=C-INT(C/26)*26
3070 E=(C+LP):E=E-INT(E/26)*26
3080 C=RF(RL,E)
3090 C=(C-LP+26):C=C-INT(C/26)*26
3100 REM REFLECTOR
3110 C=RE(C)
3120 REM ENCRYPT (INVERSE)
3130 E=(C+LP):E=E-INT(E/26)*26
3140 C=RI(RL,E)
3150 C=(C-LP+26):C=C-INT(C/26)*26
3160 E=(C+MP):E=E-INT(E/26)*26
3170 C=RI(RM,E)
3180 C=(C-MP+26):C=C-INT(C/26)*26
3190 E=(C+RP):E=E-INT(E/26)*26
3200 C=RI(RR,E)
3210 C=(C-RP+26):C=C-INT(C/26)*26
3220 RETURN
4000 REM STEP N TIMES (N IN SN)
4010 FOR SI=1 TO SN
4020 GOSUB 2000
4030 NEXT SI
4040 RETURN
5000 REM LOOP TEST
5010 S0=LP:S1=MP:S2=RP
5020 REM LEG 1: POSITION 5
5030 SN=5:GOSUB 4000
5040 C=17:GOSUB 2000:GOSUB 3000
5050 V=C
5060 REM LEG 2: POSITION 17
5070 LP=S0:MP=S1:RP=S2
5080 SN=17:GOSUB 4000
5090 C=V:GOSUB 2000:GOSUB 3000
5100 V=C
5110 REM LEG 3: POSITION 14
5120 LP=S0:MP=S1:RP=S2
5130 SN=14:GOSUB 4000
5140 C=V:GOSUB 2000:GOSUB 3000
5150 IF C=17 THEN F=1:RETURN
5160 F=0:RETURN
6000 REM BOMBE TEST (LOOP + CRIB)
6010 LP=L0:MP=M0:RP=R0
6020 GOSUB 5000
6030 IF F=0 THEN RETURN
6040 SC=SC+1
6050 REM CRIB VERIFY
6060 LP=L0:MP=M0:RP=R0:K=0
6070 GOSUB 2000:C=CR(K):GOSUB 3000
6080 IF C<>TG(K) THEN F=0:RETURN
6090 K=K+1:IF K<CL THEN 6070
6100 F=1:RETURN
The key addition is the loop test at line 5000. It saves the starting positions (S0, S1, S2), then for each leg of the R-I-G loop: restores positions, calls step_n to advance to the right message position, steps once more and encrypts, and saves the result for the next leg. If the chain closes back to R (17), the loop test passes.
The step_n subroutine at line 4000 simply calls the step routine N times in a FOR loop. Nothing fancy, but it gets the rotors to the right state.
Line 6000 ties it together: run the loop test, and if it passes (a stop), verify with the crib. The counter SC tracks how many stops occurred, so you can see the filtering in action.
With the correct ordering (3-1-5), the search finds the answer at position M-C-Q. You’ll also see the stop count, showing how many candidates passed the loop test before the crib verified the right one.
Assembly Version
The assembly version does the full search: all 336 rotor orderings, all 17,576 positions each. The only change from the cracker is in the position loop. Instead of testing the crib directly, we run the loop test first and only verify survivors.
The step_n Routine
This steps the rotors X times. It saves and restores X on the stack since the step routine uses X internally:
; step n times
; x = number of steps
step_n stx step_count
ldx #0
sn_loop cpx step_count
beq sn_done
txa
pha
jsr step
pla
tax
inx
jmp sn_loop
sn_done rts
step_count .byte 0
The Loop Test
The test_loop routine implements the R-I-G loop at positions 5, 17, and 14. It saves the starting positions, runs each leg of the loop, and checks if the chain closes:
; r-i-g loop at positions 5, 17, 14
; returns z flag set if match
test_loop
; save starting positions
lda right_pos
sta save_rp
lda mid_pos
sta save_mp
lda left_pos
sta save_lp
; leg 1: step 5, encrypt r(17)
ldx #5
jsr step_n
lda #17
jsr encrypt
sta loop_val
; restore positions
jsr restore_pos
; leg 2: step 17, encrypt result
ldx #17
jsr step_n
lda loop_val
jsr encrypt
sta loop_val
; restore positions
jsr restore_pos
; leg 3: step 14, encrypt result
ldx #14
jsr step_n
lda loop_val
jsr encrypt
; check: back to r(17)?
cmp #17
rts
The encrypt routine already calls step internally, so calling step_n(5) then encrypt gives 6 total steps before the encryption, which puts us at position 5 (0-indexed). Each leg restores the starting positions before stepping to its target position, since the three loop positions are independent snapshots of the same starting configuration.
The Two-Phase Search
The position loop runs the loop test, and when it produces a stop, falls through to a crib verification:
sp_rp
; set starting positions
lda try_lp
sta left_pos
lda try_mp
sta mid_pos
lda try_rp
sta right_pos
; test loop
jsr test_loop
beq tl_stop
; loop failed
jmp tl_fail
tl_stop
; loop passed (a "stop")
; verify with full crib
lda try_lp
sta left_pos
lda try_mp
sta mid_pos
lda try_rp
sta right_pos
ldx #0
tc_loop lda crib,x
stx savex
jsr encrypt
ldx savex
cmp target,x
bne tl_fail
inx
cpx #6
bne tc_loop
; crib confirmed
lda #1
sta found
rts
tl_fail inc try_rp
...
When the loop test returns with the Z flag set (result equals 17), we have a stop. We reset the positions and run the same crib test from the brute-force cracker. Only if all 6 characters match do we declare a find.
The Full Listing
Here’s the complete Bombe search. It assembles at $c000 and runs with sys 49152. Everything except the loop test, step_n, and the two-phase search logic is identical to the cracker.
; ==============================
; enigma bombe
; loop test search
; commodore 64
; rotors i-viii (m3), no plugboard
; turbo macro pro / tmpx
; by michael doornbos 2026
; mike@imapenguin.com
;
; uses r-i-g loop at positions
; 5, 17, 14 to eliminate
; impossible rotor settings
;
; .null/.text = screen codes
; use .byte for petscii strings
; ==============================
* = $c000
; --- zero page ---
ptr = $50
right_pos = $fb
mid_pos = $fc
left_pos = $fd
temp = $fe
chrout = $ffd2
; === entry point ===
; zero jiffy clock
lda #0
sta $a2
sta $a1
sta $a0
; cls, white text
lda #$93
jsr chrout
lda #5
jsr chrout
lda #13
jsr chrout
; header
ldx #<s_title
ldy #>s_title
jsr print
lda #13
jsr chrout
ldx #<s_sub
ldy #>s_sub
jsr print
lda #13
jsr chrout
lda #13
jsr chrout
; show ciphertext
ldx #<s_cipher
ldy #>s_cipher
jsr print
lda #13
jsr chrout
; show loop info
ldx #<s_loop
ldy #>s_loop
jsr print
lda #13
jsr chrout
lda #13
jsr chrout
; searching message
ldx #<s_search
ldy #>s_search
jsr print
lda #13
jsr chrout
; init found flag
lda #0
sta found
; run search
jsr search_all
; restore border
lda #14
sta $d020
; check result
lda found
beq not_found
; show result
lda #13
jsr chrout
jsr show_found
jmp show_time
not_found ldx #<s_notfound
ldy #>s_notfound
jsr print
lda #13
jsr chrout
; show elapsed seconds
show_time lda #13
jsr chrout
ldx #<s_time
ldy #>s_time
jsr print
jsr jiffy_sec
ldx #<s_sec
ldy #>s_sec
jsr print
lda #13
jsr chrout
rts
; === search all orderings ===
; p(8,3) = 336 permutations
search_all
lda #0
sta try_l
sa_left lda #0
sta try_m
sa_mid lda try_m
cmp try_l
beq sa_sm
lda #0
sta try_r
sa_right lda try_r
cmp try_l
beq sa_sr
cmp try_m
beq sa_sr
; valid permutation
jsr search_pos
lda found
bne sa_done
sa_sr inc try_r
lda try_r
cmp #8
bne sa_right
sa_sm inc try_m
lda try_m
cmp #8
bne sa_mid
inc try_l
lda try_l
cmp #8
bne sa_left
sa_done rts
; === search positions ===
; 26^3 = 17,576 per ordering
search_pos
; configure rotors
lda try_l
sta left_sel
lda try_m
sta mid_sel
lda try_r
sta right_sel
; border color = progress
inc $d020
; sweep all positions
lda #0
sta try_lp
sp_lp lda #0
sta try_mp
sp_mp lda #0
sta try_rp
sp_rp
; set starting positions
lda try_lp
sta left_pos
lda try_mp
sta mid_pos
lda try_rp
sta right_pos
; test loop
jsr test_loop
beq tl_stop
; loop failed
jmp tl_fail
tl_stop
; loop passed (a "stop")
; verify with full crib
lda try_lp
sta left_pos
lda try_mp
sta mid_pos
lda try_rp
sta right_pos
ldx #0
tc_loop lda crib,x
stx savex
jsr encrypt
ldx savex
cmp target,x
bne tl_fail
inx
cpx #6
bne tc_loop
; crib confirmed
lda #1
sta found
rts
tl_fail inc try_rp
lda try_rp
cmp #26
bne sp_rp
inc try_mp
lda try_mp
cmp #26
bne sp_mp
inc try_lp
lda try_lp
cmp #26
bne sp_lp
rts
; === test loop ===
; r-i-g loop at positions 5, 17, 14
; returns z flag set if match
test_loop
; save starting positions
lda right_pos
sta save_rp
lda mid_pos
sta save_mp
lda left_pos
sta save_lp
; leg 1: step 5, encrypt r(17)
ldx #5
jsr step_n
lda #17
jsr encrypt
sta loop_val
; restore positions
jsr restore_pos
; leg 2: step 17, encrypt result
ldx #17
jsr step_n
lda loop_val
jsr encrypt
sta loop_val
; restore positions
jsr restore_pos
; leg 3: step 14, encrypt result
ldx #14
jsr step_n
lda loop_val
jsr encrypt
; check: back to r(17)?
cmp #17
rts
; === restore positions ===
restore_pos
lda save_rp
sta right_pos
lda save_mp
sta mid_pos
lda save_lp
sta left_pos
rts
; === step n times ===
; x = number of steps
step_n stx step_count
ldx #0
sn_loop cpx step_count
beq sn_done
txa
pha
jsr step
pla
tax
inx
jmp sn_loop
sn_done rts
step_count .byte 0
; === show found result ===
show_found
ldx #<s_found
ldy #>s_found
jsr print
lda #13
jsr chrout
; rotors
ldx #<s_rotor
ldy #>s_rotor
jsr print
ldx left_sel
jsr print_rn
ldx #<s_sep
ldy #>s_sep
jsr print
ldx mid_sel
jsr print_rn
ldx #<s_sep
ldy #>s_sep
jsr print
ldx right_sel
jsr print_rn
lda #13
jsr chrout
; positions
ldx #<s_start
ldy #>s_start
jsr print
lda try_lp
clc
adc #65
jsr chrout
ldx #<s_sep
ldy #>s_sep
jsr print
lda try_mp
clc
adc #65
jsr chrout
ldx #<s_sep
ldy #>s_sep
jsr print
lda try_rp
clc
adc #65
jsr chrout
lda #13
jsr chrout
lda #13
jsr chrout
; decrypt full message
ldx #<s_decrypt
ldy #>s_decrypt
jsr print
; reset to found positions
lda try_lp
sta left_pos
lda try_mp
sta mid_pos
lda try_rp
sta right_pos
ldx #0
dc_loop lda cipher,x
cmp #$ff
beq dc_done
stx savex
jsr encrypt
clc
adc #65
jsr chrout
ldx savex
inx
jmp dc_loop
dc_done lda #13
jsr chrout
rts
; === encrypt ===
; a = letter (0-25) in/out
; no plugboard (identity)
encrypt pha
jsr step
pla
; right fwd
ldx right_sel
jsr set_fwd
ldx right_pos
jsr rotor_pass
; middle fwd
ldx mid_sel
jsr set_fwd
ldx mid_pos
jsr rotor_pass
; left fwd
ldx left_sel
jsr set_fwd
ldx left_pos
jsr rotor_pass
; reflector
tax
lda reflector,x
; left inv
ldx left_sel
jsr set_inv
ldx left_pos
jsr rotor_pass
; middle inv
ldx mid_sel
jsr set_inv
ldx mid_pos
jsr rotor_pass
; right inv
ldx right_sel
jsr set_inv
ldx right_pos
jsr rotor_pass
rts
; === step rotors ===
; dual notch for vi-viii
step
ldx mid_sel
lda mid_pos
cmp notch1,x
beq do_double
cmp notch2,x
bne no_double
do_double
; double step
lda left_pos
clc
adc #1
jsr mod26
sta left_pos
lda mid_pos
clc
adc #1
jsr mod26
sta mid_pos
jmp step_right
no_double
ldx right_sel
lda right_pos
cmp notch1,x
beq do_mid
cmp notch2,x
bne step_right
do_mid lda mid_pos
clc
adc #1
jsr mod26
sta mid_pos
step_right
lda right_pos
clc
adc #1
jsr mod26
sta right_pos
rts
; === mod26 ===
mod26 cmp #26
bcc m26done
sbc #26
m26done rts
; === rotor pass ===
rotor_pass
stx temp
clc
adc temp
jsr mod26
tay
lda (ptr),y
sec
sbc temp
clc
adc #26
jsr mod26
rts
; === set table pointer ===
set_fwd ldy fwd_lo,x
sty ptr
ldy fwd_hi,x
sty ptr+1
rts
set_inv ldy inv_lo,x
sty ptr
ldy inv_hi,x
sty ptr+1
rts
; === print string ===
; x=lo, y=hi, null-terminated
print stx ptr
sty ptr+1
ldy #0
ploop lda (ptr),y
beq pdone
jsr chrout
iny
bne ploop
pdone rts
; === print rotor name ===
; x = rotor index (0-7)
print_rn
lda rn_lo,x
sta ptr
lda rn_hi,x
sta ptr+1
ldy #0
rnloop lda (ptr),y
beq rndone
jsr chrout
iny
bne rnloop
rndone rts
; === jiffy clock to seconds ===
; divide 24-bit jiffy by 60
; print result as decimal
jiffy_sec lda $a0
sta dividend
lda $a1
sta dividend+1
lda $a2
sta dividend+2
lda #0
sta remainder
ldx #24
jsloop asl dividend+2
rol dividend+1
rol dividend
rol remainder
lda remainder
cmp #60
bcc jsskip
sbc #60
sta remainder
inc dividend+2
jsskip dex
bne jsloop
lda dividend+1
ldx dividend+2
jmp $bdcd
dividend .byte 0,0,0
remainder .byte 0
; === data ===
; search state
savex .byte 0
found .byte 0
try_l .byte 0
try_m .byte 0
try_r .byte 0
try_lp .byte 0
try_mp .byte 0
try_rp .byte 0
; rotor config
right_sel .byte 0
mid_sel .byte 0
left_sel .byte 0
; loop state
loop_val .byte 0
save_rp .byte 0
save_mp .byte 0
save_lp .byte 0
; crib: wetter (0-25)
crib .byte 22,4,19,19,4,17
; target: ydmaoi (0-25)
target .byte 24,3,12,0,14,8
; full ciphertext (0-25, $ff term)
cipher .byte 24,3,12,0,14,8
.byte 6,12,15,16,25,15
.byte 5,21,17,2,8,6
.byte 8,8,10,9,21,$ff
; notch positions (i-viii)
notch1 .byte 16,4,21,9,25
.byte 25,25,25
; second notch ($ff = none)
notch2 .byte $ff,$ff,$ff,$ff,$ff
.byte 12,12,12
; address tables (rotors i-viii)
fwd_lo .byte <rot1_f,<rot2_f
.byte <rot3_f,<rot4_f
.byte <rot5_f,<rot6_f
.byte <rot7_f,<rot8_f
fwd_hi .byte >rot1_f,>rot2_f
.byte >rot3_f,>rot4_f
.byte >rot5_f,>rot6_f
.byte >rot7_f,>rot8_f
inv_lo .byte <rot1_i,<rot2_i
.byte <rot3_i,<rot4_i
.byte <rot5_i,<rot6_i
.byte <rot7_i,<rot8_i
inv_hi .byte >rot1_i,>rot2_i
.byte >rot3_i,>rot4_i
.byte >rot5_i,>rot6_i
.byte >rot7_i,>rot8_i
; === rotor wiring ===
; i: ekmflgdqvzntowyhxuspaibrcj
rot1_f .byte 4,10,12,5,11,6
.byte 3,16,21,25,13,19
.byte 14,22,24,7,23,20
.byte 18,15,0,8,1,17
.byte 2,9
; ii: ajdksiruxblhwtmcqgznpyfvoe
rot2_f .byte 0,9,3,10,18,8
.byte 17,20,23,1,11,7
.byte 22,19,12,2,16,6
.byte 25,13,15,24,5,21
.byte 14,4
; iii: bdfhjlcprtxvznyeiwgakmusqo
rot3_f .byte 1,3,5,7,9,11
.byte 2,15,17,19,23,21
.byte 25,13,24,4,8,22
.byte 6,0,10,12,20,18
.byte 16,14
; iv: esovpzjayquirhxlnftgkdcmwb
rot4_f .byte 4,18,14,21,15,25
.byte 9,0,24,16,20,8
.byte 17,7,23,11,13,5
.byte 19,6,10,3,2,12
.byte 22,1
; v: vzbrgityupsdnhlxawmjqofeck
rot5_f .byte 21,25,1,17,6,8
.byte 19,24,20,15,18,3
.byte 13,7,11,23,0,22
.byte 12,9,16,14,5,4
.byte 2,10
; vi: jpgvoumfyqbenhzrdkasxlictw
rot6_f .byte 9,15,6,21,14,20
.byte 12,5,24,16,1,4
.byte 13,7,25,17,3,10
.byte 0,18,23,11,8,2
.byte 19,22
; vii: nzjhgrcxmyswboufaivlpekqdt
rot7_f .byte 13,25,9,7,6,17
.byte 2,23,12,24,18,22
.byte 1,14,20,5,0,8
.byte 21,11,15,4,10,16
.byte 3,19
; viii: fkqhtlxocbjspdzramewniuygv
rot8_f .byte 5,10,16,7,19,11
.byte 23,14,2,1,9,18
.byte 15,3,25,17,0,12
.byte 4,22,13,8,20,24
.byte 6,21
; inverse tables
rot1_i .byte 20,22,24,6,0,3
.byte 5,15,21,25,1,4
.byte 2,10,12,19,7,23
.byte 18,11,17,8,13,16
.byte 14,9
rot2_i .byte 0,9,15,2,25,22
.byte 17,11,5,1,3,10
.byte 14,19,24,20,16,6
.byte 4,13,7,23,12,8
.byte 21,18
rot3_i .byte 19,0,6,1,15,2
.byte 18,3,16,4,20,5
.byte 21,13,25,7,24,8
.byte 23,9,22,11,17,10
.byte 14,12
rot4_i .byte 7,25,22,21,0,17
.byte 19,13,11,6,20,15
.byte 23,16,2,4,9,12
.byte 1,18,10,3,24,14
.byte 8,5
rot5_i .byte 16,2,24,11,23,22
.byte 4,13,5,19,25,14
.byte 18,12,21,9,20,3
.byte 10,6,8,0,17,15
.byte 7,1
rot6_i .byte 18,10,23,16,11,7
.byte 2,13,22,0,17,21
.byte 6,12,4,1,9,15
.byte 19,24,5,3,25,20
.byte 8,14
rot7_i .byte 16,12,6,24,21,15
.byte 4,3,17,2,22,19
.byte 8,0,13,20,23,5
.byte 10,25,14,18,11,7
.byte 9,1
rot8_i .byte 16,9,8,13,18,0
.byte 24,3,21,10,1,5
.byte 17,20,7,12,2,15
.byte 11,4,22,25,19,6
.byte 23,14
; ukw-b reflector
reflector .byte 24,17,20,7,16,18
.byte 11,3,15,23,13,6
.byte 14,10,12,8,4,1
.byte 5,25,2,22,21,9
.byte 0,19
; === strings (petscii) ===
; " enigma bombe"
s_title .byte 32,32,69,78,73,71
.byte 77,65,32,66,79,77
.byte 66,69,0
; " loop test search"
s_sub .byte 32,32,76,79,79,80
.byte 32,84,69,83,84,32
.byte 83,69,65,82,67,72
.byte 0
; " cipher: ydmaoigmpqzpfvrcigiikjv"
s_cipher .byte 32,32,67,73,80,72
.byte 69,82,58,32,89,68
.byte 77,65,79,73,71,77
.byte 80,81,90,80,70,86
.byte 82,67,73,71,73,73
.byte 75,74,86,0
; " loop: r-i-g @ 5,17,14"
s_loop .byte 32,32,76,79,79,80
.byte 58,32,82,45,73,45
.byte 71,32,64,32,53,44
.byte 49,55,44,49,52,0
; " searching..."
s_search .byte 32,32,83,69,65,82
.byte 67,72,73,78,71,46
.byte 46,46,0
; " found!"
s_found .byte 32,32,70,79,85,78
.byte 68,33,0
; " not found"
s_notfound .byte 32,32,78,79,84
.byte 32,70,79,85,78,68
.byte 0
; " rotors: "
s_rotor .byte 32,32,82,79,84,79
.byte 82,83,58,32,32,0
; " start: "
s_start .byte 32,32,83,84,65,82
.byte 84,58,32,32,32,0
; " decrypted: "
s_decrypt .byte 32,32,68,69,67,82
.byte 89,80,84,69,68,58
.byte 32,0
; " time: "
s_time .byte 32,32,84,73,77,69
.byte 58,32,0
; " seconds"
s_sec .byte 32,83,69,67,79,78
.byte 68,83,0
; " - "
s_sep .byte 32,45,32,0
; rotor names (petscii)
rn1 .byte 73,0
rn2 .byte 73,73,0
rn3 .byte 73,73,73,0
rn4 .byte 73,86,0
rn5 .byte 86,0
rn6 .byte 86,73,0
rn7 .byte 86,73,73,0
rn8 .byte 86,73,73,73,0
rn_lo .byte <rn1,<rn2,<rn3
.byte <rn4,<rn5,<rn6
.byte <rn7,<rn8
rn_hi .byte >rn1,>rn2,>rn3
.byte >rn4,>rn5,>rn6
.byte >rn7,>rn8
Timing
The assembly Bombe searches all 5,909,376 candidates in about 165 minutes on a stock C64. The brute-force cracker did the same search in about 22 minutes. The Bombe is roughly 7.5x slower.
That might seem backwards. The Bombe is supposed to be smarter, so why is it slower?
Per-candidate cost. The brute-force cracker encrypts one crib character and bails if it doesn’t match. Only 1 in 26 candidates survive the first character, so the average is about 1.04 encryptions per candidate. Most candidates cost almost nothing.
The Bombe runs the full loop test on every candidate: 3 encryptions plus 36 step calls (5 + 17 + 14 pre-steps) plus 3 position restores. Every candidate pays that cost regardless of whether it’s close to correct. The ~3.8% that pass the loop test then also get the 6-character crib verification on top.
Without a plugboard, the brute-force cracker’s early exit is hard to beat. The loop test’s advantage only appears when the plugboard makes direct crib comparison impossible. That’s the scenario it was designed for.
Adding the Plugboard
Everything so far ignores the plugboard. That’s fine for learning the idea, but the real Bombe’s power came from how it handled plugboard settings through loops.
With a plugboard, you can’t just encrypt R and compare the output to I. The plugboard scrambles the input before it enters the rotors and scrambles the output after it leaves. You don’t know what R becomes after the plugboard, so you can’t predict what should come out.
But the loop test gives you a way around this. For each candidate rotor setting, try all 26 possible assumptions for what R maps to through the plugboard. Say you assume R maps to 0 (that the plugboard swaps R with A). Run the loop:
- Feed 0 into the rotors at position 5. Get some result X.
- X is the plugboard output for whatever I maps to. Feed X into the rotors at position 17. Get Y.
- Y is the plugboard output for whatever G maps to. Feed Y into the rotors at position 14. Get Z.
- If Z equals 0 (your original assumption for R), the assignment is self-consistent.
For most rotor settings, none of the 26 assumptions will be self-consistent. The loop contradicts all of them. Those settings are impossible regardless of the plugboard, and you’ve proven it with just 26 x 3 = 78 encryptions.
For the rare setting where one assumption is self-consistent, you’ve not only found a candidate rotor setting but also deduced the plugboard values for R, I, and G. Three plugboard pairs for free. Run additional loops from the same crib to get more pairs. Eventually, enough of the plugboard is known that you can try decrypting the message.
This is why the math article compared the Bombe to Sudoku. Each loop constrains the plugboard like filling in a row constrains the remaining cells. Enough constraints and the whole puzzle collapses.
The Code Change
The no-plugboard test_loop starts with lda #17 (the letter R) and checks if the result equals 17. The plugboard version wraps the whole loop in 26 iterations, trying each assumption 0 through 25:
; tries 26 plugboard assumptions
; returns z flag set if any match
test_loop
; save starting positions
lda right_pos
sta save_rp
lda mid_pos
sta save_mp
lda left_pos
sta save_lp
; try assumptions 0-25
lda #0
sta plug_try
pl_next
; leg 1: restore, step 5
jsr restore_pos
ldx #5
jsr step_n
lda plug_try
jsr encrypt
sta loop_val
; leg 2: restore, step 17
jsr restore_pos
ldx #17
jsr step_n
lda loop_val
jsr encrypt
sta loop_val
; leg 3: restore, step 14
jsr restore_pos
ldx #14
jsr step_n
lda loop_val
jsr encrypt
; back to assumption?
cmp plug_try
beq pl_done
; next assumption
inc plug_try
lda plug_try
cmp #26
bne pl_next
; all 26 failed, clear z
lda #1
pl_done rts
Instead of lda #17, we load plug_try (the current assumption). Instead of cmp #17, we compare against plug_try. If any of the 26 assumptions closes the loop, the Z flag is set and we return immediately. If all 26 fail, lda #1 clears the Z flag and we return with a rejection.
Everything else in the program is identical. The search loop, the crib verification, the rotor stepping, the display code. One routine changed, one byte of storage added (plug_try).
Plugboard Results
The Python verifier confirms the plugboard version finds the correct answer: rotors III-I-V at positions M-C-Q, with plugboard mappings R=M, I=K, G=P. Those three pairs came free from the loop test.
The stop rate is higher than the no-plugboard version: about 63% of candidates have at least one self-consistent assumption, versus 3.8% for the fixed-letter test. That makes sense. With 26 tries, the odds of at least one working by chance are much higher. More stops means more crib verifications, so the plugboard version does more total work per candidate.
On a stock C64, the plugboard Bombe takes 236 minutes (about 4 hours), roughly 1.4x slower than the no-plugboard version. That’s much less than the 26x you might expect from trying 26 assumptions. The step_n calls dominate the cost (5 + 17 + 14 = 36 steps per leg, three legs per assumption), and those are the same whether you’re trying 1 assumption or 26. The extra 25 encrypt calls per candidate are relatively cheap compared to all that stepping.
Squeezing More Out of the C64
The plugboard version works, but 26 × 3 = 78 encryptions per candidate is a lot of computation. Each encryption passes through 6 rotor lookups and a reflector. Most of that work is redundant: for a given rotor setting and loop position, the encryption function is a fixed mapping from input to output. We’re computing that same mapping over and over for each of the 26 assumptions.
Lookup Tables
Instead of encrypting 78 times per candidate, we can build three 26-byte lookup tables, one for each loop position. Each table maps every possible input (0-25) to its encrypted output at that position. Building one table takes 26 encryptions. Three tables = 78 encryptions, same as before.
But now testing the 26 assumptions is free. Instead of encrypting, we do three table lookups per assumption:
ldx #0
pl_next ldy tab5,x
lda tab17,y
tay
lda tab14,y
stx plug_try
cmp plug_try
beq pl_done
inx
cpx #26
bne pl_next
lda #1
pl_done rts
X is the assumption (what R maps to). Look up what position 5 produces for that input. Feed that result into position 17’s table. Feed that into position 14’s table. Compare to the original assumption. Three indexed loads and a compare, no subroutine calls.
The table-building cost is the same as the plugboard version (78 encryptions). But the testing cost drops from 78 encryptions to 78 table lookups. Table lookups are roughly 10 cycles each on the 6502 (load indexed + store/compare). An encryption is around 400 cycles (6 rotor passes, mod26 calls, reflector). So the testing phase runs about 40x faster.
The trick is splitting encrypt into two entry points. The normal encrypt calls step then falls through to encrypt_ns (encrypt, no step). When building tables, we step the rotors to the right position once, then call encrypt_ns 26 times without disturbing the rotor state:
; step to position 5 (6 steps total)
ldx #6
jsr step_n
; build table
ldx #0
bt5 txa
stx savex
jsr encrypt_ns
ldx savex
sta tab5,x
inx
cpx #26
bne bt5
The encrypt_ns entry point is just encrypt without the initial pha / jsr step / pla. Same rotor passes, same reflector, same result. The rotors don’t move between calls, so all 26 inputs get encrypted at the same rotor position.
Pre-Computing with the REU
The lookup table version still builds three tables for every candidate. That’s 78 encryptions times 5.9 million candidates = 460 million encryptions just for table construction. The tables themselves are cheap to search, but building them dominates the runtime.
What if we built all the tables in advance?
For one rotor ordering, there are 17,576 starting positions. Each needs three 26-byte tables (78 bytes total). That’s 17,576 × 78 = 1,370,928 bytes, about 1.3 MB. Way too much for the C64’s 64K of RAM. But the 1764 REU (Ram Expansion Unit) has 256K, and the Ultimate 64 emulates a 16 MB REU. At 1.3 MB per ordering, a 16 MB REU holds about 12 orderings at once.
The REU version works in two phases. Phase 1 (pre-compute): for each of the 17,576 positions, build the three lookup tables and DMA-stash them to the REU. Phase 2 (search): for each position, DMA-fetch the 78 bytes back from the REU and run the 26-assumption test with pure indexed loads.
The DMA transfer is fast. The REU moves data at 1 byte per clock cycle, so 78 bytes takes 78 microseconds. The search phase for one ordering becomes: 17,576 DMA fetches + 17,576 × 26 table lookups. No encryptions at all during the search. All the rotor computation happened during pre-compute.
; stash 78 bytes (tab5+tab17+tab14) to reu
reu_stash
lda #<tab5
sta reu_c64lo
lda #>tab5
sta reu_c64hi
lda r_lo
sta reu_reulo
lda r_hi
sta reu_reuhi
lda r_bank
sta reu_reubank
lda #78
sta reu_lenlo
lda #0
sta reu_lenhi
sta reu_addrctl
lda #$90
sta reu_command
rts
The REU registers at $df00-$df0a control the transfer. Set the C64 address (where the data lives in main RAM), the REU address (a 24-bit address in expansion memory), the transfer length, and write the command byte. $90 = stash (C64 to REU), $91 = fetch (REU to C64). The transfer happens instantly from the CPU’s perspective.
A 24-bit address counter tracks the current position in REU memory. After each 78-byte block, we add 78:
reu_add78
clc
lda r_lo
adc #78
sta r_lo
lda r_hi
adc #0
sta r_hi
lda r_bank
adc #0
sta r_bank
rts
This is the closest our C64 gets to how the real Bombe worked. The Bombe’s rotors were physically wired to represent every position simultaneously. Our REU stores the pre-computed result of every position, ready for instant retrieval. The Bombe’s electrical test circuit checked all positions in parallel. Our search phase is sequential, but each test is just three table lookups instead of a full encryption.
The pre-compute phase is slow (same 78 encryptions per position), but it only runs once per ordering. The search phase is where the speed comes from. Whether the REU version is faster overall depends on the balance between pre-compute cost and search savings.
How They Compare
Here are the times for all four versions searching all 5.9 million candidates on a stock 1 MHz C64:
| Version | Time | vs. Loop Test |
|---|---|---|
| Loop test (no plugboard) | 9,904s (165 min) | 1.0x |
| Table lookup | 5,313s (89 min) | 1.9x faster |
| REU pre-compute | 6,490s (108 min) | 1.5x faster |
| Plugboard (26 assumptions) | 14,188s (236 min) | 1.4x slower |
The table lookup version is the fastest. Building the three tables costs the same 78 encryptions as the plugboard version, but testing 26 assumptions with indexed loads is nearly free compared to 26 full encryptions.
The REU version is slower than the table version, which is surprising. The DMA transfers are fast (78 bytes at 1 byte per cycle), but setting up the REU registers for each transfer takes about 30 instructions. For 17,576 positions per ordering, that’s 17,576 DMA setups in the search phase alone, plus another 17,576 in the pre-compute phase. The overhead adds up. The table version avoids all of that by just rebuilding the tables in place.
The REU approach would pay off with a larger search space. With ring settings (103.9 billion candidates), the pre-compute cost is amortized across many more searches of the same table data, and the DMA overhead per candidate shrinks relative to the total work.
What’s Simplified
Our C64 Bombe uses the same core algorithm as the real machine. The loop test with plugboard assumptions is the genuine technique Turing designed. But the real Bombe at Bletchley Park had several advantages we don’t.
Multiple loops. The real Bombe wired up every loop in the crib menu simultaneously, not just one. Our crib has other connections beyond R-I-G, and each additional loop further constrains the search. A setting that passes one loop by chance is unlikely to pass three or four. With enough loops, the false positive rate drops close to zero and the crib verification becomes unnecessary.
The diagonal board. Gordon Welchman’s key improvement exploited the fact that the plugboard is symmetric: if R maps to M, then M maps to R. This doubles the information you get from each self-consistent assumption, cutting the false positive rate further. The diagonal board was so effective that it alarmed Turing when Welchman first proposed it.
Parallel testing. The real Bombe tested all 17,576 positions simultaneously using 36 sets of mechanical rotors wired in parallel. Electrical circuits checked the loop constraint at each position as the rotors stepped. Our C64 tests them one at a time.
The checking machine. Stops from the Bombe went to a separate machine that tested additional crib positions and plugboard pairs. Our crib verification serves the same purpose, but the real checking machine was more thorough.
Could a C64 Have Cracked Enigma?
The C64 was released in 1982, 40 years after the Bombe. But it’s fun to ask: how would a 1 MHz 6510 have performed in 1942?
For our simplified search (no ring settings, no plugboard), the C64 finds the answer in about 165 minutes. The real Bombe found stops in about 20 minutes per rotor ordering, testing all 17,576 positions in parallel. It could run through the likely orderings in a few hours. So for this simplified problem, the C64 and the Bombe are in the same ballpark.
But the real problem was harder. Wartime Enigma used plugboards with 10 pairs swapped, creating 150 trillion additional combinations. The Bombe handled this elegantly through its loop-and-assumption approach, running the electrical test for all positions simultaneously. A C64 running our plugboard version takes about 4 hours for the same 5.9 million candidates. That’s workable, but only because we’re ignoring ring settings.
Add ring settings and the search space hits 103.9 billion. Even our loop test can’t help: every candidate still needs testing, the loop just filters each one faster. At C64 speeds, that’s roughly 1.3 million hours, or about 150 years. You’d need a warehouse full of C64s to match what one Bombe did in an afternoon.
The REU version is the closest we get to the Bombe’s approach. Pre-computing all the lookup tables and storing them in expansion memory mirrors how the Bombe’s physical rotors were wired to represent every position at once. The search phase becomes pure data retrieval and comparison, no computation.
The real lesson isn’t about clock speed. The Bombe’s genius was parallelism. It tested thousands of positions at once through electrical circuits, not sequential code. A C64 is a sequential machine doing one thing at a time. Turing built a massively parallel special-purpose computer using 1940s technology, and it worked because the problem had exactly the right structure for that kind of parallelism. The loops in the crib menu turned a combinatorial nightmare into something that could be checked with current flowing through wires.
Extra Credit
A few ways to push this further:
-
Add ring settings: Wrap the position loop with a ring settings loop. Each ring configuration gets its own sweep of 17,576 positions. The loop test still works the same way, but ring settings affect both the rotor pass math and the notch positions. The search space goes from 5.9 million to 103.9 billion.
-
Use multiple loops: The crib has other loops beyond R-I-G. Each additional loop further constrains the search. A setting must be consistent with all loops simultaneously. With enough loops, the crib verification becomes unnecessary.
-
Try the Ultimate 64 at speed: The Ultimate 64 can run the C64 architecture at up to 64 MHz. At that speed, the plugboard search that takes 71 hours at 1 MHz would finish in about 67 minutes. The architecture scales linearly with clock speed since there’s no cache or memory contention to worry about.
A true crib-less crack of Enigma would require something like index of coincidence or frequency analysis on the output, which is a completely different (and much harder) problem. Nobody did that operationally during the war.