Pseudo Random Journal Generator Predictable permutations on programming, technology, and more.

16Jul/100

Silly Encryption Schemes: Part 2

Well this project didn't go as I had planned. Every part of it took about ten times longer than I expected. And in the end, it still didn't function exactly the way I wanted.

First some fun media to show what did work 🙂

Also a short video of it:
YouTube: Distributed Planar Key Encryption

Now let's start where I left off in part 1.

My first task was to come up with the method I would use to intersect my 3D planes. This was actually a fun exercise for me, and this is what I came up with:

Given 3 planes (Pa, Pb, Pc) first intersect Pa and Pb, resulting in a linear equation, giving any point on the line of intersection generated by Pa/Pb. Then using this linear equation, intersect that line with the third plane Pc, and generate the unique point of intersection.

I coded this up using floating point math, and the whole thing only took two or three sessions to get implemented and debugged, but it was actually pretty fun.

Next up, I needed to port my Planar intersection algorithm to fixed point math. To do this I had implement a minimum number of fixed point math operations... this took a while.

I read up on Fixed Point math and began implementing the most basic operations. But then, I realized I needed to implement others such as sin, cos, square root, and that's where things got messy.

For those of you who don't know, Fixed Point math (also referred to as Scaled Math) is simple enough in theory. Take for instance the number 3.14, if we wanted to represent this using integers and not floating point data types, we have to get rid of the decimals. Well the easiest way to do this is to just multiple it by (in this case) 100, making 3.14 into 314.

Now lets say we wanted to add 1.0 to 3.14, but in fixed math, we would need to move 1.0 into our new fixed point math space, again, by multiplying by 100, so 1 obviously becomes 100. Now we add them: 314 + 100 = 414

All pretty logical and easy. And now, if we want to go back to decimals, we just divide by our base (which is 100 in this case) making 414 / 100 = 4.14, so as you can see, things worked out, and we did all our calculations (only addition in this case) in integer math, instead of floating point math, meaning it's 100% deterministic! (aka: the whole reason I'm doing it this way)

So why is it called "Fixed Point Math"? Well when we use 100 here, we are essentially saying that our number will have two decimal places. A Fixed Point "1" in our system here is represented by 100. A Fixed Point 0.5 is represented by 50, like wise a 0.01 is represented as a 1. So how do you represent 0.009? You don't. That's the draw back of Fixed Point math. You have a Fixed number of decimal places, and anything below that is simply lost.... It gets worse.

Let's take a look at Fixed Point multiplication: 3*3 in our system this will look like: 300*300. Now we all know our answer should be 9 (or 900 in Fixed Point), but what happens when we multiply our Fixed Point representations? 300*300=90,000! It's off by a factor of 100! Well that number is familiar, isn't it! See our Fixed Point base number is in the multiplication as well, if you break it down: (3*100)*(3*100)

The fix is simple enough, just divide it out when you are done, so our fixed point multiplication now becomes two operations: (300*300)/100=900

Bbbuuuttt... You don't get off that easy. Let's take a more real world example. I used 64bit ints, and I needed much greater then 2 bits of decimal precision. When you are making a Fixed Point math system on a computer, you need to take into account your actual data type, and realize that each bit of decimal precision reduces the whole number range of your variables. Let's take a look:

Let's use 8bit ints here. This is what a 1 looks like normally:
00000001

Now lets say I want 4 bits of decimals, my one is going to sit here:
00010000

That's the binary representation, but it's still the same thing, our scaling factor, instead of being 100, is now 16 (in base 10).

Now back to the problem of multiplying our numbers which contain the scaling factor. Here we only have 4 bits of whole number precision. The largest whole number we can represent is 15. So, if during the course of multiplication we ever exceed 15, we will over flow our data type, and lose very significant parts of our number. We must prevent this, if at all possible.

It doesn't take much number crunching to realize, that because our multiplication will be off by a factor of our scaling factor, relatively small numbers, when multiplied together, will overflow our data type before we ever get a chance to divide the scaling factor out.

Luckily there is a generally accepted solution to at least try and mitigate this. Since we are using binary instead of base 10 to define our scaling factor, we can use simple binary bit shifting to attempt to alleviate this (this could be done with division, but this is simpler since we are using binary anyway). If we shift each operand in our multiplication to the right a few places, we can reduce the size of the scaling factor that goes into the multiplication, and thus reduce the likelihood of overflowing. So in this example, let's shift each operand 2 places:

00010000 becomes 00000100 (aka 4 instead of 16) here we've halved the scaling factor. Now in an equation:
2 * 2
in Fixed point:
(00100000 >> 2 ) * (00100000 >> 2)
becomes
00001000 * 00001000 = 01000000

