It is almost straightforward to use a famous large unfactored composite N to RSA-encrypt a message so that it will only become readable in the future when the composite gets factored (previously part 1: such a message would currently be readable only by a higher power): just raise (modulo N) the plaintext to an encryption exponent of your choosing, and package N and the encryption exponent with the ciphertext.
Interesting candidate N are the Fermat numbers, because people will keep working on factoring those. However, I don't know whether the special form of Fermat numbers might allow breaking RSA without factoring. (Probably not.)
The message could be a cryptocurrency prize encouraging efforts to factor Fermat numbers. Though such a prize might discourage cooperation.
This is kind of a cryptographic time capsule, or time-lock encryption.
It's only "almost" straightforward because the encryption exponent should be relatively prime to eulerphi(N), but we can't compute eulerphi(N) without knowing the full factorization of N. A workaround is to encrypt the same message with different exponents, producing multiple ciphertexts, hoping at least one of them satisfies gcd(e,phi)=1. Also, choosing a large prime number as the exponent can make the probability of a common factor with phi astronomically low.
It might be dangerous to encrypt the same plaintext with different encryption exponents. Prepend nonces to make the plaintexts different. This is already a standard operation in padding, e.g., OAEP.
If a partial factorization of N is discovered (or already known), can it be used to crack the whole ciphertext? ("Security of multi-prime RSA") If using a partially factored Fermat number as the modulus N, can one elegantly still use the whole Fermat number as the modulus, or does one need to use only the currently unfactored cofactor?
No comments:
Post a Comment