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$
1
  • $\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, 2015 at 12:32

1 Answer 1

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 and acknowledge you have read our privacy policy.

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