# 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 ...
• 149k

### 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,383
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})$,...
• 24.1k

### 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$ ...
• 143k
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 ...
• 149k

### 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 ...
• 22.9k
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 ...
• 149k

### 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 ...
• 149k

### 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,607

### 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 ...
• 143k
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 ...
• 24.1k

### 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 ...
• 438
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.
• 2,276
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$ ...
• 49.1k

### 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 ...
• 149k
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$ ...
• 143k
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 ...
• 143k
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 ...
• 49.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 ...
• 13.9k
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 ...
• 143k

### 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 ...
• 93.4k
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 ...
• 143k
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 ...
• 143k

### 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$ ...
• 143

### 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 ...
• 149k
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(...
• 143k

### 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)$ ...
• 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. ...
• 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 ...
• 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 ...
• 12.7k

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