Code kata of the week

· 3 min read

Here a collection of katas extracted from exercises and coding interviews.

Kata 01

Source: Qualified.io

Write a function that receives two strings and returns the number of characters we would need to rotate the first string forward to match the second.

For instance, take the strings “fatigue” and “tiguefa”. In this case, the first string can be rotated 5 characters forward to produce the second string, so 5 would be returned. Here are the step:

no rotations: “fatigue”

1st rotation: “efatigu”

2nd rotation: “uefatig”

3rd rotation: “guefati”

4th rotation: “iguefat”

5th rotation: “tiguefa”

If the second string isn’t a valid rotation of the first string, the method should return -1.

Specification

Challenge.shiftedDiff(first,second)

computes the number of rotations to make string first equal to string second, if possibile

Parameters

first: String - string to be rotated

second: String - target string to be matched by rotating first

Return Value

int - the number of rotations. If not possibile it returns -1.

Kata 02

Source: Qualified.io

You are provided a string containing a list of positive integers separated by a space ( " " ). Take each value and calculate the sum of its digits, which we call it’s “weight”. Then return the list in ascending order by weight, as a string joined by a space.

For example 99 will have “weight” 18, 100 will have “weight” 1 so in the output 100 will come before 99.

Specification

Challenge.orderWeight(input)
Parameters

input: String - a string containing a list of positive integers separated by a space ( " " ).

Return Value

String - a string with the values ordered by weight.

Constraints

All numbers in the list are positive integers and the list can be empty.

Examples

  • “56 65 74 100 99 68 86 180 90” ordered by numbers weights becomes:

    “100 180 90 56 65 74 68 86 99”

    When two numbers have the same “weight”, let’s consider them to be strings and not numbers: 100 is before 180 because its “weight” (1) is les than the one of 180 (9) an 180 is before 90 since, having the same “weight” (9) it comes before as a string.

Kata 03: Find routes

Source: Qualified.io

We are tracking down our rogue agent and she travels from place to place to avoid being tracked. Each of her travels are based on a list of itineraries in an unusual or incorrect order. The task is to determine the complete route she will take.

You are given an array of routes containing her travel itineraries. Convert this into a complete, in-order list of the places she will travel.

Specification

Challenge.findRoutes(routes)
Parameters

routes: List<String[]> - array of itineraries

Return Value

String - An ordered list or destinations

Constraints

All inputs have at least one valid, complete route

Examples

  • routes: [[“USA”,“BRA”],[“JPN”,“PHL”],[“BRA”,“UAE”],[“UAE”,“JPN”]]

    return: “USA, BRA, UAE, JPN, PHL”

Introduction to encryption by Michael Pound

· 7 min read

This is the first review I do about courses or lectures, they are mostly notes and personal considerations I hope you like it. I start with a live course from O’Reilly learing platform that I really appreciate, there are a lot of courses taken by famous people, try it if you can.

  • Course: Introduction to encryption. A hands-on course on applying symmetric and asymmetric encryption.
  • Relator: Michael Pound
  • Publisher: O’Reilly live online training
  • Duration: 3 hours

Michael is a regular contributor to the popular YouTube channel Computerphile, where his videos on topics such as image analysis, machine learning, and computer security have accumulated over 30 million views from people all over the world.

Course contents

  • The power of XOR, the One Time Pad
  • Symmetric criptography
    • Stream ciphers
    • Block ciphers
  • Asymmetric criptography
    • Key exchange with Diffie-Hellman
    • RSA, DSA
  • Hash functions
  • Digital signature
  • Digital certificates: issuance, CA, chain of trust
  • Protocols
    • authenticated encryption AEAD
    • handshake
    • SSL/TLS (HTTPS)

Extracts and notes

Here are some extracts and insights on the main topics.

Introduction to encryption

In his introduction to encryption he talks about the power of the operator XOR.

XOR is a binary operator between two values that returns true if either one input or the other is true, but not both

Applying XOR twice reverse its effects: A ⊕ B ⊕ A = B

One Time Pad encryption use it as a bit mask with a one time password of the same length.

Symmetric cryptography

In symmetric cryptography the same key is used to encrypt and decrypt.

There are two typologies: stream cyphers and block cypers.

Stream cyphers

