fgrieu

10,004 reputation

1237

bio	website
	location	Paris, France
	age
visits	member for	1 year, 9 months
	seen	8 mins ago
stats	profile views	93

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

	10,004 reputation	bio	website		visits	member for	1 year, 9 months
1237 badges		location	Paris, France		seen	8 mins ago

summary answers questions tags badges favorites bounties reputation activity

609 Comments

suggestions reviews revisions comments badges posts accepts all

Feb 4	comment	Why RSA encryption key is based on modulo(phi(n)) rather than modulo n @user5507: $e\cdot d \equiv 1 \pmod {\phi(n)}$ is a sufficient, but not necessary condition for $(n,e,d)$ being a working RSA key. In my counterexample above, it happens not to hold. When $n$ is the product of distinct odd primes $(p,q)$, the necessary and sufficient condition for $(n,e,d)$ being a working RSA key is $e\cdot d\equiv 1 \pmod {LCM(p-1,q-1)}$, and in my counterexample this congruence $\pmod {20}$ holds.
Feb 4	comment	What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures @hsikcah: The hardware device is supposed to apply the public key function to the signature $S$, yielding $T=S^e\bmod n$; then accepts or rejects the signature and data depending on if both (A) the hash of the data matches the appropriate 160 bits of $T$, and (B) all the other bits of $T$ are what they are supposed to be. (A) detects an alteration of data without a signature change, (B) prevents some attacks. Poor implementation of (B) is not unknown.
Feb 4	comment	What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures @poncho: Do you mean undoable ? A second-preimage attack for SHA-1 is far out of the state of the art. And as of factoring a 1024-bit RSA modulus, in this century, the largest RSA modulus publicly factored has been at most (y-2000)*32+512 bit, and I think this will hold until 2015.
Feb 3	comment	What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures @hsikcah: Also, no matter how bad the padding scheme and how many signatures an adversary gets, the private key never leaks for that reason (that's a virtue of the odd exponent in RSA). What can happen is that an adversary could forge signatures of some messages, using the signatures of other messages.
Feb 3	comment	What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures @hsikcah: to answer your question about "padding the cryptographic hash with 0xff" with certainty, some details are missing on what happens on the very left. If the padding produces a value less than n (implying that the leftmost bit is forced to 0, not 1), likely your are safe. Same if the adversary can not realistically obtain the signature of many messages of chosen content.
Feb 3	comment	What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures @hsikcah: introducing randomness is necessary for data encryption (before applying the public key operation), but is optional for signature production (before applying the private key operation). PKCS#1-v1.5 signs without randomness, and there is no known attack. ISO/IEC 9796-2 scheme 3 also signs without randomness, and even has a strong security proof.
Feb 3	comment	Why RSA encryption key is based on modulo(phi(n)) rather than modulo n It took the liberty to reverse the implication in the first statement. In the other direction, it was incorrect; check with $n=55$, $e=3$, $d=7$ which forms a valid RSA key, yet with $e\cdot d\not \equiv 1 \pmod {\phi(n)}$.
Feb 1	comment	Why RSA encryption key is based on modulo(phi(n)) rather than modulo n The intuition that computing in the ring $Z_n$ implies exponents can be considered in that ring is misguided. $Z_{\varphi(n)}$ is a more appropriate ring for exponents. $Z_{\lambda(n)}$ with $\lambda(n)=LCM(p-1,q-1)$ also works, and is what PKCS#1 uses.
Jan 31	comment	How do I correctly derive a Key and IV? In the context, collision of 64-bit salt it is not much of a problem: an attacker trying to find the password by brute force has a moderate advantage (by a factor of 2) for these these few humans which share the same salt. The simplest fix is a bigger salt, which is possible: according to Rfc2898DeriveBytes doc The salt size must be 8 bytes or larger.
Jan 31	comment	How do I correctly derive a Key and IV? Nitpick: if one picks a 64-bit salt at random for each human being, odds are high that two get the same salt.
Jan 30	comment	Proving knowledge of a preimage of a hash without disclosing it? I guess the above is intended to read "but not necessarily other hash functions", and otherwise is supportive that a practical protocol can be devised in the case of SHA-1 as claimed in the talk. I'm still a tad skeptical, on these (admittedly weak) arguments: 1) such a protocol is something we can't devise in general for a perfect hash, yet we are computationally unable to distinguish SHA-1 (with fixed message size) from a perfect hash, other than by the fact that it is SHA-1; 2) details on the talk's method are scarce; 3) this remarkable result does not appear to have been reproduced.
Jan 30	comment	Proving knowledge of a preimage of a hash without disclosing it? Do you feel confident that the answer to the question is a clear "yes, using the techniques in the Cramer-Damgård paper"? Or something weaker? I get that there is no evidence of impossibility.
Jan 30	comment	Proving knowledge of a preimage of a hash without disclosing it? @PulpSpy: now I see the error in my earlier argument for a straight "no" answer. Still I find "yes" counterintuitive. I maintain it is impossible for a random oracle, or a concrete hash of unknown design. Even if we peel the hash into its known layers, can we commit the result of combining committed values using functions from unrelated groups, recursively for so many layers, and still have something practical, as claimed in the talk?
Jan 29	comment	Proving knowledge of a preimage of a hash without disclosing it? My current intuition is that no practical protocol can rightly convince Bob of Alice's claim, for that very protocol would be able to distinguish $H$ from a random oracle, something that was never done for SHA-1 (restricted to messages of constant length). I reason that in the random oracle model, the only way for Bob to be convinced that the oracle outputs $h$ for message $m$ is to submit it himself, which implies knowledge of $m$.
Jan 27	comment	Can nesting different ciphers with different keys ever decrease security? It is easy to construct two iterated ciphers with no obvious defect, but such that the composite cipher obtained by interleaving the rounds is very unsafe, e.g. always leave some (or even all but 1 bit) of the input unchanged. An example is a symmetric Feistel cipher, and a variant with left and right inverted.
Jan 26	comment	Provable Encryption Can you elaborate on exactly what the proof is about? One way to state that would be to list what behavior(s) of Alice should be caught. Does this include submitting something random as the ciphertext? Ciphertext for which there exist plaintext, but it is random nonsense? Ciphertext for which there exist plaintext, but it is not known to Alice?
Jan 25	comment	Stretching a random seed to maximize entropy What's a "cavity-compression attack"?
Jan 24	comment	Why does the PKCS1 RSA private key structure contain more than just exponent and modulus? The text "only the modulus and public exponent is required for encryption" is correct, but has nothing to do with the rest of the question: the party doing encryption does not use or know the RSAPrivateKey.
Jan 23	comment	How much can we compress RSA public keys? @ByteCoin: Yes these reference support the idea that asymmetric RSA can be safely used. BTW, when we compare these 2000 estimates of the cost of GNFS factoring to modern results, we see that the former estimates where 80.000 times too high (and that after fixing another factor of $10^{10}$ in the formula given on page 11 in order to reconcile with the graphs).
Jan 20	comment	How much can we compress RSA public keys? I fail to follow "If there were a better method which did not run very slowly then it could be re-purposed as a factoring algorithm", and think it is disproved by the much improved bound in the reference now in the updated question. The best I can get is that if we can reach $k$ bits with a generation cost $X$, then we have a factoring algorithm of cost $X \cdot 2^k$.