Category Archives: Uncategorized

The Greatest Romance Stories of All Time

2
Filed under Uncategorized

Or, why I’ll never understand women.

Gone with the WindWoman doesn’t love her husband for a long time, then finally falls in love with him. He says “I don’t give a damn” and leaves her.
CasablancaTwo former lovers meet up, then part ways and never see each other again.
TitanicJack freezes to death.
Romeo and JulietThey both die.
The NotebookShe forgets who he is, and they both die.

Guitar Tabs for Android Kikaider: The Animation

1
Filed under Uncategorized

I couldn’t seem to find any decent tabs for the songs Jiro plays in Android Kikaider: The Animation (an anime that used to play on Adult Swim a few years ago), so I made up my own.
Disclaimer: The following is my own interpretation, not to be sold, don’t sue me etc.

Jiro’s Theme

————————-5—————————————-
———6—–5—–6——-6———–6—–5—–6————
———7—–7—–7——————-7—–7—–7————
—–7——————————-7—————————-
-5———–5—–5————-5———–5—–5————–
——————————————————————

Theme of Gemini

—–11—10—–11————-11—10—–8————————–
-8——————8——-8—————–11—–9————–8–
———————————————————–8—10——
———————————————————————–
———————————————————————–
———————————————————————–

—–11—10—–11————-11—10—–8——————-8——
-8——————8——-8—————–11—–9—–11——-8–
———————————————————————–
———————————————————————–
———————————————————————–
———————————————————————–

———————————————————————–
-8—8h9—8————–11———————11———-8h9——-
—————10—8——–10——-10—8——–10—————–
———————————————————————–
———————————————————————–
———————————————————————–

—————-8——-8—8/9—9—————-8/9—9————-
-8—9—9h11—————————9———————-9——-
——————————————10———————10—-
———————————————————————–
———————————————————————–
———————————————————————–

———————————————————————–
——9—9/11——-11—11h13—–11-10——————————
-11——————————————————————–
———————————————————————–
———————————————————————–
———————————————————————–

—–11—10—–11————-11—10—–8————————–
-8——————8——-8—————–11—–9————–8–
———————————————————–8—10——
———————————————————————–
———————————————————————–
———————————————————————–

—–11—10—–11————-10h11—10—–8——————-8—–
-8——————8——-8——————–11—–9—–11——-8-
————————————————————————-
————————————————————————-
————————————————————————-
————————————————————————-

—–11—10—–11————-10h11—10/11—
-8——————8——-9——————-
————————————————
————————————————
————————————————
————————————————

–8-9—–9—9/11—11/13-
—————————
—————————
—————————
—————————
—————————

An Interesting Random Number Problem

1
Filed under Uncategorized

In Systems Security class, the professor presented us with an interesting homework problem involving random numbers which I thought some of you might enjoy.

To begin with, a perfect random number generator is a mythical device which spits out bits of either 0 or 1 completely randomly, with a 50% chance of spitting out either a 0 or a 1 at any time regardless of what bits it’s output in the past. Of course, such a generator is impossible to create in deterministic machines (computers), so programmers use pseudo-random number generators instead.

Now, the problem: Assume you have a biased-random number generator – that is, you have a magical random number generator which is completely non-deterministic, but the probability of outputting one bit-state is higher than the other. For example, it could output a "1" with 60% probability and a "0" with 40% probability, or perhaps output a "1" with 0.01% probability and a "0" with 99.99% probability. The only thing known about the probability of outputting a 0/1 is that it’s fixed and greater than 0%.
Given only a computer which can read bits from this biased-random number generator, can you create a perfect random number generator? (and if so, how?)

Java BigInteger Benchmarks

2
Filed under Uncategorized

According to this page (near the bottom), when Java 1.3 switched from using a native BigInteger implementation to a purely-Java implementation, it gained an increase in speed of "as much as 5x or more." This has led many people to believe that Java’s BigInteger class is comparable in speed to the popular Bignum and GMP C-libraries.

I recently got to work with both BigInteger and Bignum for a project implementing a signing scheme related to RSA, so I decided to go a bit out of my way and compare the speeds of each on my machine. In addition, I needed a list of the first 16-million odd prime-numbers, so I implemented a simple Sieve (pronounced "siv," not "seeve") in both Java and C, with some surprising benchmarks.

The Setup
I used the current latest versions of the Java runtime (1.6.0.07) and OpenSSL (0.9.8i) in conducting these tests. They were run on an HP Pavilion dv9720us laptop with a dual-core Turion64 TL-60 (2 GHz) under Windows XP. Neither program was written to explicitly take advantage of the dual-core setup, and as far as I could tell (observing Windows task-manager), neither of them did.

