I am looking at a proprietary signature scheme used in production. It involves a short Weierstrass curve $E_{\mathcal{W}}:y^2=x^3+ax+b$ in the prime field $\mathbb{F}_p$. The parameters are set up such that $E_{\mathcal{W}}$ is always expressible as a Montgomery curve $E_{\mathcal{M}}:y^2=x^3+x$ (i.e. $a_{\mathcal{W}}=1$, $b_{\mathcal{W}}=0$, $A_{\mathcal{M}}=0$, and $B_{\mathcal{M}}=1$). As far as I know, the Montgomery form is never used for verification. The curve has highly composite order $n$, with a base point $B$ having prime order $\ell$.
The verification process given a hash function $H$, a keyed hash function built from $H$ with (namely $H$ in HMAC mode, $H_k$), a message $M$, a public key $K$ and a signature consisting of a scalar $s$ and a hash $h$ is performed as follows:
- $h_1=H_{c_1}(M||h)$.
- $R=s\cdot(sB+h_1K)$
- $h_2=H_{c_2}(M || R_x || R_y)$, where $R_x$ is the $x$ coordinate of $R$ and accordingly $R_y$ is the $y$ coordinate of $R$
- If $h_2=h$, the signature is valid; else, it is invalid.
$c_1$ and $c_2$ are static HMAC keys known both to the signer and the verifier. My conjecture is that they act as domain separation strings.
I am trying to determine if there is an efficient way of creating a signature that does not involve taking a square root in $\mathbb{F}_p$. Square roots are not trivially found in $p$ because $p$ it may be that $p\equiv1\pmod{4}$ and $p\equiv1\pmod{8}$. Currently, I reach the following signing process:
- Choose a nonce $r$ such that $0<r<\ell$.
- $R=rB$
- $h_2=H_{c_2}(M||R_x||R_y)$
- $h_1=H_{c_1}(M||h_2)$
- $s=\frac{-Hk\pm\sqrt{(h_1k)^2+4r}}{2}\pmod{\ell}$, where $k$ is the secret key corresponding to $K$ in the verification process
- If $\sqrt{(h_1k)^2+4r}$ has no solution in $\mathbb{F}_p$, restart from the beginning.
- Output signature $(s, h_2)$.
Is there a way to create a signature passing the above verification process that does not involve a square root in $\mathbb{F}_p$?
