Sunday, 11 January 2015

Ouray! Just completed my Machine Learning Course!

Completed my ML course from Coursera! Lots of work!

RedMart is hiring

If you are interested, please check this link. Another neat implementation in Scala is fairly easy...

Monday, 15 December 2014

So much fun recently

Had lots of fun recently: played with Scalatra, RESTful APIs, Slick, all the web services security aspects like HMAC, etc... Really fun. I am quite amazed that I never had to work on web services until now... but hey, there is always a first time.
Special Kudos to Scalatra -- just love this framework, although the integration with Swagger can be a real pain.

Tuesday, 9 December 2014

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 
        -list 
        -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")
    md.update(legalDocument.getBytes)
    md.digest()
  }
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")
    }

    keyStore
  }
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")
    dsig.initSign(privateKey.asInstanceOf[PrivateKey])
    dsig.update(legalDoc)
    val signature = dsig.sign()
    Base64.getEncoder.encodeToString(signature)
  }
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")
    dsig.initVerify(publicKey)

    val sig = Base64.getDecoder.decode(signature)
    dsig.update(legalDoc)
    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

Scalatra

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:
MBC
ARA
NMO
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 = dict.map(w => 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')  
Test
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 = fromsTos.map(t => allPaths(t._1, t._2)).flatten 
// Generates all words from the pairs path
// List(NAM, NRM, NRC, NAR, NMR, NR, NMO ....
val words = allPairsPaths.map(p => p.map(c => 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).zipped.map((_, _)).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!

Blog Archive