# Tag Info

Accepted

### Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?

The question specifically states that generating arbitrarily large primes for DH typically takes much longer than for RSA, and I am to verify this claim. Well, yes. In the simplest terms, to ...
• 150k

### On a diffie hellman related oracle

If the oracle is restricted to working with $g$ as the base, then the reduction is possible by considering the following equality: $$\frac{1}{x-1} - \frac{1}{x} = \frac{1}{x^2 - x}.$$ Inversions in ...
• 3,403
Accepted

### Separation between CDH and DDH

This is a very good question -- but we don't know! The trouble is that if a primitive $X$ exists (i.e. admits any realization in the real world), then CDH logically implies $X$ (the construction is ...
• 20.8k
Accepted

### How does the Legendre symbol reveal if $g^a$ is odd or even for Finite Field Diffie-Hellman

Since $g$ is generator then it is not square, otherwise cannot generate the group (See the bottom theorem). Therefore, as being a $\text{QNR}$, it's Legendre symbol is $−1$; \left(\frac{g}{p}\right) ...
• 49.3k

### Is this self algorithm made private key for Diffie-Hellman key exchange secure

Is this algorithm secure ? No, it is not. As kelalaka pointed out, the $a$ values you get are always less than 111 bits long; we know private exponents that small can be recovered. However, it's ...
• 150k
Accepted

### On a diffie hellman related oracle

Well, if the Oracle works with an arbitrary base 'g', then it is easy. If we give the Oracle the base $g^x$, and ask it to 'invert' $g$ with respect to that base, that is: The base is $h = g^x$ The ...
• 150k
Accepted

### How do I find the order of the subgroup in a Diffie-Hellman key exchange?

But I can't find what the value of q should be. For that group, the size of the subgroup is $q = (p-1)/2$. However, I do have these comments: That's a MODP group ...
• 150k

### Why using q = (p - 1)/2 for discrete log Diffie-Hellman scalar operations and not p?

Why Diffie-Hellman uses $\bmod q$ for scalar operations, where $q=(p-1)/2$ and for elements' operation it uses $\bmod p$ Other than the fact that DH doesn't actually do operations on scalars (it ...
• 150k

### How do I solve a discrete log using pen paper for exam without bruteforcing it?

You could try Baby-Step Giant-Step: First calculate $10^b$ for $b=0\dots 4$: $1, 10, 10\cdot 10 = 5, 10\cdot 5 = 12, 10\cdot 12 = 6$, and store them in a table manner ($\alpha_i = 10^i \bmod 19$). ...
• 1,647

### Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?

generating arbitrarily large primes for DH typically takes much longer than for RSA Yes. That's for several reasons For comparable security, the prime $p$ in DH needs to have about as many bits as ...
• 144k

### Are Safe and Sophie Germain primes evenly distributed?

Recall that $p$ is a safe prime and $q$ is a Sophie Germain prime when $p=2q+1$ and both $p$ and $q$ are prime. Safe and Sophie Germain primes are sometime useful in cryptography, e.g. in variations ...
• 144k
Accepted

### DHKE: Why using safe prime gives us "safe" subgroups?

An element $x$ has order 1 or 2 if and only if it satisfies the equation $x^2=1$. In a field (which $\mathbb{Z}/p\mathbb{Z}$ is when $p$ is prime), an equation of degree $d$ has at most $d$ solutions; ...
• 2,569
Accepted

### Why using q = (p - 1)/2 for discrete log Diffie-Hellman scalar operations and not p?

Diffie-Hellman in the multiplicative group modulo $p$ performs all operations modulo $p$: Alice chooses random secret $u$, sends $U=g^u\bmod p$ Bob chooses random secret $v$, sends $V=g^v\bmod p$ ...
• 144k
Accepted

### How to combine the keys in the Triple Diffie-Hellman (3DH) key exchange?

Rephrasing your question in multiplicative notation: Long term keys are $g^a$ and $g^b$. Ephemeral key exchange is $g^x$ and $g^y$. Compute the session key as either: version 1: $H(g^{ay}, g^{xb})$, ...
• 14.1k
Accepted

### How often do Double ratchet in Signal protocol update DH ratchet key

What does impede Signal protocol from updating DH ratchet for every message? The main obstacles are rooted in the striking of a balance between efficiency & efficacy. That balance is heavily ...
• 1,116

### Are Safe and Sophie Germain primes evenly distributed?

So, as far as I can surmise, the existence of infinitely many Sophie Germain primes is still open. There is a preprint on vixra, see here [vixra is a kind of a free for all arxiv server] but it has ...
• 23.1k

### One group element hybrid encryption for El Gamal

Are you comfortable with the connection between ElGamal encryption and the Diffie-Hellman Key Agreement (DHKA)? ElGamal is just DHKA + OTP, just "repackaged" in a different way: The ElGamal ...
• 14.1k

### Use of CertificateVerify in TLS_DH_RSA with client authentication?

Even for <=1.2, the authentication method specified by the ciphersuite fully controls only the server cert&key. If the server uses any cert (i.e. keyexchange is not anonymous or PSK or Kerberos)...
• 6,424

### Signed vs unsigned prekeys

Which keys are to be stored? Which keys are sent to the party that tries to initiate a conversation? It depends on the entity under consideration (initiator, responder or server), but I assume this ...
• 3,403

### TLS 1.3 digital certificates and ephemeral Diffie Hellman

The asymmetric keys are not used for anything else ? It is also used to verify that the initial negotiation was not tampered with; for example, a Man-in-the-Middle did not replace the server's DH key ...
• 150k