N-Queens Problem

The N-Queens problem is a classic in computer science. Place N queens on an NxN chessboard such that no queen can attack another queen.

Wut.

Imagine you’ve got a chessboard and a bunch of queen pieces. Your mission is to place these queens on the board so that none of them can attack each other. That means no two queens can be in the same row, column, or diagonal. It’s like a puzzle where you’ve got to keep the peace in the royal family by making sure each queen has her own personal space.

My friend Robin’s favorite demo is 10 print. And what’s not to love about 10 print? After all, there’s even a book about it.

My Favorite Demo

My favorite demo is more complex but still simple enough to understand. The Maze Generator, from Compute! December 1981 by Charles Bond has been a favorite of mine since it came out. In the filing cabinet of my mind, I even remember it as the “Page 54 Maze”.

Have you ever sat down at your old Olympia typewriter and felt compelled to write poetry in which each word is the same length as successive digits of Pi?

Me too!!!

This is called a Pilish:

The idea of writing a sentence (or longer piece of poetry or prose) in which the lengths of successive words represent the digits of the number π (=3.14159265358979…) has been around since the early 1900’s. - Writing in Pilish

I’ve participated in National Novel Writing Month for the last two years. While I don’t have aspirations of being a fiction author, I think there is a ton of value in writing 1500 words daily. Good writing or bad, 45000 words in a month is worth the effort.

In 2021, I used a DOS 386 with Wordperfect 6.22 to complete the writing for the month and produced a pretty terrible Techno/Wilderness thriller that no one should be subjected to reading. Using a 386 Laptop was a fantastic experience, and WordPerfect for DOS remains one of the best distraction-free word processors ever created.

As we’ve discussed, large integer math is a pretty interesting problem, even for modern computers.

What if we wanted to add very, very, very large integers without using scientific notation, but this time let’s do it extra slowly. Extra slow… this seems like a job for BASIC!!

Strings

We’re going to need to use strings. On the Commodore BASICs of the 80s, strings have a max length of 255, so the largest sum we’ll be able to represent is:

I built the world’s worst paper tape reader some weeks ago. It works pretty okay on anything with a USR-style port like a KIM-1 clone or a VIC-20.

It at least attempts to live up to the world’s worst name. Paper tape was (and is) an interesting medium. Sure it’s hard to work with and fragile, but it also has the advantage of being slow. I mean, what’s not to like??!!!

Dealing with large numbers in computing has been an attractive problem area for a long time. Using an average calculator might lead you to believe that it’s too tricky for most applications.

But it’s not that difficult. And to prove it, we’re going to implement this calculation on machines with 8 Bit registers (I mean, cmon, on this site, you can’t even pretend to be shocked).

Quite a while ago, I started playing with random numbers on 8 Bit machines. I don’t think anyone is doing “serious” work on these machines, but playing with Ciphers and Crypto got me at least curious about how a Commodore 64 generates random numbers.

There are many ways to determine randomness. Humans are pretty good at picking out patterns in visual representations. Luckily our beloved machines have easy screen memory access. Let’s poke some random stuff to the screen and see what we see.

I’ve been obsessed with the Random number generator on the Commodore computers for a LONG time, and I’m not the only one who is, to be sure.

We’ve used this random function in many of the Cipher series articles before, both via BASIC and directly getting randomness from the SID oscillator 3.

Let’s try a “practical” example we might code into a game that throws dice and tests the frequency distribution. For one or two dice, we can easily calculate what a “perfect” distribution should be, so this should be a good test to see if the random number generator is sufficient to make a fair game.

I posted this on Twitter a few weeks ago, but a young lady has been exploring programming in Python and also with Commodore BASIC which is pretty neato. She’s 11 and asked if there was a way to do modulo functions on Commodore BASIC because she’s using her Dad’s VIC-20 and Simon’s BASIC is obviously not available for the VIC-20.

The answer is pretty simple and will actually work in most programming languages.

If we wanted to do A mod B (or A%B in a lot of newer programming languages) we can do it in one line. We’re really just looking for the remainder of a division that we’ll call R

Cryptonomicon Pontifex/Solitaire

We’re back to my favorite book for another round. We’ve done quite a bit with Cryptonomicon so far. One of my favorite moments is when Enoch Root introduces a cipher that two prisoners used to communicate using just a humble playing card deck.

Bruce Schneier

Pontifex is an encryption method you can do with another person using a deck of cards. It was invented for “Cryptonomicon” for Neal Stephenson by Bruce Schneier. He called it Solitaire. In the book it’s called Pontifex to obfuscate the method a little bit.

A while ago, I explained in detail how to generate one time pad sheets and use them to encrypt and decrypt messages.

It turned out to be doable, only requiring a pencil and a way to create random numbers, but it’s slow, error prone and tedious.

Why

The one time pad article was born out of my annual reading of Cryptonomicon. I wanted to learn how to make these pads, which if used correctly are mathematically unbreakable. I figured 3 or 5 other people might read it and learn how to make them too.

Hashes

