Non-Safe-Prime Modulus

What can go wrong. MPC protocols built over discrete-log groups such as $\text{QR}_p \subset \mathbb{Z}_p^*$, or $\text{QR}_N$ for an RSA modulus $N = PQ$, rely on the hardness of the discrete logarithm problem (DLP), which holds only when the group’s order has a sufficiently large prime factor. The standard way to guarantee this is to use safe primes: a prime $p = 2q + 1$ where $q$ is also prime. Then $\lvert \text{QR}_p \rvert = q$ is a large prime, and likewise $\lvert \text{QR}_N \rvert = \phi(N)/4 = (P-1)(Q-1)/4$ is a product of two large primes when both $P, Q$ are safe primes. Without that guarantee, an adversary can choose the modulus so that the DLP is easy.

Security implication. When $\lvert \text{QR}_p \rvert = (p-1)/2$ or $\lvert \text{QR}_N \rvert = (P-1)(Q-1)/4$ are smooth, i.e, factors only into small primes (i.e each $q_i \lt 2^{100}$ bits) $q_1, \ldots, q_k$, Pohlig-Hellman solves the DLP in time roughly $O\bigl(\log M + \sum_i \sqrt{q_i}\bigr)$, where $M \in \{p, N\}$ (see Valenta et al., eprint 2016/995 for the canonical analysis). For tss-lib’s Pedersen bases $h_1, h_2 \in \text{QR}_{\tilde N}$, an adversary who factors $\tilde N$ recovers $\log_{h_1}(h_2)$ via Pohlig-Hellman and extracts the DLN proof’s witness without performing honest keygen, undermining the zero-knowledge property of every range proof built on those bases.

How to avoid. Generate $p$ (or both factors $P, Q$ of $N = PQ$) as safe primes. For standardized prime groups, prefer the audited safe-prime constructions in RFC 3526 and RFC 7919.

 1// FILE: ecdsa/keygen/round_1.go — bnb-chain/tss-lib @ a2c27b4 (vulnerable)
 2// 5-7. generate auxiliary RSA primes for ZKPs later on
 3go func(ch chan<- *rsa.PrivateKey) {
 4    pk, err := rsa.GenerateMultiPrimeKey(rand.Reader, 2, RSAModulusLen)
 5    if err != nil {
 6        common.Logger.Errorf("RSA generation error: %s", err)
 7        ch <- nil
 8    }
 9    ch <- pk
10}(rsaCh)

 1// FILE: ecdsa/keygen/prepare.go — bnb-chain/tss-lib (post-PR #68, fixed)
 2// 5-7. generate safe primes for ZKPs used later on
 3go func(ch chan<- []*common.GermainSafePrime) {
 4    sgps, err := common.GetRandomSafePrimesConcurrent(safePrimeBitLen, 2, timeout, concurrency/2)
 5    if err != nil {
 6        ch <- nil
 7        return
 8    }
 9    ch <- sgps
10}(sgpCh)
11// ...
12NTildei, h1i, h2i, err := crypto.GenerateNTildei([2]*big.Int{sgps[0].SafePrime(), sgps[1].SafePrime()})