« Posts under Programming

Privacy Tools: How to use the GnuPG encryption software

Here is a tutorial that I wrote for a particularly useful piece of encryption software. Gnu Privacy Guard or GPG allows you to use asymmetric encryption to communicate securely.

Privacy Tools: How to use the GnuPG encryption software

One thing about modern cryptography that many people don’t realize is that it is possible to encrypt communications in such a way that it is literally impossible to decrypt without a key. Symmetric and information theoretically secure schemes like large symmetric keys or one-time pads can provide encryption that is quite literally unbreakable. Without the key, the plaintext is uncorrelated with the ciphertext – the information literally does not exist without both the key and the ciphertext together.

There are other more convenient encryption schemes that are also very secure – in these cases, the amount of computational work required to break the encryption, barring supposed mathematical breakthroughs, is outrageously large. While it is supposedly possible, it is unlikely for any earthly amount of computing capacity, to be able to break the encryption without the key. One of these is RSA – a means of sending messages securely using asymmetric key encrpytion.

Asymmetric key encryption works by generating two keys – a public key which is published for others to use, and a private key which is kept securely by the owner. The public key can be used by anyone to encrypt a message which can only be decrypted using the private key. So users, on obtaining your public key, can securely send you communications. If you obtain their public key, you can then send them messages. This can happen in the open, without the need to exchange keys in private via another secure channel or meeting.

Individual average everyday computer owners and users actually have a great deal of power to secure the privacy of their communications if they want to take the time to do so. It is the intent of this how-to to help educate users on how to use some of these freely available tools to secure their communications and data.

In fact, one of the fascinating things about modern computing is that almost all of the supposedly special high-power encryption/communication/anonymizing tools that are imagined to be the province l33t hackers and super spies are actually freely available as a result of the broader open-source community. All it takes to use them is a little time to figure out how they work. The unit cost of software is zero and all computers are Turing complete. There is nothing that a super empowered agency can do with their computers that you in principle cannot with yours.

(click the link above for more information)

A New Toy: Raspberry Pi

I am playing around with a new toy tonight:

What you see here is a $35 computer on a board called the “Raspberry Pi”. The ‘hard drive’ feeding this thing it’s instructions is a microSD card (with an SD adapter) smaller than my fingernail. It has 8GB though, so it can store a special fork of the Debian Linux operating system (called “Raspbian”), plus a whole lot of other utilities (such as Apache, PHP, MySQL to form a LAMMP server), python, etc. There are libraries available to access the pinouts via python and C, so you can use a full computer environment to bit-bang electronics. The computer comes with two USB ports (currently plugged up with my keyboard and mouse, but if I stick a wireless network antenna in there, I should be able to control it remotely over a wireless network via ssh/sshd/sshfs.)

Honestly, that HDMI cable (what a ripoff) was almost as expensive as the computer itself! You have $35 to play with, don’t you? Why not try it?

Here you can see my first attempt at messing with the pins through a small python program. I am blinking an LED.

I can see all sorts of uses for this thing. You could have an always-on battery/usb powered internet-LAMMPserver-controller that, on recieving some socket connection or webpage-command pings microcontrollers and sends them commands. The microcontrollers could then move motors, turn things on and off, I could turn on my coffee maker, automatically drop a hammer on my alarm clock after detecting a noise, arm the trapdoor over the shark-tank, etc.

 

Quicksort implementation

I’ve recently coded a q-sort template function implementation. It’s part of another project, but it’s sort of stand-alone.

Author: Aaron M. Schinder
Date: 4 May 2013
Purpose: ams_qsort is an implementation of quicksort, the popular O(n*log(n)) sorting algorithm. There are millions of q-sort implementations out there, but this one is mine. This was programmed partially for the ability to sort multiple lists, but mostly for the exercise in converting a recursive program to a procedural loop.

It has some desirable features over most implementations of qsort:
1. It doesn’t use recursion of the function calls. Instead, it implements recursive behavior through the use of a tree data-structure. This means it won’t blow your call-stack when sorting large lists (which is the point of having an O(n*log(n)) sorting algorithm in the first place!).
2. What the actual sorting function returns is not a single sorted list, but a permutation map. The permutation map can be applied not just to this list, but to other related lists as well to sort each according to the first. First you acquire the permutation map that will sort the target list, then you apply it to lists.

