bn_nist.c 39 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262
  1. /* crypto/bn/bn_nist.c */
  2. /*
  3. * Written by Nils Larsch for the OpenSSL project
  4. */
  5. /* ====================================================================
  6. * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
  7. *
  8. * Redistribution and use in source and binary forms, with or without
  9. * modification, are permitted provided that the following conditions
  10. * are met:
  11. *
  12. * 1. Redistributions of source code must retain the above copyright
  13. * notice, this list of conditions and the following disclaimer.
  14. *
  15. * 2. Redistributions in binary form must reproduce the above copyright
  16. * notice, this list of conditions and the following disclaimer in
  17. * the documentation and/or other materials provided with the
  18. * distribution.
  19. *
  20. * 3. All advertising materials mentioning features or use of this
  21. * software must display the following acknowledgment:
  22. * "This product includes software developed by the OpenSSL Project
  23. * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  24. *
  25. * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  26. * endorse or promote products derived from this software without
  27. * prior written permission. For written permission, please contact
  28. * openssl-core@openssl.org.
  29. *
  30. * 5. Products derived from this software may not be called "OpenSSL"
  31. * nor may "OpenSSL" appear in their names without prior written
  32. * permission of the OpenSSL Project.
  33. *
  34. * 6. Redistributions of any form whatsoever must retain the following
  35. * acknowledgment:
  36. * "This product includes software developed by the OpenSSL Project
  37. * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  38. *
  39. * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  40. * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  41. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  42. * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
  43. * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  44. * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  45. * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  46. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  48. * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  49. * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  50. * OF THE POSSIBILITY OF SUCH DAMAGE.
  51. * ====================================================================
  52. *
  53. * This product includes cryptographic software written by Eric Young
  54. * (eay@cryptsoft.com). This product includes software written by Tim
  55. * Hudson (tjh@cryptsoft.com).
  56. *
  57. */
  58. #include "bn_lcl.h"
  59. #include "cryptlib.h"
  60. #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
  61. #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
  62. #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
  63. #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
  64. #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
  65. /* pre-computed tables are "carry-less" values of modulus*(i+1) */
  66. #if BN_BITS2 == 64
  67. static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
  68. {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
  69. {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
  70. {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
  71. };
  72. static const BN_ULONG _nist_p_192_sqr[] = {
  73. 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
  74. 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
  75. };
  76. static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
  77. {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
  78. 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL},
  79. {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
  80. 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is
  81. * "carry-full" */
  82. };
  83. static const BN_ULONG _nist_p_224_sqr[] = {
  84. 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
  85. 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
  86. 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
  87. 0xFFFFFFFFFFFFFFFFULL
  88. };
  89. static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
  90. {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
  91. 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL},
  92. {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
  93. 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL},
  94. {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
  95. 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL},
  96. {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
  97. 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL},
  98. {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
  99. 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL},
  100. };
  101. static const BN_ULONG _nist_p_256_sqr[] = {
  102. 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
  103. 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
  104. 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
  105. 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
  106. };
  107. static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
  108. {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL,
  109. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  110. {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
  111. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  112. {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL,
  113. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  114. {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL,
  115. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  116. {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL,
  117. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
  118. };
  119. static const BN_ULONG _nist_p_384_sqr[] = {
  120. 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
  121. 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
  122. 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
  123. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
  124. };
  125. static const BN_ULONG _nist_p_521[] =
  126. { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  127. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  128. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  129. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  130. 0x00000000000001FFULL
  131. };
  132. static const BN_ULONG _nist_p_521_sqr[] = {
  133. 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
  134. 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
  135. 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
  136. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  137. 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
  138. 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
  139. };
  140. #elif BN_BITS2 == 32
  141. static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
  142. {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  143. {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  144. {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
  145. };
  146. static const BN_ULONG _nist_p_192_sqr[] = {
  147. 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
  148. 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
  149. };
  150. static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
  151. {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
  152. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  153. {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
  154. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
  155. };
  156. static const BN_ULONG _nist_p_224_sqr[] = {
  157. 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
  158. 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
  159. 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
  160. 0xFFFFFFFF, 0xFFFFFFFF
  161. };
  162. static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
  163. {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
  164. 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
  165. {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
  166. 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
  167. {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
  168. 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
  169. {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
  170. 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
  171. {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
  172. 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
  173. };
  174. static const BN_ULONG _nist_p_256_sqr[] = {
  175. 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
  176. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
  177. 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
  178. 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
  179. };
  180. static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
  181. {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
  182. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  183. {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
  184. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  185. {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
  186. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  187. {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
  188. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  189. {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
  190. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
  191. };
  192. static const BN_ULONG _nist_p_384_sqr[] = {
  193. 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
  194. 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
  195. 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
  196. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
  197. };
  198. static const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
  199. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
  200. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
  201. 0xFFFFFFFF, 0x000001FF
  202. };
  203. static const BN_ULONG _nist_p_521_sqr[] = {
  204. 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
  205. 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
  206. 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
  207. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
  208. 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
  209. 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
  210. };
  211. #else
  212. # error "unsupported BN_BITS2"
  213. #endif
  214. static const BIGNUM _bignum_nist_p_192 = {
  215. (BN_ULONG *)_nist_p_192[0],
  216. BN_NIST_192_TOP,
  217. BN_NIST_192_TOP,
  218. 0,
  219. BN_FLG_STATIC_DATA
  220. };
  221. static const BIGNUM _bignum_nist_p_224 = {
  222. (BN_ULONG *)_nist_p_224[0],
  223. BN_NIST_224_TOP,
  224. BN_NIST_224_TOP,
  225. 0,
  226. BN_FLG_STATIC_DATA
  227. };
  228. static const BIGNUM _bignum_nist_p_256 = {
  229. (BN_ULONG *)_nist_p_256[0],
  230. BN_NIST_256_TOP,
  231. BN_NIST_256_TOP,
  232. 0,
  233. BN_FLG_STATIC_DATA
  234. };
  235. static const BIGNUM _bignum_nist_p_384 = {
  236. (BN_ULONG *)_nist_p_384[0],
  237. BN_NIST_384_TOP,
  238. BN_NIST_384_TOP,
  239. 0,
  240. BN_FLG_STATIC_DATA
  241. };
  242. static const BIGNUM _bignum_nist_p_521 = {
  243. (BN_ULONG *)_nist_p_521,
  244. BN_NIST_521_TOP,
  245. BN_NIST_521_TOP,
  246. 0,
  247. BN_FLG_STATIC_DATA
  248. };
  249. const BIGNUM *BN_get0_nist_prime_192(void)
  250. {
  251. return &_bignum_nist_p_192;
  252. }
  253. const BIGNUM *BN_get0_nist_prime_224(void)
  254. {
  255. return &_bignum_nist_p_224;
  256. }
  257. const BIGNUM *BN_get0_nist_prime_256(void)
  258. {
  259. return &_bignum_nist_p_256;
  260. }
  261. const BIGNUM *BN_get0_nist_prime_384(void)
  262. {
  263. return &_bignum_nist_p_384;
  264. }
  265. const BIGNUM *BN_get0_nist_prime_521(void)
  266. {
  267. return &_bignum_nist_p_521;
  268. }
  269. static void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max)
  270. {
  271. int i;
  272. #ifdef BN_DEBUG
  273. OPENSSL_assert(top <= max);
  274. #endif
  275. for (i = 0; i < top; i++)
  276. dst[i] = src[i];
  277. for (; i < max; i++)
  278. dst[i] = 0;
  279. }
  280. static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
  281. {
  282. int i;
  283. for (i = 0; i < top; i++)
  284. dst[i] = src[i];
  285. }
  286. #if BN_BITS2 == 64
  287. # define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
  288. # define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
  289. /*
  290. * two following macros are implemented under assumption that they
  291. * are called in a sequence with *ascending* n, i.e. as they are...
  292. */
  293. # define bn_cp_32_naked(to, n, from, m) (((n)&1)?(to[(n)/2]|=((m)&1)?(from[(m)/2]&BN_MASK2h):(from[(m)/2]<<32))\
  294. :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
  295. # define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
  296. # define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
  297. # if defined(L_ENDIAN)
  298. # if defined(__arch64__)
  299. # define NIST_INT64 long
  300. # else
  301. # define NIST_INT64 long long
  302. # endif
  303. # endif
  304. #else
  305. # define bn_cp_64(to, n, from, m) \
  306. { \
  307. bn_cp_32(to, (n)*2, from, (m)*2); \
  308. bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
  309. }
  310. # define bn_64_set_0(to, n) \
  311. { \
  312. bn_32_set_0(to, (n)*2); \
  313. bn_32_set_0(to, (n)*2+1); \
  314. }
  315. # define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
  316. # define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
  317. # if defined(_WIN32) && !defined(__GNUC__)
  318. # define NIST_INT64 __int64
  319. # elif defined(BN_LLONG)
  320. # define NIST_INT64 long long
  321. # endif
  322. #endif /* BN_BITS2 != 64 */
  323. #define nist_set_192(to, from, a1, a2, a3) \
  324. { \
  325. bn_cp_64(to, 0, from, (a3) - 3) \
  326. bn_cp_64(to, 1, from, (a2) - 3) \
  327. bn_cp_64(to, 2, from, (a1) - 3) \
  328. }
  329. int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  330. BN_CTX *ctx)
  331. {
  332. int top = a->top, i;
  333. int carry;
  334. register BN_ULONG *r_d, *a_d = a->d;
  335. union {
  336. BN_ULONG bn[BN_NIST_192_TOP];
  337. unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
  338. sizeof(unsigned int)];
  339. } buf;
  340. BN_ULONG c_d[BN_NIST_192_TOP], *res;
  341. PTR_SIZE_INT mask;
  342. static const BIGNUM _bignum_nist_p_192_sqr = {
  343. (BN_ULONG *)_nist_p_192_sqr,
  344. sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
  345. sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
  346. 0, BN_FLG_STATIC_DATA
  347. };
  348. field = &_bignum_nist_p_192; /* just to make sure */
  349. if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
  350. return BN_nnmod(r, a, field, ctx);
  351. i = BN_ucmp(field, a);
  352. if (i == 0) {
  353. BN_zero(r);
  354. return 1;
  355. } else if (i > 0)
  356. return (r == a) ? 1 : (BN_copy(r, a) != NULL);
  357. if (r != a) {
  358. if (!bn_wexpand(r, BN_NIST_192_TOP))
  359. return 0;
  360. r_d = r->d;
  361. nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
  362. } else
  363. r_d = a_d;
  364. nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
  365. BN_NIST_192_TOP);
  366. #if defined(NIST_INT64)
  367. {
  368. NIST_INT64 acc; /* accumulator */
  369. unsigned int *rp = (unsigned int *)r_d;
  370. const unsigned int *bp = (const unsigned int *)buf.ui;
  371. acc = rp[0];
  372. acc += bp[3 * 2 - 6];
  373. acc += bp[5 * 2 - 6];
  374. rp[0] = (unsigned int)acc;
  375. acc >>= 32;
  376. acc += rp[1];
  377. acc += bp[3 * 2 - 5];
  378. acc += bp[5 * 2 - 5];
  379. rp[1] = (unsigned int)acc;
  380. acc >>= 32;
  381. acc += rp[2];
  382. acc += bp[3 * 2 - 6];
  383. acc += bp[4 * 2 - 6];
  384. acc += bp[5 * 2 - 6];
  385. rp[2] = (unsigned int)acc;
  386. acc >>= 32;
  387. acc += rp[3];
  388. acc += bp[3 * 2 - 5];
  389. acc += bp[4 * 2 - 5];
  390. acc += bp[5 * 2 - 5];
  391. rp[3] = (unsigned int)acc;
  392. acc >>= 32;
  393. acc += rp[4];
  394. acc += bp[4 * 2 - 6];
  395. acc += bp[5 * 2 - 6];
  396. rp[4] = (unsigned int)acc;
  397. acc >>= 32;
  398. acc += rp[5];
  399. acc += bp[4 * 2 - 5];
  400. acc += bp[5 * 2 - 5];
  401. rp[5] = (unsigned int)acc;
  402. carry = (int)(acc >> 32);
  403. }
  404. #else
  405. {
  406. BN_ULONG t_d[BN_NIST_192_TOP];
  407. nist_set_192(t_d, buf.bn, 0, 3, 3);
  408. carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
  409. nist_set_192(t_d, buf.bn, 4, 4, 0);
  410. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
  411. nist_set_192(t_d, buf.bn, 5, 5, 5)
  412. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
  413. }
  414. #endif
  415. if (carry > 0)
  416. carry =
  417. (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
  418. BN_NIST_192_TOP);
  419. else
  420. carry = 1;
  421. /*
  422. * we need 'if (carry==0 || result>=modulus) result-=modulus;'
  423. * as comparison implies subtraction, we can write
  424. * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
  425. * this is what happens below, but without explicit if:-) a.
  426. */
  427. mask =
  428. 0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0],
  429. BN_NIST_192_TOP);
  430. mask &= 0 - (PTR_SIZE_INT) carry;
  431. res = c_d;
  432. res = (BN_ULONG *)
  433. (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask));
  434. nist_cp_bn(r_d, res, BN_NIST_192_TOP);
  435. r->top = BN_NIST_192_TOP;
  436. bn_correct_top(r);
  437. return 1;
  438. }
  439. typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
  440. const BN_ULONG *, int);
  441. #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
  442. { \
  443. bn_cp_32(to, 0, from, (a7) - 7) \
  444. bn_cp_32(to, 1, from, (a6) - 7) \
  445. bn_cp_32(to, 2, from, (a5) - 7) \
  446. bn_cp_32(to, 3, from, (a4) - 7) \
  447. bn_cp_32(to, 4, from, (a3) - 7) \
  448. bn_cp_32(to, 5, from, (a2) - 7) \
  449. bn_cp_32(to, 6, from, (a1) - 7) \
  450. }
  451. int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  452. BN_CTX *ctx)
  453. {
  454. int top = a->top, i;
  455. int carry;
  456. BN_ULONG *r_d, *a_d = a->d;
  457. union {
  458. BN_ULONG bn[BN_NIST_224_TOP];
  459. unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
  460. sizeof(unsigned int)];
  461. } buf;
  462. BN_ULONG c_d[BN_NIST_224_TOP], *res;
  463. PTR_SIZE_INT mask;
  464. union {
  465. bn_addsub_f f;
  466. PTR_SIZE_INT p;
  467. } u;
  468. static const BIGNUM _bignum_nist_p_224_sqr = {
  469. (BN_ULONG *)_nist_p_224_sqr,
  470. sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
  471. sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
  472. 0, BN_FLG_STATIC_DATA
  473. };
  474. field = &_bignum_nist_p_224; /* just to make sure */
  475. if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
  476. return BN_nnmod(r, a, field, ctx);
  477. i = BN_ucmp(field, a);
  478. if (i == 0) {
  479. BN_zero(r);
  480. return 1;
  481. } else if (i > 0)
  482. return (r == a) ? 1 : (BN_copy(r, a) != NULL);
  483. if (r != a) {
  484. if (!bn_wexpand(r, BN_NIST_224_TOP))
  485. return 0;
  486. r_d = r->d;
  487. nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
  488. } else
  489. r_d = a_d;
  490. #if BN_BITS2==64
  491. /* copy upper 256 bits of 448 bit number ... */
  492. nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
  493. top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
  494. /* ... and right shift by 32 to obtain upper 224 bits */
  495. nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
  496. /* truncate lower part to 224 bits too */
  497. r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
  498. #else
  499. nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
  500. BN_NIST_224_TOP);
  501. #endif
  502. #if defined(NIST_INT64) && BN_BITS2!=64
  503. {
  504. NIST_INT64 acc; /* accumulator */
  505. unsigned int *rp = (unsigned int *)r_d;
  506. const unsigned int *bp = (const unsigned int *)buf.ui;
  507. acc = rp[0];
  508. acc -= bp[7 - 7];
  509. acc -= bp[11 - 7];
  510. rp[0] = (unsigned int)acc;
  511. acc >>= 32;
  512. acc += rp[1];
  513. acc -= bp[8 - 7];
  514. acc -= bp[12 - 7];
  515. rp[1] = (unsigned int)acc;
  516. acc >>= 32;
  517. acc += rp[2];
  518. acc -= bp[9 - 7];
  519. acc -= bp[13 - 7];
  520. rp[2] = (unsigned int)acc;
  521. acc >>= 32;
  522. acc += rp[3];
  523. acc += bp[7 - 7];
  524. acc += bp[11 - 7];
  525. acc -= bp[10 - 7];
  526. rp[3] = (unsigned int)acc;
  527. acc >>= 32;
  528. acc += rp[4];
  529. acc += bp[8 - 7];
  530. acc += bp[12 - 7];
  531. acc -= bp[11 - 7];
  532. rp[4] = (unsigned int)acc;
  533. acc >>= 32;
  534. acc += rp[5];
  535. acc += bp[9 - 7];
  536. acc += bp[13 - 7];
  537. acc -= bp[12 - 7];
  538. rp[5] = (unsigned int)acc;
  539. acc >>= 32;
  540. acc += rp[6];
  541. acc += bp[10 - 7];
  542. acc -= bp[13 - 7];
  543. rp[6] = (unsigned int)acc;
  544. carry = (int)(acc >> 32);
  545. # if BN_BITS2==64
  546. rp[7] = carry;
  547. # endif
  548. }
  549. #else
  550. {
  551. BN_ULONG t_d[BN_NIST_224_TOP];
  552. nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
  553. carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
  554. nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
  555. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
  556. nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
  557. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
  558. nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
  559. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
  560. # if BN_BITS2==64
  561. carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
  562. # endif
  563. }
  564. #endif
  565. u.f = bn_sub_words;
  566. if (carry > 0) {
  567. carry =
  568. (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
  569. BN_NIST_224_TOP);
  570. #if BN_BITS2==64
  571. carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
  572. #endif
  573. } else if (carry < 0) {
  574. /*
  575. * it's a bit more comlicated logic in this case. if bn_add_words
  576. * yields no carry, then result has to be adjusted by unconditionally
  577. * *adding* the modulus. but if it does, then result has to be
  578. * compared to the modulus and conditionally adjusted by
  579. * *subtracting* the latter.
  580. */
  581. carry =
  582. (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
  583. BN_NIST_224_TOP);
  584. mask = 0 - (PTR_SIZE_INT) carry;
  585. u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
  586. ((PTR_SIZE_INT) bn_add_words & ~mask);
  587. } else
  588. carry = 1;
  589. /* otherwise it's effectively same as in BN_nist_mod_192... */
  590. mask =
  591. 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
  592. mask &= 0 - (PTR_SIZE_INT) carry;
  593. res = c_d;
  594. res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
  595. ((PTR_SIZE_INT) r_d & mask));
  596. nist_cp_bn(r_d, res, BN_NIST_224_TOP);
  597. r->top = BN_NIST_224_TOP;
  598. bn_correct_top(r);
  599. return 1;
  600. }
  601. #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
  602. { \
  603. bn_cp_32(to, 0, from, (a8) - 8) \
  604. bn_cp_32(to, 1, from, (a7) - 8) \
  605. bn_cp_32(to, 2, from, (a6) - 8) \
  606. bn_cp_32(to, 3, from, (a5) - 8) \
  607. bn_cp_32(to, 4, from, (a4) - 8) \
  608. bn_cp_32(to, 5, from, (a3) - 8) \
  609. bn_cp_32(to, 6, from, (a2) - 8) \
  610. bn_cp_32(to, 7, from, (a1) - 8) \
  611. }
  612. int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  613. BN_CTX *ctx)
  614. {
  615. int i, top = a->top;
  616. int carry = 0;
  617. register BN_ULONG *a_d = a->d, *r_d;
  618. union {
  619. BN_ULONG bn[BN_NIST_256_TOP];
  620. unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
  621. sizeof(unsigned int)];
  622. } buf;
  623. BN_ULONG c_d[BN_NIST_256_TOP], *res;
  624. PTR_SIZE_INT mask;
  625. union {
  626. bn_addsub_f f;
  627. PTR_SIZE_INT p;
  628. } u;
  629. static const BIGNUM _bignum_nist_p_256_sqr = {
  630. (BN_ULONG *)_nist_p_256_sqr,
  631. sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
  632. sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
  633. 0, BN_FLG_STATIC_DATA
  634. };
  635. field = &_bignum_nist_p_256; /* just to make sure */
  636. if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
  637. return BN_nnmod(r, a, field, ctx);
  638. i = BN_ucmp(field, a);
  639. if (i == 0) {
  640. BN_zero(r);
  641. return 1;
  642. } else if (i > 0)
  643. return (r == a) ? 1 : (BN_copy(r, a) != NULL);
  644. if (r != a) {
  645. if (!bn_wexpand(r, BN_NIST_256_TOP))
  646. return 0;
  647. r_d = r->d;
  648. nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
  649. } else
  650. r_d = a_d;
  651. nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
  652. BN_NIST_256_TOP);
  653. #if defined(NIST_INT64)
  654. {
  655. NIST_INT64 acc; /* accumulator */
  656. unsigned int *rp = (unsigned int *)r_d;
  657. const unsigned int *bp = (const unsigned int *)buf.ui;
  658. acc = rp[0];
  659. acc += bp[8 - 8];
  660. acc += bp[9 - 8];
  661. acc -= bp[11 - 8];
  662. acc -= bp[12 - 8];
  663. acc -= bp[13 - 8];
  664. acc -= bp[14 - 8];
  665. rp[0] = (unsigned int)acc;
  666. acc >>= 32;
  667. acc += rp[1];
  668. acc += bp[9 - 8];
  669. acc += bp[10 - 8];
  670. acc -= bp[12 - 8];
  671. acc -= bp[13 - 8];
  672. acc -= bp[14 - 8];
  673. acc -= bp[15 - 8];
  674. rp[1] = (unsigned int)acc;
  675. acc >>= 32;
  676. acc += rp[2];
  677. acc += bp[10 - 8];
  678. acc += bp[11 - 8];
  679. acc -= bp[13 - 8];
  680. acc -= bp[14 - 8];
  681. acc -= bp[15 - 8];
  682. rp[2] = (unsigned int)acc;
  683. acc >>= 32;
  684. acc += rp[3];
  685. acc += bp[11 - 8];
  686. acc += bp[11 - 8];
  687. acc += bp[12 - 8];
  688. acc += bp[12 - 8];
  689. acc += bp[13 - 8];
  690. acc -= bp[15 - 8];
  691. acc -= bp[8 - 8];
  692. acc -= bp[9 - 8];
  693. rp[3] = (unsigned int)acc;
  694. acc >>= 32;
  695. acc += rp[4];
  696. acc += bp[12 - 8];
  697. acc += bp[12 - 8];
  698. acc += bp[13 - 8];
  699. acc += bp[13 - 8];
  700. acc += bp[14 - 8];
  701. acc -= bp[9 - 8];
  702. acc -= bp[10 - 8];
  703. rp[4] = (unsigned int)acc;
  704. acc >>= 32;
  705. acc += rp[5];
  706. acc += bp[13 - 8];
  707. acc += bp[13 - 8];
  708. acc += bp[14 - 8];
  709. acc += bp[14 - 8];
  710. acc += bp[15 - 8];
  711. acc -= bp[10 - 8];
  712. acc -= bp[11 - 8];
  713. rp[5] = (unsigned int)acc;
  714. acc >>= 32;
  715. acc += rp[6];
  716. acc += bp[14 - 8];
  717. acc += bp[14 - 8];
  718. acc += bp[15 - 8];
  719. acc += bp[15 - 8];
  720. acc += bp[14 - 8];
  721. acc += bp[13 - 8];
  722. acc -= bp[8 - 8];
  723. acc -= bp[9 - 8];
  724. rp[6] = (unsigned int)acc;
  725. acc >>= 32;
  726. acc += rp[7];
  727. acc += bp[15 - 8];
  728. acc += bp[15 - 8];
  729. acc += bp[15 - 8];
  730. acc += bp[8 - 8];
  731. acc -= bp[10 - 8];
  732. acc -= bp[11 - 8];
  733. acc -= bp[12 - 8];
  734. acc -= bp[13 - 8];
  735. rp[7] = (unsigned int)acc;
  736. carry = (int)(acc >> 32);
  737. }
  738. #else
  739. {
  740. BN_ULONG t_d[BN_NIST_256_TOP];
  741. /*
  742. * S1
  743. */
  744. nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
  745. /*
  746. * S2
  747. */
  748. nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
  749. carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
  750. /* left shift */
  751. {
  752. register BN_ULONG *ap, t, c;
  753. ap = t_d;
  754. c = 0;
  755. for (i = BN_NIST_256_TOP; i != 0; --i) {
  756. t = *ap;
  757. *(ap++) = ((t << 1) | c) & BN_MASK2;
  758. c = (t & BN_TBIT) ? 1 : 0;
  759. }
  760. carry <<= 1;
  761. carry |= c;
  762. }
  763. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  764. /*
  765. * S3
  766. */
  767. nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
  768. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  769. /*
  770. * S4
  771. */
  772. nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
  773. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  774. /*
  775. * D1
  776. */
  777. nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
  778. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  779. /*
  780. * D2
  781. */
  782. nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
  783. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  784. /*
  785. * D3
  786. */
  787. nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
  788. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  789. /*
  790. * D4
  791. */
  792. nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
  793. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
  794. }
  795. #endif
  796. /* see BN_nist_mod_224 for explanation */
  797. u.f = bn_sub_words;
  798. if (carry > 0)
  799. carry =
  800. (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
  801. BN_NIST_256_TOP);
  802. else if (carry < 0) {
  803. carry =
  804. (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
  805. BN_NIST_256_TOP);
  806. mask = 0 - (PTR_SIZE_INT) carry;
  807. u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
  808. ((PTR_SIZE_INT) bn_add_words & ~mask);
  809. } else
  810. carry = 1;
  811. mask =
  812. 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
  813. mask &= 0 - (PTR_SIZE_INT) carry;
  814. res = c_d;
  815. res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
  816. ((PTR_SIZE_INT) r_d & mask));
  817. nist_cp_bn(r_d, res, BN_NIST_256_TOP);
  818. r->top = BN_NIST_256_TOP;
  819. bn_correct_top(r);
  820. return 1;
  821. }
  822. #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
  823. { \
  824. bn_cp_32(to, 0, from, (a12) - 12) \
  825. bn_cp_32(to, 1, from, (a11) - 12) \
  826. bn_cp_32(to, 2, from, (a10) - 12) \
  827. bn_cp_32(to, 3, from, (a9) - 12) \
  828. bn_cp_32(to, 4, from, (a8) - 12) \
  829. bn_cp_32(to, 5, from, (a7) - 12) \
  830. bn_cp_32(to, 6, from, (a6) - 12) \
  831. bn_cp_32(to, 7, from, (a5) - 12) \
  832. bn_cp_32(to, 8, from, (a4) - 12) \
  833. bn_cp_32(to, 9, from, (a3) - 12) \
  834. bn_cp_32(to, 10, from, (a2) - 12) \
  835. bn_cp_32(to, 11, from, (a1) - 12) \
  836. }
  837. int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  838. BN_CTX *ctx)
  839. {
  840. int i, top = a->top;
  841. int carry = 0;
  842. register BN_ULONG *r_d, *a_d = a->d;
  843. union {
  844. BN_ULONG bn[BN_NIST_384_TOP];
  845. unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
  846. sizeof(unsigned int)];
  847. } buf;
  848. BN_ULONG c_d[BN_NIST_384_TOP], *res;
  849. PTR_SIZE_INT mask;
  850. union {
  851. bn_addsub_f f;
  852. PTR_SIZE_INT p;
  853. } u;
  854. static const BIGNUM _bignum_nist_p_384_sqr = {
  855. (BN_ULONG *)_nist_p_384_sqr,
  856. sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
  857. sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
  858. 0, BN_FLG_STATIC_DATA
  859. };
  860. field = &_bignum_nist_p_384; /* just to make sure */
  861. if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
  862. return BN_nnmod(r, a, field, ctx);
  863. i = BN_ucmp(field, a);
  864. if (i == 0) {
  865. BN_zero(r);
  866. return 1;
  867. } else if (i > 0)
  868. return (r == a) ? 1 : (BN_copy(r, a) != NULL);
  869. if (r != a) {
  870. if (!bn_wexpand(r, BN_NIST_384_TOP))
  871. return 0;
  872. r_d = r->d;
  873. nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
  874. } else
  875. r_d = a_d;
  876. nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
  877. BN_NIST_384_TOP);
  878. #if defined(NIST_INT64)
  879. {
  880. NIST_INT64 acc; /* accumulator */
  881. unsigned int *rp = (unsigned int *)r_d;
  882. const unsigned int *bp = (const unsigned int *)buf.ui;
  883. acc = rp[0];
  884. acc += bp[12 - 12];
  885. acc += bp[21 - 12];
  886. acc += bp[20 - 12];
  887. acc -= bp[23 - 12];
  888. rp[0] = (unsigned int)acc;
  889. acc >>= 32;
  890. acc += rp[1];
  891. acc += bp[13 - 12];
  892. acc += bp[22 - 12];
  893. acc += bp[23 - 12];
  894. acc -= bp[12 - 12];
  895. acc -= bp[20 - 12];
  896. rp[1] = (unsigned int)acc;
  897. acc >>= 32;
  898. acc += rp[2];
  899. acc += bp[14 - 12];
  900. acc += bp[23 - 12];
  901. acc -= bp[13 - 12];
  902. acc -= bp[21 - 12];
  903. rp[2] = (unsigned int)acc;
  904. acc >>= 32;
  905. acc += rp[3];
  906. acc += bp[15 - 12];
  907. acc += bp[12 - 12];
  908. acc += bp[20 - 12];
  909. acc += bp[21 - 12];
  910. acc -= bp[14 - 12];
  911. acc -= bp[22 - 12];
  912. acc -= bp[23 - 12];
  913. rp[3] = (unsigned int)acc;
  914. acc >>= 32;
  915. acc += rp[4];
  916. acc += bp[21 - 12];
  917. acc += bp[21 - 12];
  918. acc += bp[16 - 12];
  919. acc += bp[13 - 12];
  920. acc += bp[12 - 12];
  921. acc += bp[20 - 12];
  922. acc += bp[22 - 12];
  923. acc -= bp[15 - 12];
  924. acc -= bp[23 - 12];
  925. acc -= bp[23 - 12];
  926. rp[4] = (unsigned int)acc;
  927. acc >>= 32;
  928. acc += rp[5];
  929. acc += bp[22 - 12];
  930. acc += bp[22 - 12];
  931. acc += bp[17 - 12];
  932. acc += bp[14 - 12];
  933. acc += bp[13 - 12];
  934. acc += bp[21 - 12];
  935. acc += bp[23 - 12];
  936. acc -= bp[16 - 12];
  937. rp[5] = (unsigned int)acc;
  938. acc >>= 32;
  939. acc += rp[6];
  940. acc += bp[23 - 12];
  941. acc += bp[23 - 12];
  942. acc += bp[18 - 12];
  943. acc += bp[15 - 12];
  944. acc += bp[14 - 12];
  945. acc += bp[22 - 12];
  946. acc -= bp[17 - 12];
  947. rp[6] = (unsigned int)acc;
  948. acc >>= 32;
  949. acc += rp[7];
  950. acc += bp[19 - 12];
  951. acc += bp[16 - 12];
  952. acc += bp[15 - 12];
  953. acc += bp[23 - 12];
  954. acc -= bp[18 - 12];
  955. rp[7] = (unsigned int)acc;
  956. acc >>= 32;
  957. acc += rp[8];
  958. acc += bp[20 - 12];
  959. acc += bp[17 - 12];
  960. acc += bp[16 - 12];
  961. acc -= bp[19 - 12];
  962. rp[8] = (unsigned int)acc;
  963. acc >>= 32;
  964. acc += rp[9];
  965. acc += bp[21 - 12];
  966. acc += bp[18 - 12];
  967. acc += bp[17 - 12];
  968. acc -= bp[20 - 12];
  969. rp[9] = (unsigned int)acc;
  970. acc >>= 32;
  971. acc += rp[10];
  972. acc += bp[22 - 12];
  973. acc += bp[19 - 12];
  974. acc += bp[18 - 12];
  975. acc -= bp[21 - 12];
  976. rp[10] = (unsigned int)acc;
  977. acc >>= 32;
  978. acc += rp[11];
  979. acc += bp[23 - 12];
  980. acc += bp[20 - 12];
  981. acc += bp[19 - 12];
  982. acc -= bp[22 - 12];
  983. rp[11] = (unsigned int)acc;
  984. carry = (int)(acc >> 32);
  985. }
  986. #else
  987. {
  988. BN_ULONG t_d[BN_NIST_384_TOP];
  989. /*
  990. * S1
  991. */
  992. nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
  993. /* left shift */
  994. {
  995. register BN_ULONG *ap, t, c;
  996. ap = t_d;
  997. c = 0;
  998. for (i = 3; i != 0; --i) {
  999. t = *ap;
  1000. *(ap++) = ((t << 1) | c) & BN_MASK2;
  1001. c = (t & BN_TBIT) ? 1 : 0;
  1002. }
  1003. *ap = c;
  1004. }
  1005. carry =
  1006. (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
  1007. t_d, BN_NIST_256_TOP);
  1008. /*
  1009. * S2
  1010. */
  1011. carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
  1012. /*
  1013. * S3
  1014. */
  1015. nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
  1016. 21);
  1017. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1018. /*
  1019. * S4
  1020. */
  1021. nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
  1022. 0);
  1023. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1024. /*
  1025. * S5
  1026. */
  1027. nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
  1028. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1029. /*
  1030. * S6
  1031. */
  1032. nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
  1033. carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1034. /*
  1035. * D1
  1036. */
  1037. nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
  1038. 23);
  1039. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1040. /*
  1041. * D2
  1042. */
  1043. nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
  1044. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1045. /*
  1046. * D3
  1047. */
  1048. nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
  1049. carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
  1050. }
  1051. #endif
  1052. /* see BN_nist_mod_224 for explanation */
  1053. u.f = bn_sub_words;
  1054. if (carry > 0)
  1055. carry =
  1056. (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
  1057. BN_NIST_384_TOP);
  1058. else if (carry < 0) {
  1059. carry =
  1060. (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
  1061. BN_NIST_384_TOP);
  1062. mask = 0 - (PTR_SIZE_INT) carry;
  1063. u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
  1064. ((PTR_SIZE_INT) bn_add_words & ~mask);
  1065. } else
  1066. carry = 1;
  1067. mask =
  1068. 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
  1069. mask &= 0 - (PTR_SIZE_INT) carry;
  1070. res = c_d;
  1071. res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
  1072. ((PTR_SIZE_INT) r_d & mask));
  1073. nist_cp_bn(r_d, res, BN_NIST_384_TOP);
  1074. r->top = BN_NIST_384_TOP;
  1075. bn_correct_top(r);
  1076. return 1;
  1077. }
  1078. #define BN_NIST_521_RSHIFT (521%BN_BITS2)
  1079. #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT)
  1080. #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
  1081. int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
  1082. BN_CTX *ctx)
  1083. {
  1084. int top = a->top, i;
  1085. BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
  1086. PTR_SIZE_INT mask;
  1087. static const BIGNUM _bignum_nist_p_521_sqr = {
  1088. (BN_ULONG *)_nist_p_521_sqr,
  1089. sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
  1090. sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
  1091. 0, BN_FLG_STATIC_DATA
  1092. };
  1093. field = &_bignum_nist_p_521; /* just to make sure */
  1094. if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
  1095. return BN_nnmod(r, a, field, ctx);
  1096. i = BN_ucmp(field, a);
  1097. if (i == 0) {
  1098. BN_zero(r);
  1099. return 1;
  1100. } else if (i > 0)
  1101. return (r == a) ? 1 : (BN_copy(r, a) != NULL);
  1102. if (r != a) {
  1103. if (!bn_wexpand(r, BN_NIST_521_TOP))
  1104. return 0;
  1105. r_d = r->d;
  1106. nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
  1107. } else
  1108. r_d = a_d;
  1109. /* upper 521 bits, copy ... */
  1110. nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
  1111. top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
  1112. /* ... and right shift */
  1113. for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
  1114. t_d[i] = (val >> BN_NIST_521_RSHIFT |
  1115. (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
  1116. val = tmp;
  1117. }
  1118. t_d[i] = val >> BN_NIST_521_RSHIFT;
  1119. /* lower 521 bits */
  1120. r_d[i] &= BN_NIST_521_TOP_MASK;
  1121. bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
  1122. mask =
  1123. 0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521,
  1124. BN_NIST_521_TOP);
  1125. res = t_d;
  1126. res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
  1127. ((PTR_SIZE_INT) r_d & mask));
  1128. nist_cp_bn(r_d, res, BN_NIST_521_TOP);
  1129. r->top = BN_NIST_521_TOP;
  1130. bn_correct_top(r);
  1131. return 1;
  1132. }