BigInteger vs Bignum
The following table summarizes the results. Note that when I say small exponentiation, what I mean is a large (1024-bit) base to a small (32-bit) power, with a large modulus.

BigInteger vs. Bignum
(smaller is better)
 BigInteger (Java)Bignum(C)
16-million small multiplies and a large exponentiation62.94 seconds16.42 seconds
2-million small exponentiations1892.92 seconds553.41 seconds

Also, here are some graphs for those of you who can’t stand to read a blog-post with no pictures:
There would be a picture here if you had a decent browserHere too.

Sieve of Eratosthenes
Perhaps the previous results should have been expected; after all, Bignum is written mostly in pure assembly, and I’m sure there’s some crazy assembly voodoo that can dramatically increase the speed of adding and multiplying large numbers. However, surely with all the amazing advancements in JIT technology I hear about so often, a plain ol’ prime-number generator in Java will perform almost as fast as, if not faster than (the JIT does, after all, have more information available to it than a normal compiler) its half-brother, C … right?

Sieve of Eratosthenes on 16-million numbers
(smaller is better)
JavaC
30.94 seconds7.80 seconds

And the graph, for those of you who dun’ do numbers so good:

Conclusion
What can I say? Everyone knows that for calculation-intensive tasks, native programs run faster than those that run under a VM – but I believe we’ve all been drastically misled as to the difference in speed between the two. Perhaps you should keep this in mind the next time you’re doing requirements analysis for your next project.

Polka, Burgers, and Sound Financial Advice

1
Filed under Uncategorized

While waiting for the completion of the Sunday Polka Worship Service (…) at my cousin’s baptism, I observed a number of people making burgers for what appeared to be the upcoming outdoor beer-and-polka festival. The large number of blatant health-code violations aside (including one woman who repeatedly picked things off the bottom of her shoes using her gloves), the one thing that stood out most was how incredibly inefficient they all were. To make a burger, each individual worker (of four) would do the following:

  • Take out a single wrapper and place it at the edge of a rather large and empty table
  • Grab two bun-halves out of the bun-bag and place them on the wrapper
  • Lean over towards the slow-cooker, pick up the tongs
  • Open the slow-cooker, grab a burger-patty, close the slow-cooker
  • Carry the patty over to wrapper and set it on the bun
  • Go back to the slow cooker and replace the tongs
  • Go back to the burger, wrap it up
  • Turn around and carry the burger to a cooler about four steps away
  • Open the cooler, place the burger arbitrarily in the cooler, close the cooler
  • Walk back to the table and start over

For most people, this probably seems fine. However, this offends most computer geeks on a deep and personal level. We (with the exception of Linux users) like to finish tasks, especially menial or repetitive ones, as quickly and efficiently as possible. For this reason, using the right tools (read: programs) for the job can mean the difference between minutes and hours when trying to get something done.

When I’m looking for a new program to help with a specific task, I always spend quite a lot of time (sometimes hours) perusing my different options, looking for the best program for the job; all the while secure in the knowledge that my time is well spent and will save me long hours of frustration and repetition in the long run. You, however, are in luck today – I’m going to spare you the long hours of research, and simply tell you what you want!

The following is a short list of what I believe are the best programs to use (for Windows, although many are cross-platform) for a given task. All of these were picked based not only on functionality, but also user-friendliness and support.

Notepad Replacement

  • Notepad++ – This baby has it all. Spell checking, code-highlighting, macros, tabbed viewing, find-and-replace in entire directories (it’s more useful to me than Windows’ built-in find function!). It has SVN and FTP support, can work as a hex-editor, and much, much more. Notepad++ is free and open-source.

Taking Screenshots / Screen-videos

  • Jing – At first I didn’t like Jing because it has a nasty OpenGL overlay that interferes with a lot of programs, but once I realized you can disable that and use a keyboard shortcut, it became indispensable. It can take screenshots and videos (with sound support, automatically compressed) of individual windows, areas, or the entire screen, and save them to your hard-drive, upload them via ftp, or send them to Screencast.com (requires a free account) for anyone to see. Jing is free.

Todo Lists

  • Toodledo.com – Of the many websites and programs I looked at for Todo lists, this was the best. It has everything you could ever need, in an easy to use interface. And best of all, it’s free! (They do offer a paid-for version with even more features)

