Good Math, Bad Math

Introduction to Block Ciphers

Category: Encryption

Where encryption starts getting really interesting, in my opinion, is block ciphers. Block ciphers are a general category of ciphers that are sort of a combination of substitution and transposition ciphers, and sort of something entirely different. They're really fascinating things, but they're pretty complicated.

The basic core of block ciphers is encryption of blocks. A block is a fixed-length series of bits. The basic cipher is a pair of functions (E,E^-1), where E (the encryption function) takes a block B and a key K, and generates a new block B'=E(K,B), which is the encrypted form of the block; and E^-1 (the decryption function) takes a key and an encrypted block, and returns the original plaintext block: B=E^-1(K,B').

Read on »

Posted by Mark C. Chu-Carroll at 3:36 PM • 12 Comments View blog reactions

Friday Random Ten, The Vacation Edition

Category: Music

I was away on vacation this week, which explains the near-total silence on the blog. But at least you'll get a FRT from me. And some nice posts on cryptography and game theory coming next week.

1. Gogol Bordello, "Dub the Frequencies of Love": Eastern european gypsies meet punk meets reggae.
2. Hawkwind, "Urban Guerilla": A live recording of a rather catchy tune by Hawkwind. Personally, I prefer their spacier stuff.
3. Porcupine Tree, "Glass Arm Shattering": Porcupine Tree is always great. This one starts off slow and quiet, and then builds.
4. IQ, "Harvest of Souls": Peter Nichols, the leader of IQ in their incarnation on this album is nothing short of a genius. This is a wonderful song - which is not surprising, since everything from the "Dark Matter" album is wonderful.
5. Naftule's Dream, "Afterwards": Lately, I've been very into Klezmer - particularly the more modern jazzy/experimental type. Naftule's Dream is one of my favorite bands of this style. They record traditional Klezmer as "the Shirim Klezmer Orchestra", and their more out-there stuff as "Naftule's Dream". This is a deceptively mellow track, which has a lot of strange stuff going on.
6. Genesis, "Supper's Ready": early Genesis - this track is the direct precursor of "The Lamb Lays Down on Broadway", which is one of the best works in the history of rock music.
7. Sonic Youth, "Lights Out"
8. Flying Bulgar Klezmer Band, "Buma": More Klez.
9. Peter Gabriel, "Signal to Noise": a masterpiece off of Peter Gabriel's latest album. This is an amazing track - blending orchestral backing, African singing and drumming, and some traditional progressive tropes. Really great - this gives me chills every time I listen to it.
10. The Flower Kings, "A King's Prayer": As far as I'm concerned, the Flower Kings can do no wrong. I can pick out any track off of any FK album, and be pretty much guaranteed to hear something amazing.

Posted by Mark C. Chu-Carroll at 4:41 PM • 5 Comments View blog reactions

Transposition Ciphers

Category: Encryption

The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be rather dull; in their pure form, they're very simple, and not very difficult to crack, even without computers. But some of the most sophisticated modern ciphers can be looked at as a sort of strange combination of substitution and transposition, so it's worth looking at.

A transposition cipher doesn't change the characters in the plain-text when it generates the cipher-text - it just re-arranges them. It applies some kind of permutation function to the text to produce a re-arrangement, which can be reversed if you know the secret to the the permutation.

Read on »

Posted by Mark C. Chu-Carroll at 7:10 PM • 8 Comments View blog reactions

Friday Random 10, August 22

Category: Music

1. Solas, "Darkness, Darkness": One of my favorite Irish bands doing a great cover of an old song.
2. A Silver Mt. Zion, "Goodbye Desolate Railyard": a decent ASMZ track, but not an outstanding one.
3. Mogwai, "Acid Food": Anything by Mogwai is terrific. This is no exception.
4. Kansas, "Myriad": One of my favorite tracks of the latest from Kansas.
5. Metaphor, "Stella Maris": I just got this album today, and haven't even gotten to listen to it all the way through yet, so I haven't really formed a strong opinion yet. But it sounds like Metaphor, and that's a good thing.
6. Rush, "The Enemy Within": A classic old Rush tune.
7. David Sylvian and Robert Fripp, "Jean the Birdman": this is pretty much what you'd expect from Fripp and Sylvian. Sylvian's crooning; Fripp playing with tape loops and strange tonality. Even though it's what you expect, it's still amazing - these are two of the most creative guy's you'll find anywhere, and when they work together, the result is something special.
8. Porcupine Tree, "The Moon Touches Your Shoulder": A bit off of PTs most traditionally progressive album. Not my favorite bit of the album, but the whole album is amazing.
9. Kruzenshtern & Parahod, "Sippurim": K&P is one of my favorite things to listen to lately. I usually describe it as progressive klezmer, which I think is accurate; but it's also not really adequate. These guys are stretching the boundaries so far that it's hard to describe. There's a very strong Klezmer element; but also very strong Jazz and Rock influences. Their stuff is hard to track down, but well worth the effort. It's really spectacular.
10. Tie the Bonnet: Traditional Irish, from the masters. Lunasa is wonderful. This, however, is not one of my favorite bits by them. Like many popular Irish bands, they tend to over-rush the tempo. It's damned impressive, but it deprives the music of some of its heart. This stuff is music to dance to - but they're playing it at tempos that no one could ever dance to.

