{"id":1819,"date":"2022-02-12T23:18:55","date_gmt":"2022-02-12T23:18:55","guid":{"rendered":"http:\/\/www.ishygddt.xyz\/~blog\/?p=1819"},"modified":"2023-06-11T01:04:33","modified_gmt":"2023-06-11T06:04:33","slug":"x25519-original-specification","status":"publish","type":"post","link":"http:\/\/www.ishygddt.xyz\/~blog\/2022\/02\/x25519-original-specification","title":{"rendered":"X25519 original specification"},"content":{"rendered":"

Adapted from the original specification<\/a>:<\/p>\n

This section defines what is now known as<\/a> the X25519 function.<\/p>\n

Theorem 2.1<\/strong>: Let $p$<\/span> be a prime number with $p\\geq 5$<\/span>. Let $A$<\/span> be an integer such that $A^2 – 4$<\/span> is not a square modulo $p$<\/span>. Define $E$<\/span> as the elliptic curve $y^2=x^3+Ax^2+x$<\/span> over the field $\\mathbb{F}_p$<\/span>. Define $X_0:E\\left(\\mathbb{F}_{p^2}\\right)\\to\\mathbb{F}_{p^2}$<\/span> as follows: $X_0\\left(\\infty\\right)=0;X_0\\left(x,y\\right)=x$<\/span>. Let $n$<\/span> be an integer. Let $q$<\/span> be an element of $\\mathbb{F}_p$<\/span>. Then there exists a unique $s\\in\\mathbb{F}_p$<\/span> such that $X_0\\left(nQ\\right)=s$<\/span> for all $Q\\in E\\left(\\mathbb{F}_{p^2}\\right)$<\/span> such that $X_0\\left(Q\\right)=q$<\/span>.<\/p>\n

In particular, define $p$<\/span> as the prime $2^{255}-19$<\/span>. Define $\\mathbb{F}_p$<\/span> as the prime field $\\mathbb{Z}\/p=\\mathbb{Z}\/{(2^{255}-19})$<\/span>. Note that $2$<\/span> is not a square in $\\mathbb{F}_p$<\/span>; define $\\mathbb{F}_{p^2}$<\/span> as the field $\\left(\\mathbb{Z}\/{(2^{255}-19)}\\right){[\\sqrt{2}]}$<\/span>. Define $A=486662$<\/span>. Note that $486662^2-4$<\/span> is not a square in $\\mathbb{F}_p$<\/span>. Define $E$<\/span> as the elliptic curve $y^2=x^3+Ax^2+x$<\/span> over $\\mathbb{F}_p$<\/span>. Define a function $X_0: E\\left(\\mathbb{F}_{p^2}\\right)\\to\\mathbb{F}_{p^2}$<\/span> as follows: $X_0\\left(\\infty\\right)=0;X_0\\left(x,y\\right)=x$<\/span>. Define $E$<\/span> as the elliptic curve $y^2=x^3+Ax^2+x$<\/span> over $\\mathbb{F}_p$<\/span>. Define a function $X: E\\left(\\mathbb{F}_{p^2}\\right)\\to\\left\\{\\infty\\right\\}\\cup\\mathbb{F}_{p^2}$<\/span> as follows: $X\\left(\\infty\\right)=\\infty;X\\left(x,y\\right)=x$<\/span>.<\/p>\n

Given $n\\in 2^{254}+8\\left\\{0,1,2,3,\\ldots,2^{251}-1\\right\\}$<\/span> and $q\\in\\mathbb{F}_p$<\/span>, the $\\text{X25519}$<\/span> function produces $s$<\/span> in Theorem 2.1.<\/p>\n

Now $\\text{X25519}:\\left\\{\\text{X25519 secret keys}\\right\\}\\times\\left\\{\\text{X25519 public keys}\\right\\}\\to{\\{0,1,\\ldots 2^{8}-1\\}}^{32}$<\/span> is defined as follows. Fix $q\\in\\left\\{0,1,\\ldots,2^{256}-1\\right\\}$<\/span> and $n\\in 2^{254}+\\left\\{0,1,2,3,\\ldots,2^{251}-1\\right\\}$<\/span>. By Theorem 2.1, there is a unique integer $s\\in\\left\\{0,1,2,\\ldots,2^{255}-20\\right\\}$<\/span> with the following property: $s=X_0\\left(nQ\\right)$<\/span> for all $Q\\in E\\left(\\mathbb{F}_{p^2}\\right)$<\/span> such that $X_0\\left(Q\\right)=q\\text{ mod }2^{255}-19$<\/span>. Finally, $\\text{X25519}{(\\underline{n},\\underline{q})}$<\/span> is defined as $\\underline{s}$<\/span>. Note that $\\text{X25519}$<\/span> is not surjective: in particular, its final output bit is $0$<\/span> and need not be transmitted.<\/p><\/blockquote>\n

The author then proceeds to give some highly applied implementation details to do with bit twiddling algebraic polynomials, reductions around the CPU register size for constant-time arithmetic and whatnot\u2026 but, if my understanding is correct, the above quote contains the full specification of the function itself<\/strong>, if you have enough mathematical knowledge to wring it out of there (left, canonically, as an exercise for the reader; the paper excuses its terseness<\/a> by recommending some math textbooks).<\/p>\n

There have been some fantastic attempts [Martin Kleppman<\/a>; Bill Buchanan<\/a>] to bridge this gap and explain the core function<\/em> at a humanly-comprehensible level, but they, like the original paper, all jump straight from the mathematically pure high-level descriptions of \"point operations on generating curves\" to the extremely technical low-level \"scalar multiplications with montgomery ladders\", without ever taking a segue through \"just normal numbers\". If I cannot find such an explanation myself, I may have to learn the relevant mathematics and write<\/em> one.<\/p>\n

\n

Though, perhaps crafting such a document wouldn't be worth the investment: X25519 isn't quantum-safe, and what may be the best upcoming quantum-safe algorithm<\/a> (produced by\u2014among others<\/a>\u2014the very same gentleman that made X25519) has already got a fantastic explainer by Ashley Valentijn of Syracuse University<\/a>, published as her honors capstone project. Better, perhaps, to study up about that, instead.<\/p>\n","protected":false},"excerpt":{"rendered":"

Adapted from the original specification<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,101],"tags":[102,103],"class_list":["post-1819","post","type-post","status-publish","format-standard","hentry","category-drafts","category-writeups","tag-cryptography","tag-elliptic-curves"],"_links":{"self":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts\/1819","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/comments?post=1819"}],"version-history":[{"count":51,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts\/1819\/revisions"}],"predecessor-version":[{"id":2854,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/posts\/1819\/revisions\/2854"}],"wp:attachment":[{"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/media?parent=1819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/categories?post=1819"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.ishygddt.xyz\/~blog\/wp-json\/wp\/v2\/tags?post=1819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}