Four Seasons challenge

Julia.Fischer.Vivaldi

It’s fun to see how fast you can learn to discern between all twelve movements in Antonio Vivaldi’s Four Seasons. I made a web app in Javascript to make it easy to explore the music and challenge yourself with a graded test. To get an A you need to listen and figure out the correct season and movement for 13 out of 16 music excerpts. Click on the picture above to try it out.

 

Annonser

Efficient recursive maze algorithm

screenshot

I made a recursive bisecting maze algorithm in just eight lines of code. (click on above image to see it in action)

codeshot

The efficiency of the algorithm comes at the cost of a fairly low entropy. It means that the randomness of the maze is limited. A high entropy algorithm could ideally produce a maze where you had to traverse every room in the labyrinth in order to move from the room in the bottom left corner to the room to it’s immediate right. This could never be the case with the above listed bisecting algorithm where internal access between rooms within the same bisection is always guarantied.

Roligt att läsa svenska från 1541. Tre bibelöversättningar.

Det är intressant att se hur svenska språket har utvecklats från 1500-talet. Jag spaltade upp en jämförelse av tre översättningar av första Mosebok (Genesis) i Gamla Testamentet. Det är Gustav Vasas bibel från 1541 tillsammans med dess revision som kallas Karl XII:s bibel (1703) och sen är det 1917-års översättning och slutligen den nu officiella den s.k. Bibel 2000.

Exempelbild

Klicka [här] eller på bilden ovan för att komma till jämförelsen.

Det som framgår rätt tydligt är att Karl XII:s bibel egentligen bara är Gustav Vasas bibel med lite moderniserad stavning.

Karl XII:s bibel skippade ofta Gustav Vasas aspirerade konsonanter, d.v.s. många ”h” rationaliseras bort; ”ffu” blir ”fw”; dubbeltecknade vokaler blir ofta enkla som t.ex. ”uu” som Gustav Vasa skriver som ”w” (dubbel-u) blir bara ”u”. I några enstaka fall kan man konstatera att Gustav Vasas bibel har en modernare stavning än Karl XII:s. När Gustav Vasas bibel skriver ”gott” så skriver Karl XXI senare ”godt”. Gustav Vasas bibel skriver ”Låt oss göra” när Karl XII senare skrev ”Låt oss giöra”.

Av allt att döma var man länge rätt nöjd med Gustav Vasas bibel.

Men 231 år efter Gustav Vasas bibel kom ut så tyckte man ändå att det var på tiden. Gustav III tillsatte år 1772 en bibelkommission med syfte att skapa en modernare översättning. Gustav III:s  bibelkommission verkade dock inte överdrivet stressade att bli klara. De tog det ganska lugnt. 144 år tog de på sig. De blev klara år 1917.

 

RSA Algorithm – Simple Demo

I put together a simple interactive demo to illustrate the principles behind RSA asymmetric public-private key encryption.

rsa.demo.2

Click on the image above or [here] to go to the javascript demo.

Note that this demo setup is for pedagogical use only. In order for the method to be of any use in a real encryption scenario we would need to use initial prime numbers more than 100 digits long.

For example, we could use these two prime numbers of 116 digits each:

p = 33 478 071 698 956 898 786 044 169 848 212 690 817 704 794 983 713 768 568 912 431 388 982 883 793 878 002 287 614 711 652 531 743 087 737 814 467 999 489

q = 36 746 043 666 799 590 428 244 633 799 627 952 632 279 158 164 343 087 642 676 032 283 815 739 666 511 279 233 373 417 143 396 810 270 092 798 736 308 917

Multiplied together you’ll get this 232 digits long public key n:

n =  1 230 186 684 530 117 755 130 494 958 384 962 720 772 853 569 595 334 792 197 322 452 151 726 400 507 263 657 518 745 202 199 786 469 389 956 474 942 774 063 845 925 192 557 326 303 453 731 548 268 507 917 026 122 142 913 461 670 429 214 311 602 221 240 479 274 737 794 080 665 351 419 597 459 856 902 143 413

One thing that is truly fascinating and that constitutes the very foundation for the whole RSA concept is the asymmetry in required work between multiplying these two numbers and doing the opposite thing – finding the factors p and q knowing only n.

I programmed a javascript function for big integer multiplication. It can multiply these two 116-digit numbers in 2 miliseconds.

