Wiggles, part 4


Just a little ongoing story to give you something to play with until the next blog post.

GSY AZIPGEC LGXYBM QP QEASLFYBQRZ AZPXLXGLPR ZM ZJYE 6,800 LXBQPTX, GSY MZIE BQERYXG ZM DSLAS QEY SZPXSI, SZKKQLTZ, XSLKZKI QPT KCIXSI. GZKCZ, ZXQKQ QPT KCZGZ QBB BLY ZP SZPXSI. XQFFZEZ LX LP SZKKQLTZ, DSLAS LX QAGIQBBC NZXGBC MQENX, NZIPGQLPX QPT FQEKBQPT. XSLKZKI SQX Q AZIFBY XNQBBYE ALGLYX, HIG LX NZXGBC NZIPGQLPX QPT GYNFBYX. KCIXSI LX Q NLO ZM MQENX, MZEYXGX, NZIPGQLPX, QPT NYTLIN-HLR ALGLYX. GSY XZIGSYEP SQBM ZM GSY LXBQPT SQX Q BZG ZM JZBAQPLA QAGLJLGC, QPT LX SZNY GZ NQPC FZFIBQE SZG XFELPR XFQX (AQBBYT “ZPXYP” LP WQFQP). ZPY ZGSYE GSLPR KCIXSI SQX LX GIPPYBX. YLGSYE HYAQIXY ZM FBQCYT ZIG XLBJYE QPT AZFFYE NLPYX, ZE GSQG GSYEY DYEY NQPC QLE EQLT XSYBGYEX TIR LPGZ GSY SLBBX TIELPR GSY HLR DQE GSQG DYEY PYJYE MLBBYT HQAK LP. NQPC ZM GSYXY GIPPYBX QPT AQJYX QEY LRPZEYT, HIG PZG PYAYXXQELBC MZERZGGYP, QPT QEYP’G EYQBBC GSY HYXG FBQAYX GZ JLXLG HC CZIEXYBM LM CZI’EY PZG FEZFYEBC YUILFFYT. QPT, GSYC QEY DLGSZIG UIYXGLZP LPSQHLGYT HC REIYX.

The Last Mechanical Monster


Brian Fies is a physics major that went on to become a webcomic artist. His two big titles are Mom’s Cancer and A Fire Story  (which documents his losing his house in the California fires last year). But, he also wrote and drew The Last Mechanical Monster, which takes the evil genius from the original Fleischer Brothers’ Superman cartoon, The Mechanical Monsters and shows what happens to him after he gets out of jail 65 years later. In the story, the genius (later named “Sparky”) returns to his lab and assembles one last monster from the scrap left over from the others. At the end of the story, Brian added a link to a Mechanical Monster papercraft. I like making papercraft models, and I had extra cardstock left over, so, this is what it looks like.

It took me at least 10 hours to cut out all the pieces, form them and glue them together, but I wasn’t really timing myself. The finished model is a huge 16″ tall. It would be even taller if I had the arms raised in rampage mode.

Brian suggested using brads for the hip-leg, neck, and shoulder joints if you wanted them to move, but I didn’t feel like buying a package of brads just for this. So, I made paper rivets. I cut out disks from the torso joint locations for the neck, shoulders and hips, then I trimmed the disks down a bit smaller than the diameter of the holes. I glued one side of the disk to the glue point for the appendage, positioned the appendage so that the disk was inside the matching hole on the body, then glued a larger piece of paper to the disk on the inside of the body. The limbs and head swivel just fine, but yeah, the rivets loosen up over time and the monster falls over under its own weight. If I were to do this again, I’d consider using small pieces of rubberized magnetic sheets.

I also didn’t glue down the tabs holding the neck collar and hips to the torso, because it’s easier to carry the monster if it’s disassembled. And I left the chest flap and back of the hips free so I could get to the paper rivets from the inside if I needed to. But, otherwise, yeah, LMM is fully ready to go out and monsterize people.

As Brian says, it’s not bullet-proof, and it won’t fly unless you throw it really hard. But, it can dream. In the land of giant mobile suits, Godzilla, and Super Saiya-jin, it can dream.

The world runs on Dunkin’.

Thinking About Encryption, Part 6


