Crypto-making vs Crypto-breaking

[Ben Laurie]

Eric Cordian wrote:
> In box number two is technology that will break any crypto designed by
> mankind in the next 1000 years.

Such a machine cannot exist. Proof:

Let O be an oracle such that any encrypted message, E can be decrypted
by O. That is, if E=Enc(M), then O(E)=M. Now, encrypt a message I as
follows.

If bit 0 of I (I_0) is 1, then choose E_0 s.t. the MS bit of O(E_0)=0
If bit 0 of I is 0, then choose E_0 s.t. the MS bit of O(E_0)=1

Then for each subsequent bit, proceed as follows:

If I_n is 1, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS
bit that is 0.
If I_n is 0, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS
bit that is 1.

Then the encrpytion of I is X=E_N||E_{N-1}...||E_0, and, by
construction, O(X) != I.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff