dr jimbob
Reputation
795
Next privilege 1,000 Rep.
5 9
Impact
~14k people reached

• 0 posts edited

# 44 Actions

 23h comment Should RSA primes p and q differ in length by “a few digits”? @gtrwoot - My guess is it was clear to Rivest et al, that if p and q were too close together there are ways to quickly factor N and undermine the security. They made the recommendation to ensure p and q differed in length by a few digits, so if p is the larger prime and is say 3 (decimal) digits longer you have p - q ≈ p - p/1000 ≈ .999 p ≈ p ≈ sqrt(N) >> N^(1/4). Hence Fermat factorization based on p being near q won't work when p and q differ in length. That said just randomly picking two n/2 bit primes will with high probability result in them being O(sqrt(N)) apart. 1d comment Should RSA primes p and q differ in length by “a few digits”? 1d comment Should RSA primes p and q differ in length by “a few digits”? Who said this? It's customary for say 2048-bit RSA to choose two 1024-bit primes that have the same length. That said there are efficient attacks on RSA if p-q is too small. See: en.wikipedia.org/wiki/Fermat%27s_factorization_method or trial division starting from the nearest odd integer to sqrt(N). (This technique is very efficient when |p-q| < O( N^(1/4) ) 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