Friday 16 January 2009

Scala, example of Diffie-Hellman

Another in the sequence of postings on Scala by simple example, this one shows an example of Diffie-Hellman to establish a shared secret over a public communication channel without that secret being revealed. Diffie-Hellman itself is prone to man-in-the-middle attacks, this example does not attempt to deal with that problem (normally addressed with authentication of some type).

The example sets up the canonical Alice and Bob, with shared public parameters g (generator) = 5 and p (prime modulus) = a large 128 random prime number.

Alice and Bob each create their secret key [sk] (a large 128 random number) and generate:

y = g^sk mod p

Alice and Bob then swap the result of this calculation.

From this, Alice and Bob both perform y^sk mod p to create a new value, the shared secret key which will be the same for both Bob and Alice even though they start with different random secret keys.

This is because:

(g^x)^y is the same as (g^y)^x

From a Scala perspective, the interesting things to note are:

  • Ease of use of large integers using the BigInt class as if it were a primitive type.
  • Constructors to create immutable instances containing g, p and name.
  • Companion object to provide helper function to wrap probable prime function.


Example code:



package test

import scala.util.Random;


object DiffieHellmanTest {

val p = DiffieHellman.randomPrime(128)
val g = 5

def main(args : Array[String]) {

// alice and bob initialise with the public parameters for DH, g and p
val alice = new DiffieHellman(g, p, "Alice")
val bob = new DiffieHellman(g, p, "Bob")

// alice and bob generate their own secret keys and public keys
alice.createSecretKey();
bob.createSecretKey();

val a1 = alice.getPublicKey();
val b1 = bob.getPublicKey();

println("a1 = " + a1)
println("b1 = " + b1)

// alice and bob exchange public keys
bob.setPeerPublicKey(a1)
alice.setPeerPublicKey(b1)

// alice and bob compute their shared secret key
val alicesk = alice.createSharedKey()
val bobsk = bob.createSharedKey()

println("Done, alice sk = " + alicesk + ", bob sk = " + bobsk)
}
}

object DiffieHellman {

def randomPrime(n : Int) : BigInt = { // return a random value with n digits

val rnd = new Random();

BigInt.probablePrime(n, rnd)
}
}

class DiffieHellman(val g : Int, p : BigInt, name : String) {

var secretKey : BigInt = 0
var peerPublicKey : BigInt = 0


def createSecretKey() {

secretKey = random(128)

println(name + " secretKey = " + secretKey)
}

def setPeerPublicKey(x : BigInt) {

peerPublicKey = x
}

def getPublicKey() : BigInt = {

doExpMod(g, secretKey, p)
}

def random(n : Int) : BigInt = { // return a random value with n digits

val rnd = new Random();

BigInt(n, rnd)
}

def createSharedKey() : BigInt = {

doExpMod(peerPublicKey, secretKey, p)
}

private def doExpMod(x : BigInt) : BigInt = {

println("doExpMod g = " + g + ", x = " + x + ", p = " + p)
doExpMod(g, x, p)
}

private def doExpMod(g : BigInt, x : BigInt, m : BigInt) : BigInt = {

g.modPow(x, m)
}
}



Results:

(Numbers may vary between runs of course!)


Alice secretKey = 197977683133285508684427285955258922592
Bob secretKey = 54690551885126631242925351374829949140
a1 = 4317900055693480003952964194026338337
b1 = 58782279533775365647086521912939284670
Done, alice sk = 275531174494727646906973085281579443284, bob sk = 275531174494727646906973085281579443284



The secret keys for Alice and Bob normally wouldn't be revealed, but they've been output here for debug purposes.

Note that the final shared secret key is the same for both Alice and Bob, which could then be used to establish a secure communication channel using symmetric encryption.


.

No comments: