Key Exchange: From Carrying Handcuffed Briefcases To Modern Cryptosystems

You should be familiar to handcuffed briefcases in spy movies. Most probably, shared secret key is in the briefcase and the agent transfers the secret key between parties in old fashioned way. Either courier’s hand is cut or he is kidnapped to steal the briefcase. So, handcuffs could not guarantee the security of the briefcase and key.

lucy-handcuffed-1000
Scarlett Johansson in Lucy (2014)

Public key cryptography gives us opportunity to securely transfer secret keys in insecure channels such as internet or broadcasting. Alternative public key algorithms depend on exponential computations and they work on large numbers. That’s why, they have high computation costs. Herein, elliptic curves offer faster computations for key exchange operations. Previous posts related to elliptic curves are described theoretically. Now, we’ll put the theory into the practice as a real world example. Basically, key exchange could be applied by point addition and scalar point multiplication.

ecdh

Suppose that Alice picks up her private key ka. Alice would compute her public key with multiplying her private key and public base point G. Then, Bob multiplyies Alice’s public key (Bob knows Alice’s public key because its public) and his private key kb. Likewise, Bob would compute his public key with multiplying his private key and public base point G. After then, Alice will multiply Bob’s public key and her private key ka. Finally, Alice and Bob both retrieves same shared secret key. This algorithm is also called as Elliptic Curve Diffie Hellman.

Let’s monitor the algorithm with real world values. Firstly, we’re going to use the following entity class to store 2D point coordinates.

import java.math.BigDecimal;

public class Point {

 BigDecimal pointX;
 BigDecimal pointY;

 public BigDecimal getPointX() {
 return pointX;
 }
 public void setPointX(BigDecimal pointX) {
 this.pointX = pointX;
 }
 public BigDecimal getPointY() {
 return pointY;
 }
 public void setPointY(BigDecimal pointY) {
 this.pointY = pointY;
 }

}

Then, the following methods are going to be used to rapid point addition (Remember double and add method is used to converge a point rapidly on elliptic curves).

 public static Point multiplyScalarPoint(Point G, BigInteger k, double a){
//this method will compute the Point kG

Point tempPoint = new Point(); //initial value of tempPoint equals to G
tempPoint.setPointX(G.getPointX());
tempPoint.setPointY(G.getPointY());
String kAsBinary = k.toString(2); //to binary string

for(int i=1;i<kAsBinary.length();i++){

int currentBit = Integer.parseInt(kAsBinary.substring(i, i+1));

tempPoint = pointAddition(tempPoint, tempPoint, a); //doubling

if(currentBit == 1)
tempPoint = pointAddition(tempPoint, G, a); //tempPoint + P

}

return tempPoint;

}

public static Point pointAddition(Point P, Point Q, double a){

BigDecimal x1 = P.getPointX(), y1 = P.getPointY(), x2 = Q.getPointX(), y2 = Q.getPointY();

MathContext mc = new MathContext(128); //calculation precision on bits

BigDecimal beta;

if(x1.compareTo(x2) == 0 && y1.compareTo(y2) == 0){ //check P and Q point
beta = ((BigDecimal.valueOf(3).multiply(x1.multiply(x1)))
.add(BigDecimal.valueOf(a))).divide((BigDecimal.valueOf(2).multiply(y1)), mc);
}
else{
beta = (y2.subtract(y1)).divide((x2.subtract(x1)), mc);
}

BigDecimal x3 = (((beta.multiply(beta)).subtract(x1)).subtract(x2));
BigDecimal y3 = (beta.multiply(x1.subtract(x3))).subtract(y1);

Point R = new Point();
R.setPointX(x3);
R.setPointY(y3);

return R;

}

