Reporting slider — 11 October 2014

by

Chris Miller

 

The thing I’ve always hated most about school is how you’re force fed answers to questions and solutions to problems you’re either not interested in or, more likely, don’t understand. To this day, I remember the quadratic formula but not the equation it solves, or what solving this equation even means. Just a bad poem I was inundated with for a semester or two. It seems ironic, people spending months and years of their lives absorbed in plumbing mathematical mysteries and solving big problems only to have their solutions, their huge eureka! moments and breakthroughs, thrust down the throats of disinterested high school and college students from then on. It’s kind of how I feel about kids still being forced to read “To Kill a Mocking Bird” in English class.

Back in grade 8, fifty years ago almost to the day, I followed my best friend to his advanced math class (I joined the swim team the same way even though I couldn’t swim). As usual, I’d lost my schedule, and didn’t know where I was supposed to be. School has always bored me silly. Today they call this condition ADD and give you uppers. Back then they called it daydreaming and put you in remedial classes.

But I enjoyed that math class. I remember the teacher once claiming that it’s impossible to trisect an angle with a straight-edge and compass, and that anyone who could would become famous. So of course I spent the night on it. My solution was to make the to-be-trisected angle the top of an isosceles triangle, and, with my compass and straight-edge, create another congruent triangle whose sides were 3 times as long and whose area could be divided evenly into 9 of my original triangle. Then, by connecting the top point to the outside corners of the middle bottom triangle, I trisected my angle. After presenting my breakthrough discovery to the class (the little people I vowed never to forget) the teacher proved me wrong. He showed that the 3 triangles I’d divided it into weren’t congruent, viz. the middle was an isosceles, and so the outer pair couldn’t be, and therefore the 3 angles formed by each of their tops could not be the same. This morning, for the first time in the half a century since, I realized he was wrong. Not about my failure to have trisected the angle (I probably did fail), but in his proof. Any pair of lines trisecting that isosceles triangle’s top angle would’ve formed a middle isosceles triangle. So, he hadn’t so much proved that I hadn’t done it as, were his reasoning sound, that no trisection can possibly exist. I felt vindicated. If I could remember his name, I’d dig him up and rub it in. I really liked that guy.

trisect an angle

Last night, on an episode of “Numbers” which features a genius mathematician, and various other eggheads, who help the FBI solve crimes by using math and science (and which I don’t recommend you watch if you are over the age of nine), they were trying to hack into a terrorist’s laptop. Some brainiac says: “His password’s been encrypted using a Diffie-Hellman code, which is unbreakable.” While this sounds really intelligent and knowledgeable, it’s hogwash. Diffie-Hellman’s a public/private scheme used only for secure key exchanges across public networks (like the internet) and encrypting small amounts of data to verify signatures and whatnot. There are much stronger, faster symmetric encryption methods for securing personal data. And, since all DH does is raise an integer to some unknown power modulo some prime, it’s hard to imagine how anyone could just look at this number and declare it a “Diffie-Hellman code.” Plus, while the DH problem (figuring out the secret exponent some known integer was raised to) is still considered “NP hard” to “difficult” given large enough “safe” primes, better attacks are constantly being devised, machines keep getting faster, and so, as with RSA, these primes keep getting bigger. Up to about 4000 bits now. I know it sounds really geeky and nit-picky to gripe about stuff like this (and it annoys my wife to no end) but it bugs me when TV and movie writers use encryption lingo to sound savvy, but can’t bother to invest 2 or 3 minutes to google up something that might be credible to someone with a modicum of actual interest in or understanding of the subject.

So it always annoys me when some genius hacker says, “It looks like military grade encryption’s been used here. I’ll need some time to break it.” Then everyone stands around looking over his shoulder while he does. In books, too. Like how, in Dan Brown’s “Digital Fortress,” possibly the dumbest book ever written (and not just pertaining to encryption) the government has this supercomputer that can decrypt anything through brute force. Like, go ahead: LZH-compress it, then encrypt and re-encrypt it under 20 different algorithms, even proprietary ones, with 20 different keys. No problem. The government’s supercomputer will sort it all out. Or, send it the output from your two-year-old’s banging on your broken laptop’s keyboard, or random noise from the Big Bang. It’d decrypt that too, I suppose. My point being, data encrypted using strong modern methods cannot be decrypted (without the key).

