Paper 2026/2256

Affine-Padding Rabin-Oracle Factoring in $L_n\left(\frac{1}{3},\sqrt[3]{\frac{32}{9}}\right)$

Abstract

The 2007 algorithm of Joux, Naccache, and Thomé (JNT) shows that, with subexponential access to an $e$-th root oracle, one can forge RSA signatures for odd $e$ in time close to the special number field sieve, without factoring the modulus; a recent JNT implementation by Shea et al. [2] carried that attack to $1024$-bit RSA. We revisit the JNT construction at $e=2$, the Rabin case, where an $e$-th root oracle is a square-root oracle. A raw square-root oracle factors $n=pq$ in one query, so it is of no interest; the interesting object is a redundancy-constrained (affine-padded) Rabin oracle that returns a single canonical root and thereby resists the one-query attack. We show that a one-sided number field sieve against such an oracle produces a congruence of squares $X^2\equiv Y^2\pmod n$ with $X\not\equiv\pm Y$ with probability $\tfrac12$ per dependency, and hence factors $n$ in special-number-field-sieve time \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{32}{9}}}\right)\simeq L_n(1/3,{1.526\ldots}), \] strictly below the general number field sieve's \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{64}{9}}}\right)\simeq L_n(1/3,{1.923\ldots}). \] The mechanism is a pleasant inversion: the sign ambiguity that the odd-$e$ algorithm must suppress becomes, at $e=2$, the very quantity that leaks the factorization. We give the algorithm in full --- LLL polynomial selection for a quadratic field, a line sieve producing prime-ideal relations, quadratic characters, $\mathbb F_2$ linear algebra, and an exact number-field square root --- prove the half-rate splitting, and analyse the complexity, including the precise reason the attack collapses when the padding is a hash rather than an affine function of an attacker-chosen message. An open-source implementation realises every step. A small toy example run of it, from the padded modulus to the recovered factors, is given in Appendix A. Our implementation confirms a clear performance improvement in factoring speed.