2
$\begingroup$

I don't know if I've placed the question right, It is half maths, half programming. I'm writing Schnorr Ring Signatures on Elliptic Curves in Java and I have a problem. I've found scheme on integers and translated it to elliptic curves.

In point 3 on page 11

$R_s = g^a \prod_{i \neq s}(y_i^{-H(m, R_i)}) \ mod \ p$

and in my elliptic curve version

$R_s = aG + \sum_{i\neq s}(Y_i*-H(m,R_i))$

where $G$ is a generator, $Y_i$ is a public key of i-th user, $m$ is a message and $R_i$ is $a_iG$ where $a_i$ is random.

I have

  • basepoint $G$
  • cofactor $h$ to the order of $G$
  • order $n$ of $G$
  • points $A$ and $B$

My question is how to perform a modular inverse of $H(m,R_i)$. In Java I have a modInverse method on BigIntegers but I have to know value of $p$. How to find value of $p$? Or how to calculate $-H(m,R_i)$?

EDIT: OK, thakns. I've found $p$ value. But still I'm getting wrong results. If someone would be so nice to look at it here is my sample code. Thanks in advance for help

$\endgroup$
  • $\begingroup$ Are you sure you haven't got $p$ as well? It's part of the curve definition, e.g. in Bouncy you can do params.getCurve().getField().getCharacteristic(); $\endgroup$ – Maarten Bodewes Dec 28 '15 at 12:32
1
$\begingroup$

If $g^a$ in the modular version translates to $aG$ or $a*G$ in the elliptic curve version, then $y_i^{-H(m, R_i)}$ should translate to $$\begin{align*} (-H(m, R_i))*Y_i&=-(H(m, R_i)*Y_i)&\text{(1)}&\text{ or equivalently}\\ &=H(m, R_i)*(-Y_i)&\text{(2)}&\text{ or equivalently}\\ &=((-H(m, R_i))\bmod n)*Y_i&\text{(3)}&\\ \end{align*}$$

The form (1) leads to an expression requiring one point subtraction or inversion: $$R_s=a*G-\sum_{i\neq s}(H(m,R_i)*Y_i)$$

The form (3) leads to an expression that requires none: $$R_s=a*G+\sum_{i\neq s}(((-H(m,R_i))\bmod n)*Y_i)$$

Note: By definition, $u\bmod n$ is the uniquely defined $v$ with $0\le v<n$ and $u-v$ a multiple of $n$. When $u\ge0$, $(-u)\bmod n$ can be computed as $n-1-r$, where $r$ is the remainder of the division of $(n-1+u)$ by $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.