Except at some point in RSA key pair generation, where we must invert the public exponent e modulo both p−1 and q−1, which are even. For that operation, BearSSL must employ additional tricks.↩
Go also seems to use the same "Extended Binary" GCD - by Thomas Pornin -
"It assumes that the given y is odd, which is often the case in cryptography; if y is not odd, the algorithm first divides out powers of 2 from y and/or x until y is odd"
NIST.SP.800-56Br2 - Appendix C.2 - Deterministic Prime-Factor Recovery
The second part would require GCD(modulus - 1, public * private exp - 1)
This leads the modulus to be
Even
- https://github.com/RustCrypto/RSA/pull/394/files#r1553034591However Bernstein-Yang (BY) GCD has a tripwire for left side to be
Odd
:BearSSL Trick
Footnote 4. in bigint
Go also seems to use the same "Extended Binary" GCD - by Thomas Pornin -
https://github.com/pornin/bingcd | https://eprint.iacr.org/2020/972.pdf | ncc
Go has report 3.3.2 for Inversion for both Even and Odd with "a standard trick" applied to calculate 𝑥−1 mod 𝑚
https://cronokirby.com/papers/2021/06/bsc_report.pdf
Other related:
Yaoan Jin & Atsuko Miyaji - CT-GCD work if BY-GCD is not an option for
Even
modulus ?Also Hamburg has a paper -https://eprint.iacr.org/2021/1271.pdf re: Jacobi & Bernstein-Yang