20,283 reputation
12786
bio website
location Paris, France
age
visits member for 3 years, 2 months
seen 3 mins ago

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


Jan
14
comment Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?
I especially like the contrast with DualEC_DRBG: the key to that backdoor is one in the (asymmetric) cryptographic sense, not a scientific progress as the key to the hypothetical backdoor in P-XXX would be.
Jan
14
comment Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?
@catpnosis: Short of SNFS as explained in the accepted answer, I do not know any attack specific to how safe primes are generated. If safe primes are not used and the DLP in $\operatorname{GF}(p)$ matters, Pohlig-Hellman might apply; which is why safe primes are used for (non-ECC) DH and DSA.
Jan
14
comment Where does the $\varphi(n)$ part of RSA come from?
The bit "If we didn't use $\phi(n)$ the mathematics wouldn't work out" is not quite accurate. When $n=p q$ with $p$ and $q$ distinct primes, any positive multiple of $\operatorname{LCM}(p-1,q-1)$ can be used instead of $\phi(n)$ in $e d\equiv 1\bmod{\phi(n)}$.
Jan
14
comment Time complexity to solve Discrete log problem
Thanks for fixing the formula (save for the dots after 1.92). Notice that the little-oh in the exponent makes it impossible to give a big-Oh expression for the complexity. If that $o(1)$ is taken to be $0.01$, the effort is raised by $37\%$ for $1024$-bit $p$, and $52\%$ for $2048$-bit $p$.
Jan
14
comment how do you calculate the private exponent in asymmetric key encryption
Except for the value of $e$, and the use of $\varphi(n)=(p-1)\cdot(q-1)$ rather than $\mathrm{LCM}(p-1, q-1)$, this question is a duplicate of this one which has a fair answer, and others.
Jan
13
comment Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?
My question links to the one that is cited in this answer. And while this answer addresses that other question, it does not directly address my question, which is focused on the techniques than could be used to rig P-192 and friends.
Jan
13
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
I get your proof, and it solves my (now gone) interrogation of what $g$ in the generator framework maps to in the LFSR framework. The algorithm allows me to choose a random LFSR that is maximal-length with high probability, and convince someone that I did so. Many thanks! I can't refrain to note that it does not work well for generating a LFSR corresponding to a sparse polynomial, e.g. a trinomial, which has some computational advantage.
Jan
13
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
I think that we should choose the feedback polynomial with terms $x^n$ and the constant term set, else I have no proof that even the classical algorithm is correct. We could also choose it with an odd number of terms, since that's a necessary condition for maximal length. Independently: I'd like that others could run the algorithm to check that a LFSR that I propose is maximal-length; if randomizing the non-zero starting state (and perhaps making a few iterations) was demonstrably enough for low odds of letting a non-maximal LFSR creep, that would be perfect; but I'm unsure that holds.
Jan
13
comment Can you show how that RSA does/doesn't provide anonymity?
@Bush: Neither (but now that you have added to the question that the adversary is bound to submit a single message per experiment, mean and maximum are moot). I suggest that you compute a rough approximation of the odds that $(m^e\mod N_A)<(m^e\mod N_B)$ for random $m$, as a function of $N_A$ and $N_B$, the public modulus of Alice and Bob; have a mild illumination to define a strategy for the attacker; and compute the advantage obtained by applying this strategy.
Jan
12
comment Is Truecrypt's multiple/cascading encryption safe?
@catpnosis: I added material in the answer that I hope will answer some of your question.
Jan
11
comment Is Truecrypt's multiple/cascading encryption safe?
@catpnosis: I wrote "compromise of the software" as the first thing to worry about. I maintain that, and every bit in my answer, in light of the recent revelations that you point out. It is rational to be very cautious (not paranoid, by definition of that), but it is nowadays not very rational to use cascading ciphers for bulk encryption.
Jan
10
comment Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?
@D.W.: I do not need an LFSR, much less one any near (or exactly) 2991 bits (that part came as an excuse to point to a fascinating effort, that occasionaly has some applications). However I'd like moderate size LFSRs (like 320 bits) to illustrate an article on the ASG, arguably the simplest (conjectured) CSPRNG with a demonstrably long period and constant work per bit ouput. In turn I'd like a simple program testing that an LFSR is maximal-length, and for this I'd like to get rid of the requirement to have the factors of $2^n−1$.
Jan
9
comment Can you show how that RSA does/doesn't provide anonymity?
My hint is directly relevant to a working strategy for the adversary in the experiment; except number in my hint is 1 in the experiment, thus maximum and mean are the same, and we must average the outcome of a number of experiments.
Jan
9
comment Can you show how that RSA does/doesn't provide anonymity?
Hint: what are the expected maximum and mean value of the ciphertext after a number of messages?
Jan
9
comment Short length asymmetric encryption?
Signature schemes with message recovery only aim at saving bandwidth, compared to signature schemes with appendix. For example, the signature scheme of ISO/IEC 9796-2 allows to convey a 480-byte message as a 514-byte cryptogram (assuming 4096-bit RSA and SHA-256 hash), when SSA schemes of PKCS#1 would make that a 992-byte cryptogram.
Jan
9
comment Short length asymmetric encryption?
"(I) encrypt the message with a private key where the readers decrypt it with my public key" is a sin in terminology. That should be "(I) sign the message with a private key where the readers verify it with my public key". The change in terminology also comes with a change in the appropriate methodology, even though in RSA the modular exponentiation remains the same. In RSA, using only exponentiation is called textbook RSA or naked RSA, and is unsafe (often for encryption, most often for signature).
Jan
8
comment Why hash the message before signing it? Digital signature with RSA
Addition: If one hashes then apply the naked RSA signature function $x\mapsto x^d\bmod N$ without padding, one stands vulnerable to multiplicative forgeries in a chosen-message setup using an attack devised by Desmedt and Odlyzko, combining signature of messages which hashes are smooth into the signature of another such message. Even with proper padding on the signing side, implementations of signature verification have been vulnerable to incorrect verification of the padding; here's an example.
Jan
6
comment What is the difference between PKCS#5 padding and PKCS#7 padding
@user4982: the definition of PKCS#7 padding for $k$-octet block cipher as "pad the input at the trailing end with $k-(l\bmod k)$ octets all having value $k-(l\bmod k)$, where $l$ is the length of the input" is not applicable to $k=256$ (notice that for $l$ multiple of $k$, it is prescribed octets with value $256$, which is wrong). A correct extension would be "pad the input at the trailing end with $k-(l\bmod k)$ octets all having value $(k-(l\bmod k))\bmod k$, where $l$ is the length of the input".
Jan
5
comment In this example, which is a premaster secret, and which is a master secret?
Perhaps try the obvious search
Jan
5
comment In this example, which is a premaster secret, and which is a master secret?
This is Diffie-Hellman key exchange with artificially small $p$. One thing is misleading: for $p$ of practical interest, that is of some thousand(s) bits, when computing $g^a\bmod p$, one does not computes $g^a$ then reduce $\bmod p$; $g^a$ is simply too huge. Note: I do not know a standard usage of the terms master key or pre-master key in this context.