Samuel Neves

1,027 reputation

bio	website
	location
	age
visits	member for	1 year, 9 months
	seen	1 hour ago
stats	profile views	34

	1,027 reputation	bio	website		visits	member for	1 year, 9 months
49 badges		location			seen	1 hour ago

summary answers questions tags badges favorites bounties reputation activity

23 Comments

suggestions reviews revisions comments badges posts accepts all

Apr 2	comment	“Weaknesses” in SHA-256d? By find colliding $m, m'$, you can forge $H(m \, \|\| \, K)$ authenticators in $2^{n/2}$ time instead of $2^n$.
Mar 28	comment	*Solving hard problems in $\mathbb Z_{p}^{}$ when $\mathbb p$ is close to $\mathbb 2^{n}$** I cannot. It is possible that with clever methods (tuning the regular polynomial selection methods) we can can come up with better bounded polynomials easily, but I have found no existing work on this.
Mar 26	comment	*Solving hard problems in $\mathbb Z_{p}^{}$ when $\mathbb p$ is close to $\mathbb 2^{n}$** Thanks, the notation was indeed suboptimal.
Mar 25	comment	Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus? You're right, fixed.
Jan 24	comment	Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack I used SAGE, it has all kids of useful things. I've posted the code to do the above here.
Jan 10	comment	Is it possible to break a hash-based block cipher? CBC doesn't help you; what you get is something like Block 0: IV Block 1: IV ^ M[0] ^ H(K, 0) Block 2: (IV ^ M[0] ^ H(K, 0)) ^ M[1] ^ H(K, 1) ... By XORing IV with the first block, the first with the second, etc, you are able to recover M[i] ^ H(K, i)
Jan 10	comment	Is it possible to break a hash-based block cipher? What you describe is not a block cipher, as a block cipher by definition has no notion of position (i.e. $n$). What you're describing is a stream cipher made out of a hash in counter mode (see Salsa20 for a similar construction).
Jan 9	comment	Choosing good parameter for Lenstra's elliptic curve factorization I am unsure what you mean by "factor" in the ECM case; if you mean the integer multiplied by P, then yes, that's it.
Jun 26	comment	How does the cyclic attack on RSA work? Right, just changed the answer to make the modulo explicit.
Jun 13	comment	Why would anyone use an elliptic curve with a cofactor > 1? Yeah, you're right. Whenever the $xy$ coefficient is nonzero, there's a trivial order 2 point. When it's not, you get either singular (unusable) or supersingular (weaker) curves.
Mar 29	comment	SHA3 conference highlights? Both papers and slides of the presentations are available at csrc.nist.gov/groups/ST/hash/sha-3/Round3/March2012/… It's unclear what else you are asking for.
Jan 18	comment	Pairing-friendly curves in small characteristic fields Understood. Should not have just skimmed the paper...
Jan 17	comment	Pairing-friendly curves in small characteristic fields I marked the above reply correct because I failed to specify genus in my question --- Freeman does seem to provide pairing-friendly curves in $J(F_{q^k})$ for genus 2. In genus 1, what you say makes sense.
Nov 16	comment	Are there practical upper limits of RSA key lengths? An an addendum, I actually made the experiment. Generated 3 $2^{20}$-bit numbers $a$, $b$ and $m$, and performed various arithmetic operations (using GMP): $a·b \bmod m$: 0.08s; $a^{65537} \bmod m$: 1.16s; $a^b \bmod m$: 107873.130s (~29 hours).
Nov 14	comment	Are there practical upper limits of RSA key lengths? To be fair to RSA, 1 million bits is well over the FFT range. Encryption is closer to $O(n \log n \log \log n)$, and decryption $O(n^2 \log n \log \log n)$.
Oct 6	comment	How to calculate the time it'll take to crack RSA or DH? It's probably worth pointing out that the main difference between the NFS for factoring vs discrete log is the linear algebra step: in the former, we only have to solve a matrix modulo 2, while the latter requires it be solved modulo $p-1$, which greatly increases the cost of this step (even ignoring space and communication constraints).
Sep 30	comment	How robust is discrete logarithm in GF(2^n) ? Note that the Weil descent approach to elliptic curves of composite-degree transfers the discrete logarithm from $E(\mathbb{F}_{2^n})$ to $J(\mathbb{F}_{2^{(n/p)}})$, where $p$ is some divisor of $n$, and $J$ is the Jacobian of a high-degree hyperelliptic curve where the discrete log might be faster. The original question, however, was about discrete logarithms in the base field $\mathbb{F}_{2^n}$; the Weil/Tate pairing might be used to transfer $E(\mathbb{F}_{2^n})$ to $\mathbb{F}_{2^n}$ (MOV and FR attacks).
Sep 23	comment	Is there a simple hash function that one can compute without a computer? Squaring modulo something wouldn't be NP-hard; if modulo a prime, we know how to compute square roots efficiently, and if modulo a composite reduces to factorization, which is not known to be in NP-hard or NP-complete.
Sep 21	comment	Accelerating SHA-1 In an SSL server, you are serving many independent (parallel) clients simultaneously...there's plenty of coarse-grained parallelism to explore there. Not sure whether that is your case. Note that you can also explore SIMD (XMM, soon YMM) registers to perform 4 (resp. 8)-way SHA-1, along with multiple cores/GPU.
Sep 9	comment	Mapping points between elliptic curves and the integers This is probably a silly question, but doesn't regular point compression almost do this? Granted, the output is not in $Z_p$, but it's guaranteed to be in $Z/(2p+1)Z$.