I want to tackle a couple transposition ciphers in En/De next, but for various real-life reasons I’m probably not going to be able to get the time for that for a while. I expect it’d only take a few hours each, but I have other stuff of higher priority to get out of the way first. On the other hand, I can scrounge out a few minutes per day to write up this blog entry. So I’ll do this now, and then get to actually writing code later.

There are two very simple transposition ciphers – the Rail Fence, and the Scytale. I’ll start with the Scytale. This was originally a cylinder of wood of a particular diameter, around which the sender would wrap a length of parchment or animal skin. They’d write the message along the length of the cylinder in rows, rotating the cylinder as they went to the next row. When they unwrapped the parchment from the Scytale, the letters were all jumbled. The recipient, though, just needed to wrap the parchment around a second cylinder of the same diameter to read the message back off.

In essence, this cipher can be treated like an array, with a width matching the length of the Scytale (or, the number of wrappings around the cylinder), and a depth corresponding to the length of the message divided by the width. If we pick a width of 4, and use the message “This is a Scytale cipher”, the array looks like:

This
isaS
cyta
leci
pher

To build up the finished cipher message, we just read down the columns from left to right.

TiclphsyehiatcesSair

The first indication that this is a transposition, rather than a substitution, cipher is that a frequency analysis will show that the most common letters are still ETAOIN SHRDLCU. We can break this either through brute force, trying all possible widths up to length/2 (after that we start getting the plain text back out again), or we can look at the spacings between letter combinations for 3- and 4- letter words. For example, the spacings between “t” and “h” are 5 and 9; between “h” and “i” are 1, 5, 9 and 13; between “h” and “e” are 3, 5 and 9; and between “i” and “s” are 5, 5, 6, 14, 15. 5 and 9 show up a lot, so we then go to “the” and “this”. The first “t” is followed by “h”s 5 and 9 letters later, but with a spacing of 9 we get “thi” before running out of letters. For the same “t”, a spacing of 5 gives us “this”, and by taking the length of the message = 20/5, we get a width of 4, which then cracks the cipher.

For the rail fence (or zigzag), we again pick a width up to 1/2 the length of the message, but now we alternate directions, kind of like we’re drawing w’s. For a width of 4, and a message of “This is a rail fence cipher”:

T—–a—–e—–p
-h—s-r—f-n—i-h
–i-i—a-l—c-c—e
—s—–i—–e—–r

and reading off the lines left to right, top to bottom, we get:
Taephsrfnihiialccesier

