# Tag Info

10

$g^x \cdot g^y \;\;\; = \;\;\; (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x$ of them] $\ldots \cdot g\cdot g\cdot g) \: \cdot \: (\hspace{.02 in}g\cdot g\cdot g\cdot \ldots$ [$\hspace{.03 in}y$ of them] $\ldots \cdot g\cdot g\cdot g)$ $= \;\;\; g\cdot g\cdot g\cdot \ldots$ [$\hspace{.02 in}x\hspace{-0.05 in}+\hspace{-0.05 in}y$ of them] ...

9

Diffie Hellman Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key typically used for some symmetric encryption scheme. I take the notation from the link above and this means we have a group $\mathbb{Z}_p^*$ for prime $p$ ...

9

Actually, there is no major difference between $p \equiv 23\ (\bmod\ 24)$ vs $p \equiv 11\ (\bmod\ 24)$; any minor difference boils down to "do you prefer the DH shared secret to be limited to half the possible values; or do you prefer to leak a bit of the secret exponents?". OpenSSL prefers to leak one bit; the RFC 3526 designers decided they preferred ...

7

ElGamal appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to ...

7

Rather risk vulnerabilities of third party library than implement your own. If you feel novice on this field, only implement cryptography yourself as an learning exercise. Why: Mistakes, lack of know-how and maintenance. It is very easy to make novice mistakes in custom implementation of cryptography. Even battle scarred veterans of the field do mistakes ...

7

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$. If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$). Now, we know that ...

7

A generator of a finite group is a value $g$ such that all elements of the group can be represented as $g^k$ for some integer $k$. Another key of looking at it is that if we consider the sequence $g,\ \ g \cdot g,\ \ g \cdot g \cdot g, ...$, saying $g$ is a generator means that all values in the group will appear somewhere in the sequence. Now, when it ...

7

There are actually only 5 unique $x$-coordinates one needs to be concerned about: $(0, \ldots)$ $(1, \ldots)$ $(-1, \ldots)$ $(x_1, \ldots)$ $(x_2, \ldots)$, where $$\begin{eqnarray} x_1 =& 393823572354896145817230607815530211125 \\ & 29911719440698176882885853963445705823 \end{eqnarray}$$ and $$\begin{eqnarray} x_2 =& ... 6 It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other). If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given g^b, you ... 6 For what it's worth, the OpenSSL developers have committed changes that improve this. I assume they will be in OpenSSL 1.0.2, but I don't know for sure. In any case, if you clone the git repo and compile the OpenSSL_1_0_2-stable branch (or master, I suppose), s_client will display the curve name:  OPENSSL_CONF=apps/openssl.cnf apps/openssl s_client -CApath ... 6 Yes, you are correct. The simplest way without stepping outside NaCl would be to have both create an ephemeral, random crypto_box_keypair, then exchange public keys using their long term keys. Further communication would use that new keypair for crypto_box during that session. After they are done with the session, delete those ephemeral keys from memory. ... 5 With addition and \mathbb{Z}_n, each party chooses a secret x and sends xg \pmod n over the wire, for an agreed upon generator g. Division by g modulo n is easily computable, and reveals x. In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With \mathbb{Z}_n and ... 5 You can make OpenSSL print out the handshake messages with the -msg parameter: openssl s_client -msg -connect myserver.net:443 Then look for the ServerKeyExchange message. Here is an example: <<< TLS 1.2 Handshake [length 014d], ServerKeyExchange 0c 00 01 49 03 00 17 41 04 6b d8 6e 14 1c 9b 12 4d 58 29 20 e8 e2 1a 24 0d da 8f 38 1a 5d 85 ... 5 This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ... 5 This is due to the Extended Euclidean algorithm, which allows us to compute inverses modulo any number. If the modulus is prime, things are even more easier to explain. For prime p, we know that g^{p-1} \equiv 1 \pmod{p}. Therefore, y = g^{p-2} \equiv 1/g \pmod {p}. Therefore, (xg).y \equiv x \pmod{p}, revealing the secret key. If modulus is not ... 5 The problem doesn't lie with curves in Weierstrass form necessarily, but with naive implementations of elliptic curve arithmetic on such curves. Basically, if you implement an ECC scheme (ECDH, ECDSA or whatever) on a smart card using a curve in Weierstrass form in the most straightforward way possible (by writing a simple double-and-add loop for ... 4 Given a EC public key, can a different, but plausible and functional private key be derived to match the public key? No, a public key will correspond to only one private key (with one minor exception, which I will explain below). With Elliptic Curve systems, the private key is an integer d between 1 and q (the order the generator point G), and ... 4 When using a Discrete Logarithm based scheme, such as SRP, the rule of thumb is to always use private exponents with a bit length twice the desired security strength. Hence, a 128 bit exponent a will at most give you 64 bits of security. If you want 128 bit security, you need (at least) a 256 bit exponent. This is because the algebraic structure of the ... 4 To decrypt with this system, the decryptor first computes g^{ab} (which he can do because he knows one of the two private exponents); then, he computes the modular inverse of g^{ab}; that is written as (g^{ab})^{-1}. The modular inverse is defined the same way that the regular multiplicative inverse is defined in the reals (although there it is ... 4 Even if you were doing that you would only ensure that the communication between you and "some" router is secure. It's still possible to MITM using arpspoof for instance such that in: [you] <--- A ---> [hacker] <--- B ---> [router] Communications A & B are encrypted, yet you're not talking to the real router. 4 The simplest index-calculus attack on discrete logarithms is the following. You have a generator g, a target y and a bunch of small primes \ell_1, \dots, \ell_k. The computation proceeds in three phases. First generate lots of relations of the form$$g^{r_i} = \prod_j \ell_j^{s_{ij}}. These relations give you a set of linear equations in $r_i$, ...

