31,736 reputation
560119
bio website bolet.org/~pornin
location Quebec City, Canada
age 39
visits member for 3 years, 1 month
seen 2 days ago

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


Nov
17
answered What is the proper way to use a client nonce?
Nov
17
reviewed Approve suggested edit on white-box tag wiki excerpt
Nov
17
reviewed Approve suggested edit on white-box tag wiki
Nov
17
reviewed Approve suggested edit on resources tag wiki excerpt
Nov
17
reviewed Approve suggested edit on resources tag wiki
Nov
17
reviewed Approve suggested edit on entropy tag wiki excerpt
Nov
17
reviewed Approve suggested edit on entropy tag wiki
Nov
17
answered RSA-PSS salt size
Nov
16
reviewed Approve suggested edit on prime-numbers tag wiki
Nov
16
reviewed Approve suggested edit on
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.