# Questions tagged [discrete-logarithm]

In cryptography, a discrete logarithm is the number of times a generator of a group must be multiplied by itself to produce a known number. By choosing certain groups, the task of finding a discrete logarithm can be made intractable.

646 questions
Filter by
Sorted by
Tagged with
17 views

### What logarithm does the "discrete logarithm problem" refer to in the context of ECC? [duplicate]

In the case of integers, solving the DLP is finding a solution to $n=\log_b(x)$ given $b$ and $x$. There's a "log" in the equation, so the name DLP makes sense. In the context of ECC, many ...
• 123
1 vote
73 views

### Is generating random blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?

I know there’re many questions that ask how to safely HashToCurve, but I want to know if the method I found in an actual implementation is secured against the ...
• 196
63 views

### diffie hellman key exchange compared with ECDH [closed]

I have to write a paper about the Diffie Hellman key agreement. I want to focus on the implementation with elliptic curves and comparing the safety for selected attacks such as Pollards Rho and ...
200 views

### Discrete log of Goldilocks, Babybear, and Mersenne31 fields

Does anyone know if the discrete log problem of these small prime fields: Goldilocks, Babybear, Mersenne31, has been solved? If not, is there a small prime field in which the discrete log of any ...
• 23
111 views

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

I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this 3 = (10^XA) mod 19 now everywhere I am finding only ...
• 141
4k views

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

For RSA, we need two primes p and q to define N = pq. We will only look how long it takes to generate a prime for p because the process is similar for q. From my lecture slides, my professor states ...
42 views

### SDLog - looking for papers

Reading trough SEC 1 V2.0 in txe appendices there is a mention of a elliptic curve semi logarithm (ECSLP) being used to forge ECDSA signatures. I am looking for papers on that problem and have been ...
1 vote
95 views

### 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?

I’m in the following situation : I’ve a portion/first bytes of a private secp256k1 security key such as it would take minutes to fully recover it through Pollard’s Kangaroo if I had the public key. ...
• 196
71 views

### Why do we use elliptic curves instead of just the discrete logarithm problem?

We have a cyclic field Fp where p is a prime number, a generator g, and an order n. A generator is an element such that $g^n=1$. A random number x has been chosen as the private key, selected from the ...
• 101
86 views

• 662
59 views

### Is it hard to find m, R to make RG^H(m||R)=C?

Assuming the generator of one group $\mathbb G$ is $G$. Given an element $C\in \mathbb G$ and a cryptographic hash function $H(\cdot)$, is it hard for one adversary to find a pair of message $m$ and ...
1 vote
102 views

### Discrete log problem - does luck exist?

Assume the discrete log problem: $g^x mod (p) = h$ For sure, $p$ is a prime number and $g$ is its primitive root or generator and assume that Alice sent $h$ to Bob and middle man caught it. So ...
94 views

### One group element hybrid encryption for El Gamal

I am really curious about this one problem 10.12 from Katz/Lindell's book. It goes as follows: I am quite sure we can assume that $\textsf{Enc}_k(m) \in \mathbb{G}$, as the authors devoted the whole ...
64 views

### Cryptographic accumulator via function composition

I am looking for an alternative to RSA accumulators, and I am wondering if the following option based on function composition might fit the bill. It seems like an obvious tweak on RSA accumulators, ...
59 views

32 views

### Cryptographic Applications of Composite Modular Exponentiation

I've developed an algorithm for fast modular exponentiation modulo composite numbers with known factorization. I'm not very well versed in cryptography, so I'm wondering if any of you know of an ...
92 views

### Discrete log hardness when secret is multiplied by public value

Given y = g ^ x is discrete log hard on some finite field, is y = g ^ (kx) also equally secure if the value ...
• 23
216 views

### When does index calculus work for discrete log?

Reading about index calculus for discrete logarithm, I noticed that it works for $(\mathbb Z / p \mathbb Z)^*$. Is this the only situation in which it works? If not, please give examples of other ...
103 views

### Key exchange from discrete logarithm only

Diffie-Hellman key exchange is sometimes informally said to be hard under the discrete logarithm assumption in the chosen group. But if I am reading literature correctly, it actually uses a stronger ...
• 233
1 vote
507 views

### Challenges like RSA factoring challenge

RSA factoring challenge is a famous one and is still not completely solved. Are there similar challenges for Discrete log over $\mathbb Z_p^*$? Discrete log over Elliptic curves? LWE? LPN?
• 930
167 views

### Hiding property of Elgamal-like bit commitment

An Elgamal-like bit commitment scheme: Let $\langle g \rangle$ be a group of order $n$, where $n$ is a large prime. Let $h\in_{R}\langle g \rangle\setminus\{1\}$ denotes a random group element such ...
• 450
163 views

### Why NIST 800-56A rev3 does not use cross secret calculation in C(2e, 2s, ECC CDH) scheme?

In the NIST 800-56A rev3 "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography" in section 6.1.1.2 "(Cofactor) Full Unified Model, C(2e, 2s, ECC ...
• 117
390 views

### Best Known Attacks on Discrete Logarithm in Generic Groups

This is a followup to my recent question Discrete Logarithm Challenges and Records. I am interested in confirming my understandings from the answer to that question, stated below: For a discrete ...
• 22.7k
527 views

### Discrete Logarithm Challenges and Records

I am wondering whether there are any current challenge problems for Discrete Logarithms. Specifically in $\mathbb{Z}_p^\ast$ as well as in elliptic curve groups. It turns out CERTICOM still has some ...
• 22.7k
98 views

### Given two unrelated generators $G_1$ and $G_2$, and a third with $H = G_1 + G_2$. Is it hard to compute $xG_1$ from $xH$?

Given some group in which both discrete logarithms and the computational Diffie-Hellman problem are hard. Furthermore, two random, unrelated group generators $G_1, G_2$, and a third generator defined ...
• 359
508 views

### Method to break a baby Elliptic Curve analog to secp256k1

What would be the method of choice to compute the private key from the public key on a baby analog of secp256k1, say with $p$ and $n$ 144-bit? What would be the pros and cons of Pollard's rho and ...
211 views

### Prove DSA signature scheme is EUF-CMA secure

I want to prove that the DSA signature scheme is EUF-CMA secure in the random oracle model, if the discrete logarithm problem is hard. I know it can be proved by the following two parts: Discrete ...
• 31
1 vote
44 views

### Can some cryptographic conclusions in the prime field be applied to the Galois field？

Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two ...
• 23
566 views

### What's wrong with this simple reduction of discrete logarithms to the Diffie-Hellman problem?

This recent paper shows that discrete logarithms are solvable if you have an oracle for the Diffie–Hellman problem. However, to me, it seems there is a much simpler reduction and I wonder where I am ...
• 359
1 vote
73 views

### How can I perform a one-client MITM attack in a Diffie-Hellman key exchange? [closed]

Suppose we have intercepted a public key exchange (via Diffie-Hellman protocol). In addition to the keys A and B, the generator g and the module p are known. Assuming that it is possible to exchange ...
• 11