And there you go! We pre-shift half of the scale value from each, so that when multiplied together, the scale value repairs itself, and we avoid an overflow in many cases.

SO! Why have I dragged you through this? Because this is the part that ruined my encryption!! Obviously, the pre-shifting knocks off 2 bits of decimals here, so whatever their value was, is lost! This is an accepted drawback of Fixed point math, but not for me!

In my actual implementation I have 64bit ints, with 16bits of decimal precision, and 48bits of whole number range (clearly range was more important to me then precision. My scaling factor is 65,536) which means I pre-shift by 8bits during multiplication.

Here's the problem: if I multiply 3.141592 by 12.345678 I will get a different number than if I multiply 3.14 by 12.34 ( 38.78508323 vs. 38.7476 ), that's a difference in the hundredths place! That's fairly significant! Now if I take that result and feed it into another part of an equation (as happens many many times in my equations), that difference will propagate through along with other inaccuracies, and the final number will be greatly effected by each inaccuracy.

You might say "Why is this a problem, Adam! you knew Fixed Point math was inaccurate when you started this!" and the answer is, because I didn't have the foresight to realize this wrecked the communicativeness of equations!

Using the example above, let's say the result is then multiplied by 8.765432, in theory:
3.141592 * 12.345678 * 8.765432 == 8.765432 * 3.141592 * 12.345678

But because of how the inaccuracies propagate through from one operation to the next, they don't equal each other!!!

So what exactly does this destroy for me? Well if you pass my Planar intersection algorithm 3 keys, it will generate a 3D point (the encryption key).

If you give the algorithm Pa, Pb, Pc, it will create a linear equation for the intersection of Pa/Pb, then intersect that with Pc. The point generated from that will be used to encrypt the file. NNnnnoooowwww if I want to decrypt the file, and I provide the keys in ANY OTHER ORDER (such as Pb, Pa, Pc) the inaccuracies propagating through the equations will result in a significantly different point! Thus when it is used to decrypt the file, the decryption will fail!

It gets worse! Another central tenet of the algorithm is to be able to generate more than 3 keys, and use any 3 of the keys to generate the parent encryption key, but because of this problem, using ANY KEYS OTHER THAN THE ORIGINAL, in ANY ORDER OTHER THAN THE ORIGINAL will never generate the proper 3D point!

I didn't realize all of this right off the bat. I wrote my Fixed Point math, I even implemented the more complex functions: sqrt(), sin(), etc... And moved on.

The encryption itself is actually just a simple XOR. I take the 3D point, parse each component to a string, concatenate them together, and then use CryptoPP to create a secure hash (high randomness, low redundancy, low collision rate), which I use as the bit stream for my XOR encryption. Not terribly secure, but the whole point was the key generation, not the encryption itself. So I was ok with it.

Then I went on to make the 3D view of it all, so it would have "Hollywood style" graphics. I added a "lookat()" function to my camera and learned quite a bit more 3D math in the process of creating and orienting the 3D Planes. All in all, I learned a ton on this project. But when I realized the problem with the math, I became very disheartened, so the 3D View is a bit unfinished... I had intended to do more. But I don't want to now.

Now I'm sure, that given enough time, I could eventually solve these problems. But this is a project with absolutely no practical application. It's demo-able, and I've learned a ton. So it's time I move on.

Time to get back to some actual game development 🙂

P.S.
If you'd like to try it, you can see the project page, and download it directly here (source is included, it's ugly).

Filed under: Uncategorized No Comments
29Mar/100

Back to the grind

Welp, I'm back from my vacation. Actually I got back over a week ago, things have just been really busy.

Some cool photos if you are into Mayan ruins or caves (this pic links to the whole gallery):

Anyway, easing my self back into things I finally finished up a long time (non-technical) project:
Paper Craft - Mad Cat (BattleTech)

You can see the full build log here