But doing the opposite, doing the reverse operation – factoring – how long time does that take?

In this particular case, it has actually been done. It’s the largest integer hitherto factorized. It took two years of computer processing and was accompliced on December 12, 2009. The CPU time spent on finding these factors by a collection of parallel computers amounted approximately to the equivalent of more than 2000 years of computing on a single-core 2.2 GHz AMD Opteron-based computer.

Professional RSA encryption today uses public keys n of at least the magnitude of 2048 bits. That’s a number with 616 decimal digits and that means we use prime numbers p and q with 308 digits each.

My homemade javascript function multiplies two such primes to form a 616 digit integer in 20 miliseconds.

For the above mentioned Opteron-based computer, the task of factoring a 616 digit integer is estimated to require 6.4 quadrillion years of CPU time. That’s like the age of the universe multiplied by half a million.

The second obvious weakness in the simple javascript demo apart from the prime numbers being too small is the fact that only one character at a time is encrypted with the algorithm.

Let’s look at the scenario shown in the initial screen dump.

n = 323
e = 139 (public encryption key)
d = 259 (private decryption key)

Now we’re going to encrypt the word ”hello” where each letter is represented by its ”ascii-code”

h = 104
e = 101
l = 108
l = 108
o = 111

 

So we RSA-encrypt them with the public key (139) like this:

”h”: 104^139 (mod 323) = 25
”e”: 101^139 (mod 323) = 118
”l”: 108^139 (mod 323) = 243
”l”: 108^139 (mod 323) = 243
”o”: 111^139 (mod 323) = 100

And we can decrypt them using the private key (259) like this:

25^259 (mod 323) = 104 (”h”)
118^259 (mod 323) = 101 (”e”)
243^259 (mod 323) = 108 (”l”)
243^259 (mod 323) = 108 (”l”)
100^259 (mod 323) = 111 (”o”)

The glaring weakness here is of course that anyone having only the public key (139) can produce a translation table relating each non-encrypted letter of the alphabet with an encrypted value. So, even without access to the private key, an unauthorized person can, using this translation table, discover the word ”hello” in the encrypted sequence 25, 118, 243, 243, 100.

The fix for this weakness is to encrypt larger chunks of text at each powermod-operation. The textual chunk size should correspond to the size of n. If n is a 2048 bit value, then you can encrypt the text in chunks of 2048 bits (corresponding to 256 8-bit ascii characters).

But what if a prosecutor for example gets hold of a suspects RSA-encrypted file and he thinks that it contains a certain known compromising document? Wouldn’t he be able to prove  that? If he himself encrypts that known document using the public key he can then look for the same encrypted chunks of 256 charaters in the suspects encrypted file. The solution to this weakness lies in letting a certain portion of each chunk consist of completely random bits of information. The consequence of that system will be that identical files will never result in identical encrypted files.

 

 

Use Game of Life to Generate 256 bit Hash

game.of.life.256.bit.hash

One of the most fascinating aspects of Game of Life is that it illustrates so well how a completely deterministic process can be so unpredictable. Use a fixed starting pattern and run. Watch the result. Use the same starting pattern but change a single cell somewhere. The new result can be as different from the old as night and day.

Absolute determinism plus unpredictability are precisely the two things you look for in a hash algorithm. When you store passwords on a server you don’t store the passwords themselves but their hashes, calculated using some hash algorithm like for example MD5, SHA-256 or Whirlpool.

A user authenticating himself on the server inputs his password and the server hashes the password to see if the hash corresponds to the hash stored on the server.

For a hacker getting hold of the stored hashes, or for the system administrator, there is no way to run the hash algorithms backwards to retrieve the real passwords. The only way to break a hash is to systematically hash every possible password (out of zillions) and see if the hash matches.

I made this Javascript application to illustrate the idea of using Game of Life to generate hash values. The application is not using Conways standard B3/S23-rules but instead B23/S23-rules.

Try to hash different words or sentences differing only by a single letter adjacent in the alphabet and watch how the hash value changes. You can also try to hash some text but before you click on the ”Run 200 steps” click somewhere on the gird with the mouse pointer to change a single bit.

Game of Life with B345/S45 rules

A lot of people are familiar with British mathematician John Horton Conway’s ”Game of Life” – an algorithm to simulate cellular growth and decay, first published in Scientific American in 1970.

