Sunday, 12 October 2014

Private Key for Digital Signature, KeyStore, PKCS#12

The following demonstrates the use of the Java security API to digitally sign a document.
Before we get to the Scala code, we must first use Java's keytool to create a self-signed certificate.
In real-life, you'd probably buy one from Verisign for example. The archive file format chosen is PKCS12.
keytool -genkey
        -alias tj
        -keystore mykeystore
        -storepass storepass
        -validity 365
        -keyalg RSA
        -keysize 2048
        -storetype pkcs12
Once you have answered the questions, you can list the aliases using the following command:
keytool -keystore mykeystore 
        -storepass storepass 
        -storetype pkcs12
Should output:
Keystore type: PKCS12
Keystore provider: SunJSSE

Your keystore contains 1 entry

tj, Oct 12, 2014, PrivateKeyEntry,
Certificate fingerprint (SHA1): 52:6B:0D:05:9E:CE:5A:CA:5E:EF:74:C9:51:FE:46:8D:E6:CE:4F:11
Let's get to the coding part. We will extract the private key from the store to digitally sign a document. I usually first create a digest from the initial document and store this digest as base 64. But there is no need for this step.
  def createDigest(legalDocument: String): Array[Byte] = {
    val md = MessageDigest.getInstance("SHA-256")
to be called like this:
val alias = "tj"
val password = "storepass".toCharArray
val legalDoc = createDigest("This is a legal document I must digitally sign")
legalDoc is an array of bytes - it contains a SHA-256 digest from the initial document.

The code to list the keystore entries, just to make sure we are on the right path:
  def listStoreEntries(password: Array[Char]): KeyStore = {
    val keyStoreDefaultType = KeyStore.getDefaultType
    val keyStore = KeyStore.getInstance("pkcs12")
    keyStore.load(new FileInputStream("mykeystore"), password)

    val aliases = keyStore.aliases()
    while(aliases.hasMoreElements) {
      val alias = aliases.nextElement()
      log(s" Alias: $alias")

listStoreEntries returns the initialized keystore. Let's now sign the legal document and return a base 64 encoded digital signature:
  def signLegalDocument(keystore: KeyStore, alias: String, password: Array[Char], legalDoc: Array[Byte]): String = {
    val privateKey = keystore.getKey(alias, password)
    val dsig = Signature.getInstance("MD5withRSA")
    val signature = dsig.sign()
And the code to verify the signature:
  def verifyDigitalSignature(keystore: KeyStore, alias: String, legalDoc: Array[Byte], signature: String): Unit = {
    val certificate = keystore.getCertificate(alias)
    val x509Certificate = certificate.asInstanceOf[X509Certificate]
    val publicKey = x509Certificate.getPublicKey
    val dsig = Signature.getInstance("MD5withRSA")

    val sig = Base64.getDecoder.decode(signature)
    val verifiedSig = dsig.verify(sig)
    log(s"Has the legal document signature successfully been verified? $verifiedSig")
    require(verifiedSig == true)
The whole main method:
  def main(args: Array[String]) {
    val alias = "tj"
    val password = "storepass".toCharArray
    val legalDoc = createDigest("This is a legal document I must digitally sign")
    val keyStore = listStoreEntries(password)

    val signature = signLegalDocument(keyStore, alias, password, legalDoc)
    verifyDigitalSignature(keyStore, alias, legalDoc, signature)

  def log(ref: Any) = println(ref)
How do I import my self-signed certificate into Windows cert manager?
Just rename the keystore from mykeystore to mykeystore.pfx On Windows, simple double-click on it and follow the instructions.
Open certmgr.msc via the run command or from a DOS console - under Certificates - Currrent User, Personal, Certificates you should see your previously create certificate using Java's keytool.

Friday, 5 September 2014


Just found this neat Scala project, Scalatra.
Quite amazing I did not know it... but looks pretty cool: I love the integration with Slick and Akka...

Friday, 29 August 2014

Another neat interview question: a kind of crossword puzzle

My friend had another interview question. You have already seen the first one.
This one is about crosswords. It involves graphs obviously.
Let me start by giving a brief overview of the problem he had to solve, and my Scala take on it ;-)
Question Imagine a crossword grid of size n x n containing letters. Given a dictionary of words, find all possible paths in the grid that match the words in the dictionary.
For Example:
is a 3x3 grid of letters, if the dictionary contains the word MAN, there are two paths possible: [(0,0), (0,1), (0,2)] and [(1,2), (0,1), (0,2)].

My Scala take on it
Let's define a Coord class that represents the grid coordinates - and a bunch of methods to work out the neighbours of a given coordinate:
  val gridSize = 3                                //> gridSize  : Int = 3
  case class Coord(val x: Int, y: Int) {
    def /\ = Coord(x, y - 1)
    def \/ = Coord (x, y + 1)
    def |> = Coord(x + 1, y)
    def <| = Coord(x - 1, y)
    def -/ = Coord(x + 1, y - 1)
    def -\ = Coord(x + 1, y + 1)
    def \- = Coord(x - 1, y - 1)
    def /- = Coord(x - 1, y + 1)
    def isValid = x >= 0 && x < gridSize && y >= 0 && y < gridSize
  type Path = List[Coord]
  type Paths = List[Path]
The next method works out all valid neighbours for a given coordinate:
  def /\/\ (c: Coord) = List(c /\, c \/, c |>, c <|, c -/, c -\, c \-, c /-).filter(_.isValid)
For example:
  require((/\/\(Coord(1, 1))).size == 8)
  require((/\/\(Coord(0, 0))).size == 3)
Let's define a dictionary for our tests:
  val dict = Set("MAN", "ARM", "CAR")             //> dict  : scala.collection.immutable.Set[String] = Set(MAN, ARM, CAR)
  val dictMaxLength = => w.size).max   //> dictMaxLength  : Int = 3
The main algorithm is the following that enumerates all the paths between two nodes in the graph. Note that I restrict the path length based on the maximum of letters defined in the dictionary. This can be improved further using the dictionary (prefix.. etc. left as an exercise).
  def allPaths(from: Coord, to: Coord): Paths = {
    def allPathsRec(currentCoord: Coord, currentPath: Path): Paths = {
      if (currentPath.size > dictMaxLength) Nil
      else if (currentCoord == to) List(currentPath)
      else /\/\(currentCoord).filter(c => !(currentPath contains c)).flatMap(c => allPathsRec(c, c :: currentPath))
    allPathsRec(from, List(from)).map(_.reverse)
As an example, the following will give you the diagonal:
allPaths(Coord(0, 0), Coord(2, 2))  //WordGrid.Paths = List(List(Coord(0,0), Coord(1,1), Coord(2,2)))
Before we test it, we need one final procedure: a def to generate all pairs of cells (from one cell to another cell):
  def fromsTos: List[(Coord, Coord)] = {
    val keys = dictMap.keySet.toList
    for {
      c1 <- keys
      c2 <- keys.filter(_ != c1)
    } yield (c1, c2)
dictMap is the crossword definition:
val dictMap = Map(Coord(0, 0) -> 'M', Coord(1, 0) -> 'B', Coord(2, 0) -> 'C',
                  Coord(0, 1) -> 'A', Coord(1, 1) -> 'R', Coord(2, 1) -> 'A',
                  Coord(0, 2) -> 'N', Coord(1, 2) -> 'M', Coord(2, 2) -> 'O')  
Time to put this to the test:
// Generates all possible pairs path in the grid
// List(List(Coord(0,2), Coord(0,1), Coord(0,0)),  ...
val allPairsPaths = => allPaths(t._1, t._2)).flatten 
// Generates all words from the pairs path
// List(NAM, NRM, NRC, NAR, NMR, NR, NMO ....
val words = => => dictMap(c))).map(cs => cs.mkString)
// Combine the two lists, keep only what is in the dictionary
// List((MAN,List(Coord(0,0), Coord(0,1), Coord(0,2))), (CAR,List(Coord(2,0), Coord(2,1), Coord(1,1))) ....
val wordsPath = (words, allPairsPaths), _)).filter(t => dict contains t._1)
// Pretty print
wordsPath.foreach(wp => {println(s"Word ${wp._1} has path ${wp._2}")})
//> Word MAN has path List(Coord(0,0), Coord(0,1), Coord(0,2))
//| Word CAR has path List(Coord(2,0), Coord(2,1), Coord(1,1))
//| Word ARM has path List(Coord(0,1), Coord(1,1), Coord(0,0))
//| Word ARM has path List(Coord(0,1), Coord(1,1), Coord(1,2))
//| Word MAN has path List(Coord(1,2), Coord(0,1), Coord(0,2))
//| Word ARM has path List(Coord(2,1), Coord(1,1), Coord(0,0))
//| Word ARM has path List(Coord(2,1), Coord(1,1), Coord(1,2))
There are a few optimizations to do here and there. An interview question not easy to get right on a white board!

Some Scala Interview Questions

This is not for you. It is just a brain dump on Scala interview questions.. I like this site - questions like:

What is tail recursion? A hack to transform a recursive function into a for loop :-). Like the compute method there
What is function currying in Scala? It is a technique of transforming a function that takes multiple arguments into a function that takes a single argument. mult2 is mult1 after currying.
  def mult1(d1: Double, d2: Double) = d1 * d2     //> mult1: (d1: Double, d2: Double)Double
  def mult2(d1: Double) = (d2: Double) => d1 * d2 //> mult2: (d1: Double)Double => Double
  mult1(3, 4)                                     //> res0: Double = 12.0
  mult2(4)(3)                                     //> res1: Double = 12.0

Above can be applied to partially applied functions:
  def filter1[T](predicate: T => Boolean)(input: List[T]): List[T] = {
    input match {
      case head::tail => if (predicate(head)) head :: filter1(predicate)(tail) else filter1(predicate)(tail)
      case Nil => Nil
  }                                               //> filter1: [T](predicate: T => Boolean)(input: List[T])List[T]
  val even = (i : Int) => i % 2 == 0              //> even  : Int => Boolean = 
  val odd = (i: Int) => i % 2 != 0                //> odd  : Int => Boolean = 
  filter1(even)((0 until 10) toList)              //> res2: List[Int] = List(0, 2, 4, 6, 8)
  filter1(odd)((0 until 10) toList)               //> res3: List[Int] = List(1, 3, 5, 7, 9)
To avoid calling the filter method with the same predicate, another cool variant is this one, using lazy val and _:
  def filter2[T](predicate: T => Boolean)(input: List[T]): List[T] = {
    lazy val rec = filter2(predicate) _
    input match {
      case head::tail => if (predicate(head)) head :: rec(tail) else rec(tail)
      case Nil => Nil
And lots of other ways with partials and co. Quite neat.
What are implicit parameters? For me they are tricky... without an IDE, ... anyway. Best definition is obviously there
  implicit def myImplicit(i: Int): Boolean = i < 3//> myImplicit: (i: Int)Boolean
  def filter3[T](input: List[T])(implicit predicate: T => Boolean): List[T] = {
    input match {
      case head::tail => if (predicate(head)) head :: filter3(tail) else filter3(tail)
      case Nil => Nil
  }                                               //> filter3: [T](input: List[T])(implicit predicate: T => Boolean)List[T]
  filter3[Int]((0 until 10) toList)               //> res5: List[Int] = List(0, 1, 2)

How to create enum? For me, Scala enums are weird...
  object PrimaryColours extends scala.Enumeration {
    type PrimaryColours = Value
    val Red, Green, Blue = Value
    def asInts(c: PrimaryColours): (Int, Int, Int) = {
      c match {
        case Red => (255, 0, 0)
        case Green => (0, 255, 0)
        case Blue => (0, 0, 255)
  import PrimaryColours._PrimaryColours.asInts(Red)   //> res6: (Int, Int, Int) = (255,0,0)PrimaryColours.asInts(Red)

Referential transparency? Given a function and a set of inputs, the results will always be the same... no side effect, can be parallelised, cached, etc....

Saturday, 16 August 2014

Snail Algo in Scala

A friend of mine just had an interview for a job at Amazon... and he had a funny algorithm to work on. Something that I would describe as a 'snail algorithm' for a matrix. A bit like this:
So, I was wondering how to implement this .. and I wrote this in Scala.. seems to work - although not entirely tested ;-) Some type def
  val numRows = 4
  val numCols = 3        
  val matrixSize = numRows * numCols 
  type Coord = (Int, Int)
  type Operand = (Int, Int)
  type Path = List[Coord]

  val incs = List((0, 1), (1, 0), (0, -1), (-1, 0))
incs defines directions: go right, go down, go left, go up, etc. In order to continuously iterate through those values, I used Stream.continually():
  val incsIt = (for(x <- Stream.continually(); y <- incs) yield y).iterator
  def nxtOp = 
Then a small recursive function to snail-walk the matrix:
  def walk(coord: Coord = (0, 0), op: Operand = nxtOp, path: Path = List()): Path = {
    if (path.size == matrixSize) path else {
      val nrc = (coord._1+op._1, coord._2+op._2)
      if (nrc._1 < 0 || nrc._1 >= numRows || nrc._2 < 0 || nrc._2 >= numCols || (path contains nrc))
        walk(coord, nxtOp, path)
        walk(nrc, op, if (path.size == matrixSize-2) path :+ coord :+ nrc else path :+ coord)
The result for (4, 3) shows:
  val p1 = walk()                                 

//> p1  : org.jts.z.Snail.Path = 
// List((0,0), (0,1), (0,2), (1,2), (2,2), (3,2), (3,1), (3,0), (2,0), (1,0), (1,1), (2,1))
I really have the feeling it can be done in a better way. Have not found how yet.

Thursday, 7 August 2014

SOM (2D Grid)

This time, just a Google + Video. Next time.. the 3D version :-)

Sunday, 27 July 2014

Self-Organizing Map in Scala

My Scala code of the day relates to Self-Organising Maps. The end result can be seen on this short video. Let's start with some basic definition
case class Coord(x: Int, y: Int)
case class Weight(r: Double, g: Double, b: Double) // Represents the color vector
case class Node(coord: Coord, weight: Weight) // The node in the lattice
Some utility class, wrapped in a Scala object. As you can see, Euclidean distance is used for weight proximity (r, g, b) and nodes (x, y)
object SOMUtils {
  private val rnd = new
  def rndWeight = Weight(rnd.nextDouble(), rnd.nextDouble(), rnd.nextDouble())
  def squa(d: Double) = d*d
  def euclDist(w1: Weight, w2: Weight) = sqrt(squa(w1.r-w2.r)+squa(w1.g-w2.g)+squa(w1.b-w2.b)) // Euclidian distance
  def euclDist(n1: Node, n2: Node) = sqrt(squa(n1.coord.x-n2.coord.x)+squa(n1.coord.y-n2.coord.y)) // Euclidian distance
  def rndElem[T](list: List[T]):T = list(rnd.nextInt(list.size))
Follows the definition of the lattice
import SOMUtils._

class Lattice(val size: Int, val nodes: List[Node])
object Lattice {
  def apply(size: Int) = new Lattice(size, (for(x<-0 until size; y<-0 until size) yield Node(Coord(x, y), rndWeight)).toList)
And finally the core of the algorithm
class SOM(val size: Int, val numIterations: Int, val trainingSet: List[Weight]) {
  val mapRadius = size / 2.0
  val timeConstant = numIterations / log(mapRadius)
  def neighbourhoodRadius(iter: Double) = mapRadius * exp(-iter/timeConstant)
  def bmu(input: Weight, lattice: Lattice): Node = {
    val sortedNodesByDist = lattice.nodes.sortBy(n => euclDist(input, n.weight))
  def bmuNeighbours(radius: Double, bmu: Node, lattice: Lattice): (List[(Node, Double)], List[(Node, Double)]) = => (n, euclDist(n, bmu))).partition(n => n._2 <= radius)
  def learningRate(iter: Double) = 0.072 * exp(-iter/numIterations) // decays over time
  def theta(d2bmu: Double, radius: Double) = exp(-squa(d2bmu)/(2.0*squa(radius))) // learning proportional to distance
  def adjust(input: Weight, weight: Weight, learningRate: Double, theta: Double): Weight = {
    def adjust(iW: Double, nW: Double) = nW + learningRate * theta * (iW - nW)
    Weight(adjust(input.r, weight.r), adjust(input.g, weight.g), adjust(input.b, weight.b))

  def nextLattice(iter: Int, lattice: Lattice): Lattice = {
    val randomInput = rndElem(trainingSet)
    val bmuNode = bmu(randomInput, lattice)
    val radius = neighbourhoodRadius(iter)
    val allNodes = bmuNeighbours(radius, bmuNode, lattice)
    val lrate = learningRate(iter)
    val adjustedNodes = => {
      val tTheta = theta(t._2, radius)
      val nWeight = adjust(randomInput, t._1.weight, lrate, tTheta)
      Node(t._1.coord, nWeight)
    new Lattice(lattice.size, adjustedNodes ++ => t._1))

  def compute {
    def helper(iter: Int, lattice: Lattice): Lattice =
      if (iter >= numIterations) lattice else helper(iter+1, nextLattice(iter, lattice))

    val endLattice = helper(0, Lattice(size))
    UIUtils.persist(endLattice, "lattice")
That's it. Hope you enjoyed that. Check it out and learn more. Next step: to implement the 2-D grid version - still using Scala and JavaFX, develop a generic SOM-Scala lib, and finally, re-implement the 2-D version using Three.js