Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
32 views

Collisions in Diffie-Hellman private keys

Given a generator $g$, a large, safe prime $P$ and a result of the DH key exchange $g^{xy} \mod P$, how would I come up with two different $x', y'$ s.t. $g^{x'y'} = g^{xy} \mod P$
0
votes
0answers
33 views

Algorithm to compute DLOG for elliptic curve $E(F_p)$ with order p

I was reading about elliptic curves in this pdf. Page 55 of the pdf states that if number of points on elliptic curve #$E(F_p) = p$, then there exists a p-adic logarithmic map that homomorphically ...
-1
votes
0answers
29 views

How to Generate an Instance of Discrete Logarithm Problem [duplicate]

I am looking to generate an instance of the discrete logarithm problem in Java, using a cyclic field $F_p$ with its generator $g$. But looking for a generator of a field could take too long, So is ...
2
votes
1answer
92 views

Solving discrete log in partially known group

Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,...
0
votes
4answers
83 views

Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$

In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
4
votes
0answers
57 views

Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
1
vote
0answers
59 views

Security of BLS under additional information on the secret key

Question A Is the BLS signature scheme still secure if an adversary in addition to the public key $ pk = g_2 \, sk \in \mathbb{G}_2 $ also obtains additional information on the private key $ sk $, ...
-1
votes
1answer
79 views

Find $F(2x)$ from $F(x) = a^x \bmod p$

Given $F(x) = a^x \bmod p$, where $a$ is a primitive root of $p$, Is it possible to work out what $F(2x)$ or $F(3x)$, etc if you know what $F(x)$ is but not $x$. If you use $F(x)$ then $F(2x)$, etc ...
2
votes
1answer
59 views

Pedersen commitments, what happens if I choose $H$ such that $H = a\times G$?

For Pedersen commitments of the form $C = x\times G + r\times H$, what is the worst thing I can do if I already know $H$ such that $H = a\times G$ ? For standard curves, there are specifications for ...
4
votes
1answer
137 views

Is there a group where CDH is easy but DLog is hard?

The question is quite simple: Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard? Refresher on the problems: CDH:...
0
votes
1answer
119 views

What math should I learn to get in depth with Elliptic Curve Cryptography research?

My background is computer scientist. I have done applied cryptography research for a while. Currently, I'm working on Elliptic curve cryptography. To understand the idea and how to use Elliptic curve ...
0
votes
0answers
45 views

Discrete logarithm for a range

I previously asked this question on the math site but didn't get a response. Are there any efficient algorithms for solving the following problem? Let $b\leq m<n$, what is the smallest value for $...
1
vote
0answers
37 views

Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?

I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you. "...
0
votes
1answer
58 views

Solving discret log problem

Can the discret log problem be solved when the modulus is a hard to factor composite number, i.e. when modulus $n=p*q$, where $p$ and $q$ are two large prime numbers?
-1
votes
1answer
65 views

Is this problem still as hard as discrete logarithm (modified ElGamal)?

I am trying to find a vulnerability or proof for the following problem: ElGamal part. Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate ...
2
votes
1answer
84 views

Understanding the Pohlig-Hellman algorithm

The paper has the following relation: $$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$ where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation ...
4
votes
0answers
78 views

Zero knowledge proof for a discrete logarithm

Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows: Pick $g$ as a random element from $Z_N^*$ Pick $x$ as a ...
4
votes
1answer
174 views

Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes

The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this ...
1
vote
1answer
52 views

Galois Field multiplication instead of Diffie Hellmans discrete logarithm

I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I ...
1
vote
1answer
51 views

Is this problem same as discrete logarithm?

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\...
2
votes
0answers
56 views

How many qbits are required to break Diffie-Hellman over a multiplicative group

There have been comparisons between RSA and ECDH with regards to the number of qbits (qubits) required to break the algorithm with a specific key size. But how many qbits are required to break "...
2
votes
1answer
277 views

How to solve this ECDLP?

The Problem is as follows: $E: y^2=x^3+17230x+22699 \pmod{23981} $ $p=23981$ is prime number point $G$ $G$'s order $109$ : prime number Alice creates a public key by ...
-1
votes
1answer
70 views

Is that right what I understand about MOV attack?

There is an elliptic curve. $y^2 = x^3 +ax+b \pmod p$ ($p$ is prime number) To solve DLP, need to find $r$ from given points $G$, $rG$. ($G$'s order is $q$ and $q$ is prime number) The MOV attack ...
0
votes
1answer
61 views

If the order of g is a prime number, is Pollard-rho the best?

If the bit size is 128 bits, I know that BSGS is not possible due to memory issues. I know that the complexity of Pollard-rho for 128 bits is 2^64. and I know that it is not possible to do 2 ^ 64 ...
1
vote
1answer
54 views

Can I use Pollard'-Rho even when the order is not a Prime?

I am now solving the ECDL problem. I want to use [discrete_log_rho] in SageMath, but I can not use it because ORDER is not a prime number. Can I change it to a decimal number close to ORDER at my ...
-2
votes
1answer
45 views

Diffie Hellman Key Exchange Security wrt the hardness of discrete Logarithm

Hi I am very new to this field and I was wondering how one would prove or disprove the following statements: 1) if the DH key exchange protocol is secure for a finite cyclic group G, then computing ...
1
vote
1answer
62 views

Does knowledge of equal exponents decrease security?

Say I have a group $G$ with two different generators $g_1$ and $g_2$, where the discrete log from one to another is unknown. Also, there are two public commitments $g_1^{r}$ and $g_2^{r}$, where it ...
2
votes
1answer
134 views