4

The risks are much higher that there will be mistakes in a novice (or even advanced) implementation. Look at the history of OpenSSL. It was long thought secure, until someone discovered a timing side channel attack. How would you know your code is secure against all the vulnerabilities you don't know about?

4

$\pi$ is the transcendental number 3.1415926... It's there in the formula to show this specific number was not chosen with a specific cryptographical backdoor in mind; it seems unlikely that anyone was able to select the value of $\pi$ (unless Carl Sagan was correct, of course :-)

4

What we have to show for random self reducibility is that we can reduce an efficient algorithm for solving an arbitrary (worst-case) instance to an algorithm that solves a random instance efficiently. Consequently, an efficient algorithm for the average case implies an efficient algorithm for the worst case. You already have outlined how this is ...

4

No, DHE is secure and allows to share a common secret between two parties over an insecure channel. But you cannot know, if the one you share the secret with is the one you want (DHE is vulnerable to man in the middle attacks). So DHE-RSA uses DHE to share a common secret and signs the communication with RSA to make sure, that both persons communicate with ...

4

The encryption of the signatures $\;$ keeps the identity of the initiator (Alice) confidential, even against active attackers $\;\;\;\;$ and $\;$ keeps the identity of the responder (Bob) confidential against passive eavesdroppers $\;\;\;\;$ and $\;$ provides some protection against identity misbinding attacks, $\;$ although not as much as a good protocol ...

4

What you are envisioning has basically been standardized as the integrated encryption scheme being a hybrid encryption scheme providing message authenticity (IND-CCA security).

3

You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$. So your optimization isn't possible in practice. Take a look at the alternatives at Can one generalize the Diffie-Hellman key exchange to three or more ...

3

How does Diffie-Hellman prevent a man-in-the-middle attack? Answer: Diffie-Hellman does not prevent a man-in-the-middle attack. If you're using Diffie-Hellman without any sort of authentication, then Oscar can certainly change the keys. When he does that, what's effectively happen is that Alice and Bob aren't actually negotiating keys; Alice is ...

3

The scheme itself seems pretty standard, so it should be secure, if defined and implemented correctly. A simple textual descripion as you have provided here is not enough to prove your protocol secure. The authentication part only describes the RSA algorithm and key size - it does not specify how trust is established, nor does it define how the session keys ...

Only top voted, non community-wiki answers of a minimum length are eligible