22,324 reputation
12992
bio website
location Paris, France
age
visits member for 3 years, 5 months
seen yesterday

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


Dec
12
comment 2048-bit RSA Decryption
Right. Notice that if $e=2^{16}+1$, the cost of brute force is $\approx 17\cdot M$ modular multiplications; when the answer's algorithm uses about $17\cdot4\sqrt M$ in the first phase, and $k\cdot4\sqrt M$ in the second phase, for some $k$ depending on the modular inverse algorithm, certainly $k<2\log_2(N)=4096$, which is a huge improvement, trouncing the $4\cdot10^{20}$ asked in the question. $\;$ As an aside, we can simplify things slightly by merging the two phases: we can search for $(M^e)\cdot((a^e)^{-1})\bmod N$ in the table right after entering $a^e\bmod N$ in the table.
Dec
11
revised Statistical properties of hash functions when calculating modulo
Better safe than sory or at even unsure: simplify
Dec
11
revised Statistical properties of hash functions when calculating modulo
add missing k
Dec
11
comment 2048-bit RSA Decryption
I think that "operations" should be modular multiplications. $\;$ @Thomas: perhaps the poster realized that asking the (interesting) question was infringing some honor code?
Dec
11
comment Why does the recommended key size between symmetric and assymetric encryption differ greatly?
I do not buy that "1) there are less asymmetric keys for a given number of bits (key space)" is an important reason. This effect can be estimated in RSA: there are well over $2^{2020}$ 2048-bit integers product of two 1024-bit primes, so that argument is good for less than 2% of the increase in key size. $\;$ My alternative, hand-waving, non-quantifiable explanation is that the private key is related to the public key by some direct relation; thus revealing the public key to an attacker (as we must do) would compromise the private key if we used sizes comparable to symmetric encryption.
Dec
10
comment Difference between Symmetric and Asymmetric. Is this answer correct, based on a written test?
The question would have been better with "use a key of up to 256 bits on the best case"; and "Explain the reason for the difference in key size". $\;$ One reason that the answer miss the point (as it does) could be that the reader did not catch that the question was about key (rather than data) size. On the other hand, one knowing that AES, DES, and Blowfish, have a data size of at most 128 bits should have figured out that the question was about key.
Dec
10
comment How Brittle Are LCG-Cracking Techniques?
An improved attack: because $M=2^{64}$ is a power of $2$, we can remove the leftmost $32-r$ bits of every constant and variable in the problem, say with $r\approx6$. We now know $r/(r+32)$ of the state (in Case 3: within XOR with unknown $r$-bit XOR we can enumerate), rather than $r/64$ in my previous attack; and that's an easier problem according to Contini&Shparlinski. If the running time to solve Case 2 with $r/(r+32)$ exposed bits is $f(r)$, choose $r$ that minimize $2^r f(r)$ to minimize total time to find the right XOR. Then, finding the other bits one by one is very easy.
Dec
10
awarded  Nice Answer
Dec
10
revised Statistical properties of hash functions when calculating modulo
Simplify the satement, and give only the full algorithm. The complex case is rather rare.
Dec
10
revised Statistical properties of hash functions when calculating modulo
Simplify the satement, and give only the full algorithm. The complex case is rather rare.
Dec
10
revised Statistical properties of hash functions when calculating modulo
algorithm needed a justification (but no change); polish
Dec
10
revised Statistical properties of hash functions when calculating modulo
algorithm needs a tweak
Dec
10
revised Statistical properties of hash functions when calculating modulo
Answer extension of question
Dec
10
revised Statistical properties of hash functions when calculating modulo
Polish
Dec
10
revised Statistical properties of hash functions when calculating modulo
Improve the TeX content
Dec
10
answered Statistical properties of hash functions when calculating modulo
Dec
10
comment How Brittle Are LCG-Cracking Techniques?
If with enough output your method (or that of Stern improved by Contini & Shparlinski) could solve Case 2 with only say the 4 top bits of the output, then we could enumerate the $2^4$ possible values of the XOR mask, and solve Case 3 by solving Case 2 at most 16 times.
Dec
10
revised How Brittle Are LCG-Cracking Techniques?
Simplify the formula; some duplicate SAT variables can be eliminated
Dec
10
revised Streaming API to authenticated encryption
Improve understandability of the last example
Dec
9
comment Polynomial Modulus
Hint: for a.) the first steps are: $x^{16}=x^{12}(x^4+x^3+1)+x^{15}+x^{12}$, therefore $x^{16}\equiv x^{15}+x^{12}\pmod{f(x)}$; $\;$ $x^{15}+x^{12}=x^{11}(x^4+x^3+1)+x^{14}+x^{12}+x^{11}$, therefore $x^{16}\equiv x^{14}+x^{12}+x^{11}\pmod{f(x)}$.