The concept is simple. Imagine an infinite grid of empty squares. Each of these squares can either be empty or occupied by a ”cell”. The are only two rules. One rule for empty squares (the birth rule) and one rule for squares occupied by a cell (the survival rule).

Birth: If an empty square has exactly three neighboring cells a new cell is born in that square.
Survival: An existing cell will only survive if it has either two or three neighbors.

These two rules implies a time axis along which the grid will project forward in discrete phases.

But why do we have these specific rules? Why is exactly three neighbors required to give birth to a new cell?

Conway’s classical rules are sometimes abbreviated to the code B3/S23.

The reason for these particular rules to have become so popular isn’t that strange. Anyone who has experimented with a simulation engine using these rules knows that they often create very complex and interesting situations.

But this being a fact doesn’t exclude the possibility of other rules also having the potential of creating complex and interesting scenarios.

Conway himself and others have explored a lot of other possible rules for Birth and Survival.

I played around two days ago with my own javascript-powered game of life engine where I can chose any set of rules for birth and survival. I wanted to explore an idea I had to use the game of life cellular automaton concept to create a cryptographic hashing algorithm. So, by a mere coincidence, I tried the B345/S45 rules and was fascinated by the way that an initial small colony of cells transformed during hundreds of phases only to later die out. This was almost always the fate that awaited small colonies occupying an initial eight times eight square. I tried out new random shaped colonies, one after another and very seldom a shape would pop up that wouldn’t die out but instead grow and grow and never stop growing. How come, I wondered?

I dealt with this question systematically and found out that there are only 36 symmetrical shapes out of a total of 37888 that will grow indefinitely. All the other symmetrical 8×8-shapes will eventually be either totally annihilated or get stuck in small for ever repeating loops of shapes (so called pulsars).

Here is the total set of miracle seeds – the smallest possible symmetrical shapes that I found that will grow forever. All the tens of thousands of others are destined to perish or stagnate.

smallest.possible.symmetrical

I have shown that there exist no smaller symmetrical shapes, for example 7×7-shapes or 6×6-shapes, that will grow indefinitely.

Add or remove a single pixel anywhere and they will die – that’s how sensitive they are (try it out for yourself).

So these are the symmetrical ones. What about the asymmetrical ones?

I don’t know, but I guess that you can’t find an asymmetrical shape smaller that 8×8 that will grow indefinitely.

It could be tested systematically but the number of all shapes that occupy a maximum space of 8 times 8 squares are much larger than just the symmetrical ones.

Click on this link or on the picture above to go to my B345/S45 simulation engine.

Update: July 28 2015

Amazing news. After seventeen hours of automatic testing of random shaped populations eight different asymmetric 8×7 indefinite growers presented themselves!

8x7 grower 8x7 grower 2 8x7 grower 3 8x7 grower 4 8x7 grower 5 8x7 grower 6 8x7 grower 7 8x7 grower 8

I  also found three shapes that lasted a long time but in the end didn’t quite make it.

8x7 lasted 539 8x7 lasted 542 8x7 lasted 716

They lasted 539, 542 and 716 (!) rounds respectively.

Evil Bible Discussion Forum

evil.bible.774px I sometimes encounter the idea that engaging in philosophy is an activity of the past or that the subject of philosophy is mainly about studying what ancient bearded greek men draped in white linen said to one another. As a philosophy teacher I find it interesting to challenge that idea.

One of the best ways to show that philosophy plays a practical role today is to point to the fact that philosophical discussions are going on in forums all over the internet. People engage their heart and soul right now in discussions about ethics, political philosophy, theory of knowledge, philosophy of science, philosophy of language. One of my favorite examples of philosophical discussions where people tend to be über-passionate is discussions concerning belief in God versus atheism and materialism. Evilbible.com is a website that used to have a forum bustling with animated discussions that made a big impression on me. That forum is now closed an unavailable but I’d like to publish some excerpts to show what the discussions could look like…

evilbible.icon God commands murder and rape, and the Moses salutes…

evilbible.icon Biased – and a few mistakes

evilbible.icon I am a christian pondering why this site exists.

evilbible.icon Atheism = A Leap of Faith? Pt. 2

evilbible.icon Why did it take 7 days?

evilbible.icon A response to an essay about atheists