Next privilege 1,000 Rep.
See votes, expandable usercard
5 9
~14k people reached

  • 0 posts edited
  • 1 helpful flag
  • 11 votes cast
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).
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:…
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.
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: or or ). 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.
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).
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.
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.)
comment What is the lowest level of mathematics required in order to understand how encryption algorithms work?
Yes, XOR is minimal (but does it provide a "good understanding" of encryption?). The perfect security of OTP doesn't matter in practice, since OTP requires securely storing a key that's the same size as the text (and only using it once) so its rarely used in practice (why not just store the text securely)? But the math I mentioned doesn't require devoting your whole life to it; learning modular arithmetic to understand RSA takes a few days at most if you take the time to digest each part and play around with toy examples. Yes, there's much more to learn after that, but its easy to start.
comment Is every output of a hash function possible?
@fgrieu - No its demonstratable. H(m) maps {0,1}^infinity to {0,1}^N for an N-bit hash function. So, H(H(m)) at the outer function call takes {0,1}^N as input and maps it to {0,1}^N. Thus if we assume one single collision exists (which we expect with overwhelming probability for any hash function -- they intend to attack as random oracles not as permutations), then by the pigeonhole principle the whole output space is not reachable.
comment LT codes with Homomorphic hashing
@makerofthings7 ⊕ is one customary way of writing xor (exclusive or).
comment Can I construct a zero-knowledge proof that I solved a Project Euler problem?
@poncho - yes edited obviously was not thinking clearly. (The answer I got is roughly 1/3 of that so that's a much more reasonable limit).