1

I was implementing threshold signatures protocol described in this paper and I run into a case where it fails and I don't understand reasons why. In the end, u and x should be the same, but they are not. I would appreciate any advice that will help me to find the bug.

This is JS code, it can be executed in browser console

/// TSS 2-of-2 case
// Field modulus, secp2561k
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337n

// party 1 Polynomial coeff of degree 1
coeff_1 = 103808273981011494448342588544071102049904991793672697167547228275701563388858n
// coeff_1 = 10380827398101149444834258854407110204990499179367269716754722827570156338885n // Working coeff
 
// party 1 Polynomial coeff of degree 1
coeff_2 = 49961718147812071312795198333632033669565055597187655909241672498689891015278n
// coeff_2 = 4996171814781207131279519833363203366956505559718765590924167249868989101527n // Working coeff 

// Party 1 secret
u_1 = 6989964936015280241594720270850184250394589151026058230978623558313385587815n

// Party 2 secret
u_2 = 91492373973552717359377053249757253672786176158857596037729237022345023720795n

// Party 1 Shamir points
y1_x = 1n
y1_1 = (y1_x * coeff_1 + u_1) % n
// 110798238917026774689937308814921286300299580944698755398525851834014948976673n
y1_2 = (y1_x * coeff_2 + u_2) % n
// 25662002884048593248601266574701379489513667476970347564365746379516753241736n

// Party 2 Shamir points
y2_x = 2n
y2_1 = (y2_x * coeff_1 + u_1) % n
// 98814423660722073714708912350304480497367008459296548183467916968198350871194n
y2_2 = (y2_x * coeff_2 + u_2) % n
// 75623721031860664561396464908333413159078723074158003473607418878206644257014n

// Party 1 point (y1_x, y1)
y1 = (y1_1 + y1_2) % n

// Party 2 point (y1_x, y1)
y2 = (y2_1 + y2_2) % n

// Common secret
u = (u_1 + u_2) % n

// Same secret, that went though Shamir schema
x = (y1*2n - y2) % n

// Checking calculations, should be 0 
u - x
```
Maarten Bodewes
  • 90,524
  • 13
  • 150
  • 263
Max
  • 2,063
  • 2
  • 17
  • 16

1 Answers1

1

Your code is almost correct, just missing the final modulus at the end. Change the last line to

(u - x) % n;

The (u -x) is exactly n.

115792089237316195423570985008687907852837564279074904382605163141518161494337

kelalaka
  • 5,064
  • 5
  • 27
  • 44
  • oooo, thank you very much, I spent so much time trying to figure out what is the issue there, and totally missed this fact. – Max Jul 06 '21 at 07:41
  • When working with modulo, make sure that you compare their residues and also make sure that the modulus operation is [non-negative](https://stackoverflow.com/q/4467539/1820553) – kelalaka Jul 06 '21 at 07:59
  • That's exactly what was driving me crazy. I totally missed the fact that the residue was minus the modulo – Max Jul 07 '21 at 07:11