RSA arithmetic and small-parameter failure modes

Mechanism

RSA security relies on the structure and size of the modulus, correct exponents, and secure message encoding. Textbook RSA is deterministic and multiplicative. A small public exponent is not inherently broken, but unpadded small messages, repeated related messages, shared primes, or malformed parameters can create recoverable algebraic structure.

Practical method

Extract n, e, and ciphertext as exact integers. Check modulus size, parity, perfect powers, and gcd relationships across public keys. Identify the padding scheme before attempting roots or congruences. Validate any candidate private exponent or plaintext by re-encrypting it with the original public parameters.

from math import gcd
g = gcd(n1, n2)
if 1 < g < n1:
    p, q = g, n1 // g

Interpreting evidence

A nontrivial shared divisor factors both affected moduli. An integer-root result is meaningful only if the recovered value raised to e reproduces the ciphertext under the stated no-wrap assumptions.

Pitfalls and limits

OAEP and signature encodings change the attack model. Floating-point roots lose large-integer precision. RSA private-key records include CRT values whose consistency can help distinguish corruption from genuine parameters.