In stream cyphers you can encrypt long continuos streams. In a stream cipher, keys and algorithm are applied to each binary digit in a data stream, one bit at a time, rather than encrypting block of data.

The implementation is simple: each bit of the input is XORed with a one time bit key genereated from a pseudo random generator. A short password is used as a seed. “Pseudo random” means that it seems random but with the same seed it generates the same series of values. If the key stream output is random, then it will take a longer time for a crypt analyst to break it.

It is useful for movies because you can seek to any localtion of the stream and for devices where hardware AES acceleration is not available. An example of stream cypher is ChaCha20.

Block cyphers

A block cypher takes a block of plain text bits and generates a block of cipher text bits, generally of same size. The size of block is fixed in the given scheme. The choice of block size does not directly affect to the strength of encryption scheme. The strength of cipher depends up on the key length.

Other primitives related treated are IVs, padding and block modes (ECB, CBC, CTR).

Here a simple explanation of how AES (Advanced Encryption Standard) works from his channel:

Asymmetric cryptography

In asymmetric cryptography there are two keys envolved: a private and a public. You use the public key of the recipient to encrypt the message; only him can decrypt it with his private key.

RSA

RSA algorithm si used for generate public-private key pair. The keys (e, n) and (d) are reversible: either can be used for encryption, and the other used for decryption.

This leads us to two very useful use cases for RSA:

  1. Encryption only the owner can read
  2. Signing that must have been performed by the owner

PEM/DER formats

When we generate the keys the generate files will contains data like this:

—–BEGIN PRIVATE KEY—–
MIIEczCCA1ugA..AkGA1UEBhMCR0Ix
EzARBgNVBAgTC..0EgTHRkMTcwNQYD
……
It8una2gY4l2O..adsGeFKkyNrwGi/
7vQMfXdGsRrXN..HoX
-—-END CERTIFICATE—–

This format called PEM format is a text representation of the real binary key in DER format. We could store the binary version of the file only with DER encoding, but the most common way is the PEM version.

Diffie-Hellman

The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

Here two videos from his channel explaining Diffie-Hellman and the mathematics envolved

Hash functions

A hash function (in particular in cryptography) is any function that can be used to map data of arbitrary size to fixed-size values.

There are main characteristics of a good hash function:

  1. Deterministic: the same message always results in the same hash;
  2. Quick: it is quick to compute the hash value for any given message;
  3. One-way function: it is infeasible to generate a message from its hash value except by trying all possible messages;
  4. Avalanche effect: a small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value;
  5. Collision resistant: it is infeasible to find two different messages with the same hash value

Examples: MD5, SHA-1, SHA-2, SHA-3.

MD5 and SHA1 has been demoted from being a cryptographic hash function to a non-cryptographic hash function now.

Digital signature

When a signer electronically signs a document, the signature is created using the signer’s private key on the document hash. The resulting encrypted data is the digital signature. Who receives the document also receives a copy of the public key. If the public key can’t decrypt the signature is then considered invalid. The signature is also marked with the time that the document was signed. If the document changes after signing, the digital signature is invalidated.

Digital signatures use a standard format called PKI.

Public Key Infrastructure

The PKI is the infrastructure that the industry created to manage the digital identities. The PKI created a hierarchical body of many organizations which their role is to issue digital identies. These organizations called Certificate Authority (CA) make sure that you are a legitimate company, and you are who you want to claim you are.

When you visit a website via a secure connection, the site sends a digital certificate to your browser. Your Internet browser compares the issuer with a list of trusted Certificate Authorities. If a match can’t be found, the client browser checks to see whether a trusted Root CA signs the issuing CA certificate. The browser’s chaining engine continues verifying the issuer of each certificate until it finds a trusted root or upon reaching the end of the trust chain.

Digital Certificate

SSL required the web server to have public key, and a digital identity, to give to the browsers. The industry decided to combine these two in one file, which is called : digital certificate, or SSL certificate. PKI policies defined the format for this certificate in a standard called X.509 that contains:

  • Serial Number
  • Signature Algorithm ID
  • Issuer Name
  • Validity period
  • Subject name
  • Public Key Algorithm
  • Subject Public Key
  • Certificate Signature Algorithm
  • Certificate Signature
  • …

