22,324 reputation
12992
bio website
location Paris, France
age
visits member for 3 years, 5 months
seen 2 hours ago

I'm an engineer with experience in applied cryptography, in particular in Smart Card systems.


Dec
9
comment How Brittle Are LCG-Cracking Techniques?
@Charphacy: I have adapted my answer per your last comment.
Dec
9
revised How Brittle Are LCG-Cracking Techniques?
Further align notation; take comment into account
Dec
9
comment Cocks IBE Scheme: why is -a a quadratic residue mod n?
Quoting Wikipedia: modulus some composite not a prime power, the product of two nonresidues may be either a residue, a nonresidue, or zero
Dec
9
revised How Brittle Are LCG-Cracking Techniques?
Align to other answer's notation for the multiplier
Dec
9
revised How Brittle Are LCG-Cracking Techniques?
Repair adder formula, link for that
Dec
9
revised How Brittle Are LCG-Cracking Techniques?
Leave Case 2 to others; slight simplification by searchign for i' rather than i; use M rather than n; polish.
Dec
9
comment Fermats Little Theorem, primitive root
Hint: assume $x$ is such that $2^x\equiv3\pmod p$ with $p=3\cdot2^k−1$. $\;$ What's the smallest $y$ such that $2^{x+y}\equiv1\pmod p$? $\;$ Now, assume $p$ is prime, what would be a value of $x+y$ such that $2^{x+y}\equiv1\pmod p$? That should be enough to find a value of $x$ that could do the job. Now, prove that it does.
Dec
8
comment How Brittle Are LCG-Cracking Techniques?
@Charphacy: I have an itch to try the SAT approach (no insurance). I think that I can't use the LLL, because there is too little output to carry it, at least the way that I have sketched it (did not check the references in detail).
Dec
8
revised How Brittle Are LCG-Cracking Techniques?
Link to SAT solvers
Dec
8
revised How Brittle Are LCG-Cracking Techniques?
Give references
Dec
8
revised How Brittle Are LCG-Cracking Techniques?
Some polish
Dec
8
answered How Brittle Are LCG-Cracking Techniques?
Dec
7
comment How Brittle Are LCG-Cracking Techniques?
@Thomas M. DuBuisson: interesting; if time allows I'll try translation to SAT by more primitive means, and state-of-the-art solvers. $\;$ Side note: the @ sign before a name in a comment creates a notification; the name itself does not.
Dec
7
comment How Brittle Are LCG-Cracking Techniques?
@Thomas M. DuBuisson: My intuition is that even Case 3 could be solved using Cryptol and a SAT/SMT solver, as you did in this nice answer to a much more trivial problem. $\;$ If it indeed works, that would be a very convincing demo!
Dec
7
comment Asymmetric encryptions' computational complexity
Hint: start by establishing that (for arguments of $n$ bits) the cost of the classic multiplication algorithm is $O(n^2)$ for arguments of $n$ bits; extend to $O(n^2)$ for $a\cdot b\bmod N$; then $O(n^3)$ for $x^d\bmod N$. There are faster algorithms, but they are not extremely useful in cryptography because $n$ is at most in the thousands (for RSA) or hundreds (for ECC).
Dec
6
revised DES key complementation property
improve tags
Dec
6
comment DES key complementation property
Note: By definition $\overline x$ is the bitwise complement or bitwise NOT of $x$. $\;$ Hint: assume that you can obtain the ciphertexts for two values of plaintext: an $m$ that you know [that is: you obtain $m$ and $c=\operatorname{DES}_k(m)$ ], and an $m′$ that you choose [that is: you choose $m′$ and obtain $c′=\operatorname{DES}_k(m′)$ ]. How do you choose $m′$ so that you can test (with low odds of false positive) two values of $k$ with a single DES encryption?
Dec
6
revised DES key complementation property
Fix the statement so that it makes sense
Dec
6
comment SHA1 Collisions - what about practical attacks?
@owlstead: I see no difference in principle about attacks exploiting MD5 collisions, and attacks exploiting SHA-1 collisions; feasibility is about operational details, and the cost of the search given the constraints. However MD5 is significantly more badly broken than SHA-1 is, in particular 1-block (64-byte) MD5 collisions are possible when the minimum is 2-block (128-byte) for SHA-1; and significantly constrained MD5 collisions can be built, when we do not have even a single SHA-1 collision.
Dec
6
revised SHA1 Collisions - what about practical attacks?
More references