Main functions of interest:
bool quicksort(std::vector<T> *V, std::vector<long> *map, bool (*comparator)(T, T));
bool rearrange(std::vector<T> *V, std::vector<long> *map);
void invertmap(std::vector<long > *map, std::vector<long > *inv);
void mapcompose(std::vector<long > *map_in_main, std::vector<long > *map_in_sub, long indstart);

Typical use:
quicksort(&myvector,&map,&comparatorfn);
rearrange(&myvector,&map); //rearranges myvector (sorts it)
rearrange(&myothervector, &map); //rearranges some other vector (sorts it according to myvector)

invertmap(&map,&othermap); //creates a map which, when composed with map, de-permutes it.
rearrange(&myothervector,&othermap); //unsorts the myothervector

bool comparator(T A,T B)
comparator is a pointer to a bool function that returns true if A>B, according to whatever evaluation of A and B you want.

ams-qsort.hpp

ams-qsort.cpp

 

Shapelib

So, I was thinking one day when working on this scheme I have for this unstructured finite difference PDE thing that is one of these never-ending ongoing programming projects of mine.

Wouldn’t it be great if you could take shapes and operate one them as if they were data-types?

Well now you can! At least in 2d. This is pretty much still a work in progress on my part. I intend to add the 3d version of this same logic after I work up the plane-projection and point identification nonsense.

This library has some limitations, but it basically provides you with some shape classes and binary operators (union, intersect, difference). (fairly wide-open ones at that – I’ve tried the whole keeping data private thing, and it just introduces a lot of rigidity IMO. Eventually you want to feed these to some other algorithm, or pry them apart to do something else with, and doing that through entirely redundant set and get members is a waste of time. Why is this part of OO coding practice?)

The shape classes can have arbitrary holes. It’s based on oriented planar straight-line graph stuff.

Anyway, what do you think? Does this sound useful to you guys? I can post the code when it’s properly commented and cleaned up if so. It’ll be useful to me when I finally get the 3d stuff working, so I can build arbitrary 3d shapes.

First Java Applet

So, I just finished looking through some example code from a Java Applet games contest, and managed to wrap my head around their AWT windowing and event system. (It was hard though – the guy who wrote the applet I was parsing a few minutes ago had all sorts of helpful variable names like i,j,sg,bl and piled everything into fifteen nested levels of loops in a single method. :-P)

But it was informative.

And now, I present, my very first java applet:
(For some reason, this sucker just will not display from within a wordpress page. Link to HTML:)
ColorPatch Applet

And the source code:
src

Putting up a new forum

I’m putting up a new forum for family and friends. After getting my head around MySQL administration, now the only choice comes down to which server software will fit my needs best:

* PhpBB3 – this is the end-all be-all everything on it option with a billion and a half knobs to turn
* SimpleMachines – this one seems pretty straightforward. Content might have to be hosted elsewhere though (uploaded pictures and the like).

What to do, what to do … oh yes. That’s right. Study for finals.

(get’s hooked offstage)

Random Stuff

Keepalive …. keeeepalive!

I haven’t posted anything in ages. Graduate school has been eating *all* my time. But perhaps I should continue to post occasionally, even if it isn’t some epic or profound piece of deep insight, or the result of one of my never-ending projects (which seldom produce complete results :-P).

So, random fantasies as to what I might do eventually given time:

I’ve been thinking off and on of setting up my old POS dell server again. I started apache on my machine and was playing around with it, but it would be preferable to set up a gateway/server that could stay on all the time. I don’t like running my main machine constantly for two reasons:

1. Thunderstorms and brownouts – I don’t want my machine dying while I’m halfway across the city. I don’t care if the dell box fries.

2. Random suspicous port-scans from Russia – some dude in Russia keeps trying to connect to things. McAffee pitched a fit once when I had apache open and tried to connect to freenode on IRC. If somethings going to get hacked, I’d much rather it be my POS dell box.

The dell box is interesting. I bought it from a used computer store for $80 (and probably overpayed! :-P). It is a bit flaky in the way I wired the hard drive to the mother board (it’s a SATA drive going through a converter chip that occasionally shorts). On the other hand, it’s a perfect platform for messing around with esoteric server/gateway projects. I’ve currently got it running Fedora 10, and everything works well. I’ve got Apache set up and configured on it.

