Reputation
36,290
Next tag badge:
99/100 score
20/20 answers
Badges
2 56 151
Newest
 Good Answer
Impact
~631k people reached

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<e$, thus $K$ is small when $e$ is. In particular $e=3\implies K=2$. That does not harm security in any known way, when proper RSA padding is used.
Mar
17
comment Is there a standard notation for a message concatenated with its signature?
@Cryptostasis: what you describe is a message with its signature as appendix appended, and a degenerate form of signature with message recovery. Signature with message recovery is a more general concept, where the message (or some fraction of it) can be recovered from the signature. With RSA and small $M$, an example is $\sigma_{(e,d)}(M)=(M\|H(M))^d\bmod N$; or for something with provable reduction to the RSA problem, $\sigma_{(e,d)}(M)=(\operatorname{PRF}(M\|H(M)))^d\bmod N$ where the public PRF could be based on few rounds of a public Feistel transformation.
Mar
17
comment Demonstrating the insecurity of an RSA signature encoding scheme
@verdict: my statement was wrong (though on the right tracks); I've revised it, and give a justification.
Mar
11
comment Implementing RSA with small integers in CUDA
Many 10y old are familiar with algorithms to perform integer multiplication, and Euclidian division yielding remainder (and quotient), for integers with multiple decimal digits. On a computer, it is more efficient to use base $2^n$ where $n$ is just small enough that $n$-bit values can be efficiently used as operands of multiplication with exact result. In the case of something written for the CUDA compiler you consider, that might be base $2^{32}$. These multiplication and division with remainder algorithms are the hardest part of implementing a working RSA (but not a side-channel proof one).