Financial Budgeting

  • Mint.com – Many people would recommend Quicken Online for this, but I’ve found that Mint.com is not only better, but also cheaper – in fact, it’s free! They make money by making recommendations (which you only see when you request them), and from my research I’ve determined the site is both extremely safe and secure to use. Check out their FAQ for more info on their security practices.

Other free software I couldn’t live without

  • Launchy – A Quicksilver clone that allows you to run a program just by entering it’s name. Vista has this built in, but for XP it’s a godsend – everyone I’ve showed it to has told me they love it.
  • Allsnap – A program that forces all windows to snap to the edges of the screen and to each other. Additionally, you can tell it to force all windows to stay inside the screen at all times, making it a breeze to move a window to the corner of the screen (for those rare occasions you want to move a window outside the screen, you can still do it simply by holding alt).
  • Taskbar Shuffle – a program that allows you to rearrange the icons in the taskbar by dragging them. It also allows you to use the "group all taskbar items" feature to force items of the same type to be near each other, without also collapsing every window into the same damn icon.

These are but a few of the plethora of programs I use constantly – there are many more (email, instant messaging, backup, firewall, antivirus, Internet browser, IDEs, video player…) I rely on almost every day.

So tell me – what programs could you not live without?

Golb

1
Filed under Uncategorized

I wanted to see how easy setting up a WordPress blog was compared to Drupal. This Drupal blog took about 16 hours over the course of about five days to set up. WordPress took about 20 minutes, and only because I was really lazy.
I’m going to use the new blog not to replace this one, but to coincide with it – I need someplace to record my more rampant thoughts, the ones that don’t quite fit here.
If you’re the one person who actually reads this blog, check it out. It can be found here.

No News is Good News

1
Filed under Uncategorized

Sorry, no post for this week – been too busy with work and posting elsewhere.
I know, I know – you feel like I’ve been cheating on you. Don’t worry though – next week, I’ll come home with a nice bottle of champagne, give you a long back-massage, and we can forget this whole thing ever happened.

Until then.

RSA Encryption, Part 3

3
Filed under Uncategorized

Finally, we get to the point: how RSA encryption works. You may want to review parts 1 and 2 to make sure all that modular arithmetic stuff is fresh in your mind.

3. RSA Encryption
For those of you who are unaware, the term encryption is used to describe any method that changes a message so that only its intended recipient can read it. RSA encryption (named after its creators) belongs to a special class of encryption called public key encryption. In public key encyption, separate keys are used to encrypt and decrypt the message: the public key is known to everyone, and can be used to encrypt a message, while the private key is known only to the recipient, and is required to decode the message. This is opposed to symmetric-key encryption, in which the same key must be known to both the sender and receiver.
Thus, if you want to send me a message, all you have to do is encode your message with my public key, and only I will be able to read it (since only I have the corresponding private key). If I then want to send you a message in response, I would simply encrypt my response using your public key.
Think safes: public key encryption would be akin to a safe with a slot on top for inserting messages. Anyone with access to the safe (that is, who has the public key) can drop messages into the safe through the slot, but only the person who has the key to the safe (the private key) can read them.

As a quick refresher, remember what we finished with last time. For all cases important to us, if we want to determine ak (mod n), then
ak ≡ ak mod Φ(n) (mod n).

First of all, we need some convention for mapping letters to numbers and vice versa. Let’s use the convention that A=0, B=1, C=2, …, Y=24, Z=25.

Next, we begin the encryption process by choosing any two prime numbers; for convenience, let’s choose 3 and 11. The product of these will be our n: thus, n = 3*11 = 33. Also, since n is the product of two primes, Φ(n) = (3-1)(11-1) = 20 (as was discussed last time).
We also choose some number less than (and relatively prime to) Φ(n) and compute its inverse (mod Φ(n)) – we will see why in a minute. Let’s choose e=3 and d = e-1 = 7 (since 3*7 ≡ 21 ≡ 1 (mod Φ(n))). Keep in mind that, since we defined e and d to be inverses, their product ed ≡ 1 (mod Φ(n)).
We’ll call the pair of numbers (d,n)=(7,33) our Private Key, and the pair of numbers (e,n)=(3,33) our Public Key.

Now we have everything we need – this is where it gets cool. Let’s try to encrypt the message “HELLO” using the public key. We will do this by encoding the message into numbers using our convention and then taking each number in turn to the power of e (mod n). We can then decrypt by taking each number to the power d (mod n). Let’s go over the example, and then I’ll explain why it works.

