RustCrypto
GCD with `Even` modulus
NIST.SP.800-56Br2 - Appendix C.2 - Deterministic Prime-Factor Recovery
The second part would require GCD(modulus - 1, public * private exp - 1)
1. Let a = (de – 1) × GCD(n – 1, de – 1).
This leads the modulus to be Even - https://github.com/RustCrypto/RSA/pull/394/files#r1553034591
However Bernstein-Yang (BY) GCD has a tripwire for left side to be Odd:
impl Gcd for BoxedUint {
type Output = CtOption<Self>;
fn gcd(&self, rhs: &Self) -> CtOption<Self> {
let ret = bernstein_yang::boxed::gcd(self, rhs);
CtOption::new(ret, self.is_odd())
}
}
BearSSL Trick
Footnote 4. in bigint
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 -
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 𝑚
𝑢 := 𝑚−1 mod 𝑥 using odd moduli + um - 1 / x
https://cronokirby.com/papers/2021/06/bsc_report.pdf
Other related:
- https://www.mdpi.com/2078-2489/12/11/462 - Profiling Attack against RSA Key Generation Based on a Euclidean
- https://eprint.iacr.org/2019/266.pdf - BY-GCD Bernstein & Yang
- https://www.youtube.com/watch?v=BLR63o5Px2g
Yaoan Jin & Atsuko Miyaji - CT-GCD work if BY-GCD is not an option for Even modulus ?
- https://www.jstage.jst.go.jp/article/transinf/E106.D/9/E106.D_2022ICP0009/_article
Also Hamburg has a paper -https://eprint.iacr.org/2021/1271.pdf re: Jacobi & Bernstein-Yang
"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"
