Notes on RSA

There are three parts in RSA

1.     Key generation: where you will generate two keys a public key and a private key.

2.  Encryption: where you use the public key and data to generate the ciphertext.

3.  Decryption: where you use the ciphertext generated in the previous step and the private key to obtain the original data.

Let’s try to understand the example below. Most probably you will be given 4 values and you will be asked to generate public key private key ciphertext and decrypt the ciphertext.

You are given p = 61 and q = 53. You are given e = 17 and the data to be encrypted as m = 65

Step 1. Calculate the public and private keys.

1.     You multiply p and q together and find their product

n = p x q

In our example n = 61 x 53 = 3233

2.    Find the totient of n. If n has two factors p and q, then totient φ (n) = (p-1)(q-1). We already know p and q so the totient of n, φ (n) = (61 – 1) x (53 – 1) = 60 x 52 = 3120.

3.     You need to choose a value for e, which is between 1 and φ (n) which is 3120 in this case. In this case let's e is 17.

4.     Compute the modular inverse of 17 mod φ (n). This is the hard part.

A multiplicative inverse of x mod y will be a number which when multiplied by x and the product divided by y gives the remainder 1.

We can use the calculator here http://ptrow.com/perl/calculator2.pl

Put modulus as the φ (n) value which is 3120 in this case, use a = 17 and hit the 1/a button, the result will be the multiplicative inverse. Let us call the multiplicative inverse d, which comes out to be 2753.

5.   Once you have calculated the multiplicative inverse, you have both the public and the private keys with you.

Public key is (n = 3233, e = 17).

Private key is (n = 3233, d = 2753).

Step 2. Now we encrypt the data given to us using the public key we calculated.

          The formula for encryption is

                   C = m ^e (mod n)

                   C = 65 ¹⁷ (mod 3233) = 2790

Step 3. The result from step 2 is the ciphertext, now we want to decrypt it to obtain the original data m. To do so we need the private key and the following formula.

          M = C ^d (mod 3233)

          M = 2790 ²⁷⁵³ (mod 3233) = 65.

Social Engineering

Why waste your time trying to break passwords and encryptions when you can so easily social engineer. Social engineering can be defined as obtaining information, gaining access or making the target perform certain actions using psychological tricks on a person rather than breaking into a system. Hacking using social engineering is often easier than breaking into computers. In any secure system the weakest link is the human. Humans have cognitive biases, also called the bugs in the human hardware, and social engineers exploit these bugs. There are several techniques of social engineering in existence, some of the more prominent ones are.

1.       Pretexting

Pretexting means, using a fake, invented scenario to persuade the victim to divulge valuable information. Pretexting involves some amount of background research on the victim, so that the hacker appears to be a legitimate person. Pretexting can be in person, online or through phone. Hackers can call individuals, pretending to be customer service representatives or can call company individuals pretending to be high ranked officials and get them to divulge confidential information.

2.       Dumpster Diving

Dumpster diving is gathering information which has been discarded by a company to a dumpster. Things like discarded policy manuals, calendars, outdated hardware, memos and letter provide a huge amount of information to a hacker.

3.       Phising

In a phising scam, the hacker sends the victim an email, usually alerting him about changing his password to a certain website or even just asking them to login to a certain website where they have their account, like facebook, yahoo or some bank website. The scammer then provides a link in the email, which will supposedly carry the victim to the website mentioned in the email. The link instead carries the victim to a fake website which looks exactly like the original website. The difference though is that this website is designed by the scammer to forward the login information to him.

4.       Reverse Social Engineering

Reverse social engineering is the smartest technique of social engineering which has the best probability of getting results to the hacker. In this technique the attacker sets up the system such that the victim comes to him asking for help. Since the victim himself is asking for directions he can be manipulated at will. Reverse social engineering consists of three steps, sabotage, advertising and assisting. First the attacker sabotages the system and causes a problem to arise. He then advertises himself as the person who can fix the problem. This makes people come to him asking for help. He then helps the people fix the problem he himself had created and in the process extracts confidential information bit by bit from them.

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.)