Under our encoding, the message “HELLO” is given by the numbers “7 4 11 11 14″. Since e=3, we raise 7 to the 3rd power to get 73 ≡ 13 (mod n); so the first number in our encrypted message is 13. Likewise, 43 ≡ 31 (mod n). After a bit of calculation, we get an encrypted message of “13 31 11 11 5″. We can now transmit this message down the line without having to worry about somebody reading it without the private key.
Now let’s decrypt the message: taking each of the numbers “13 31 11 11 5″ and raising them in turn by the power d=7, we get “7 4 11 11 14″, which decodes to the message “HELLO”. Great!

So how did this all work? The reasoning is simple, actually. If you’ll remember back to last time, we concluded with the formula
ak ≡ ak (mod Φ(n)) (mod n)
In this case, a is our message, and k is e, our public key exponent. Thus, for each digit a, what we’re transmitting is ae (mod n). When the message is received, we take it to the exponent d; thus, the new value is
(ae)d ≡ aed ≡ aed mod Φ(n) (mod n)
by the above formula. However, if you’ll remember, ed ≡ 1 (mod Φ(n)). Thus, after decryption we’re left with simply a (mod n), the original message!††

Yep – it’s just that simple. So simple, in fact, it might seem too simple. Why, you may be asking, can’t someone who’s given e (part of the public key) just calculate its inverse to get d (the unknown half of the private key)? Keep in mind that d is the inverse of e (mod Φ(n)) – and in order to calculate Φ(n), we need to know p and q, the two primes which make up n. And here’s the point – integers, as every computer scientist knows, are hard to factor into primes. Very hard. This means that if n is very large (usually along the order or tens or hundreds of decimal digits), it will be nearly impossible for even the fastest super computers to determine p and q, meaning an attacker is very unlikely to be able to determine Φ(n) and thus determine d. It is this inability to "reverse" our choice of n that gives RSA its security.

For those of you more familiar with computers, mappings based on strings of several ASCII or Unicode characters are most common.
†† The astute reader will have noticed that this only holds true if the encoded message is relatively prime to n. As it turns out, however, for RSA it just happens to hold true even when the message is not relatively prime to n; a proof of this can be found on wikipedia.
Probably. That is, it’s believed to be very hard, but nobody knows for sure.

RSA Encryption, Part 2

1
Filed under Uncategorized

Ah, welcome back my vigilant peons. Today we will be continuing the topic of our last discussion: modular arithmetic. Throughout this discussion, we will assume all numbers are integers.

2. Euler’s Φ Function
If you’ll recall, the last fun-filled example we gave was to find the last digit of 3403 – we did this simply by noting that 34 ≡ 1 (mod 10) and following some simple logic. Today we generalize this technique.

Euler’s Phi (pronounced "fee") Function Φ(n) is the count of the positive integers less than n that are relatively prime to n. “Wait,” I hear you say, in a pathetically clueless tone, “what does it mean for two numbers to be relatively prime?” Well, my young padawan, if you’ll recall from 4th grade mathematics, two numbers are relatively prime if their greatest common divisor (GCD) is 1 – however, even if you don’t remember this, it’s not terribly important. Just know that if the larger of the two numbers is prime, then they will always be relatively prime to one another.

Here’s a quick quiz – if n is prime, what is Φ(n)?
If you’re wracking your brain for this one, then you’re not listening carefully enough. I just told you that if n is prime, then all positive integers less than it are relatively prime to it; since there are n-1 integers less than n,
Φ(n) = n-1 (if n is prime).
Although the general formula for Φ(n) isn’t important for our purposes, I will state (though I know I haven’t been the most trustworthy person in the past, you’re just going to have to take my word on this one) that if n is the product of two primes, say n=p*q (p and q both primes), then Φ(n) = (p-1)(q-1).

Here’s the point of all this – Euler discovered a neat little formula (aptly named Euler’s Formula) which says that, if a and n are relatively prime (there’s that word again!), then
aΦ(n) ≡ 1 (mod n)
The proof of this is fairly simple (in fact, if you know group theory, it consists of literally four words); however, since we’re all so new to this whole modular arithmetic thing anyways, and since we all know that these so-called “proofs” should really only be handled by those lowly peasants of pure-mathematics – high class folk like us are only interested in the blatent, ignorant facts – we won’t dirty our precious hands any more than we have to.

Let’s put our new theorem to use: say we want to find the value of 3123 (mod 77). We note that 77 is the product of two primes; thus,
Φ(77) = (7-1)(11-1) = 60.
Therefore,
360 ≡ 1 (mod 77), and
3123 ≡ (360)2 * 33 ≡ (1)2 * 27 ≡ 27 (mod 77).