Twenty years ago I invented a symmetric encryption method. With symmetric encryption, you use a secret key (i.e., [big] number) to scramble and obfuscate to-be-encrypted data (often called “plain text”) into data that is completely indistinguishable (except that you can decrypt it) from random data. In fact, there’s an algorithm for calculating pi, called the Monte Carlo method, that uses random data, and output from any strong symmetric encryption method, e.g., 3DES, Rijndael, Blowfish, Serpent, etc., fed to the Monte Carlo algorithm, will quickly calculate pi to at least several decimal places. It’s always blown my mind a little that seemingly and even demonstrably random data can hide such order. Like does this mean that there might be no such thing as randomness? Or is it order that’s the illusion?

Anyway, with symmetric encryption you need the secret key, the one you used to encrypt, in order to decrypt. Basically you just do everything in reverse. Source code for all the big, vetted methods is available online. But, instead, as a fun exercise, I suggest those interested try to develop one on their own. It might not be as “provably” strong as Rijndael, but it’ll be proprietary, and not knowing or having access to the algorithm used to encrypt something can make hacking it (decrypting without the key) orders of magnitude more difficult. Plus it’ll be fun. Once you’re able to encrypt some plain text message and decrypt it using a secret password or key, try encrypting, but then change only one bit in your key before decrypting. Did it sort of work? Does what you encrypted seem partially recovered? If so, back to the drawing board. Most systems perform what’s called key scheduling to avoid this. They take the original primary key and explode and hash it into a larger key that’s then used.

After inventing my symmetric method, I met with a friend of the family who held a doctorate in pure math and a number of patents pertaining to elliptic curve encryption. Elliptic curve, or ECC or ECDH (like Diffie-Hellman, RSA, et. al.) is what’s called an asymmetric encryption method. Asymmetric methods are cooler and mathier (and more potentially valuable) than symmetric methods and I could tell he was a little disappointed. Bit for bit, symmetric methods are stronger, but, like he pointed out, once one key is compromised, the whole system collapses. All new keys must be reassigned. Like, for example, if anyone were to learn Master Card or Visa’s master 3DES keys, all their cardholders would need new chip cards. Or, in the financial transaction gateway (e.g., POS and ATM switch processing) world, if even one cryptogram (which is a raw key encrypted under some exorbitantly priced box’s hardware-protected master file key) is exposed/known, every key in the entire system, and there are potentially thousands, must be reassigned. But with asymmetric methods, only one key, the public key, if broken, need be changed. Working (symmetric) keys are generated randomly and “agreed upon” on the fly. When this mathematician friend told me that it was possible to give someone enough information to encrypt something but not decrypt it, I said, “Impossible.” Then he laughed.

And that’s how asymmetric encryption became a hobby of mine. More specifically, key agreement protocols. These are methods that allow two users to arrive at a shared secret key that no eavesdropper in the middle can figure out. Most rely on the commutative property of some arithmetic operation. Say, for instance, Bob wants to communicate securely with Alice. Bob, who’s not very mathematically astute and has never heard of division, has devised a custom protocol. His public key is 7. His private/secret key is 5. He multiplies 7 by 5 and sends Alice the 7 and the 35. Alice has no idea what Bob multiplied 7 by to arrive at 35, and doesn’t care. She multiplies the public 7 by her secret 3 and sends Bob the product, 21. Now they each multiply the other’s product by their secret keys. Bob multiplies Alice’s 21 by 5 and gets 105. Alice multiplies Bob’s 35 by 3 and gets… 105! Eve, who is eavesdropping, and who has also never heard of division (or subtraction, for that matter) cannot figure out what they did to that 7 and so cannot figure out their agreed upon 105. After Bob learns about division, he refines his protocol to multiply everything mod 19. Now, 7 x 5 mod 19 = 16, and 7 x 3 mod 19 = 2. Happily it still works! 16 x 3 mod 19 = 10, and 2 x 5 mod 19 = 10. Bob is comfortable in the assumption that modular division is impossible. Eve, who has also discovered division, still cannot calculate 16/7 mod 19 to discover Bob’s secret 5, or 2/7 mod 19 to learn Alice’s secret 3. But, just to be safe, Bob starts using numbers that are 100s of digits long.

