Can you efficiently construct an RSA public/private key pair with $8k$-bit public modulus such that $C=\left\lfloor\pi\,2^{8k-2}\right\rfloor$ deciphers per RSA-OAEP to your name as a bytestring in ASCII or UTF-8?

The decryption must be per RSAES-OAEP of PKCS#1v2.2, SHA-256 hash, no label, MGF1 with SHA-256, and sucessful. The key pair must conform¹ to section 3. It could come as $n$, $e$, $d$, or as a PEM text encoding of the private key per the format of section A.1.2 acceptable by an ASN.1 decoder. Kudos if it passes² OpenSSL's RSA_check_key, more kudos if $8k\ge1024$, the higher the better.

$C$ is the first $k$ bytes of these (in hex) for $8k$ up to $2^{16}$ bits.

Update: this answers in the affirmative, for whatever usual $k$, with $p$ and $q$ equal-size primes, and $N$ hard to factor. The next frontier is a low $e$, say in $[3,2^{256})$, ideally $65537$.

Further stunts are possible, like having $C$ or $2$ the signature of anything per any usual RSA signature scheme, even deterministic and/or with message recovery.

As a consequence: verifying a signature of a file against Alice's RSA public key (including, certified and used for other purposes) is proof neither that the file is unchanged since signature, nor that Alice was the signer.

Example where that matters: the signature of a file is on a trusted site, the file is not. Alice manages to get her public key (which she uses normally) in the verifier's keystore (with the key identifier of the legitimate signer, if there is such thing in the signature). The verifier, who just uses crypto as a magic tool, sees that the signature verifies, and (rightly) trusts the secure site to hold only trusted signatures of trusted files. There is a chance that a file alteration by Alice goes uncaught, or/and that she can wrongly convince the verifier that she made the signature at the date notarized by the trusted site.

Update 2: Some consequences of the same possibility are discussed in Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon and Ralf Sasse's Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures, originally in proceedings of CCS 2019.

¹ That is: public modulus $n$ must be the product of $u\ge2$ distinct odd primes, odd public exponent $e$ with $3\le e<n$, private exponent $d$ with $0<d<n$ and $e\,d\equiv1\pmod{r-1}$ for each prime $r$ divisor of $n$.

² For keys otherwise per the above, it limits $u$ (including $u=2$ for $n$ less than 1024-bit, $u\le3$ for $n$ less than 4096-bit, see rsa_multip_cap). It also requires the full factorization of $n$ to be given, as well as reduced exponents and multiplicative inverses.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.