Posted by Mark C. Chu-Carroll at 8:50 PM • 0 Comments View blog reactions

Astrology and the Olympics

Category: Bad Probability

An alert reader sent me link to a stupid article published by Reuters about the Olympics and Astrology.

It's a classic kind of crackpot silliness, which I've described in numerous articles before. It's yet another example of pareidolia - that is, seeing patterns where there aren't any.

When we look at large quantities of data, there are bound to be things that look like patterns. In fact, it would be surprising if there weren't apparent parents for us to find. That's just the nature of large quantities of data.

In this case, it's an astrologer claiming to have found astrological correlations in who wins olympic competitions:

Something fishy is happening at the Olympic Games in Beijing. Put it all down to the stars.

Forget training, dedication and determination. An athlete's star sign could be the secret to Olympic gold.

After comparing the birthdates of every Olympic winner since the modern Games began in 1896, British statistician Kenneth Mitchell discovered gold medals really are written in the stars.

He found athletes born in certain months were more likely to thrive in particular events.

Mitchell dubbed the phenomenon "The Pisces Effect" (pisces is Latin for fish) after finding that athletes born under the sign received around 30 percent more medals than any other star sign in events like swimming and water polo.

Read on »

Posted by Mark C. Chu-Carroll at 5:42 PM • 19 Comments View blog reactions

The Food Experience Meme

Category: Chatter

I found a fun meme via Rev. BigDumbChimp, involving food. I'm a sucker for anything involving eating.

