10
votes
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
5
votes
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
5
votes
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
4
votes
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
4
votes
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
4
votes
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
4
votes
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
4
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
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
2
votes
Is it possible to use Diffie-Hellman protocol for symmetric group?
In the question, a symmetric group is the set $S_n$ of permutations of $n$ things. $S_n$ has $n!$ elements. It's internal law noted $\circ$ is function composition: $w=u\circ v$ is defined by $w(i)=...
- 144k
2
votes
Is any safe prime sufficient for a secure DH key exchange?
In terms of the computational complexity of solving the discrete logarithm on classical computational resources, any safe prime of 4096-bits or greater should be safe from this attack for the ...
- 25.4k
2
votes
DH Encrypt by XOR
Some observations:
Curve25519 is only 255 bits effective. The top bit is always 0, so you leak 1 bit of secret.
Elliptic-curve point coordinate is not uniformly distributed, which means there's bias ...
- 9,672
2
votes
Accepted
Why MDDH is DDH when k in Matrix D is 1?
With overwhelming probability $1-1/p$, the element $[\![ \mathbf{a} ]\!]_s$ can be written in the form $(g,g^a)$ for some generator $g$ of $\mathbb{G}_s$ and $a$ uniform mod $p$. And then, you can ...
- 2,569
2
votes
Accepted
When was EDH key exchange introduced to SSL/TLS?
The Ephemeral Diffie-Hellman (EDH) key exchange, also known as DHE (Diffie-Hellman Ephemeral), was introduced to SSL/TLS as part of the SSL 3.0 specification (page 54), which was released in 1996. ...
- 2,492
1
vote
diffie hellman key exchange compared with ECDH
That sounds interesting and you will learn a lot! I assume you are a student.
You should start at the start: "New Directions in Cryptography" - This is a fundamental and well-written paper. ...
- 2,357
1
vote
Is shared secret and SKEYID are same in the IPSec?
First off, you are asking about IKEv1, which is an obsolete protocol - everything should be using IKEv2 instead (which does things quite differently).
However, as to how IKEv1 generates SKEYID (which ...
- 150k
1
vote
Why does it take longer to generate suitably large primes for Diffie-Hellman key exchange as opposed to for RSA encryption / decryption?
The complexity of generating a prime depends only on the size (bitlength) of the prime. So whether for DH or not this won't change and will be polynomial complexity (polynomial in $\log p$ see details ...
- 23.1k
1
vote
Accepted
A simple guide to Diffie-Hellman Key Exchange including the what, the how and the why
One of the most important requirement is missing: for security, $p$ must be large, in the thousands bits. That's a necessary (not sufficient) condition for the Discrete Logarithm Problem modulo $p$ to ...
- 144k
1
vote
App for Secure delivery of the gray images using AES, DH, DSA - Help in implemeting the system structure
Beware that "key delivery using Merkle-Hellman knapsack" has very little to do with Diffie-Hellman Key Exchange (DHKE, often abbreviated DH as in the question's title) which seems to be the ...
- 144k
Only top scored, non community-wiki answers of a minimum length are eligible