Latest: adam_25sep2009.plan
So something a bit more interesting this time (at least for the more technically inclined).

I have been milling around on cryptography sites again, pretending to understand what I'm reading. I can't see the day when my pseudo understanding of asymmetrical encryption will pay off, but hey, you never know ;)

So with thoughts of lovely encryption algorithms dancing in my head, I turned to another topic I had been mulling about, it had to do with some 3D math I had abandoned in another project: Calculating the intersection points of 3D Spheres (It's not redundant, look up 4D Spheres, AKA: Quaternions). This oddly enough lead me to a strange idea for an encryption key generation scheme: Distributed Planar Key Encryption

( Or at least that's what I'm calling it. I don't know if it's something that has been done before. Probably not. It's kinda pointless, but cool :P )

Let me stop right there, I'll come back to the math in a moment. So the idea for this encryption scheme came (as many ideas of mine do) from the movies. You've seen those movies where a super important vault, or missile launch system, or whatever has multiple key holes, and both keys must be inserted at the same time to be able to unlock it? It prevents any single person from misusing their key, as multiple people are required to agree on accessing it.

Well maybe it's just me, but I think that's kinda cool :P

Ok so back to Distributed Planar Key Encryption, that's exactly what this scheme aims to be. You see, several Child Keys will be generated at encryption time. These keys, Child Keys, will combine to form the single unique Parent Key which is the actual encryption key. That of course will be used to encrypt the data.

Then the encrypted data can be sent to each concerned party along with a single Child Key. Or the encrypted data can be kept in a single place, whatever, that's not the point. The point is that no single user can decrypt the data with their given key. They must bring together enough keys to pass the Key Threshold. Once that Threshold is passed, the Parent Key can be generated, and the data can be decrypted.

The important part is that ANY combination of Child Keys, as long as you have enough of them, can generate the Parent Key. So you can't just take the Parent key and break it up into pieces. If you did that, you would have to have specific Child Keys in order to reconstruct the Parent Key. It would also mean that given one Child Key you could begin to solve for the other Child Keys. Needless to say, this would be a bad thing...

OHKAY... So. How do you go about making a scheme that satisfies these requirements! Actually it's a lot easier than you'd think. And this is where we come back to the 3D Spheres I mentioned earlier. Given 4 unique Spheres (they ALL must overlap) you can calculate a single unique point in 3D space where they all intersect. And use that point as the basis for your encryption key (aka: the Parent Key).

So this was my first attempt at a Distributed Key Encryption Scheme, dubbed: Distributed Spherical Key Encryption

But there were some problems. The first was that the math to intersect Spheres is quite complicated. Though I got that working finally. The next problem is what killed it however. See, on the surface of a sphere, there are, in theory, an infinite number of points, because 1.3 is a different number then 1.33, and so on. (Of course, a computer is a finite machine, so it's not quite infinite, but still pretty good.) The problem came in how modern computers store decimal (aka: rational) numbers.

They are called "Floating Point" numbers, and computers actually suck at storing them exactly. You can read up more on why that is on Wikipedia if it really interests you. But here is why it's a problem: when I run these complicated equations to calculate the point of intersection, I get slightly different numbers every time. That is to be expected with Floating Point arithmetic. And we, as computer scientists, have ways of dealing with it. Generally, we look at two numbers that we want to compare, and if the difference between them is under some threshold (epsilon) then we consider them to be the same number.

So the difference between 1.45555 and 1.45556 is less then the threshold of 0.001, we would consider them the same number. I'm pulling these numbers out of you know where, in reality epsilon (aka: 0.001) is much much smaller, but you get the idea.

So it should have worked, right? Wrong. See, the equations are complicated enough, and each time a floating point operation is done (+, -, *, /) there is a slight bit of error. Since so many operations are done in the course of determining the point of intersection, all the different errors add up to quite significant fractions so that the epsilon test would fail ~9 out of 10 times, making it quite unreliable.

What this means is... Given however many Child keys, 9 out of 10 times, you would NOT generate the proper Parent Key. And the Decryption of the data would fail.

My only option was either to round off to, at MOST two decimals, or to use fixed point math and drop decimals all together.

Neither solution was preferable. The first one, would probably make it reliable to 99 in 100, but that 1 in 100 times when your secret data didn't decrypt, wouldn't be a happy day.

The latter method can be refereed to as "Discretizing" the math. Or, making the math use Discrete numbers. The problem with this is that, instead of having theoretically INFINITE points of intersection on the surface of your sphere, you now had a discrete, known number of possible points. Now remember, the point of intersection of 4 Child Keys IS the Parent Key. Thus, the complete Parent Key actually and truly exists on the surface of every single Child Key sphere.

When there were an infinite number of points of the surface of each child, it didn't matter. But now, by making the numbers discrete, there are a known number of points on each sphere. Thus, given a single Child Key you could brute force through the points on that Sphere alone, and find the Parent Key.

(While there are ways to mitigate this [using particularly massive spheres], it actually reduces the search space in other ways, but that's for another article.)

Just to reiterate, one of the key points of this encryption scheme is to not be able to determine the Parent Key with any fewer then N Child Keys. N being the Key Threshold as defined by the algorithm.

So this was clearly not an acceptable solution as it violated one of the core tenants of the encryption scheme.

(As a side note. The spherical keys were flawed from the start. See, N (the Key Threshold) for the algorithm was 4. You need 4 spheres to generate a completely unique point. But given just 3 spheres, you can in fact generate exactly 2 unique points. Well you don't need a computer scientist to tell you that brute forcing 2 possible solutions won't take you very long... Thus with only 3 of the 4 required Child Keys, the Parent Key could easily be deduced.)

Quite a bit discouraged, I stepped back from it and had some dinner. And it struck me. I was only fixated on using Spheres because it was what I had been working with previously in an unrelated project. And that in fact, as I just mentioned, they are quite poorly suited to the task anyway.

3D Planes however are perfect!

For those who forgot their highscool geometry:
3 Dimensional Plane: A theoretical surface which has infinite width and length, zero thickness, and zero curvature.

  • Planes have a theoretically infinite surface area, thus they don't suffer the same problems from using discrete, fixed point math

  • Planar intersection testing is much simpler then Spherical intersection testing.

  • It only required 3 planes to determine a unique point of intersection (Thus the Key Threshold is one less then for Spheres)

  • Given 2 keys (AKA Planes) an entire line of intersection results with theoretically, infinite points on it, even with discrete math, the security of the algorithm doesn't degrade as you approach but do not meet the key threshold.

So while 3 keys are the minimum that must be generated, you can generate any number you wish that all intersect at a single unique point, and any 3 keys can be intersected to unlock the Parent Key.

This was exactly what I had been searching for. So I began coding in earnest. (It also occurred to me, that a Linear Key system could work as well, reducing the number of Child Keys required down to 2. But I stuck with the Planar Keys.)

Now. That's all well and good. Mission accomplished and all that. (No really!) But encryption can be a very boring subject to many people. And it sure doesn't look as cool as it does in the movies, crazy blocks flying every which way to unlock the secret file. Which got me to thinking. I am actually using 3D constructs in the math, so there really is no reason I couldn't visualize this in a 3D app. Ya know, actually show the different planes (keys) in a 3D view, and show them intersecting, and then highlight the common intersection point. I could even do a little animation with it to make it snazzier.

So that's what I'm currently working on, and I will be sure to post here about it when it's done!

Post a Comment
Your Name:
Your Comment:


Commenting has been permanently disabled