Finding missing bits mathematicaly in a DLP situation (full problem)

In a preparatory question we had to recover decimal digits $@$ of $r$ and $s$ given $g=51234$, $h=90403$, $N=111649$, $r=3@497$, $s=276@3$, with $r$ and $s$ the smallest positive solutions to $g^r\...
2
votes
1answer
98 views

Finding missing bits mathematicaly in a DLP situation

Here is a DLP exercice $g = 51234,\; h = 90403 ,\; N = 311 \cdot 359 = 111649$. Define $r$ as the smallest positive integer with $g^r \equiv h \pmod N$. Define $s$ as the smallest positive integer ...
1
vote
1answer
94 views

BLS hash as a group element exponent?

In BLS short signatures paper, the authors describe a hash function $H\colon\ \{0, 1\}^∗ → G^∗$, where $G$ is a Gap-Diffie-Hellman group. They present a structure where a standard hash is used on a ...
2
votes
0answers
69 views

Explanation of a proof of one of Shoup's lemmas

In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma: Lemma 1 Let $p$ be prime and let $t \ge 1$. Let $F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \...
1
vote
1answer
38 views

Discrete Log with regard to a random base

Suppose DL is hard in $G=\langle g \rangle$. For a uniformly random group element $r \in G$ (suppose $r=g^a$), is it hard to find $s$ given $r^s$ and $r$? Does the computational assumption have a well ...
4
votes
1answer
103 views

Trouble understanding the correctness of this Zero-Knowledge proof of posession of a discrete log

I came across the following protocol for a "Zero-Knowledge Proof of a Discrete Logarithm" in Bruce Schneier's Applied Cryptography (second edition) book. I simply cannot prove to myself that this ...
0
votes
2answers
80 views

Specific discrete logarithm question

I came across a DL that I need to solve... 5^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587) The modulus is a 124 bit ...
0
votes
1answer
88 views

Sigma protocol ZK-proof of a pair of pedersen commitments

Let's say you are using a $\Sigma$ protocol ZK proof to prove knowledge of $x_1, x_2$ so that $Y = g_1^{x_1}g_2^{x_2}$. Of course $g_1$, $g_2$ are generators within cyclic group G of prime order q, ...
0
votes
1answer
73 views

Describing Discrete Logarithm Assumption

I'd like to work out how exactly we should describe the discrete logarithm assumption (say, if we are writing a paper). Consider this: Let Gen be a group-generation algorithm on input $1^n$, which ...
3
votes
2answers
75 views

Discrete Logarithm in a specific group

I am considering a setting similar to the one of the Paillier cryptosystem, where we sample two distinct odd primes $p,q$, we set $n=pq$, we generate $a \leftarrow \mathbb{Z}_{n^2}^*$ and finally we ...
-1
votes
1answer
54 views

Breaking DDH assumption

DDH says that: $(g,g^a,g^b,g^c)$ should be indistinguishable from $(g,g^a,g^b,g^{ab})$ assuming $a,b,c\in Z_P$. However, since $Z_p$ is finite and has $p-1$ elements, can we not just try $n^2$ ...
3
votes
0answers
98 views

Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve ...
2
votes
2answers
70 views

Number of bits specified in standards implementation?

Currently deployed RSA and discrete logarithm implementation uses $1024$ to $2048$ bits. Hypothetically speaking if a crypto team produces a faster algorithm that moves current factoring and discrete ...
-1
votes
2answers
78 views

about DL hash function proof

$$h(m) = g^m(\bmod p)$$ where $p$ is a prime number, how can I prove that this is a one way function and collision free? $$h(m) = g^m(\bmod n) $$ where $n=pq$ for two distinct primes $p,q$, how can I ...
0
votes
1answer
39 views

Discrete logarithm problem - Pohlig Hellman $GF(2^p)$

I would like to ask how to modify Pohlig Hellman algorithm if I need to work with polynomials $GF(2^{60})$ I know how this algorithm works with numbers, but I am not able to imagine how to do some ...
4
votes
1answer
264 views

Solving the discrete logarithm problem for a weak group

I was reading an answer about an attack on a weak group for the discrete logarithm problem and wanted to formalize and verify that the attack was correct. That is, that it was guaranteed to always ...
4
votes
3answers
662 views

How can there be insecure elliptic curves if the discrete logarithm problem is hard?

The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure ...
0
votes
1answer
265 views

Schnorr signature using discrete logarithm / problem with python implementation [closed]

For educational purposes (by purpose with small values for the prime order q), I tried to write a small Python implementation of the Schnorr signature described in the Wikipedia article https://en....
1
vote
1answer
32 views

DLP-based keyed one-way function

I am trying to understand if it possible to use DLP to build a keyed one-way function with the following properties: $H_a(H_b(M)) = H_c(M)$, where $a$ and $b$ are the keys, and $c=a*b$ The output of ...
10
votes
1answer
243 views

Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
0
votes
0answers
56 views

Information sharing using interactive zero-knowledge system

I am trying to build a system that would allow information sharing in a kind of zero-knowledge way. Here is the set up: Let's say there is a trusted third party that has Alice's sensitive info M (e.g....
0
votes
1answer
39 views

Breaking a modified version of Diffie Hellmann Protocol

I'm modifying the Diffie Hellman protocol as follows: We are given a large prime number $p$ and exponent $x$ such that $0 \lt x \lt p-1$ and $\mathrm{gcd}(x, p-1) = 1$. Also we pick $g$ such as $1 \lt ...
3
votes
1answer
139 views

How hard is the following q-Strong Diffie-Hellman problem?

From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard. For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the ...