Elliptic Curves

Public key cryptography, also known as asymmetric cryptography is widely used now days in distributed environments. From key distribution to secure communication and message signing, public key cryptography is everywhere. However, public key algorithms generally are power hungry and clearly not suitable for wireless sensors. Over the last few years Elliptic curve cryptography (ECC) has emerged as an attractive and viable public key system for constrained environments. An elliptic curve E can be defined as points on the equation of the form y² =x³+ax +b, along with a point at infinity. Here a and b are real numbers and 4a³ + 27b² ≠ 0(mod p), p is a prime number greater than 3. This condition makes the curve defined by the above equation to be non singular. The graph of a non singular curve has two components if the discriminant is positive and one if the discriminant is negative. An example of the elliptic curve used in practice is shown below

y2 = x3 + 317689081251325503476317476413827693272746955927x

+ 79052896607878758718120572025718535432100651934

This elliptic curve is used in the Microsoft Windows Media Digital Rights Management Version 2.

The points on an elliptic curve form an abelian group. An abelian group exhibits the following characteristics. We'll see how each of these properties is satisfied by an elliptic curve.

(1) has a group operator

(2) has an identity element with respect to the operator

(3) exhibits closure and associativity with respect to the operator

(4) exhibits commutative property

(4) the existence of inverses with respect to the operator.

GROUP OPERATOR

The group operator defined on the points on an elliptic curve is known as addition.  Geometrically the addition of two points on the curve takes place as follows.

Let there be two points P and Q on the elliptic curve, to add these points a straight line is drawn which passes through the two points. This straight line may or may not intersect the curve at a third point. If it does, then a mirror image of this point is taken on the x axis and this point R is called the sum of P and Q. If the line does not intersect the curve at a third point, we say the sum is the point at infinity.

Algebraically

If we have two points P(x_P,y_P) and Q(x_Q,y_Q), then the point R(x_R,y_R)=P+Q is given by

s = (y_P - y_Q) / (x_P - x_Q) 
x_R = s² - x_P - x_Q and y_R = -y_P + s(x_P - x_R) 

Point doubling is done as below

2P = R where 

s = (3x_P² + a) / (2y_P ) 
x_R = s² - 2x_P and y_R = -y_P + s(x_P - x_R) 

The point at infinity acts as the identity element of the group, therefore, P + O = P.

INVERSE

The additive inverse of a point is its mirror image across the x axis. Let’s assume we have a point P and its inverse -P which is its mirror image across the s axis. A straight line passing through these two points will be parallel to the y axis and thus will never intersect the curve at any other point. Which implies that P + (-P) = O. So we have a valid inverse operation.

CLOSURE

We can see from the above discussion that the addition operation will only produce points which are on the elliptic curve, which satisfies the closure property.

COMMUTATIVE PROPERTY

Geometrically it’s easy to see that two points P and Q will define the same straight line, irrespective of the order. This implies that irrespective of the order the straight line will intersect the curve at the same point and thus produce the same result for P+Q and Q+P.

ASSOCIATIVITY

The proof for associativity is a tedious one which I am skipping here because it’s not relevant to the matter at hand. It should suffice here to say that the group defined by, the points on the elliptic curve obeys the associativity rule.

REFERENCES

http://math.rice.edu/~friedl/papers/AAELLIPTIC.PDF

http://129.81.170.14/~erowland/courses/2009-2/projects/Margolis.pdf

http://cobweb.ecn.purdue.edu/~kak/compsec/NewLectures/Lecture14.pdf

http://www.tataelxsi.com/whitepapers/ECC_Tut_v1_0.pdf?pdf_id=public_key_TEL.pdf

The Spyware Report

For my Trustworthy Networks course, we had to write a report on a malware and I chose to write mine on Spyware. Every few days you find somebody who's talking about how slow his computer has become and everyone including me blames it on buggy software and slow hardware. It’s not until the spyware becomes very obvious and starts showing itself up that we realize what the real problem is. Did you know that 80% of the computers connected to the internet have some sort of spyware installed on them and 9 out of 10 people don’t even know they have spyware? The total financial loss caused by spyware in 2007 was $1.7 billion in US alone!

Spyware is annoying, really annoying but that’s not the worst thing about it. Spyware is growing like anything, so much so that it has left its older cousins the virus and the worm far far behind in internet penetration. And surprise surprise, did you think spyware was illegal like the worm and virus? If you did you were wrong. Current law in most places deems spyware legal. Not that the lawmakers want spyware to be legal, but the spyware makers make use of the loopholes in the law.

I came upon a number of interesting facts, figures and technologies when I was writing my report. A copy of that report can be found here. I have tried to make it easier to read for a non technical person while at the same time trying to fulfill the objective of a technical report. Hope somebody finds it useful.

Coding Standards

Let’s start with the very basic, the coding standards. You don’t find them in a lot of programming books but believe it or not coding standards go a long way in improving your coding efficiency. It’s always better to develop good habits early than try and correct them later like I did. Coding standards are very easy to ignore as they don’t seem to hold any practical value, but if brought into practice can save you a lot of time in debugging and can make your code much more readable.

1. Naming those variables.

Spend a little time in naming your variables. These variables will be littered all over your code, and if you name them intelligently they can help make your code more readable. Not only does “int loopCounter” manages to convey its purpose in a much better way than “ int a”, it helps you keep track of the code when it spans thousands of lines. A number of conventions exist namely camelBack, underscore_notation and the Hungarian notation for naming the variables. The important thing to keep in mind though is to choose one of them and be consistent throughout your code. Do not switch from one notation to the other in a program, it makes the code confusing and difficult to read.

CamelBack int loopCounter

underscore_notation int loop_counter

Hungarian int iLoopCounter

2. Indentation

Indentation again is one of those things which are easy to miss. Indentation makes your code look well structured, easy to understand and helps in debugging. Indent whenever you start a block of code like a function or an if,else,while,for etc.

3. Comments

For a lot of people including me comments are a pain in the A, but make no mistakes they are useful. They come in really handy when you look at your code after a break of a few days. Also, your code will be easier to understand for someone other than you. I have seen people suffering, while having to work with totally uncommented code. Commenting is a good habit and comment as much as you can even at places, where you think they will be useless.

There are a few more of these standards, but these three are the very basic ones. Writing code which is readable and nicely formatted is always a good thing, I hope these standards help you do that.

Happy Coding!
(Thanks to Dylan for giving me these tips and also for making me realize how important these are.)