edwards25519.go 42 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793
  1. // Copyright 2016 The Go Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style
  3. // license that can be found in the LICENSE file.
  4. package edwards25519
  5. import "encoding/binary"
  6. // This code is a port of the public domain, “ref10” implementation of ed25519
  7. // from SUPERCOP.
  8. // FieldElement represents an element of the field GF(2^255 - 19). An element
  9. // t, entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77
  10. // t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on
  11. // context.
  12. type FieldElement [10]int32
  13. var zero FieldElement
  14. func FeZero(fe *FieldElement) {
  15. copy(fe[:], zero[:])
  16. }
  17. func FeOne(fe *FieldElement) {
  18. FeZero(fe)
  19. fe[0] = 1
  20. }
  21. func FeAdd(dst, a, b *FieldElement) {
  22. dst[0] = a[0] + b[0]
  23. dst[1] = a[1] + b[1]
  24. dst[2] = a[2] + b[2]
  25. dst[3] = a[3] + b[3]
  26. dst[4] = a[4] + b[4]
  27. dst[5] = a[5] + b[5]
  28. dst[6] = a[6] + b[6]
  29. dst[7] = a[7] + b[7]
  30. dst[8] = a[8] + b[8]
  31. dst[9] = a[9] + b[9]
  32. }
  33. func FeSub(dst, a, b *FieldElement) {
  34. dst[0] = a[0] - b[0]
  35. dst[1] = a[1] - b[1]
  36. dst[2] = a[2] - b[2]
  37. dst[3] = a[3] - b[3]
  38. dst[4] = a[4] - b[4]
  39. dst[5] = a[5] - b[5]
  40. dst[6] = a[6] - b[6]
  41. dst[7] = a[7] - b[7]
  42. dst[8] = a[8] - b[8]
  43. dst[9] = a[9] - b[9]
  44. }
  45. func FeCopy(dst, src *FieldElement) {
  46. copy(dst[:], src[:])
  47. }
  48. // Replace (f,g) with (g,g) if b == 1;
  49. // replace (f,g) with (f,g) if b == 0.
  50. //
  51. // Preconditions: b in {0,1}.
  52. func FeCMove(f, g *FieldElement, b int32) {
  53. b = -b
  54. f[0] ^= b & (f[0] ^ g[0])
  55. f[1] ^= b & (f[1] ^ g[1])
  56. f[2] ^= b & (f[2] ^ g[2])
  57. f[3] ^= b & (f[3] ^ g[3])
  58. f[4] ^= b & (f[4] ^ g[4])
  59. f[5] ^= b & (f[5] ^ g[5])
  60. f[6] ^= b & (f[6] ^ g[6])
  61. f[7] ^= b & (f[7] ^ g[7])
  62. f[8] ^= b & (f[8] ^ g[8])
  63. f[9] ^= b & (f[9] ^ g[9])
  64. }
  65. func load3(in []byte) int64 {
  66. var r int64
  67. r = int64(in[0])
  68. r |= int64(in[1]) << 8
  69. r |= int64(in[2]) << 16
  70. return r
  71. }
  72. func load4(in []byte) int64 {
  73. var r int64
  74. r = int64(in[0])
  75. r |= int64(in[1]) << 8
  76. r |= int64(in[2]) << 16
  77. r |= int64(in[3]) << 24
  78. return r
  79. }
  80. func FeFromBytes(dst *FieldElement, src *[32]byte) {
  81. h0 := load4(src[:])
  82. h1 := load3(src[4:]) << 6
  83. h2 := load3(src[7:]) << 5
  84. h3 := load3(src[10:]) << 3
  85. h4 := load3(src[13:]) << 2
  86. h5 := load4(src[16:])
  87. h6 := load3(src[20:]) << 7
  88. h7 := load3(src[23:]) << 5
  89. h8 := load3(src[26:]) << 4
  90. h9 := (load3(src[29:]) & 8388607) << 2
  91. FeCombine(dst, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
  92. }
  93. // FeToBytes marshals h to s.
  94. // Preconditions:
  95. // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
  96. //
  97. // Write p=2^255-19; q=floor(h/p).
  98. // Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
  99. //
  100. // Proof:
  101. // Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
  102. // Also have |h-2^230 h9|<2^230 so |19 2^(-255)(h-2^230 h9)|<1/4.
  103. //
  104. // Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
  105. // Then 0<y<1.
  106. //
  107. // Write r=h-pq.
  108. // Have 0<=r<=p-1=2^255-20.
  109. // Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
  110. //
  111. // Write x=r+19(2^-255)r+y.
  112. // Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
  113. //
  114. // Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
  115. // so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
  116. func FeToBytes(s *[32]byte, h *FieldElement) {
  117. var carry [10]int32
  118. q := (19*h[9] + (1 << 24)) >> 25
  119. q = (h[0] + q) >> 26
  120. q = (h[1] + q) >> 25
  121. q = (h[2] + q) >> 26
  122. q = (h[3] + q) >> 25
  123. q = (h[4] + q) >> 26
  124. q = (h[5] + q) >> 25
  125. q = (h[6] + q) >> 26
  126. q = (h[7] + q) >> 25
  127. q = (h[8] + q) >> 26
  128. q = (h[9] + q) >> 25
  129. // Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20.
  130. h[0] += 19 * q
  131. // Goal: Output h-2^255 q, which is between 0 and 2^255-20.
  132. carry[0] = h[0] >> 26
  133. h[1] += carry[0]
  134. h[0] -= carry[0] << 26
  135. carry[1] = h[1] >> 25
  136. h[2] += carry[1]
  137. h[1] -= carry[1] << 25
  138. carry[2] = h[2] >> 26
  139. h[3] += carry[2]
  140. h[2] -= carry[2] << 26
  141. carry[3] = h[3] >> 25
  142. h[4] += carry[3]
  143. h[3] -= carry[3] << 25
  144. carry[4] = h[4] >> 26
  145. h[5] += carry[4]
  146. h[4] -= carry[4] << 26
  147. carry[5] = h[5] >> 25
  148. h[6] += carry[5]
  149. h[5] -= carry[5] << 25
  150. carry[6] = h[6] >> 26
  151. h[7] += carry[6]
  152. h[6] -= carry[6] << 26
  153. carry[7] = h[7] >> 25
  154. h[8] += carry[7]
  155. h[7] -= carry[7] << 25
  156. carry[8] = h[8] >> 26
  157. h[9] += carry[8]
  158. h[8] -= carry[8] << 26
  159. carry[9] = h[9] >> 25
  160. h[9] -= carry[9] << 25
  161. // h10 = carry9
  162. // Goal: Output h[0]+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
  163. // Have h[0]+...+2^230 h[9] between 0 and 2^255-1;
  164. // evidently 2^255 h10-2^255 q = 0.
  165. // Goal: Output h[0]+...+2^230 h[9].
  166. s[0] = byte(h[0] >> 0)
  167. s[1] = byte(h[0] >> 8)
  168. s[2] = byte(h[0] >> 16)
  169. s[3] = byte((h[0] >> 24) | (h[1] << 2))
  170. s[4] = byte(h[1] >> 6)
  171. s[5] = byte(h[1] >> 14)
  172. s[6] = byte((h[1] >> 22) | (h[2] << 3))
  173. s[7] = byte(h[2] >> 5)
  174. s[8] = byte(h[2] >> 13)
  175. s[9] = byte((h[2] >> 21) | (h[3] << 5))
  176. s[10] = byte(h[3] >> 3)
  177. s[11] = byte(h[3] >> 11)
  178. s[12] = byte((h[3] >> 19) | (h[4] << 6))
  179. s[13] = byte(h[4] >> 2)
  180. s[14] = byte(h[4] >> 10)
  181. s[15] = byte(h[4] >> 18)
  182. s[16] = byte(h[5] >> 0)
  183. s[17] = byte(h[5] >> 8)
  184. s[18] = byte(h[5] >> 16)
  185. s[19] = byte((h[5] >> 24) | (h[6] << 1))
  186. s[20] = byte(h[6] >> 7)
  187. s[21] = byte(h[6] >> 15)
  188. s[22] = byte((h[6] >> 23) | (h[7] << 3))
  189. s[23] = byte(h[7] >> 5)
  190. s[24] = byte(h[7] >> 13)
  191. s[25] = byte((h[7] >> 21) | (h[8] << 4))
  192. s[26] = byte(h[8] >> 4)
  193. s[27] = byte(h[8] >> 12)
  194. s[28] = byte((h[8] >> 20) | (h[9] << 6))
  195. s[29] = byte(h[9] >> 2)
  196. s[30] = byte(h[9] >> 10)
  197. s[31] = byte(h[9] >> 18)
  198. }
  199. func FeIsNegative(f *FieldElement) byte {
  200. var s [32]byte
  201. FeToBytes(&s, f)
  202. return s[0] & 1
  203. }
  204. func FeIsNonZero(f *FieldElement) int32 {
  205. var s [32]byte
  206. FeToBytes(&s, f)
  207. var x uint8
  208. for _, b := range s {
  209. x |= b
  210. }
  211. x |= x >> 4
  212. x |= x >> 2
  213. x |= x >> 1
  214. return int32(x & 1)
  215. }
  216. // FeNeg sets h = -f
  217. //
  218. // Preconditions:
  219. // |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
  220. //
  221. // Postconditions:
  222. // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
  223. func FeNeg(h, f *FieldElement) {
  224. h[0] = -f[0]
  225. h[1] = -f[1]
  226. h[2] = -f[2]
  227. h[3] = -f[3]
  228. h[4] = -f[4]
  229. h[5] = -f[5]
  230. h[6] = -f[6]
  231. h[7] = -f[7]
  232. h[8] = -f[8]
  233. h[9] = -f[9]
  234. }
  235. func FeCombine(h *FieldElement, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64) {
  236. var c0, c1, c2, c3, c4, c5, c6, c7, c8, c9 int64
  237. /*
  238. |h0| <= (1.1*1.1*2^52*(1+19+19+19+19)+1.1*1.1*2^50*(38+38+38+38+38))
  239. i.e. |h0| <= 1.2*2^59; narrower ranges for h2, h4, h6, h8
  240. |h1| <= (1.1*1.1*2^51*(1+1+19+19+19+19+19+19+19+19))
  241. i.e. |h1| <= 1.5*2^58; narrower ranges for h3, h5, h7, h9
  242. */
  243. c0 = (h0 + (1 << 25)) >> 26
  244. h1 += c0
  245. h0 -= c0 << 26
  246. c4 = (h4 + (1 << 25)) >> 26
  247. h5 += c4
  248. h4 -= c4 << 26
  249. /* |h0| <= 2^25 */
  250. /* |h4| <= 2^25 */
  251. /* |h1| <= 1.51*2^58 */
  252. /* |h5| <= 1.51*2^58 */
  253. c1 = (h1 + (1 << 24)) >> 25
  254. h2 += c1
  255. h1 -= c1 << 25
  256. c5 = (h5 + (1 << 24)) >> 25
  257. h6 += c5
  258. h5 -= c5 << 25
  259. /* |h1| <= 2^24; from now on fits into int32 */
  260. /* |h5| <= 2^24; from now on fits into int32 */
  261. /* |h2| <= 1.21*2^59 */
  262. /* |h6| <= 1.21*2^59 */
  263. c2 = (h2 + (1 << 25)) >> 26
  264. h3 += c2
  265. h2 -= c2 << 26
  266. c6 = (h6 + (1 << 25)) >> 26
  267. h7 += c6
  268. h6 -= c6 << 26
  269. /* |h2| <= 2^25; from now on fits into int32 unchanged */
  270. /* |h6| <= 2^25; from now on fits into int32 unchanged */
  271. /* |h3| <= 1.51*2^58 */
  272. /* |h7| <= 1.51*2^58 */
  273. c3 = (h3 + (1 << 24)) >> 25
  274. h4 += c3
  275. h3 -= c3 << 25
  276. c7 = (h7 + (1 << 24)) >> 25
  277. h8 += c7
  278. h7 -= c7 << 25
  279. /* |h3| <= 2^24; from now on fits into int32 unchanged */
  280. /* |h7| <= 2^24; from now on fits into int32 unchanged */
  281. /* |h4| <= 1.52*2^33 */
  282. /* |h8| <= 1.52*2^33 */
  283. c4 = (h4 + (1 << 25)) >> 26
  284. h5 += c4
  285. h4 -= c4 << 26
  286. c8 = (h8 + (1 << 25)) >> 26
  287. h9 += c8
  288. h8 -= c8 << 26
  289. /* |h4| <= 2^25; from now on fits into int32 unchanged */
  290. /* |h8| <= 2^25; from now on fits into int32 unchanged */
  291. /* |h5| <= 1.01*2^24 */
  292. /* |h9| <= 1.51*2^58 */
  293. c9 = (h9 + (1 << 24)) >> 25
  294. h0 += c9 * 19
  295. h9 -= c9 << 25
  296. /* |h9| <= 2^24; from now on fits into int32 unchanged */
  297. /* |h0| <= 1.8*2^37 */
  298. c0 = (h0 + (1 << 25)) >> 26
  299. h1 += c0
  300. h0 -= c0 << 26
  301. /* |h0| <= 2^25; from now on fits into int32 unchanged */
  302. /* |h1| <= 1.01*2^24 */
  303. h[0] = int32(h0)
  304. h[1] = int32(h1)
  305. h[2] = int32(h2)
  306. h[3] = int32(h3)
  307. h[4] = int32(h4)
  308. h[5] = int32(h5)
  309. h[6] = int32(h6)
  310. h[7] = int32(h7)
  311. h[8] = int32(h8)
  312. h[9] = int32(h9)
  313. }
  314. // FeMul calculates h = f * g
  315. // Can overlap h with f or g.
  316. //
  317. // Preconditions:
  318. // |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
  319. // |g| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
  320. //
  321. // Postconditions:
  322. // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
  323. //
  324. // Notes on implementation strategy:
  325. //
  326. // Using schoolbook multiplication.
  327. // Karatsuba would save a little in some cost models.
  328. //
  329. // Most multiplications by 2 and 19 are 32-bit precomputations;
  330. // cheaper than 64-bit postcomputations.
  331. //
  332. // There is one remaining multiplication by 19 in the carry chain;
  333. // one *19 precomputation can be merged into this,
  334. // but the resulting data flow is considerably less clean.
  335. //
  336. // There are 12 carries below.
  337. // 10 of them are 2-way parallelizable and vectorizable.
  338. // Can get away with 11 carries, but then data flow is much deeper.
  339. //
  340. // With tighter constraints on inputs, can squeeze carries into int32.
  341. func FeMul(h, f, g *FieldElement) {
  342. f0 := int64(f[0])
  343. f1 := int64(f[1])
  344. f2 := int64(f[2])
  345. f3 := int64(f[3])
  346. f4 := int64(f[4])
  347. f5 := int64(f[5])
  348. f6 := int64(f[6])
  349. f7 := int64(f[7])
  350. f8 := int64(f[8])
  351. f9 := int64(f[9])
  352. f1_2 := int64(2 * f[1])
  353. f3_2 := int64(2 * f[3])
  354. f5_2 := int64(2 * f[5])
  355. f7_2 := int64(2 * f[7])
  356. f9_2 := int64(2 * f[9])
  357. g0 := int64(g[0])
  358. g1 := int64(g[1])
  359. g2 := int64(g[2])
  360. g3 := int64(g[3])
  361. g4 := int64(g[4])
  362. g5 := int64(g[5])
  363. g6 := int64(g[6])
  364. g7 := int64(g[7])
  365. g8 := int64(g[8])
  366. g9 := int64(g[9])
  367. g1_19 := int64(19 * g[1]) /* 1.4*2^29 */
  368. g2_19 := int64(19 * g[2]) /* 1.4*2^30; still ok */
  369. g3_19 := int64(19 * g[3])
  370. g4_19 := int64(19 * g[4])
  371. g5_19 := int64(19 * g[5])
  372. g6_19 := int64(19 * g[6])
  373. g7_19 := int64(19 * g[7])
  374. g8_19 := int64(19 * g[8])
  375. g9_19 := int64(19 * g[9])
  376. h0 := f0*g0 + f1_2*g9_19 + f2*g8_19 + f3_2*g7_19 + f4*g6_19 + f5_2*g5_19 + f6*g4_19 + f7_2*g3_19 + f8*g2_19 + f9_2*g1_19
  377. h1 := f0*g1 + f1*g0 + f2*g9_19 + f3*g8_19 + f4*g7_19 + f5*g6_19 + f6*g5_19 + f7*g4_19 + f8*g3_19 + f9*g2_19
  378. h2 := f0*g2 + f1_2*g1 + f2*g0 + f3_2*g9_19 + f4*g8_19 + f5_2*g7_19 + f6*g6_19 + f7_2*g5_19 + f8*g4_19 + f9_2*g3_19
  379. h3 := f0*g3 + f1*g2 + f2*g1 + f3*g0 + f4*g9_19 + f5*g8_19 + f6*g7_19 + f7*g6_19 + f8*g5_19 + f9*g4_19
  380. h4 := f0*g4 + f1_2*g3 + f2*g2 + f3_2*g1 + f4*g0 + f5_2*g9_19 + f6*g8_19 + f7_2*g7_19 + f8*g6_19 + f9_2*g5_19
  381. h5 := f0*g5 + f1*g4 + f2*g3 + f3*g2 + f4*g1 + f5*g0 + f6*g9_19 + f7*g8_19 + f8*g7_19 + f9*g6_19
  382. h6 := f0*g6 + f1_2*g5 + f2*g4 + f3_2*g3 + f4*g2 + f5_2*g1 + f6*g0 + f7_2*g9_19 + f8*g8_19 + f9_2*g7_19
  383. h7 := f0*g7 + f1*g6 + f2*g5 + f3*g4 + f4*g3 + f5*g2 + f6*g1 + f7*g0 + f8*g9_19 + f9*g8_19
  384. h8 := f0*g8 + f1_2*g7 + f2*g6 + f3_2*g5 + f4*g4 + f5_2*g3 + f6*g2 + f7_2*g1 + f8*g0 + f9_2*g9_19
  385. h9 := f0*g9 + f1*g8 + f2*g7 + f3*g6 + f4*g5 + f5*g4 + f6*g3 + f7*g2 + f8*g1 + f9*g0
  386. FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
  387. }
  388. func feSquare(f *FieldElement) (h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64) {
  389. f0 := int64(f[0])
  390. f1 := int64(f[1])
  391. f2 := int64(f[2])
  392. f3 := int64(f[3])
  393. f4 := int64(f[4])
  394. f5 := int64(f[5])
  395. f6 := int64(f[6])
  396. f7 := int64(f[7])
  397. f8 := int64(f[8])
  398. f9 := int64(f[9])
  399. f0_2 := int64(2 * f[0])
  400. f1_2 := int64(2 * f[1])
  401. f2_2 := int64(2 * f[2])
  402. f3_2 := int64(2 * f[3])
  403. f4_2 := int64(2 * f[4])
  404. f5_2 := int64(2 * f[5])
  405. f6_2 := int64(2 * f[6])
  406. f7_2 := int64(2 * f[7])
  407. f5_38 := 38 * f5 // 1.31*2^30
  408. f6_19 := 19 * f6 // 1.31*2^30
  409. f7_38 := 38 * f7 // 1.31*2^30
  410. f8_19 := 19 * f8 // 1.31*2^30
  411. f9_38 := 38 * f9 // 1.31*2^30
  412. h0 = f0*f0 + f1_2*f9_38 + f2_2*f8_19 + f3_2*f7_38 + f4_2*f6_19 + f5*f5_38
  413. h1 = f0_2*f1 + f2*f9_38 + f3_2*f8_19 + f4*f7_38 + f5_2*f6_19
  414. h2 = f0_2*f2 + f1_2*f1 + f3_2*f9_38 + f4_2*f8_19 + f5_2*f7_38 + f6*f6_19
  415. h3 = f0_2*f3 + f1_2*f2 + f4*f9_38 + f5_2*f8_19 + f6*f7_38
  416. h4 = f0_2*f4 + f1_2*f3_2 + f2*f2 + f5_2*f9_38 + f6_2*f8_19 + f7*f7_38
  417. h5 = f0_2*f5 + f1_2*f4 + f2_2*f3 + f6*f9_38 + f7_2*f8_19
  418. h6 = f0_2*f6 + f1_2*f5_2 + f2_2*f4 + f3_2*f3 + f7_2*f9_38 + f8*f8_19
  419. h7 = f0_2*f7 + f1_2*f6 + f2_2*f5 + f3_2*f4 + f8*f9_38
  420. h8 = f0_2*f8 + f1_2*f7_2 + f2_2*f6 + f3_2*f5_2 + f4*f4 + f9*f9_38
  421. h9 = f0_2*f9 + f1_2*f8 + f2_2*f7 + f3_2*f6 + f4_2*f5
  422. return
  423. }
  424. // FeSquare calculates h = f*f. Can overlap h with f.
  425. //
  426. // Preconditions:
  427. // |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
  428. //
  429. // Postconditions:
  430. // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
  431. func FeSquare(h, f *FieldElement) {
  432. h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 := feSquare(f)
  433. FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
  434. }
  435. // FeSquare2 sets h = 2 * f * f
  436. //
  437. // Can overlap h with f.
  438. //
  439. // Preconditions:
  440. // |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
  441. //
  442. // Postconditions:
  443. // |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
  444. // See fe_mul.c for discussion of implementation strategy.
  445. func FeSquare2(h, f *FieldElement) {
  446. h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 := feSquare(f)
  447. h0 += h0
  448. h1 += h1
  449. h2 += h2
  450. h3 += h3
  451. h4 += h4
  452. h5 += h5
  453. h6 += h6
  454. h7 += h7
  455. h8 += h8
  456. h9 += h9
  457. FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
  458. }
  459. func FeInvert(out, z *FieldElement) {
  460. var t0, t1, t2, t3 FieldElement
  461. var i int
  462. FeSquare(&t0, z) // 2^1
  463. FeSquare(&t1, &t0) // 2^2
  464. for i = 1; i < 2; i++ { // 2^3
  465. FeSquare(&t1, &t1)
  466. }
  467. FeMul(&t1, z, &t1) // 2^3 + 2^0
  468. FeMul(&t0, &t0, &t1) // 2^3 + 2^1 + 2^0
  469. FeSquare(&t2, &t0) // 2^4 + 2^2 + 2^1
  470. FeMul(&t1, &t1, &t2) // 2^4 + 2^3 + 2^2 + 2^1 + 2^0
  471. FeSquare(&t2, &t1) // 5,4,3,2,1
  472. for i = 1; i < 5; i++ { // 9,8,7,6,5
  473. FeSquare(&t2, &t2)
  474. }
  475. FeMul(&t1, &t2, &t1) // 9,8,7,6,5,4,3,2,1,0
  476. FeSquare(&t2, &t1) // 10..1
  477. for i = 1; i < 10; i++ { // 19..10
  478. FeSquare(&t2, &t2)
  479. }
  480. FeMul(&t2, &t2, &t1) // 19..0
  481. FeSquare(&t3, &t2) // 20..1
  482. for i = 1; i < 20; i++ { // 39..20
  483. FeSquare(&t3, &t3)
  484. }
  485. FeMul(&t2, &t3, &t2) // 39..0
  486. FeSquare(&t2, &t2) // 40..1
  487. for i = 1; i < 10; i++ { // 49..10
  488. FeSquare(&t2, &t2)
  489. }
  490. FeMul(&t1, &t2, &t1) // 49..0
  491. FeSquare(&t2, &t1) // 50..1
  492. for i = 1; i < 50; i++ { // 99..50
  493. FeSquare(&t2, &t2)
  494. }
  495. FeMul(&t2, &t2, &t1) // 99..0
  496. FeSquare(&t3, &t2) // 100..1
  497. for i = 1; i < 100; i++ { // 199..100
  498. FeSquare(&t3, &t3)
  499. }
  500. FeMul(&t2, &t3, &t2) // 199..0
  501. FeSquare(&t2, &t2) // 200..1
  502. for i = 1; i < 50; i++ { // 249..50
  503. FeSquare(&t2, &t2)
  504. }
  505. FeMul(&t1, &t2, &t1) // 249..0
  506. FeSquare(&t1, &t1) // 250..1
  507. for i = 1; i < 5; i++ { // 254..5
  508. FeSquare(&t1, &t1)
  509. }
  510. FeMul(out, &t1, &t0) // 254..5,3,1,0
  511. }
  512. func fePow22523(out, z *FieldElement) {
  513. var t0, t1, t2 FieldElement
  514. var i int
  515. FeSquare(&t0, z)
  516. for i = 1; i < 1; i++ {
  517. FeSquare(&t0, &t0)
  518. }
  519. FeSquare(&t1, &t0)
  520. for i = 1; i < 2; i++ {
  521. FeSquare(&t1, &t1)
  522. }
  523. FeMul(&t1, z, &t1)
  524. FeMul(&t0, &t0, &t1)
  525. FeSquare(&t0, &t0)
  526. for i = 1; i < 1; i++ {
  527. FeSquare(&t0, &t0)
  528. }
  529. FeMul(&t0, &t1, &t0)
  530. FeSquare(&t1, &t0)
  531. for i = 1; i < 5; i++ {
  532. FeSquare(&t1, &t1)
  533. }
  534. FeMul(&t0, &t1, &t0)
  535. FeSquare(&t1, &t0)
  536. for i = 1; i < 10; i++ {
  537. FeSquare(&t1, &t1)
  538. }
  539. FeMul(&t1, &t1, &t0)
  540. FeSquare(&t2, &t1)
  541. for i = 1; i < 20; i++ {
  542. FeSquare(&t2, &t2)
  543. }
  544. FeMul(&t1, &t2, &t1)
  545. FeSquare(&t1, &t1)
  546. for i = 1; i < 10; i++ {
  547. FeSquare(&t1, &t1)
  548. }
  549. FeMul(&t0, &t1, &t0)
  550. FeSquare(&t1, &t0)
  551. for i = 1; i < 50; i++ {
  552. FeSquare(&t1, &t1)
  553. }
  554. FeMul(&t1, &t1, &t0)
  555. FeSquare(&t2, &t1)
  556. for i = 1; i < 100; i++ {
  557. FeSquare(&t2, &t2)
  558. }
  559. FeMul(&t1, &t2, &t1)
  560. FeSquare(&t1, &t1)
  561. for i = 1; i < 50; i++ {
  562. FeSquare(&t1, &t1)
  563. }
  564. FeMul(&t0, &t1, &t0)
  565. FeSquare(&t0, &t0)
  566. for i = 1; i < 2; i++ {
  567. FeSquare(&t0, &t0)
  568. }
  569. FeMul(out, &t0, z)
  570. }
  571. // Group elements are members of the elliptic curve -x^2 + y^2 = 1 + d * x^2 *
  572. // y^2 where d = -121665/121666.
  573. //
  574. // Several representations are used:
  575. // ProjectiveGroupElement: (X:Y:Z) satisfying x=X/Z, y=Y/Z
  576. // ExtendedGroupElement: (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
  577. // CompletedGroupElement: ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T
  578. // PreComputedGroupElement: (y+x,y-x,2dxy)
  579. type ProjectiveGroupElement struct {
  580. X, Y, Z FieldElement
  581. }
  582. type ExtendedGroupElement struct {
  583. X, Y, Z, T FieldElement
  584. }
  585. type CompletedGroupElement struct {
  586. X, Y, Z, T FieldElement
  587. }
  588. type PreComputedGroupElement struct {
  589. yPlusX, yMinusX, xy2d FieldElement
  590. }
  591. type CachedGroupElement struct {
  592. yPlusX, yMinusX, Z, T2d FieldElement
  593. }
  594. func (p *ProjectiveGroupElement) Zero() {
  595. FeZero(&p.X)
  596. FeOne(&p.Y)
  597. FeOne(&p.Z)
  598. }
  599. func (p *ProjectiveGroupElement) Double(r *CompletedGroupElement) {
  600. var t0 FieldElement
  601. FeSquare(&r.X, &p.X)
  602. FeSquare(&r.Z, &p.Y)
  603. FeSquare2(&r.T, &p.Z)
  604. FeAdd(&r.Y, &p.X, &p.Y)
  605. FeSquare(&t0, &r.Y)
  606. FeAdd(&r.Y, &r.Z, &r.X)
  607. FeSub(&r.Z, &r.Z, &r.X)
  608. FeSub(&r.X, &t0, &r.Y)
  609. FeSub(&r.T, &r.T, &r.Z)
  610. }
  611. func (p *ProjectiveGroupElement) ToBytes(s *[32]byte) {
  612. var recip, x, y FieldElement
  613. FeInvert(&recip, &p.Z)
  614. FeMul(&x, &p.X, &recip)
  615. FeMul(&y, &p.Y, &recip)
  616. FeToBytes(s, &y)
  617. s[31] ^= FeIsNegative(&x) << 7
  618. }
  619. func (p *ExtendedGroupElement) Zero() {
  620. FeZero(&p.X)
  621. FeOne(&p.Y)
  622. FeOne(&p.Z)
  623. FeZero(&p.T)
  624. }
  625. func (p *ExtendedGroupElement) Double(r *CompletedGroupElement) {
  626. var q ProjectiveGroupElement
  627. p.ToProjective(&q)
  628. q.Double(r)
  629. }
  630. func (p *ExtendedGroupElement) ToCached(r *CachedGroupElement) {
  631. FeAdd(&r.yPlusX, &p.Y, &p.X)
  632. FeSub(&r.yMinusX, &p.Y, &p.X)
  633. FeCopy(&r.Z, &p.Z)
  634. FeMul(&r.T2d, &p.T, &d2)
  635. }
  636. func (p *ExtendedGroupElement) ToProjective(r *ProjectiveGroupElement) {
  637. FeCopy(&r.X, &p.X)
  638. FeCopy(&r.Y, &p.Y)
  639. FeCopy(&r.Z, &p.Z)
  640. }
  641. func (p *ExtendedGroupElement) ToBytes(s *[32]byte) {
  642. var recip, x, y FieldElement
  643. FeInvert(&recip, &p.Z)
  644. FeMul(&x, &p.X, &recip)
  645. FeMul(&y, &p.Y, &recip)
  646. FeToBytes(s, &y)
  647. s[31] ^= FeIsNegative(&x) << 7
  648. }
  649. func (p *ExtendedGroupElement) FromBytes(s *[32]byte) bool {
  650. var u, v, v3, vxx, check FieldElement
  651. FeFromBytes(&p.Y, s)
  652. FeOne(&p.Z)
  653. FeSquare(&u, &p.Y)
  654. FeMul(&v, &u, &d)
  655. FeSub(&u, &u, &p.Z) // y = y^2-1
  656. FeAdd(&v, &v, &p.Z) // v = dy^2+1
  657. FeSquare(&v3, &v)
  658. FeMul(&v3, &v3, &v) // v3 = v^3
  659. FeSquare(&p.X, &v3)
  660. FeMul(&p.X, &p.X, &v)
  661. FeMul(&p.X, &p.X, &u) // x = uv^7
  662. fePow22523(&p.X, &p.X) // x = (uv^7)^((q-5)/8)
  663. FeMul(&p.X, &p.X, &v3)
  664. FeMul(&p.X, &p.X, &u) // x = uv^3(uv^7)^((q-5)/8)
  665. var tmpX, tmp2 [32]byte
  666. FeSquare(&vxx, &p.X)
  667. FeMul(&vxx, &vxx, &v)
  668. FeSub(&check, &vxx, &u) // vx^2-u
  669. if FeIsNonZero(&check) == 1 {
  670. FeAdd(&check, &vxx, &u) // vx^2+u
  671. if FeIsNonZero(&check) == 1 {
  672. return false
  673. }
  674. FeMul(&p.X, &p.X, &SqrtM1)
  675. FeToBytes(&tmpX, &p.X)
  676. for i, v := range tmpX {
  677. tmp2[31-i] = v
  678. }
  679. }
  680. if FeIsNegative(&p.X) != (s[31] >> 7) {
  681. FeNeg(&p.X, &p.X)
  682. }
  683. FeMul(&p.T, &p.X, &p.Y)
  684. return true
  685. }
  686. func (p *CompletedGroupElement) ToProjective(r *ProjectiveGroupElement) {
  687. FeMul(&r.X, &p.X, &p.T)
  688. FeMul(&r.Y, &p.Y, &p.Z)
  689. FeMul(&r.Z, &p.Z, &p.T)
  690. }
  691. func (p *CompletedGroupElement) ToExtended(r *ExtendedGroupElement) {
  692. FeMul(&r.X, &p.X, &p.T)
  693. FeMul(&r.Y, &p.Y, &p.Z)
  694. FeMul(&r.Z, &p.Z, &p.T)
  695. FeMul(&r.T, &p.X, &p.Y)
  696. }
  697. func (p *PreComputedGroupElement) Zero() {
  698. FeOne(&p.yPlusX)
  699. FeOne(&p.yMinusX)
  700. FeZero(&p.xy2d)
  701. }
  702. func geAdd(r *CompletedGroupElement, p *ExtendedGroupElement, q *CachedGroupElement) {
  703. var t0 FieldElement
  704. FeAdd(&r.X, &p.Y, &p.X)
  705. FeSub(&r.Y, &p.Y, &p.X)
  706. FeMul(&r.Z, &r.X, &q.yPlusX)
  707. FeMul(&r.Y, &r.Y, &q.yMinusX)
  708. FeMul(&r.T, &q.T2d, &p.T)
  709. FeMul(&r.X, &p.Z, &q.Z)
  710. FeAdd(&t0, &r.X, &r.X)
  711. FeSub(&r.X, &r.Z, &r.Y)
  712. FeAdd(&r.Y, &r.Z, &r.Y)
  713. FeAdd(&r.Z, &t0, &r.T)
  714. FeSub(&r.T, &t0, &r.T)
  715. }
  716. func geSub(r *CompletedGroupElement, p *ExtendedGroupElement, q *CachedGroupElement) {
  717. var t0 FieldElement
  718. FeAdd(&r.X, &p.Y, &p.X)
  719. FeSub(&r.Y, &p.Y, &p.X)
  720. FeMul(&r.Z, &r.X, &q.yMinusX)
  721. FeMul(&r.Y, &r.Y, &q.yPlusX)
  722. FeMul(&r.T, &q.T2d, &p.T)
  723. FeMul(&r.X, &p.Z, &q.Z)
  724. FeAdd(&t0, &r.X, &r.X)
  725. FeSub(&r.X, &r.Z, &r.Y)
  726. FeAdd(&r.Y, &r.Z, &r.Y)
  727. FeSub(&r.Z, &t0, &r.T)
  728. FeAdd(&r.T, &t0, &r.T)
  729. }
  730. func geMixedAdd(r *CompletedGroupElement, p *ExtendedGroupElement, q *PreComputedGroupElement) {
  731. var t0 FieldElement
  732. FeAdd(&r.X, &p.Y, &p.X)
  733. FeSub(&r.Y, &p.Y, &p.X)
  734. FeMul(&r.Z, &r.X, &q.yPlusX)
  735. FeMul(&r.Y, &r.Y, &q.yMinusX)
  736. FeMul(&r.T, &q.xy2d, &p.T)
  737. FeAdd(&t0, &p.Z, &p.Z)
  738. FeSub(&r.X, &r.Z, &r.Y)
  739. FeAdd(&r.Y, &r.Z, &r.Y)
  740. FeAdd(&r.Z, &t0, &r.T)
  741. FeSub(&r.T, &t0, &r.T)
  742. }
  743. func geMixedSub(r *CompletedGroupElement, p *ExtendedGroupElement, q *PreComputedGroupElement) {
  744. var t0 FieldElement
  745. FeAdd(&r.X, &p.Y, &p.X)
  746. FeSub(&r.Y, &p.Y, &p.X)
  747. FeMul(&r.Z, &r.X, &q.yMinusX)
  748. FeMul(&r.Y, &r.Y, &q.yPlusX)
  749. FeMul(&r.T, &q.xy2d, &p.T)
  750. FeAdd(&t0, &p.Z, &p.Z)
  751. FeSub(&r.X, &r.Z, &r.Y)
  752. FeAdd(&r.Y, &r.Z, &r.Y)
  753. FeSub(&r.Z, &t0, &r.T)
  754. FeAdd(&r.T, &t0, &r.T)
  755. }
  756. func slide(r *[256]int8, a *[32]byte) {
  757. for i := range r {
  758. r[i] = int8(1 & (a[i>>3] >> uint(i&7)))
  759. }
  760. for i := range r {
  761. if r[i] != 0 {
  762. for b := 1; b <= 6 && i+b < 256; b++ {
  763. if r[i+b] != 0 {
  764. if r[i]+(r[i+b]<<uint(b)) <= 15 {
  765. r[i] += r[i+b] << uint(b)
  766. r[i+b] = 0
  767. } else if r[i]-(r[i+b]<<uint(b)) >= -15 {
  768. r[i] -= r[i+b] << uint(b)
  769. for k := i + b; k < 256; k++ {
  770. if r[k] == 0 {
  771. r[k] = 1
  772. break
  773. }
  774. r[k] = 0
  775. }
  776. } else {
  777. break
  778. }
  779. }
  780. }
  781. }
  782. }
  783. }
  784. // GeDoubleScalarMultVartime sets r = a*A + b*B
  785. // where a = a[0]+256*a[1]+...+256^31 a[31].
  786. // and b = b[0]+256*b[1]+...+256^31 b[31].
  787. // B is the Ed25519 base point (x,4/5) with x positive.
  788. func GeDoubleScalarMultVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte) {
  789. var aSlide, bSlide [256]int8
  790. var Ai [8]CachedGroupElement // A,3A,5A,7A,9A,11A,13A,15A
  791. var t CompletedGroupElement
  792. var u, A2 ExtendedGroupElement
  793. var i int
  794. slide(&aSlide, a)
  795. slide(&bSlide, b)
  796. A.ToCached(&Ai[0])
  797. A.Double(&t)
  798. t.ToExtended(&A2)
  799. for i := 0; i < 7; i++ {
  800. geAdd(&t, &A2, &Ai[i])
  801. t.ToExtended(&u)
  802. u.ToCached(&Ai[i+1])
  803. }
  804. r.Zero()
  805. for i = 255; i >= 0; i-- {
  806. if aSlide[i] != 0 || bSlide[i] != 0 {
  807. break
  808. }
  809. }
  810. for ; i >= 0; i-- {
  811. r.Double(&t)
  812. if aSlide[i] > 0 {
  813. t.ToExtended(&u)
  814. geAdd(&t, &u, &Ai[aSlide[i]/2])
  815. } else if aSlide[i] < 0 {
  816. t.ToExtended(&u)
  817. geSub(&t, &u, &Ai[(-aSlide[i])/2])
  818. }
  819. if bSlide[i] > 0 {
  820. t.ToExtended(&u)
  821. geMixedAdd(&t, &u, &bi[bSlide[i]/2])
  822. } else if bSlide[i] < 0 {
  823. t.ToExtended(&u)
  824. geMixedSub(&t, &u, &bi[(-bSlide[i])/2])
  825. }
  826. t.ToProjective(r)
  827. }
  828. }
  829. // equal returns 1 if b == c and 0 otherwise, assuming that b and c are
  830. // non-negative.
  831. func equal(b, c int32) int32 {
  832. x := uint32(b ^ c)
  833. x--
  834. return int32(x >> 31)
  835. }
  836. // negative returns 1 if b < 0 and 0 otherwise.
  837. func negative(b int32) int32 {
  838. return (b >> 31) & 1
  839. }
  840. func PreComputedGroupElementCMove(t, u *PreComputedGroupElement, b int32) {
  841. FeCMove(&t.yPlusX, &u.yPlusX, b)
  842. FeCMove(&t.yMinusX, &u.yMinusX, b)
  843. FeCMove(&t.xy2d, &u.xy2d, b)
  844. }
  845. func selectPoint(t *PreComputedGroupElement, pos int32, b int32) {
  846. var minusT PreComputedGroupElement
  847. bNegative := negative(b)
  848. bAbs := b - (((-bNegative) & b) << 1)
  849. t.Zero()
  850. for i := int32(0); i < 8; i++ {
  851. PreComputedGroupElementCMove(t, &base[pos][i], equal(bAbs, i+1))
  852. }
  853. FeCopy(&minusT.yPlusX, &t.yMinusX)
  854. FeCopy(&minusT.yMinusX, &t.yPlusX)
  855. FeNeg(&minusT.xy2d, &t.xy2d)
  856. PreComputedGroupElementCMove(t, &minusT, bNegative)
  857. }
  858. // GeScalarMultBase computes h = a*B, where
  859. // a = a[0]+256*a[1]+...+256^31 a[31]
  860. // B is the Ed25519 base point (x,4/5) with x positive.
  861. //
  862. // Preconditions:
  863. // a[31] <= 127
  864. func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte) {
  865. var e [64]int8
  866. for i, v := range a {
  867. e[2*i] = int8(v & 15)
  868. e[2*i+1] = int8((v >> 4) & 15)
  869. }
  870. // each e[i] is between 0 and 15 and e[63] is between 0 and 7.
  871. carry := int8(0)
  872. for i := 0; i < 63; i++ {
  873. e[i] += carry
  874. carry = (e[i] + 8) >> 4
  875. e[i] -= carry << 4
  876. }
  877. e[63] += carry
  878. // each e[i] is between -8 and 8.
  879. h.Zero()
  880. var t PreComputedGroupElement
  881. var r CompletedGroupElement
  882. for i := int32(1); i < 64; i += 2 {
  883. selectPoint(&t, i/2, int32(e[i]))
  884. geMixedAdd(&r, h, &t)
  885. r.ToExtended(h)
  886. }
  887. var s ProjectiveGroupElement
  888. h.Double(&r)
  889. r.ToProjective(&s)
  890. s.Double(&r)
  891. r.ToProjective(&s)
  892. s.Double(&r)
  893. r.ToProjective(&s)
  894. s.Double(&r)
  895. r.ToExtended(h)
  896. for i := int32(0); i < 64; i += 2 {
  897. selectPoint(&t, i/2, int32(e[i]))
  898. geMixedAdd(&r, h, &t)
  899. r.ToExtended(h)
  900. }
  901. }
  902. // The scalars are GF(2^252 + 27742317777372353535851937790883648493).
  903. // Input:
  904. // a[0]+256*a[1]+...+256^31*a[31] = a
  905. // b[0]+256*b[1]+...+256^31*b[31] = b
  906. // c[0]+256*c[1]+...+256^31*c[31] = c
  907. //
  908. // Output:
  909. // s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
  910. // where l = 2^252 + 27742317777372353535851937790883648493.
  911. func ScMulAdd(s, a, b, c *[32]byte) {
  912. a0 := 2097151 & load3(a[:])
  913. a1 := 2097151 & (load4(a[2:]) >> 5)
  914. a2 := 2097151 & (load3(a[5:]) >> 2)
  915. a3 := 2097151 & (load4(a[7:]) >> 7)
  916. a4 := 2097151 & (load4(a[10:]) >> 4)
  917. a5 := 2097151 & (load3(a[13:]) >> 1)
  918. a6 := 2097151 & (load4(a[15:]) >> 6)
  919. a7 := 2097151 & (load3(a[18:]) >> 3)
  920. a8 := 2097151 & load3(a[21:])
  921. a9 := 2097151 & (load4(a[23:]) >> 5)
  922. a10 := 2097151 & (load3(a[26:]) >> 2)
  923. a11 := (load4(a[28:]) >> 7)
  924. b0 := 2097151 & load3(b[:])
  925. b1 := 2097151 & (load4(b[2:]) >> 5)
  926. b2 := 2097151 & (load3(b[5:]) >> 2)
  927. b3 := 2097151 & (load4(b[7:]) >> 7)
  928. b4 := 2097151 & (load4(b[10:]) >> 4)
  929. b5 := 2097151 & (load3(b[13:]) >> 1)
  930. b6 := 2097151 & (load4(b[15:]) >> 6)
  931. b7 := 2097151 & (load3(b[18:]) >> 3)
  932. b8 := 2097151 & load3(b[21:])
  933. b9 := 2097151 & (load4(b[23:]) >> 5)
  934. b10 := 2097151 & (load3(b[26:]) >> 2)
  935. b11 := (load4(b[28:]) >> 7)
  936. c0 := 2097151 & load3(c[:])
  937. c1 := 2097151 & (load4(c[2:]) >> 5)
  938. c2 := 2097151 & (load3(c[5:]) >> 2)
  939. c3 := 2097151 & (load4(c[7:]) >> 7)
  940. c4 := 2097151 & (load4(c[10:]) >> 4)
  941. c5 := 2097151 & (load3(c[13:]) >> 1)
  942. c6 := 2097151 & (load4(c[15:]) >> 6)
  943. c7 := 2097151 & (load3(c[18:]) >> 3)
  944. c8 := 2097151 & load3(c[21:])
  945. c9 := 2097151 & (load4(c[23:]) >> 5)
  946. c10 := 2097151 & (load3(c[26:]) >> 2)
  947. c11 := (load4(c[28:]) >> 7)
  948. var carry [23]int64
  949. s0 := c0 + a0*b0
  950. s1 := c1 + a0*b1 + a1*b0
  951. s2 := c2 + a0*b2 + a1*b1 + a2*b0
  952. s3 := c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0
  953. s4 := c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0
  954. s5 := c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0
  955. s6 := c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0
  956. s7 := c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0
  957. s8 := c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0
  958. s9 := c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0
  959. s10 := c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0
  960. s11 := c11 + a0*b11 + a1*b10 + a2*b9 + a3*b8 + a4*b7 + a5*b6 + a6*b5 + a7*b4 + a8*b3 + a9*b2 + a10*b1 + a11*b0
  961. s12 := a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1
  962. s13 := a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2
  963. s14 := a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3
  964. s15 := a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4
  965. s16 := a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5
  966. s17 := a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6
  967. s18 := a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7
  968. s19 := a8*b11 + a9*b10 + a10*b9 + a11*b8
  969. s20 := a9*b11 + a10*b10 + a11*b9
  970. s21 := a10*b11 + a11*b10
  971. s22 := a11 * b11
  972. s23 := int64(0)
  973. carry[0] = (s0 + (1 << 20)) >> 21
  974. s1 += carry[0]
  975. s0 -= carry[0] << 21
  976. carry[2] = (s2 + (1 << 20)) >> 21
  977. s3 += carry[2]
  978. s2 -= carry[2] << 21
  979. carry[4] = (s4 + (1 << 20)) >> 21
  980. s5 += carry[4]
  981. s4 -= carry[4] << 21
  982. carry[6] = (s6 + (1 << 20)) >> 21
  983. s7 += carry[6]
  984. s6 -= carry[6] << 21
  985. carry[8] = (s8 + (1 << 20)) >> 21
  986. s9 += carry[8]
  987. s8 -= carry[8] << 21
  988. carry[10] = (s10 + (1 << 20)) >> 21
  989. s11 += carry[10]
  990. s10 -= carry[10] << 21
  991. carry[12] = (s12 + (1 << 20)) >> 21
  992. s13 += carry[12]
  993. s12 -= carry[12] << 21
  994. carry[14] = (s14 + (1 << 20)) >> 21
  995. s15 += carry[14]
  996. s14 -= carry[14] << 21
  997. carry[16] = (s16 + (1 << 20)) >> 21
  998. s17 += carry[16]
  999. s16 -= carry[16] << 21
  1000. carry[18] = (s18 + (1 << 20)) >> 21
  1001. s19 += carry[18]
  1002. s18 -= carry[18] << 21
  1003. carry[20] = (s20 + (1 << 20)) >> 21
  1004. s21 += carry[20]
  1005. s20 -= carry[20] << 21
  1006. carry[22] = (s22 + (1 << 20)) >> 21
  1007. s23 += carry[22]
  1008. s22 -= carry[22] << 21
  1009. carry[1] = (s1 + (1 << 20)) >> 21
  1010. s2 += carry[1]
  1011. s1 -= carry[1] << 21
  1012. carry[3] = (s3 + (1 << 20)) >> 21
  1013. s4 += carry[3]
  1014. s3 -= carry[3] << 21
  1015. carry[5] = (s5 + (1 << 20)) >> 21
  1016. s6 += carry[5]
  1017. s5 -= carry[5] << 21
  1018. carry[7] = (s7 + (1 << 20)) >> 21
  1019. s8 += carry[7]
  1020. s7 -= carry[7] << 21
  1021. carry[9] = (s9 + (1 << 20)) >> 21
  1022. s10 += carry[9]
  1023. s9 -= carry[9] << 21
  1024. carry[11] = (s11 + (1 << 20)) >> 21
  1025. s12 += carry[11]
  1026. s11 -= carry[11] << 21
  1027. carry[13] = (s13 + (1 << 20)) >> 21
  1028. s14 += carry[13]
  1029. s13 -= carry[13] << 21
  1030. carry[15] = (s15 + (1 << 20)) >> 21
  1031. s16 += carry[15]
  1032. s15 -= carry[15] << 21
  1033. carry[17] = (s17 + (1 << 20)) >> 21
  1034. s18 += carry[17]
  1035. s17 -= carry[17] << 21
  1036. carry[19] = (s19 + (1 << 20)) >> 21
  1037. s20 += carry[19]
  1038. s19 -= carry[19] << 21
  1039. carry[21] = (s21 + (1 << 20)) >> 21
  1040. s22 += carry[21]
  1041. s21 -= carry[21] << 21
  1042. s11 += s23 * 666643
  1043. s12 += s23 * 470296
  1044. s13 += s23 * 654183
  1045. s14 -= s23 * 997805
  1046. s15 += s23 * 136657
  1047. s16 -= s23 * 683901
  1048. s23 = 0
  1049. s10 += s22 * 666643
  1050. s11 += s22 * 470296
  1051. s12 += s22 * 654183
  1052. s13 -= s22 * 997805
  1053. s14 += s22 * 136657
  1054. s15 -= s22 * 683901
  1055. s22 = 0
  1056. s9 += s21 * 666643
  1057. s10 += s21 * 470296
  1058. s11 += s21 * 654183
  1059. s12 -= s21 * 997805
  1060. s13 += s21 * 136657
  1061. s14 -= s21 * 683901
  1062. s21 = 0
  1063. s8 += s20 * 666643
  1064. s9 += s20 * 470296
  1065. s10 += s20 * 654183
  1066. s11 -= s20 * 997805
  1067. s12 += s20 * 136657
  1068. s13 -= s20 * 683901
  1069. s20 = 0
  1070. s7 += s19 * 666643
  1071. s8 += s19 * 470296
  1072. s9 += s19 * 654183
  1073. s10 -= s19 * 997805
  1074. s11 += s19 * 136657
  1075. s12 -= s19 * 683901
  1076. s19 = 0
  1077. s6 += s18 * 666643
  1078. s7 += s18 * 470296
  1079. s8 += s18 * 654183
  1080. s9 -= s18 * 997805
  1081. s10 += s18 * 136657
  1082. s11 -= s18 * 683901
  1083. s18 = 0
  1084. carry[6] = (s6 + (1 << 20)) >> 21
  1085. s7 += carry[6]
  1086. s6 -= carry[6] << 21
  1087. carry[8] = (s8 + (1 << 20)) >> 21
  1088. s9 += carry[8]
  1089. s8 -= carry[8] << 21
  1090. carry[10] = (s10 + (1 << 20)) >> 21
  1091. s11 += carry[10]
  1092. s10 -= carry[10] << 21
  1093. carry[12] = (s12 + (1 << 20)) >> 21
  1094. s13 += carry[12]
  1095. s12 -= carry[12] << 21
  1096. carry[14] = (s14 + (1 << 20)) >> 21
  1097. s15 += carry[14]
  1098. s14 -= carry[14] << 21
  1099. carry[16] = (s16 + (1 << 20)) >> 21
  1100. s17 += carry[16]
  1101. s16 -= carry[16] << 21
  1102. carry[7] = (s7 + (1 << 20)) >> 21
  1103. s8 += carry[7]
  1104. s7 -= carry[7] << 21
  1105. carry[9] = (s9 + (1 << 20)) >> 21
  1106. s10 += carry[9]
  1107. s9 -= carry[9] << 21
  1108. carry[11] = (s11 + (1 << 20)) >> 21
  1109. s12 += carry[11]
  1110. s11 -= carry[11] << 21
  1111. carry[13] = (s13 + (1 << 20)) >> 21
  1112. s14 += carry[13]
  1113. s13 -= carry[13] << 21
  1114. carry[15] = (s15 + (1 << 20)) >> 21
  1115. s16 += carry[15]
  1116. s15 -= carry[15] << 21
  1117. s5 += s17 * 666643
  1118. s6 += s17 * 470296
  1119. s7 += s17 * 654183
  1120. s8 -= s17 * 997805
  1121. s9 += s17 * 136657
  1122. s10 -= s17 * 683901
  1123. s17 = 0
  1124. s4 += s16 * 666643
  1125. s5 += s16 * 470296
  1126. s6 += s16 * 654183
  1127. s7 -= s16 * 997805
  1128. s8 += s16 * 136657
  1129. s9 -= s16 * 683901
  1130. s16 = 0
  1131. s3 += s15 * 666643
  1132. s4 += s15 * 470296
  1133. s5 += s15 * 654183
  1134. s6 -= s15 * 997805
  1135. s7 += s15 * 136657
  1136. s8 -= s15 * 683901
  1137. s15 = 0
  1138. s2 += s14 * 666643
  1139. s3 += s14 * 470296
  1140. s4 += s14 * 654183
  1141. s5 -= s14 * 997805
  1142. s6 += s14 * 136657
  1143. s7 -= s14 * 683901
  1144. s14 = 0
  1145. s1 += s13 * 666643
  1146. s2 += s13 * 470296
  1147. s3 += s13 * 654183
  1148. s4 -= s13 * 997805
  1149. s5 += s13 * 136657
  1150. s6 -= s13 * 683901
  1151. s13 = 0
  1152. s0 += s12 * 666643
  1153. s1 += s12 * 470296
  1154. s2 += s12 * 654183
  1155. s3 -= s12 * 997805
  1156. s4 += s12 * 136657
  1157. s5 -= s12 * 683901
  1158. s12 = 0
  1159. carry[0] = (s0 + (1 << 20)) >> 21
  1160. s1 += carry[0]
  1161. s0 -= carry[0] << 21
  1162. carry[2] = (s2 + (1 << 20)) >> 21
  1163. s3 += carry[2]
  1164. s2 -= carry[2] << 21
  1165. carry[4] = (s4 + (1 << 20)) >> 21
  1166. s5 += carry[4]
  1167. s4 -= carry[4] << 21
  1168. carry[6] = (s6 + (1 << 20)) >> 21
  1169. s7 += carry[6]
  1170. s6 -= carry[6] << 21
  1171. carry[8] = (s8 + (1 << 20)) >> 21
  1172. s9 += carry[8]
  1173. s8 -= carry[8] << 21
  1174. carry[10] = (s10 + (1 << 20)) >> 21
  1175. s11 += carry[10]
  1176. s10 -= carry[10] << 21
  1177. carry[1] = (s1 + (1 << 20)) >> 21
  1178. s2 += carry[1]
  1179. s1 -= carry[1] << 21
  1180. carry[3] = (s3 + (1 << 20)) >> 21
  1181. s4 += carry[3]
  1182. s3 -= carry[3] << 21
  1183. carry[5] = (s5 + (1 << 20)) >> 21
  1184. s6 += carry[5]
  1185. s5 -= carry[5] << 21
  1186. carry[7] = (s7 + (1 << 20)) >> 21
  1187. s8 += carry[7]
  1188. s7 -= carry[7] << 21
  1189. carry[9] = (s9 + (1 << 20)) >> 21
  1190. s10 += carry[9]
  1191. s9 -= carry[9] << 21
  1192. carry[11] = (s11 + (1 << 20)) >> 21
  1193. s12 += carry[11]
  1194. s11 -= carry[11] << 21
  1195. s0 += s12 * 666643
  1196. s1 += s12 * 470296
  1197. s2 += s12 * 654183
  1198. s3 -= s12 * 997805
  1199. s4 += s12 * 136657
  1200. s5 -= s12 * 683901
  1201. s12 = 0
  1202. carry[0] = s0 >> 21
  1203. s1 += carry[0]
  1204. s0 -= carry[0] << 21
  1205. carry[1] = s1 >> 21
  1206. s2 += carry[1]
  1207. s1 -= carry[1] << 21
  1208. carry[2] = s2 >> 21
  1209. s3 += carry[2]
  1210. s2 -= carry[2] << 21
  1211. carry[3] = s3 >> 21
  1212. s4 += carry[3]
  1213. s3 -= carry[3] << 21
  1214. carry[4] = s4 >> 21
  1215. s5 += carry[4]
  1216. s4 -= carry[4] << 21
  1217. carry[5] = s5 >> 21
  1218. s6 += carry[5]
  1219. s5 -= carry[5] << 21
  1220. carry[6] = s6 >> 21
  1221. s7 += carry[6]
  1222. s6 -= carry[6] << 21
  1223. carry[7] = s7 >> 21
  1224. s8 += carry[7]
  1225. s7 -= carry[7] << 21
  1226. carry[8] = s8 >> 21
  1227. s9 += carry[8]
  1228. s8 -= carry[8] << 21
  1229. carry[9] = s9 >> 21
  1230. s10 += carry[9]
  1231. s9 -= carry[9] << 21
  1232. carry[10] = s10 >> 21
  1233. s11 += carry[10]
  1234. s10 -= carry[10] << 21
  1235. carry[11] = s11 >> 21
  1236. s12 += carry[11]
  1237. s11 -= carry[11] << 21
  1238. s0 += s12 * 666643
  1239. s1 += s12 * 470296
  1240. s2 += s12 * 654183
  1241. s3 -= s12 * 997805
  1242. s4 += s12 * 136657
  1243. s5 -= s12 * 683901
  1244. s12 = 0
  1245. carry[0] = s0 >> 21
  1246. s1 += carry[0]
  1247. s0 -= carry[0] << 21
  1248. carry[1] = s1 >> 21
  1249. s2 += carry[1]
  1250. s1 -= carry[1] << 21
  1251. carry[2] = s2 >> 21
  1252. s3 += carry[2]
  1253. s2 -= carry[2] << 21
  1254. carry[3] = s3 >> 21
  1255. s4 += carry[3]
  1256. s3 -= carry[3] << 21
  1257. carry[4] = s4 >> 21
  1258. s5 += carry[4]
  1259. s4 -= carry[4] << 21
  1260. carry[5] = s5 >> 21
  1261. s6 += carry[5]
  1262. s5 -= carry[5] << 21
  1263. carry[6] = s6 >> 21
  1264. s7 += carry[6]
  1265. s6 -= carry[6] << 21
  1266. carry[7] = s7 >> 21
  1267. s8 += carry[7]
  1268. s7 -= carry[7] << 21
  1269. carry[8] = s8 >> 21
  1270. s9 += carry[8]
  1271. s8 -= carry[8] << 21
  1272. carry[9] = s9 >> 21
  1273. s10 += carry[9]
  1274. s9 -= carry[9] << 21
  1275. carry[10] = s10 >> 21
  1276. s11 += carry[10]
  1277. s10 -= carry[10] << 21
  1278. s[0] = byte(s0 >> 0)
  1279. s[1] = byte(s0 >> 8)
  1280. s[2] = byte((s0 >> 16) | (s1 << 5))
  1281. s[3] = byte(s1 >> 3)
  1282. s[4] = byte(s1 >> 11)
  1283. s[5] = byte((s1 >> 19) | (s2 << 2))
  1284. s[6] = byte(s2 >> 6)
  1285. s[7] = byte((s2 >> 14) | (s3 << 7))
  1286. s[8] = byte(s3 >> 1)
  1287. s[9] = byte(s3 >> 9)
  1288. s[10] = byte((s3 >> 17) | (s4 << 4))
  1289. s[11] = byte(s4 >> 4)
  1290. s[12] = byte(s4 >> 12)
  1291. s[13] = byte((s4 >> 20) | (s5 << 1))
  1292. s[14] = byte(s5 >> 7)
  1293. s[15] = byte((s5 >> 15) | (s6 << 6))
  1294. s[16] = byte(s6 >> 2)
  1295. s[17] = byte(s6 >> 10)
  1296. s[18] = byte((s6 >> 18) | (s7 << 3))
  1297. s[19] = byte(s7 >> 5)
  1298. s[20] = byte(s7 >> 13)
  1299. s[21] = byte(s8 >> 0)
  1300. s[22] = byte(s8 >> 8)
  1301. s[23] = byte((s8 >> 16) | (s9 << 5))
  1302. s[24] = byte(s9 >> 3)
  1303. s[25] = byte(s9 >> 11)
  1304. s[26] = byte((s9 >> 19) | (s10 << 2))
  1305. s[27] = byte(s10 >> 6)
  1306. s[28] = byte((s10 >> 14) | (s11 << 7))
  1307. s[29] = byte(s11 >> 1)
  1308. s[30] = byte(s11 >> 9)
  1309. s[31] = byte(s11 >> 17)
  1310. }
  1311. // Input:
  1312. // s[0]+256*s[1]+...+256^63*s[63] = s
  1313. //
  1314. // Output:
  1315. // s[0]+256*s[1]+...+256^31*s[31] = s mod l
  1316. // where l = 2^252 + 27742317777372353535851937790883648493.
  1317. func ScReduce(out *[32]byte, s *[64]byte) {
  1318. s0 := 2097151 & load3(s[:])
  1319. s1 := 2097151 & (load4(s[2:]) >> 5)
  1320. s2 := 2097151 & (load3(s[5:]) >> 2)
  1321. s3 := 2097151 & (load4(s[7:]) >> 7)
  1322. s4 := 2097151 & (load4(s[10:]) >> 4)
  1323. s5 := 2097151 & (load3(s[13:]) >> 1)
  1324. s6 := 2097151 & (load4(s[15:]) >> 6)
  1325. s7 := 2097151 & (load3(s[18:]) >> 3)
  1326. s8 := 2097151 & load3(s[21:])
  1327. s9 := 2097151 & (load4(s[23:]) >> 5)
  1328. s10 := 2097151 & (load3(s[26:]) >> 2)
  1329. s11 := 2097151 & (load4(s[28:]) >> 7)
  1330. s12 := 2097151 & (load4(s[31:]) >> 4)
  1331. s13 := 2097151 & (load3(s[34:]) >> 1)
  1332. s14 := 2097151 & (load4(s[36:]) >> 6)
  1333. s15 := 2097151 & (load3(s[39:]) >> 3)
  1334. s16 := 2097151 & load3(s[42:])
  1335. s17 := 2097151 & (load4(s[44:]) >> 5)
  1336. s18 := 2097151 & (load3(s[47:]) >> 2)
  1337. s19 := 2097151 & (load4(s[49:]) >> 7)
  1338. s20 := 2097151 & (load4(s[52:]) >> 4)
  1339. s21 := 2097151 & (load3(s[55:]) >> 1)
  1340. s22 := 2097151 & (load4(s[57:]) >> 6)
  1341. s23 := (load4(s[60:]) >> 3)
  1342. s11 += s23 * 666643
  1343. s12 += s23 * 470296
  1344. s13 += s23 * 654183
  1345. s14 -= s23 * 997805
  1346. s15 += s23 * 136657
  1347. s16 -= s23 * 683901
  1348. s23 = 0
  1349. s10 += s22 * 666643
  1350. s11 += s22 * 470296
  1351. s12 += s22 * 654183
  1352. s13 -= s22 * 997805
  1353. s14 += s22 * 136657
  1354. s15 -= s22 * 683901
  1355. s22 = 0
  1356. s9 += s21 * 666643
  1357. s10 += s21 * 470296
  1358. s11 += s21 * 654183
  1359. s12 -= s21 * 997805
  1360. s13 += s21 * 136657
  1361. s14 -= s21 * 683901
  1362. s21 = 0
  1363. s8 += s20 * 666643
  1364. s9 += s20 * 470296
  1365. s10 += s20 * 654183
  1366. s11 -= s20 * 997805
  1367. s12 += s20 * 136657
  1368. s13 -= s20 * 683901
  1369. s20 = 0
  1370. s7 += s19 * 666643
  1371. s8 += s19 * 470296
  1372. s9 += s19 * 654183
  1373. s10 -= s19 * 997805
  1374. s11 += s19 * 136657
  1375. s12 -= s19 * 683901
  1376. s19 = 0
  1377. s6 += s18 * 666643
  1378. s7 += s18 * 470296
  1379. s8 += s18 * 654183
  1380. s9 -= s18 * 997805
  1381. s10 += s18 * 136657
  1382. s11 -= s18 * 683901
  1383. s18 = 0
  1384. var carry [17]int64
  1385. carry[6] = (s6 + (1 << 20)) >> 21
  1386. s7 += carry[6]
  1387. s6 -= carry[6] << 21
  1388. carry[8] = (s8 + (1 << 20)) >> 21
  1389. s9 += carry[8]
  1390. s8 -= carry[8] << 21
  1391. carry[10] = (s10 + (1 << 20)) >> 21
  1392. s11 += carry[10]
  1393. s10 -= carry[10] << 21
  1394. carry[12] = (s12 + (1 << 20)) >> 21
  1395. s13 += carry[12]
  1396. s12 -= carry[12] << 21
  1397. carry[14] = (s14 + (1 << 20)) >> 21
  1398. s15 += carry[14]
  1399. s14 -= carry[14] << 21
  1400. carry[16] = (s16 + (1 << 20)) >> 21
  1401. s17 += carry[16]
  1402. s16 -= carry[16] << 21
  1403. carry[7] = (s7 + (1 << 20)) >> 21
  1404. s8 += carry[7]
  1405. s7 -= carry[7] << 21
  1406. carry[9] = (s9 + (1 << 20)) >> 21
  1407. s10 += carry[9]
  1408. s9 -= carry[9] << 21
  1409. carry[11] = (s11 + (1 << 20)) >> 21
  1410. s12 += carry[11]
  1411. s11 -= carry[11] << 21
  1412. carry[13] = (s13 + (1 << 20)) >> 21
  1413. s14 += carry[13]
  1414. s13 -= carry[13] << 21
  1415. carry[15] = (s15 + (1 << 20)) >> 21
  1416. s16 += carry[15]
  1417. s15 -= carry[15] << 21
  1418. s5 += s17 * 666643
  1419. s6 += s17 * 470296
  1420. s7 += s17 * 654183
  1421. s8 -= s17 * 997805
  1422. s9 += s17 * 136657
  1423. s10 -= s17 * 683901
  1424. s17 = 0
  1425. s4 += s16 * 666643
  1426. s5 += s16 * 470296
  1427. s6 += s16 * 654183
  1428. s7 -= s16 * 997805
  1429. s8 += s16 * 136657
  1430. s9 -= s16 * 683901
  1431. s16 = 0
  1432. s3 += s15 * 666643
  1433. s4 += s15 * 470296
  1434. s5 += s15 * 654183
  1435. s6 -= s15 * 997805
  1436. s7 += s15 * 136657
  1437. s8 -= s15 * 683901
  1438. s15 = 0
  1439. s2 += s14 * 666643
  1440. s3 += s14 * 470296
  1441. s4 += s14 * 654183
  1442. s5 -= s14 * 997805
  1443. s6 += s14 * 136657
  1444. s7 -= s14 * 683901
  1445. s14 = 0
  1446. s1 += s13 * 666643
  1447. s2 += s13 * 470296
  1448. s3 += s13 * 654183
  1449. s4 -= s13 * 997805
  1450. s5 += s13 * 136657
  1451. s6 -= s13 * 683901
  1452. s13 = 0
  1453. s0 += s12 * 666643
  1454. s1 += s12 * 470296
  1455. s2 += s12 * 654183
  1456. s3 -= s12 * 997805
  1457. s4 += s12 * 136657
  1458. s5 -= s12 * 683901
  1459. s12 = 0
  1460. carry[0] = (s0 + (1 << 20)) >> 21
  1461. s1 += carry[0]
  1462. s0 -= carry[0] << 21
  1463. carry[2] = (s2 + (1 << 20)) >> 21
  1464. s3 += carry[2]
  1465. s2 -= carry[2] << 21
  1466. carry[4] = (s4 + (1 << 20)) >> 21
  1467. s5 += carry[4]
  1468. s4 -= carry[4] << 21
  1469. carry[6] = (s6 + (1 << 20)) >> 21
  1470. s7 += carry[6]
  1471. s6 -= carry[6] << 21
  1472. carry[8] = (s8 + (1 << 20)) >> 21
  1473. s9 += carry[8]
  1474. s8 -= carry[8] << 21
  1475. carry[10] = (s10 + (1 << 20)) >> 21
  1476. s11 += carry[10]
  1477. s10 -= carry[10] << 21
  1478. carry[1] = (s1 + (1 << 20)) >> 21
  1479. s2 += carry[1]
  1480. s1 -= carry[1] << 21
  1481. carry[3] = (s3 + (1 << 20)) >> 21
  1482. s4 += carry[3]
  1483. s3 -= carry[3] << 21
  1484. carry[5] = (s5 + (1 << 20)) >> 21
  1485. s6 += carry[5]
  1486. s5 -= carry[5] << 21
  1487. carry[7] = (s7 + (1 << 20)) >> 21
  1488. s8 += carry[7]
  1489. s7 -= carry[7] << 21
  1490. carry[9] = (s9 + (1 << 20)) >> 21
  1491. s10 += carry[9]
  1492. s9 -= carry[9] << 21
  1493. carry[11] = (s11 + (1 << 20)) >> 21
  1494. s12 += carry[11]
  1495. s11 -= carry[11] << 21
  1496. s0 += s12 * 666643
  1497. s1 += s12 * 470296
  1498. s2 += s12 * 654183
  1499. s3 -= s12 * 997805
  1500. s4 += s12 * 136657
  1501. s5 -= s12 * 683901
  1502. s12 = 0
  1503. carry[0] = s0 >> 21
  1504. s1 += carry[0]
  1505. s0 -= carry[0] << 21
  1506. carry[1] = s1 >> 21
  1507. s2 += carry[1]
  1508. s1 -= carry[1] << 21
  1509. carry[2] = s2 >> 21
  1510. s3 += carry[2]
  1511. s2 -= carry[2] << 21
  1512. carry[3] = s3 >> 21
  1513. s4 += carry[3]
  1514. s3 -= carry[3] << 21
  1515. carry[4] = s4 >> 21
  1516. s5 += carry[4]
  1517. s4 -= carry[4] << 21
  1518. carry[5] = s5 >> 21
  1519. s6 += carry[5]
  1520. s5 -= carry[5] << 21
  1521. carry[6] = s6 >> 21
  1522. s7 += carry[6]
  1523. s6 -= carry[6] << 21
  1524. carry[7] = s7 >> 21
  1525. s8 += carry[7]
  1526. s7 -= carry[7] << 21
  1527. carry[8] = s8 >> 21
  1528. s9 += carry[8]
  1529. s8 -= carry[8] << 21
  1530. carry[9] = s9 >> 21
  1531. s10 += carry[9]
  1532. s9 -= carry[9] << 21
  1533. carry[10] = s10 >> 21
  1534. s11 += carry[10]
  1535. s10 -= carry[10] << 21
  1536. carry[11] = s11 >> 21
  1537. s12 += carry[11]
  1538. s11 -= carry[11] << 21
  1539. s0 += s12 * 666643
  1540. s1 += s12 * 470296
  1541. s2 += s12 * 654183
  1542. s3 -= s12 * 997805
  1543. s4 += s12 * 136657
  1544. s5 -= s12 * 683901
  1545. s12 = 0
  1546. carry[0] = s0 >> 21
  1547. s1 += carry[0]
  1548. s0 -= carry[0] << 21
  1549. carry[1] = s1 >> 21
  1550. s2 += carry[1]
  1551. s1 -= carry[1] << 21
  1552. carry[2] = s2 >> 21
  1553. s3 += carry[2]
  1554. s2 -= carry[2] << 21
  1555. carry[3] = s3 >> 21
  1556. s4 += carry[3]
  1557. s3 -= carry[3] << 21
  1558. carry[4] = s4 >> 21
  1559. s5 += carry[4]
  1560. s4 -= carry[4] << 21
  1561. carry[5] = s5 >> 21
  1562. s6 += carry[5]
  1563. s5 -= carry[5] << 21
  1564. carry[6] = s6 >> 21
  1565. s7 += carry[6]
  1566. s6 -= carry[6] << 21
  1567. carry[7] = s7 >> 21
  1568. s8 += carry[7]
  1569. s7 -= carry[7] << 21
  1570. carry[8] = s8 >> 21
  1571. s9 += carry[8]
  1572. s8 -= carry[8] << 21
  1573. carry[9] = s9 >> 21
  1574. s10 += carry[9]
  1575. s9 -= carry[9] << 21
  1576. carry[10] = s10 >> 21
  1577. s11 += carry[10]
  1578. s10 -= carry[10] << 21
  1579. out[0] = byte(s0 >> 0)
  1580. out[1] = byte(s0 >> 8)
  1581. out[2] = byte((s0 >> 16) | (s1 << 5))
  1582. out[3] = byte(s1 >> 3)
  1583. out[4] = byte(s1 >> 11)
  1584. out[5] = byte((s1 >> 19) | (s2 << 2))
  1585. out[6] = byte(s2 >> 6)
  1586. out[7] = byte((s2 >> 14) | (s3 << 7))
  1587. out[8] = byte(s3 >> 1)
  1588. out[9] = byte(s3 >> 9)
  1589. out[10] = byte((s3 >> 17) | (s4 << 4))
  1590. out[11] = byte(s4 >> 4)
  1591. out[12] = byte(s4 >> 12)
  1592. out[13] = byte((s4 >> 20) | (s5 << 1))
  1593. out[14] = byte(s5 >> 7)
  1594. out[15] = byte((s5 >> 15) | (s6 << 6))
  1595. out[16] = byte(s6 >> 2)
  1596. out[17] = byte(s6 >> 10)
  1597. out[18] = byte((s6 >> 18) | (s7 << 3))
  1598. out[19] = byte(s7 >> 5)
  1599. out[20] = byte(s7 >> 13)
  1600. out[21] = byte(s8 >> 0)
  1601. out[22] = byte(s8 >> 8)
  1602. out[23] = byte((s8 >> 16) | (s9 << 5))
  1603. out[24] = byte(s9 >> 3)
  1604. out[25] = byte(s9 >> 11)
  1605. out[26] = byte((s9 >> 19) | (s10 << 2))
  1606. out[27] = byte(s10 >> 6)
  1607. out[28] = byte((s10 >> 14) | (s11 << 7))
  1608. out[29] = byte(s11 >> 1)
  1609. out[30] = byte(s11 >> 9)
  1610. out[31] = byte(s11 >> 17)
  1611. }
  1612. // order is the order of Curve25519 in little-endian form.
  1613. var order = [4]uint64{0x5812631a5cf5d3ed, 0x14def9dea2f79cd6, 0, 0x1000000000000000}
  1614. // ScMinimal returns true if the given scalar is less than the order of the
  1615. // curve.
  1616. func ScMinimal(scalar *[32]byte) bool {
  1617. for i := 3; ; i-- {
  1618. v := binary.LittleEndian.Uint64(scalar[i*8:])
  1619. if v > order[i] {
  1620. return false
  1621. } else if v < order[i] {
  1622. break
  1623. } else if i == 0 {
  1624. return false
  1625. }
  1626. }
  1627. return true
  1628. }