A Note on Secret Sharing

Leave a comment

The words Secret and Sharing when used together produce a kind of ambiguity.! Traditionally! a secret is something which is not to be shared.!. Well to clarify,in this scenario it is about dividing a secret into many different secrets. This was surely a breakthrough in Cryptography when Adi Shamir and George Blakley independently invented it in 1979. Blakley’s scheme was something related to hyperplanes. I will brief about Shamir’s scheme.

Shamir’s paper on secret sharing titled “How to share a secret?” was a kind of revolution. Shamir proposed a scheme in which a secret can be divided into many secrets where each secret independently would not reveal any information about the original or the parent secret for reasons that are obvious. It is a mere two page paper which holds a lot information. In brief the scheme is something as follows: A secret, is divided into ‘n’ different parts. Let this secret be ‘scrt’. If any ‘k’ of the ‘n'(1 < k <= n) parts come together( come together here refers to some mathematics), then the secret ‘scrt’ is revealed. Beauty of the scheme is that if any of the ‘k-1′ or less shares come together then even with theoretically infinite computing power, the original secret,’scrt’ cannot be recovered.

The scheme is based on the mathematical concept of interpolation. The secret ‘scrt'(assumed to be a number) is divided into ‘n’ parts. This is done by randomly picking a polynomial of degree ‘k-1’. Let this polynomial be called q(x).

q(x) = a0 + a1x + a2x^2+…..+a’k-1’x^k-1.

Now the original secret, scrt = q(0) = a0. scrt1 = q(1),scrt2 = q(2)…scrtn = q(n).

Now consider any subset of this ‘n’ broken secrets (scrt’i’), With these a ‘k’ values a polynomial can be formed by interpolation whose constant term ‘a0’ will give the value of the original secret. scrt = q(0). On the other hand, any k-1 or less number of broken secrets can form polynomials of degree strictly less than k-1 and hence value of scrt can never be recovered. Advantages of the scheme and a better explanation! can be found in the original paper.


How do I download a youtube video without any external agents?!?

Leave a comment

English: A download symbol.

Suppose that you have no external downloaders (plenty of them) installed and yet you are in need of downloading a video. What do you do?

Here is a simple method which you can use. I’ll assume you use Chrome..

1) Go to youtube.com browse for the required video and ALLOW IT TO STREAM FOR SOME TIME. 

2) Now right click and select Inspect Element or alternatively you can just do ctrl+shift+i.

3) Now go to the Networks tab. There are a lot of things (downloads etc., rather) happening but we are concerned with the “videoplayback” found in Name Path column.

4)Now right click on the “videoplayback” and select “copy link”.

5) Now open an editor and paste the link. Now look for the word “range” (Use FIND, for obvious reasons!)..

6) Now delete the words starting from “range” till you encounter an “&”.

7) Now copy this new link paste it in your browser.!!!


Leave a comment

This is a small video made to explain the basics of User mode and Kernel mode Rootkits

Water-Jug and the diophantine equations!!?

Leave a comment

Many of you might have heard about the famous problem of water and jugs. It goes as follows:

There are n jugs each having particular capacity (all unique) and unlimited supply of water. The problem is to find whether a particular value, say w, be measured from the given jugs.

To make it simple, say there are 2 jugs of capacity 5L and 3L each. The problem is  to find whether 4L can be measured?

Well many of you know the solution, and it can be found at many of the places!!!

* Fill the 3l, pour into 5l

* Fill the 3l, pour into 5l (1l remaining in 3l jug)

* Empty the 5l an pour into it the water from 3l, that is 1l

* Fill the empty 3l and pour into 5l jug and done.

What to do with diophantine equations?

I am not sure!!! but this one could be possible.

Let the capacities be a,b,c,d and the final quantity to be measured be p, consider the following equation.

ax + by + cz + dw = p…………………….(1)

The result which I am not sure of (:D) :

The problem (of water – jug ) has a solution if (1) has solution. (1) has a solution only when gcd (s,b,c,d) = kp, where k = 1,2,3,4,..

How do I verify both problems are the same ??


The story behind NONSECRET encryption!!!

Leave a comment

Whitfield Diffie and Martin Hellman, authors o...

Whitfield Diffie and Martin Hellman, authors of the first published paper on public-key cryptography (Photo credit: Wikipedia)

We are very much familiar with the Diffie – Hellman idea of secret exchange. It was surely a revolution in the field of information security and modern cryptography. This idea also in some sense led to the invention of many of the existing public-key systems including RSA and ElGamal systems.

But here is a story that tells such a remarkable idea was invented much before the invention of RSA or any other public – key system. It is about the cryptographers and mathematicians of the GCHQ who, the GCHQ claims to have invented systems similar to RSA much before the one’s published by Rivest, Shamir and Adleman. Here is the story.

How do I generate large primes???

Leave a comment

Many of the cryptography based techniques involves handling large numbers, specially large prime numbers. It is obvious from experience that our computers cannot handle such huge numbers(Here, huge refers to numbers involving 300 digits and even more!!!).

Set your computer for this task!!

There are many libraries and extensions out there to handle huge numbers. My choice from them is GNU Multiple Precision (GMP). It is very easy to understand and offers a lot of functionality including efficient number theoretic algorithms.

You can download gmp at this link. It is a library for C. It has its own data types(mpz_t, mpz_f etc.) defined in the library.

Using gmp in C may be a bit frustrating due to the data types and initialization of the declared variables. There is a python extension for this library: gmpy. This makes your task a lot easier.

Assuming, you have gmp and gmpy let us see how to generate large prime numbers.

There are few methods to generate(test, to be more precise) prime numbers apart from the trivial method of checking for its divisibility.

The available methods can be classified into two types:

1) Probabilistic

2)  Deterministic

1) Probabilistic: Algorithms falling in this category are probabilistic, in simple words they cannot be trusted. There is chance of the algorithms giving a wrong answer. Some of these are

a) Primality test based on Fermat’s little theorem

b) Solovay – Strassen test

c) Miller – Rabin Test

2) Deterministic approach: Algorithms of this class always give exact answers. There is no chance of error.

a) Algorithm due to AKS( Agarwal, Kayal, Saxena IIT Kanpur)

We heavily rely upon probabilistic test though we have an implementation for the deterministic test mentioned above. This is due to the fact that the running time of AKS is pretty huge.

Fermat’s little theorem by itself is not a very good method for testing primality because there are composite numbers which do satisfy the theorem.

Compared to Miller – Rabin, Solovay – Strassen has higher probability of error. Hence Miller – Rabin is used. More explanation regarding Miller – Rabin can be found here.

Following is a python program for Miller – Rabin Test:



More Explanation about the code in my upcoming posts.

Do Gaps Between Primes Affect RSA Keys?

Leave a comment

Very Interesting…

Gödel's Lost Letter and P=NP

Arjen Lenstra is one of the top computational number theorists in the world, especially on the state-of-the-art in integer factoring. For example, he helped create the best general factorization method known to date—the number field sieve—see here for a previous discussion. Also he was one of the authors of the great paper that introduced the LLL lattice algorithm, which was joint work with one of his brothers, Hendrik Lenstra, and also with László Lovász.

Today we wish to add some potential considerations to the discussion of Lenstra’s recent paper on why RSA public keys deployed in practice are sometimes breakable. Ken and I do not know whether they actually apply, but there are some reasonable questions to ask, and a tie-in to general problems in number theory.

The paper is joint work with James Hughes, Maxime Augie, Joppe Bos, Thorsten Kleinjung, and Christophe Wachter, and bears the title, “Ron was…

View original post 2,492 more words