fgrieu
Reputation
36,265
99/100 score
 Apr 18 comment Integer factorization still hard with Hamming weight hypothesis? I believe that a similar trick also allows to reduce to a small set of possibilities the high-order bits of the primes. I vaguely tried to combine that on both ends to come up with a specialized version of Fermat factoring, but back-of-the-envelope (literally) scribblings have so far ended in: hopelessly slow, for 512-bit primes with 80-bits Hamming weight. It would definitely work if we lowered $h$ to something much smaller. And as the saying (attributed to the NSA) goes: attacks only get better; they never get worse. Apr 18 answered Integer factorization still hard with Hamming weight hypothesis? Apr 18 comment Meaning of “random n/2 bit prime length prime p” Hint: the length in bit of a positive integer $N$ (including a prime), also known as its size in bits or bit size, is the number of digits in its expression in binary with the leftmost / highest order digit non-zero. It is thus $n=\lfloor\log_2(N)\rfloor+1$, and approximately $\log_2(N)$ for large $N$. It holds that $2^{n-1}\le N<2^n$. Thus $N=3337$ has $n=12$ bits, while $107$ has $7$ bits, about half as much. Apr 18 comment State of the art low memory arbitrary-domain PRP? The problem seems to be studied, and solved, by format-preserving encryption. We have tag for that. Apr 18 comment Is the following obfuscation weak in security or not? The question could be answerable if we knew: wether the same pair $(x,z)$ is reused for several $y$; if $q$ secret or public; a definition of "too easy to break"; for certain that $(x/z)*y$ is computed modulo $q$ (and then what happens when $z$ or $x$ happens to be $q$), rather than in some other way. Apr 16 awarded Enlightened Apr 16 awarded Nice Answer Apr 15 comment Can RSA-PSS signing be made deterministic without loss of security? An issue with this method is that the verifier (not knowing $k$) can not be convinced that the signature does not convey a subliminal channel. Apr 15 comment Can RSA-PSS signing be made deterministic without loss of security? I think this paper could help towards a (not fully positive) answer: J.S. Coron, Optimal security proofs for PSS and other signature schemes, in proceedings of Eurocrypt 2002. Apr 15 comment Time taken for a brute force attack on a key size of 64-bits Hints: brute force attack is trying keys, until finding one that matches. We can try them by increasing order. Trying involves one encryption with the key tried, and then a comparison of comparably small cost, and (if there's a match, that is, rarely) some confirmation operation. If a key has $b$ bits, how many possible keys are there? What's the time to try them all at a rate of $r$ keys per second? For the average time, you can compute the average of the exact time over all possible key values, or use a well-known approximation. Apr 14 comment Can RSA-PSS signing be made deterministic without loss of security? There's a discussion about that in PKCS#1v2, end of section 8.1. I'm in for a real answer to the question, with preferably quantitative proof, and no secret involved in preparing the salt (that's cheating; and impractical, for the verifier is assumed to hold no secret, and then can't ascertain that there is no side channel in the salt). Apr 14 comment Sending KCV (key check value) with cipher text @Maarten Bodewes: Granted, one should not trust a key identifier (and my well, some level of certainty was tongue-in-cheek for: less than perfect certainty even when Murphy, famous for his law, is the only adversary). On the other hand, to support key rotation, you do need a key identifier; and then you can do without a KCV. Apr 14 awarded Popular Question Apr 14 comment Sending KCV (key check value) with cipher text Many real systems send a key identifier, which allows selection of the appropriate key with, well, some level of certainty. Apr 14 comment how to use common modulus attack? The question assumes that Alice, Bob and Chris are using raw/textbook RSA, rather than RSA with random padding or hybrid encryption, as they should; therefore, Eve can verify a guess of a message sent by Alice to Bob, e.g. tell if it is head or tail; this fails modern security definition. Independently: Chris can factor his modulus, and since that the same as Bob's, Chris can find Bob's private key (or an equivalent), and decipher messages intended to Bob only, another disaster. Apr 14 reviewed Approve Software timing attack using Kocher method Apr 14 revised Software timing attack using Kocher method Tentatively reword the question Apr 14 revised Software timing attack using Kocher method Give title of the paper Apr 14 revised Software timing attack using Kocher method removed wrong reference Apr 14 revised Software timing attack using Kocher method added 9 characters in body