1. Venison: Nope.
2. Nettle tea: yes. Didn't like it.
3. Huevos rancheros: Yes, yummy.
4. Steak tartare: nope.
5. Crocodile: Yup. Mediocre. Not a bad flavor, but it had a nasty texture.
6. Black pudding: Gads, no.
7. Cheese fondue: Yup.
8. Carp: Yup.
9. Borscht: I'm an Ashkenazi Jew, of course I've had borscht. Out of a jar, it's absolutely, mind-bogglingly horrible. Cooked fresh, it's at best mediocre.
10. Baba ghanoush: Yum!
11. Calamari: Tried it once. Turned out that I'm violently allergic to it. Not one of my more pleasant food experiences.
12. Pho: Nope, but I've had the chinese version (Nu Rou Mien).
13. PB&J sandwich: of course.
14. Aloo gobi: Yup; in fact, I make it myself. Great stuff - one of the very best things you can do with a cauliflower.
15. Hot dog from a street cart: of course. I'm a NYer.
16. Epoisses: One of my favorite cheeses! Nothing compares to Epoisses washed in Sauvingon blanc. Yum.
17. Black truffle: yup. Overrated. They're very good, but considering what they cost, they need to be *better* than just very good.
18. Fruit wine made from something other than grapes: I've had hungarian brandies made from peaches, but that's not wine. I've had something that's called blackberry wine, but it's really blackberry juice mixed with neutral brandy and sugar, so I assume that doesn't count. So I guess that's a no.
19. Steamed pork buns: Nope. I don't like pork.
20. Pistachio ice cream: yes.
21. Heirloom tomatoes: Oh, yes. Really good, fresh, vine-grown tomatoes - not the commercially bred shippable kind, but the kind that you get from the farmer, and have to carry carefully because they'll bruise - are one of the greatest culinary treasures of the world. The things you buy in the store simply are not tomatoes.
22. Fresh wild berries: Yup. As a kid, I lived in a house on a wooded lot, and there were wild raspberries. The wild ones really do taste better.
23. Foie gras: Yes. Another favorite. Yeah, it's not particularly nice for the duck. I don't care; it's too damned good. Not something I'd eat every day, but it's a treat when I can get it.
24. Rice and beans: Yes.
25. Brawn, or head cheese: No. And I hopefully never will!
26. Raw Scotch Bonnet pepper: Yes, accidentally. My grad-school roommate bought some, not knowing what they were. And then he made me taste one. The heat was mind-boggling, and my eyes starting burning, so I rubbed them. Wound up spending the next half-hour or so in the the bathroom soaking my eye in cold water.
27. Dulce de leche: Yes.
28. Oysters: Yes. I love oysters.
29. Baklava: Yes.
30. Bagna cauda: Yes, I've made it.
31. Wasabi peas: Yes. Eh.
32. Clam chowder in a sourdough bowl: a favorite of mine.
33. Salted lassi: nope.
34. Sauerkraut: NY Jew - of course!
35. Root beer float: yup.
36. Cognac with a fat cigar: I don't do the smoking thing. Cognac, yes; but it's not my favorite. I prefer the subtler Armagnac in the french grape brandies, or Calvados if I can get away from the grapes.
37. Clotted cream tea: Yes.
38. Vodka jelly/Jell-O: No.
39. Gumbo: Yes.
40. Oxtail: No.
41. Curried goat: Yes. I worked for a computer store owned by an Indian family during college. They had a party that they invited all of the employees too. The only thing that wasn't too hot for us to eat was goat. Not thrilling, but not bad.
42. Whole insects: Nope.
43. Phaal: looked it up to see what it was. I'm honestly not sure. See my story two up - I tried nibbles of a few things there, which were considerably spicier than goat vindaloo. So maybe. But since I don't know, I'll count this as a "no".
44. Goat's milk: Nope. Lots of goat's milk cheeses, but not the milk itself.
45. Malt whisky from a bottle worth £60/$130 or more: Once. Didn't much like it.
46. Fugu: Nope.
47. Chicken tikka masala: Who hasn't had this?
48. Eel: One of the most wonderful tasting fish in the world. I adore eel.
49. Krispy Kreme original glazed doughnut: Yes. Not impressed.
50. Sea urchin: No.
51. Prickly pear: Yes. Eh.
52. Umeboshi: Yes. Eh.
53. Abalone: Yes. Eh.
54. Paneer: Yes. Eh.
55. McDonald's Big Mac Meal: Yes. Ick.
56. Spaetzle: I've never had German spaetzle; I have had the hungarian galushka, which are supposedly pretty much the same. It's wonderful. I've also had Da Sha Mien, which is sort of the chinese equivalent, also wonderful. There's nothing quite like the texture of a fresh dough dumpling.
57. Dirty gin martini: Nope. I'm not a huge martini fan, and a martini with the olive juice mixed in just sounds awful.
58. Beer above 8% ABV: Oh, yes. In my opinion, most of the beers worth drinking are up there. I tend to like Belgian bottle-fermented ales, and they can get up to 12-14% ABV. I also once had a fantastic barley wine, which is basically a strongly hopped beer coming in at 18% ABV!
59. Poutine: Yum! My wife is Canadian, and she introduced me to it. If you've never heard of it, it's french fries with fresh cheese curds and brown gravy. It's really, really fantastic stuff. We mail order cheese curds from Wisconsin so that we can make it at home!
60. Carob chips: Yes. It's no substitute for chocolate.
61. S'mores: of course.
62. Sweetbreads: Nope. Very few organ meats appeal to me.
63. Kaolin: Not sure what this is... A quick search suggests one of the ingredients of kaopectate - a horrific substance with which I have had entirely too much experience. (I've got some really awful stomach problems.)
64. Currywurst: Like I said, I'm not a fan of pork. If you could make this with some other meat, it sounds yummy.
65. Durian: Nope. I'd love to try it. Another grad school roommate of mine was from Bangladesh, and raved about how good it was despite the smell. Since when it comes to cheese, the stinkier it is, the more I like it, I suspect that I'd really enjoy it.
66. Frogs' legs: Yes. Greasy, bland. Not thrilling.
67. Beignets, churros, elephant ears or funnel cake: all of the above.
68. Haggis: What am I, crazy? Hell no!
69. Fried plantain: Yes. Ech.
70. Chitterlings, or andouillette: Nope.
71. Gazpacho: Yes! Love it when it's a bit chunky and nice and spicy!
72. Caviar and blini: Yes. Overrated.
73. Louche absinthe: Nope. Definitely want to.
74. Gjetost, or brunost: Yes. Some friends are big fans of it, and they've gotten me to try it. It's very peculiar.
75. Roadkill: No.
76. Baijiu: I think so. When I went to Taiwan to meet my in-laws, we went out to dinner with some of their friends, and we had some kind of very strong, warm stuff. I think it was Baijiu, but I'm not sure. I definitely did not like whatever it was.
77. Hostess Fruit Pie: Yes.
78. Snail: Yum!
79. Lapsang souchong: never tasted it. Smelled it, because of another guy I knew who drank the stuff constantly, but every time he brewed a cup, the entire room would stink like stale cigar smoke. Ech.
80. Bellini: Yup, at one of Mario Batalli's restaurants. My wife ordered it, and I had a taste. Very nice, refreshing.
81. Tom yum: Oh, yes. One of my favorite soups!
82. Eggs Benedict: Yes. As I keep saying, I'm not a big pork fan, so I prefer many of the numerous variants better than the traditional. Benedict with fresh cold-smoked pacific salmon is my favorite.
83. Pocky: Yes. Eh.
84. Tasting menu at a three-Michelin-star restaurant: Nope. Until very recently, I was a non-meat-eater, and I still can't stand most Pork or most organ meats. So there's not much point in the great French restaurants. I have done chefs tasting menu at Nobu, which deserves to be a three-star.
85. Kobe beef: Nope.
86. Hare: Nope.
87. Goulash: Yes! I really like Hungarian food. Goulash, paprikash, roast goose with red cabbage, etc. Hungarian food isn't fancy, but it's really wonderful.
88. Flowers: Yes, in many forms. I've had candied flowers, flowers in salads, flowers in cookies, stuffed zucchini flowers, etc.
89. Horse: Nope.
90. Criollo chocolate: I'm not sure. I've had a lot of very fine chocolates, but I'm not sure if any of it was Criollo. Probably not - the makers generally flaunt it if they use it, so I'd probably know.
91. Spam: Nope.
92. Soft shell crab: One of my favorite foods in the entire world. There is absolutely nothing as wonderful as a Maryland Blue softshell.
93. Rose harissa: no. I've had harissa, but never rose. It sounds wonderful!
94. Catfish: Yes. I love farmed catfish; wild is a bit overwhelming.
95. Mole poblano: Yes, yummy.
96. Bagel and lox: New York Jew. Of course!
97. Lobster Thermidor: no. I'm not a huge lobster fan. It's good, but not my favorite thing. Every time I've had a chance to order it, there's been something I'd rather have.
98. Polenta: Yes. Ick. I hate polenta.
99. Jamaican Blue Mountain coffee: Yes. Overrated. I think that many of the really top-quality Indonesian coffees are better.
100. Snake: Nope.

The Rev also added a few extras.

1. Elk: No.
2. Ostrich: Yes. Several times. I really don't like it. I keep trying it cooked different ways, because people who's taste I trust keep telling me that it's something I should really love. But every time I've tried it, I've been disappointed.
3. Moose: No.
4. Whole hog BBQ. I've been to BBQs where they did it, but since I don't like pork, I didn't have any. (Just the smell of it cooking was unpleasant to me; there's just something about pork that I can't stand. It's not a kosher thing, because there's plenty of non-kosher stuff that I eat all the time.)
5. Wine @ >$400/bottle.: Nope. I'd like to, but I can't afford it.
6. Home made bacon/sausage: again, no pork.
7. Chocolate and chilis: an amazing combination. I found a south american chocolate bar with chilis in it. Strange from an american perspective - they didn't do the kind of very smooth chocolate that we tend to like. This was brittle, with hard crystals of sugar in it, and visible flecks of chili pepper. It was fantastic.
9. Chittlins: Nope.
10. Moonshine: Nope.
11. Quail eggs: Yup.

And I'll add a few of my own that I've tried:

1. Monkfish liver: nice, but not exceptional.
2. Live scallop: amazing!
3. Fried chicken giblets.
4. Duck cracklings. Yummy! This is what you get when you take duck skin, and render it for duck fat. You cook it very slowly to get out the fat without getting any burned skin flavor in it. When you're done, you've got these crispy little bits of duck skin fried in duck fat. A sprinkle of salt, and you've got something amazing.
5. Grappa: amazingly wonderful.

Posted by Mark C. Chu-Carroll at 2:21 PM • 32 Comments View blog reactions

Why is randomness informative? Correcting the Clueless Creationists

Category: Debunking Creationism

Someone sent me some questions about information theory; or actually, about some questions raised by a bozo creationist arguing about information theory. But the issues raised are interesting. So while I'm nominally snarking at a clueless creationist, I'm really using it as an excuse to talk about one of my favorite mathematical subjects.

The creationist is confused by the information theory idea of information and complexity. That is somewhat confusing. Intuitively, we think of information in terms of semantics and communication. We think that information is related to semantic content. And our understanding of semantic content comes from language. So we expect things that are rich in information to be highly structured, like language.

Read on »

Posted by Mark C. Chu-Carroll at 11:17 AM • 59 Comments View blog reactions

Friday Random 10, August 15

Category: Music

One of the things that I always like to talk about is how a natural expression of randomness will periodically produce something that appears non-random - and in fact, if it doesn't, then it's not really random!

This weeks friday random 10 is a great example of this. In the past, when I've been in a mood for a particular kind of music, I'm done random shuffles within a playlist containing the stuff I feel like listening to. I didn't do that this week. I let iTunes randomly pick out 10 things, and these are the first ten from the list. It turned out to be a nice week for progressive music.

1. IQ, "Infernal Chorus": IQ is one of the great neo-progressive bands that started off as a Genesis ripoff. A lot of those bands have gone on to do a two-album magnum-opus work that tries to be comparable to "The Lamb Lays Down on Broadway". IQ is the only one that's really been able to pull it off. "Infernal Chorus" is off of a double-album concept set by IQ called "Subterannea", and in my opinion it's as good as "Lamb". Magnificent.
2. The Flower Kings, "The Devil's Danceschool": Instrumental flower kings featuring improv played on a trumpet piped through a distortion rig. Seriously out-there; they wander pretty far away from the tonic chord in this. It's the kind of thing that only the Flower Kings could really pull off.
3. Yes, "Our Song": Ick.
4. Porcupine Tree, "Mellotron Scratch": Another great neo-progressive band. Porcupine Tree started off as a joke, and turned into one of the best serious bands out there. This is a mellow piece off of their "Deadwing" album.
5. The Police, "King of Pain": a track off of an album that Sting one described as a "nasty piece of work". It's all very dark, but it's good music.
6. Naftule's Dream, "Emperor Red": progressive Klezmer, with a seriously bluesy feel to it.
7. Marillion, "Paper Lies": Brave is one of my favorite Marillion albums. Every bit of it is wonderful. This is a track that's actually sort of catchy, which seems sort of incongruous considering how totally dark "Brave" is. But it fits in, and it's a great song.
8. Spock's Beard, "Skeletons at the Feast": Another band that started off as a Genesis ripoff. They did try to do their own "Lamb", called "Snow", but unlike IQ, they didn't pull it off so well. After that, their founder left, and it took them a while to find their feet again. But they did, and this album is terrific.
9. Genesis, "Here Comes the Supernatural Anaesthetist": I really didn't plan this - it's just the way the shuffle turned out. But here's a track from "Lamb". Not my favorite track, but every on Lamb is incredible.
10. Metaphor, "Battle of the Archons": A relatively unknown neo-progressive band. Definitely not from the Genesis ripoff school.

Posted by Mark C. Chu-Carroll at 1:32 PM • 2 Comments View blog reactions

Introducing Cryptanalysis

Category: Encryption

To understand why serious encryption algorithms are so complex, and why it's so important to be careful with the critical secrets that make an encryption system work, it's useful to understand something about how people break encryption systems. The study of this is called cryptanalysis, and it's an amazingly fascinating field of applied mathematics. I'm going to be interspersing information about cryptanalysis with my cryptography posts. One thing to remember here is that we'll be talking about it mainly in the context of how you can break an encryption system - but cryptanalysis is also used for designing cryposystems, because you can only design a successful cryptosystem by thinking about how it can defeat the ways that it could be broken.

One caveat: I'm going to be describing cryptanalysis in terms of how I understand it, which is sometimes different from classical descriptions by cryptanalysists. My understanding is strongly rooted in computation and information theory, rather than pure math. So sometimes my presentation will be a bit different, but hopefully by staying in the ground where I'm most comfortable, I can do a better job of making it comprehensible.

Read on »

Posted by Mark C. Chu-Carroll at 9:01 AM • 14 Comments View blog reactions