fgrieu
Reputation
36,290
99/100 score
 Apr 5 comment Why is CRC said to be linear? Ah, that corrects a long-standing terminology problem I have had, with (wrongly) using linear where affine was meant in a cryptanalytic context! I'll have to scrub my earlier answers.. Apr 4 comment For RSA keys, is the safety of a given key-length different for signing vs encryption? I thing that you mean the other way around. It is always possible to re-sign the original message with a stronger key, and that gives the signature the strongest strength; but re-enciphering the original secret message with a stronger key is pointless if the adversary has the cryptogram made with the weaker one. Apr 4 comment For RSA keys, is the safety of a given key-length different for signing vs encryption? There is a reason sometime given to use longer/stronger keys for encryption of things that are intended to remain secret "forever"; when often, signatures become pointless after a shorter time. Mar 31 comment Speed of a 16384-bit RSA key Also: it you stick to RSA with two prime factors of the public modulus, each will exceed the typical capability of hardware accelerators and tested-secure implementations, thus the very feasibility in secure conditions may be lost. A reasonable compromise could be using multi-prime RSA with 4 factors of 4096 bit each. If that's supported by the hardware (and a lot of lesser ifs) that should allow 16384-bit RSA private key operations to run only about 16 times slower than 4096-bit RSA private key operations with CRT and two factors, beating the $\Theta(b^3)$ scaling by a factor of about 4. Mar 31 comment In case M is small is it possible to recover the message That nice answer works even without using that the given $e=17$ is small. Mar 30 comment How to invert a linear hash function? Hint: write down (perhaps in the question) your definition of a linear hash function. Obtain $H(M_i)$ for all $M_i$ of some fixed size with exactly one bit set, and if that's not implied by your definition, the hash of the all-zero message with that fixed size. Show how you can constructively and efficiently compute a message $M$ of that fixed size with $H(M)=H(M′)$, given $H(M′)$, for any unknown $M′$ of that fixed size (we do not care if $M=M′$ or not). That achieves your goal. Mar 30 comment What are the applications of sha3 algorithm? SHA-3 is a family of hash algorithms, enacted in August 2015, which is recent. Therefore there are few actual uses, if any. Are you asking how members of the SHA-3 family could be used ? Mar 29 comment Is One Time Pad considered Chosen-Plaintext Attack Secure? @jjang: if repeated IND test use the same two keys for enciphering m1for one and m2 for the other, then you first get theses two keys from a probe with chosen (or known) distinct plaintexts; then you pass all tests with total confidence. If the keys used for different tests are random and independent, the system is unbreakable. Mar 29 comment Why is padded RSA not CCA-secure? One obvious additional issue is that with $l(n)=2n-2$ (where $n$ is the number of bits in each of the prime factors of $N$), there remains almost no room for randomness in $r$. Mar 25 comment ChaCha20 core vs ideal unkeyed PRP @CodesInChaos: perhaps the OP considers ChaCha without the final $\boxplus$; but unambiguously, the Salsa20 core includes $\boxplus$, and I see that a lot for the term Chacha core; e.g. here; here; and even arguably by the author here. Mar 23 comment Can the SHA256 hashes of consecutive integers be attacked? Perhaps it should be noted more strongly that what's stated in the question is not enough to insure that the range of possible values of $n/k$ is sufficiently large. For example, we could have $n=2^{88}$ [so that we do not expect anyone but a massively funded adversary to be able to brute force $n$ just by SHA256(n) ], and $m=2^{32}$ [making the attack outlined in the answer feasible with an expected $2^{55}$ hashes and as many memory fetches and like 25 GB memory, which is clearly feasible]. Mar 22 comment Given the first half of a SHA-1 hash, can you predict the second half? That depends on what's hashed. If the first half of the SHA-1 hash of a password is EC461B5480380ECF863D, I bet the second half is 9802EDBE70152AEE1C46. Search the concatenation to see why. When the present page will have been indexed, searching the first half will likely yield the second. Mar 21 comment Algebraic structures in RSA The nature of $*$ in this answer is confusing (at least to me), and that muddies (my perception of) the whole answer. $*$ can't be an associative group law, e.g. in $m*k*k^{-1}=m$. And $k^{-1}$ is not the inverse of $k$ with respect to the law in the group $m$ belongs to. Further, messages that have no inverse modulo $n$ still are valid RSA, and I fail to reconcile that with "RSA encryption can be seen as an operation in a finite abelian group (..)". Mar 21 comment Why is it so hard to make a good KDF? One of the especially difficult aspect of KDF / key stretching functions is that, contrary to most cryptographic functions, speed of implementation in actually used devices is critical to security. Mar 21 comment what is DHE_EXPORT cipher suite There seems to be an history of using that termDHE_EXPORTinstead of DHE_DSS_EXPORT or/andDHE_RSA_EXPORT of RFC2246. Mar 20 comment Finding Private key in RSA with public key, cipher text and plain text As to that part of the question asking for an integer $k$ such that $(k\cdot N-P) = C^d$, is there a typo in that equation, like a minus where plus is thought? If not, what's wrong with the obvious: reduce that equation modulo $N$, combine with $P = C^d\bmod N$, and get to the conclusion that there is a solution only if $P\bmod N=0$, assuming only that $N$ is odd. Mar 20 comment Finding d given everything else in RSA @HennoBrandsma: \$K