21,915 reputation
12991
bio website
location Paris, France
age
visits member for 3 years, 4 months
seen 10 hours ago

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


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
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
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
comment SHA1 Collisions - what about practical attacks?
@crypto-learner: I now give a lot more details, especially for the second example.
Dec
5
comment Will X9.31 remain a secure & acceptable deterministic random generator beyond 2015?
@Gilles: yes, in some uses the lack of backtracking resistance can be an issue. I semi-consciously worded the hypothesis of my endorsement so that it excludes this concern, but in retrospect should have mentioned it. You did, very well.
Dec
3
comment practical use of homomorphic encryption
Mental poker (in the setup where $n$ is composite) arguably uses the homomorphic properties of RSA.
Dec
3
comment Existential Forgery on textbook RSA signatures
You can be made right, if you properly define $m' = m_1/m_2$ and $σ' = σ_1/σ_2$, and handle the possible case of these quantities being undefined; by showing that it is extremely unlikely; or/and showing that should it occur nevertheless, the adversary can trivially forge any signature. $\;$ Hint: you need to amend $σ' = σ_1\cdot σ_2$ in a similar way, if you use (as you seem to do) that the definition of a valid signature $σ$ of message $m$ is that $σ=m^d\bmod N$, or the more usual and equivalent definition that $0\le σ<N$ and $σ^e\equiv m\pmod N$.
Dec
2
comment Find generator for irreducible polynomial over binary field
The lazy man's way to pick up a small polynomial with this or that characteristic is to lookup the appropriate list in Joerg Arndt's useful and ugly page of mathematical data. For example, your irreducible polynomial $x^4+x+1$ is the line reading 4,1,0 in the Complete list of binary irreducible polynomials up to degree 11.
Dec
2
comment Reversing a Psuedo Crytographic Hash
I added this in hope that it could help simplify the answer. In particular, msg[i+1] is (digest[i+1] XOR msg[i])*19 MOD 256 or something on that tune. I do realize that it makes use of an SMT solver less useful.
Dec
2
comment Reversing a Psuedo Crytographic Hash
It helps to notice that when working on bytes, multiplication by 129 is always exactly undone by a further multiplication by 19, because $19\cdot129\equiv1\pmod{256}$
Dec
1
comment Implementing a pseudo random function in practice
@sashank: AES-128 with a fixed key is a PRP over $\{0,1\}^{128}$; as such, we can expect to distinguish it from a PRF with about $2^{64}$ encryptions, and that's not a "good PRF".
Nov
30
comment Generation of strong primes
FIPS 186-4, appendix B.3 contains one of several possible definitions of strong prime, and methods to generate these.
Nov
30
comment RSA Cryptosytsem, choosing $e$
That's covered here.
Nov
30
comment transforming RC2 keys to have effective minimum length in implementations with fixed effective lengths
Have you determined the values of T and T1 (in the sense of rfc2268 section 2) used in the implementation that you want, and in the OpenSSL implementation that you start from? My reading is that the "effective key length" T1 in rfc2268 can be any multiple of 8 from 128 to 1024 for an implementation accepting both T=5 and T=16 bytes of key.
Nov
30
comment Factoring a number who has factors with same number of digits
Here is a fine description of MPQS. GMP-ECM is one of your best bet for a ready-made tool.
Nov
30
comment Factoring a number who has factors with same number of digits
Being the product of two primes with the same number of digits is NOT by itself a good indication of being factorisable by Fermat's factoring. Rather, try QS and friends, or ECM.
Nov
30
comment Cracking RSA with Small exponent 5
I guess that what the TA means is to include the final quote in the unknown. So the plaintext is $m=2^{8k}a+b$ where $b$ is the unknown password (including quotes, at least final, if any), $k\approx9$ is the number of bytes in $b$, and $a$ is the known prefix (I'd say, with the final quote, but we can remove it and increase $k$ by 1). $\;$ Again, read section 4 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem or some other source on Coppersmith's method; then tell us what you are stuck with.
Nov
29
comment Cracking RSA with Small exponent 5
@codeomnitrix: If there is no quotes before and after password, then why is it that the "Known message bits" are precisely the ASCII encoding of Anonymous: This door has RSA encryption with exponent 5 and the password is: ', INCLUDING a final ' ?
Nov
28
comment Collision in Merkle–Damgård without a collision in compression function
Welcome to crypto.SE! $\;$ Is your claim that SHA-1 without insertion of the extra 1 bit is breakable? Are you exhibiting an explicit collision? If yes, what are the two colliding messages? $\;$ I'm trying to follow you, but fail. If guess you mean $f:\{0,1\}^{128+512+1}\to\{0,1\}^{128}$ (written $f:\{0,1\}^{128+512+1}\to\{0,1\}^{128}$ on this nice website, which handles a subset of $\TeX$), but then I'm getting lost; what's $y$, why does the binary representation of 24 matters (I get that $24=512-488$ but fail to see the significance), what is $z$, what is "z1=f 0^129||y1 z1" meaning?
Nov
28
comment Cracking RSA with Small exponent 5
My reading of the amended statement is that the plaintext is of the form: $m=2^{8(k+1)}a+2^{8}b+c$ with $a=$1779358514627318781383126548094807672538311874318159242622686075224638123273‌​733409785484042478408686091630450639923610751161891182321936751949320492657334925‌​6096527256865557690760788844583 the integer matching ASCII Anonymous: This door has RSA encryption with exponent 5 and the password is: ', $b$ the integer matching the ASCII password, $c=$39 matching ASCII ', and $k$ the number of characters in the password. $\;$ Can this be confirmed?