Re: Public Key Recovery Operation
Ricardo Alex <[email protected]> Thu, 9 Nov 2023 06:05:18 -0800 (PST)
| Newsgroups | gmane.comp.encryption.cryptopp |
|---|---|
| Message-ID | <[email protected]> |
------=_Part_9976_2099669675.1699538718789
Content-Type: multipart/alternative;
boundary="----=_Part_9977_72596269.1699538718789"
------=_Part_9977_72596269.1699538718789
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I am trying to follow the instructions in https://www.secg.org/sec1-v2.pdf=
section =20
4.1.6
Output: An elliptic curve public key Q for which (r, s) is a valid=20
signature on message M.=20
Actions: Find public key Q as follows.=20
1. For j from 0 to h do the following. 1.1. Let x =3D r + jn.=20
1.2. Convert the integer x to an octet string X of length mlen using the=20
conversion routine specified in Section 2.3.7, where mlen =3D d(log2 p)/8e =
or=20
mlen =3D dm/8e.=20
1.3. Convert the octet string 0216kX to an elliptic curve point R using the=
=20
conversion routine specified in Section 2.3.4. If this conversion routine=
=20
outputs =E2=80=9Cinvalid=E2=80=9D, then do another iteration of Step 1.=20
1.4. If nR 6=3D O, then do another iteration of Step 1. 1.5. Compute e from=
M=20
using Steps 2 and 3 of ECDSA signature verification. 1.6. For k from 1 to 2=
=20
do the following. 1.6.1. Compute a candidate public key as: Q =3D r =E2=88=
=921 (sR =E2=88=92=20
eG).
The code so far:
DL_GroupParameters_EC<ECP> params =3D ASN1::secp256k1();
Integer=20
r("eefd86d83fd068cf979cfb11bf0696c66fc568ee342319a733ac9e804d6ea88d");
Integer=20
s("0c12365ddc49f1b631c4c4a80764f8938afdd05563e00cff367da7cb715fccf1");
std::string message =3D=20
"e9128504a817c80082520894787945765ac5a4f186a13e702664d6ecb78f57b68203e88083=
0138818080";
byte hash[CryptoPP::SHA256::DIGESTSIZE];
SHA256().CalculateDigest(hash, (const byte*)message.data(), message.size())=
;
Integer e(hash, CryptoPP::SHA256::DIGESTSIZE);
for (int j =3D 0; j <=3D params.GetCofactor(); ++j)
{
Integer x =3D r + j * params.GetSubgroupOrder();
SecByteBlock xBytes(x.MinEncodedSize());
x.Encode(xBytes.BytePtr(), xBytes.SizeInBytes());
ECP::Point R;
if (!params.GetCurve().DecodePoint(R, xBytes, xBytes.SizeInBytes()))
{
std::cout << "Invalid point. Trying another iteration." << std::endl;
continue;
}
if (!params.GetCurve().Multiply(e, R).identity)
{
std::cout << "nR is not the point at infinity. Trying another iteration."=
=20
<< std::endl;
continue;
}
for (int k =3D 1; k <=3D 2; ++k)
{=20
// Compute a candidate public key ...
}
}=20
Any Idea how to compute a candidate public key considering according to=20
manual it is Q =3D r =E2=88=921 (sR =E2=88=92 eG)?
Em quinta-feira, 9 de novembro de 2023 =C3=A0s 08:54:44 UTC-3, Ricardo Alex=
=20
escreveu:
> According to https://www.secg.org/sec1-v2.pdf
>
> In section 4.1.6 Public Key Recovery Operation it' s possible to=20
> recover the public Key Q, at least to within a small number of choices, =
=20
> given an ECDSA signature (r, s) and EC domain parameters.
>
> Input: The public key recovery operations takes as input:=20
>
> 1. Elliptic curve domain parameters T =3D (p, a, b, G, n, h) or T =3D (m,=
=20
> f(x), a, b, G, n, h) at the desired security level.
> 2. A message M.=20
> 3. An ECDSA signature value (r, s) that is valid on message M for some=20
> public key to be determined. =20
>
> Is it possible to achieve that using the crypto++ library?=20
>
--=20
You received this message because you are subscribed to the Google Groups "=
Crypto++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to [email protected].
To view this discussion on the web visit https://groups.google.com/d/msgid/=
cryptopp-users/6dc529f2-9adc-4894-9134-b52b705bfef6n%40googlegroups.com.
------=_Part_9977_72596269.1699538718789
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I am trying to follow the instructions in=C2=A0
<a href=3D"https://www.secg.org/sec1-v2.pdf" target=3D"_blank" rel=3D"nofol=
low" style=3D"color: rgb(26, 115, 232);">https://www.secg.org/sec1-v2.pdf</=
a>=C2=A0section=C2=A0
4.1.6<div>=C2=A0 Output: An elliptic curve public key Q for which (r, s) is=
a valid signature on message M.=C2=A0</div><div>Actions: Find public key Q=
as follows.=C2=A0</div><div>1. For j from 0 to h do the following.
1.1. Let x =3D r + jn.=C2=A0</div><div>1.2. Convert the integer x to an oct=
et string X of length mlen using the conversion routine
specified in Section 2.3.7, where mlen =3D d(log2 p)/8e or mlen =3D dm/8e.=
=C2=A0</div><div>1.3. Convert the octet string 0216kX to an elliptic curve =
point R using the conversion routine
specified in Section 2.3.4. If this conversion routine outputs =E2=80=9Cinv=
alid=E2=80=9D, then do another
iteration of Step 1.=C2=A0</div><div>1.4. If nR 6=3D O, then do another ite=
ration of Step 1.
1.5. Compute e from M using Steps 2 and 3 of ECDSA signature verification.
1.6. For k from 1 to 2 do the following.
1.6.1. Compute a candidate public key as:
Q =3D r
=E2=88=921
(sR =E2=88=92 eG).</div><div><br /></div><div>The code so far:</div><div><b=
r /></div><div><font color=3D"#008000">=C2=A0</font><font color=3D"#0000ff"=
>DL_GroupParameters_EC<ECP> params =3D ASN1::secp256k1();</font></div=
><font color=3D"#0000ff"><br />Integer r("eefd86d83fd068cf979cfb11bf0696c66=
fc568ee342319a733ac9e804d6ea88d");<br />Integer s("0c12365ddc49f1b631c4c4a8=
0764f8938afdd05563e00cff367da7cb715fccf1");<br /><span style=3D"white-space=
: pre;"> </span><br />std::string message =3D "e9128504a817c800825208947879=
45765ac5a4f186a13e702664d6ecb78f57b68203e880830138818080";<br />byte hash[C=
ryptoPP::SHA256::DIGESTSIZE];<br />SHA256().CalculateDigest(hash, (const by=
te*)message.data(), message.size());<br /><br />Integer e(hash, CryptoPP::S=
HA256::DIGESTSIZE);<br /><br />for (int j =3D 0; j <=3D params.GetCofact=
or(); ++j)<br />{<br /><span style=3D"white-space: pre;"> </span>Integer x =
=3D r + j * params.GetSubgroupOrder();<br /><span style=3D"white-space: pre=
;"> </span><br /><span style=3D"white-space: pre;"> </span>SecByteBlock x=
Bytes(x.MinEncodedSize());<br /><span style=3D"white-space: pre;"> </span>x=
.Encode(xBytes.BytePtr(), xBytes.SizeInBytes());<br /><span style=3D"white-=
space: pre;"> </span><br /><span style=3D"white-space: pre;"> </span>ECP:=
:Point R;<br /><span style=3D"white-space: pre;"> </span>if (!params.GetCur=
ve().DecodePoint(R, xBytes, xBytes.SizeInBytes()))<br /><span style=3D"whit=
e-space: pre;"> </span>{<br /><span style=3D"white-space: pre;"> </span>st=
d::cout << "Invalid point. Trying another iteration." << std::e=
ndl;<br /><span style=3D"white-space: pre;"> </span>continue;<br /><span s=
tyle=3D"white-space: pre;"> </span>}<br /><span style=3D"white-space: pre;"=
> </span><br /><span style=3D"white-space: pre;"> </span>if (!params.GetC=
urve().Multiply(e, R).identity)<br /><span style=3D"white-space: pre;"> </s=
pan>{<br /><span style=3D"white-space: pre;"> </span>std::cout << "n=
R is not the point at infinity. Trying another iteration." << std::en=
dl;<br /><span style=3D"white-space: pre;"> </span>continue;<br /><span st=
yle=3D"white-space: pre;"> </span>}<br /><span style=3D"white-space: pre;">=
</span><br /><span style=3D"white-space: pre;"> </span>for (int k =3D 1; k=
<=3D 2; ++k)<br /><span style=3D"white-space: pre;"> </span>{<span styl=
e=3D"white-space: pre;"> </span><br /><span style=3D"white-space: pre;"> =
</span>// Compute a candidate public key ...<br /><span style=3D"white-spa=
ce: pre;"> </span><br /><span style=3D"white-space: pre;"> </span>}<br /><=
/font><div><font color=3D"#0000ff">}=C2=A0</font><br /><br /></div><div>Any=
Idea how to c<font color=3D"#000000">ompute a candidate public key</font>=
=C2=A0 considering according to manual it is=C2=A0
Q =3D r
=E2=88=921
(sR =E2=88=92 eG)?</div><div class=3D"gmail_quote"><div dir=3D"auto" class=
=3D"gmail_attr">Em quinta-feira, 9 de novembro de 2023 =C3=A0s 08:54:44 UTC=
-3, Ricardo Alex escreveu:<br/></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); paddin=
g-left: 1ex;">According to=C2=A0<a href=3D"https://www.secg.org/sec1-v2.pdf=
" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.go=
ogle.com/url?hl=3Dpt&q=3Dhttps://www.secg.org/sec1-v2.pdf&source=3D=
gmail&ust=3D1699623811779000&usg=3DAOvVaw081YpfQC9nIDdTslOZT5nP">ht=
tps://www.secg.org/sec1-v2.pdf</a><div><br></div><div>=C2=A0 In section 4.1=
.6=C2=A0
Public Key Recovery Operation it' s possible to recover the public Key =
Q, at least to within a small number of choices,=C2=A0 given an ECDSA signa=
ture (r, s) and EC domain parameters.</div><div><br></div><div>=C2=A0 Input=
: The public key recovery operations takes as input:=C2=A0</div><div><br></=
div><div>1. Elliptic curve domain parameters T =3D (p, a, b, G, n, h) or T =
=3D (m, f(x), a, b, G, n, h) at the
desired security level.</div><div>2. A message M.=C2=A0</div><div>3. An ECD=
SA signature value (r, s) that is valid on message M for some public key to=
be
determined.=C2=A0=C2=A0<br></div><div><br></div><div>Is it possible to achi=
eve that using the crypto++ library?=C2=A0<br></div></blockquote></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Crypto++ Users" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]">cryp=
[email protected]</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/cryptopp-users/6dc529f2-9adc-4894-9134-b52b705bfef6n%40googlegro=
ups.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d=
/msgid/cryptopp-users/6dc529f2-9adc-4894-9134-b52b705bfef6n%40googlegroups.=
com</a>.<br />
------=_Part_9977_72596269.1699538718789--
------=_Part_9976_2099669675.1699538718789--