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

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


2d
comment Security concern about reducing hash value using modulo operation
See this answer
Dec
24
comment power consumption in a XOR
Since a difference in energy is asked, that is proportional to a duration, which could be anything from a clock cycle (perhaps down to 10ns in some areas of the Smart Card) to months. That also depends tremendously on where in the Smart Card the XOR occurs (is that in the CPU ALU? An AES block? Some bus encryption unit?); the silicon technology; and exactly what one accounts as radiated. Also, it can happen that whatever quantity is available to the attacker depends more on change of state, than on the state itself.
Dec
22
comment On-the-fly computation of AES Round Keys for decryption?
@Craig McQueen: you are absolutely right! Fixed the answer accordingly.
Dec
20
comment Are there signatures that don't have subliminal channels?
Indeed. In addition to PKCS#1v1.5, there are ISO/IEC 9796-2 schemes 1 and 3 (with defined-in-advance parameters such as choice of hash), and the defunct ISO/IEC 9796(-1), which are RSA-based signature schemes such that a single valid signature exists for any signed message, implying there is no subliminal channel.
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
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
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
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
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)}$.
Dec
9
comment How Brittle Are LCG-Cracking Techniques?
@Charphacy: I have adapted my answer per your last comment.
Dec
9
comment Cocks IBE Scheme: why is -a a quadratic residue mod n?
Quoting Wikipedia: modulus some composite not a prime power, the product of two nonresidues may be either a residue, a nonresidue, or zero
Dec
9
comment Fermats Little Theorem, primitive root
Hint: assume $x$ is such that $2^x\equiv3\pmod p$ with $p=3\cdot2^k−1$. $\;$ What's the smallest $y$ such that $2^{x+y}\equiv1\pmod p$? $\;$ Now, assume $p$ is prime, what would be a value of $x+y$ such that $2^{x+y}\equiv1\pmod p$? That should be enough to find a value of $x$ that could do the job. Now, prove that it does.
Dec
8
comment How Brittle Are LCG-Cracking Techniques?
@Charphacy: I have an itch to try the SAT approach (no insurance). I think that I can't use the LLL, because there is too little output to carry it, at least the way that I have sketched it (did not check the references in detail).
Dec
7
comment How Brittle Are LCG-Cracking Techniques?
@Thomas M. DuBuisson: interesting; if time allows I'll try translation to SAT by more primitive means, and state-of-the-art solvers. $\;$ Side note: the @ sign before a name in a comment creates a notification; the name itself does not.
Dec
7
comment How Brittle Are LCG-Cracking Techniques?
@Thomas M. DuBuisson: My intuition is that even Case 3 could be solved using Cryptol and a SAT/SMT solver, as you did in this nice answer to a much more trivial problem. $\;$ If it indeed works, that would be a very convincing demo!