dr jimbob
Reputation
795
Next privilege 1,000 Rep.
 Mar 7 comment Best non-digital cipher? Complicated rotor-cipher machines like Enigma were probably state of the art in the late 1930s early 1940s. I'm not saying there was widespread agreement it was best anymore than there's no widespread agreement about any modern cipher is widely considered the undisputed best. (This ignores one-time-pad OTP which is intrinsically unbreakable with random pad, but require securely exchanging a pad that is the length (or greater) of the secret message by some secure method prior to communication). Feb 24 answered What does the comma mean in m, c := E(K, m) Feb 5 awarded Critic Feb 5 comment Why do “nothing up my sleeve numbers” have low entropy? @PaulUszak H = -Σpᵢ log pᵢ is an exact formula the entropy of random strings generated with probabilities pᵢ. If you have many random strings generated with a total entropy of N bits, it will be impossible (in aggregate) to losslessly compress such data with less than N bits. This does mean that H is an estimate or upper bound on the entropy; it means this calculated entropy sets a lower-bound on the size of losslessly compressed data (in aggregate). Furthermore, 11.9 bits is not less than 7.3. See: en.wikipedia.org/wiki/… Jan 25 awarded Commentator Jan 25 comment Why do “nothing up my sleeve numbers” have low entropy? @PaulUszak - Simply generate say N=100,000 random 50 digit passwords and write them to a text file. Try any method of encoding or compression (that doesn't have knowledge of some phenomenon underlying the randomness of how the 50-digit passwords were generated; e.g., no access to PRNG seeds). If you can encode 100k such passwords in less than 166*N = 16,609,640 bits (about 2.07 MB), then you've shown it's an overestimate. As quick check, applying standard compression (which adds things like checksums), I can compress such a file to about 2.15 MB (bzip2) which is 172 bits/pw. Jan 25 comment Why do “nothing up my sleeve numbers” have low entropy? @PaulUszak - I never said Shannon entropy and Kolmogorov complexity are equivalent concepts, they aren't. I said they are related concepts (which they are see for example: en.wikipedia.org/wiki/Kolmogorov_complexity#Relation_to_entropy or homepages.cwi.nl/~paulv/papers/info.pdf or www-isl.stanford.edu/~cover/papers/transIT/0331leun.pdf ). Second, I have read Shannon's 1948 paper and see his theorem 2 defining entropy as H = -Σpᵢ log pᵢ . This isn't an approximation or upper bound and if it was a gross overestimate, prove it. Jan 14 comment Why do “nothing up my sleeve numbers” have low entropy? The formula for Shannon entropy is S = - Σ p_i log (p_i) where you iterate over all possibilities. E.g., if you have a 1 digit password where all 10 digits were chosen uniformly p_i = 1/10 for all i (from 0 to 9), then S = - 10 * (1/10 lg (1/10)) = lg 10 ~ 3.322. Similarly for 2-digit there are N=100 possibilities, each with prob p=1/100, so S = lg 100 = 2*lg 10 ~ 6.644. Thus, for 50 digit passwords, each password is chosen at p=10^-50 and there are 10^50 of them, so the Shannon entropy of generating a random 50 digit password is exactly S = 50*lg 10 (which is approximately 166.096). Jan 14 comment Why do “nothing up my sleeve numbers” have low entropy? @PaulUszak - If I need to send someone a trillion 0s, you don't say the entropy is a trillion bits. You merely agree on an appropriate compression scheme for that type of data, say a digit and how many times to repeat that digit. Then it ends up being under 100 bits (~40 to store a trillion, plus the digit (maybe 8 bit) to repeat and some overhead to indicate the compression scheme, separators, end of transmission). Similarly, if you needed to send the first digits of pi efficiently, you could use a compression scheme that transmits a formula for pi and the number of digits to calculate. Dec 13 comment What is a good algorithm to scramble data in a 2-D grid @JoshKurien By not particularly secure, I'm stating that if you have a scrambled message, it may be possible to unscramble it (by searching for valid english words and letter counts) as well as modify the scramble message. (E.g., if the message was ATTACK AT DUSK scrambled to CTA TSAK*K DATU* someone can put it in an anagram finder and decipher the message, figure out what permutations could have been used to recover the key (unique up to repeated letters) and then change the message.) Dec 12 answered What is a good algorithm to scramble data in a 2-D grid Dec 8 revised What is the lowest level of mathematics required in order to understand how encryption algorithms work? Dead link. Oct 25 revised Is md5(x)&md5(y&x) secure? added 2 characters in body Oct 25 revised Is md5(x)&md5(y&x) secure? added 2 characters in body Oct 24 answered Is md5(x)&md5(y&x) secure? Jan 28 awarded Yearling Sep 24 awarded Autobiographer Jul 8 awarded Good Answer May 16 answered Why do “nothing up my sleeve numbers” have low entropy? Apr 30 awarded Citizen Patrol