Reputation
38,270
Next tag badge:
384/400 score
80/80 answers
Badges
1 36 82
Impact
~570k people reached

2h
revised Is Paillier cryptosystem commutative?
Paillier addition is not a field operation (the power is a non-prime-power). It is a group operation, and that sufficies.
4h
answered In which step does AES use the key to encrypt data?
1d
comment Library to find an addition chain for a large number?
What do you mean by 'good'? The simple-minded binary method gives a decent one (within 50% of optimal for random inputs), and is completely trivial to compute. If that's not good enough, how close to optimal are you demanding?
1d
comment Permuting Small Sized Set in Practice
I believe you need to rethink what security means in this context. It doesn't mean that the attacker can't take a guess at the permutation (and have a $1/|S|!$ chance of getting it correct). Instead, it's that the attacker doesn't get any additional information about the permutation. That is, even if $|S|=2$, the attacker knows that either the two elements remain where they are, or that they are swapped; but he doesn't know which it is.
1d
answered Reduction to cdp,dl or cdh?
1d
comment Reduction to cdp,dl or cdh?
Where does the randomization come into play? $f(x) = g^{sk \cdot x} \bmod p$ (for fixed $g$, $sk$, $p$) looks determanstic.
1d
comment Construction of ElGamal signature?
As for a hint to #1, if you know $s$ and $r$ with $s = k^{-1}(m + ar)$ (for some unknown $k$, $a$; what would you need to adjust to make an $s' = k'^{-1}(rm + ar')$ (for some $k'$, $r'$ that are related to the original $k$, $r$)? I'd suggest trying to figure out what $r'$ needs to be first; then going back to the $r = g^k$ relation to deduce what $k'$ needs to be.
1d
answered Ephemeral key is held constant in ElGamal
Jul
23
comment parallel shifters
You might want to revise your question - I really can't make heads or tails of it. You might want to outline what problem space you're looking at (e.g. does 'register' mean a CPU register, or a set of flipflops on an FPGA?); you probably want to be a bit more explicit about the question as well.
Jul
22
revised Fast attack on approximate GCD problem?
added 117 characters in body
Jul
22
answered Fast attack on approximate GCD problem?
Jul
20
comment How many bits to flip in an RSA public key to do signature forgery?
@dannycrane: that was discussing the $e=3$ case; if $n = pq$, where $p$ and $q$ are primes, then $p=2 \pmod{3}$ (because that's a requirement that RSA makes if $e=3$) and $q = 2 \pmod{3}$ (ditto), and hence $pq = 2\cdot 2 = 1 \pmod{3}$. As for what $n - n'$ is nonzero mod $e$, well, flipping bit $k$ of $n$ will either increase it's value by $2^k$ (if the bit was original 0), or decrease it by $2^k$ (if it was 1). Hence, $n - n'$ is either $2^k$ or $-2^k$. As $e$ is odd, then neither $2^k$ nor $-2^k$ will be a multiple of $e$, and that's what $(n - n') \bmod e \ne 0$ means
Jul
19
answered What is the run-time on finding collisions with MACs,…?
Jul
19
reviewed Reviewed Is a book cipher provably secure?
Jul
19
comment Is a book cipher provably secure?
How is this an answer to the question?
Jul
19
reviewed No Action Needed What values constitute failing for ENT tests?
Jul
18
comment How many bits to flip in an RSA public key to do signature forgery?
@dannycrane: what I was thinking was that we knew that $n' \bmod e \ne 0$ (because we previously checked that $n'$ was prime), and hence there are $e-1$ possible values of $n' \bmod e$, one of which is 1. Actually, if we look deeper, it's rather more complex. Actually, if $e=3$, and $n$ is a standard RSA modulus (with two prime factors), the probability that $n' \bmod e \ne 1$ is 1; that's because $n \bmod e = 1$ (as it's the product of two $2 \bmod 3$ primes), and $n-n' \bmod e \ne 0$ (as that difference is $2^k$, for some integer $k$)
Jul
18
comment How many bits to flip in an RSA public key to do signature forgery?
@MaartenBodewes: actually, it wouldn't set $d$ to a low value; instead, it would be detectable because the proported $n$ would be prime (alternatively, easy to factor), should anyone happen to check.
Jul
17
answered How many bits to flip in an RSA public key to do signature forgery?
Jul
11
comment RSA signatures without padding
@SEJPM: not off the top. However, this sort of 'factor a series of 256 bit integers, and look for a linear combination' is somewhat similar to what the Quadratic Field Sieve does when factoring a 512 bit number, and so there's a (very) rough starting point...