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.

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.

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?

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.

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

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.

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.

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.

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.

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.

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.

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

Hashes

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

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:

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:

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?”

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.

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

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.

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.

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.