Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * TP1 - Partage de secret de Shamir
- *
- * @author Simon Bessenay
- * @author Antoine Marjault
- *
- * @date 10/04/2019
- */
- // Galois Field
- const Reals = {
- add : (a,b) => a + b,
- sub : (a,b) => a - b,
- mul : (a,b) => a * b,
- '0' : 0,
- '1' : 1,
- div : (a,b) => a / b,
- };
- /**
- * @function gcd
- * Extended Euclidean algorithm
- *
- * @param a
- * @param b
- */
- function xgcd(a, b) {
- if (b < 0) {
- [g,c,d] = xgcd(a,-b);
- return [g,c,-d];
- }
- else if (a < b) {
- [g,c,d] = xgcd(b, a);
- return [g,d,c];
- }
- else if (b == 0) {
- return [a,1,0];
- }
- else {
- [g,c,d] = xgcd(a-b,b);
- return [g,c,d-c];
- }
- }
- /**
- * @function GF
- * Galois Field
- *
- * @param p
- */
- const GF = p => {
- const inverses = [];
- const modp = n => ((n % p) + p) % p;
- const inv = n => {
- n = modp(n);
- if (!inverses[n]) {
- let [g,c,d] = xgcd(n,p);
- c = modp(c);
- inverses[c] = n;
- inverses[n] = c;
- }
- return inverses[n];
- }
- return {
- add : (a,b) => modp(a + b),
- sub : (a,b) => modp(a - b),
- mul : (a,b) => modp(a * b),
- div : (a,b) => modp(a / b),
- '0' : 0,
- '1' : 1,
- };
- }
- /**
- * @function evaluatePolynomial
- * evaluates a polynomial function at a given value
- *
- * @param {Field} F field object (reals, complexes...)
- * @param {Array} C coefficients representing the polynomial function p.
- * @param {Field element} x value
- * @returns {Number} Returns the value of p(x).
- *
- * @example
- * // returns(x -> x + x²)(2) = 6
- * evaluatePolynomial(Reals, [0, 1, 1], 2)
- *
- * @example
- * // returns a function that evaluates(x -> x + x²)
- * var p = evaluatePolynomial.bind(Reals, [0, 1, 1])
- * // returnsp(2) = 6
- * p(2)
- */
- function evaluatePolynomial(F, C, x) {
- return C.map((elem, index) => F.mul(elem, Math.pow(x, index)))
- .reduce((accu, elem) => F.add(accu, elem));
- }
- /**
- * @function lagrange
- * generate polynomial interpolation of Lagrange
- *
- * @param {Field} F field object (reals, complexes...)
- * @param {Points} P list of points
- * @returns {Polynom} Polynom (the interpolated polynom)
- *
- * @example
- * // returns [2, -11/2, 5/2]
- * lagrange(Reals, [(0,2), (1,-1), (2,1)])
- *
- */
- function lagrange(F, P){
- conv2 = (t,b) => [...t,0].map((v,k) => F.add(F.mul(b, v), t[k-1] | 0));
- let l = {}
- for (let i = 0; i < P.length; i++) {
- li = P.filter((_,j) => j !== i)
- .map(({x}) => -x)
- .reduce(conv2, [1]);
- var den = 1;
- for (let j = 0; j < P.length; j++) {
- if(i != j) {
- den *= F.sub(P[i]['x'], P[j]['x']);
- }
- }
- l[i] = li.map(x => F.mul((x/den),P[i]['y']));
- }
- //Initializing result
- res = []
- for(let i = 0; i < P.length; i++) {
- res.push(0);
- }
- for( let i = 0; i < Object.keys(l).length; i++) {
- for( let j = 0; j < P.length; j++) {
- res[j] = F.add(res[j],l[i][j]);
- }
- }
- return res;
- }
- /**
- * @function encodeSecret
- * generate polynomial interpolation of Lagrange
- *
- * @param {Field} F
- * @param {Integer} Secret
- * @param {Integer} n number of pieces
- * @param {Integer} t number of pair required to reconstruct the secret
- * @returns {List} l list of n pairs (xi, P(xi))
- *
- * @example
- * // returns [2, -11/2, 5/2]
- * lagrange(Reals, [(0,2), (1,-1), (2,1)])
- *
- */
- function encodeSecret(F, secret, n, t) {
- //creating random polynom with secret key
- polynome = [secret];
- for(let i=1; i<t; i++) {
- polynome.push(Math.floor(Math.random() * Math.floor(1000)));
- }
- pairs = [];
- for(let i = 1; i <= n; i++) {
- pairs.push({ x : i, y : evaluatePolynomial(F, polynome, i)});
- }
- tmp = [];
- res = [];
- count = 0;
- while (count != 3){
- randint = Math.floor(Math.random() * Math.floor(n));
- if (!tmp.includes(randint)) {
- res.push(pairs[randint]);
- tmp.push(randint);
- count ++;
- }
- }
- return res;
- }
- function decodeSecret(F, pairs) {
- return evaluatePolynomial(F, lagrange(F, pairs), 0);
- }
- //console.log('xgcd = ' + xgcd(28, 34));
- //console.log('f(2) = ' + evaluatePolynomial(Reals, [0,1,1], 2));
- //console.log(lagrange(Reals, [{x: 0, y: 2}, {x: 1, y: -1}, {x: 2, y: 1}]));
- pairs = encodeSecret(Reals, 1234, 6, 3);
- console.log(decodeSecret(Reals, pairs));
- //comment utiliser votre code pour :
- //Comment on peut partager un secret -> donner un petit exemple
- //Comment faire de l'interpolation polynomiale -> donner un petit exemple
- // .md 1 page
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement