Shamir Secret Splitting code in C++

This is the rough code for Shamir secret splitting and combining written in C++. Kindly change according to your own preferences 🙂 P.S: you have to know the basics of Shamir Secret Sharing and Lagrange’s Interpolation before understanding this code. More details can be found here and a java implementation of Shamir Secret Splitting can be found  here.

void split(int number, int available, int needed, int prime){
int coef[10];
int shar[10][2]={0,0};
coef[0] = number;
int n = prime - 1;
for(int c = 1; c < needed; c++) {
coef[c] = rand() % n + 1; // (prime-1)+1 is upper and lower bound respectively
}
int x, exp, y;
double accum;
for(x = 1, y = 0; x <= available; x++)
{
/*
* e.g coef = [1234, 166, 94] which is 1234x^0 + 166x^1 + 94x^2
*/
for(exp = 1, accum = coef[0]; exp < needed; exp++)
{
double inn= fmod((pow(double(x), exp)), prime); //pow func always take first argu as float or double
double ac = accum + fmod(coef[exp] * inn,prime);
accum = fmod(ac,prime);

//accum = (accum + (coef[exp] * (Math.pow(x, exp) % prime) % prime)) % prime;

} // Modular math
/*
* Store values as (1, 1494), (2, 1942), (3, 2578), (4, 3402), (5, 4414) (6, 5614) in a 2D Array
*/
shar[x – 1][y] = x;
shar[x – 1][y + 1] = accum;
std::cout << “( index = “<< shar[x – 1][y];
std::cout << “, value = “<< shar[x – 1][y + 1] << ” )” << std::endl;
}
}


/* This is the recursive method Using Extended Euclidean Algorithm*/
/* This function return the gcd of a and b followed by
the pair x and y of equation ax + by = gcd(a,b) */

pair<int, pair<int, int> > extendedEuclid(int a, int b) {
if(a == 0) return make_pair(b, make_pair(0, 1));
pair<int, pair<int, int> > p;
p = extendedEuclid(b % a, a);
return make_pair(p.first, make_pair(p.second.second – p.second.first*(b/a), p.second.first));
}

int modInverse(int a, int m) {
return (extendedEuclid(a,m).second.first + m) % m;
}

int combine(int shares[10][2], int primeNum, int threshold) {
long double accum = 0, startposition =0, nextposition =0;
for (int i=0 ; i<threshold; i++)
{
cout<< shares[i][0] << “-“<<shares[i][1] << endl;
}
for (int i = 0; i < threshold; i++) {
long double num = 1;
long double den = 1;

for (int j = 0; j < threshold; j++) {
if (i != j) {
startposition = shares[i][0];
nextposition = shares[j][0];
num = fmod((num * (-nextposition)), primeNum);
den = fmod((den * (startposition – nextposition)), primeNum);
}
else if (i==j) {continue;}
}

cout<< “den: ” << den ;
cout<<” num: ” << num ;
int mi = modInverse(den, primeNum);
cout<<” inv: ” << mi <<endl;
int value = shares[i][1];

long double tmp = value* num * (modInverse(den, primeNum));
long double acc = (accum + primeNum + tmp);
accum = fmod(acc,primeNum);

cout<< ” value: ” << value ;
cout<< ” tmp: ” << tmp ;
cout<< ” accum: ” << accum <<endl;
}

cout<< “The secret is: ” << accum;

return accum;
}

Modular Multiplicative Inverse

A very useful post … helps me very much writing key splitter in c++ .. reference code is taking from http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

COME ON CODE ON

The modular multiplicative inverse of an integer a modulo m is an integer x such that $latex a^{-1} equiv x pmod{m}.$

That is, it is the multiplicative inverse in the ring of integers modulo m. This is equivalent to $latex ax equiv aa^{-1} equiv 1 pmod{m}.$

The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1).

Let’s see various ways to calculate Modular Multiplicative Inverse:

1. Brute Force
We can calculate the inverse using a brute force approach where we multiply a with all possible values x and find a x such that $latex ax equiv 1 pmod{m}.$ Here’s a sample C++ code:

The time complexity of the above codes is O(m).

2. Using Extended Euclidean Algorithm
We have to find a number x such that a·x = 1 (mod m). This can be written as well…

View original post 985 more words

Tips and Tricks about creating an effective presentation

While reading through online blogs i’ve found out some useful articles related to graphical presentation styles by Scott Schwertly. First article named The 4 Basic Principles of Presentation describes Balance, Emphasis, Unity and movement among objects as key factors to attain viewer’s attention. Whereas, the second article on How to utilize the Gestalt principle explains about The Gestalt Principles designed and developed by The Berlin School.

Trying to install and configure OpenSSL  from last two days. Finally, i did it 😀

My Specs were:

> Windows 8.1 (64 bit)

> Visual studio 2010 64 bit command prompt

> OpenSSL (v 1.0.1g)

> ActivePerl (v 5.16.3)

BTW, a very simple and useful procedure is described here and here

P.S : make sure not to include any spaces in your directory names (i-e always create “OpenSSL-bin” instead of “OpenSSL bin”)