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

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


Feb
13
revised Does RSA work for any message M?
Cover what happens when p=q, and call it a day
Feb
13
revised Does RSA work for any message M?
Refer to A Method for Obtaining Digital Signatures and Public-Key Cryptosystem
Feb
13
comment RSA: What happens to restrictions of plaintext n, dependent on p and q?
I think that you want to revise your third point. With $p=q$ prime, RSA no longer works for messages that are non-zero multiples of $p$. Also, the relation between $e$ and $d$ to make these work for the other messages becomes $e\cdot d\equiv 1\pmod{(p−1)}$. And in the second point, you need $p$ and $q$ coprime and squarefree in order to avoid restrictions on message. Finally, considerations on security arising from how $p$ and $q$ are chosen are explicitly out of the question's scope, see the butlast paragraph in the question.
Feb
13
comment Prime factorization of RSA modulus
@Moses: If you insist on using both private keys, it may help that $\operatorname{lcm}(p-1,q-1)$, and perhaps also $\phi(N)$, divides $e_j\cdot d_j-1$. However in a logician's or cryptographer's view, it is fine to use just one $(e_j,d_j,N)$ to factor $N$ when two are known; and with just one, the method in the proof of fact 1 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem works.
Feb
13
comment RSA: What happens to restrictions of plaintext n, dependent on p and q?
That's my interpretation of the question. The answer is: NO, it will NOT work for quite all messages; specifically, not for those few messages such that the (padded) message is a non-zero multiple of $r>1$ such that $r^2$ divides $N$.
Feb
13
comment RSA: What happens to restrictions of plaintext n, dependent on p and q?
You note the lack of security of RSA when $p=q$. This is a valid point (in the sense of observation). But it is excluded by the question stating: "_The questions are not about argueing about the security of RSA and well choosen parameters $p$ and $q$_". The question really asks if RSA works in the sense of allowing decryption (or signature verification) for any message and choice of $p,q$.
Feb
13
comment RSA: What happens to restrictions of plaintext n, dependent on p and q?
See this answer I gave to a related question. And a more concise proof using the Chinese Remainder Theorem, there, with trivial generalization to $N$ with any number of distinct prime factors.
Feb
13
revised Does RSA work for any message M?
Expand, give theorems used with link, and add the formely implicit condition that p≠q
Feb
13
comment RSA: What happens to restrictions of plaintext n, dependent on p and q?
This is not an answer; and the (valid) point raised is excluded from the question, by the butlast paragraph (in its original version).
Feb
13
comment Signature based on public key cryptography and forgery
@Ricky Demer: You just opened my eyes to what the question really asked!!
Feb
13
revised Signature based on public key cryptography and forgery
Final polish
Feb
13
revised Signature based on public key cryptography and forgery
In fact I did answer the question. Link to a must-read comment
Feb
13
revised Signature based on public key cryptography and forgery
I now realize that my answer missed the point entirely !
Feb
13
revised Signature based on public key cryptography and forgery
Improved the definitions, and moved the case of signature with message recovery into a separate note.
Feb
13
comment “SHA-256” vs “any 256 bits of SHA-512”, which is more secure?
@Pacerier: SHA-512/224 and SHA-512/256 differ in output size (the second number, in bits), and initialization value (so that the result of SHA-512/224 is not a subset of the other).
Feb
12
comment RSA assumption and cryptography
Yes, ASCII has the benefit of universality. Last hint before the no-chat-police spots us: one can examine other's $\TeX$ (or MathML) with a right click. Or remove one's own comments if no longer useful. Or revert to earlier versions of questions and answers. Or..
Feb
12
comment RSA assumption and cryptography
Hi Brock, I've improved my English thanks to you. This site is much nicer than sci.crypt has been since well over a decade; and occasional friendly nitpicks also occur here! PS: try this TeX cheat sheet, and wrapping subexpressions into braces, like this: $m:=x\cdot r^{-1}\bmod n$ to get $m:=x\cdot r^{-1}\bmod n$
Feb
12
comment Certificate signature with SHA-1 and RSA: where do 1888 bits come from?
@owlstead: yes I am nitpicking, and my has been defined as was refering to the definition "$S$, which is also an integer between $0$ and $N$" given in the answer, which is not that in PKCS#1, which uses a bytestring in big-endian order for bytes (or, I hope equivalently, a bitstring of size multiple of 8 in big-endian order) representing an integer, as you rightly pointed out. In crypto, the devil is in the details, as the practitioner knows.
Feb
12
revised Why can't hashes be reversed with toffoli gates?
Also cover notation T(x) rather than T(x,z)
Feb
12
revised Why can't hashes be reversed with toffoli gates?
Expand and remove some conditionals since I'm now confident with the answer