Recover a stereotyped message encrypted with RSA (small public exponent only).

rsa_stereotyped_message.sage

#!/usr/bin/env -S sage -python3
import argparse
from sage.all import PolynomialRing, Zmod


def recover(N, e, c, prefix):
    P = PolynomialRing(Zmod(N), 'x')
    x = P.gen()
    poly = (prefix + x)**e - c
    return poly.small_roots(epsilon=1/2**e)


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Recover a stereotyped message encrypted with RSA')
    
    parser.add_argument('PUBKEY', type=int,
        help='Public modulus that encrypted the message')

    parser.add_argument('PUBEXP', type=int,
        help='Public exponent that encrypted the message')

    parser.add_argument('CIPHERTEXT', type=int,
        help='Encrypted message')

    parser.add_argument('KNOWN_MSB', type=int,
        help='Known upper bytes of the message (pad with zeros to the right)')

    args = parser.parse_args()
    
    probable_plaintexts = recover(
        args.PUBKEY, 
        args.PUBEXP, 
        args.CIPHERTEXT, 
        args.KNOWN_MSB
    )
    
    if probable_plaintexts:
        print(f'\u001b[1;92m[+]\u001b[0m Found {len(probable_plaintexts)} candidate plaintexts')
    else:
        print(f'\u001b[1;91m[-]\u001b[0m Plaintext not recovered')
    
    for i, pt in enumerate(probable_plaintexts):
        pt += args.KNOWN_MSB
        
        print(F'\u001b[1;96m[*]\u001b[0m Probable plaintext {i+1}:')

        print(f'    \u001b[1;93mINT\u001b[0m: {pt}')
        print(f'    \u001b[1;93mHEX\u001b[0m: {hex(pt)[2:]}')
        print(f'    \u001b[1;93mSTR\u001b[0m: {bytes.fromhex(hex(pt)[2:])}')