Skip to main content
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 ...
poncho's user avatar
  • 149k
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 ...
Marc Ilunga's user avatar
  • 3,383
5 votes
Accepted

Cost of solving multiple Discrete Logarithm Problems in the same group

There are two main cases to address here. One is the generic "black box methods" which apply to elliptic curves. With these, the cost to solve one discrete logarithm is $O(n^{1/2+\epsilon})$,...
Daniel S's user avatar
  • 24.1k
4 votes

Modular multiplication of two k-bit numbers takes k^2 modular additions?

TL,DR: The quote is wrong. Repair it by changing $k^2$ to $k$, or by counting bit operations rather than modular additions. We can perform multiplication modulo $p$ of two $k$-bit numbers $A$ and $B$ ...
fgrieu's user avatar
  • 143k
4 votes
Accepted

Multiplicative inversion of a generated point?

But can you construct $p^{-1}G$? No, you can't if: You're assuming that you can compute the inverse modulo an arbitrary base point (rather than a fixed one) The CDH problem is hard. That's because ...
poncho's user avatar
  • 149k
4 votes

Why is discrete logarithm not quantum proof?

The problem is by definition modular, and the equation is $$g^x\equiv h \pmod p$$ for the integer case. This equation a single solution since the map $x \mapsto g^x \pmod p$ is one to one. Thus there ...
kodlu's user avatar
  • 22.9k
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 ...
poncho's user avatar
  • 149k
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 ...
poncho's user avatar
  • 149k
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$). ...
j.p.'s user avatar
  • 1,607
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 ...
fgrieu's user avatar
  • 143k
3 votes
Accepted

Example of CM field discriminant of elliptic curves

The speed up is not for all curves with small CM discriminant, but specifically for those with CM by $\sqrt{-3}$ (hence allowing us to define a cube root of unity $\beta=(1+\sqrt{-3})/2$. For a given ...
Daniel S's user avatar
  • 24.1k
3 votes

Cost of solving multiple Discrete Logarithm Problems in the same group

I think the other provides an excellent overview of the classical algorithmic side. Let me add some other perspectives. There are corresponding lower bounds in the generic group model. Namely, in the ...
Hhan's user avatar
  • 438
3 votes
Accepted

On a problem assuming Diffie-Hellman oracle

If the group is of known prime order $q$ (which is usually the setting in which DH is considered), then $g^{1/x} = g^{x^{q-2}}$, and the latter can be obtained with $O(\log q)$ calls to the DH oracle.
Mehdi Tibouchi's user avatar
3 votes
Accepted

Modular multiplication of two k-bit numbers takes k^2 modular additions?

We want to find $x$ such that $ g^x = h$, i.e. the discrete logarithm of $h$ to the base $g$ in $\mathbb F_p^*$ with $g$'s order $n$. For trial-and-error, brute-force, we can start to find $g^x$ ...
kelalaka's user avatar
  • 49.1k
3 votes

RSA like problem with unknown e and d

If I understand correctly, it's a DLP (Discrete Logarithm Problem) to find that value. I may make it somewhat easier if I try to solve the DLP for p and q respectively, but for ~500 bits, it's still a ...
poncho's user avatar
  • 149k
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$ ...
fgrieu's user avatar
  • 143k
2 votes
Accepted

Finding scalar in scalar multiplication on secp256k1 elliptic curve

There is no known feasible method to find the private key $k$ for a random public key $Q$, or equivalently for $Q$ computed from a random secret $k$ in $[0,n)$, where $n$ is the known order of ...
fgrieu's user avatar
  • 143k
2 votes
Accepted

Implementing Floor Division on secp256k1 Elliptic Curve in Python

Let, us have a public base point $G$ on the curve $E$, and let us have a public key $P$ with a related secret key $k$ with $P = [k]G$. Discrete Logarithm Finding $k$ given $G$ and $P$ and curve ...
kelalaka's user avatar
  • 49.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 ...
Mikero's user avatar
  • 13.9k
2 votes
Accepted

How long would it take to calculate discrete log modulo a number modulo prime of 78 digits?

The effort and best method to solve for $x$ the Discrete Logarithm Problem $g^x \equiv b\pmod p$ for prime $p$ depends on characteristics of $p$ beyond being a prime of a given size, and of what we ...
fgrieu's user avatar
  • 143k
2 votes

Discrete log problem - does luck exist?

Examples that use very small parameter and key sizes are mainly provided to let students understand the system. Of course they do provide the same security as expected for the algorithm. The thing is ...
Maarten Bodewes's user avatar
  • 93.4k
2 votes
Accepted

Discrete log of Goldilocks, Babybear, and Mersenne31 fields

The DLP in these small prime fields is quite easy. E.g. for $p=2^{64}-2^{32}+1$, the largest prime factor of $p-1$ is $q=65537$, thus the Pohlig–Hellman algorithm applies, and it's cost is dominated ...
fgrieu's user avatar
  • 143k
2 votes
Accepted

How to use smt solvers in order to restrict the possible key search where a portion of the private key and a portion of the public key hash is known?

search for the public key which then… That's infeasible if we hash public keys that are not chosen according to what's known of the private key. It would require about $2^{160}$ hashes to find one ...
fgrieu's user avatar
  • 143k
2 votes

Is the discrete root considered a hard problem?

After the discussion in the comments, and with the help of @kelalaka I will answer myself. I will assume that $p$, the order of the group $|G|$, is prime, and that $0 \neq x \in\mathbb{{Z}}_{p}$. $p$ ...
Amit Keinan's user avatar
2 votes

Given a random point on a curve defined over a prime field, is it possible to compute 2 different scalar that will lead to the same result?

does 2 scalars $S1$ $S2$ exist such as $packed(S1\cdot P)= packed(S2\cdot P$) $S1 = S2$ is equivalent to the statement that $S1 - S2$ is an integer multiple of the order of $P$. $S1 \ne S2$ If ...
poncho's user avatar
  • 149k
2 votes
Accepted

Given a random point on a curve defined over a prime field, is it possible to compute 2 different scalar that will lead to the same result?

Consider an Edwards curve with equation $x^2+y^2=d\,x^2y^2$ in the field $\mathbb F_p$, with prime $p\bmod 4=1$, integer $d$ with $d^{(p-1)/2}\bmod p=p-1$. The group law is $$\bigl(x_1,y_1\bigr)+\bigl(...
fgrieu's user avatar
  • 143k
2 votes

Is MOV attack against ECDLP fundamentally impossible?

Actually, the multiplicative group of the extension field $GF(p^k)$ does have order $p^k-1$. In particular, for any $m$ that does not have $p$ as a factor, there will exist a $k$ such that $GF(p^k)$ ...
poncho's user avatar
  • 149k
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. ...
Titanlord's user avatar
  • 2,327
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 ...
kodlu's user avatar
  • 22.9k
1 vote
Accepted

SDLog - looking for papers

That is the name the problem is known as. It may also be seen as forging an ECDSA signature without signing queries and having a message such that $H(m) = 1$. See Limits in the Provable Security of ...
Samuel Neves's user avatar
  • 12.7k

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