Cryptanalysis of RSA-Variant Cryptosystem Generated by Potential Rogue CA Methodology

Abstract

Rogue certificate authorities (RCA) are third-party entities that intentionally produce key pairs that satisfy publicly known security requirements but contain weaknesses only known to the RCA. This work analyses the Murru–Saettone RSA variant scheme that obtains its key pair from a potential RCA methodology. The Murru–Saettone scheme is based on the cubic Pell equation x3+ry3+r2z3−3rxyz=1. The public, e, and private, d key generation process uses the secret parameter ψ=(p2+p+1)(q2+q+1) in place of the standard Euler–phi function ϕ(N)=(p−1)(q−1), where ed≡1(modψ). We prove that, upon obtaining an approximation of ψ, we are able to identify the provided key pair that was maliciously provided even if the private key d size is approximate to ψ. In fact, we are able to factor the modulus N=pq.

Keywords

• RSA
• factorization
• continued fractions
• cubic Pell equation
• rogue certificate authority
• secure symmetric encryption