21,885 reputation
12991
bio website
location Paris, France
age
visits member for 3 years, 4 months
seen 4 hours ago

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


Dec
14
comment N way collision of hashes
The answer is fine if we are content with the statement's For a collision $H(A_1) = H(A_2)$, the number of queries is $T^{1/2}$. $\;$ But this is less than precise; rather, the number of queries to reach an $n$-collision with odds $1/2$ (or any fixed probability in range $]0,1[$ ) is $\mathcal O(T^{1-1/n})$ when $T$ goes to infinity.
Dec
14
revised N way collision of hashes
base-2 log is used
Dec
14
reviewed Approve N way collision of hashes
Dec
12
comment Probability of factoring keys as a function of bit length
This answer (as it stands at time of writing this comment) is wrong. The closest thing to a question answerable with a formula is the title of the question: (what is the) probability of factoring keys as a function of (their prime factor's) bit length ($n$, by the method in the question). After correction of $X$ into $x$, we are left with $x/\operatorname{ln}(x)$ where $x$ would be $2^n$. Problems: a) This is greater than 1, thus not a probability. b) the method succeeds if $p_a$ or $q_a$ is $p_b$ or $q_b$, thus a factor of 4 is missing somewhere. c) there's another lesser mistake.
Dec
12
comment Crack RSA with imaginary algorithm
It is not evident that the algorithm in the first comment succeeds. In fact, if we had $2^{k\cdot e}\bmod N=1$ for some $k<100$, then the algorithm would fail its goal. $\;$ The canonical answer to this question uses random numbers, rather than successive powers of two, in order to avoid that issue.
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 many bits should my random number be if I used 2048 bits to create my RSA key
@Nicolas Edwards: Sign and encrypt are not the same thing; among other differences, they are not made with the same kind of key. $\;$ In any public key encryption scheme, a message is encrypted using a public key, and decrypted using a private key. $\;$ In any public key signature scheme, a message is signed using a private key, and the signature verified using a public key. $\;$ Use of the appropriate wording is important to be understood. Proof of possession of private key can be performed in two ways: with decryption, or with signature. Mikeaso bets you mean the first, I bet on the second.
Dec
10
comment How many bits should my random number be if I used 2048 bits to create my RSA key
We can't decrypt with a public key. $\;$ Another guess at what's considered: "I want a person/computer who has the public key to generate a random bit stream and send it to the person/computer with the private key. They can sign the random bits with the private key then send the signature back to the first person who can check the signature using the public key and in that way verify that the person/computer with the private key was involved in the exchange". Is that right?
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