Cryptography Asked by Columbida on January 26, 2021

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=scdot(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 $pequiv1pmod{4}$ and $pequiv1pmod{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{-Hkpmsqrt{(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$?**

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.

Answered by asnfkjsdx on January 26, 2021

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...

Answered by poncho on January 26, 2021

1 Asked on December 31, 2021 by kaa

0 Asked on December 31, 2021 by sunitha-tappari

0 Asked on December 28, 2021 by dawnforce

2 Asked on December 26, 2021 by maarten-bodewes

0 Asked on December 24, 2021

2 Asked on December 21, 2021 by skaht

1 Asked on December 21, 2021 by kmart875

1 Asked on December 19, 2021 by sanket1729

1 Asked on December 19, 2021 by vivekanand-v

2 Asked on December 17, 2021

0 Asked on December 17, 2021

3 Asked on December 14, 2021 by antonpug

1 Asked on December 14, 2021 by beroal

0 Asked on December 8, 2021

Get help from others!

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir