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

5
votes
1answer
363 views

Safe generator for ElGamal signature

What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)? I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ ...
2
votes
1answer
256 views

Finding a solution to a (sort of) discrete logarithm by asking questions

Let $p = kq + 1$ and $q$ be primes such that $log$ $q = n$, $log$ $k = n$ and such that the bit size of every prime factor of $k$ is bounded by $log$ $n$. Let $g$ be a generator of the unique ...
2
votes
2answers
728 views

ECC algorithm pollard's $\rho$ complexity

One of the methods to break a ECDLP is Pollard's rho algorithm. When ECDLP is defined over a finite field $F_p$, and given a relation $S=w.T$, where S and T are a member of $F_p$. Then ECDLP is to ...
3
votes
0answers
113 views

RSA security assumptions - does breaking the DLP also break RSA? [duplicate]

Possible Duplicate: Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, ...
8
votes
3answers
4k views

What should be the size of a Diffie-Hellman private key?

I'm implementing the SRP-6 protocol, which relies on discrete logarithms for it's security (essentially Diffie-Hellman). The RFC documents state: The private values $a$ and $b$ SHOULD be at least ...
5
votes
4answers
2k 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 ...
13
votes
2answers
425 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 ...
4
votes
2answers
337 views

An Elliptic curve cryptography implementation which can be terminated

I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken. One idea would be to use ...
5
votes
2answers
2k views

How to calculate the time it'll take to crack RSA or DH?

Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
7
votes
3answers
1k views

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective. RSA labs makes a similar statement: The discrete logarithm problem bears the same ...
10
votes
3answers
367 views

Mapping between subgroups and the integers

This question is a companion to the equivalent question on elliptic curves. Preliminaries Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime ...
2
votes
2answers
211 views

Is there a cumulative commitment scheme?

For a certain application I need a commitment scheme where each user could make a commitment, and a single verification operation could verify all the commitments simultaneously, faster than single ...
4
votes
1answer
2k views

How to practically find solutions to a discrete logarithm?

Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit ...
6
votes
1answer
184 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 ...
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
3answers
679 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 ...