23,773 reputation
23199
bio website
location Paris, France
age
visits member for 3 years, 7 months
seen 2 hours ago

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


Mar
4
comment Is CBC theoretically harder to brute force when compared with ECB?
Hint: Bruteforce enumerates the possible keys and checks each one (by procedures different in ECB and CBC); how many keys are expected to be tested in each case? What's the hardest step in each check? $\;$ Note: I think you want to assume known plaintext (and known ciphertext, but that one is always assumed in crypto); and perhaps something about the plaintext to allow ECB to be bruteforced.
Mar
3
comment Power analysis and exponentiation by squaring
Hint: execute exp-by-squaring instrumented by printing a S each time x2 is computed (computation of either two last lines) and a M each time x * is computed (computation of last line). See how what's printed relates to n.
Mar
3
comment How to compare between two cryptographic algorithms in terms of security?
Algorithm security can't be reliably compared on the basis of their result (a value), even for multiple known (or chosen) inputs. Examining results sometime allows to conclude that an algorithm is insecure, not that it is secure
Mar
1
comment How does $g$ being a generator imply Diffie-Hellman's correctness?
Right: the choice of $g$ is immaterial to Alice and Bob obtaining the same shared key. However the choice of $g$ matters to the diversity of that key, thus its security. For example, $g=1$ would imply that the shared key is always $1$, and that's not at all secure. $g$ being a generator ensures that the shared key can take any value in $[1\dots p]$, as (somewhat tersely) explained in that other answer.
Feb
28
comment How does knowing the factorization of N can help to obtain the secret?
The CRT (and the appropriate conditions on $p$, $q$: that $p$ divides $N$, $q$ divides $N$, $\gcd(p,q)=1$) gives you that $x=a^2\bmod N$ if and only if $x=a^2\bmod p$ and $x=a^2\bmod q$. Now you need to solve these two equations, and walk back to $N$.
Feb
27
comment How does knowing the factorization of N can help to obtain the secret?
I won't deprive you from the benefit of doing your homework. $\;$ Hint: establish that if $N$ is prime, it is possible to solve $x=a^2\bmod N$ for $a$ (that's the modular square root problem). Now, assume the factorization of $N$ is available, and use the Chineese Remainder Theorem (at first, handle the case of $N$ not divisible by the square of a prime).
Feb
24
comment RSA Key composition
Montgomery arithmetic's main advantages are 1) Quotient estimation is easier 2) Estimated quotient is always right, thus not exceptional case is needed, which is great from the perspective of resisting timing attacks (but beware of other timing dependencies during the extra steps) 3) It's slightly easier to perform multiplication and reduction without a wide intermediary result than with natural arithmetic. $\;$ But it does NOT significantly lower the multiplications of elementary words, or the size of operands, compared to natural arithmetic; and does NOT pay for the public-key operation.
Feb
24
comment RSA Key composition
@haster8558: In many hardware implementations of RSA using CRT, the recombination after exponentiation is performed in software, and still does not dominate the execution time. CRT may actually significantly reduce silicon requirement for a given public modulus size, since all quantities manipulated in the time-critical part are only half as wide as in regular RSA (assuming balanced primes as in FIPS 186-4); that will be the case if there's hardware to make modular multiplication over the full modulus width. $\;$ Another design choice will be using Montgomery arithmetic, or regular one.
Feb
24
comment RSA Key composition
Right. Notice that for RSA signature verification, $e$ can be small ($3$ or $65537$) and software on a modern 32-bit CPU (rather than anything done in VHDL) is typically adequately fast. In either case you want signature padding, e.g. RSASSA-PKCS1-V1_5 or RSASSA-PSS or ISO/IEC 9796-2, which is almost exclusively done in software, except for the hashing part.
Feb
24
comment RSA Key composition
@haster8558: Right for private key in $(M,d)$ form. But if you care for speed or power, you'll want to support RSA with CRT when doing the part (use of private key) that requires large exponents; the potential savings approaches a factor of 4 with common RSA keys (the aforementioned FIPS 186-4). $\;$ If you care for security, you'll have to study if your threat model requires protection against at least fault attacks, timing attacks, power analysis and other variants of side-channel attacks.
Feb
24
comment RSA Key composition
@haster8558: No, you should not "divide the message to get more than one crypted messages", see e.g. this. Use hybrid encryption.
Feb
24
comment RSA Key composition
@Mok-Kong Shen: $2^n<M$ where $n$ is the message size in bits, and $M$ the public modulus, applies to Textbook RSA, which is insecure in many use cases, and in good practice mostly used for largely random messages. It does NOT apply to secure versions of RSA used in practice, like RSAES-PKCS1-V1_5 or RSAES-OAEP, which have a significantly smaller message capacity $n$ for a given modulus $M$. And that does not apply to hybrid encryption (as used in practice for any sizable message), where the message size $n$ is practically unconstrained.
Feb
24
comment RSA Key composition
@Haster8558: Beware, this answer is wrong in practice: in most actual use of RSA, the public exponent is small; most often $65537$, or $3$, $5$, $17$, or within some limit; I have seen such limits of $2^{32}$, $2^{64}$, $2^{128}$, $2^{256}$. In particular the later limit is enforced in FIPS 186-4, thus many HSMs.
Feb
21
comment Convert numeric message from RSA ciphertext to alphabetic
Hint: when you have an integer in range [000..999] on a computer, how do you break it into 3 integers having the value of each decimal digit? Do the same with base 26 instead of base 10. $\;$ BTW, RSA is not used in that way.
Feb
19
comment Do all stream ciphers (and AES-128-CTR in particular) produce equal output size as the input size?
Right. At the end of the day, no (rather than all) stream cipher produce output of size equal to the input size, and is secure, and allows key reuse for several messages (which is in the definition of a cipher), if one accounts for the fraction of the output devoted to IV.
Feb
18
comment Find a polynomial time algorithm for the following problem
Hint, more direct than given by Robert NACIRI: How can you efficiently find $d\in\mathbb N$, $d<p-1$, such that $e\cdot d\equiv1\pmod{p-1}$? What can you tell about $c^d\bmod p$, with the help of Fermat's little theorem? Show that the cost of each step in this algorithm is polynomial in the size of $p$ [or of the size of $\max(p,|c|,|e|)$, if the statement is not read as implying that $0\le c<p$ and $0<e<p-1$]
Feb
17
comment Equivalent key size between HMAC and AES?
Note: HMAC with an internal state of $n$ bits is vulnerable to a collision attack with $O(2^{n/2})$ queries to an oracle implementing HMAC with fixed key; this is another limit to HMAC's security.
Feb
17
comment Anonymous Gravatar Problem
Could you confirm that in the context of the question, email is a long-term, short email address (e.g. roberto@giaml.com, typo intentional); not a short-term, long email identifier aka Message-ID like 026b01d04aa6$9c2d37a0$d487a6e0$@giaml.com
Feb
17
comment What prime lengths are used for RSA?
I very much depends on what security recommendation was followed when generating the 2048-bit modulus. If that's FIPS 186-4 (a very common choice), then the factors $p$ and $q$ must each be exactly 1024-bit (further, each factor must be at least $2^{1023.5}$).
Feb
13
comment Symmetric mutual authentication with client using a derived secret
If "the client doesn't know a secret" then the server can't authenticate the client by cryptographic means. Your protocol is no exception: you assume CT is known by the client (or its token, which from a cryptographic standpoint is part of the client), and kept secret. $\;$ I fear that the security depends on what AES mode (CBC, CTR..) is used. $\;$ Also, CT = SHA(CID+Secret) is an ad-hoc (but so far unbroken) key derivation function; CT = HMAC(Secret, CID)would be more academic.