We did an implementation of a once popular hashing function in Part 8 on RC4 without really going into why.

A hash function is any function that is used to map data of an arbitrary size (input) to a fixed size output. An algorithm is applied to the input and results in a fixed length output called the hash.

In cryptography it’s important to get a repeatable output for a given input, but ideally NO information about the input that created it.

Recap

So far we’ve

• Reversed a string
• Shifted bits left and right (mostly right)
• Brute forced a known simple cipher
• Channeled our inner John Connor by cracking ATM machines
• Searched through a large number looking for matches
• Learned how to use XOR to recover data
• Created a Linear Feedback Shift Register to generate better random numbers
• Implemented a “real” but outdated cipher: RC4

Disclaimer: I’m sure I’ll get an angry email from a mathematician about this, but we’re going for understanding here. No one expects to be looking for large primes on a Commodore 64. Calm down.

Recap

So far in this 8 part series on doing weird things with Ciphers on old computers we’ve:

• Reversed a string
• Shifted bits left and right (mostly right)
• Brute forced a known simple cipher
• Channeled our inner John Connor by cracking ATM machines
• Searched through a large number looking for matches
• Learned how to use XOR to recover data
• Created a Linear Feedback Shift Register to generate better random numbers

The warning

“In September, 1994 someone posted source code to the Cyberpunks mailing list-anonymously. It quickly spread to the Usenet newsgroup sci.crypt, and via the Internet to ftp sites around the world. Readers with legal copies of RC4 confirmed compatibility. RDA Data Security, Inc. tried to put the genie back into the bottle, claiming that it was still a trade secret even through it was public, it was too late. It has since been discussed and dissected on Usenet, distributed at conferences, and taught in cryptography courses.” - Applied Cryptography, Bruce Schneier, 1997

So far in this 7 part (shocked I’ve made it through 7!) series on doing weird things with Ciphers on old computers we’ve:

• Reversed a string
• Shifted bits left and right (mostly right)
• Brute forced a known simple cipher
• Channeled our inner John Connor by cracking ATM machines
• Searched through a large number looking for matches
• Learned how to use XOR to recover data

Author’s Note:

This one stretched my skills quite a bit, but I kept it under 2000 words (by 89). I’m not sure when I started this I knew I’d be doing a Linear Congruential Generator on a 40 year old machine, but here we are ;-)

Review

So far we’ve:

• Reversed a string
• Shifted bits left and right (mostly right)
• Brute forced a known simple cipher
• Faked it, but then looking for a 4 digit known pin
• Searched through a large number looking for matches

We now have most of the basic skills in Assembly to start doing some real work. Let’s tackle what is arguably the most important of the bitwise operators for ciphers and encryption: The exclusive OR. (XOR/EOR)

A common task in our code is to determine the length of something. In this example, let’s check the length of a string like “are you keeping up?”

In Python, this is crazy easy.

#!/usr/bin/env python

message = "are you keeping up?"
len(message)

In 6510 Assembly, this is also easy. Not crazy easy, but straightforward anyway.

messagelength
	ldx #$00
checkdel 
	lda message,x
	cmp #$00 ; or whatever we're using as a delimeter
    	beq done
    	inx
    	jmp checkdel
done 
	stx messagelen
	rts
    
.byte messagelen 0

message .null "are you keeping up?"
    
    

Pretty easy right?

A few minutes into Terminator 2, the young John Connor takes his Atari Portfolio out of his bag and inserts a foil covered card into an ATM machine and proceeds to crack a pin number and steal some cash from an unsuspecting account.

This is a movie prop and doesn’t really appear to do anything useful. It’s almost certainly just a script that runs on the Atari Portfolio, and just counts down some strings to make a “cool” effect.

Well here we are at part three and it’s a lot to pack into one page.

Let’s build upon [what I called the Shift Cipher] and implement what is often referred to as the Caesar Cipher, although there is much debate on when this was really first done.

The idea is the same as our Part 2. We’re going to shift the letters a given number of times, but this time we’re going to do the encoding and decoding programmatically instead of just creating a reference to do it by hand.

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.

Sometime during my weeklong exploration of SHA-256 on a Commodore realized that there was a whole world of exploration that could be explored. Just because a Computer system is old, doesn’t mean it’s not interesting or useful.

I had expected it to take months to figure out the SHA-256 implementation, but it only took me a week or so. This was pretty surprising to me and is an excellent demonstration of what might be possible on a Commodore 64

Last week, at this bat-time on this bat-channel, I talked about checking off one of my 35 year old bucket list items by learning Commodore assembly language. (shut up, you’re old too.) Coincidentally, I picked this up at the time I was re-reading Cryptonomicon by Neal Stephenson for the ump-teenth time. There are a few books that I consider so good that they’re worth re-visiting, and this is one of them.

If you haven’t read it, you don’t need to worry about spoilers. The plot is multi-generational. One character, Lawrence Waterhouse, is a high level Allied Cryptographer tasked with cracking codes and coming up with new encryption methodologies. His weapon of choice for the most secure messages is the one time pad.