crypton 2.2.1 → 2.2.2
raw patch · 19 files changed
+2178/−116 lines, 19 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- CHANGELOG.md +34/−0
- Crypto/Number/ModArithmetic.hs +61/−1
- Crypto/System/CPU.hs +12/−2
- README.md +60/−54
- cbits/crypton_bignum.h +25/−6
- cbits/crypton_cpu.c +57/−0
- cbits/crypton_powm.c +263/−24
- cbits/crypton_powm.h +22/−0
- cbits/s2n/README.md +85/−2
- cbits/s2n/arm/bignum_montifier.S +462/−0
- cbits/s2n/import.sh +16/−1
- cbits/s2n/x86_att/bignum_montifier.S +545/−0
- cbits/s2n/x86_att/bignum_mul.S +160/−0
- cbits/s2n/x86_att/bignum_sqr.S +190/−0
- cbits/tests/ct/ct_powm.c +30/−1
- cbits/tests/ct/known.txt +23/−2
- cbits/tests/ct/run.sh +87/−8
- cbits/tests/ppc8_diff.c +16/−0
- crypton.cabal +30/−15
CHANGELOG.md view
@@ -1,5 +1,39 @@ # CHANGELOG for crypton +## 2.2.2++**crypton builds on an Intel Mac again.** From 2.1.2 onwards, Apple's+assembler rejected one of the vendored RSA assembly files, so the default+configuration did not build on x86-64 macOS. With an older release,+`-f-support_s2n_bignum` works around it.++* doc: the Ed25519 verify step was the AVX2 flag, and the tables move to 2.2.1+ [#318](https://github.com/kazu-yamamoto/crypton/pull/318)+* test: the window the exponentiation walks in, and the macro that hid it+ [#319](https://github.com/kazu-yamamoto/crypton/pull/319)+* perf: the Montgomery constant in assembly, on both architectures+ [#320](https://github.com/kazu-yamamoto/crypton/pull/320)+* perf: verification need not hide an exponent that is public+ [#321](https://github.com/kazu-yamamoto/crypton/pull/321)+* doc: the generic AArch64 routines, measured at last+ [#322](https://github.com/kazu-yamamoto/crypton/pull/322)+* doc: a VM's CPUID is not the hardware: two descriptions that said otherwise+ [#323](https://github.com/kazu-yamamoto/crypton/pull/323)+* test: switches to assume what CPUID hides, for testing only+ [#324](https://github.com/kazu-yamamoto/crypton/pull/324)+* perf: RSA-3072's halves through s2n-bignum on x86-64+ [#325](https://github.com/kazu-yamamoto/crypton/pull/325)+* perf: 3072- and 4096-bit secure exponentiation through s2n-bignum+ [#326](https://github.com/kazu-yamamoto/crypton/pull/326)+* test: the two AES differential tests, in CI+ [#327](https://github.com/kazu-yamamoto/crypton/pull/327)+* perf: s2n-bignum on x86-64 Windows+ [#328](https://github.com/kazu-yamamoto/crypton/pull/328)+* fix: crypton builds on an Intel Mac again+ [#329](https://github.com/kazu-yamamoto/crypton/pull/329)+* ci: link with the Command Line Tools on macOS+ [#330](https://github.com/kazu-yamamoto/crypton/pull/330)+ ## 2.2.1 **A binary built on one x86-64 machine runs on another again.** Since
Crypto/Number/ModArithmetic.hs view
@@ -141,6 +141,20 @@ -- what GMP's own secure exponentiation lets slip !eLen = 8 * ((numBytes e + 7) `div` 8) +-- safe, as the secure one below is: the call is tens of microseconds at RSA+-- sizes, and the hundred nanoseconds this costs over an unsafe call is+-- nothing beside holding a capability for that long in a server+foreign import ccall safe "crypton_powm_pub"+ c_powm_pub+ :: Ptr Word8+ -> Ptr Word8+ -> Word32+ -> Ptr Word8+ -> Word32+ -> Ptr Word8+ -> Word32+ -> IO CInt+ foreign import ccall safe "crypton_powm_sec" c_powm_sec :: Ptr Word8@@ -158,6 +172,14 @@ -- -- Use this function when all the parameters are public, -- otherwise 'expSafe' should be preferred.+--+-- A short exponent on an odd modulus -- RSA verification, where the exponent+-- is 65537 and comes out of the public key -- is walked a bit at a time in+-- C, squaring at each step and multiplying where a bit is set, which reads+-- the exponent and branches on it and is why this is not 'expSafe'. That+-- path is taken only where it is the faster of the two, which the C decides;+-- everywhere else, and for every longer exponent, this is GMP's windowed+-- exponentiation as it has always been. expFast :: Integer -- ^ base@@ -167,7 +189,45 @@ -- ^ modulo -> Integer -- ^ result-expFast b e m = gmpPowModInteger b e m `onGmpUnsupported` exponentiation b e m+expFast b e m+ | odd m && m > 1 && e > 0 = case expPub (b `mod` m) e m of+ Just r -> r+ Nothing -> slow+ | otherwise = slow+ where+ slow = gmpPowModInteger b e m `onGmpUnsupported` exponentiation b e m++-- | The windowless exponentiation in C, for an exponent that is not a+-- secret. 'Nothing' when the C declines, which it does on every machine+-- where what the caller already has is faster -- so this is an+-- optimisation and never the only path. The base has to be reduced and+-- the exponent positive, which the guard above sees to.+expPub :: Integer -> Integer -> Integer -> Maybe Integer+expPub b e m = unsafeDoIO $+ allocaBytes (sum widths) $ \start -> case scanl plusPtr start widths of+ (out : base : expo : modu : _) -> do+ _ <- Internal.i2ospOf b base mLen+ _ <- Internal.i2ospOf e expo eLen+ _ <- Internal.i2ospOf m modu mLen+ r <-+ c_powm_pub+ out+ base+ (fromIntegral mLen)+ expo+ (fromIntegral eLen)+ modu+ (fromIntegral mLen)+ if r == 0+ then do+ !v <- Internal.os2ip out mLen+ return (Just v)+ else return Nothing+ _ -> return Nothing+ where+ !mLen = numBytes m+ !eLen = numBytes e+ widths = [mLen, mLen, eLen, mLen] -- | @exponentiation@ computes modular exponentiation as /b^e mod m/ -- using repetitive squaring.
Crypto/System/CPU.hs view
@@ -171,8 +171,18 @@ show PPCVPMSUM = "PPCVPMSUM" show (ProcessorOption n) = "ProcessorOption " ++ show n --- | Options which have been enabled at compile time and are supported by the--- current CPU.+-- | Options which have been enabled at compile time and which this machine+-- says may be used: on x86-64 what the processor declares through CPUID, and+-- for the vector extensions only where the operating system saves their+-- state as well; elsewhere what the operating system reports of the+-- processor.+--+-- That is what crypton itself decides by, and it is not always everything+-- the core underneath executes. A guest under a hypervisor may be shown an+-- older processor model than the host's, so that it can be moved to another+-- host -- and an instruction used because it happens to run would fail+-- there. So an option missing here means crypton will not use it, not that+-- the hardware lacks it. -- -- Sorted, and without repeats. A machine reports the names of its own -- architecture only: an AArch64 processor with AES says 'ARMAES', not
README.md view
@@ -111,31 +111,31 @@ Throughput in MB/s, **higher is better**: -| | crypton 1.1.5 | crypton 2.2.0 | OpenSSL | 2.2.0 / OpenSSL |+| | crypton 1.1.5 | crypton 2.2.1 | OpenSSL | 2.2.1 / OpenSSL | | --- | ---: | ---: | ---: | ---: |-| AES-128-GCM | 1335 | **6034** | 4050 | 1.49 |-| AES-256-GCM | 1093 | **5484** | 3783 | 1.45 |-| ChaCha20-Poly1305 | 399 | 2198 | 2213 | 0.99 |-| SHA-1 | 729 | 1695 | 1673 | 1.01 |-| SHA-256 | 290 | 1585 | 1571 | 1.01 |-| SHA-512 | 449 | 770 | 752 | 1.02 |-| SHA3-256 | 109 | 422 | 425 | 0.99 |+| AES-128-GCM | 1335 | **6037** | 4053 | 1.49 |+| AES-256-GCM | 1093 | **5487** | 3786 | 1.45 |+| ChaCha20-Poly1305 | 399 | 2196 | 2214 | 0.99 |+| SHA-1 | 729 | 1681 | 1679 | 1.00 |+| SHA-256 | 290 | 1586 | 1578 | 1.00 |+| SHA-512 | 448 | 770 | 749 | 1.03 |+| SHA3-256 | 109 | 422 | 427 | 0.99 | Time per operation in microseconds, **lower is better**: -| | crypton 1.1.5 | crypton 2.2.0 | OpenSSL | OpenSSL / 2.2.0 |+| | crypton 1.1.5 | crypton 2.2.1 | OpenSSL | OpenSSL / 2.2.1 | | --- | ---: | ---: | ---: | ---: |-| X25519 | 44.63 | 28.29 | 36.52 | 1.29 |-| ECDH P-256 | 164.8 | 50.85 | 51.63 | 1.02 |-| ECDH P-384 | 2255 | **164.8** | 835.4 | 5.07 |-| Ed25519 sign | 29.27 | 18.54 | 33.63 | 1.81 |-| Ed25519 verify | 48.44 | 51.80 | 109.8 | 2.12 |-| ECDSA P-256 sign | 81.91 | 18.81 | 21.81 | 1.16 |-| ECDSA P-256 verify | 233.1 | 70.00 | 67.57 | 0.97 |-| ECDSA P-384 sign | 2287 | **300.0** | 878.7 | 2.93 |-| ECDSA P-384 verify | 2673 | **468.3** | 723.3 | 1.54 |-| RSA-2048 sign/decrypt | 759.2 | 617.8 | 659.8 | 1.07 |-| RSA-2048 verify/encrypt | 33.07 | 30.08 | 18.87 | 0.63 |+| X25519 | 44.27 | 28.55 | 36.49 | 1.28 |+| ECDH P-256 | 164.8 | 50.57 | 51.50 | 1.02 |+| ECDH P-384 | 2242 | **163.8** | 850.3 | 5.19 |+| Ed25519 sign | 29.61 | 18.62 | 33.70 | 1.81 |+| Ed25519 verify | 48.47 | 48.01 | 109.9 | 2.29 |+| ECDSA P-256 sign | 81.23 | 18.90 | 21.93 | 1.16 |+| ECDSA P-256 verify | 233.5 | 70.52 | 67.76 | 0.96 |+| ECDSA P-384 sign | 2262 | **303.6** | 895.7 | 2.95 |+| ECDSA P-384 verify | 2682 | **471.5** | 725.4 | 1.54 |+| RSA-2048 sign/decrypt | 758.2 | 616.2 | 658.3 | 1.07 |+| RSA-2048 verify/encrypt | 33.01 | 30.12 | 18.86 | 0.63 | ### AArch64 @@ -144,35 +144,35 @@ Throughput in MB/s, **higher is better**: -| | crypton 1.1.5 | crypton 2.2.0 | OpenSSL | 2.2.0 / OpenSSL |+| | crypton 1.1.5 | crypton 2.2.1 | OpenSSL | 2.2.1 / OpenSSL | | --- | ---: | ---: | ---: | ---: |-| AES-128-GCM | 129 | **11847** | 10770 | 1.10 |-| AES-256-GCM | 98 | **9770** | 9187 | 1.06 |-| ChaCha20-Poly1305 | 778 | 2312 | 2257 | 1.02 |-| SHA-1 | 1237 | 3393 | 3368 | 1.01 |-| SHA-256 | 485 | 3398 | 3370 | 1.01 |-| SHA-512 | 740 | 1882 | 1878 | 1.00 |-| SHA3-256 | 552 | 1081 | 1079 | 1.00 |+| AES-128-GCM | 127 | **11753** | 10748 | 1.09 |+| AES-256-GCM | 98 | **9834** | 9130 | 1.08 |+| ChaCha20-Poly1305 | 755 | 2232 | 2235 | 1.00 |+| SHA-1 | 1200 | 3382 | 3339 | 1.01 |+| SHA-256 | 473 | 3395 | 3309 | 1.03 |+| SHA-512 | 727 | 1854 | 1816 | 1.02 |+| SHA3-256 | 550 | 1076 | 1075 | 1.00 | Time per operation in microseconds, **lower is better**: -| | crypton 1.1.5 | crypton 2.2.0 | OpenSSL | OpenSSL / 2.2.0 |+| | crypton 1.1.5 | crypton 2.2.1 | OpenSSL | OpenSSL / 2.2.1 | | --- | ---: | ---: | ---: | ---: |-| X25519 | 17.62 | **11.92** | 15.35 | 1.29 |-| ECDH P-256 | 66.93 | **20.32** | 24.53 | 1.21 |-| ECDH P-384 | 3308 | **73.17** | 371.1 | 5.07 |-| Ed25519 sign | 13.67 | **7.967** | 13.25 | 1.66 |-| Ed25519 verify | 18.25 | 18.22 | 35.18 | 1.93 |-| ECDSA P-256 sign | 32.33 | **7.00** | 10.82 | 1.55 |-| ECDSA P-256 verify | 95.78 | **27.42** | 32.69 | 1.19 |-| ECDSA P-384 sign | 3244 | **124.3** | 394.6 | 3.17 |-| ECDSA P-384 verify | 3900 | **203.2** | 327.4 | 1.61 |-| RSA-2048 sign/decrypt | 447.6 | 458.1 | 322.0 | 0.70 |-| RSA-2048 verify/encrypt | 18.20 | 15.15 | 8.450 | 0.56 |+| X25519 | 18.15 | **11.65** | 15.38 | 1.32 |+| ECDH P-256 | 69.23 | **19.62** | 24.47 | 1.25 |+| ECDH P-384 | 3322 | **73.42** | 370.9 | 5.05 |+| Ed25519 sign | 13.27 | **7.983** | 13.24 | 1.66 |+| Ed25519 verify | 18.32 | 18.20 | 34.05 | 1.87 |+| ECDSA P-256 sign | 32.02 | **6.983** | 10.73 | 1.54 |+| ECDSA P-256 verify | 94.30 | **27.10** | 32.46 | 1.20 |+| ECDSA P-384 sign | 3256 | **124.7** | 392.4 | 3.15 |+| ECDSA P-384 verify | 3896 | **203.5** | 329.4 | 1.62 |+| RSA-2048 sign/decrypt | 448.6 | 458.6 | 320.1 | 0.70 |+| RSA-2048 verify/encrypt | 18.27 | 15.20 | 8.421 | 0.55 | ### What the numbers say -There are two changes behind the 1.1.5 column and the 2.2.0 one, not a+There are two changes behind the 1.1.5 column and the 2.2.1 one, not a single steady improvement. The first, in 2.0.0, was a rewrite: the bulk algorithms moved into C, the@@ -210,7 +210,7 @@ hiding the exponent is what the difference bought. On x86-64 that cost is more than repaid -- s2n-bignum's Montgomery multiplication is twice the C's, because the C cannot form the two carry chains `ADCX` and `ADOX` give, and-2.2.0 signs in less than 1.1.5 took while keeping what 2.0.0 gained. On+2.2.1 signs in less than 1.1.5 took while keeping what 2.0.0 gained. On AArch64 there is nothing to use: s2n-bignum has no generic routine for it, and the same five that help on x86-64 measure level with the C there, so the C stays and the gap with it. No portable C closes that gap either -- the@@ -236,7 +236,7 @@ takes a block at a time where crypton takes two. The same idea as theirs, one step further down the feature ladder; not a better one. -The 512-bit path arrived after 2.1.2, so it is in the 2.2.0 column -- but+The 512-bit path arrived after 2.1.2, so it is in the 2.2.1 column -- but neither machine in the tables above has AVX-512, so neither column shows it. On the runners that do, measured over 16 KiB in MB/s: an EPYC 9V45 (Zen 5) goes from 9616 to 14268 with it, a Xeon 6973P-C from 8095 to 9848, a Xeon@@ -264,17 +264,23 @@ and the row is still 1.66 on AArch64 and 1.81 on x86-64, so the safety is had for nothing here rather than paid for. -Ed25519 verification wants one too, for a less happy reason. On x86-64 the-row is about eight per cent slower than it was, and the step is at 2.1.8:-2.1.5, 2.1.6 and 2.1.7 all measure near 48 microseconds there, and-2.1.8, 2.1.10 and 2.2.0 all measure near 52. Nothing in Ed25519 changed-across that step. No commit touches `cbits/ed25519` between those releases,-the compiled `ed25519.o` is byte for byte the same object either side of it,-and AArch64 did not move at all. What 2.1.8 did was vendor ML-KEM and-ML-DSA, some seventy thousand lines of C that Ed25519 never calls. The same-instructions, put somewhere else; signing, which is the same file and a-different routine, is where it was. The row is still better than twice-OpenSSL's, and there is nothing in Ed25519 to fix.+Ed25519 verification wanted one too, for an unhappier reason, and 2.2.1+settles it. On x86-64 the row was about eight per cent slower from 2.1.8+onwards: 2.1.5, 2.1.6 and 2.1.7 all measure near 48 microseconds there,+2.1.8, 2.1.10 and 2.2.0 all measure near 52, and 2.2.1 is near 48 again.+Nothing in Ed25519 ever changed -- no commit touches `cbits/ed25519` across+any of it, and AArch64 never moved, the compiled `ed25519.o` there being+byte for byte the same object either side of 2.1.8. What moved was a line+in this package's cabal file. The ML-KEM and ML-DSA backends that 2.1.8+vendored want `-mavx2 -mbmi2`, and they were given as `cc-options` inside an+`if arch(x86_64)` block -- but cc-options in a conditional belong to the+component and not to the block, so every C file in the library was compiled+with AVX2 allowed, `cbits/ed25519` among them, and what the compiler made of+it that way is slower on this machine than what it replaced. Signing, which+is the same file and a different routine, is where it always was. 2.2.1+narrowed the flags to the assembly that asked for them, which is also what+stopped a binary built on one x86-64 machine from dying on another, and the+row came back. SHA-1 is in the tables because a number of protocols and file formats still ask for it, not because it is a good choice for anything new. The algorithms
cbits/crypton_bignum.h view
@@ -29,11 +29,6 @@ #define LIMB_BYTES (LIMB_BITS / 8) -/* four bits of exponent per window, so a table of sixteen and no leftover- * bits: a byte holds exactly two windows */-#define WINDOW_BITS 4-#define TABLE_SIZE (1 << WINDOW_BITS)- /* r = a - b, returning the borrow out of the top */ static inline limb_t sub_n(limb_t *r, const limb_t *a, const limb_t *b, uint32_t n) {@@ -444,7 +439,20 @@ * What the trip counts depend on is the modulus' length, which is what the * doubling loop showed as well, and nothing else about it. */-static inline void mont_r2(limb_t *r2, const limb_t *m, limb_t n0, uint32_t n,+/* s2n-bignum's bignum_montifier computes the same constant in assembly, on+ * both architectures, and is the faster of the two by a good margin -- the+ * C cannot form the carry chains it does. It is used where it is built,+ * and the C below is what everywhere else gets and what it is checked+ * against. It needs a scratch buffer of n limbs, which every caller+ * already passes. */+#if defined(CRYPTON_S2N_BIGNUM) && !defined(CRYPTON_NO_MONTIFIER) \+ && (defined(__x86_64__) || defined(__aarch64__)) && LIMB_BITS == 64+#define CRYPTON_MONTIFIER 1+extern void bignum_montifier(uint64_t k, uint64_t *z, const uint64_t *m,+ uint64_t *t);+#endif++static inline void mont_r2_c(limb_t *r2, const limb_t *m, limb_t n0, uint32_t n, limb_t *t) { uint32_t lgr = n * LIMB_BITS;@@ -475,6 +483,17 @@ if ((lgr >> (i - 1)) & 1) dbl_mod(r2, m, n, t); }+}++static inline void mont_r2(limb_t *r2, const limb_t *m, limb_t n0, uint32_t n,+ limb_t *t)+{+#ifdef CRYPTON_MONTIFIER+ (void) n0;+ bignum_montifier(n, r2, m, t);+#else+ mont_r2_c(r2, m, n0, n, t);+#endif } /* big-endian bytes into limbs, least significant limb first; anything above
cbits/crypton_cpu.c view
@@ -207,6 +207,7 @@ #include <sys/auxv.h> #elif defined(__FreeBSD__) #include <sys/auxv.h>+ #endif /*@@ -240,6 +241,41 @@ } #endif /* __powerpc64__ */ +/*+ * For testing on a machine whose CPUID says less than its core executes, and+ * for nothing else: each of these makes the detection below report a+ * feature it did not find.+ *+ * CRYPTON_CPU_TESTING_ADX BMI2 and ADX+ * CRYPTON_CPU_TESTING_SHA_NI the SHA extensions+ * CRYPTON_CPU_TESTING_VAES VAES and VPCLMULQDQ, 256-bit+ *+ * A hypervisor may show a guest an older processor model than the host's so+ * that the guest can be moved to another host, and the instructions it hides+ * then still run. That is the only place this is for: forcing a path that+ * CPUID would not choose, to measure it or to test it, on a machine where the+ * instructions have been seen to execute. Anywhere they do not, the first+ * use is a SIGILL -- which is the bug #317 fixed, made on purpose.+ *+ * What the operating system has to agree to is still asked. VAES works in+ * the wide registers, so it is assumed only where AVX2 was found, which+ * means XCR0 says those are saved; the SHA extensions still want SSSE3 and+ * SSE4.1 to have been found, as the detection asks. Nothing 512-bit can be+ * assumed: whether the operating system saves that state is not something a+ * build can promise.+ *+ * The library is never built with these, and a build that has one says so.+ */+#if defined(CRYPTON_CPU_TESTING_ADX) || defined(CRYPTON_CPU_TESTING_SHA_NI) \+ || defined(CRYPTON_CPU_TESTING_VAES)+/* The code below asks for each switch by its own name, which comes from the+ * command line and so is seen everywhere in the file. It once asked for one+ * umbrella name defined beside the first function that read it -- and the+ * capability vector the assembly reads is filled earlier in the file than+ * that, so the SHA bit never reached it, without a word from the compiler. */+#warning "CRYPTON_CPU_TESTING_*: features assumed, not detected"+#endif+ #ifdef ARCH_X86 static void cpuid(uint32_t info, uint32_t *eax, uint32_t *ebx, uint32_t *ecx, uint32_t *edx) {@@ -366,6 +402,16 @@ } if (!(f & CRYPTON_X86_AVX2)) leaf7_ebx &= ~(1u << 5);+ /* what the testing switches assumed, told to the assembly as+ * well: its SHA-256 reads the SHA bit here, not the word */+#ifdef CRYPTON_CPU_TESTING_SHA_NI+ if (f & CRYPTON_X86_SHA_NI)+ leaf7_ebx |= 1u << 29;+#endif+#ifdef CRYPTON_CPU_TESTING_ADX+ if (f & CRYPTON_X86_ADX)+ leaf7_ebx |= (1u << 8) | (1u << 19);+#endif crypton_ia32cap_P[2] = leaf7_ebx & ~IA32CAP_AVX512; resolved = 1;@@ -467,6 +513,17 @@ && !(amd && family == 0x19)) f |= CRYPTON_X86_VAES512; }+#ifdef CRYPTON_CPU_TESTING_ADX+ f |= CRYPTON_X86_ADX;+#endif+#ifdef CRYPTON_CPU_TESTING_SHA_NI+ if ((leaf1 & (1 << 9)) && (leaf1 & (1 << 19)))+ f |= CRYPTON_X86_SHA_NI;+#endif+#ifdef CRYPTON_CPU_TESTING_VAES+ if (f & CRYPTON_X86_AVX2)+ f |= CRYPTON_X86_VAES;+#endif features = f; resolved = 1; }
cbits/crypton_powm.c view
@@ -32,7 +32,9 @@ * Not on AArch64, where the C measures 5% faster than the assembly. * See cbits/s2n/README.md. */-#if defined(CRYPTON_S2N_BIGNUM) && defined(__x86_64__)+/* Not on macOS, where crypton.cabal leaves these files out: Apple's assembler+ * cannot assemble bignum_emontredc_8n. See the note beside them there. */+#if defined(CRYPTON_S2N_BIGNUM) && defined(__x86_64__) && !defined(__APPLE__) #define CRYPTON_POWM_S2N 1 #include <crypton_cpu.h> @@ -44,20 +46,53 @@ extern void bignum_ksqr_32_64(uint64_t *z, const uint64_t *x, uint64_t *t); extern uint64_t bignum_emontredc_8n(uint64_t k, uint64_t *z, const uint64_t *m, uint64_t w);+extern void bignum_mul(uint64_t k, uint64_t *z, uint64_t m, const uint64_t *x,+ uint64_t n, const uint64_t *y);+extern void bignum_sqr(uint64_t k, uint64_t *z, uint64_t n, const uint64_t *x); /* 16 limbs is 1024 bits and 32 is 2048: the halves a CRT exponentiation- * works in for RSA-2048 and RSA-4096, and the whole thing without CRT. The- * reduction wants ADX, so the answer is a run-time one. */+ * works in for RSA-2048 and RSA-4096, and the whole thing without CRT. 24+ * is 1536, the half of RSA-3072, which has no Karatsuba routine of its own+ * and is run through the 32-limb one with its operands padded -- a third+ * of that routine's work wasted, and still nearly twice the C, since the C+ * cannot form ADCX and ADOX's two carry chains at any size.+ *+ * 48 and 64 are 3072 and 4096 bits: finite-field Diffie-Hellman over the+ * RFC 7919 groups of those sizes, and RSA without CRT. There is no+ * Karatsuba routine at either, and padding to the next would be wasteful,+ * so the multiplication is s2n-bignum's schoolbook one of any size --+ * plain MUL and ADC, no ADX -- and the reduction is the same ADX one. Not+ * the gain the Karatsuba sizes have, and still well ahead of the C.+ *+ * The reduction wants ADX, so the answer is a run-time one. */ static int powm_s2n_usable(uint32_t n) {- return (n == 16 || n == 32)+ return (n == 16 || n == 24 || n == 32 || n == 48 || n == 64) && (crypton_x86_simd_features() & CRYPTON_X86_ADX) != 0; } -/* The scratch the widest of them asks for, in multiples of n: kmul_32_64- * wants 96 limbs for n = 32. */-#define POWM_S2N_SCRATCH 3+/* The scratch the routines ask for, in limbs. kmul_16_32 and kmul_32_64+ * want three times their operand. A 24-limb operand padded to 32 wants the+ * 32-limb routine's 64-limb product and its 96 limbs of its own, and the two+ * padded operands besides. */+#define POWM_S2N_PAD_Z 0+#define POWM_S2N_PAD_T 64+#define POWM_S2N_PAD_X (64 + 96)+#define POWM_S2N_PAD_Y (64 + 96 + 32)+static uint32_t powm_s2n_scratch(uint32_t n)+{+ return n == 24 ? 64 + 96 + 32 + 32 : 3 * n;+} +/* a 24-limb operand in the low limbs of 32, the rest zero: zeroed every+ * time rather than once, so that nothing else writing the scratch can+ * leave a high limb behind */+static void powm_s2n_pad(limb_t *to, const limb_t *from)+{+ memcpy(to, from, 24 * sizeof(limb_t));+ memset(to + 24, 0, 8 * sizeof(limb_t));+}+ /* bignum_emontredc_8n leaves the result in the top half of z with one more * bit as its return value, and what is there is under twice the modulus -- * the same place mont_reduce ends up, and finished the same way. */@@ -74,7 +109,19 @@ const limb_t *m, limb_t n0, uint32_t n, limb_t *z, limb_t *scratch) {- if (n == 16)+ if (n == 24) {+ /* the product of two 24-limb numbers is 48 limbs, so the top+ * sixteen of the 64 written are zero and the reduction reads+ * only what it should */+ z = scratch + POWM_S2N_PAD_Z;+ powm_s2n_pad(scratch + POWM_S2N_PAD_X, a);+ powm_s2n_pad(scratch + POWM_S2N_PAD_Y, b);+ bignum_kmul_32_64(z, scratch + POWM_S2N_PAD_X,+ scratch + POWM_S2N_PAD_Y,+ scratch + POWM_S2N_PAD_T);+ } else if (n == 48 || n == 64)+ bignum_mul(2 * n, z, n, a, n, b);+ else if (n == 16) bignum_kmul_16_32(z, a, b, scratch); else bignum_kmul_32_64(z, a, b, scratch);@@ -84,14 +131,25 @@ static void powm_s2n_sqr(limb_t *r, const limb_t *a, const limb_t *m, limb_t n0, uint32_t n, limb_t *z, limb_t *scratch) {- if (n == 16)+ if (n == 24) {+ z = scratch + POWM_S2N_PAD_Z;+ powm_s2n_pad(scratch + POWM_S2N_PAD_X, a);+ bignum_ksqr_32_64(z, scratch + POWM_S2N_PAD_X,+ scratch + POWM_S2N_PAD_T);+ } else if (n == 48 || n == 64)+ bignum_sqr(2 * n, z, n, a);+ else if (n == 16) bignum_ksqr_16_32(z, a, scratch); else bignum_ksqr_32_64(z, a, scratch); powm_s2n_finish(r, z, m, bignum_emontredc_8n(n, z, m, n0), n); } #else-#define POWM_S2N_SCRATCH 0+static uint32_t powm_s2n_scratch(uint32_t n)+{+ (void) n;+ return 0;+} #endif /* One or the other, decided once per call */@@ -126,21 +184,60 @@ mont_sqr(r, a, m, n0, n, t); } -/* Four bits of exponent per window, so a table of sixteen and no leftover- * bits: a byte holds exactly two windows.+/* Four bits of exponent per window, so a table of sixteen. *- * Five was written and measured, and is not here. A wider window saves+ * Five was written and measured and is not here. A wider window saves * multiplications -- 205 of them against 256 at 1024 bits, with the same * 1024 squarings -- and pays for it in the masked scan of a table twice as- * long, and which way that comes out depends on the machine and on which- * multiplication is running: 3.5% better on an Apple M4, about 1% worse on- * an older x86-64, and 7% worse anywhere s2n-bignum's multiplication is- * used, since that makes the scan the expensive half. Six measured level- * with five on the M4 and seven worse. What would make a wider window pay- * everywhere is a cheaper scan, not a wider window. */-#define WINDOW_BITS 4+ * long. When that was first measured the scan was the scalar one, and five+ * came out 3.5% better on an Apple M4, about 1% worse on an older x86-64 and+ * 7% worse where s2n-bignum's multiplication runs, since that makes the scan+ * the expensive half. The conclusion written here was that what would make+ * a wider window pay is a cheaper scan.+ *+ * The cheaper scan arrived twenty-one minutes later, in the AVX2 form above,+ * and nobody measured the window again. Measured since, on the machine the+ * x86-64 table is measured on and with both builds raced in one run: five is+ * 0.6% worse than four, beside 0.5% between two builds that differ in+ * nothing. So the cheaper scan did not turn it round -- the window stays at+ * four, and now for a reason that was checked after the scan rather than+ * before it.+ *+ * The width is POWM_WINDOW_BITS so that it can be measured rather than+ * argued about. It had to be renamed to be settable at all: WINDOW_BITS was+ * defined here, in cbits/crypton_ecc.c and in cbits/crypton_bignum.h, all+ * three to four, and a redefinition to the same value is silent -- so+ * -DWINDOW_BITS=5 was overridden by the header and three builds meant to+ * differ did not. cbits/tests/powm builds the walk at four, five and six+ * and requires the same answers of all three. */+#ifndef POWM_WINDOW_BITS+#define POWM_WINDOW_BITS 4+#endif+#define WINDOW_BITS POWM_WINDOW_BITS #define TABLE_SIZE (1 << WINDOW_BITS) +/* Window number k counting from the bottom, where the bottom window holds+ * the exponent's least significant WINDOW_BITS bits. The exponent is+ * big-endian bytes, and a window may straddle a byte boundary once the width+ * stops dividing eight, so this reads the two bytes it can fall across.+ *+ * Which window is being read is the loop counter, not the exponent, so the+ * shifts and the index here are public.+ */+static limb_t exp_window(const uint8_t *exp, uint32_t explen, uint32_t k)+{+ uint32_t lo = k * WINDOW_BITS; /* bit offset from the bottom */+ uint32_t byte = lo / 8, off = lo % 8;+ uint32_t v;++ if (byte >= explen)+ return 0;+ v = exp[explen - 1 - byte];+ if (off + WINDOW_BITS > 8 && byte + 1 < explen)+ v |= (uint32_t) exp[explen - 2 - byte] << 8;+ return (v >> off) & (TABLE_SIZE - 1);+}+ /* The masked scan of the table: every entry is read and a mask keeps the one * wanted, so that the address stream does not follow the exponent. At * RSA-2048's CRT size that is two kilobytes read per window, and the window@@ -205,13 +302,156 @@ } #endif +/* Modular exponentiation for an exponent that is not a secret.+ *+ * RSA verification raises a signature to the public exponent, which is in+ * the public key and is usually 65537. crypton_powm_sec below hides the+ * exponent and pays for it twice: a table of sixteen powers built before the+ * walk begins, and every entry of that table read at every window. For a+ * seventeen-bit exponent the table alone costs more than the exponentiation.+ *+ * So this one reads the exponent's bits and branches on them, squaring at+ * every step and multiplying where a bit is set. It is for public exponents+ * only, and nothing in this library may call it with a secret.+ *+ * It declines -- returning 1 without touching out -- in three cases, so a+ * caller must have something to fall back to.+ *+ * The first is a long exponent. Walking it a bit at a time costs about one+ * and a half multiplications per bit where a windowed walk costs a quarter+ * less, and the table that buys the difference pays for itself after some+ * sixty-odd bits. Past that the caller's own exponentiation is the better+ * algorithm and this one would have to grow a table to compete, which is+ * the thing it exists not to have. RSA public exponents are seventeen+ * bits; the bound is set well above them and well below where a Diffie-+ * Hellman or DSA exponent starts.+ *+ * The second is a machine where s2n-bignum's Montgomery multiplication does+ * not run. There the multiplication here is the C one, which is not faster+ * than what the caller already has, so there is nothing to take over. That+ * was written as an expectation and has since been measured: on an Apple+ * M4, verification through here and through GMP come out level, the+ * difference no larger than between two rows neither of them touches.+ * The third is every size but 2048 bits, where the assembly runs and GMP is+ * faster all the same; see powm_pub_wanted.+ *+ * Define CRYPTON_POWM_PUB_ALWAYS to make it accept anyway: the differential+ * test builds that way, so that this arithmetic is exercised on the+ * machines the assembly never reaches.+ */+#define POWM_PUB_MAX_EXP_BYTES 8++/* Which sizes this is worth taking at is not which sizes the assembly runs+ * at. Against GMP, which is what the caller has, on an EPYC 7763 with ADX+ * on both sides: ahead at 2048 bits, and behind everywhere else measured --+ * slightly at 1024, by more at 1536, and by more again at 3072 and 4096,+ * which is the size where GMP's own setup and multiplication are the better+ * pair. So 2048 alone, which is RSA-2048's modulus and the size nearly+ * every RSA public key has. It once took every size the assembly ran at,+ * on the strength of 2048 alone, and was slower than GMP at 1024. */+static int powm_pub_wanted(uint32_t n)+{+#if defined(CRYPTON_POWM_PUB_ALWAYS)+ return n > 0;+#elif defined(CRYPTON_POWM_S2N)+ return n == 32 && powm_s2n_usable(n);+#else+ (void) n;+ return 0;+#endif+}++int crypton_powm_window_bits(void)+{+ return WINDOW_BITS;+}++int crypton_powm_pub(uint8_t *out,+ const uint8_t *base, uint32_t baselen,+ const uint8_t *exp, uint32_t explen,+ const uint8_t *mod, uint32_t modlen)+{+ uint32_t n = (modlen + LIMB_BYTES - 1) / LIMB_BYTES;+ uint32_t words = (6 + 2) * n + powm_s2n_scratch(n);+ limb_t *space, *m, *r2, *acc, *tmp, *bm, *one, *t, *scratch, n0;+ uint32_t top, i;+ int s2n = 0;++ if (modlen == 0 || n == 0 || (mod[modlen - 1] & 1) == 0)+ return 1;+ if (explen > POWM_PUB_MAX_EXP_BYTES)+ return 1;+ if (!powm_pub_wanted(n))+ return 1;+#ifdef CRYPTON_POWM_S2N+ s2n = powm_s2n_usable(n);+#endif++ /* the exponent's top set bit, counted from the bottom. An exponent of+ * zero is left to the caller, whose answer for it is already right. */+ top = explen * 8;+ while (top > 0 &&+ ((exp[explen - 1 - (top - 1) / 8] >> ((top - 1) % 8)) & 1) == 0)+ top--;+ if (top == 0)+ return 1;++ space = calloc(words, sizeof(limb_t));+ if (space == NULL)+ return 1;+ m = space;+ r2 = m + n;+ acc = r2 + n;+ tmp = acc + n;+ bm = tmp + n;+ one = bm + n;+ t = one + n;+ scratch = t + 2 * n;++ if (from_be(m, n, mod, modlen) != 0)+ goto fail;+ n0 = mont_n0(m[0]);+ mont_r2(r2, m, n0, n, t);++ /* the base into Montgomery form. The accumulator starts there rather+ * than at one, because the exponent's top bit is a one by+ * construction and the first squaring would be of one. */+ if (from_be(tmp, n, base, baselen) != 0)+ goto fail;+ powm_mul(bm, tmp, r2, m, n0, n, t, scratch, s2n);+ memcpy(acc, bm, n * sizeof(limb_t));++ for (i = top - 1; i > 0; i--) {+ limb_t *swap;++ powm_sqr(tmp, acc, m, n0, n, t, scratch, s2n);+ swap = acc; acc = tmp; tmp = swap;+ if ((exp[explen - 1 - (i - 1) / 8] >> ((i - 1) % 8)) & 1) {+ powm_mul(tmp, acc, bm, m, n0, n, t, scratch, s2n);+ swap = acc; acc = tmp; tmp = swap;+ }+ }++ /* out of Montgomery form */+ one[0] = 1;+ powm_mul(tmp, acc, one, m, n0, n, t, scratch, s2n);+ to_be(out, modlen, tmp, n);++ free(space);+ return 0;++fail:+ free(space);+ return 1;+}+ int crypton_powm_sec(uint8_t *out, const uint8_t *base, uint32_t baselen, const uint8_t *exp, uint32_t explen, const uint8_t *mod, uint32_t modlen) { uint32_t n = (modlen + LIMB_BYTES - 1) / LIMB_BYTES;- uint32_t words = (TABLE_SIZE + 7 + POWM_S2N_SCRATCH) * n;+ uint32_t words = (TABLE_SIZE + 7) * n + powm_s2n_scratch(n); limb_t *space, *m, *r2, *acc, *sel, *prod, *table, *t, *scratch, n0; uint32_t i, j, k; int s2n = 0;@@ -259,9 +499,8 @@ memcpy(acc, table, n * sizeof(limb_t)); - for (i = explen * 2; i > 0; i--) {- uint32_t nib = i - 1;- limb_t w = (exp[explen - 1 - nib / 2] >> (4 * (nib % 2))) & 0xf;+ for (i = (explen * 8 + WINDOW_BITS - 1) / WINDOW_BITS; i > 0; i--) {+ limb_t w = exp_window(exp, explen, i - 1); /* squaring into the other buffer and swapping the two saves a * copy of the modulus' width every time; which of the three
cbits/crypton_powm.h view
@@ -20,4 +20,26 @@ const uint8_t *exp, uint32_t explen, const uint8_t *mod, uint32_t modlen); +/* The same, for an exponent that is not a secret: it reads the exponent's+ * bits and branches on them. Nothing in this library may call it with a+ * secret exponent.+ *+ * It declines -- returning 1 with out untouched -- whenever it is not the+ * faster of the two things the caller could do: for an exponent of more+ * than eight bytes, where a windowed walk is the better algorithm;+ * everywhere the vendored assembly's Montgomery multiplication does not+ * run; and at every modulus size but 2048 bits, where GMP was measured the+ * faster even with the assembly. So a caller must have something to fall+ * back to.+ */+int crypton_powm_pub(uint8_t *out,+ const uint8_t *base, uint32_t baselen,+ const uint8_t *exp, uint32_t explen,+ const uint8_t *mod, uint32_t modlen);++/* The window the secure exponentiation walks the exponent in, so that a+ * build which did not take -DPOWM_WINDOW_BITS cannot pass for one that+ * did. */+int crypton_powm_window_bits(void);+ #endif
cbits/s2n/README.md view
@@ -67,7 +67,34 @@ | multiplication | 0.4832 us | **0.2479** | | square | 0.3984 | **0.1994** | -**Nothing is vendored for AArch64**, where the same five routines measure level+### The Montgomery constant++`bignum_montifier` is vendored for **both** architectures. It is the one+routine here that is not about a particular curve or a particular size: every+modular exponentiation and every setup in `crypton_ecc.c` starts by computing+R^2 mod m, and this computes it. crypton's C climbs to it by a+binary ladder of Montgomery squarings -- log2 of the modulus' bits of them,+eleven at 2048 -- and the assembly is between two and three and a half times+faster, the gap being the carry chains again:++| | C | s2n-bignum |+| --- | ---: | ---: |+| M4, 1024 bits | 1.853 us | **0.771** |+| M4, 2048 bits | 5.835 | **2.407** |+| an Intel x86-64, 1024 bits | 6.145 | **1.995** |+| an Intel x86-64, 2048 bits | 23.332 | **6.852** |++A CRT signature computes it twice, so an RSA-2048 private operation on the+EPYC 7763 goes from 613.5 to 606.4 microseconds -- a little over one per+cent, which is all a constant computed twice out of some two and a half+thousand multiplications can be. It is worth much more than that to anything+whose exponent is short, which is why it is here: see `crypton_powm.c`.++The two agree bit for bit; `cbits/tests/powm` requires it at six widths, with+moduli that fill their limbs and moduli that do not, and a build without the+assembly (`-DCRYPTON_NO_MONTIFIER`) is what it is checked against.++**None of the five above is vendored for AArch64**, where they measure level with the C. That took three attempts to establish, and the first two were wrong in opposite directions: a reading when the x86-64 routines went in put the C 5% ahead, and one on 2026-09-26 put the assembly 4% ahead. Both were@@ -91,10 +118,66 @@ the window is worth, and why it is four and not five, is in `cbits/crypton_powm.c` beside the constant. +## Windows++x86-64 Windows takes the assembly as every other x86-64 does. Two things+stood in the way, and neither is fixed in a vendored file:++* **The ELF directives.** Each file ends its symbols with `.type` and+ `.size`, which the COFF assemblers refuse -- mingw's gas says "junk at end+ of line" after a warning, clang says "expected absolute expression".+ There is nothing in a PE object for them to say, so on `_WIN32` they are+ emptied, as upstream already does for Mach-O.+* **The calling convention.** Each file carries a prologue that moves+ Microsoft's argument registers into System V's, under `WINDOWS_ABI`, which+ upstream leaves to the build to define. On `_WIN32` it is defined.++Both are done in `x86_att/_internal_s2n_bignum_x86_att.h`, which is crypton's+and not upstream's. Every vendored file includes that name in quotes, and a+quoted include looks first beside the file that asks for it, so this is the+one each gets; it hands on to upstream's in `include/` by a relative path.+**It must not be removed as an upstream file that went missing**: without it+Windows does not assemble. On Linux and macOS it changes nothing -- the+objects are byte for byte what they were without it.++Not `#include_next`, which is the obvious way to hand on: clang, finding this+header beside the file that asked for it, starts that search from the top+and finds this header again, without end.++Windows on ARM keeps the C. The AArch64 files have the same directives and+would want the same header, and there is no runner to check one.+ ## What is not here s2n-bignum has only x86-64 and AArch64, so crypton's C stays and is what-every other architecture uses. `p384_montjscalarmul` and `p521_jscalarmul`+every other architecture uses.++Its `generic` directory holds a complete variable-size bignum library on both+architectures -- `bignum_montmul`, `bignum_montredc`, `bignum_emontredc`,+`bignum_modinv` and a whole `bignum_modexp` -- and only `bignum_montifier` is+taken from it. **The rest was measured on an M4 and is slower than what is+here**, which is why it stays out; they agree with crypton's answers in every+case first, so both were computing the same thing.++| nanoseconds, AArch64 | C | s2n-bignum |+| --- | ---: | ---: |+| Montgomery multiply, 1024 bits | **171.7** | 227.9 |+| Montgomery multiply, 2048 bits | **649.6** | 870.3 |+| Montgomery square, 1024 bits | **157.3** | 202.6 |+| Montgomery square, 2048 bits | **539.2** | 870.8 |++That is the inline assembly above doing its job: four limbs to an iteration+with two carry chains, where a size-parametric routine takes them one at a+time. `bignum_modexp`, which would have replaced `crypton_powm_sec` outright,+loses by more again -- 421.0 microseconds against 246.4 at 1024 bits and 3578+against 1534 at 2048 -- because it has that multiplication inside it and no+window, so it pays about twice the multiplications as well.++The README there says every function is written in a constant-time style, with+one named exception that is none of these, though it also says that unlike+functional correctness this is not machine-checked.++`p384_montjscalarmul` and `p521_jscalarmul` have no affine wrapper upstream; crypton's is in `cbits/p256/p256_s2n.c`'s sibling for those curves. There is no fixed-base routine for P-384 or P-521 at all, so signing on those curves keeps crypton's comb.
+ cbits/s2n/arm/bignum_montifier.S view
@@ -0,0 +1,462 @@+// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.+// SPDX-License-Identifier: Apache-2.0 OR ISC OR MIT-0++// ----------------------------------------------------------------------------+// Compute "montification" constant z := 2^{128k} mod m+// Input m[k]; output z[k]; temporary buffer t[>=k]+//+// extern void bignum_montifier(uint64_t k, uint64_t *z, const uint64_t *m,+// uint64_t *t);+//+// The last argument points to a temporary buffer t that should have size >= k.+// This is called "montifier" because given any other k-digit number x,+// whether or not it's reduced modulo m, it can be mapped to its Montgomery+// representation (2^{64k} * x) mod m just by Montgomery multiplication by z.+//+// Standard ARM ABI: X0 = k, X1 = z, X2 = m, X3 = t+// ----------------------------------------------------------------------------++#include "_internal_s2n_bignum_arm.h"++ S2N_BN_SYM_VISIBILITY_DIRECTIVE(bignum_montifier)+ S2N_BN_FUNCTION_TYPE_DIRECTIVE(bignum_montifier)+ S2N_BN_SYM_PRIVACY_DIRECTIVE(bignum_montifier)+ .text+ .balign 4++#define k x0+#define z x1+#define m x2+#define t x3++// Some variables+// Modular inverse w is aliased to i, but we never use them together++#define i x4+#define w x4+#define j x5+#define h x6+#define a x7+#define l x8+#define c x9+#define b x10+#define d x11++// Some aliases for the values b and d++#define r x10+#define q x11+++S2N_BN_SYMBOL(bignum_montifier):+ CFI_START++// If k = 0 the whole operation is trivial++ cbz k, Lbignum_montifier_end++// Copy the input m into the temporary buffer t. The temporary register+// c matters since we want it to hold the highest digit, ready for the+// normalization phase.++ mov i, xzr+Lbignum_montifier_copyinloop:+ ldr c, [m, i, lsl #3]+ str c, [t, i, lsl #3]+ add i, i, #1+ cmp i, k+ bcc Lbignum_montifier_copyinloop++// Do a rather stupid but constant-time digit normalization, conditionally+// shifting left (k-1) times based on whether the top word is zero.+// With careful binary striding this could be O(k*log(k)) instead of O(k^2)+// while still retaining the constant-time style.+// The "cmp c, xzr" sets the zeroness predicate (ZF) for the entire inner loop++ subs i, k, #1+ beq Lbignum_montifier_normalized+Lbignum_montifier_normloop:+ mov j, xzr+ cmp c, xzr+ mov a, xzr+Lbignum_montifier_shufloop:+ mov c, a+ ldr a, [t, j, lsl #3]+ csel c, c, a, eq+ str c, [t, j, lsl #3]+ add j, j, #1+ sub d, j, k+ cbnz d, Lbignum_montifier_shufloop+ subs i, i, #1+ bne Lbignum_montifier_normloop++// We now have the top digit nonzero, assuming the input was nonzero,+// and as per the invariant of the loop above, c holds that digit. So+// now just count c's leading zeros and shift t bitwise that many bits.++Lbignum_montifier_normalized:+ clz c, c++ mov b, xzr+ mov i, xzr+ ands xzr, c, #63+ csetm l, ne+ neg d, c+Lbignum_montifier_bitloop:+ ldr j, [t, i, lsl #3]+ lsl a, j, c+ orr a, a, b+ lsr b, j, d+ and b, b, l+ str a, [t, i, lsl #3]+ add i, i, #1+ cmp i, k+ bcc Lbignum_montifier_bitloop++// Let h be the high word of n, which in all the in-scope cases is >= 2^63.+// Now successively form q = 2^i div h and r = 2^i mod h as i goes from+// 64 to 126. We avoid just using division out of constant-time concerns+// (at the least we would need to fix up h = 0 for out-of-scope inputs) and+// don't bother with Newton-Raphson, since this stupid simple loop doesn't+// contribute much of the overall runtime at typical sizes.++ sub h, k, #1+ ldr h, [t, h, lsl #3]+ mov q, #1+ neg r, h+ mov i, #62+Lbignum_montifier_estloop:+ add q, q, q+ mov a, h+ sub a, a, r+ cmp r, a // CF <=> r >= h - r <=> 2 * r >= h+ csetm a, cs+ sub q, q, a+ add r, r, r+ and a, a, h+ sub r, r, a+ subs i, i, #1+ bne Lbignum_montifier_estloop++// Strictly speaking the above loop doesn't quite give the true remainder+// and quotient in the special case r = h = 2^63, so fix it up. We get+// q = 2^63 - 1 and r = 2^63 and really want q = 2^63 and r = 0. This is+// supererogatory, because the main property of q used below still holds+// in this case unless the initial m = 1, and then anyway the overall+// specification (congruence modulo m) holds degenerately. But it seems+// nicer to get a "true" quotient and remainder.++ cmp r, h+ csinc q, q, q, ne++// So now we have q and r with 2^126 = q * h + r (imagining r = 0 in the+// fixed-up case above: note that we never actually use the computed+// value of r below and so didn't adjust it). And we can assume the ranges+// q <= 2^63 and r < h < 2^64.+//+// The idea is to use q as a first quotient estimate for a remainder+// of 2^{p+62} mod n, where p = 64 * k. We have, splitting n into the+// high and low parts h and l:+//+// 2^{p+62} - q * n = 2^{p+62} - q * (2^{p-64} * h + l)+// = 2^{p+62} - (2^{p-64} * (q * h) + q * l)+// = 2^{p+62} - 2^{p-64} * (2^126 - r) - q * l+// = 2^{p-64} * r - q * l+//+// Note that 2^{p-64} * r < 2^{p-64} * h <= n+// and also q * l < 2^63 * 2^{p-64} = 2^{p-1} <= n+// so |diff| = |2^{p-64} * r - q * l| < n.+//+// If in fact diff >= 0 then it is already 2^{p+62} mod n.+// otherwise diff + n is the right answer.+//+// To (maybe?) make the computation slightly easier we actually flip+// the sign and compute d = q * n - 2^{p+62}. Then the answer is either+// -d (when negative) or n - d; in either case we effectively negate d.+// This negating tweak in fact spoils the result for cases where+// 2^{p+62} mod n = 0, when we get n instead. However the only case+// where this can happen is m = 1, when the whole spec holds trivially,+// and actually the remainder of the logic below works anyway since+// the latter part of the code only needs a congruence for the k-digit+// result, not strict modular reduction (the doublings will maintain+// the non-strict inequality).++ mov c, xzr+ adds i, xzr, xzr+Lbignum_montifier_mulloop:+ ldr a, [t, i, lsl #3]+ mul l, q, a+ adcs l, l, c+ umulh c, q, a+ str l, [z, i, lsl #3]+ add i, i, #1+ sub a, i, k+ cbnz a, Lbignum_montifier_mulloop++ adc c, c, xzr+ mov a, #0x4000000000000000+ subs c, c, a+ csetm q, cs++// Now do [c] * n - d for our final answer++ subs i, xzr, xzr+Lbignum_montifier_remloop:+ ldr a, [t, i, lsl #3]+ ldr b, [z, i, lsl #3]+ and a, a, q+ sbcs a, a, b+ str a, [z, i, lsl #3]+ add i, i, #1+ sub a, i, k+ cbnz a, Lbignum_montifier_remloop++// Now still need to do a couple of modular doublings to get us all the+// way up to 2^{p+64} == r from the initial 2^{p+62} == r (mod n).++ mov c, xzr+ subs j, xzr, xzr+Lbignum_montifier_dubloop1:+ ldr a, [z, j, lsl #3]+ extr c, a, c, #63+ ldr b, [t, j, lsl #3]+ sbcs c, c, b+ str c, [z, j, lsl #3]+ mov c, a+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_dubloop1+ lsr c, c, #63+ sbc c, c, xzr+ adds j, xzr, xzr+Lbignum_montifier_corrloop1:+ ldr a, [z, j, lsl #3]+ ldr b, [t, j, lsl #3]+ and b, b, c+ adcs a, a, b+ str a, [z, j, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_corrloop1++// This is not exactly the same: we also copy output to t giving the+// initialization t_1 = r == 2^{p+64} mod n for the main loop next.++ mov c, xzr+ subs j, xzr, xzr+Lbignum_montifier_dubloop2:+ ldr a, [z, j, lsl #3]+ extr c, a, c, #63+ ldr b, [t, j, lsl #3]+ sbcs c, c, b+ str c, [z, j, lsl #3]+ mov c, a+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_dubloop2+ lsr c, c, #63+ sbc c, c, xzr+ adds j, xzr, xzr+Lbignum_montifier_corrloop2:+ ldr a, [z, j, lsl #3]+ ldr b, [t, j, lsl #3]+ and b, b, c+ adcs a, a, b+ str a, [z, j, lsl #3]+ str a, [t, j, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_corrloop2++// We then successively generate (k+1)-digit values satisfying+// t_i == 2^{p+64*i} mod n, each of which is stored in h::t. Finish+// initialization by zeroing h initially++ mov h, xzr++// Then if t_i = 2^{p} * h + l+// we have t_{i+1} == 2^64 * t_i+// = (2^{p+64} * h) + (2^64 * l)+// == r * h + l<<64+// Do this 2*k more times so we end up == 2^{192*k+64}, one more than we want+//+// Writing B = 2^{64k}, the possible correction of adding r, which for+// a (k+1)-digit result is equivalent to subtracting q = 2^{64*(k+1)} - r+// would give the overall worst-case value minus q of+// [ B * (B^k - 1) + (B - 1) * r ] - [B^{k+1} - r]+// = B * (r - 1) < B^{k+1} so we keep inside k+1 digits as required.+//+// This implementation makes the shift implicit by starting b with the+// "previous" digit (initially 0) to offset things by 1.++ add i, k, k+Lbignum_montifier_modloop:+ mov j, xzr+ mov b, xzr+ adds c, xzr, xzr+Lbignum_montifier_cmaloop:+ ldr a, [z, j, lsl #3]+ mul l, h, a+ adcs b, b, c+ umulh c, h, a+ adc c, c, xzr+ adds l, b, l+ ldr b, [t, j, lsl #3]+ str l, [t, j, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_cmaloop++ adcs h, b, c++ csetm l, cs++ adds j, xzr, xzr+Lbignum_montifier_oaloop:+ ldr a, [t, j, lsl #3]+ ldr b, [z, j, lsl #3]+ and b, b, l+ adcs a, a, b+ str a, [t, j, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_oaloop+ adc h, h, xzr++ subs i, i, #1+ bne Lbignum_montifier_modloop++// Compute the negated modular inverse w (same register as i, not used again).++ ldr a, [m]+ lsl w, a, #2+ sub w, a, w+ eor w, w, #2+ mov l, #1+ madd c, a, w, l+ mul b, c, c+ madd w, c, w, w+ mul c, b, b+ madd w, b, w, w+ mul b, c, c+ madd w, c, w, w+ madd w, b, w, w++// Now do one almost-Montgomery reduction w.r.t. the original m+// which lops off one 2^64 from the congruence and, with the usual+// almost-Montgomery correction, gets us back inside k digits for+// the end result.++ ldr b, [t]+ mul d, b, w++ mul l, d, a+ umulh c, d, a+ mov j, #1+ sub a, k, #1+ adds xzr, b, l+ cbz a, Lbignum_montifier_amontend++Lbignum_montifier_amontloop:+ ldr a, [m, j, lsl #3]+ ldr b, [t, j, lsl #3]+ mul l, d, a+ adcs b, b, c+ umulh c, d, a+ adc c, c, xzr+ adds b, b, l+ sub a, j, #1+ str b, [t, a, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_amontloop+Lbignum_montifier_amontend:+ adcs h, h, c+ csetm l, cs+ sub a, k, #1+ str h, [t, a, lsl #3]++ subs j, xzr, xzr+Lbignum_montifier_osloop:+ ldr a, [t, j, lsl #3]+ ldr b, [m, j, lsl #3]+ and b, b, l+ sbcs a, a, b+ str a, [z, j, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_osloop++// So far, the code(basically a variant of bignum_amontifier) has produced+// a k-digit value z == 2^{192k} (mod m), not necessarily fully reduced mod m.+// We now do a short Montgomery reduction (similar to bignum_demont) so that+// we achieve full reduction mod m while lopping 2^{64k} off the congruence.+// We recycle h as the somewhat strangely-named outer loop counter.++ mov h, k++Lbignum_montifier_montouterloop:+ ldr b, [z]+ mul d, b, w+ ldr a, [m]+ mul l, d, a+ umulh c, d, a+ mov j, #1+ sub a, k, #1+ adds xzr, b, l+ cbz a, Lbignum_montifier_montend+Lbignum_montifier_montloop:+ ldr a, [m, j, lsl #3]+ ldr b, [z, j, lsl #3]+ mul l, d, a+ adcs b, b, c+ umulh c, d, a+ adc c, c, xzr+ adds b, b, l+ sub a, j, #1+ str b, [z, a, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_montloop+Lbignum_montifier_montend:+ adc c, c, xzr+ sub a, k, #1+ str c, [z, a, lsl #3]++ subs h, h, #1+ bne Lbignum_montifier_montouterloop++// Now do a comparison of z with m to set a final correction mask+// indicating that z >= m and so we need to subtract m.++ subs j, xzr, xzr+Lbignum_montifier_cmploop:+ ldr a, [z, j, lsl #3]+ ldr b, [m, j, lsl #3]+ sbcs xzr, a, b+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_cmploop+ csetm h, cs++// Now do a masked subtraction of m for the final reduced result.++ subs j, xzr, xzr+Lbignum_montifier_corrloop:+ ldr a, [z, j, lsl #3]+ ldr b, [m, j, lsl #3]+ and b, b, h+ sbcs a, a, b+ str a, [z, j, lsl #3]+ add j, j, #1+ sub a, j, k+ cbnz a, Lbignum_montifier_corrloop++Lbignum_montifier_end:+ CFI_RET++S2N_BN_SIZE_DIRECTIVE(bignum_montifier)++#if defined(__linux__) && defined(__ELF__)+.section .note.GNU-stack,"",%progbits+#endif
cbits/s2n/import.sh view
@@ -20,7 +20,10 @@ git clone -q "$REPO" "$TMP/s2n" git -C "$TMP/s2n" checkout -q "$REV" -# The headers every vendored file includes.+# The headers every vendored file includes. Not x86_att/'s own header of+# the same name, which is crypton's -- it makes the x86-64 files assemble on+# Windows and hands on to this one; see README.md. Nothing here copies into+# that name, and nothing should. for h in _internal_s2n_bignum_arm.h _internal_s2n_bignum_x86_att.h; do cp "$TMP/s2n/include/$h" "$HERE/include/$h" done@@ -107,6 +110,18 @@ take_x86 fastmul bignum_kmul_32_64 take_x86 fastmul bignum_ksqr_32_64 take_x86 fastmul bignum_emontredc_8n+# and, for the sizes there is no Karatsuba routine for, the schoolbook+# multiplication and squaring of any size, which bignum_emontredc_8n then+# reduces as it reduces the others+take_x86 generic bignum_mul+take_x86 generic bignum_sqr++# R^2 mod m, which every exponentiation and every setup in crypton_ecc.c+# begins with. Both architectures: the C climbs to it by a ladder of+# Montgomery squarings and this is faster on both. Taken from upstream's+# main when it went in rather than by this script, which is why it was+# missing here; it is the same file at the COMMIT above.+take generic bignum_montifier git -C "$TMP/s2n" rev-parse HEAD > "$HERE/COMMIT" echo "imported $(cat "$HERE/COMMIT")"
+ cbits/s2n/x86_att/bignum_montifier.S view
@@ -0,0 +1,545 @@+// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.+// SPDX-License-Identifier: Apache-2.0 OR ISC OR MIT-0++// ----------------------------------------------------------------------------+// Compute "montification" constant z := 2^{128k} mod m+// Input m[k]; output z[k]; temporary buffer t[>=k]+//+// extern void bignum_montifier(uint64_t k, uint64_t *z, const uint64_t *m,+// uint64_t *t);+//+// The last argument points to a temporary buffer t that should have size >= k.+// This is called "montifier" because given any other k-digit number x,+// whether or not it's reduced modulo m, it can be mapped to its Montgomery+// representation (2^{64k} * x) mod m just by Montgomery multiplication by z.+//+// Standard x86-64 ABI: RDI = k, RSI = z, RDX = m, RCX = t+// Microsoft x64 ABI: RCX = k, RDX = z, R8 = m, R9 = t+// ----------------------------------------------------------------------------++#include "_internal_s2n_bignum_x86_att.h"+++ S2N_BN_SYM_VISIBILITY_DIRECTIVE(bignum_montifier)+ S2N_BN_FUNCTION_TYPE_DIRECTIVE(bignum_montifier)+ S2N_BN_SYM_PRIVACY_DIRECTIVE(bignum_montifier)+ .text+ .balign 32++#define k %rdi+#define z %rsi++// These two inputs get moved to different places since RCX and RDX are special++#define m %r12+#define t %r13++// Other variables++#define i %rbx+// Modular inverse; aliased to i, but we never use them together+#define w %rbx+#define j %rbp+// Matters that this is RAX for special use in multiplies+#define a %rax+// Matters that this is RDX for special use in multiplies+#define d %rdx+// Matters that this is RCX as CL=lo(c) is assumed in shifts+#define c %rcx+#define h %r11+#define l %r10+#define b %r9+#define n %r8++// Some aliases for the values b and n++#define q %r8+#define r %r9++#define ashort %eax+#define ishort %ebx+#define jshort %ebp+#define qshort %r8d+++S2N_BN_SYMBOL(bignum_montifier):+ CFI_START+ _CET_ENDBR++#if WINDOWS_ABI+ CFI_PUSH(%rdi)+ CFI_PUSH(%rsi)+ movq %rcx, %rdi+ movq %rdx, %rsi+ movq %r8, %rdx+ movq %r9, %rcx+#endif++// Save some additional registers for use, copy args out of RCX and RDX++ CFI_PUSH(%rbp)+ CFI_PUSH(%rbx)+ CFI_PUSH(%r12)+ CFI_PUSH(%r13)++ movq %rdx, m+ movq %rcx, t++// If k = 0 the whole operation is trivial++ testq k, k+ jz Lbignum_montifier_end++// Copy the input m into the temporary buffer t. The temporary register+// c matters since we want it to hold the highest digit, ready for the+// normalization phase.++ xorq i, i+Lbignum_montifier_copyinloop:+ movq (m,i,8), c+ movq c, (t,i,8)+ incq i+ cmpq k, i+ jc Lbignum_montifier_copyinloop++// Do a rather stupid but constant-time digit normalization, conditionally+// shifting left (k-1) times based on whether the top word is zero.+// With careful binary striding this could be O(k*log(k)) instead of O(k^2)+// while still retaining the constant-time style.+// The "neg c" sets the zeroness predicate (~CF) for the entire inner loop++ movq k, i+ decq i+ jz Lbignum_montifier_normalized+Lbignum_montifier_normloop:+ xorq j, j+ movq k, h+ negq c+ movl $0, ashort+Lbignum_montifier_shufloop:+ movq a, c+ movq (t,j,8), a+ cmovcq a, c+ movq c, (t,j,8)+ incq j+ decq h+ jnz Lbignum_montifier_shufloop+ decq i+ jnz Lbignum_montifier_normloop++// We now have the top digit nonzero, assuming the input was nonzero,+// and as per the invariant of the loop above, c holds that digit. So+// now just count c's leading zeros and shift t bitwise that many bits.+// Note that we don't care about the result of bsr for zero inputs so+// the simple xor-ing with 63 is safe.++Lbignum_montifier_normalized:++ bsrq c, c+ xorq $63, c++ xorq b, b+ xorq i, i+Lbignum_montifier_bitloop:+ movq (t,i,8), a+ movq a, j+ shldq %cl, b, a+ movq a, (t,i,8)+ movq j, b+ incq i+ cmpq k, i+ jc Lbignum_montifier_bitloop++// Let h be the high word of n, which in all the in-scope cases is >= 2^63.+// Now successively form q = 2^i div h and r = 2^i mod h as i goes from+// 64 to 126. We avoid just using division out of constant-time concerns+// (at the least we would need to fix up h = 0 for out-of-scope inputs) and+// don't bother with Newton-Raphson, since this stupid simple loop doesn't+// contribute much of the overall runtime at typical sizes.++ movq -8(t,k,8), h+ movl $1, qshort+ movq h, r+ negq r+ movl $62, ishort+Lbignum_montifier_estloop:++ addq q, q+ movq h, a+ subq r, a+ cmpq a, r // CF <=> r < h - r <=> 2 * r < h+ sbbq a, a+ notq a // a = bitmask(2 * r >= h)+ subq a, q+ addq r, r+ andq h, a+ subq a, r+ decq i+ jnz Lbignum_montifier_estloop++// Strictly speaking the above loop doesn't quite give the true remainder+// and quotient in the special case r = h = 2^63, so fix it up. We get+// q = 2^63 - 1 and r = 2^63 and really want q = 2^63 and r = 0. This is+// supererogatory, because the main property of q used below still holds+// in this case unless the initial m = 1, and then anyway the overall+// specification (congruence modulo m) holds degenerately. But it seems+// nicer to get a "true" quotient and remainder.++ incq r+ cmpq r, h+ adcq $0, q++// So now we have q and r with 2^126 = q * h + r (imagining r = 0 in the+// fixed-up case above: note that we never actually use the computed+// value of r below and so didn't adjust it). And we can assume the ranges+// q <= 2^63 and r < h < 2^64.+//+// The idea is to use q as a first quotient estimate for a remainder+// of 2^{p+62} mod n, where p = 64 * k. We have, splitting n into the+// high and low parts h and l:+//+// 2^{p+62} - q * n = 2^{p+62} - q * (2^{p-64} * h + l)+// = 2^{p+62} - (2^{p-64} * (q * h) + q * l)+// = 2^{p+62} - 2^{p-64} * (2^126 - r) - q * l+// = 2^{p-64} * r - q * l+//+// Note that 2^{p-64} * r < 2^{p-64} * h <= n+// and also q * l < 2^63 * 2^{p-64} = 2^{p-1} <= n+// so |diff| = |2^{p-64} * r - q * l| < n.+//+// If in fact diff >= 0 then it is already 2^{p+62} mod n.+// otherwise diff + n is the right answer.+//+// To (maybe?) make the computation slightly easier we actually flip+// the sign and compute d = q * n - 2^{p+62}. Then the answer is either+// -d (when negative) or n - d; in either case we effectively negate d.+// This negating tweak in fact spoils the result for cases where+// 2^{p+62} mod n = 0, when we get n instead. However the only case+// where this can happen is m = 1, when the whole spec holds trivially,+// and actually the remainder of the logic below works anyway since+// the latter part of the code only needs a congruence for the k-digit+// result, not strict modular reduction (the doublings will maintain+// the non-strict inequality).++ xorq c, c+ xorq i, i+Lbignum_montifier_mulloop:+ movq (t,i,8), a+ mulq q+ addq c, a+ adcq $0, d+ movq a, (z,i,8)+ movq d, c+ incq i+ cmpq k, i+ jc Lbignum_montifier_mulloop++// Now c is the high word of the product, so subtract 2^62+// and then turn it into a bitmask in q = h++ movq $0x4000000000000000, a+ subq a, c+ sbbq q, q+ notq q++// Now do [c] * n - d for our final answer++ xorq c, c+ xorq i, i+Lbignum_montifier_remloop:+ movq (t,i,8), a+ andq q, a+ negq c+ sbbq (z,i,8), a+ sbbq c, c+ movq a, (z,i,8)+ incq i+ cmpq k, i+ jc Lbignum_montifier_remloop++// Now still need to do a couple of modular doublings to get us all the+// way up to 2^{p+64} == r from initial 2^{p+62} == r (mod n).++ xorq c, c+ xorq j, j+ xorq b, b+Lbignum_montifier_dubloop1:+ movq (z,j,8), a+ shrdq $63, a, c+ negq b+ sbbq (t,j,8), c+ sbbq b, b+ movq c, (z,j,8)+ movq a, c+ incq j+ cmpq k, j+ jc Lbignum_montifier_dubloop1+ shrq $63, c+ addq b, c+ xorq j, j+ xorq b, b+Lbignum_montifier_corrloop1:+ movq (t,j,8), a+ andq c, a+ negq b+ adcq (z,j,8), a+ sbbq b, b+ movq a, (z,j,8)+ incq j+ cmpq k, j+ jc Lbignum_montifier_corrloop1++// This is not exactly the same: we also copy output to t giving the+// initialization t_1 = r == 2^{p+64} mod n for the main loop next.++ xorq c, c+ xorq j, j+ xorq b, b+Lbignum_montifier_dubloop2:+ movq (z,j,8), a+ shrdq $63, a, c+ negq b+ sbbq (t,j,8), c+ sbbq b, b+ movq c, (z,j,8)+ movq a, c+ incq j+ cmpq k, j+ jc Lbignum_montifier_dubloop2+ shrq $63, c+ addq b, c+ xorq j, j+ xorq b, b+Lbignum_montifier_corrloop2:+ movq (t,j,8), a+ andq c, a+ negq b+ adcq (z,j,8), a+ sbbq b, b+ movq a, (z,j,8)+ movq a, (t,j,8)+ incq j+ cmpq k, j+ jc Lbignum_montifier_corrloop2++// We then successively generate (k+1)-digit values satisfying+// t_i == 2^{p+64*i} mod n, each of which is stored in h::t. Finish+// initialization by zeroing h initially++ xorq h, h++// Then if t_i = 2^{p} * h + l+// we have t_{i+1} == 2^64 * t_i+// = (2^{p+64} * h) + (2^64 * l)+// == r * h + l<<64+// Do this 2*k more times so we end up == 2^{192*k+64}, one more than we want+//+// Writing B = 2^{64k}, the possible correction of adding r, which for+// a (k+1)-digit result is equivalent to subtracting q = 2^{64*(k+1)} - r+// would give the overall worst-case value minus q of+// [ B * (B^k - 1) + (B - 1) * r ] - [B^{k+1} - r]+// = B * (r - 1) < B^{k+1} so we keep inside k+1 digits as required.+//+// This implementation makes the shift implicit by starting b with the+// "previous" digit (initially 0) to offset things by 1.++ leaq (k,k), i+Lbignum_montifier_modloop:+ xorq b, b+ movq k, n+ xorq j, j+ xorq c, c+Lbignum_montifier_cmaloop:+ adcq b, c+ sbbq l, l+ movq (z,j,8), a+ mulq h+ subq l, d+ addq c, a+ movq (t,j,8), b+ movq a, (t,j,8)+ movq d, c+ incq j+ decq n+ jnz Lbignum_montifier_cmaloop+ adcq c, b+ movq b, h++ sbbq l, l++ xorq j, j+ xorq c, c+Lbignum_montifier_oaloop:+ movq (t,j,8), a+ movq (z,j,8), b+ andq l, b+ negq c+ adcq b, a+ sbbq c, c+ movq a, (t,j,8)+ incq j+ cmpq k, j+ jc Lbignum_montifier_oaloop+ subq c, h++ decq i+ jnz Lbignum_montifier_modloop++// Compute the negated modular inverse w (same register as i, not used again).++ movq (m), a+ movq a, c+ movq a, w+ shlq $2, c+ subq c, w+ xorq $2, w+ movq w, c+ imulq a, c+ movl $2, ashort+ addq c, a+ addq $1, c+ imulq a, w+ imulq c, c+ movl $1, ashort+ addq c, a+ imulq a, w+ imulq c, c+ movl $1, ashort+ addq c, a+ imulq a, w+ imulq c, c+ movl $1, ashort+ addq c, a+ imulq a, w++// Now do one almost-Montgomery reduction w.r.t. the original m+// which lops off one 2^64 from the congruence and, with the usual+// almost-Montgomery correction, gets us back inside k digits++ movq (t), c+ movq w, b+ imulq c, b++ movq (m), a+ mulq b+ addq c, a+ movq d, c+ movl $1, jshort+ movq k, n+ decq n+ jz Lbignum_montifier_amontend+Lbignum_montifier_amontloop:+ adcq (t,j,8), c+ sbbq l, l+ movq (m,j,8), a+ mulq b+ subq l, d+ addq c, a+ movq a, -8(t,j,8)+ movq d, c+ incq j+ decq n+ jnz Lbignum_montifier_amontloop+Lbignum_montifier_amontend:+ adcq c, h+ sbbq l, l+ movq h, -8(t,k,8)++ xorq j, j+ xorq c, c+Lbignum_montifier_aosloop:+ movq (t,j,8), a+ movq (m,j,8), b+ andq l, b+ negq c+ sbbq b, a+ sbbq c, c+ movq a, (z,j,8)+ incq j+ cmpq k, j+ jc Lbignum_montifier_aosloop++// So far, the code (basically a variant of bignum_amontifier) has produced+// a k-digit value z == 2^{192k} (mod m), not necessarily fully reduced mod m.+// We now do a short Montgomery reduction (similar to bignum_demont) so that+// we achieve full reduction mod m while lopping 2^{64k} off the congruence.+// We recycle h as the somewhat strangely-named outer loop counter.++ movq k, h++Lbignum_montifier_montouterloop:+ movq (z), c+ movq w, b+ imulq c, b+ movq (m), a+ mulq b+ addq c, a+ movq d, c+ movl $1, jshort+ movq k, n+ decq n+ jz Lbignum_montifier_montend+Lbignum_montifier_montloop:+ adcq (z,j,8), c+ sbbq l, l+ movq (m,j,8), a+ mulq b+ subq l, d+ addq c, a+ movq a, -8(z,j,8)+ movq d, c+ incq j+ decq n+ jnz Lbignum_montifier_montloop+Lbignum_montifier_montend:+ adcq $0, c+ movq c, -8(z,k,8)++ decq h+ jnz Lbignum_montifier_montouterloop++// Now do a comparison of z with m to set a final correction mask+// indicating that z >= m and so we need to subtract m.++ xorq j, j+ movq k, n+Lbignum_montifier_cmploop:+ movq (z,j,8), a+ sbbq (m,j,8), a+ incq j+ decq n+ jnz Lbignum_montifier_cmploop+ sbbq d, d+ notq d++// Now do a masked subtraction of m for the final reduced result.++ xorq l, l+ xorq j, j+Lbignum_montifier_corrloop:+ movq (m,j,8), a+ andq d, a+ negq l+ sbbq a, (z,j,8)+ sbbq l, l+ incq j+ cmpq k, j+ jc Lbignum_montifier_corrloop++Lbignum_montifier_end:+ CFI_POP(%r13)+ CFI_POP(%r12)+ CFI_POP(%rbx)+ CFI_POP(%rbp)++#if WINDOWS_ABI+ CFI_POP(%rsi)+ CFI_POP(%rdi)+#endif+ CFI_RET++S2N_BN_SIZE_DIRECTIVE(bignum_montifier)++#if defined(__linux__) && defined(__ELF__)+.section .note.GNU-stack,"",%progbits+#endif
+ cbits/s2n/x86_att/bignum_mul.S view
@@ -0,0 +1,160 @@+// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.+// SPDX-License-Identifier: Apache-2.0 OR ISC OR MIT-0++// ----------------------------------------------------------------------------+// Multiply z := x * y+// Inputs x[m], y[n]; output z[k]+//+// extern void bignum_mul(uint64_t k, uint64_t *z, uint64_t m, const uint64_t *x,+// uint64_t n, const uint64_t *y);+//+// Does the "z := x * y" operation where x is m digits, y is n, result z is k.+// Truncates the result in general unless k >= m + n+//+// Standard x86-64 ABI: RDI = k, RSI = z, RDX = m, RCX = x, R8 = n, R9 = y+// Microsoft x64 ABI: RCX = k, RDX = z, R8 = m, R9 = x, [RSP+40] = n, [RSP+48] = y+// ----------------------------------------------------------------------------++#include "_internal_s2n_bignum_x86_att.h"+++ S2N_BN_SYM_VISIBILITY_DIRECTIVE(bignum_mul)+ S2N_BN_FUNCTION_TYPE_DIRECTIVE(bignum_mul)+ S2N_BN_SYM_PRIVACY_DIRECTIVE(bignum_mul)+ .text+ .balign 32++// These are actually right++#define p %rdi+#define z %rsi+#define n %r8++// These are not++#define c %r15+#define h %r14+#define l %r13+#define x %r12+#define y %r11+#define i %rbx+#define k %r10+#define m %rbp++// These are always local scratch since multiplier result is in these++#define a %rax+#define d %rdx++++S2N_BN_SYMBOL(bignum_mul):+ CFI_START+ _CET_ENDBR++#if WINDOWS_ABI+ CFI_PUSH(%rdi)+ CFI_PUSH(%rsi)+ movq %rcx, %rdi+ movq %rdx, %rsi+ movq %r8, %rdx+ movq %r9, %rcx+ movq 56(%rsp), %r8+ movq 64(%rsp), %r9+#endif++// We use too many registers, and also we need %rax:%rdx for multiplications++ CFI_PUSH(%rbx)+ CFI_PUSH(%rbp)+ CFI_PUSH(%r12)+ CFI_PUSH(%r13)+ CFI_PUSH(%r14)+ CFI_PUSH(%r15)+ movq %rdx, m++// If the result size is zero, do nothing+// Note that even if either or both inputs has size zero, we can't+// just give up because we at least need to zero the output array+// If we did a multiply-add variant, however, then we could++ testq p, p+ jz Lbignum_mul_end++// Set initial 2-part sum to zero (we zero c inside the body)++ xorq h, h+ xorq l, l++// Otherwise do outer loop k = 0 ... k = p - 1++ xorq k, k++Lbignum_mul_outerloop:++// Zero our carry term first; we eventually want it and a zero is useful now+// Set a = max 0 (k + 1 - n), i = min (k + 1) m+// This defines the range a <= j < i for the inner summation+// Note that since k < p < 2^64 we can assume k + 1 doesn't overflow+// And since we want to increment it anyway, we might as well do it now++ xorq c, c // c = 0+ incq k // k = k + 1++ movq k, a // a = k + 1+ subq n, a // a = k + 1 - n+ cmovcq c, a // a = max 0 (k + 1 - n)++ movq m, i // i = m+ cmpq m, k // CF <=> k + 1 < m+ cmovcq k, i // i = min (k + 1) m++// Turn i into a loop count, and skip things if it's <= 0+// Otherwise set up initial pointers x -> x0[a] and y -> y0[k - a]+// and then launch into the main inner loop, postdecrementing i++ movq k, d+ subq i, d+ subq a, i+ jbe Lbignum_mul_innerend+ leaq (%rcx,a,8), x+ leaq -8(%r9,d,8), y++Lbignum_mul_innerloop:+ movq (y,i,8), %rax+ mulq (x)+ addq $8, x+ addq %rax, l+ adcq %rdx, h+ adcq $0, c+ decq i+ jnz Lbignum_mul_innerloop++Lbignum_mul_innerend:++ movq l, (z)+ movq h, l+ movq c, h+ addq $8, z++ cmpq p, k+ jc Lbignum_mul_outerloop++Lbignum_mul_end:+ CFI_POP(%r15)+ CFI_POP(%r14)+ CFI_POP(%r13)+ CFI_POP(%r12)+ CFI_POP(%rbp)+ CFI_POP(%rbx)+#if WINDOWS_ABI+ CFI_POP(%rsi)+ CFI_POP(%rdi)+#endif+ CFI_RET++S2N_BN_SIZE_DIRECTIVE(bignum_mul)++#if defined(__linux__) && defined(__ELF__)+.section .note.GNU-stack,"",%progbits+#endif
+ cbits/s2n/x86_att/bignum_sqr.S view
@@ -0,0 +1,190 @@+// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.+// SPDX-License-Identifier: Apache-2.0 OR ISC OR MIT-0++// ----------------------------------------------------------------------------+// Square z := x^2+// Input x[n]; output z[k]+//+// extern void bignum_sqr(uint64_t k, uint64_t *z, uint64_t n, const uint64_t *x);+//+// Does the "z := x^2" operation where x is n digits and result z is k.+// Truncates the result in general unless k >= 2 * n+//+// Standard x86-64 ABI: RDI = k, RSI = z, RDX = n, RCX = x+// Microsoft x64 ABI: RCX = k, RDX = z, R8 = n, R9 = x+// ----------------------------------------------------------------------------++#include "_internal_s2n_bignum_x86_att.h"+++ S2N_BN_SYM_VISIBILITY_DIRECTIVE(bignum_sqr)+ S2N_BN_FUNCTION_TYPE_DIRECTIVE(bignum_sqr)+ S2N_BN_SYM_PRIVACY_DIRECTIVE(bignum_sqr)+ .text+ .balign 32++// First three are where arguments come in, but n is moved.++#define p %rdi+#define z %rsi+#define x %rcx+#define n %r8++// These are always local scratch since multiplier result is in these++#define a %rax+#define d %rdx++// Other variables++#define i %rbx+#define ll %rbp+#define hh %r9+#define k %r10+#define y %r11+#define htop %r12+#define l %r13+#define h %r14+#define c %r15++// Short versions++#define llshort %ebp++S2N_BN_SYMBOL(bignum_sqr):+ CFI_START+ _CET_ENDBR++#if WINDOWS_ABI+ CFI_PUSH(%rdi)+ CFI_PUSH(%rsi)+ movq %rcx, %rdi+ movq %rdx, %rsi+ movq %r8, %rdx+ movq %r9, %rcx+#endif++// We use too many registers, and also we need %rax:%rdx for multiplications++ CFI_PUSH(%rbx)+ CFI_PUSH(%rbp)+ CFI_PUSH(%r12)+ CFI_PUSH(%r13)+ CFI_PUSH(%r14)+ CFI_PUSH(%r15)+ movq %rdx, n++// If p = 0 the result is trivial and nothing needs doing++ testq p, p+ jz Lbignum_sqr_end++// initialize (hh,ll) = 0++ xorl llshort, llshort+ xorq hh, hh++// Iterate outer loop from k = 0 ... k = p - 1 producing result digits++ xorq k, k++Lbignum_sqr_outerloop:++// First let bot = MAX 0 (k + 1 - n) and top = MIN (k + 1) n+// We want to accumulate all x[i] * x[k - i] for bot <= i < top+// For the optimization of squaring we avoid duplication and do+// 2 * x[i] * x[k - i] for i < htop, where htop = MIN ((k+1)/2) n+// Initialize i = bot; in fact just compute bot as i directly.++ xorq c, c+ leaq 1(k), i+ movq i, htop+ shrq $1, htop+ subq n, i+ cmovcq c, i+ cmpq n, htop+ cmovncq n, htop++// Initialize the three-part local sum (c,h,l); c was already done above++ xorq l, l+ xorq h, h++// If htop <= bot then main doubled part of the sum is empty++ cmpq htop, i+ jnc Lbignum_sqr_nosumming++// Use a moving pointer for [y] = x[k-i] for the cofactor++ movq k, a+ subq i, a+ leaq (x,a,8), y++// Do the main part of the sum x[i] * x[k - i] for 2 * i < k++Lbignum_sqr_innerloop:+ movq (x,i,8), a+ mulq (y)+ addq a, l+ adcq d, h+ adcq $0, c+ subq $8, y+ incq i+ cmpq htop, i+ jc Lbignum_sqr_innerloop++// Now double it++ addq l, l+ adcq h, h+ adcq c, c++// If k is even (which means 2 * i = k) and i < n add the extra x[i]^2 term++Lbignum_sqr_nosumming:+ testq $1, k+ jnz Lbignum_sqr_innerend+ cmpq n, i+ jnc Lbignum_sqr_innerend++ movq (x,i,8), a+ mulq a+ addq a, l+ adcq d, h+ adcq $0, c++// Now add the local sum into the global sum, store and shift++Lbignum_sqr_innerend:+ addq ll, l+ movq l, (z,k,8)+ adcq hh, h+ movq h, ll+ adcq $0, c+ movq c, hh++ incq k+ cmpq p, k+ jc Lbignum_sqr_outerloop++// Restore registers and return++Lbignum_sqr_end:+ CFI_POP(%r15)+ CFI_POP(%r14)+ CFI_POP(%r13)+ CFI_POP(%r12)+ CFI_POP(%rbp)+ CFI_POP(%rbx)+#if WINDOWS_ABI+ CFI_POP(%rsi)+ CFI_POP(%rdi)+#endif+ CFI_RET++S2N_BN_SIZE_DIRECTIVE(bignum_sqr)++#if defined(__linux__) && defined(__ELF__)+.section .note.GNU-stack,"",%progbits+#endif
cbits/tests/ct/ct_powm.c view
@@ -4,8 +4,34 @@ #include <string.h> #include "crypton_powm.h" +/* A 2048-bit modulus unless the build says otherwise: run.sh builds it at+ * the other sizes the vendored multiplication takes as well, since those+ * are different code. */+#ifndef CT_POWM_BYTES+#define CT_POWM_BYTES 256+#endif++#ifdef CT_POWM_COUNT_S2N+/* run.sh links this build with -Wl,--wrap=bignum_emontredc_8n, so every+ * reduction the s2n-bignum path does comes through here and is counted.+ * The build then says which implementation it ran, rather than leaving it+ * to be inferred: under valgrind the processor's answers are valgrind's,+ * and a build that quietly took the C would pass here while checking what+ * the plain powm build already has. */+#include <stdint.h>+uint64_t __real_bignum_emontredc_8n(uint64_t k, uint64_t *z,+ const uint64_t *m, uint64_t w);+static unsigned long s2n_reductions;+uint64_t __wrap_bignum_emontredc_8n(uint64_t k, uint64_t *z,+ const uint64_t *m, uint64_t w)+{+ s2n_reductions++;+ return __real_bignum_emontredc_8n(k, z, m, w);+}+#endif+ int main(void) {- enum { LEN = 256 }; /* a 2048-bit modulus */+ enum { LEN = CT_POWM_BYTES }; uint8_t out[LEN], base[LEN], mod[LEN], exp[LEN]; ct_fill(base, sizeof base);@@ -25,5 +51,8 @@ } CT_PUBLIC(out, sizeof out); ct_sink(out, sizeof out);+#ifdef CT_POWM_COUNT_S2N+ printf("dispatch powm_s2n=%lu\n", s2n_reductions);+#endif return 0; }
cbits/tests/ct/known.txt view
@@ -40,6 +40,27 @@ # 400f64 b.ne 400f3c <- what memcheck names # 404c6c cmp x3, x6 <- public: j against n_table # 404c70 b.ne 404c30 <- what memcheck names-p256.c:147 addM's loop; the carry is taken with cset and cinc-p256.c:149 the same+addM@p256.c the carry of addM's loop, which is taken without a+# branch. Named by function rather than by line because+# the line is the compiler's choice and the function is+# not. Three compilers were asked: AArch64 names 147 and+# 149, gcc 11.5 on x86-64 names 147, 148 and 149, and the+# gcc 14 the CI uses names none of them -- and all three+# name addM.+#+# On AArch64 the only instructions consuming the secret's+# flags are cset and cinc, which do not branch. On x86-64,+# disassembled in a -no-pie build, the body between the+# loop label and its closing branch is+#+# 401ad6 mov (%rax,%rdx,1),%rbx+# 401aeb and %rcx,%rbx <- the secret, as a mask+# 401af1 add %r12,%r8+# 401af4 adc %r13,%r9 <- carried, not branched on+# 401afd mov %rsi,0x120(%rsp,%rdx,1)+# 401b0e cmp $0x20,%rdx <- public: the loop offset+# 401b12 jne 401ad6 <- the only branch+#+# one branch, on a public counter; no conditional move, and+# no address the secret reaches. constant_time.h:150 decaf's constant-time lookup, over j < n_table
cbits/tests/ct/run.sh view
@@ -148,14 +148,47 @@ return fi ;;+ powm_s2n_*)+ got=$("$out/$name" 2>/dev/null | sed -n 's/^dispatch powm_s2n=\([0-9]*\).*/\1/p')+ if [ -z "$got" ]; then+ echo "FAIL $name: it did not run to the end on this processor"+ status=1+ return+ elif [ "$got" -eq 0 ]; then+ echo "FAIL $name: the s2n-bignum reduction ran 0 times --"+ echo " this build checked the C again, not the path it is named for"+ status=1+ return+ fi+ ;; esac if [ "$have_valgrind" = no ]; then "$out/$name" > /dev/null 2>&1 && echo "built $name (no valgrind here; nothing checked)" \ || { echo "FAIL $name did not run"; status=1; } return fi- valgrind --error-exitcode=0 --track-origins=yes --num-callers=20 \- --log-file="$out/$name.log" "$out/$name" > /dev/null 2>&1 || true+ # in a subshell, so that a driver valgrind kills is not announced by+ # this shell as well -- the log says what happened+ ( valgrind --error-exitcode=0 --track-origins=yes --num-callers=20 \+ --log-file="$out/$name.log" "$out/$name" > /dev/null 2>&1 ) \+ 2> /dev/null || true+ # A driver valgrind could not run to the end reports nothing, and nothing+ # used to read as a pass. An instruction valgrind cannot decode is the+ # likely one: the vendored ADX assembly needs a valgrind that knows it.+ if grep -q "unhandled instruction\|Illegal instruction\|SIGILL" "$out/$name.log"; then+ case $name in+ powm_s2n_*)+ echo "skip $name: this valgrind cannot decode the vendored assembly's"+ echo " instructions, so it cannot run the path this build is for"+ ;;+ *)+ echo "FAIL $name: valgrind could not run it to the end"+ grep -m3 "unhandled instruction\|Illegal instruction\|SIGILL" "$out/$name.log" | sed 's/^/ /'+ status=1+ ;;+ esac+ return+ fi n=$(grep -c "^==[0-9]*== \(Conditional jump\|Use of uninitialised\)" "$out/$name.log" || true) # Which places did it name? Only the frame the report is against -- the # first "at" line under the complaint -- is the place; the "by" lines@@ -163,18 +196,28 @@ # on anything. Nor is the "at" line under "Uninitialised value was # created by", which --track-origins prints to say where the value came # from: that frame is a stack allocation, not a branch, and taking it- # for one put a function's opening brace on the list. A site is- # "file:line", and the ones listed in known.txt are understood.+ # for one put a function's opening brace on the list.+ #+ # A site is kept as "function@file:line", and known.txt may name any of+ # the three widths: that exact line, the function, or the whole file.+ # The function is there because the line is the compiler's choice and+ # not the code's: gcc 14 names no line of addM's loop at all, gcc 11.5+ # on x86-64 names three, and clang on AArch64 named two of those three.+ # What the disassembly establishes is a property of the function, so+ # that is what an entry should be able to say. sites=$(awk ' /^==[0-9]*== (Conditional jump|Use of uninitialised)/ { want = 1; next } want && /^==[0-9]*== at 0x/ { print; want = 0 } ' "$out/$name.log" |- sed -n 's/^==[0-9]*== at 0x[0-9A-Fa-f]*: [A-Za-z_0-9]* (\([^)]*\))$/\1/p' |- grep -v '^ct_' | sort -u)+ sed -n 's/^==[0-9]*== at 0x[0-9A-Fa-f]*: \([A-Za-z_0-9.]*\) (\([^)]*\))$/\1@\2/p' |+ grep -v '@ct_' | sort -u) unknown= for site in $sites; do- file=${site%%:*}- if grep -q "^$site[[:space:]]" cbits/tests/ct/known.txt ||+ funcfile=${site%%:*}+ fileline=${site#*@}+ file=${fileline%%:*}+ if grep -q "^$fileline[[:space:]]" cbits/tests/ct/known.txt ||+ grep -q "^$funcfile[[:space:]]" cbits/tests/ct/known.txt || grep -q "^$file[[:space:]]" cbits/tests/ct/known.txt; then continue fi@@ -231,6 +274,42 @@ run_one canary "" "" run_one powm "cbits/crypton_powm.c" ""++# The same exponentiation through s2n-bignum, which is what RSA signing runs+# on x86-64 with ADX. The build above is the C: it does not define+# CRYPTON_S2N_BIGNUM, so from the release the assembly went in until this+# was added, the path that actually runs was never put through this+# harness. Each size is a different routine -- Karatsuba at 1024 and 2048,+# a padded operand through the 2048-bit one at 1536, schoolbook at 3072 and+# 4096 -- so each is built.+#+# ADX is assumed by CRYPTON_CPU_TESTING_ADX, and only where the processor+# reports it: under valgrind the processor's answers are valgrind's, and+# what this is for is the assembly, not valgrind's opinion of the+# processor. The driver counts the reductions it did through the assembly,+# and a count of nothing fails the build rather than passing it.+case $(uname -m) in+x86_64 | amd64)+ if grep -qw adx "${CRYPTON_CT_CPUINFO:-/proc/cpuinfo}" 2>/dev/null; then+ s2n=cbits/s2n/x86_att+ powm_s2n_src="cbits/crypton_powm.c cbits/crypton_cpu.c cbits/tests/ct/cpu_stub.c+ $s2n/bignum_montifier.S $s2n/bignum_emontredc_8n.S+ $s2n/bignum_kmul_16_32.S $s2n/bignum_ksqr_16_32.S+ $s2n/bignum_kmul_32_64.S $s2n/bignum_ksqr_32_64.S+ $s2n/bignum_mul.S $s2n/bignum_sqr.S"+ powm_s2n_inc="-Icbits/s2n/include -DCRYPTON_S2N_BIGNUM+ -DCRYPTON_CPU_TESTING_ADX -DCT_POWM_COUNT_S2N+ -Wl,--wrap=bignum_emontredc_8n"+ for bytes in 128 192 256 384 512; do+ run_one "powm_s2n_$((bytes * 8))" "$powm_s2n_src" \+ "$powm_s2n_inc -DCT_POWM_BYTES=$bytes" powm+ done+ else+ echo "skip powm_s2n: this processor reports no ADX, so the vendored"+ echo " multiplication cannot run here"+ fi+ ;;+esac run_one p256 "cbits/p256/p256.c cbits/p256/p256_ec.c" "" run_one x25519 "cbits/curve25519/curve25519-donna-c64.c" "" run_one ed25519 "cbits/ed25519/ed25519.c cbits/crypton_sha512.c" "-Icbits/ed25519"
cbits/tests/ppc8_diff.c view
@@ -36,6 +36,22 @@ #include "aes/block128.h" #include "aes/ppc8.h" +/* The portable mode loops this compares against. crypton_aes.c defines+ * them and declares them only to itself, at the top of that file, so they+ * are declared again here. They were once in a header; when they left it,+ * this file -- built by hand and by nobody since -- went on calling them+ * undeclared, which C has not allowed since C99 and gcc 14 refuses. */+void crypton_aes_generic_encrypt_ecb(aes_block *output, aes_key *key,+ aes_block *input, uint32_t nb_blocks);+void crypton_aes_generic_decrypt_ecb(aes_block *output, aes_key *key,+ aes_block *input, uint32_t nb_blocks);+void crypton_aes_generic_encrypt_cbc(aes_block *output, aes_key *key,+ aes_block *iv, aes_block *input,+ uint32_t nb_blocks);+void crypton_aes_generic_decrypt_cbc(aes_block *output, aes_key *key,+ aes_block *iv, aes_block *input,+ uint32_t nb_blocks);+ /* the portable CTR, which reaches generic.c rather than the branch table */ void crypton_aes_bitsliced_encrypt_ctr(uint8_t *output, aes_key *key, aes_block *iv, uint8_t *input,
crypton.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: crypton-version: 2.2.1+version: 2.2.2 -- crypton's own code is BSD-3-Clause. The parts of -- cbits/aes/gcm_fused_x86.c that follow picotls's fusion are MIT, and the -- vendored s2n-bignum assembly in cbits/s2n is taken under ISC, and the@@ -596,11 +596,17 @@ -- unlike OpenSSL's and BoringSSL's ecp_nistz256 it can be used. Both -- variants of each routine are built and chosen between in -- cbits/p256/p256_s2n.c -- see cbits/s2n/README.md for why the question- -- is a different one on the two architectures. Windows is left out for- -- now: the vendored files carry ELF and Mach-O directives and nothing- -- for COFF, the same reason the CRYPTOGAMS AArch64 assembly above skips- -- it. x86-64 there wants -DWINDOWS_ABI=1 as well.- if (flag(support_s2n_bignum) && (arch(x86_64) || arch(aarch64)) && !os(windows))+ -- is a different one on the two architectures.+ --+ -- On Windows, x86-64 only. The vendored files carry the ELF directives+ -- .type and .size, which neither of Windows' assemblers accepts, and+ -- assume the System V calling convention unless WINDOWS_ABI is set;+ -- cbits/s2n/x86_att/_internal_s2n_bignum_x86_att.h, which every one of+ -- them reaches first, empties the first and sets the second on _WIN32,+ -- so the vendored files themselves stay as upstream wrote them. The+ -- AArch64 files have the same directives and no such header yet, and no+ -- runner to check one, so Windows on ARM keeps the C.+ if flag(support_s2n_bignum) && (arch(x86_64) || (arch(aarch64) && !os(windows))) cc-options: -DCRYPTON_S2N_BIGNUM include-dirs: cbits/s2n/include c-sources:@@ -613,6 +619,7 @@ if arch(aarch64) asm-sources: cbits/s2n/arm/bignum_deamont_p384.S+ cbits/s2n/arm/bignum_montifier.S cbits/s2n/arm/bignum_modinv.S cbits/s2n/arm/curve25519_x25519.S cbits/s2n/arm/curve25519_x25519_alt.S@@ -690,20 +697,28 @@ cbits/s2n/x86_att/p256_scalarmulbase.S cbits/s2n/x86_att/p256_scalarmulbase_alt.S - -- Modular exponentiation at RSA sizes, x86-64 only: on AArch64- -- crypton's C measures faster than these, so nothing is taken- -- for it. All of them want ADX, which the run-time check in- -- cbits/crypton_powm.c asks about before using any. asm-sources:- cbits/s2n/x86_att/bignum_emontredc_8n.S- cbits/s2n/x86_att/bignum_kmul_16_32.S- cbits/s2n/x86_att/bignum_kmul_32_64.S- cbits/s2n/x86_att/bignum_ksqr_16_32.S- cbits/s2n/x86_att/bignum_ksqr_32_64.S+ cbits/s2n/x86_att/bignum_montifier.S cbits/s2n/x86_att/p384_montjscalarmul.S cbits/s2n/x86_att/p384_montjscalarmul_alt.S cbits/s2n/x86_att/p521_jscalarmul.S cbits/s2n/x86_att/p521_jscalarmul_alt.S++ -- Modular exponentiation at RSA sizes, x86-64 only: on AArch64+ -- crypton's C measures faster than these, so nothing is taken+ -- for it. All of them want ADX, which the run-time check in+ -- cbits/crypton_powm.c asks about before using any.+ -- Not on macOS: Apple's assembler reads $0 in bignum_emontredc_8n's+ -- macros as a macro argument and rejects the file.+ if !os(osx)+ asm-sources:+ cbits/s2n/x86_att/bignum_emontredc_8n.S+ cbits/s2n/x86_att/bignum_mul.S+ cbits/s2n/x86_att/bignum_sqr.S+ cbits/s2n/x86_att/bignum_kmul_16_32.S+ cbits/s2n/x86_att/bignum_kmul_32_64.S+ cbits/s2n/x86_att/bignum_ksqr_16_32.S+ cbits/s2n/x86_att/bignum_ksqr_32_64.S -- The PQ Code Package's mlkem-native and mldsa-native, vendored under -- cbits/mlkem and cbits/mldsa. Apache-2.0 OR ISC OR MIT, the same