Reputation
26,609
Next tag badge:
419/400 score
79/80 answers
Badges
2 37 113
Newest
 Nice Answer
Impact
~412k people reached

Jul
30
comment Why calculate pi to estimate randomness?
@Paul Uszak: Generating random numbers, and testing them, is fascinating; that's the state of mind at fourmilab's hotbits. Their generator seems to be a high-quality, physically-seeded TRNG, with multiple statistical tests at the lightly-conditioned output, which is fine. However their use of the π-by-Monte-Carlo test is more an extra, simple demo that the thing works, for added confidence that there's no horrible goof, than a test designed for real use in fielded cryptographic devices.
Jul
28
comment Library to find an addition chain for a large number?
A reference to some of the best solutions known to the problem of addition chains (without subtraction) is Daniel Bernstein's Pippenger's exponentiation algorithm
Jul
27
comment Permuting Small Sized Set in Practice
In this pseudocode, t = rand(0, i) must generate a random integer uniformly distributed among the i+1 integers in range [0,i] inclusive; otherwise the permutation is distinguishable from random, especially for small sets.
Jul
27
comment Permuting Small Sized Set in Practice
What's wrong with the Fisher–Yates shuffle, which is the archetypal way to randomly make a permutation of a set small enough that we can store the index of each element? Or/and (especially, for wider sets) enciphering the index using one of the many techniques of Format-Preserving Encryption and a fixed key?
Jul
24
comment Collision or second preimage for the ChaCha core?
If we could demonstrate that the ChaCha core is not a bijection (other than for 0 rounds, where that result is trivial), it would be something. I conjecture that's feasible for few rounds (like 2), but becomes infeasible for enough rounds to reach security (like 8 or more). The final addition destroys the argument of bijection, but lack of argument for a proposition does not prove that it does not hold (much less provide a counterexample).
Jul
24
comment Collision or second preimage for the ChaCha core?
Nitpick: the final addition in the core makes it not easily invertible. We know how to make public, easily computable functions over a 512-bit domain that are demonstrably bijective, but quite computationally hard to invert for arbitrary output (admittedly, building such function using only ARX operations requires a lot of these).
Jul
24
comment Collision or second preimage for the ChaCha core?
Summarizing the discussion: the theorem prover proved that 2 rounds of ChaCha can't collide; this is not directly related to the ChaCha core with 2 rounds colliding. $\;$ It did not answer on if the ChaCha core with 10x2 rounds collides. In fact, if an automated tool could prove or disprove that the ChaCha core with only 2 rounds has collisions, that would be even more an achievement than proving that for the Salsa20 core. $\;$ There are strong heuristic arguments that there are collisions for the ChaCha core using enough rounds for security, we just do not know any (for now).
Jul
17
comment How many bits to flip in an RSA public key to do signature forgery?
@dannycrane: Yes, in $2/{\log_e n}$ the letter $e$ is the base of natural logarithm, not the public exponent. $\;$ No, in $(1 - 2/{\log_e n}) ^ {\log_2 n - 1} \approx 0.044$, exponentiation is meant; think of $\log_2 n - 1$ as a number of trials, each flipping a bit with odds $1-2/{\log_e n}$ of not reaching a prime.
Jul
17
comment How many bits to flip in an RSA public key to do signature forgery?
Nice. Flipping a single bit of $e$ to make it $1$, if $e$ is suitable (most $e$ used in practice are), and that's accepted by Alice (which would not be unseen), is another way, involving less work.
Jul
17
comment How many bits to flip in an RSA public key to do signature forgery?
Do you mean: Eve is restricted to invent (e', n') that differ from (e, n) in a small number of bits ? If yes, what is the convention used to map (e, n) to a bitstring ? In particular, would it prevent changing the customary e=65537 to e=1 by flipping the high-order bit, or would that be otherwise rejected by Alice ?
Jul
11
comment Why should the primes used in RSA be distinct?
@rt_mn: in RSA with distinct primes $p$ and $q$, $d\equiv e^{-1}\pmod{(p-1)\cdot(q-1)}$ is a sufficient, but not necessary condition for $d$ being a valid private exponent.
Jul
10
comment How far is public-key crypto involved in “banking world”?
As to your first bullet: yes, see EMV 4.3
Jul
8
comment RSA algorithm assignment
Hints: a) consider what happens when $e$ is small; say 3, 5, or 17, which are reasonable choices when proper padding is used. $\;$ b) regardless of $e$, consider odds that $K$ can be written as the product of two integers neither exceeding, say, $2^{40}$.
Jul
7
comment RSA with $\lambda(n)$ or $\varphi(n)$
@tylo: very right. My mistake. I wish I could edit (rather than delete) wrong comments.
Jun
25
comment what are the most common stream ciphers algorithms?
I think you mean Salsa20 (a family of 3 stream ciphers Salsa20/8, Salsa20/12, Salsa20/20) rather than ChaCha20 (the 20-round version of ChaCha), since ChaCha was published in 2008.
Jun
25
comment Why is HMAC-SHA1 still considered secure?
There seems to be a confusion in the question: HMAC-SHA1 is not used for signing a document (at least, not usually; and assuming it was, the standard assumption for HMAC that its key input is secret can't hold since the signature verification procedure is public). I find that answer quite fine.
Jun
25
comment Implementing AES MixColumns with fewest XOR gates
@RFuentess: AES decryption is much less common than AES encryption, because AES tends to be used in CTR mode (sometime OFB or CFB, and for authentication CBC-MAC) which all use AES encryption only (including during decryption); not coincidentally, AES decryption is unavoidably slower and bigger than encryption. That likely explains why AES decryption was not coded. $\;$ I'm not the author or otherwise related to the nice code that I linked to; I only highly recommend it as the theoretical basis of a compact 8-bit implementation.
Jun
23
comment Attack for RSA 1024 bit with Low Public Exponent
@poncho: Great, that's what I was attempting in 5, done the right way, that I missed entirely! You nailed it!! I'll update the answer.
Jun
23
comment Attack for RSA 1024 bit with Low Public Exponent
@poncho: Had the same idea but you beat me on publishing first!
Jun
23
comment What is the danger if a non-prime is chosen for RSA?
The question is very similar to this one. To summarize my answer: if it accidentally happened that we use a composite, most likely the RSA key pair would fail on first use (in a PKI: when the certification request is checked, thus thus wrong key would not get certified). Another option, so unlikely that the combination of bad luck and a hardware defect is not enough to cause it, is that it was picked a Charmichael number instead of a prime, in which case RSA will work.