We’re rewarding the question askers & reputations are being recalculated! Read more.

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

393 questions
Filter by
Sorted by
Tagged with
28 views

### Weakness in Pohlig-Hellman algorithm

Let's try to solve a discrete logarithm: $\beta \equiv \alpha ^{x} \bmod \,\, p$ using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that ...
129 views

### Factorization or discrete logarithm is difficult for an attacker?

I have read that difficulty in breaking many algorithms are based either on Factorization or discrete logarithm. I am reading about schemes that are similar to RSA which make use of integer ...
8k views

### What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?

How are the three problems Discrete Logarithm, Computational Diffie-Hellman and Decisional Diffie-Hellman related? From my understanding, since the Discrete Log (DL) Problem is considered hard, then ...
37 views

### Identity Based Encryption: Known Random Value

Let's consider a situation whereby: Alice generates a ciphertext c from a message m using Bob’s ID. An attacker Carol can get c from the open channel. She knows that c is generated by using ...
47 views

### Discrete log problem in $N$ and $Z$

Is the discrete log problem hard in $N$ or $Z$?
35 views

### For discrete elliptic curves, can you find G, if you are given b and B?

I know you cannot find $b$ if you are given $B$ and $G$, where $B = [b]G$, but can you find $G$ given $b$ and $B$?
53 views

### Elliptic curve discrete logarithm problem

I'd like to know what is the maximum bits of the finite field that we can solve the ECDLP in a "regular" computer in trivial time. Is there any recent data about this?
52 views

### How does the order of Q affect the time it takes to solve ECDLP?

I use Sagemath's built-in function discrete_log() to solve ECDLP and according to the documentation it uses Pohling-Hellman algorithm to solve an ECDLP. This is ...
35 views

### Retrieving correct ciphertext from additive ElGamal

I have been studying additive ElGamal and I think I have the hang of it except the part where the message $M$ must be retrieved by computing the discrete log of $g^M$. From what I've read, the ...
43 views

### Does the discrete log assumption hold if k > p

In discrete log cryptosystems like ElGamal it is noted that the "private key" $k$ should be chosen as any element of the group $G$ i.e. $k < p-1$. Does the integrity of the cryptosystem rely on $k$ ...
111 views

### Attacking any one in many public keys

The problem of finding private key from public key is typically studied in the one-key setup: what's the expected cost of breaking one key (e.g. by factoring a public modulus, or solving a discrete ...
59 views

### How do I interpret the CADO-NFS output for discrete logarithm calculation in GF(p)?

I'm using CADO-NFS to calculate discrete logarithm in a finite field GF(p). The problem is when I type ...
3k views

### What does “export grade” cryptography mean? And how is this related to the Logjam attack?

I am doing some research on the Logjam attack, and I need help in learning some terms that are new for me. What does "export grade" cryptography mean? And how is this related to the Logjam attack?
95 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 ...
175 views

36 views

### Questions regarding random values in Schnorr authentication

In Chapter 21.3 of Schneier, Applied Cryptography I read the following about the Schnorr Authentication Protocol: To generate a key pair, first choose two primes, $p$ and $q$, such that $q$ is a ...
66 views

### Difference between when select x from $\mathbb{Z}_{p-1}$ and $\mathbb{Z}_p$ in discrete logarithm Problem?

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions. Q1. when it refers to "El Gamal signature scheme", The key generation algorithm: it ...
76 views

### Proof Dlog is hard in generic group model

I want to know a proof for why the dlog problem is hard in the generic group model. But i can't find any resources online. Can someone please provide me a link or an explanation?
118 views

### Finding tetration in a multiplicative group modulo p

I have a variant on the discrete logarithm problem, involving finding tetration in a multiplicative cyclic group of integers modulo a large prime $p$: $$a = x^x \mod p$$ Where $a$ and $p$ are known, ...
82 views

### Discrete logarithm problem particularly hard for Schnorr groups?

The Wikipedia article on Discrete Logarithm just states without source: In some cases (e.g. large prime order subgroups of groups ($\mathbb{Z}_p)^×$) there is not only no efficient algorithm known ...
84 views

### Why are some group representations much easier to compute discrete logarithm for? [duplicate]

The multiplicative group mod $p$ is isometric to the additive group mod $p-1$, yet computing discrete logarithms in the additive group is easy and completing discrete logarithms in the multiplicative ...
76 views

Elliptic curves are usually defined over prime rings (fields), but what if we chose a ring of composite order? Let $n = pq$ for $p,q$ large primes. Say I have elliptic curve $y^2 = x^3 + ax + b$ over ...
970 views

### Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus?

I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime. Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete ...
366 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 ...
134 views

### Does knowing that the exponent is in a certain range help solving discrete log?

given: $c=g^i \bmod P$ $g$ generator for group with group size $\varphi(P)$ $g,P,\varphi(P)$,c is known by the attacker He wants to know $i$. Now the attacker also knows $j,k$ with $j<i<k$ $k-j$...
73 views

### How do discrete logarithm with modulo a prime and a non-prime compare?

Let $c_N = g^i \mod N$ and $N=p \cdot q$ and $c_P = f^j \mod P$ and $P$ a prime We assume $N,P$ has the same bit-length. $P$ is the best type of prime you can choose (e.g. safe prime). $N$ is a ...
### What information does $g^x$ reveal about $x$?
Let $p$ be a large prime number. Let $G$ be a subgroup of $\mathbb{Z}_p^*$ with order $q$ - again a large prime. Let $g$ be a generator of $G$. Consider the following standard protocol for ...