Notice carefully what we did there. We realized by Euler’s Formula that 3Φ(77) ≡ 1 (mod 77), so we were able to keep taking out 360 from 3123 until we couldn’t take it out anymore. That is, we converted 3123 to 3123 mod Φ(77) without changing its value (mod 77). It’s not hard to convince yourself that this is true in general; that is, if we’re trying to find the value of ak (mod n), then
ak ≡ ak mod Φ(n) (mod n)

As we will see next post, it is this final formula that allows us to encrypt and decrypt messages in RSA encryption.

Go on to part 3…

RSA Encryption, Part 1

5
Filed under Uncategorized

I’m always really surprised, disappointed, and a bit gassy over how despised anything involving even the simplest of Mathematics is by most Computer Scientists; the mere mention of the word “derivative” is enough to invoke a cringe of repressed childhood-pain from all but the strongest-willed of programmers. However, even if a ‘matrix’ is nothing more to you than a bootleg DVD you torrented when you were 16, you can still enjoy the limitless pleasure provided by a basic understanding of modern mathematics. In fact, after a few simple preliminaries in modular arithmatic (don’t worry – it’s not nearly as scary as it sounds), the algorithm for RSA encryption is actually incredibly simple – so buckle your seatbelt and put on your thinking cap for today’s magical adventure into the strange and wondrous world of mathematics.

1. Modular Arithmetic
If you are still reading this, then either you were misdirected here by the malevolent Internet traffik demon (which means my monetary bribes are working), or you sincerely want to learn how RSA encryption works, in which case I hope our almighty five-legged overlord takes mercy on your soul as it burns in the deepest pits of hell.

Most programmers are familiar with the syntax
18 mod 5
In case you are not, mod (which stands for modulus) simply gives back the remainder from dividing the left number by the right. Since the remainder of 18/5 is 3, this means
18 mod 5 = 3

In mathematics, the syntax is a bit different. Rather than saying “the modulus of 18 by 5 is equal to some number (ie. 3)”, we say “18 is congruent to some number mod 5." It is just as correct to say “3 is congruent to 18 mod 5″ as it is to say “18 is congruent to 3 mod 5.”
We would write this latter statement as 18 ≡ 3 (mod 5).

What we are really saying using this notation is that if we take left-hand of the equation and mod it by 5, then take the right-hand side and mod it by 5, we will get the same thing. When we restrict our world to numbers mod 5 like this, 18 and 3 act like the same number.

This new notation allows us to do some very cool symbol-pushing (all of which, I assure you, is completely valid). For instance, it can be shown that the properties of most normal integer operations – addition, subtraction, multiplication, exponentiation – carry over to modular arithmetic, so that, for example,
xa * xb ≡ x(a+b) (mod n)
It is also rather obvious (and, of course, can be proved) that when adding, subtracting, or multiplying, you can replace one number with another it is congruent to; so, for instance, since 18 ≡ 3 (mod 5),
182 ≡ 32 ≡ 9 ≡ 4 (mod 5)

When working with negative numbers mod n, we find congruencies by simply adding n repeatedly until we get a positive number. For example,
-21 ≡ -1 ≡ 19 (mod 20)
This gives us a new trick to put in our bag for determining (without a calculator) some large numbers mod n:
1910 ≡ (-1)10 ≡ 1 (mod 20)

Cool!

In modular arithmetic, we are usually concerned with only integers; this means that numbers don’t have fractional inverses the way they do in regular arithmetic. That is, there is no number you can multiply 5 by (mod 10) to get 1, since we’re not considering 1/5 a number. Nonetheless, there are certain cases in which numbers in modular arithmetic still have inverses! For instance, notice that 7 * 3 ≡ 21 ≡ 1 (mod 10), so 7 and 3 are inverses (mod 10).

For a final example to show just how powerful modular arithmetic is, let’s calculate the last decimal digit of, say, 3403. Notice that “the last decimal digit” is the same as “its value (mod 10).” Hence, we’re looking to reduce
3403 (mod 10).
The solution is actually quite simple. First, we realize that
34 ≡ 81 ≡ 1 (mod 10)
Then, since 3403 = (34)100 * 33,
3403 ≡ (34)100 * 33 ≡ (1)100 * 33 ≡ 27 ≡ 7 (mod 10)
Thus, in less than a minute, we just determined that the last digit of 3403 is 7, without a calculator!

Go on to part 2…

A number has a unique inverse (mod n) if and only if it is relatively prime to n. The concept of “relatively prime” will be briefly discussed in the next post.