Plaintext that consists of an RSA key is easily recognizable as such, because it
ID: 651407 • Letter: P
Question
Plaintext that consists of an RSA key is easily recognizable as such, because it satisfies certain mathematical properties, in particular (See the answer for Why can an encrypted private key be brute forced?):
d = e-1 mod (p?1) (q?1).
Is it impossible to design a public key system where it was harder to verify that the decryption of the key was successful? The usual answer to protect an encrypted key from being brute forced is to use a larger key size, but I thought hard to recognize plain-text is a good property to have in an encryption system?
Explanation / Answer
A key pair (private key and corresponding public key) is always "verifiable" by simply trying to use it. E.g., if this is a key pair for a signature algorithm, then you can try to sign some data with the putative "private" part, and see if the signature can be verified with the "public" part. There is not much you can do about that.
"Hard to recognize plaintext" was thought as a line of defense in cryptosystems from, say, the 1930s. This was before the invention of the computer, hence algorithms had to be performed by hand or through relatively simple electro-mechanical apparatus. Invariably, they were quite weak and needed the extra safety of having a relatively uniform distribution of plaintext data elements. But we are now in 2011, and we have big computers and good algorithms. To state things plainly: if having a "hard to recognize plaintext" makes any difference, then your encryption algorithm sucks.
With a modern symmetric encryption systems (e.g. AES-128 with CBC mode), plaintext internal structure is not an issue.