Can you tell me why doing scalar multiplication of a point on a Elliptic curve over a finite field gets to a...
$begingroup$
I am reading Programming Bitcoin. The author said:
Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.
He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.
elliptic-curves cryptocurrency
edited yesterday
Maarten Bodewes♦
55.8k679196
asked yesterday
inherithandleinherithandle
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I am reading Programming Bitcoin. The author said:
Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.
He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.
elliptic-curves cryptocurrency
edited yesterday
Maarten Bodewes♦
55.8k679196
asked yesterday
inherithandleinherithandle
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures.
$endgroup$
– Squeamish Ossifrage
yesterday
add a comment |
$begingroup$
I am reading Programming Bitcoin. The author said:
Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.
He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.
elliptic-curves cryptocurrency
edited yesterday
Maarten Bodewes♦
55.8k679196
asked yesterday
inherithandleinherithandle
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I am reading Programming Bitcoin. The author said:
Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the additive identity or $0$). If we imagine a point $G$ and scalar-multiply until we get the point at infinity.
He doesn't explain why. So I don't understand why. I would like you to give me a plain explanation, without a serious mathematical proof, if that could be possible.
elliptic-curves cryptocurrency
elliptic-curves cryptocurrency
edited yesterday
Maarten Bodewes♦
55.8k679196
asked yesterday
inherithandleinherithandle
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Maarten Bodewes♦
55.8k679196
asked yesterday
inherithandleinherithandle
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Maarten Bodewes♦
55.8k679196
edited yesterday
Maarten Bodewes♦
55.8k679196
edited yesterday
Maarten Bodewes♦
55.8k679196
55.8k679196
asked yesterday
inherithandleinherithandle
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
inherithandleinherithandle
1111
asked yesterday
inherithandleinherithandle
1111
1111
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
inherithandle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures.
$endgroup$
– Squeamish Ossifrage
yesterday
add a comment |
1
$begingroup$
If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures.
$endgroup$
– Squeamish Ossifrage
yesterday
1
1
$begingroup$
If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures.
$endgroup$
– Squeamish Ossifrage
yesterday
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The points on the Elliptic Curves are forming an additive group with the identity $mathcal{O}$, the point at infinity.
The scalar multiplication $k P$ this actually means adding $P$, $k$-times itself
$$kP=underbrace{P+P+cdots+P}_{text{$k$ times}}.$$
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
Point addition in $mathbb{Z}_p$ has an interesting property since the number of elements is finite if you add a point $P$ itself many times eventually you will get the identity $mathcal{O}$.
$$underbrace{P+P+cdots+P}_{text{$t$ times}} = mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge.
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field are same then the discrete logarithm on this curves runs in linear time.
edited yesterday
Squeamish Ossifrage
22.3k132101
answered yesterday
kelalakakelalaka
8,78032351
$endgroup$
1
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
inherithandle is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68593%2fcan-you-tell-me-why-doing-scalar-multiplication-of-a-point-on-a-elliptic-curve-o%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The points on the Elliptic Curves are forming an additive group with the identity $mathcal{O}$, the point at infinity.
The scalar multiplication $k P$ this actually means adding $P$, $k$-times itself
$$kP=underbrace{P+P+cdots+P}_{text{$k$ times}}.$$
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
Point addition in $mathbb{Z}_p$ has an interesting property since the number of elements is finite if you add a point $P$ itself many times eventually you will get the identity $mathcal{O}$.
$$underbrace{P+P+cdots+P}_{text{$t$ times}} = mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge.
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field are same then the discrete logarithm on this curves runs in linear time.
edited yesterday
Squeamish Ossifrage
22.3k132101
answered yesterday
kelalakakelalaka
8,78032351
$endgroup$
1
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
add a comment |
$begingroup$
The points on the Elliptic Curves are forming an additive group with the identity $mathcal{O}$, the point at infinity.
The scalar multiplication $k P$ this actually means adding $P$, $k$-times itself
$$kP=underbrace{P+P+cdots+P}_{text{$k$ times}}.$$
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
Point addition in $mathbb{Z}_p$ has an interesting property since the number of elements is finite if you add a point $P$ itself many times eventually you will get the identity $mathcal{O}$.
$$underbrace{P+P+cdots+P}_{text{$t$ times}} = mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge.
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field are same then the discrete logarithm on this curves runs in linear time.
edited yesterday
Squeamish Ossifrage
22.3k132101
answered yesterday
kelalakakelalaka
8,78032351
$endgroup$
1
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
add a comment |
$begingroup$
The points on the Elliptic Curves are forming an additive group with the identity $mathcal{O}$, the point at infinity.
The scalar multiplication $k P$ this actually means adding $P$, $k$-times itself
$$kP=underbrace{P+P+cdots+P}_{text{$k$ times}}.$$
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
Point addition in $mathbb{Z}_p$ has an interesting property since the number of elements is finite if you add a point $P$ itself many times eventually you will get the identity $mathcal{O}$.
$$underbrace{P+P+cdots+P}_{text{$t$ times}} = mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge.
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field are same then the discrete logarithm on this curves runs in linear time.
edited yesterday
Squeamish Ossifrage
22.3k132101
answered yesterday
kelalakakelalaka
8,78032351
$endgroup$
The points on the Elliptic Curves are forming an additive group with the identity $mathcal{O}$, the point at infinity.
The scalar multiplication $k P$ this actually means adding $P$, $k$-times itself
$$kP=underbrace{P+P+cdots+P}_{text{$k$ times}}.$$
Bitcoin uses Secp256k1 which has characteristic $p$ and it is defined over the prime field $mathbb{Z}_p$ with the curve equation $y^2=x^3+7$.
Point addition in $mathbb{Z}_p$ has an interesting property since the number of elements is finite if you add a point $P$ itself many times eventually you will get the identity $mathcal{O}$.
$$underbrace{P+P+cdots+P}_{text{$t$ times}} = mathcal{O}$$
The smallest $t$ will be the order of the subgroup generated by the $P$. For security, we want this order huge.
Note 1: a point $P$ may not generate the whole group but it generates a cyclic subgroup.
Note 2: As pointed by SqueamishOssifrage, The Smart showed that if the order of the curve and order of the base field are same then the discrete logarithm on this curves runs in linear time.
edited yesterday
Squeamish Ossifrage
22.3k132101
answered yesterday
kelalakakelalaka
8,78032351
edited yesterday
Squeamish Ossifrage
22.3k132101
edited yesterday
Squeamish Ossifrage
22.3k132101
edited yesterday
Squeamish Ossifrage
22.3k132101
22.3k132101
answered yesterday
kelalakakelalaka
8,78032351
answered yesterday
kelalakakelalaka
8,78032351
answered yesterday
kelalakakelalaka
8,78032351
8,78032351
1
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
add a comment |
1
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
1
1
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
The order of the scalar ring is not the characteristic or order of the coordinate field. The orders are related, but are not the same except in cases that are trivially breakable as Nigel Smart showed.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
$begingroup$
@SqueamishOssifrage thanks and for the links.
$endgroup$
– kelalaka
yesterday
add a comment |
inherithandle is a new contributor. Be nice, and check out our Code of Conduct.
inherithandle is a new contributor. Be nice, and check out our Code of Conduct.
inherithandle is a new contributor. Be nice, and check out our Code of Conduct.
inherithandle is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68593%2fcan-you-tell-me-why-doing-scalar-multiplication-of-a-point-on-a-elliptic-curve-o%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
If you're interested in elliptic curve cryptography, you should maybe just get a book on elliptic curve cryptography in which the basic concepts of groups, elliptic curves, scalar multiplication, and the point at infinity will appear in the first act. If you're interested in cryptocurrency applications, you probably don't need to worry about elliptic curves in detail, and can just use higher-level ideas like signatures.
$endgroup$
– Squeamish Ossifrage
yesterday