Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

I have a couple of related questions:

I read about an estimate, ascribed to Turing, of the entropy of English text to be between 0.6 and 1.3 bits per letter. The modern day corpus, including the huge and exponentially ever expanding volume of materials accessible via the Internet, is different from the one available a century back. Is there a revised estimate?

If one simply takes two books from one's small private library (that contains e.g. only very common novels) and arbitrarily select two starting points to combine with xor the letters, then the resulting pseudo-random sequence presumably could be argued to have a non-negligible risk of being attacked through brute-force by a knowledgeable opponent. But the actual choice of materials (including especially those via the Internet) to be combined is nowadays virtually unlimited. If one could thus appropriately choose a sufficiently large number of text sources to be combined, wouldn't the result be practically secure for crypto usages in view of the combinatorial explosion of the complexity that the attacker has to deal with? One could certainly also employ some more complex operations than xor and even a couple of different operations either simultaneously or in variations. Are some good schemes in this direction already being used in non-trivial practical applications?

share|improve this question
But since you - obviously - no longer have unconditional security, what advantages does this awkward and complicated scheme have over just using generic cryptographic primitives? – Thomas Feb 4 at 11:58
For practical applications, one commonly doesn't always necessarily require theoretical unconditional security. No crypto algorithm used in practice is absolutely theoretically secure IMHO. In other words, one does compromises to achieve one's purposes in some presumably optimal way. – Mok-Kong Shen Feb 4 at 12:30
Which is exactly what I said. What advantage does your scheme have over, say, using AES? And what advantages does AES have over yours? In your application, that is. – Thomas Feb 4 at 12:43
Firstly, it could serve other purposes than "directly" for encryption, for example to generate keys for ciphers. Secondly, if it turns out to be a satisfactory way to obtain entropy-rich sequences, than its usage as key stream for stream encryption would also be practically feasible. Awkwardness you mentioned is a rather subjective issue. What really counts would be simplicity and that is the case with the scheme IMHO. – Mok-Kong Shen Feb 4 at 12:56
1  
How is collecting a huge library of texts, and generating something that sort-of kind-of looks random from it, simpler and less awkward than generating 128-256 pseudorandom bits from a well-vetted and easily accessible source of entropy? Your scheme doesn't even let you measure the amount of entropy you're collecting to any degree of accuracy ("entropy" is a lot more than just "english text has 0.6 to 1.3 bits of entropy per character"). – Thomas Feb 4 at 13:00
show 1 more comment

1 Answer

up vote 2 down vote

Shannon's paper Prediction and Entropy of Printed English details the experiment to determine the entropy of English. Without getting into too much detail, it's only really proper to talk about the entropy of a source of information. You can estimate the entropy given a sample of the source's output and it's fair to say that Shannon's method gives an estimate for the upper bound. A more sophisticated experiment would give a lower estimate for the upper bound. Another way to arrive at an upper bound would be to look at the results of a competition to compress a portion of wikipedia which shows that 100M of English can be compressed into 16M.

I'm reminded of a similar scheme I read about which relied on a long stream of publicly available bits derived in this case from digitizing a picture of the surface of the moon. I can't find the reference but I'm sure it would be relevant, although of purely academic interest.

There are no practical schemes that I am aware of which use your idea or anything similar. You would have to ask yourself what security guarantees you're trying to achieve and whether this really is the best way of obtaining them. I believe that it should always be preferable to implement your system using established cryptographic primitives in the prescribed fashion.

share|improve this answer
I meant that, if a good lower estimate is known, one could, to be conservative, use a somewhat still smaller value and thus be able with a rather simply coding to obtain letter sequences that achieve sufficiently high entropy value for practical use. (The main point is simplicity.) – Mok-Kong Shen Feb 4 at 14:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.