Yes, RSA without padding is susceptible to chosen ciphertext attacks, small exponent attacks, etc. "Cryptography is a mixture of mathematics and muddle, and without the muddle the mathematics can be used against you." — Ian Cassels, former Bletchley Park cryptanalyst and & Professor of Maths at Cambridge. In RSA, the muddle is OAEP: http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding On Mon, Aug 19, 2013 at 9:00 PM, Warren D Smith <warren.wds@gmail.com> wrote:
E.Salamin claimed if simplicity paramount, using RSA as a secret key cipher (perhaps with a few modifications?) ought to have security exponential in bit length N, not in N^(1/2) or N^(1/3), and it is very easy to describe.
At first I thought: there is much to be said for this suggestion. But I think "simplicity" has to be reckoned not merely in terms of mathematical conceptual simplicity, but also in terms of the program size, and effort to verify and fully comprehend the program.
---
Anyhow, for this approach: M=p*q is a product of 2 primes p,q; or for this mode we might more simply make M be a prime. Then E and D related by E*D mod EulerTotient(M) = 1 are the two secret keys, E for encrypting, D for decrypting, and a message X is encrypted to X^E mod M, and ciphertext Y is decrypted to Y^D mod M. M is also part of the secret key.
M is deducible if attacker has black box access to a cryptor box -- you binary search to see how large allowed to go, to deduce M. One that is done, M can be factored in subexponential time. Also, if know M and have a plaintext-ciphertext pair then can deduce E and D by solving discrete log problem in subexponential time.
So... sorry, you lose. This "RSA as secret key cryptosystem" suggestion is breakable in subexponential, not exponential, time, by certain kinds of attacks, whereas, conventional secret key ciphers are thought/hoped immune to all such attacks even in exponential time.
----
However... suppose we instead employ a 4-round Feistel cipher whose frobulation function is a discrete exponential. I.e. divide the message into two halves A and B. Now perform A = A XOR DiscreteExponential(B) B = B XOR DiscreteExponential(A) A = A XOR DiscreteExponential(B) B = B XOR DiscreteExponential(A) and output the new A,B as the ciphertext. (Decrypt by going thru the 4 steps in reverse order.) The exponents in the discrete exponentials will be the secret keys. All will have the same modulus which will be a public constant large mersenne prime, specifically M=2^127 - 1 causing the message to be 127*2=254 bits long where a few "all 0s or all 1s" message-types are forbidden. If 4 general exponents were used this would be 127*4=508 bits of secret key, but if we agree that 2 of the exponents are determined in some simple public way by the other two (e.g, specified linear relations), then only 254-bit-long secret key needed.
And I see no way to attack this in subexponential time, albeit perhaps there is some way which takes a smaller exponential that you might have hoped for.
This here suggestion, it seems to me, might actually be a good candidate. In terms of conceptual simplicity it is hard to beat, but in terms of either efficiency or program length & effort it seems pretty bad versus rivals. On other hand if language already supports discrete exponentiation so you do not need to program it...
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com