21,390 reputation
12989
bio website
location Paris, France
age
visits member for 3 years, 3 months
seen 4 hours ago

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


Nov
1
comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$
I'm truly glad that you have found and explained me another way to find $p$ given $k$, which is original, very interesting, and perhaps could be useful in some way!
Nov
1
comment Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$
Kudos for the number-theoretic method to find $p$ given $k$; I only considered solving for $p$ the second-degree equation: $k⋅p^2+p=n$, perhaps just as $p=\lfloor\sqrt{n/k}\rfloor$ followed by a check that this divides $n$. $\;$ I agree with everything except perhaps the sentence ending in security is at least questionable; I really don't know for sure!
Oct
30
comment Public key encryption without ciphertext expansion
By a counting argument, strictly non-expanding public-key encryption is bound to be deterministic, hence vulnerable to verification of a successful guess of the plaintext. So at least, it is not applicable to encryption of small or otherwise guessable fields, such as gender, or first name. For the rest, follow Ricky Demer's link.
Oct
30
comment About the Algebraic Normal Form (ANF) of S-Box in DES
KP stands for Known Plaintext(/Ciphertext pairs); the more are available to an attacker, the easier are the attacks. $\;$ XL is eXtended Linearization as discussed here. $\;$ XLS stands for eXtended Sparse Linearization. $\;$ I can't discuss these in a comment about a largely unrelated question.
Oct
29
comment What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply?
@Ruggero: I have added reference to your question, and quote that I interpret as suggesting the attack(s) do not apply to protocols doing straight ECDH; I'm seeking clarification of this.
Oct
29
comment About the Algebraic Normal Form (ANF) of S-Box in DES
If you are interested in most compact algebraic representations of DES S-boxes (which is not stated in the question, and why I made a comment rather than an answer), the best result is reportedly in the source code of john-the-ripper, I believe buried in the macros S1..S8 in john-1.8.0.tar.gz.tar file src/x86-64.S.
Oct
29
comment About the Algebraic Normal Form (ANF) of S-Box in DES
Compact representation of DES S-boxes indeed has been studied, starting (AFAIK) with Eli Biham's A fast new DES implementation in software (1997, in proceedings of the fourth FSE conference). See also Matthew Kwan's website and paper Reducing the Gate Count of Bitslice DES (2000, IACR eprint archive). I can't tell how the form in the question ranks.
Oct
28
comment Interpretation of the results of NIST (p)NRG suite
As explained in the answer, the test passed. However, be aware that this is not a good indication (much less proof) that the (p)RNG tested is cryptographically strong; nor that it is correctly implemented. These tests can (only) catch some grossly inadequate RNGs, some implementations errors (hardware or software), and (normal) imperfections in TRNGs. For an illustration of why your three p-values of 0.025, 0.027, and 0.029 are not alarming, there's an obligatory XKCD.
Oct
27
comment RSA CRT modulo reduction
What you wrote in comment is true, but does not satisfactorily answer your question. Fermat's Little Theorem goes a long way towards that; use it to prove that $\forall x\not\equiv0\pmod p, x^d\equiv x^{d_p}\pmod p$. $\;$ Also, notice that you do not HAVE to compute $d_p$ and $d_q$ the way you do; $d_p=d_q=d$ will also work, albeit with much less savings compared to regular modular exponentiation.
Oct
27
comment How to encrypt letters less than block n using Hill Cipher
In the Hill Cipher, the number of components in the vector (that you note $n$) is not usually the same as the modulus you set at $26$. $n=3$ is typical, and makes the padding issue less relevant. Notice that the cipher is slightly less vulnerable if the modulus is prime.
Oct
27
comment How to encrypt letters less than block n using Hill Cipher
Yes. If the implementation is manual, we can pad with haphazard (non-constant) characters chosen such that a human will understand they are not part of the real plaintext. E.g. ATTACKATDAWNWVK. If a computer is used, why use the Hill Cipher when we have incomparably safer options?
Oct
25
comment Use case of RSA CRT
More reasons, especially in Smart Cards: $\;$ a) It is slightly involved to derive the CRT key $(p,q,dp,dp,qInv)$ from $(n,d)$, which may be the specified form for key injection. $\;$ b) If all we know is that the key is per PKCS#1 and $N$ is $k$-bit, $p$ might still be much more than $k/2$ bits, so perhaps for some keys it does not fit the available hardware well and CRT gives no time savings. $\;$ c) As mentioned in answer, the CRT form of the key requires more space, about +75% more since $(N,e)$ needs to be available in order to check the result as a countermeasure against fault attacks.
Oct
24
comment Operation which needs much computing power to be created, but just a little to be solved?
@stereo_: What's "a crypto CTF" in your comment about the use case? $\;$ Does a Proof-of-Work system combined to adding the plaintext in clear to the problem fits your needs? If not, why? Note: answer that my clarifying your question (hopefully, you can use the edit button).
Oct
23
comment Small Prime Difference in RSA
@mikeaso: Your technique makes $(p-q)/2$ guesses. $\;$ I initially thought it was equivalent to the Fermat factorization method (see Wikipedia or MathWorld), but the later makes about $(p-q)^2\over8\sqrt n$ guesses, which can be MUCH less. With $n=2189284635403183$ (such that $p-q=18)$, your technique makes $9$ guesses, Fermat's only $1$. With the similarly sized $n=2189283205227561$ (such that $p-q=40040)$, your technique makes $20020$ guesses, Fermat's only $5$.
Oct
22
comment I need to know number of encryption/decryption operations?
Hint, assuming 4DES with independent keys: minimally adapt a simple technique that works with 3DES, leaving the part dealing with the first two rounds unchanged. $\;$ For the best theoretical complexity of breaking 3DES with independent keys, see Stefan Lucks: Attacking Triple Encryption in proceedings of FSE 1998, which has it less than $2^{112}$ DES operations. $\;$ Notice that strictly speaking, $O(2^{112})$ is the same as $O(1)$, and thus best avoided.
Oct
22
comment What is the use of Mersenne Primes in cryptography
Addtion: If $2^n-1$ is prime, it becomes easier to ascertain that the feedback of a LFSR of order $n$ makes it maximum-length: it is then enough to show that the LFSR loops after $2^n-1$ steps, which is easy (otherwise, we would also need to show that it does not loops after $2^n-1\over p$ steps for each prime divisor $p$ of $2^n-1$). $\;$ That observation is not so useful, though: LFSR by themselves are poor keystream generators (we need to combine them, see the ASG).
Oct
22
comment Small Prime Difference in RSA
@ddddavidee: as far as I can tell, the only difference is that your $l$ is mikeazo's $\frac{p-q}2$
Oct
21
comment Small Prime Difference in RSA
It is correct that "The difference between $p$ and $q$ should not be small"; however, under the assumption that $p$ and $q$ are randomly seeded and appropriately large for cryptographic use, odds are entirely negligible that the difference between $p$ and $q$ is dangerously small. So much that the (often mandated) check that$|p-q|$ is above some limit really is useful only as an additional check that said assumptions hold, and to reassure those who do not trust math.
Oct
21
comment To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
@user153465: indeed, to answer Question 1 by the affirmative, we need to replace arbitrary value in $Z_n$ with random in $Z_n$ (as Poncho did), or chosen in $Z^*_n$ without knowledge of the factorization of $n$ (as I did). $\;$ Question 2 as currently worded is not answerable by yes or no until both this and secure are better defined.
Oct
21
comment To prove $r_2$ is a uniformly at random value in $Z_n$, where $r_2=r_1 . m$
Rephrased without a question mark: $\;$ Show that if $m$ has a multiplicative inverse in $Z^*_n$, then $f: r_1\to f(r_1)=r_2=r_1\cdot m\bmod n$ is an injection from $Z^*_n$ to itself. $\;$ Show that if an $m$ chosen in $Z^*_n$ without knowledge allowing the factorization of $n$ had sizable odds of having no multiplicative inverse, it would be easy to factor $n$. $\;$ Conclude about what we can safely assume about $f$ (noticing $Z^*_n$ is a finite set); then about what that implies for $r_2$ if $r_1$ is uniformly random.