(I'm a big BattleTech fan, just started reading the Blood of Kerensky series, any BattleTech fans here?)

I also finished up my encryption project, so I will have a postmortem on that soon, as well as progress on my Arduino hardware project. So keep reading! 😀

Filed under: Uncategorized No Comments
7Mar/100

Arduino Adventures :: Day 7

So on my last post, benryves pointed out that I might be able to use some of the Analog input pins as Digital I/O pins. And as it turns out, he's right. I could swear I read some where that you couldn't, but I was wrong.

Well this put my design in a bit of jeopardy, not because it was wrong or wouldn't work, but just because it might be unnecessary, which would make it kinda silly.

And for a 64 LED circuit, its actually a bit overkill. Because I could hook up four 4x16 demux's and address them just fine with only 16 pins. But if I wanted anything more than 64, I would be out of luck. Since I have had plans for larger arrays all along, this made me feel a bit better about my design. But to make my self feel even better, I made my self a bunch of graphs on how my design is superior to straight demultiplexing 😛

(Efficiency in terms of LEDs per Input Pins increases as you add more pins)

So, being softly reassured by my graphs, I turned my attention to the build.

I still needed quite a few things to manufacture the circuit board. I needed a way to drill the holes in the board. I needed a way to get the circuit design onto the board precisely, and so on. So I did some research and bought some tools! (Who doesn't love power tools!!)

I had read that high RPMs (around 30,000) was key to getting clean precise holes on your boards, and the Dremel 4000 has variable RPM control that can go up to 35,000 RPMs, so I should be good 😀

Also, the printable Acid Resist allows me to design my circuit on the computer, and just print it out, and apply it to the board, very precisely, so that's nice.

For drill bits, all the reading I did mentioned that I would need Solid Carbide Drill bits to really drill precision holes, but they were $5 a bit! So after some quick searching I found a few on E-Bay selling military surplus ones for mmuucchh cheaper:

With all my new tools, I finally got around to designing the actual circuit board. And wow... I under estimated this. It was not trivial. And it's still not perfect.

First thing is, I have these two 3"x5" blank PCBs that I want to use as practice before I etch the much larger 9"x12" blank that I have. So I wanted to design a paired down version of the circuit that would fit on the smaller one. So here it is. This is the actual circuit, but it only has half the outputs that the final one will have (32 instead of 64, there will be two more 4x16 demux's in the final one). And on this one I have all the LED leads on the edge of the board since this is only for testing purposes:

Well that's all from me for a bit. On Wednesday I'm heading to Belize for a week! Gonna romp around in the jungle for a few days 😛

3Mar/100

Arduino Adventures :: Day 6

I had been thinking about how to achieve individual addressing using demultiplexers even before I gave Charlieplexing a shot. But during my preliminary research the stumbling block was that the largest demux I could find was only a 4 to 16. If I wanted to individually address 64 LEDs I would need four of these, thats 16 I/O pins required to drive them all (I only have 14 on the Arduino).

So that wouldn't work. I continued to mull about this because there was an itch in the back of my skull telling me it could still work. And then it hit me! As you may or may not know, demultiplexers have a given number of inputs to select which output pin to activate. But they also have an enable pin that can disable the entire demux (so no output pins are active).

My idea was to hook up all of the four demux inputs up in parallel with each other. So pin 1 for each demux would be hooked up in parallel together to one I/O pin on the Arduino, and same for pin 2, 3, and 4. So to drive all four demux's you only need 4 I/O pins on the Arduino. Now the problem with this of course is that if you select pin 8 for output, then pin 8 on every demux will go active.

My solution is to use a smaller 2 to 4 demux, and hook these outputs up to the enable pins on each 4 to 16 demux. So with only 2 I/O pins on the Arduino I can select which Demux is active, and only that one will have an output pin going active.

When all is said and done, I only need 4 pins to drive the 4x16 inputs, and 2 to drive the 2x4 inputs. Thats 6 I/O pins to individually address 64 LEDs 😀

Now my previous exploration of Charlieplexing was far from a waste of time because it got me thinking about Persistence of Visionas a valid way of presenting a static image. Using this demux method for individual addressing of the LEDs, and Persistence of Vision to present a static image, I have a perfect method for engineering my display! Some bonuses of this method over Charlieplexing are:

  1. The circuit complexity increases linearly as you add more LEDs
  2. LEDs always get the same amount of current
  3. The layout lends itself very well to being in a grid!

So with this rough sketch I set forth! It's a real shame that "The Shack" (Formerly known as Radio Shack, they re-branded them selves, seriously) doesn't carry the stuff they used too. They have just a single cabinet of fairly worthless components. It's a real let down. So finding ICs and other small electronics is a real pain these days. Ordering them from sites is an option, but it took some research to find sites that sell in small quantities. I did find a few good ones finally. Shipping time and cost kinda suck, but what can you do.

The first issue I ran into was that nearly every demux was active LOW. Meaning, all unactive output pins were putting out 5V (HIGH), and when you activated one, it would go to 0V (LOW). Thats fine if you have a logic circuit that is all active LOW. But in my case, that would mean that every LED would always be on, and when I addressed one of them, it would actually turn OFF... Not what I wanted 😛

So the only one I found that was active HIGH had a 4bit transparent latch for the input. Not a big deal, kinda cool actually, but it means I need an extra I/O pin for the latch strobe. That puts me at 5 pins rather then 4 for the 4x16 demux's (since i will be hooking all the strobes up in parallel as well), which makes it 7 pins total, well within bounds. The inputs were active HIGH as well, but oddly the enable was active LOW. So if I'm pushing 5V (HIGH) into the enable pins, it DISABLES the demux, and if I drop that to 0V (LOW) it ENABLES the demux.

This actually worked to my advantage because every 2x4 demux i could find (whos output would feed into the 4x16 demux's enable pin) were active LOW logic, so every output pin would propagate HIGH until I activated one, which itself would then go LOW.

2 to 4 Demultiplexer : CD74HC139E

4bit Transparent Latch/4 to 16 Demultiplexer : MC14514BCP

As I was saying, the thing that sucks with Radio Shack and every other small eletronics outfit going the way of the Dinosaurs, is the shipping time. If i got a dead IC, or burned one out my self, I'd have to wait another two weeks for a replacement. So i ordered double of everything I needed. (Each IC was only like $0.75, so not a big deal). And to be extra careful, I'm ordering IC sockets, so I won't be soldering the ICs directly.

Now I ordered and received the demultiplexers already. And hooked one of the 2x4s up to my Arduino to test it all out. I haven't worked with ICs let alone demux's in years, so I wanted to test out my self as well as the hardware, to know for sure they all work:

This is being controlled by my computer via serial input, so i can flip the inputs manually, and see the output state instantly. I plan on modifying the program to run through each state automatically and verify the output for each input state. Sort of unit testing the ICs. Then I will do the same for my 4x16's.

Still quite a bit to do before I'm ready to begin the build, but it feels good to have a solid design finally.

27Feb/100

Arduino Adventures :: Day 5

As I stated last time, I had decided to try out Charlieplexing as a way of individually addressing 64 LEDs with only 14 I/O pins (9 is all I need for this actually). So I ordered some resistors and some very specific LEDs. Before I get into the build, let me give a high level overview of what Charlieplexing is and how it works, so that you can understand the conclusions I came to later.

Charlieplexing was invented in 1995 by Charlie Allen as a way of driving many LEDs with few I/O pins and nothing but resistors to implement it. It relies on two facts about LEDs:

  1. That they are diodes, thus electricity will only flow through them in one direction
  2. That they have a specific "operating voltage", below which they will not light up even if current is flowing through them

( Instructables has a really great in-depth explanation here. )

Simply put, you hook LEDs up in combinations such that electricity will either not flow through certain LEDs due to the fact they are diodes in the wrong direction, or that electricity will flow through ones you don't want to light up, but not enough current to actually light them:

When all is said and done, only one LED will light up at a time. Thus, individual addressing:

Now the more astute reader may have noticed I just glossed over something. Yes I can turn individual LEDs on by themselves, but as is dictated by the circuit, I can not turn on all the LEDs at once, in fact not even a third of them, and in practice, you can actually only turn one LED on at a time using this method, which sounds pretty limiting. But there is a way around it: Persistence of Vision.

I'm sure you've seen it used some where before but not known it. The idea is if you can turn a light on and off fast enough, the human eye won't be able to perceive that it was ever actually off, and thus it will look like it is always on. So to make this useful, you "schedule" all the lights that you want to be on, and then the software scans through and turns each one on and off in succession, when it gets to the end, it starts over. You have to be able to scan through the lights enough times per second to fake out the human eye:

So with all that, I set forth to implement a prototype on my breadboard, and have a video of it here (it look a long time to make, not because it's long, but because I suck with the video editing software, so give it a watch 😀 ).

Now this whole research and prototype cycle allowed me to draw some important conclusions. And they aren't favorable for Charlieplexing 😛

There are some small issues that make this method problematic for my application.

The circuit layout does not lend itself to have the LEDs in a grid. It could be designed around, but would be a real pain. This isn't a big one, but it's certainly a consideration.

As the circuit expands with more pins, and you want to have more LEDs on at once, I found the LEDs got dimmer. This could be for one of two reasons (or both). It could be the fact that the circuit itself is larger and has more resistance built into it over all (and the current is being split many different ways), and the more LEDs are scheduled to be on, the longer each LED will be off for during a given "scan". Now you can counteract this, by using lower ohm resistors to increase the overall current in the circuit, but then you run into the issue of the "compliment drive" LEDs lighting up dimly when they shouldn't.
And that last issue is a problem I ran into even in my small circuit.

So where does this leave me!

Well it leaves me out in the cold as far as Charlieplexing is concerned.

But I got to thinking... my original idea of using demultiplexers could still work, so that's where I am at, I have a few ideas I'm going to explore on paper, and I'll post when I have something concrete.

24Feb/100

Arduino Adventures :: Day 4

So I've been thinking about what I want my first big project to be, tossing around a lot of ideas. Trying to balance complexity & difficulty VS coolness. (Also, I want the project to be fun to make!) One of the things I've been interested in doing ever since I heard that you could do it at home, was acid etching your own circuit boards, so I wanted that to be a part of the project too.

With those requirements in mind, I finally settled on a project: John Conway's Game of Life. I've written two different versions of it in software previously:

I am absolutely fascinated by the whole thing. At one point I was in the planning stages of a hardware based version using only logic gates. But the complexity was astronomical, I would have ended up building an ENIAC sized machine 😛

But now with a micro-controller to do all the heavy lifting, it's feasible! With that as my goal, I began planning and research in earnest. So what do I need. Well all I really need is a way to display a grid. There are some LCD screens you can buy and hook up, but thats no fun, and doesn't look very cool. So I began looking into LEDs.

Now, in the software version I wrote, the longer a cell had been alive, the more it's color would change. So I wanted multi-color LEDs that I could modulate the color on. The plan was to have a grid of NxN multi-color LEDs. But after thinking things through a little, I decided I had enough issues to deal with anyway, without adding in the whole analog aspect, so I opted for digital (one color, on or off) LEDs.

My next step was to prototype. I needed to determine what the value of N would be. This would determine a lot about the circuit complexity and how I would go about implementing things. Now in the theory behind the Game of Life, the grid is infinite, there for the larger your actual grid is, the more interesting the result will be. So size is key.

The grid in my software version is 64x64. But after looking at things from a hardware perspective I figured roughly 8x8 was the largest I could manager. So I tweaked my software to be 8x8 to see if it was still interesting. It wasn't...

Until I wrapped the world that is! (So each edge is connected to each other edge.) Satisfied that it could still be interesting at 8x8 as long as the edges wrapped to each other, it was time to start thinking seriously about how I was going to implement this in hardware.

The key here, is I need to be able to individually address each LED. An 8x8 grid means 64 individually addressable LEDs, but the Arduino only has 14 digital I/O pins! (and even less analog I/O pins.) So the question became: "How to drive 64 LEDs with only 14 digital I/O pins?"

The first thing that jumped into my head was multiplexing (well, demultiplexing to be accurate). But that meant researching and ordering ICs, and during some research on the interwebs I found a possible alternative called "Charlieplexing". No ICs were required, just a few current limiting resistors. It allowed you to address N(N-1) LEDs where N is the number of I/O pins. Thus with only 14 pins, I could address 182 LEDs! (Plus the circuit looks fun to design)

So I ordered parts for that: 100 red LEDs and some 68 and 82 Ohm resistors (I'll get into why that is later) and I will write up another entry on that build soon 🙂
(Probably do a video too, I'm still exploring video editing software, trying to figure it all out.)

18Feb/100

DIY Capacitive Touch Gloves, Take that Apple patent #20090000010

So a small diversion from my Arduino efforts today, and a focus on warm winter apparel.

I bought a Motorola Droid when it came out last year and haven't looked back to my LG 77C (the C is for crap) or what ever it's stupid model was.

But now that winter is firmly upon us, grinding us down 'till the last breath of hope and life escapes from our frigid, sun starved bodies, as nothing more then a fart in the arctic wind... I got to thinking:

"Boy my hands are cold, wish I could answer phone calls with out having to take my gloves off."

So I began testing a few materials around my house, trying to find something non-abrasive that would create some capacitance on the screen (since they are capacitive touch screens). Nothing worked, not well anyway, so I tried tinfoil which worked of course, but covered it with some thin plastic, as to protect the screen, and it worked!

So without further ado, I give you the DIY Capacitive Touch Glove, or as I like to call it, "The one glove to rule them all":


Filed under: Uncategorized No Comments
15Feb/100

Arduino Adventures :: Day 3

It's time to do my first actual Arduino project!

This is a very simple one, but taught me some very important lessons about physical computing. Modern computers do tons of things so that we as programmers don't have to worry about all the random chaos in the real world. But in physical computing, small micro-controllers like the Arduino don't have the complexity to handle these things, so we as the designers/programmers must handle them our selves.

Take a look and see what I mean:

[I also took this as an opportunity to try making a real video about it. Still learning the best ways to record it all, and splice it together, so some parts of this are rough.]