# How to simplify a the signing process in an elliptic curve signature scheme that involves a quadratic verification equation?

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:

1. $$h_1=H_{c_1}(M||h)$$.
2. $$R=s\cdot(sB+h_1K)$$
3. $$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$$
4. 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:

1. Choose a nonce $$r$$ such that $$0.
2. $$R=rB$$
3. $$h_2=H_{c_2}(M||R_x||R_y)$$
4. $$h_1=H_{c_1}(M||h_2)$$
5. $$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
6. If $$\sqrt{(h_1k)^2+4r}$$ has no solution in $$\mathbb{F}_p$$, restart from the beginning.
7. 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$$?

• "The curve has highly composite order $n$"; it is easy to compute discrete logs in curves of smooth order; and even if "highly composite" doesn't mean smooth, that makes it easier than it needs to be. Why do you select such a curve? – poncho Sep 7 '20 at 13:28
• @poncho I do not select such a curve. I am studying a commercial system being used in practice. The rationale behind choices like that is beyond me. It may need adding that the scheme dates from the early 2000s, so perhaps this may be related to generating curves efficiently. – Columbida Sep 7 '20 at 13:38
• Well, if the largest prime factor of the curve order is $q$, you can recover the private key from the public key in essentially $O(\sqrt{q})$ time. Depending on how large $q$ is, this might be doable on a laptop... – poncho Sep 7 '20 at 13:51
• @poncho Thank you once more. But this is not about recovering the key. I am fully ware of $\ell$, $K$ and $k$. This is about signature generation efficiency given the secret key $k$, not about recovering the key in the first place. – Columbida Sep 7 '20 at 13:59
• If Poncho's point-at-infinity attack does not cut it, an option is to code Tonelli-Shanks, which is not rocket science. – fgrieu Sep 7 '20 at 14:12

## 2 Answers

Is there a way to create a signature passing the above verification process that does not involve a square root in $$\mathbb{F}_p$$?

Well, one obvious thing to try is setting $$R=0$$ (the point at infinity); assuming the code doesn't have any protection against that (and the pseudocode doesn't), you compute $$h = H_{c_2}(M || R_x || R_y )$$ (where $$R_x, R_y$$ is whatever representation the point-at-infinity has), set $$s=0$$, and you're done...

Ignoring the case of $$R$$ being the point at infinity, I have found a patent that seems to describe the system you outline to a T: US 7,512,232 B2, which also makes me suspect that your "commercial" system ends up being Microsoft's in particular. It specifically notes that taking the square root modulo $$\ell$$ is a requirement. In other words, no, there is no way to simplify.