)]}'
{
  "commit": "02d2715bcc95d0f03ae394310d32739f4fcfa1ac",
  "tree": "359d14ca6a6c57a99bcdf44d380410f7dc8ceb2f",
  "parents": [
    "98e1227cb7bfe4b845c7fc5136e83f8d368065b2"
  ],
  "author": {
    "name": "David Benjamin",
    "email": "davidben@google.com",
    "time": "Thu Jan 06 19:18:45 2022 -0500"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Tue Jun 13 22:22:53 2023 +0000"
  },
  "message": "Implement BN_MONT_CTX_new_consttime with Montgomery reduction\n\nSetting up Montgomery reduction requires computing RR, a larger power of\n2 mod N. When N is secret (RSA primes), we currently start at\n2^(n_bits-1), then iteratively double and reduce.\n\nInstead, once we reach 2R \u003d 2^(r_bits+1) or higher, we can switch to a\nMontgomery square-and-multiply. (Montgomery reduction only needs n0. RR\nis just for conversion.) This takes some tuning because, at low powers\nof 2 (in Montgomery form), it is still more efficient to square by\ndoubling. I ran benchmarks for 32-bit and 64-bit, x86 and Arm, on the\nmachines I had available and picked a threshold that works decently\nwell.\n\n(On the hardware I tested, it\u0027s the right threshold on all but the Pixel\n5A. The 5A would ideally want a slightly higher threshold---it seems to\nbe worse at multiplying or better at addition, but the gap isn\u0027t that\nlarge, and this operation isn\u0027t perf-sensitive anyway.)\n\nThe result is dramatically faster than the old shift-based approach.\nThat said, see I06f4a065fdecc1aec3160fe32a41e200538d1ee3 for discussion\non this operation. These speedups are not expected to translate to\nincreased RSA throughput. They just clear up some initialization work.\nThis speedup is not quite enough to match the division-based\nvariable-time one (perf-sensitive for RSA verification), so we\u0027ll keep\nboth codepaths around.\n\nM1 Max\nBefore:\nDid 712000 256-bit mont (constime) operations in 2000454us (355919.2 ops/sec)\nDid 440000 384-bit mont (constime) operations in 2001121us (219876.8 ops/sec)\nDid 259000 512-bit mont (constime) operations in 2003709us (129260.3 ops/sec)\nDid 212000 521-bit mont (constime) operations in 2007033us (105628.6 ops/sec)\nDid 107000 1024-bit mont (constime) operations in 2018551us (53008.3 ops/sec)\nDid 57000 1536-bit mont (constime) operations in 2001027us (28485.4 ops/sec)\nDid 37000 2048-bit mont (constime) operations in 2039631us (18140.5 ops/sec)\nDid 20000 3072-bit mont (constime) operations in 2041163us (9798.3 ops/sec)\nDid 11760 4096-bit mont (constime) operations in 2007195us (5858.9 ops/sec)\nAfter:\nDid 3996000 256-bit mont (constime) operations in 2000366us (1997634.4 ops/sec) [+461.3%]\nDid 2687000 384-bit mont (constime) operations in 2000464us (1343188.4 ops/sec) [+510.9%]\nDid 2615000 512-bit mont (constime) operations in 2000146us (1307404.6 ops/sec) [+911.5%]\nDid 1029000 521-bit mont (constime) operations in 2000944us (514257.3 ops/sec) [+386.9%]\nDid 1246000 1024-bit mont (constime) operations in 2000899us (622720.1 ops/sec) [+1074.8%]\nDid 688000 1536-bit mont (constime) operations in 2000579us (343900.4 ops/sec) [+1107.3%]\nDid 425000 2048-bit mont (constime) operations in 2003622us (212115.9 ops/sec) [+1069.3%]\nDid 212000 3072-bit mont (constime) operations in 2004430us (105765.7 ops/sec) [+979.4%]\nDid 125000 4096-bit mont (constime) operations in 2009677us (62199.0 ops/sec) [+961.6%]\n\nIntel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz\nBefore:\nDid 781000 256-bit mont (constime) operations in 2000740us (390355.6 ops/sec)\nDid 414000 384-bit mont (constime) operations in 2000180us (206981.4 ops/sec)\nDid 258000 512-bit mont (constime) operations in 2001729us (128888.6 ops/sec)\nDid 194000 521-bit mont (constime) operations in 2008814us (96574.4 ops/sec)\nDid 79000 1024-bit mont (constime) operations in 2009309us (39317.0 ops/sec)\nDid 36000 1536-bit mont (constime) operations in 2003945us (17964.6 ops/sec)\nDid 21000 2048-bit mont (constime) operations in 2074987us (10120.5 ops/sec)\nDid 9040 3072-bit mont (constime) operations in 2003869us (4511.3 ops/sec)\nDid 5250 4096-bit mont (constime) operations in 2067796us (2538.9 ops/sec)\nAfter:\nDid 3496000 256-bit mont (constime) operations in 2000542us (1747526.4 ops/sec) [+347.7%]\nDid 2466000 384-bit mont (constime) operations in 2000327us (1232798.4 ops/sec) [+495.6%]\nDid 2392000 512-bit mont (constime) operations in 2000732us (1195562.4 ops/sec) [+827.6%]\nDid 908000 521-bit mont (constime) operations in 2001181us (453732.1 ops/sec) [+369.8%]\nDid 1054000 1024-bit mont (constime) operations in 2001429us (526623.7 ops/sec) [+1239.4%]\nDid 548000 1536-bit mont (constime) operations in 2002417us (273669.3 ops/sec) [+1423.4%]\nDid 339000 2048-bit mont (constime) operations in 2004127us (169151.0 ops/sec) [+1571.4%]\nDid 162000 3072-bit mont (constime) operations in 2008221us (80668.4 ops/sec) [+1688.2%]\nDid 94000 4096-bit mont (constime) operations in 2013848us (46676.8 ops/sec) [+1738.4%]\n\nIntel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz, 32-bit mode\nBefore:\nDid 335000 256-bit mont (constime) operations in 2000006us (167499.5 ops/sec)\nDid 170000 384-bit mont (constime) operations in 2010398us (84560.4 ops/sec)\nDid 102000 512-bit mont (constime) operations in 2013510us (50657.8 ops/sec)\nDid 88000 521-bit mont (constime) operations in 2022909us (43501.7 ops/sec)\nDid 27000 1024-bit mont (constime) operations in 2063490us (13084.6 ops/sec)\nDid 11760 1536-bit mont (constime) operations in 2000600us (5878.2 ops/sec)\nDid 6825 2048-bit mont (constime) operations in 2069343us (3298.1 ops/sec)\nDid 2982 3072-bit mont (constime) operations in 2090651us (1426.3 ops/sec)\nDid 1680 4096-bit mont (constime) operations in 2074824us (809.7 ops/sec)\nAfter:\nDid 1559000 256-bit mont (constime) operations in 2000884us (779155.6 ops/sec) [+365.2%]\nDid 940000 384-bit mont (constime) operations in 2001511us (469645.2 ops/sec) [+455.4%]\nDid 608000 512-bit mont (constime) operations in 2000380us (303942.3 ops/sec) [+500.0%]\nDid 439000 521-bit mont (constime) operations in 2004282us (219031.1 ops/sec) [+403.5%]\nDid 180000 1024-bit mont (constime) operations in 2005427us (89756.4 ops/sec) [+586.0%]\nDid 85000 1536-bit mont (constime) operations in 2017009us (42141.6 ops/sec) [+616.9%]\nDid 49000 2048-bit mont (constime) operations in 2035401us (24073.9 ops/sec) [+629.9%]\nDid 22000 3072-bit mont (constime) operations in 2047404us (10745.3 ops/sec) [+653.3%]\nDid 12642 4096-bit mont (constime) operations in 2094210us (6036.6 ops/sec) [+645.5%]\n\nPixel 5A:\nBefore:\nDid 483000 256-bit mont (constime) operations in 2001460us (241323.8 ops/sec)\nDid 279000 384-bit mont (constime) operations in 2004682us (139174.2 ops/sec)\nDid 198000 512-bit mont (constime) operations in 2003995us (98802.6 ops/sec)\nDid 141000 521-bit mont (constime) operations in 2006305us (70278.4 ops/sec)\nDid 62000 1024-bit mont (constime) operations in 2022138us (30660.6 ops/sec)\nDid 29000 1536-bit mont (constime) operations in 2007150us (14448.3 ops/sec)\nDid 17376 2048-bit mont (constime) operations in 2044894us (8497.3 ops/sec)\nDid 7686 3072-bit mont (constime) operations in 2011537us (3821.0 ops/sec)\nDid 4620 4096-bit mont (constime) operations in 2048780us (2255.0 ops/sec)\nAfter:\nDid 1187000 256-bit mont (constime) operations in 2000099us (593470.6 ops/sec) [+145.9%]\nDid 794000 384-bit mont (constime) operations in 2002162us (396571.3 ops/sec) [+184.9%]\nDid 658000 512-bit mont (constime) operations in 2002808us (328538.7 ops/sec) [+232.5%]\nDid 373000 521-bit mont (constime) operations in 2005135us (186022.4 ops/sec) [+164.7%]\nDid 231000 1024-bit mont (constime) operations in 2008117us (115033.1 ops/sec) [+275.2%]\nDid 112000 1536-bit mont (constime) operations in 2003151us (55911.9 ops/sec) [+287.0%]\nDid 66000 2048-bit mont (constime) operations in 2022295us (32636.2 ops/sec) [+284.1%]\nDid 30000 3072-bit mont (constime) operations in 2006199us (14953.7 ops/sec) [+291.4%]\nDid 17182 4096-bit mont (constime) operations in 2017938us (8514.6 ops/sec) [+277.6%]\n\nPixel 5A, 32-bit mode:\nBefore:\nDid 124000 256-bit mont (constime) operations in 2013082us (61597.1 ops/sec)\nDid 66000 384-bit mont (constime) operations in 2024604us (32599.0 ops/sec)\nDid 40000 512-bit mont (constime) operations in 2018560us (19816.1 ops/sec)\nDid 38000 521-bit mont (constime) operations in 2043776us (18593.0 ops/sec)\nDid 11466 1024-bit mont (constime) operations in 2010767us (5702.3 ops/sec)\nDid 5481 1536-bit mont (constime) operations in 2061892us (2658.2 ops/sec)\nDid 3171 2048-bit mont (constime) operations in 2075359us (1527.9 ops/sec)\nDid 1407 3072-bit mont (constime) operations in 2032032us (692.4 ops/sec)\nDid 819 4096-bit mont (constime) operations in 2070367us (395.6 ops/sec)\nAfter:\nDid 718000 256-bit mont (constime) operations in 2000496us (358911.0 ops/sec) [+482.7%]\nDid 424000 384-bit mont (constime) operations in 2000523us (211944.6 ops/sec) [+550.2%]\nDid 401000 512-bit mont (constime) operations in 2000933us (200406.5 ops/sec) [+911.3%]\nDid 205000 521-bit mont (constime) operations in 2004212us (102284.6 ops/sec) [+450.1%]\nDid 153000 1024-bit mont (constime) operations in 2004644us (76322.8 ops/sec) [+1238.5%]\nDid 78000 1536-bit mont (constime) operations in 2007510us (38854.1 ops/sec) [+1361.6%]\nDid 47000 2048-bit mont (constime) operations in 2018015us (23290.2 ops/sec) [+1424.3%]\nDid 22848 3072-bit mont (constime) operations in 2079082us (10989.5 ops/sec) [+1487.1%]\nDid 13156 4096-bit mont (constime) operations in 2067424us (6363.5 ops/sec) [+1508.6%]\n\nBug: 316\nChange-Id: I402df85170cae780442225eaa879884e707ffa86\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/60686\nReviewed-by: Adam Langley \u003cagl@google.com\u003e\nCommit-Queue: David Benjamin \u003cdavidben@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "ca3e3e7905c4abc8d83b8164f6a9c857d818cdf1",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/internal.h",
      "new_id": "7b939de5e7f6ceeeec6fda5c41da4cb7a6a35261",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/internal.h"
    },
    {
      "type": "modify",
      "old_id": "92bfa5e327143837649aabc336149ad4ff6d14e1",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/montgomery.c",
      "new_id": "a5df5ff4b061235e4d4f33c98433b001d8bde5e1",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/montgomery.c"
    },
    {
      "type": "modify",
      "old_id": "137af1dd65c769e5429002a419b8a610fb63e629",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/montgomery_inv.c",
      "new_id": "f496fe9a7d28746170edd8ecb81296d10c293eed",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/montgomery_inv.c"
    }
  ]
}
