poncho
Reputation
39,895
398/400 score
 Aug 28 comment Generate RSA-2048 private key for a VERY fast decryption (don't care if it will be unsecure) @SEJPM: $d=1$ if for every prime factor $p$ of $n$, we have $e \equiv 1 \bmod p-1$. So, I picked an $e$ where $e−1$ is divisible by a lot of numbers, and then tested all those divisors to find which ones were one less than a prime, and then made sure that the product of all those primes was $>2^{2048}$ Aug 28 comment Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$ @111: In the field $GF(p^2)$, we often use a representation $ai + b$, where $i$ is one of the field elements with $i^2 = -1$ (and it turns out not to matter which, as they are isomorphic). In your representation, $i$ is one of two values $4z+3$ and $7z+8$. Aug 27 comment Does Curve25519 only provide 112 bit security? @RichieFrame: actually, 4 of those bits are already accounted for by the fact that the full order size is 255 (not 256) bits, and that the cofactor is 8. DJB does leave one addition bit fixed (however, that's not inherent in the Curve25519; that's how Dan suggests it be used); however even with that change, that reduces the strength to 125.5 bits... Aug 27 comment What was the NSA's reasoning for making their bitwise combination functions in SHA-1 the way they did? Well, one obvious distinction between their F1 and yours is that their F1 has evenly distributed output (assuming the inputs are evenly distributed); yours has a distinct bias towards 1 bits. Aug 26 comment Inverse public-key encryption What are you actually worried about? Is it that someone can figure out how to fake a response from your server (and if so, a good signature algorithm would fix that)? Or, is it that someone would modify your Java application so that it no longer cares whether it can talk to the server? The latter is a much tougher problem. Aug 26 comment Possible to determine equivalence of hash codes from different hashing functions? @P.Anderson: actually, after I wrote this, I realized that if $i$ and $j$ were relatively prime, you could reconstuct $SHA256(x)$ from $H_i(x)$ and $H_j(x)$. This isn't fatal, though; one way to make this work is to make our 'indicies' values which aren't relatively prime; for $H_i$, we use the exponent $3 \times 5 \times 7 \times ... \times p_n / p_i$, where $p_i$ is the ith odd prime (and where $n$ is the total number of indicies). That way, even with all the values $H_i$ other than $H_j$, we still can't recover $H_j$ Aug 25 comment Complement of information on software usage Are you looking for shareware to generate such images? If not, what precisely are you asking for? Aug 24 comment What is the difference between a random oracle and a probabilistic algorithm? One important distinction is that the random oracle is generally considered public (that is, the adversary is free to make queries to it); for a probabilistic algorithm, we don't expect that the adversary has special insight into the choices we make (he might be able to deduce them from the ciphertext) Aug 24 comment How can I handle the situation if key size is less than 64 bits in DES? Actually, it's not historic; instead, a DES key is defined to be 64 bits. Yes, 8 of those bits do not actually contribute for the transform (and so are typically ignored for cryptographical purposes), but as far as the API is concerned, all 64 bits need to be there. Aug 24 comment Possible to determine equivalence of hash codes from different hashing functions? @P.Anderson: I was thinking about two different approaches; one just did the same approach, but using Whitebox cryptography. The other approach was to use public key crypto; one approach (extending the comparison function to include the $i, j$ values) would be to define an RSA modulus $m$ with secret factorization, and $H_i(x) = SHA256(x)^ i \bmod m$ (with obvious restrictions on the $i$ values), and defining $F(M_i, i, M_j, j) = (M_i^j == M_j^i) \bmod m$ Aug 24 comment How many bits to flip in an RSA public key to do signature forgery? @dannycrane: In that clause, I was assuming that the public exponent $e=3$. A simple calculation (and substituting in the value of $e$) gives $2.89 \times 1/(3-1) \approx 1.44$ Aug 24 comment How feasible would it be to generate 300 million public key pairs in 8 hours? @fgrieu: One reason this may come up is if you're trying to generate an RSA private/public key where the public key has a specific fingerprint. Aug 22 comment How can you produce visual cryptography? Actually, I believe that the combination function used in the example is AND, not XOR. That is, the pixel in the final image is white only if the pixels in both the original images is white. That said, it turns out the generation process still (mostly) works (!) Aug 21 comment Probability of $D_k(a*k+b) =p$ for a PRP What's $p$? Is that another free choice, or is it a fixed value? Also, is $*$ multiplication mod $2^{128}$? Or, is it multiplication in some representation of $GF(2^{128})$? Aug 18 comment Usage of Zero-knowledge proofs for NP-complete languages If you had a PPT algorithm that could find a coloring in a graph with nonnegligible probability, then you can likely use it to break AES (or RSA or EC); to find the setting of key bit i, generate two SAT instances, one with a solution if the bit is 0, and one with a solution if the bit is 1; convert those into G3C problems and hand both to your PPT algorithm. If it finds a coloring in one of them, then you know that bit setting. Because of this nonrigorous argument, it appears unlikely that any such algorithm exists (assuming $P \ne NP$) Aug 18 comment Would the encryption of bigrams and trigrams weaken the code? Obvious question: suppose that 'th' was one of your frequent bigrams; then suppose you encrypt the three character plaintext string 'sup' as the two letters 't' 'h' and the bigram 'th'. How would the decryptor then know that the ciphertext 'thth' consisted of three symbols 't', 'h', 'th', and not any of the other 3 ways to lex it? Aug 18 comment Is calculating HMAC from hashed input a good idea? It comes down to what the question is. Is it "would doing HMAC(K, H(M)) yield any practical attacks", or "might there be academic attacks on HMAC(K, H(M)) that would be easier than HMAC(K, M)?" Aug 15 comment Perfect secrecy with n-time key Actually, in your example, $E(M) = (K_1M + K_0) \bmod p-1$, then either you leak $M_0 - M_1 \bmod 2$, or you can't uniquely decrypt. If $K_1$ is even, you can't uniquely decrypt (because $p-1$ is even). If $K_1$ is odd, then $E(M_0) - E(M_1) \equiv M_0 - M_1 \pmod{2}$ (again, because $p-1$ is even). Try $E(M) = (K_1M + K_0) \bmod p$ instead Aug 14 comment Simple example to describe Bilinear mapping @hanugm: I selected 3 because the order of 3 (mod 11) is 5; that is, $3^5 \bmod 11 = 1$ and $3^x \bmod 11 \ne 1$ for $0 < x < 5$. Any such value with this property will work, and in fact, 5 will (in fact) work. Aug 13 comment How to hash similar strings to the same hash value? And, it's easy to show that the only hash function where $H(s_1) = H(s_2)$ holds consistently is one which is constant (for a specific input length). So, assuming that a constant output isn't the answer you're looking for, how often must $H(s_1) = H(s_2)$ hold?