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.
654
questions
1
vote
2
answers
193
views
Why using q = (p - 1)/2 for discrete log Diffie-Hellman scalar operations and not p?
As defined in RFC 3526 the prime $p$ and generator $g$ are known. The prime $p$ defined there is a safe prime, which can also be expressed as $p=2q+1$ with $q$ prime. The amount of elements in this ...
- 121
-1
votes
1
answer
68
views
Is MOV attack against ECDLP fundamentally impossible?
The main idea of the MOV attack is to map EC additive group of order $n$ to multiplicative group in the finite field extension $p^k$. For this, the groups must have the same order, what fully relies ...
2
votes
1
answer
227
views
RSA like problem with unknown e and d
I have encountered a strange source code part in a soon-to-be-decommissioned legacy app, which uses an RSA-like scheme for "one-way hashing" data.
It works like this:
base^input mod N = hash
...
- 21
0
votes
0
answers
48
views
Why exactly finding the same result by changing a scalar in such a case is equivalent to solving the discrete logarithm between one or more points?
Let’s say I have 3 randomly sampled points on a curve in Edwards form (sampled only the first time and not at each computation) $P1$ $P2$ $P3$ and 3 scalars $S1$ $S2$ $S3$ such as :
Both $S1$ $S2$ $...
- 178
0
votes
2
answers
176
views
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?
Simple question : given a randomly selected point $P$ belonging on a given Edwards curve defined on a prime field, does 2 scalars $S1$ $S2$ exist such as :
$packed(S1\cdot P)= packed(S2\cdot P$) (...
- 178
0
votes
1
answer
49
views
Is discrete logarithm good approach for a time-bounded proof of work?
I'm writing a system where a client needs to show via proof of work that it's really intending to consume CPU resources on the server, and not just bombing the server with denial of service queries. ...
- 1,371
3
votes
2
answers
575
views
Why is discrete logarithm not quantum proof?
I don't understand why discrete logarithm is not quantum proof. I understand that quantum computer can quickly compute the exponent, but there is a modulo in the equation. Doesn't it mean, that there ...
- 31
4
votes
0
answers
77
views
Comparing quantum computing resources to break the DLP on elliptic curve group vs Schnorr group
Take an elliptic curve group of 256-bit prime order $n$ over a 256-bit prime field in which the Discrete Logarithm Problem is believed hard, e.g. secp256r1. Build an isomorphic Schnorr group by taking ...
- 143k
0
votes
0
answers
26
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
0
answers
88
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 ...
- 178
0
votes
1
answer
65
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 ...
- 1
2
votes
1
answer
228
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 ...
- 33
4
votes
2
answers
113
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
6
votes
3
answers
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 ...
- 63
0
votes
1
answer
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 ...