Transport Layer Security SSL/TLS

SSL is the standard protocol to secure the communication between a web server and a browser, by creating an encrypted link between the two.

When a browser hits the web server using the HTTPS protocol, it start the process. At the beginning, the encryption used is public-key encryption, which is an asymmetric type encryption. The web server has a couple of keys public and private. It sends the public key to the browsers, and the browsers use the public key to encrypt the communications later. Only the web server can know how to decrypt the communication. Because the public key decryption is slow and expensive, so the web server and the browser will switch to symmetric encryption where only one key is required. They negotiate between each other on what the best encryption algorithm they should use. The algorithm used would depend on the server and the browser. This negotiation phase is called TLS handshake.

  1. The Handshake Phase
    • Agree on a set of cryptographic protocols, e.g. AES 128, ECDH, RSA etc.
    • Perform a key exchange to obtain session keys and other values
    • Verify any authenticity using PKI
  2. Transport Phase
    • Packets encrypted using the agreed cipher
    • Includes a MAC or similar to verify integrity

Review

I really appreciate this course, Mike Pound is an excellent speaker and he deals with those complex topics in such a simple way. In this three hour course he walks you through the fundamental components of encryption and in the end he combine those multiple primitives into an entire end-to-end system.

Set up a static website with Hugo, Forestry and GitHub Pages

· 3 min read

I’m moving a private knowledge base powered by WordPress to a public blog so I seized the opportunity to study a static site generator like Jekyll.

The generator: Hugo

I chose Hugo one of the most popular generators, it’s really simple to use and to extend. Just download the CLI and run it in an empty folder and it will scaffold a basic site structure.

hugo new site quickstart

Then it’s time to download a theme, put it in the themes folder and set the config.toml file. I choose a theme named Soho.

To keep the theme updated I’m going to use a submodule as recommented by the quick start guide.

git submodule add https://github.com/alexandrevicenzi/soho.git themes/soho

Each theme has a lot of customizations that you can enable in the config.toml file.

The editor: Forestry

To manage contents in a web interface it comes in our aid Forestry.io: it reads data from a repository and let you edit pages easily, then it pushes back the changes keeping all synchronized.

The hosting: GitHub Pages

GitHub Pages offers a static site hosting service for free available at https://<username>.github.io. Content is read from the master root folder of a special public repository under https://<username>/<username>.github.io.

I’m going to use two different repositories:

  • one private where manage my contents and build the web site
  • one public to host the generated web site

Every time I make a change on the private repository, I must commit on it, build the web site and then publish all the content to the public repository. This can be done in two ways: using git submodules or using GitHub Actions to automate the deploy; let’s try the second choice.

I’m gonna use an available action here to set up a CD workflow:

name: publish
# on every commit in the master branch
on:  
  push:
    branches: [ master ]
jobs:
  # it starts a job named build
  build:
    runs-on: ubuntu-latest
    steps:
      # it checkout the master branch and init/update the submodules (the themes)
      - uses: actions/checkout@v2
        with:
          submodules: true
          fetch-depth: 0
      # it prepares the hugo command line on ubuntu
      - name: Setup Hugo
        uses: peaceiris/actions-hugo@v2
        with:
          hugo-version: '0.76.5'
      # it builds the contents
      - name: Build
        run: hugo --minify
      # it deploys the build on another repository
      - name: Deploy
        uses: peaceiris/actions-gh-pages@v3
        #docs: https://github.com/peaceiris/actions-gh-pages
        with:
          personal_token: ${{ secrets.PERSONAL_TOKEN }}
          publish_dir: ./public
          external_repository: <username>/<username>.github.io
          user_name: <username>
          publish_branch: master

This task runs at every push:

  1. prepare an ubuntu OS
  2. checkout the code
  3. setup the right version of Hugo CLI
  4. build the web site in a destination folder
  5. publish the result in the public repository with the static hosting service enabled

Here’s an example of the workflow running:

Both repositories are under the same user so you can use a personal token to share permissions across them (another way is to use a deploy key).

You must generate it and put the generated hash in the private repository secrets store so you can use it during the build like in the script example above.

Now you can manage locally a simple markdown file and push it or you can do that online in a rich editor like Forestry and in a few seconds is available online.