Finally, we can monitor the key exchange between two parties in the following code.

 public static void main(String[] args) {

double a = -4, b = 4; //curve y^2 = x^3 - 4*x + 4

//public base point G
Point G = new Point();
G.setPointX(new BigDecimal(-2));
G.setPointY(new BigDecimal(-2));

System.out.println("Public base point G("+G.getPointX()+", "+G.getPointY()
+") on the curve y^2 = x^3 + ("+a+"*x) + ("+b+")\n");

//--------------

BigInteger ka = new BigInteger("1000077001100"); //private key of Alice
BigInteger kb = new BigInteger("1000077001907"); //private key of Bob

int scale = 25;

Date beginDate = new Date();

//Alice computes her public key by multiplying her private key ka and base point P
Point alicePublic = multiplyScalarPoint(G, ka, a);
System.out.println("Alice sends her public key to Bob: kaG("
+alicePublic.getPointX().setScale(scale,BigDecimal.ROUND_HALF_UP)
+", "+alicePublic.getPointY().setScale(scale,BigDecimal.ROUND_HALF_UP)+")");

//Bob computes his public key by multiplying his private key kb and base point P
Point bobPublic = multiplyScalarPoint(G, kb, a);
System.out.println("Bob sends his public key to Alice: kbG("
+bobPublic.getPointX().setScale(scale,BigDecimal.ROUND_HALF_UP)
+", "+bobPublic.getPointY().setScale(scale,BigDecimal.ROUND_HALF_UP)+") \n");

//Alice computes the shared key by multiplying Bob's public key and her private key ka
Point aliceShared = multiplyScalarPoint(bobPublic, ka, a);
System.out.println("Alice aggrees on the shared secret key with Bob: ("
+aliceShared.getPointX().setScale(scale,BigDecimal.ROUND_HALF_UP)
+", "+aliceShared.getPointY().setScale(scale,BigDecimal.ROUND_HALF_UP)+")");

//Bob computes the shared key by multiplying Alice's public key and his private key kb
Point bobShared = multiplyScalarPoint(alicePublic, kb, a);
System.out.println("Bob aggrees on the shared secret key with Alice: ("
+bobShared.getPointX().setScale(scale,BigDecimal.ROUND_HALF_UP)
+", "+bobShared.getPointY().setScale(scale,BigDecimal.ROUND_HALF_UP)+")\n");

Date endDate = new Date();

System.out.println("key exchanged lasts "
+(double)(endDate.getTime() - beginDate.getTime())/1000+" seconds\n");

}
key_exchange_trace
Trace of Key Exchange Example

As illustrated above, key exchange is completed in milliseconds even though worked with very large numbers. Also, the code is run with a personal laptop (HP EliteBook 8570p, Intel(R) Core(TM) i7-3540M CPU @ 3.00GHZ, 8.00 GB RAM, 64-bit OS)

How Secure?

Of course, computing Alice’s private key from her public key is possible. However, computation time would last too long with brute force attack in worst case scenario. The following code applies sample brute force attack. It starts from base point G and applies point addition repeatly until it reaches to the public key. Basically, private key equals to the iteration count. Let’s look at the computational cost of attacking over private key value.

 public static BigInteger attack(Point publicKey, Point basePoint, double a){

Point tempPoint = new Point(); //initial value of tempPoint equals to P
tempPoint.setPointX(basePoint.getPointX());
tempPoint.setPointY(basePoint.getPointY());

int scale = 25;

boolean isAttackSuccessful = false;
BigInteger iteration = new BigInteger("1");
Date beginDate = new Date();

while(isAttackSuccessful == false){

tempPoint = pointAddition(tempPoint, basePoint, a);
iteration = iteration.add(new BigInteger("1")); //iteration++

if(tempPoint.getPointX().setScale(scale,BigDecimal.ROUND_HALF_UP)
.compareTo(publicKey.getPointX().setScale(scale,BigDecimal.ROUND_HALF_UP)) == 0
&& tempPoint.getPointY().setScale(scale,BigDecimal.ROUND_HALF_UP)
.compareTo(publicKey.getPointY().setScale(scale,BigDecimal.ROUND_HALF_UP)) == 0 ){

Date endDate = new Date();

System.out.println("Private key found in "
+ (double)(endDate.getTime() - beginDate.getTime())/1000+" seconds");

isAttackSuccessful = true;

}

}//while end

return iteration;

}
ecc_attack_cost
Computational Cost of Key Exchange and Successful Attack. x-axis: Private Key Value, y-axis: Computation Time (in seconds)

As demonstrated above, computation time of key exchange operation remains stable while private key value increased. In contrast, computation time of successful attack (in worst case) increases linearly while private key value increased. Maximum scale of the illustration equals to the 20 bit integer (1M), and successful attack approximately lasts 2 minutes. Minimum length of 256 bit private keys are strongly suggested by NIST for elliptic curve cryptosystems to offer same level security of AES-128. Moreover, trendline equation of the successful attack line is y = (6.0808x/50000) + 0.8818. This means 128 bit key requires more than 13×1026 years to solve with a single computer in the worst case scenario. If 1T (1012) computers run in parallel, then private key could be solved in  13×1014 years. As known, the age of the universe is 13×109.

To sum up, elliptic curves offer faster computations for key exchange operations. Moreover, known attacking algorithms run very slowly for elliptic curve cryptography. Thus, elliptic curves provide to transfer information securely on insecure channels.

Bonus: I’ve also shared the example of public key generation on finite fields on GitHub. In this case, public and shared keys are generated as integer.

Illustration: Scarlett Johansson with handcuffed briefcase in Lucy (2014)

One thought on “Key Exchange: From Carrying Handcuffed Briefcases To Modern Cryptosystems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s