I’d say that knowing the algorithm, it’s much simpler to brute force the Rail Fence, and pick the width that provides you the greatest number of 3- and 4-letter words when you do a frequency count. The other approach is to look at repeating cycles. From left to right, top to bottom and then back up, “Thisis” represents one full cycle of the zigzag (a length of 6), which gives us the formula: cycle = (# of rails * 2) – 2. (i.e. – (4 * 2) – 2 = 6)

The length of the message becomes important now. At 22 characters, we could have 2 rows of 11 characters each; 3 of 7 each; 4 with 4-7-7-4 characters; 5 with 3-5-5-6-3; etc. We could pad the message so that it always ends on the bottom rail, but it’s not necessary, and actually padding would make it easier to guess the rail width.

If we look at letter spacing, the “t” is followed by “h”s 4 and 10 characters later. The first “h” is followed by “i”s 5, 7, 8 and 15 characters later; and second “h” is preceded by a “i” by one character, and followed by “i”s at 1, 2 and 9 characters. The first “i” is preceded by “s” 4 characters earlier, and followed by “s” 9 characters later. The point of this exercise is that if the message is too short, or lacks common 3- and 4- letter words, there’s no obvious pattern to the letter spacing. Compare this to a width of 5:

T——-a——-c
-h—–r-i—–e-i
–i—a—l—c—p
—s-s—–f-n—–h-r
—-i——-e——-e

Tachrieiialcpssfnhriee

The spacing for “t” and “h” is 3 and 17. For the first “h” and “i” is 2, 4, 5 and 16. For the “i”s and “s”s, it’s between 5 and 8. At least this time, none of the numbers are negative.

If we know that the first word is “this” and we count the spacings between consecutive letters, for the 4-rail, we get 4-7-7 (we have to ignore the first “i” and the first “s”). For the 5-rail, it’s 3-5-5 (we need to ignore the first two “i”s). Of course, if “this” occurred a little later in the plain text, the spacings between the letters would change.

A——-r——-e
-t—–a-a—–c-c
–h—s—i—n—i—r
—i-i—–l-e—–p-e
—-s——-f——-h

Aretaacchsiniriilepesfh

“this” = 5-6-6″.

Meh. With a message this short, just try every value for width from 2 to 11 and do a visual check for the width that gives you a readable result.

Again, both of these ciphers are easy to crack as-is. But, there are a few ways to harden them. First, we could reverse the letters on alternating rows. Or we could use a keyword to set the width of the cipher (i.e. – “maple” (12345), and then rearrange the associated rows so the keyword letters are in alphabetic order (“aelmp” (25413)), Or, we could do both.

These two variants alone would throw off the letter spacings, and if you didn’t know this was an option, brute-forcing the ciphers would be a waste of time, because you’d only be expecting the letters to be going one way, and you’d miss all the other combinations the algorithm knows about.

Why go through this? Well, if we look at the Vigenere cipher, it is attackable because the keyword used creates a predictable cyclic pattern. So, if we break up that cyclic pattern by applying a rail fence where alternating rows are in reverse order, and the rows themselves are rearranged like “maple” (12345) -> “aelmp” (25413), the Vigenere keyword cycles get disguised.

If we were to try doing something like this by hand to encipher and decipher our messages, it would be time-consuming and prone to error. But, it’s trivial in software. We just need to let our recipient know what algorithm we’re using, and what the keywords are.

And this is where the use of private key ciphers falls apart.

As long as I don’t tell anyone what my algorithm is, I’m fine. If I just use it without publicizing the details (“Hey, recipient, I’m giving you a message using Cipher-1 from the program menu. Use keyword “xyz” to read it.”) and I change the the keyword all the time, I’m going to be pretty safe. But if I try to patent or trademark my method, I have to release the details of the algorithm. Then, if I say, my method combines Vigenere with a rail fence, and the keyword allows me to choose whether to reverse row directions and row orders, then I’m back to square one again, because now someone intercepting my messages knows which methods to brute force prior to checking letter frequencies.

In other words, most algorithms (especially private key ciphers) can be broken if you know the approach, even if you don’t know the key. The only option is to make brute forcing or frequency analysis so time-consuming that the universe would suffer from heat death before a third party could make the cipher text readable. Or, keep the messages short and never repeat your keys.

Wiggles, part 3


Just a little ongoing story to give you something to play with until the next blog post.

OPP YX YWJI YWS YSMPSMEA XD NXPSUM COUZI OMP XBYPXXU EXNNBMJYA ICOESI YX NOZS BIS XD OTT OLOJTOVTS TOMP. J’TT VS HOTZJMQ OTXMQ O COLSP COYW JM O WBQS COUZ HJYWJM YWS TJNJYI XD O EJYA TJZS YXZAX, OMP HJYW O TJYYTS EBULS JM YWS COYW J’TT DJMP NAISTD JM O YJMA, POUZ, POMZ YUSS-TJMSP EBT-PS-IOE TJYYSUSP HJYW IJQMI IOAJMQ “VSHOUS XD YWS HJTP VXOU,” OMP “TXXZ XBY DXU CJY LJCSUI.” YWS SMYJUS EXBMYUA JI TJZS XMS WBQS 1980’I YSGY OPLSMYBUS QONS. AXB MSLSU ZMXH HWOY AXB’TT DJMP MSGY HWSM AXB UXBMP O COUYJEBTOU EXUMSU, XU SMYSU O MSH MSJQWVXUWXXP. JM YWS VJQ EJYJSI, SMYJUS VBJTPJMQI, DJTTSP HJYW HSJUP XDDJESI, IWXCI OMP VOUI, EXBTP VS BISP OI YWS CTOAQUXBMP DXU O DBTT OPLSMYBUS QONS KBIY VA YWSNISTLSI. OMP, SLSUA IJMQTS CTOES AXB QX YX, YWSUS JI O VSYYSU YWOM FSUX EWOMES XD VSJMQ SOYSM VA O QUBS.

Tom Gauld science-like strips


Cartoonist Tom Gauld also likes science, and beats it over the head with a club to show his affections. You can find more by him at You’re All Just Jealous of My Jetpack.

Turing Test

Time Travel Experiment

Satellite

Moon and Comet

Graphene

Dark Energy

Adventures of Schrodie the Cat

Thinking About Encryption, Part 5


I’ve mentioned that there are various ways to harden the random substitution cipher. One specific method is known as the Vigenere Cipher. It is named after Blaise de Vigenere (1523 – 1596), although it was originally described by Giovan Battista Bellaso (1505-?). The basic idea is to create a table of Caesar ciphers, each shifted one more place than the line above.


(Choosing to use the Vigenere cipher in En/De.)

ABCDEFGHIJKLMNOPQRSTUVWXYZ
BCDEFGHIJKLMNOPQRSTUVWXYZA
CDEFGHIJKLMNOPQRSTUVWXYZAB
DEFGHIJKLMNOPQRSTUVWXYZABC
EFGHIJKLMNOPQRSTUVWXYZABCD
FGHIJKLMNOPQRSTUVWXYZABCDE
GHIJKLMNOPQRSTUVWXYZABCDEF
HIJKLMNOPQRSTUVWXYZABCDEFG
IJKLMNOPQRSTUVWXYZABCDEFGH
JKLMNOPQRSTUVWXYZABCDEFGHI
KLMNOPQRSTUVWXYZABCDEFGHIJ
LMNOPQRSTUVWXYZABCDEFGHIJK
MNOPQRSTUVWXYZABCDEFGHIJKL
NOPQRSTUVWXYZABCDEFGHIJKLM
OPQRSTUVWXYZABCDEFGHIJKLMN
PQRSTUVWXYZABCDEFGHIJKLMNO
QRSTUVWXYZABCDEFGHIJKLMNOP
RSTUVWXYZABCDEFGHIJKLMNOPQ
STUVWXYZABCDEFGHIJKLMNOPQR
TUVWXYZABCDEFGHIJKLMNOPQRS
UVWXYZABCDEFGHIJKLMNOPQRST
VWXYZABCDEFGHIJKLMNOPQRSTU
WXYZABCDEFGHIJKLMNOPQRSTUV
XYZABCDEFGHIJKLMNOPQRSTUVW
YZABCDEFGHIJKLMNOPQRSTUVWX
ZABCDEFGHIJKLMNOPQRSTUVWXY

Actually, Simon Singh’s The Code Book starts the table one line down, with “ABCDEFGHIJKLMNOPQRSTUVWXYZ” on the bottom row of the table, but it really doesn’t matter, because row positions aren’t important. You pick the row such that the first letter of the row matches a given letter of your keyword.

So, ok, keywords. You give the recipient of your encrypted message the key that you use to encipher it. This keyword will contain only upper case letters, with no spaces, punctuation, digits or duplicated letters.


(Using “JULY AUGUST” as the Vigenere key phrase.)

As an example, let’s pick “JULY AUGUST”, and then remove the space, and extra “U”s. That gives us “JULYAGST”. We will cycle through this key as we go through our plain text.

Let’s use “THIS IS A VIGENERE CIPHER”.

The first letter of our JULYAGST key is “J”, and the first letter we want to encrypt is “T”. So, go along the top of the above table to “T”, and then down the column to the line that starts with “J”, where we find that our cipher text letter is “C”.

The next plain text character is “H”, and the keyword letter is “U”. Going down the “H” column to the “U” line, we get “B”. We continue in this way until we reach the ninth plain text character, “I”. We’ve gotten to the end of the keyword, so we just start over again with the “J” line.

Our final encrypted message is: CBTQIYSORAPLEXWVRJSCR.


(Encrypted text.)

To decipher the message, use the selected keyword again. Pick the row that starts with the given key letter (i.e. – “J”), go along that row until you get to the desired cipher message letter (“C”), and then follow the column up to the “ABCDE” line to obtain the plain text letter (“T”).

The real strength of this cipher is that it flattens out the frequency distribution of the plain text message, making frequency analysis a lot harder. “R” appears three times in the cipher text, twice for “I” and once for “R”. “E” shows up 4 times in the plain text, but in the cipher text it’s treated as separate instances of “P”, “E”, “W” and “C”.

The Vigenere cipher isn’t perfect. For a long time, it was considered too difficult to use by hand, and its main weakness is in the cyclical nature of the key used. Breaking Vigenere depends first on establishing the key length. The so-called Kasiski examination works assuming that by chance, certain words will be repeated in cycles that are a factor of the keyword apart. That is, if “the” appears twice in the plaintext 25 letters apart, and the keyword is 5 letters long, then “the” will be enciphered the same way both times. Taking the factors of 25 only gives us “5”, which makes the guess easier to make. Once we have the key length, we can apply frequency analysis to groups of letters (1, 6, 11, 16, etc. in group 1; 2, 7, 12, 17, etc. in group 2, and so on). Vigenere is harder to break than a simpler Caesar cipher, but it’s not that bad with a PC.

Say the plain text is: “One of the cars in the store is a red car in the store”, and the keyword is “tank.”
The cipher text would be (spaces added for readability):
HNRYY TUOVA ECBNG RXSGY KEVCT RRNVA ESGTU OLTBB X

“TUO” appears twice (which is what I wanted), 28 letters apart. The factors of 28 are 2, 4 and 7. 2 is too short to make a good key, but 4 and 7 are reasonable possibilities. With a longer plaintext message, we might get more repetitions, making it easier to narrow the keyword length further.

The thing is, though, Vigenere is absolutely painless to use on a PC. And, if you pick a longer key, with shorter plain text messages, it is much harder to crack.

Summary:
The Vigenere is a polyalphabetic substitution cipher.
It consists of a table made of Caesar shifted ciphers.
It uses a keyword to select which row (alphabet) of the (poly) table to use for each character of the plain text.
It’s very hard to break, but it’s not invulnerable.
It’s easy to use as a software app.

Wiggles, part 2


Just a little ongoing story to give you something to play with until the next blog post.

FNE WCFIQFCVS OQW AQXE OVUWE XIUCSH FNE EQULB 90’W, CS FNE BEQUW LEQXCSH IM FV ONQF’W SVO GQLLEX “FNE EGVSVACG KIKKLE,” ONES EDEUB GCFB PVISX CFWELP QPLVVX OCFN ISKIUSEX KQSZ GUEXCF, QSX OEUE LVVZCSH PVU OQBW FV WMESX CF. FNCW UEWILFEX CS NISXUEXW VP XVVAEX GVSWFUIGFCVS MUVYEGFW – WNVMMCSH AQLLW, QAIWEAESF MQUZW, QSX QUESQW – FNQF AQB VU AQB SVF NQDE KEES PCSCWNEX, KIF NQDE WCSGE KEES QKQSXVSEX KEGQIWE FNE XEAQSX PVU FNEA NQX SEDEU EJCWFEX. AVWF VP FNE MUVYEGF OEUE WIMMVWEX FV KE PLQHWNCMW FV WNVOGQWE FNE QUEQ’W OEQLFN QSX/VU QFFUQGFCVSW. SVO, FNEB’UE UIWFCSH, UVFFCSH NILZW FNQF QUE FVV EJMESWCDE FV EDES FEQU XVOS FV AQZE OQB PVU MQUZCSH LVFW CS FNCW SEO OQDE VP GVSWFUIGFCVS.

Hatayama Cast Marble Puzzle


Because I keep taking my puzzles to my English classes to show the students, I have gotten kind of (an undeserved) reputation for being able to solve 3D metal puzzles. A couple weeks ago, one woman brought in the Hatayama Cast Marble puzzle and said that one of her sons had bought it and taken it apart. No one in the family could put it back together again, so she’d wanted to challenge me to reverse solve it. It’s a bit small, but very heavy and well-built, about 2″ square and maybe 1″ deep.

I figured it out after about an hour, but I did have to cheat. The solution, as with most of the 5 star level puzzles from Hatayama, is very elegant. I can now take it apart and reassemble it in under a minute. As with the other puzzles, too, there’s a right way, and a whole bunch of less right ways, to put it together. That part has taken me whole days to figure out. I can’t wait to return it to the student and see what happens.

Thinking About Encryption, Part 4


I’m going to talk about the references I’m using for En/De, and for these blog entries, and I’ll add an elaboration to the random substitution cipher algorithm at the end.

One year ago, I received Simon Singh’s The Code Book for Christmas, and it’s been a major incentive for my learning Free Pascal and wanting to write my own encryption program. The Code Book came out in 1999, so it is a bit dated, but it does have a lot of historical background behind a number of the ciphers he discusses, and he does cover most of the biggies (Caesar, Vigenere, Beale, ADFGVX, Enigma and RSA). He also goes into great detail on how to break Caesar, Vigenere and Enigma. Simon includes enough examples for how to use the algorithms as to help me get over the more confusing parts of the descriptions. So, this book is near the top of my list, and I am rereading it now to figure out what I’d forgotten.

Next, as may be guessed from my last few blog entries, wikipedia is very useful, both in terms of identifying ciphers I want to include in En/De, as well as for describing approaches to cracking them.
Ciphers
Bigram
Letter frequency
Frequency analysis
Index of coincidence
Topics of Cryptography
Vigenere cipher
Kasiski examination
Most common words in English

The above list is good enough for the moment, and I’ll add to it as I feel like.

As for other websites… well, I admit to a certain hesitation to check out most of the sites that come up on a yahoo search simply because they may intimidate me into giving up on En/De before I even start. But, I will include Practical Cryptography here, because they have a good list of ciphers, and I’ll probably use it in deciding which ciphers to tackle next in my program.

As for the elaboration mentioned at the top of this blog entry – I was going through the Singh book, and Simon talks about an inconvenience involving the random substitution cipher.

In essence, random cipher keys need to be written down. Especially when you’re working with something like a one-time pad. This means you have to get the key to your recipient, and they can either lose it, or it can be intercepted by a third party. For a random substitution cipher, the key is a random arrangement of the upper case letters A-Z, and few people can simply commit that to memory to avoid having to write it down.

The work-around is to use a simple key word or phrase, which can in turn be used to generate the full table.


(Generating a pseudo-random substitution table.)

For example, say we choose “july august”. First, we convert the letters to upper case, and then strip out the spaces, any punctuation, and all subsequent duplicated letters. That gives us:

JULYAGST

We then continue with the rest of the letters, starting with the next letter after the key, and again dropping duplicate letters already in the key.

JULYAGSTVWXZBCDEFHIKMNOPQR


(Our new key table.)

This gives us a substitution pattern of A=J, B=U, C=L, D=Y, etc. If we want a new table, just pick a new key phrase. Simple suggestions could be movie, song, TV show or book titles.

Keep in mind, though, that you’re still dealing with a simple substitution cipher, and these can easily be broken through frequency analysis, as described in the last entry.

Wiggles, part 1


Just a little ongoing story to give you something to play with until the next blog post.

SWBWQ UL W NGUYA BTWJG. TUVVTG QIIKL WQA JYWQQUGL TUVVGY VHG JUVUGL, WQA WTTGML WQA VDQQGTL YDQ AGGB UQVI VHG LHWAINL. ZWJK ADYUQE VHG VIKDEWNW LHIEWQWVG (1600’L VI WZIDV 1850), YIWAL NGYG LBGJUFUJWTTM AGLUEQGA VI JDYXG ZWJK IDV IF VHG VINQL LI VHWV UQXWAUQE WYCUGL NIDTA ZG DQWZTG VI LUCBTM CWYJH LVYWUEHV UQVI VHG JWLVTG WV VHG JUVM’L JGQVGY. VHUL CWKGL QWXUEWVUIQ HWYA FIY CIAGYQ VIDYULVL, ZGJWDLG, NHGQ MID’YG NWTKUQE WTIQE W LVYGGV FIY W JIDBTG HIDYL, MID FUQA MIDYLGTF EIUQE VHG IBBILUVG AUYGJVUIQ FYIC NHGQ MID LVWYVGA. VHUQEL WYG W ZUV ZGVVGY QIN, UQ VHWV VHG JUVM BTWQQGYL BTINGA VHYIDEH W TIV IF VHG QGUEHZIYHIIAL VI CWKG YIIC FIY CWSIY VHIYIDEHFWYGL, LI VHGYG WYG LICG LVYGGVL VHWV EI LVYWUEHV VHYIDEH. ZDV, VHWV SDLV JYGWVGA W NHITG ZDQJH CIYG JYWPM AGWA GQAL, WQA HIDLGL ZDUTV UQ LVYWQEG LHWBGL VI FUV UQVI VUQM NGAEGL IF YGWT GLVWVG.