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.

learn more… | top users | synonyms

16
votes
3answers
1k views

How robust is discrete logarithm in $GF(2^n)$?

"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime $p$. However, there exist other finite fields out there, in ...
7
votes
1answer
222 views

Are there security issues with discrete logarithm keys not being uniformly distributed?

Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both ...
6
votes
1answer
202 views

Is it possible to determine or estimate the period for Blum-Micali PRG?

The Blum-Micali is a cryptographically secure pseudorandom number generator. The construction (from wikipedia): Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$. Let $x_0$ be a ...
2
votes
0answers
46 views

How does the Number Field Sieve find the target number for Diffie-Hellman?

I have read some papers relating to the Number Field Sieve, but I could not figure out how this algorithm helps in Logjam, or even what is meant by the number field. What is this? What is meant by ...
0
votes
0answers
26 views

Why $p-1$ needs large factors in discrete logarithm?

In discrete logarithm over cyclic group $\Bbb Z_p$ where $p$ is a prime or $p=q^n$ a prime power it is desired that $p-1$ needs to have large factors except for $2$. What is the consequence even if ...
10
votes
3answers
1k views

Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?

In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization ...
2
votes
1answer
53 views

Fixed primes in discrete logarithm

The discrete logarithm problem is to find $z$ when the inputs are $g,h,p$ where $g^z\bmod p$. Supposing if you fix $p$ then does the problem become any easier to attacks and is there a $(\log p)^c$ ...
0
votes
0answers
56 views

How to calculate the exponent in modular exponentiation?

I have a problem when calculating power in modular, $a^b \bmod c = d$. where we can know values of $a$, $c$ and d, but we don't know values of $b$. example : $29^b \bmod 1024 = 365$. So, how can I ...
6
votes
2answers
139 views

The difficulty of computing discrete logs

I understand that in Diffie-Hellman it should be hard to compute $a$ given $g$ and $g^a$. In computational Diffie-Hellman, it appears to be hard to compute $(g^{ab})$ from $g^a$ and $g^b$. As for ...
2
votes
2answers
247 views

Zero knowledge-proof for discrete log that is not honest-verifier

Take a cyclic group of prime order. The Schnorr-protocol for proving knowledge of the discrete logarithm of some group element is honest-verifier zero-knowledge, meaning that if the verifier chooses ...
1
vote
0answers
16 views

Sigma protocol: witness hiding

