This may serve as a cheat-sheet for someone who wants to get an understanding of the computational complexity terms, hopefully in the shortest possible time.

P – Problems that can be solved in polynomial time, obvious to this is, solutions to such problems can be verified in polynomial time as well. Example –  Sorting problem.

NP (Non-Deterministic Polynomial) – Problems that can be verified in polynomial time but not necessarily can be solved in polynomial time. Example –  Subset Sum Problem.

NP Complete – Problems that are as hard as any problem in NP. These are problems on the edge of NP space.

NP Hard – Problems that are higher in complexity than that of NP Complete problems. Example – Travelling Salesman Problem (TSP).

EXP – Problems that can be solved in exponential time. While TSP is a N! problem, it can be solved in exponential time using Dynamic Programming with  2^n*n^2.

P!=NP means, problems that can be verified in polynomial time can’t necessarily be solved in polynomial time.

Bitcoin and Blockchain  – these terms seem to be going around a lot lately. Got curious to get to the bottom of it, as much as I could, anyway. Here’s a summary of what I understood.

Bitcoin is digital currency that is decentralized (reminded me of Internet, DNS, etc.). It is anonymous – like paying through cash. Anybody can use it – directly or through service providers. It appears there are about 8% of folks who do not have a bank account, time for them to transact using bitcoins.

Every transaction is represented digitally by referring to all previous transactions that led the spender to receive money – proof that the spender owns a certain amount of money. In addition, carries the receiver identity (public key) in the bitcoin system, plus the transaction amount. Plus, a digital signature of the afore mentioned data using the spender’s private key. This is transmitted to the receiver (payee) and on to the bitcoin network of computers. The signature is verified using the spender’s public key and proves the payment is from the spender.

Miners on the bitcoin network gather the unverified transactions, put them together into a block and append to existing chain of verified blocks to make the transactions legit. To do this, miners need to solve a “proof of work” mathematical puzzle that requires considerable computing power to solve. Whoever solves it faster will get to add the block to the block chain and be rewarded. Blockchain is the equivalent of a ledger.

There is this case of double spending fraud – paying a number of people with same money. This is harder to do as the double spender will have to create new blocks before others to remove the first transaction from becoming legit – this is hard to do for one person as many blocks would have formed in the mean time (decentralized helps here as many are solving the proof of work puzzle that is different for every miner), that needs to be computed, solved and substituted by the double spender.

The incentive for the miners includes transaction fees and rewards for aggregating transactions into blocks and adding them to the blockchain.

Spring Boot comes with interesting features, one of which is to provide production ready, stand-alone application (embeds web server) with built-in monitoring and debugging facilities out-of-the-box.  This enables immutable container deployment units that can help with continuous deployment at scale.

Impressed by the above, I converted a spring mvc based webservice to a spring boot application. Things I did included adding the following dependencies to pom.xml, removing the existing spring-context and spring-webmvc dependencies, changing the packaging to jar from war and providing a starter class that wires up spring boot and spring. Viola – got endpoints that allow me to look at config, url to controller mapping/documentation, take thread dumps, health check, access logs and more, click here for endpoints documentation.

<parent>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-parent</artifactId>
<version>1.3.3.RELEASE</version>
</parent>
<dependencies>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-actuator</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-test</artifactId>
<scope>test</scope>
</dependency>

...

<plugin>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-maven-plugin</artifactId>
</plugin>

Starter class looks like this:

@SpringBootApplication
public class Application {
    public static void main(String[] args) {
        SpringApplication.run(Application.class, args);
    }
}

In case, if you want to leverage the monitoring and debugging features for an existing war application, the following maven pom additions are required in addition to retaining packaging to war.

<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-tomcat</artifactId>
<scope>provided</scope>
</dependency>

We all know there is some security on the web – https, ssl, encryption, mac, etc. But, do we know what is behind all these security? In this article, I attempt to explain in simple terms, the underpinning behind web security.

Let us take the case of RSA, a  public key infrastructure mechanism that kicks in when a website is accessed over https – remember the padlock we see in the browser address bar when we access a bank website?

The way RSA works is that it has two keys. A public key, published to anyone including browsers via the certificate downloaded while accessing a https web page. A private key, only available to the website you access over https. When data is sent by the browser, it is scrambled (encrypted) using the public key and the scrambled data is sent to the server. The server decrypts and gets the original data using the private key it has, this prevents eavesdropping of the transmitted message.

The keys under discussion are  nothing but integers. The public key is a product of 2 prime numbers p and q. The private key is p and q. While this is much simplified for understanding purposes, it is not hyperbolic though. Security is riding on the fact that it is hard to find p and q given the product pq, especially, for large values of p and q, of the order of hundreds of digits. Once somebody finds p and q, they can decrypt the messages that they can sniff off the internet.

Let us understand why it is hard. In order to factor a number (such as finding p and q given pq), one needs to divide the product by numbers from 1 to the square root of that number (why, needs another article). And this takes an immense amount of time for computers, of the order of several billion years beyond the age of the universe, when p & q are large prime numbers and one can do millions of divisions in a second. You can try this on your computer for considerably large numbers. These methods, that make reversing harder are called trapdoor functions. They are easy one way (multiplying p & q), harder the other way (finding p & q given pq).

This is the underpinning behind web security – some simple, but genius, factorization math. When computing capacity increases in the future to the level where we can factor huge numbers quickly – bets are off on the current security model.  This is also the reason why the number of bits of the keys used for encrypting has increased over the years, most recently from 1024 to 2048, to keep up with increasing computing capacity.

While cracking is hard with public key infrastructure that uses 2 different keys for encryption and decryption (asymmetric cryptography),  same is true for symmetric encryptions, where same key is used for encryption and decryption, such as AES where the probability of guessing a key is hard as the possible universe from which the key is drawn is too large to try out all possible keys within a practical amount of time. Certain things like initialization vectors, cipher modes, substitutions, permutations, etc have been left out for understanding purposes.