Making and Breaking Ciphers with Python, er Commodore- Part 2: The Shift Cipher

Making and Breaking Ciphers with Python, er Commodore- Part 2: The Shift Cipher

In Part 1 we did a simple reverse of a string. While simple, these software steps will help build the skills we need going forward in Assembly without feeling like I skipped right to a 300 line  after doing a short one. One foot in front of the other and all that.

The Shift Cipher

For Christmas, my wife and I bought my sister's kids this code wheel. It implements a simple shift cipher to be transposed by hand. This was common low tech way to scramble messages for quite some time, and fits nicely in between reversing a string and a more complex implementation of the Caesar cipher in software.

Commercial version of what we'll make

The idea is straightforward. You line up a letter of the inner ring with a letter of the outer ring and use it as the "key". Then you encode your message matching your plain text with the outer ring and "scrambling it" with the matching inner ring letters.

So as an example:

MEET ME AT THE MISSION AT MIDNIGHT

To "encode it" rotate the ring and pick and inner and outer letter so serve as the key. The recipient will need to set their decoder to this combination to decode. So if our rings line up like:

ZYXWVUTSRQPONMLKJIHGFEDCBA   
TUVWXYZABCDEFGHIJKLMNOPQRS

Let's use RB as the key. "Inner" R lines up with "Outer" B.

Now that we have our keys aligned, eliminate the spaces in the message:

MEETMEATTHEMISSIONATMIDNIGHT

We'll use the "Outer" ring as the decoded part and the "Inner" ring as the encoded part. You can switch this around as long as the recipient is aware that you're doing it that way. So our "encrypted" message is:

MEETMEATTHEMISSIONATMIDNIGHT 	-message
GOOZGOSZZLOGKAAKEFSZGKPFKMLZ	-encrypted

Python version

This is much easier to implement if we flatten this disk shape into a straight line as above:

ZYXWVUTSRQPONMLKJIHGFEDCBA # Inner "ring"
ABCDEFGHIJKLMNOPQRSTUVWXYZ # Outer "ring"

Now all we need to do is "shift" the bottom row to the right 1 char at a time, taking the right-most character and adding it to the left-most position.

#!/usr/bin/env python
from collections import deque
import sys

inner = "ZYXWVUTSRQPONMLKJIHGFEDCBA"
outer = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def rotatekeys(shift):
    print(inner)
    items = deque(outer)
    items.rotate(shift)
    print(''.join(items))

if __name__ == '__main__':
    shift = int(sys.argv[1])
    rotatekeys(shift)

This works well. Just add the number of positions you want to shift to the right as an argument and if shifts them for you.

> python shift.py 7
ZYXWVUTSRQPONMLKJIHGFEDCBA
TUVWXYZABCDEFGHIJKLMNOPQRS

That was pretty easy, but to implement this on the Commodore, we're not going to be able to use this fancy collections/deque library are we?

As a coder, you now need to decide what the best way to handle going forward is. We have a perfectly acceptable implementation in Python, but it doesn't use the same method we'll need to use to port this concept to Assembly. Decide for yourself if you need to reimplement this in Python in a way that more closely matches the "table" we'll have to create and shift.

Commodore Version

We can now visualize the outcome of our program thanks to the Python program.

We'll need to handle the bytes individually on the Commodore. A common way to do this is to put them in a "table". I use air quotes here because it's not a table at all, it's really just the bytes in a row starting at a memory address (that we'll let the assembler decide the location of for us)  and using the x register to index over that set of locations.

We'll be using the ASCII values of the letters and sticking to uppercase only for now.  The Commodore 64 is VERY memory constrained compared to a modern computer, it can't even get CLOSE to holding the graphics on this webpage in memory.  

In this program the 64k we have is WAY more memory than needed, so we'll go for ease of reading/understanding over memory conservation.

Let's make two "tables" for simplicity.

We'll also stick to the decimal representations of these numbers as it also makes it easier to read. The Assembler is happy to have these as decimal, hexadecimal or binary so it's up to us to chose what's best for our code

The "outer" "table" is the alphabet A-Z and the "inner" is backwards "Z-A" just like our Python implementation.

