Paper 2026/1529

Generalized Wiener-Type Attacks on Two RSA-Like Cryptosystems

Abstract

In AfricaCrypt 2025, Seck et al. proposed a new generalized Wiener-type attack on an RSA-like cryptosystem proposed by Cotan and Teseleanu (NordSec 2023). In their attack, they studied the generalized key equation $eu - (p^4 - 1)(q^4 - 1)v = w$ and showed that a private exponent $d$ which is too large or too small can be recovered in polynomial time. Another RSA variant based on cubic Pell curves with key equation $ed - (p - 1)^2(q - 1)^2 k = 1$, was examined by Rahmani and Nitaj in AfricaCrypt 2025. Note that these two attacks are valid for a balanced modulus $N = pq$ ($q < p < 2 q$). In this paper, we extend these two attacks by showing that for a modulus $N=pq$ product of arbitrary primes $p$, $q$, one can efficiently factor $N$ by studying the two key equations $ex - (p^4 - 1)(q^4 - 1)y = \omega$ and $ex - (p - 1)^2(q - 1)^2 y = \omega$ under certain conditions on $x,y$ and $\omega$. Our new attacks are based on Coppersmith method and continued fractions.