32,416 reputation
562124
bio website bolet.org/~pornin
location Quebec City, Canada
age 39
visits member for 3 years, 3 months
seen 2 hours ago

Cryptographer, programmer in several languages (C, Java, several assemblies, Pascal, Forth...). I also have a life.


Nov
16
reviewed Approve suggested edit on elgamal-encryption tag wiki
Nov
16
reviewed Approve suggested edit on cbc tag wiki
Nov
16
comment Mapping between subgroups and the integers
@sophie: when working modulo a prime $p$ which is equal to 3 modulo 4, $-1$ is not a square (there is no $z$ such that $z^2 = p-1 \mod p$). This implies that if $x$ is a (non-zero) square (there is a $y \neq 0$ such that $y^2 = x \mod p$) then $-x \mod p$ cannot be a square; and it also works in the other direction (if $x$ is not a square than $-x$ is a square). This can be linked to Fermat's theorem (not the famous one): $x^{p-1} = 1 \mod p$; hence $x^{(p-1)/2} = ±1 \mod p$. This implies that $y = x^{(p+1)/4} \mod p$ is a square root of either $x$ or $-x$ (try it !).
Nov
15
answered Random Coin Flip using ElGamal and a Trusted Party
Nov
15
awarded  Nice Answer
Nov
15
answered Why is elliptic curve cryptography not widely used, compared to RSA?
Nov
14
comment Is H(k||length||x) a secure MAC construction?
For the length encoding, one can use 7-bit encoding: you represent the length in base 128. Then each "digit" is encoded as a byte, setting the most significant bit for all bytes except the last. This is what is used to encode OID elements in ASN.1/DER; it has no inherent limit. Of course, realistically, encoding over a fixed-length 128-bit field is sufficient and much simpler.
Nov
14
comment Are there practical upper limits of RSA key lengths?
@Paŭlo: for a 500k-bit prime, you can arrange for generation of candidates which are not multiple of 2, 3, 5, 7, 11... up to, say, 23. This can divide the number of calls to Miller-Rabin by 3 or 4, hence my estimate of 100000 tests (200000 in total, for $p$ and $q$). Miller-Rabin rules out a non-prime with probability at least $3/4$, so the average number of invocations is bounded by $4/3$ (actually much closer to 1, because the $3/4$ probability is a worst case).
Nov
14
comment Are there practical upper limits of RSA key lengths?
@jug: Karatsuba, Schönage-Strassen and their ilk, are for multiplication of plain integers; for RSA, we need modular multiplications. Even if we optimize the "multiplication" part with a sub-quadratic algorithm, the modular reduction is still quadratic. I am not aware of any modular exponentiation algorithm which goes below $O((\log n)^3)$ complexity. Edit: it seems such algorithms actually exist, see this presentation.
Nov
14
comment Are there practical upper limits of RSA key lengths?
@Paŭlo: it is $(\log n)^2$ operations for a modular multiplication, and there are $\log n$ of them in an exponentiation, so $(\log n)^3$. I do not know where your exponent $4$ comes from. For primality testing, a basic Miller-Rabin test is $O((\log p)^3)$ and you will need to do about 200000 of these (on average), if you select candidates for $p$ and $q$ with some care; so that's roughly the cost of 25000 private key operations. But at least key pair generation can be distributed over several cores / nodes.
Nov
14
answered Are there practical upper limits of RSA key lengths?
Nov
13
revised Linear Cryptanalysis
rewrote text to phrase it as an actual question
Nov
13
comment Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
@Ricky: if we knew how to handcraft data blocks specifically to trigger a SHA-256 collision, with better success than with random blocks, then this would be advertised as a break on SHA-256. No such break is currently known on SHA-256. Current methods for attacking MD5 and SHA-1 appear unlikely to apply to SHA-256 (this has been tried).
Nov
12
comment What is pre-image resistance, and how can the lack thereof be exploited?
Preimage resistance is needed for time stamping RFC 3161, an combining time stamping with hash trees (as in ERS) opens the possibility of "multi-target preimage attacks" in which you want to find one preimage for any hash value among a rather large set of hash values, which is somewhat easier (down to $O(\sqrt{N})$ for a hash value set of size $O(\sqrt{N})$).
Nov
12
comment What is pre-image resistance, and how can the lack thereof be exploited?
There are no known preimage (or second preimage) attacks on MD5 or SHA-1. There is a theoretical preimage attack on MD4(complexity of $2^{102}$) and also an attack on MD2($2^{73}$).
Nov
11
comment Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
@poncho: $2^{-60}$ per day. So $2^{-120}$ is the probability of encountering two gorillas the same day. You can view it with a time frame: on average, you will meet a gorilla every $2^{60}$ days. You will get a SHA-256 collision every $2^{76}$ days (there was a mistake in my estimate, so 65000 gorillas, not 250000)(assuming you regenerate the $2^{90}$ 1MB blocks every day). So you really get $2^{16}$ gorillas for every collision -- but not in one go, as a massive gorilla army attack ! (that would be spooky)
Nov
11
revised Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
fixed probability of collision (2^{-76}, not 2^{-78})
Nov
11
answered Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?
Nov
11
answered Linear Cryptanalysis
Nov
10
comment Is it reasonable to assure that p-1 and q-1 aren't smooth?
@fgrieu: to be precise, testing a given $p-1$ (from a random prime $p$) for smoothness is expensive, while _generating a $p$_ specifically for $p-1$ to be non-smooth is relatively easy.