It's a good idea as you're learning Assembly code to take a look in a Monitor program at the memory locations. You'll DEFINITELY need to do this for debugging. My favorite Commodore Machine language 101 book has its examples exclusively in a Monitor, so if you're lost, put a pin in this post and spend a couple weeks reading that book. THERE ARE NO SHORTCUTS when it comes to Assembly/Machine language.

Looking at these in the Machine Code monitor we see that the Assembler has lined them up like this:

I'm using the Monitor built into the Super Snapshot cartridge. Whatever monitor you use may display this differently. Read the documentation.

The inner loop starts at $C0B1 and the outer loop starts at $C0CB. I know, I know, the monitor prints everything in Hexadecimal and our tables were written in decimal in the Assembler. Feel free to switch it up if this is too much conversion.

The first thing to do is a snap. We just need to print the "inner" ring so let's do that. We can actually print the "outer" ring as well on the line under it while we're at it.

chrout = $ffd2
plot   = $fff0

pinner
	.block
    	ldx #6
    	ldy #6
    	clc
    	jsr plot ;kernal call set the cursor position to 6 down
    		 ; 6 to the right
            
        ldx #0
loop	lda inner,x
	jsr chrout ;kernal call to print char at current pos
        inx			
        cpx #26 ;do this 26 times
        bne loop
        rts
        .block
        
pouter
	.block
    	ldx #7 ; down one line
    	ldy #6
    	clc
    	jsr plot 
            
        ldx #0
loop	lda outer,x
	jsr chrout 
        inx			
        cpx #26 ;do this 26 times
        bne loop
        rts
        .block
        
Great, it works. I added a border color to mine. Try the Programmer's reference guide for how to do this or "8 Bit Show and Tell" channel if you want to YouTube it

Tangent: I'm obviously doing this with the Western alphabet in American English. I think it would be fun to do this in other languages and maybe even character sets. I understand that there are some ROM hacks to implement other character sets into the Commodore like Arabic and Japanese. I'd LOVE to hear about any work you do with those.

Shift "outer"

I set up two labels (think variables kinda) in zero page. You don't actually need to use zero page here, I just do out of habit if there are locations available

zp1 = $fc
zp2 = $fd
I used zp1 and zp2 out of habit here. Use whatever labels make sense to you

You could just as easily use labels and let the Assembler find a free location for you:

zp1 .byte 0
zp2 .byte 0
Again, name these "variables" (they're labels) whatever makes sense to you

Now we're going to load the leftmost and rightmost bytes into zp1 and zp2 and then loop through each location, copying one to the y register, saving what's in zp1 to that location and then saving what's in y back to zp1 so we can use it in the next position. Finally we put zp2 which we stored in the beginning into the leftmost location in the table.

shiftrouter
	.block
    	ldy outer
    	sty zp1
    	ldy outer+25
    	sty zp2
loop 	ldy outer+1,x
	lda zp1
    	sta outer+1,x
    	sty zp1
    	inx
    	cpx #25
    	bne loop
    	lda zp2
    	sta outer
    
    	rts
    	.bend

If you're still following along, experiment with other ways to do this. This version makes sense to me. I find it readable and it fits my brain. I'm sure there are ways to make it use less memory, or execute faster. This is plenty compact and fast enough for this implementation.

In action

Here's my finished version "in action". I'm checking for the "s" key on the keyboard to be pressed and I'm rewriting that lower row after running our shift routine after I detect a press.

Next

In part 3 coming up, we'll tackle the Caesar cipher and learn now to crack it. Can a Commodore 64 crack codes? We'll find out.

Extra Credit

  • Reverse the direction of the shift
  • add more characters (start with numbers, it's easiest)
  • rewrite our Python implementation to perform the same store and replace we do in the Assembly version

Random Notes

If I find time, I may post all of this code as a free git repo at the end of the series, nicely commented and cleaned up. At the moment I'm concentrating on getting the series done and then will be able to devote the time to giving you all of the answers so you don't have to do any actual hard work of looking it up yourself. Just kidding (or am I?)

OMG Kernal?

Commodore famously (infamously?) spelled the word we today spell as kernel with an "a". I'll be using the Commodore spelling of kernal when referring to the Commodore kernal. Cringe if you like.