I am working on an assignment and I am stuck with the last part of proving witness hiding for the protocol. I have previously proved it is witness indistinguishable, and it has q (primer number ...
3
votes
2answers
343 views

Why is “multiplying” $g^x$ and $g^y$ not possible?

The computational Diffie-Hellman problem states that for a cyclic group $G$ of order $p$ and a generator $g$, it is hard to find the value $g^{xy}$ given only $g^x$ and $g^y$ (but easy if either $x$ ...
0
votes
1answer
70 views

How secure is this logarithmic encryption algorithm?

How secure would the following logarithmic encryption algorithm be when tested under the same conditions as high end encryption algorithms (AES, RSA etc...). Note: For smaller text the text will be ...
1
vote
0answers
62 views

Calculating the discrete logarithm

I'm given a prime number $p = 1217$ I'm also given the following equations: $$ 40 \equiv \log2 \pmod{64} \\ 63 \equiv \log3 \pmod{64} \\ 13 \equiv \log5 \pmod{64} \\ 13 \equiv \log2 \pmod{19} \\ 10 ...
5
votes
0answers
57 views

Software timing attack using Kocher method

What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$? I'm working from this paper: Volker ...
0
votes
2answers
76 views

Is the Discrete logarithm problem suitable for this pairing scheme?

Let $Ans$ be the product of two pairings : $e(g,h)^{k} \times e(g,h)^{r}=Ans$ If everybody knows only $[g,h,e(g,h)^{k}]$ but $[r,Ans]$ is not known. In the discrete logarithm problem, the user knows ...
4
votes
1answer
201 views

Discrete logarithm problem is easy in a cyclic group of order a power of two

Let $G=\langle g\rangle$ be a cyclic group of order $2^{k}$ and let $h\in G$. I have read that it is easy to find $\log _{g} h$, but I haven't been able to figure out how. Do you know why this can be ...
0
votes
0answers
29 views

Is original DSA a TEGTSS-I scheme?

Brickell et al. define TEGTSS-I scheme in paper "Design validations for discrete logarithm based signature schemes" In this paper original DSA is generalized as DSA-I variant where $r = g^k \bmod p ...
1
vote
1answer
123 views

What is the difference between discrete logarithm and logarithm? [closed]

Why discrete logarithm? Is discrete logarithm is part of logarithm? I do not understand the difference between these two concepts.
2
votes
1answer
61 views

Bilinear map assumpion

Is there an assumption that says from a tag $k\cdot e(g,g_1)^{rx}$ ($k,r$ are secret) it is difficult to forge it with some x': $k\cdot e(g,g_1)^{rx'}$, as long as you cannot solve DL in ...
0
votes
1answer
56 views

What is base of $\log$ in Subexponential Algo for DLP?

I am currently going through this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem" by Leonard Adleman. On page 56, author mentions that Dixon's algorithm - Asymptotically Fast ...
19
votes
0answers
687 views

Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $\log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at ...
1
vote
1answer
52 views

How to compute the discrete logarithm of Diffie-Hellman with a composite modulus?

Imagine $n = pq$ with $p-1 = 2 p_1 p_2$ and $q-1 = 2 q_1 q_2$. I can compute the discrete logarithm of $y = g^x \pmod{n}$ by computing the discrete logarithm of $y$ modulo $p$ and $q$. But then how ...
3
votes
1answer
124 views

Given $g,g^t$ in a cyclic group of order $pq$, is it hard to compute $g^{t^{-1}}$?

Suppose we have a group $G$ cyclic of order $pq$ , where $p,q$ are primes. Let $g$ be a generator of $G$ and $t\in \mathbb{Z}_{pq}$. Having $g$ and $g^t$, it seems to be very hard to find ...
0
votes
2answers
50 views

Is the complexity of Pollard rho for discrete logartihm really the modulus?

so I'm reading everywhere that the Pollard Rho for Dlog's complexity of $g^a \pmod{n}$ is $\mathcal O(\sqrt{n})$. Shouldn't it be $\mathcal{O}(\sqrt{q})$ with $q$ the order of $g$?
3
votes
1answer
87 views

Why do the subexponential algoriths for the DLP not work for the ECDLP?

Elliptic curve cryptography is much more secure for the same parameters because attacks that work on the DLP do not work on the ECDLP. Why do the attacks fail in the latter case?
0
votes
2answers
126 views

How can prime factor of $q-1$ divide prime $q$?

In this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem", author mentions (page 56), For each $p_l^{e_l} | q$ proceed.... $p_l^{e_l}$ is one of the prime factors of ...
0
votes
2answers
97 views

Discrete logarithm hash function Exercises

I have a problem with this exercise: Let $G$ be a group of order a prime $q$ and let $g, h$, be two randomly selected elements of $G$, with $g,h\ne 1$. Consider the following hash function on ...
2
votes
0answers
42 views

Recover secret $x$ when $c\equiv m^x \pmod p$ with public $p$ (modified)

Given an encryption system where $c\equiv m^x \pmod p$, $p$ is a known prime, 1. Is it possible to recover $x$ with a known plaintext attack? Given $(p,\text{factorization of }\varphi(p),m,c)$ 2. Is ...
2
votes
0answers
59 views

Convert messages to elliptic curve points [duplicate]

Let $E$ be an elliptic curve; $\alpha,\beta$ two points of $E$; and $a$ a private key such that $\beta=a\cdot\alpha$. We choose random integer $k$ and plain text $x\in E$. Encryption and decryption ...
1
vote
1answer
333 views

How is El Gamal different from Diffie Hellman Key Exchange [duplicate]

I am Reading RSA and Public-Key Cryptography by Mollin and I can't make out how El Gamal is different from Diffie Hellman Key Exchange. Any thoughts?
11
votes
4answers
1k views

RSA & DH at risk due to math advances, will this eventually affect elliptic curves too?

I was looking into the predictions by some researchers that RSA and Diffie-Hellman may not be secure in the next few years due to advances in math and being able to calculate the discrete logarithm ...
7
votes
3answers
212 views

Do I understand (below) why Q = dP is easy while finding d is hard

As we all know for discussion of Dual_EC_DBRG, the point on an elliptic curve Q can be calculated from P and some (large) integer d $Q = dP$ And we know that knowledge of Q and P is not sufficient ...
4
votes
1answer
81 views

Diffie-Hellman: *assumed* largest prime factor of order of $g$?

I've read in several places: some of my confusions about DDH assumption - comment by Thomas Pornin on his own post Is there a key length definition for DH or DHE? - the answer by Tom Leek that ...
2
votes
1answer
69 views

Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order

In regular ElGamal and DSA, we choose large primes $p$ and $q$ such that $p\equiv 1\pmod{q}$, and a group element $g$ of order $q$ by computing $a^{(p-1)/q}$ for some random $a$. This is to prevent ...
2
votes
1answer
50 views

Generalization of the DL-assumption in bilinear group pair

When thinking about a pairing-based cryptographic scheme, I encountered the following problem. Let $e \colon G_1, G_2 \to G_T$ be a Type 3 pairing. Then: Given $P, zP \in G_1$ and $Q, zQ \in G_2$, ...
3
votes
0answers
47 views

Cost of attack on DSA with attack on DLP

Are there any (recent) estimates of cost of attack on DSA by solving the discrete logarithm? I'm especially interested in attacks that use Pollard's rho algorithm. Are there any optimized ...
1
vote
0answers
39 views

How to find the integer multiplicand from given two points?

I have two points on an elliptic curve $P(x_1,y_1)$ and $Q(x_2,y_2)$ and a scalar value $x$, where $P=x \cdot Q$. What is the best way that I could figure out the value of $x$? Given that I know all ...
3
votes
1answer
43 views

How many bits of an exponent are leaked when doing a powmod?

How many bits of the exponent $x$ are leaked when you calculate and reveal $g^x \pmod p$ for some generator $g$ of $\mathbb Z^∗_p$? The low bit of $x$ is obviously leaked: the low bit equals ...
0
votes
1answer
194 views

How to prove knowledge of discrete logarithm in a product?

Definitions Suppose I have two large safe primes $p$ and $q$, and a composite number $N=pq$. I have $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$; $g$ and $h$ are generators of $G$. I commit ...
3
votes
2answers
70 views

Discrete Logarithm problem with inverse

Let $\mathbb G$ be a cyclic group of order $q$. The Discrete Logarithm Problem (DLP) is, given $g, g^x \in \mathbb G$, to compute $x \in \mathbb Z_q $. I'm interested to know if there is a known ...
4
votes
1answer
55 views

State level “Weak Diffie-Hellman” working for SRP too?

I've read about the "Weak Diffie-Hellman" attack (paper, website), where a resourceful entity like a state can pre-compute values for known primes to aid solving the discrete logarithm problem for ...
1
vote
2answers
673 views

Reuse of a DH / ECDH public key

I was wondering whether it is safe to use the same DH or ECDH key pair in more than one key agreement, particularly if these public keys are in a public registry. These public keys could be used by ...
9
votes
3answers
1k views

Perfect zero knowledge for the Schnorr protocol?

Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?
2
votes
0answers
41 views

Is it possible to generate backdoored DH parameters?

I know it has been already asked and answered whether it's possible to generate weak DH parameters. But "recentely" we experienced the Logjam attack, which makes use of the pre-computation ...
2
votes
0answers
45 views

Testing PRNG quality from ECC public keys?

Having a large set of ECC public keys $P_i = n_iB$ on a fixed curve $E$ over a prime field, is there a way to determine if coefficients $n_i$ were generated using a bad PRNG? In other words, can a ...
0
votes
1answer
47 views

Reduction to cdp,dl or cdh?

Assuming a randomize encoding scheme that takes as input a secret key $\mathsf{sk} \in \mathbb{Z}_p$ for a large prime number $p$. Then the algorithm outputs $g^{\mathsf{sk}x}, x \in \mathbb{Z}_p^*$. ...
4
votes
1answer
228 views

Do Gap-CDH groups exist?

A Gap-CDH group is such that, given group elements $g, a = g^x, b = g^y$, it is hard to compute $g^{xy}$, but, given a group element $c$, easy to verify if $c = g^{xy}$. While such groups have been ...
0
votes
1answer
63 views

Brute forcing the secret key in Elgamal encryption

Crypto noob here, I am attempting to do this programming challenge. I do not have the secret key that is used to decrypt the message. However, the key is small enough for a brute force approach. I am ...
1
vote
1answer
51 views

Degenerate discrete logarithm in binary field

Given a field $\mathbb{F}_{2^n}$, are there any choices of primitive element $g$ that make the discrete logarithm easier for that generator? That is, are there any degenerate cases? For example, if I ...