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.
13
votes
3answers
814 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 ...
10
votes
2answers
276 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 ...
8
votes
1answer
188 views
Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?
A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using ...
7
votes
1answer
132 views
Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$
Suppose, for some security parameter $n$ you choose a prime $p$ such that $p = 2^n+c$ for some relatively small $|c| < 2^m << 2^n$. I have seen such primes being called Pseudo-Mersenne Primes ...
7
votes
1answer
222 views
Security of pairing-based cryptography over binary fields regarding new attacks
In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$.
Pairing-based cryptography using binary ...
6
votes
3answers
270 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 ...
6
votes
3answers
464 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 ...
5
votes
2answers
184 views
Why would this method of discrete logarithm finding not work?
Say we do know $b$ but not $k$, and are given $g$ such that $g\equiv b^k\pmod p$. And say there exist factors $E = e + m'p$ ($e \equiv b^i \bmod p$) and $F = f + m''p$ ($f \equiv b^j \bmod p$) of $g$. ...
5
votes
1answer
128 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 ...
4
votes
1answer
162 views
What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA
After just reading the post Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?
I was a bit confused. DSA, ElGamal and others are based on ...
4
votes
2answers
234 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 ...
4
votes
0answers
83 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, ...
3
votes
3answers
465 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 ...
3
votes
3answers
1k 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 ...
3
votes
1answer
885 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 ...
3
votes
1answer
72 views
How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$
Use the notations form the Wikipedia article Paillier Cryptosystem
, assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?
3
votes
1answer
78 views
How much do we trust KEA1 Assumption?
Let $$(g,h=g^s,q)$$ be a tuple such that $g$ is a generator for a group $\mathbb{G}$ of ord $q$ and $s$ is uniformly random in $\mathbb{Z}_q$.
The KEA1 Assumption saies that for any adversary ...
3
votes
1answer
71 views
iterated discrete log problem
Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$
For $i=1$ this is the discrete log problem and is assumed to to have ...
3
votes
2answers
210 views
How can I solve the discrete logarithm modulo 2q+1 if I can solve it in the subgroup of order q?
As part of my cryptography course I came across an exercise that neither me or my friends could figure out.
The problem statement is as follows:
Let $p$ be a large prime of the form $p = 2q + 1$ ...
3
votes
1answer
114 views
Trying to better understand the failure of the Index Calculus for ECDLP
So I'm going to give you guys my understanding and then if you would be so kind as to tell me where I'm off the mark (hopefully I'm not completely wrong).
So basically the index calculus for the ...
3
votes
1answer
60 views
Chosen ciphertext insecurity in an ElGamal variant
I'm trying to prove something and if I can show that there is a simple way to calculate $(g^a \bmod p)^k$ if I know both $g^k \bmod p$ and $g^a \bmod p$, then (I think) it will help me prove it, but ...
3
votes
1answer
181 views
A discrete-log-like problem, with matrices: given $A^k x$, find $k$
Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer.
Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
3
votes
0answers
127 views
Finding where I am in a linear recurrence relation
Suppose I have a linear recurrence relation
$$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$
where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as ...
2
votes
1answer
224 views
Why are elliptic curve variants of RSA “chiefly of academic interest”?
Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My ...
2
votes
3answers
195 views
Discrete log problem, when we have many examples
Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem?
Oh, heck, I should be more precise. ...
2
votes
1answer
283 views
Why can't I break ElGamal encryption by brute-forcing the secret exponent?
I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system.
I am using the terms as defined in Wikipedia.
Alice publishes $g$ and $g^x$. ...
2
votes
2answers
90 views
How to test if a number is a primitive root?
How to test if a number is a primitive root, assuming the modulus is a prime? And if not?
Is it not enough if the number is relatively prime to the modulus or prime?
2
votes
1answer
82 views
Why is the discrete log problem easy when the exponent comes from a binomial distribution?
I read in http://epubs.surrey.ac.uk/7219/2/esorics06.pdf that in exponential El Gamal the discrete log problem for recovering $m$ from $g^m$ can be made tractable when $m$ is drawn from a binomial ...
2
votes
2answers
346 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 ...
2
votes
1answer
51 views
How is ElGamal not secure under chosen ciphertext attack, but semantically secure in some cases?
I know that you can create a ciphertext c' using c and then find the corresponding m' for c' which you can use to find m for c. So, doesn't this mean that it is not semantically secure? But I also ...
2
votes
1answer
57 views
Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack
The curve $E(\mathbb{F}_{47}):y^2=x^3+x+38$ has order $61$ and $61|47^3-1$ so the embedding degree of $E$ is $3$ and therefore the MOV attack, presumably using some sort of distortion map and a ...
2
votes
2answers
115 views
Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset
Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ ...
2
votes
1answer
145 views
Stream ciphers based on discrete logs
Blum Blum Shub is a stream cipher that is provably reducible to the difficulty of factoring integers.
I'm wondering whether there is a similar construction for discrete logs?
For example, I could ...
2
votes
2answers
138 views
Is there a way to compare the 923 bit pairing based key with RSA or AES, etc
I've see many articles, most of them basically the same, praising Fujitsu for cracking what is referred to as a 923 bit pairing based encryption. I understand that in comparing RSA to AES you've got ...
2
votes
1answer
112 views
DLP based crypto systems with multiple independent generators
One example of a DLP based crypto system (or rather DDH based crypto system) where the public key parameters include two independent generators of the subgroup, is Cramer Shoup. Since the security ...
2
votes
1answer
77 views
Discrete log analog of ECM factoring algorithm?
Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas.
Is there an analog of the elliptic curve (ECM) ...
2
votes
1answer
172 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
0answers
167 views
Is there a practical zero-knowledge proof for this special discrete log equation?
We have a multiplicative cyclic group $G$ with generators $g$ and $h$, as in El Gamal. Assume $G$ is a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$. There are two parties, Alice and Bob:
Alice knows: ...
2
votes
0answers
138 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$ ...
1
vote
2answers
158 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 ...
1
vote
1answer
88 views
Key sizes for discrete logarithm based methods
I have a question regarding the key generation process of methods that are based on the discrete logarithm problem.
This site gives some good insights, but I don't fully grasp it I think: ...
0
votes
1answer
85 views
Can one detect if two pairs of elements in Zp have the same exponential relation?
Suppose that $p$ is a safe prime of 2048 bits ($p = 2q + 1$, and $q$ is prime).
Suppose that one is given two pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that:
$y_1 = x_1^{r_1} \pmod p$
$y_2 = ...
0
votes
1answer
80 views
Preimage resistance hash in digital signature
I'm studying about preimage resistance property of the hash functions.
In particularly I'm reading as the missing of this property can be fatal in digital signatures that use RSA.
Further details:
...
0
votes
0answers
55 views
How compared encryption algorithm in terms of efficiency
I doing to compare two algorithm cryptography. first algorithm is RSA cryptography and second algorithm is El Gamal elliptic curve cryptography. now I want a way to compare between two algorithm by ...
