Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.80 KB | None | 0 0
  1. /**
  2. * TP1 - Partage de secret de Shamir
  3. *
  4. * @author Simon Bessenay
  5. * @author Antoine Marjault
  6. *
  7. * @date 10/04/2019
  8. */
  9.  
  10. // Galois Field
  11. const Reals = {
  12. add : (a,b) => a + b,
  13. sub : (a,b) => a - b,
  14. mul : (a,b) => a * b,
  15. '0' : 0,
  16. '1' : 1,
  17. div : (a,b) => a / b,
  18. };
  19.  
  20. /**
  21. * @function gcd
  22. * Extended Euclidean algorithm
  23. *
  24. * @param a
  25. * @param b
  26. */
  27. function xgcd(a, b) {
  28. if (b < 0) {
  29. [g,c,d] = xgcd(a,-b);
  30. return [g,c,-d];
  31. }
  32. else if (a < b) {
  33. [g,c,d] = xgcd(b, a);
  34. return [g,d,c];
  35. }
  36. else if (b == 0) {
  37. return [a,1,0];
  38. }
  39. else {
  40. [g,c,d] = xgcd(a-b,b);
  41. return [g,c,d-c];
  42. }
  43. }
  44.  
  45. /**
  46. * @function GF
  47. * Galois Field
  48. *
  49. * @param p
  50. */
  51. const GF = p => {
  52. const inverses = [];
  53.  
  54. const modp = n => ((n % p) + p) % p;
  55.  
  56. const inv = n => {
  57. n = modp(n);
  58. if (!inverses[n]) {
  59. let [g,c,d] = xgcd(n,p);
  60. c = modp(c);
  61. inverses[c] = n;
  62. inverses[n] = c;
  63. }
  64. return inverses[n];
  65. }
  66.  
  67. return {
  68. add : (a,b) => modp(a + b),
  69. sub : (a,b) => modp(a - b),
  70. mul : (a,b) => modp(a * b),
  71. div : (a,b) => modp(a / b),
  72. '0' : 0,
  73. '1' : 1,
  74. };
  75. }
  76.  
  77. /**
  78. * @function evaluatePolynomial
  79. * evaluates a polynomial function at a given value
  80. *
  81. * @param {Field} F field object (reals, complexes...)
  82. * @param {Array} C coefficients representing the polynomial function p.
  83. * @param {Field element} x value
  84. * @returns {Number} Returns the value of p(x).
  85. *
  86. * @example
  87. * // returns(x -> x + x²)(2) = 6
  88. * evaluatePolynomial(Reals, [0, 1, 1], 2)
  89. *
  90. * @example
  91. * // returns a function that evaluates(x -> x + x²)
  92. * var p = evaluatePolynomial.bind(Reals, [0, 1, 1])
  93. * // returnsp(2) = 6
  94. * p(2)
  95. */
  96. function evaluatePolynomial(F, C, x) {
  97. return C.map((elem, index) => F.mul(elem, Math.pow(x, index)))
  98. .reduce((accu, elem) => F.add(accu, elem));
  99. }
  100.  
  101. /**
  102. * @function lagrange
  103. * generate polynomial interpolation of Lagrange
  104. *
  105. * @param {Field} F field object (reals, complexes...)
  106. * @param {Points} P list of points
  107. * @returns {Polynom} Polynom (the interpolated polynom)
  108. *
  109. * @example
  110. * // returns [2, -11/2, 5/2]
  111. * lagrange(Reals, [(0,2), (1,-1), (2,1)])
  112. *
  113. */
  114. function lagrange(F, P){
  115. conv2 = (t,b) => [...t,0].map((v,k) => F.add(F.mul(b, v), t[k-1] | 0));
  116. let l = {}
  117.  
  118. for (let i = 0; i < P.length; i++) {
  119. li = P.filter((_,j) => j !== i)
  120. .map(({x}) => -x)
  121. .reduce(conv2, [1]);
  122.  
  123. var den = 1;
  124. for (let j = 0; j < P.length; j++) {
  125. if(i != j) {
  126. den *= F.sub(P[i]['x'], P[j]['x']);
  127. }
  128. }
  129.  
  130. l[i] = li.map(x => F.mul((x/den),P[i]['y']));
  131. }
  132.  
  133. //Initializing result
  134. res = []
  135. for(let i = 0; i < P.length; i++) {
  136. res.push(0);
  137. }
  138.  
  139. for( let i = 0; i < Object.keys(l).length; i++) {
  140. for( let j = 0; j < P.length; j++) {
  141. res[j] = F.add(res[j],l[i][j]);
  142. }
  143. }
  144.  
  145. return res;
  146. }
  147.  
  148. /**
  149. * @function encodeSecret
  150. * generate polynomial interpolation of Lagrange
  151. *
  152. * @param {Field} F
  153. * @param {Integer} Secret
  154. * @param {Integer} n number of pieces
  155. * @param {Integer} t number of pair required to reconstruct the secret
  156. * @returns {List} l list of n pairs (xi, P(xi))
  157. *
  158. * @example
  159. * // returns [2, -11/2, 5/2]
  160. * lagrange(Reals, [(0,2), (1,-1), (2,1)])
  161. *
  162. */
  163. function encodeSecret(F, secret, n, t) {
  164.  
  165. //creating random polynom with secret key
  166. polynome = [secret];
  167. for(let i=1; i<t; i++) {
  168. polynome.push(Math.floor(Math.random() * Math.floor(1000)));
  169. }
  170.  
  171. pairs = [];
  172. for(let i = 1; i <= n; i++) {
  173. pairs.push({ x : i, y : evaluatePolynomial(F, polynome, i)});
  174. }
  175.  
  176. tmp = [];
  177. res = [];
  178. count = 0;
  179. while (count != 3){
  180. randint = Math.floor(Math.random() * Math.floor(n));
  181. if (!tmp.includes(randint)) {
  182. res.push(pairs[randint]);
  183. tmp.push(randint);
  184. count ++;
  185. }
  186. }
  187.  
  188. return res;
  189. }
  190.  
  191. function decodeSecret(F, pairs) {
  192. return evaluatePolynomial(F, lagrange(F, pairs), 0);
  193. }
  194.  
  195. //console.log('xgcd = ' + xgcd(28, 34));
  196. //console.log('f(2) = ' + evaluatePolynomial(Reals, [0,1,1], 2));
  197. //console.log(lagrange(Reals, [{x: 0, y: 2}, {x: 1, y: -1}, {x: 2, y: 1}]));
  198.  
  199. pairs = encodeSecret(Reals, 1234, 6, 3);
  200. console.log(decodeSecret(Reals, pairs));
  201.  
  202. //comment utiliser votre code pour :
  203. //Comment on peut partager un secret -> donner un petit exemple
  204. //Comment faire de l'interpolation polynomiale -> donner un petit exemple
  205. // .md 1 page
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement