GCD with Even modulus

[pinkforest]

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"

[tarcieri]

Added in #617 / #618