16,783 reputation
12266
bio website
location Paris, France
age
visits member for 2 years, 8 months
seen 9 hours ago

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


Nov
8
revised Randomized algorithms and the one time pad
Major rework
Nov
8
revised Randomized algorithms and the one time pad
incorporate first comment, thanks Bob
Nov
8
answered Randomized algorithms and the one time pad
Nov
7
reviewed Reviewed Finding partial pre-image of MD5 hash
Nov
7
comment CPA Secure Chosen plaintext scheme
I second that when $E$ is a block cipher with equal key and input size, $x\mapsto E_k(x)$ is a member of a family of PRF (and PRP) indexed by $k$, and the first scheme in the question meets IND_CPA; while $x\mapsto E_x(k)$ is not a PRF (or PRP), and it is possible to show that the second scheme does not meet IND-CPA, by exhibiting a concrete strategy winning the corresponding game.
Nov
6
comment Carmichael number factoring
I think that you have the right sketch: find a witness to the Miller-Rabbin test; since that's a liar to the Fermat test, you can efficiently exhibit a non-trivial factor of $N$ as $\gcd(x-1,N)$ or $\gcd(x+1,N)$, where $x$ is the butlast result in the Miller-Rabbin test. I see no reason why odds of success would not be $\ge3/4$ for each random base tested.
Nov
6
revised Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
Reorder formulas for readability, and other polish
Nov
6
awarded  Self-Learner
Nov
5
revised Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
Polish and fix
Nov
5
comment Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
I put the above argument in writing. It hints we can have $f<2^ {b/2-2⋅k}$ if (but not only if) we trust that RSA remains safe with $\left|p-q\right|<2^{b/2-k}$.
Nov
5
comment RSA and prime difference
The recommendation $\left| p - q \right|>2^{k/2-100}$ appeared in ANSI X9.31, sponsored by a banker's association, and remains in FIPS 186-3 from that origin. I think the objective was to justify that due diligences have been made in the selection process of the RSA key to protect against well known factorization algorithms, allowing to summarily reject rhetorical arguments on the line of: this signature thing is a joke, an algorithm known since the 17th century could allow a forgery. It's only technical use, if any, is to protect against a fault in the process that generated $p$ and $q$.
Nov
4
revised Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
More adventurous choice of $k$ in the new method.
Nov
4
revised Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
added 187 characters in body
Nov
4
answered Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
Nov
4
awarded  Enlightened
Nov
3
awarded  Nice Answer
Nov
2
comment Why does HOTP use such a complex truncate function?
Looks like over-engineering to me.
Nov
2
comment Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
Very interesting reasoning and pertinent linked papers. BTW I spotted a mistake in the intro of More on Correcting Errors in RSA Private Keys: Breaking CRT-RSA with Low Weight Decryption Exponents, it states that in RSA $e⋅d>\phi(n)=(p-1)⋅(q-1)$, which should be $e⋅d>\lambda(n)=\mathtt{LCM}(p-1,q-1)$.
Oct
31
comment Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
I think I have a hand-waving entropy-based security argument that the system as shown is safe, because the customary choice of $p$ and $q$ at step 2 and knowledge of $n$ gives almost as much information about $(p-1)·(q-1)$ to an adversary as does knowledge of $e$ and the range of $f$. But I so far fail to formalize that, and much less to determine if we can reduce the range for $f$ and still have some juice in this security argument.
Oct
31
revised Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?
Expand title. Polish & freeze.