It would be nice to have it always connected to the internet, but I only have the one modem comcast gave me, and it only has one ethernet port. I would have to configure the dell box as a gateway, and set it up to forward traffic. Fortunately, linux apparently has all the stuff needed to do this. (Routers are internally usually linux/unix computers with certain software setups installed to boot on powerup). Unfortunately, this will require knowing more about networking than I probably do right now.

But to get me started in my pie in the sky project, the following FAQ provides some hints as to the steps required. http://www.stanford.edu/~fenn/linux/

Once I get this project done (read never) it should allow me to have an always-on internet “face” that I can log into remotely, use as a file and web-server, a platform to mess around with internet programming experiments, and forward all my traffic to my main machine which can be on or off half the day.

Levi-Civita Matlab Function

I banged out a quick matlab script for implementing something that has turned up quite a bit lately in my mathematical investigations: The Levi-Civita symbol.

The Levi-Civita symbol turns up in certain definitions of the determinant (including some definitions of partial determinants), and also in Grassman and Clifford Algebra (the branch of linear algebra dealing with the construction of higher order geometric objects from vectors through an operator called the Wedge Product). Evaluating these requires the ability to call on this pseudo-tensor.

So, what is it, and what does it do? The Levi-Civita pseudo-tensor takes a certain group of indices and returns +1 if these are arranged in ascending order, or an order that can be composed as ascending with an even number of swaps. It returns -1, if the permutation is an odd number of swaps away from ascending order. It returns 0 in all cases where there is a repeated index. In general, the levi-civita symbol can be defined for any number of dimensions (number of indices given), and returns values for incomplete lists of indices (such as [3,4,5]) as if the elements not given in that list were prepended in ascending order e_3,4,5 = e_1,2,3,4,5 = 1

Here it is:

LeviCivita.m

Here is how to call it in Matlab:

>> LeviCivita([1,2,3])

ans =

1

>> LeviCivita([2,3,4])

ans =

1

>> LeviCivita([2,4,3,1])

ans =

1

>> LeviCivita([1,4,3,2])

ans =

-1

>> LeviCivita([1,4,3,2,18,91,128])

ans =

-1

Hope this helps anyone else out there who is exploring tensor calculus!

Victory is mine!!! !! !

Finally! I managed to figure out what I was doing wrong. When I calculated the orbital positions on the plane, I was measuring both the perigree axis and the true anomaly from the same reference axis (called k1, 90 degrees from the axis of the ascending node). This was incorrect – in the 3d case I was measuring the true anomaly from the perigree axis, as I was supposed to. Just one tiny change, and now everything works!


Edge cases are evil!

So, I’m in the middle of putting together a bunch of code under a project called “Project Navigator”. Navigator is supposed to help me perform astrodynamics calculations.

While the math involved has been easy, the programming has been a nightmare. Why? Edge cases. I don’t know how many times I thought I was almost done, only to have some obscure numerical condition come up to bite me. If there are hyperbolic transfers, I need code to handle all the period counters to make sure I don’t wander off to infinity in a finite time. I also need to be able to integrate clockwise and counterclockwise around the conic section without bridging any critical angles.

My prior attempt at solving for transfer orbits attempted to avoid all this minutia by running a generalized solver to fit one conic section to bridge the departure and arrival points of the other two. Unfortunately, there are all sorts of perverse local minima lurking in configuration space which my solver delighted in bombing out on. It was also waaay to slow.

Okay, so I did some math and worked through everything on the plane with only one variable. I finally managed to beat all those problems into submission. Only I didn’t. When I tried to map the projected orbit back into three dimensions, I discovered that there was something screwed up about the projection – now there *are* no angles I can pick to match the transfer plane to the departure and arrival points, and I have no idea why, because I quadruple checked my rotation matrices and angle math.

I attempted a C3 plot of the delta-v for departure to Mars. See that blob? It’s supposed to be relatively contiguous, with two minima. Instead it is cut up, folded over, and scattered all over the plot.

Gaah!

I spent an entire week trying to *fix* all the bugs. At this point I’m not learning anything new, I’m just bogging down trying to find out why the code is blowing up.

The most galling thing is that none of this *should* be difficult. It shouldn’t require 4000 lines of code, it shouldn’t need 15 levels of nested if statements to handle everything that goes wrong. I can solve these cases by hand faster than I can via computer!

I’ll take a break, but won’t give up on the project entirely. I seem to have made a few key corrections. It looks (jinx) like I am approaching the end of the fatal bugs.