The simplest and perhaps second most common method (after RSA) is Diffie-Hellman (DH). With Diffie-Hellman all you do is raise some (huge) public integer to some (huge) private/secret/random exponent modulo some (huge) public prime. The net is rife with examples and explanations to which I can add nothing. Same for Elliptic curve cryptography (ECC). If you do try to code your own implementation of either (really any asymmetric scheme, including Bob’s above), you’ll probably need to know how to calculate multiplicative inverses. These are how division is done in modular arithmetic. A simple example:

3 * 6 mod 7 = 4 (because 18/7 leaves a remainder of 4)

Q: But how does one divide 4 by 3 mod 7 to retrieve the (divisor) 6?

A: One must compute the reciprocal (i.e., multiplicative inverse) of 3 mod 7, or 1/3 mod 7. I.e., given i * 3 mod 7 = 1, solve for i.

Q: How?

A: Trial and error maybe… 1×3=3, 2×3=6, 3×3=9 (I feel like Jethro Bodine), 4×3=12, 5×3=15! 15 mod 7=1, so i=5

Q: So then how do you divide 4 by 3 mod 7?

A: Just multiply 4 by the mod 7 multiplicative inverse of 3, which is 5. I.e. 4 * 5 = 20, 20 mod 7 = 6. So 4/3 mod 7 = 6.

Q: Okay, but what if I need to find the multiplicative inverse of some 100-digit integer modulo some 100-digit prime? The universe is expanding; I haven’t got forever.

A: Euclid’s extended algorithm. But, before you go look it up online, try to figure it out for yourself. Remember, Euclid didn’t have a computer, just a stick and some sand… or was that Pythagoras? Anyway, I spent a couple days on this problem and, in hindsight, came kind of close, was on the right track, and wish now I’d persevered more before googling up the solution.

Just as a heads up, it took me some pain to realize that all remainders in modular cryptographic arithmetic are positive. So that -3 mod 5 is not -3, but 2. If you get a negative remainder after division, you have to add the modulus to it.

You probably/definitely will not figure out how to multiply points on an elliptic curve on your own. But you should now have the tools to perform the math once you’ve sussed it out online.

Here’s another interesting method that can replace both RSA and Diffie-Hellman: http://www.cecm.sfu.ca/CAG/papers/Cheb.pdf If you are like me, you won’t understand 95 percent of the math, but you might be able to grasp the basic idea behind it. And the algorithms for evaluating large Chebyshev polynomials at the end work! Really.

My first attempt at a key agreement protocol wasn’t much different than Bob’s (above) second attempt. It was just modular multiplication, but with a hashing of the multiplier (that confused only me). I even went so far as to contact a patent lawyer. I came “that” close to patenting multiplication. My next attempt boiled down to what at first I thought were the utterly unsolvable intersections of many (e.g., > 100) multidimensional objects, but that some “Ask a Math Geek” site’s mathematician then informed me was just a system of linear equations readily solvable using Gaussian Elimination (which, after banging my forehead and saying, “Doh!” I googled up and coded). My current system now defies brute force (naive) attacks and Gaussian elimination, and might even be some flavor of what’s called the multivariate quadratic problem, which is hot in encryption now. The latest to be patented and implemented is called NTRU, and which is just so insanely gnarly that any examples and explanations I’ve tried to suss out leave me feeling delightfully feeble minded.

I think what draws me to all of this is the same thing that draws me to creative writing. It’s a way of feeling smarter than I am, yet delightfully in over my head; a way of communicating via muses and past sundry eavesdroppers, to connect to one person who might really understand what it is I’m saying.

Share

About Author

(0) Readers Comments

Leave a Reply

Your email address will not be published. Required fields are marked *


seven − = 6