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.
368
questions
3
votes
1answer
130 views
Why is the NIST recommendation for the private key exponent so much smaller than the modulus?
NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. This question answered how the modulus was chosen/calculated, however, why isn't the private key size closer to the ...
0
votes
2answers
59 views
Verify the discrete log of ECDSA is in range
Is it possible to verify the discrete log in elliptic curve is within range without uncovering it? I need to verify that $x$ is within $1$, $2^{64}$ for $xG=P$.
1
vote
0answers
48 views
How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?
Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element?
In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....
-1
votes
0answers
59 views
Collision resistance from discrete log
Let $G$ be a cyclic group of prime order $q$ generated by $g \in G$. $H$ is a hash function defined over as $H(\alpha_1,\alpha_2,...,\alpha_n)=g_1^{\alpha_1}g_2^{\alpha_2}...g_n^{\alpha_n}$ where $(\...
10
votes
0answers
216 views
How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?
There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time.
...
1
vote
1answer
77 views
How is the recommended NIST modulus for DLP chosen/calculated?
NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. From this answer it appears that the range of private key numbers is derived by calculating a prime modulus via $2⋅p$ ...
2
votes
1answer
48 views
Pollard's Kangaroo— What is the failure probability (assuming random functions)?
I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group.
He has a Kangaroo Algorithm (page 4) which allows you, if you ...
3
votes
0answers
76 views
What can be said about the self-power map on groups based on DLP?
Introduction
I've been playing with group representation theory some time, concretely representing groups as permutation groups (Cayley's theorem), where the group $G$ has an embedding into the ...
2
votes
1answer
68 views
Bit-strength of discrete logarithm for a group of integers modulo a safe prime
Preliminaries
Let $p$ be a safe prime number.
Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$.
We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ .
Let $g \...
3
votes
1answer
175 views
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 ...
2
votes
2answers
327 views
0
votes
0answers
36 views
Why do they use elliptic curve instead of circle or other simpler curves? [duplicate]
I am curious why people use elliptic curve in cryptography. I know the main requirement is DLP, but elliptic curve is not the only curve with such property. Some of curves seem to be even simpler.
As ...
0
votes
1answer
83 views
What makes the Discrete Logarithm Problem hard?
I am missing a crucial piece of the maths behind the DLP, and I'm hoping someone can give me a really dumbed down answer..
If $h=g^x \bmod p$ and we're working in the group $Z^*_p$, why can I not ...
2
votes
1answer
51 views
How to determine if $\{n \cdot g^a \mod P\}$ and $\{m \cdot g^a \mod P\}$ generate the same sets? (set size < $P-1$)
given some examples $k_{n_i},k_{m_i}$ out of each value set:
$k_{n_i} \in \{n \cdot g^a \mod P\, \forall a \in \mathbb{N}<P\}=G_m$
$k_{m_i} \in \{m \cdot g^a \mod P, \forall a \in \mathbb{N}<P\}...
-1
votes
1answer
74 views
Is there a fast way to solve $k = n \cdot g^a \mod P$? (get $a$ for unknown $n$)
Would a factor besides the normal discrete logarithm problem increase or decrease the solving time?
$k = n \cdot g^a \mod P$
with given $k,g,P$ and the knowledge $P= 2 \cdot N \cdot f+1$, while $...
0
votes
0answers
27 views
Is there any property of the product you can predict before using $n$-times generator $g$ $\mod P$? Can any $n$'th element have a certain property?
Given a value $v$ which is in same group as the generator $g$ modulo prime $P$. The group size is a prime $s$.
$v = g^a \mod P$
Only known values are $v,g,P,s$. Some (possible) computation of other ...
0
votes
1answer
32 views
Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$
Assuming you know the factorization of used prime $P-1$
$P-1 = s \cdot f_2\cdot f_3...f_i$
Now you want to find a member of a subgroup $\mathbb{Z}_s$.
This means any $x$ with
$x^s \equiv 1 \mod P $
...
7
votes
1answer
229 views
How safe is a prime with $P=2 \cdot Q \cdot R \cdot S \cdot t+1$ for discrete logarithm? How to enhance/compare?
To get some certain properties for my use case I need a prime $P$ which has the form:
$P=2\cdot Q \cdot R \cdot S \cdot t+1$
with $Q,R,S,t$ primes as well.
Why that form - Use case
Together with ...
6
votes
1answer
86 views
why a group used in cipher based on DLP must be Abelian group?
I can't understand it because $(g^x)^y=(g^y)^x$ in nonabelian group too.
thank you very much for read my question
-1
votes
1answer
45 views
Is there a way to determine the number of subgroups (with size $s$) while computing $A^b \bmod P$? Constructing a $P$ with $n$ times size $s$?
If you compute $A^b \bmod P$ for all $b$ the set of results $R$ depend at $A$ (and $P$).
$R = \{A^b \bmod P, \forall \space b \in \mathbb{N}\}$
In case $R$ contain all numbers from 1 to $P-1$, it ...
4
votes
1answer
135 views
Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?
The Schnorr identification protocol is widely recognized as the simplest ZKPoK of the discrete logarithm (more clearly, Honest-Verifier ZKPoK).
However, I can't figure out why this simple protocol, ...
1
vote
1answer
52 views
Does a different exponent and base but same key help to resolve discrete logarithm?
E.g.:
$k = N^a \mod P$
The attacker knows the prime $P$ and $N$, which is also a prime and
(1.) prime root of $P$ or
(2.) has a cycle size of $s$, so $1 = N^s \mod P$, (and for $\forall s'<s$, $...
1
vote
1answer
89 views
How to compute a discrete logarithm modulo a power of 2?
This question is related to this one. Specifically, assume that we have $p$ = 2048, $m$ = 13 and $c$ = 357.
In this case, $c\ =m^e\ \bmod \ p$.
I know that many algorithms rely on the difficulty of ...
2
votes
1answer
70 views
Discrete logarithm with exponentiation oracle
Suppose $(n, d)$ is an RSA private keypair. We know the public key only (wlog suppose it's $(n, 2^{16}+1)$ and we are given oracle $E$, decryption oracle for $(n, d)$. Is there any efficient algorithm ...
2
votes
2answers
281 views
Does classifying an integer as a discrete log require it be part of a multiplicative group?
This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.
The confusion is whether any integer can be considered a discrete log or ...
11
votes
3answers
3k views
Why was the term “discrete” used in discrete logarithm?
Is there anything especially "discrete" about a discrete logarithm? This is not a question of what is a discrete logarithm or why the discrete logarithm problem is an "intractable problem" given ...
2
votes
2answers
103 views
Compute discrete logarithm mod $n=p \times q$ knowing factorisation
I read in a document that for a given $n = p\times q$ ($p$, $q$ primes), if you know $p$ and $q$ then you can easily solve the discrete logarithm problem, i.e. for fixed $a,b$, you can find $x$ such ...
2
votes
0answers
38 views
Selection of parameters for Massey-Omura Cryptosystem
I have 4 questions about Massey-Omura Cryptosystem.
Are there standards that define these parameters?
How to choose a group order?
What is better to take the function f?
What is the recommended key ...
1
vote
1answer
70 views
Understanding Baby-Step Giant-Step Algorithm and discrete logarithm
Studying the Baby-Step/Giant-Step Algorithm, I have some questions:
In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\...
1
vote
0answers
61 views
Breaking the discrete logarithm problem in subgroups of $G$
I need to find the discrete logarithm of 20 modulo 71 where the generator of the group is 7. I need to break the group $|G|=2 \times 5 \times 7$ in subgroups $|G_1|=2, |G_2|=5, |G_3|=7$. I am new to ...
1
vote
2answers
48 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 ...
2
votes
1answer
147 views
find $a$ and $k$ for a given el gamal cryptosystem
I am given this question:
Suppose Alice is using the ElGamal Signature scheme with parameters
$p = 31847$, $\alpha = 5$, and $\beta = 25703$
Assuming that we have received signed messages
$(x_1,(\...
1
vote
0answers
69 views
Prove that two commitments are commitments to the same value
Let $x$ be the secret value, $(n,a,b,c)$ a public key, $(n_C, g, h)$ the commitment public key. Furthermore let $r, r_C$ be two random numbers.
Define $C = g^x h^{r_C} \bmod n_C$, $C_x = a^x b^r \...
0
votes
1answer
70 views
How should one refer to the smallest remainders generated by a modulus within DH or DLP?
It's my understanding that the integer base and exponents chosen to create the initial public keys in DH are from the remainders of a modulus.
For example, if the value of the modulus is $N=11$, a ...
4
votes
1answer
125 views
Digital Signature Algorithm (DSA) with medium fields
I understand it when we have to solve Discrete Logarithm Problem $a^x\equiv b\pmod p$, where $a$ and $b$ are given integers and we have to find secret integer $x$ that makes the equation true for some ...
-1
votes
2answers
321 views
Can Shamir’s Trick crack the cryptographic strength of ECDSA?
Recently stumbled upon a discussion in the forum
What is Shamir’s Trick used for?
Are there any such examples?
3
votes
1answer
92 views
In NIST modulus and key size recommendations is `group` equivalent to modulus and `key` equivalent to exponent?
Looking at the following NIST recommendations for a discrete logarithm, for 2016-2030 and beyond they list 3072-bit number for the group and 256-bit for the ...
3
votes
1answer
253 views
Diffie-Hellman private key recover with non-prime modulus
Say we have a classic Diffie-Hellman key exchange. We have the following parameters of a public key:
p,g,y
Where $p$ is the modulus, $g$ is the base, $y$ is the ...
-2
votes
1answer
52 views
Elliptical Curve Actual Encryption
Im havirng a had time understanding ECC. For example, I have the equation below:
...
2
votes
0answers
62 views
Distributed key generation (for discrete-log based cryptosystems) with fake shares
Under the definition of Gennaro et al (link), a DKG protocol needs to satisfy “correctness” and “secrecy”. Correctness is divided into three sub-properties:
C1. All subsets of $t+1$ shares provided ...
0
votes
0answers
103 views
Using division polynomials to prove that EC discrete log is even
This question is related to the other question I recently asked. I'm trying to figure out if it is possible to use division polynomials to prove that knowing $A = a \cdot G$ we can prove that $a$ is ...
-1
votes
1answer
199 views
How does Diffie Hellman protocol work in Bitcoin Blockchain Transactions?
Greetings to all! Please explain how the Diffie-Hellman protocol works in Bitcoin?
That is, in Blockchain Transactions, there is also a total number of "K" recipient and sender?
"K" the recipient and ...
0
votes
0answers
15 views
Are compressed pairings used for Barreto-Naehrig curves in practice?
In 2009 Galbraith and Lin wrote the article "Computing Pairings Using x-Coordinates Only" https://link.springer.com/article/10.1007/s10623-008-9233-3, where they proposed to compute pairings on ...
2
votes
2answers
100 views
Random Self-reducibility in Discrete Log
I understand what Random Self-reducibility means and how it is used in the Discrete Log. What is not clear is
how does it show that DL is hard in the average case.
The probability of success of an ...
0
votes
0answers
40 views
Discrete Logarithm within DH exchange - finding out A and B secret number [duplicate]
How would i find out Alices or Bobs private number from the details exchanged in public.
prime - g = 7
primitive root - n = 3
Alice - A = 3
Bob - B = 4
The details visible in public exchange are:
...
1
vote
1answer
79 views
Continuous logarithms in cryptography
Cryptographic procedures seem to almost exclusively use discrete logarithms rather than continuous logarithms. Hence, I assume there are good and sound reasons for this.
In essence, answers provided ...
3
votes
1answer
165 views
Why is Diffie-Hellman Insecure If Order of the Generator Has Only Small Prime Factors?
In this post from security SE, Tom Leek mentioned that, for Diffie-Hellman to be secure order of the group $g$ should have a prime factor at least $2k$ bits long, where $k$ is the security parameter.
...
2
votes
2answers
208 views
What prevents the successful use of the Giant-step/Baby-step algorithm solving a discrete log problem implemented with modulo arithmetic?
Does the size of base, exponent, and modulus thwart the Giant-step/Baby-step algorithm in solving DLP using modular arithmetic or is it the use of a property of a particular prime as the modulus, or ...
2
votes
0answers
54 views
Proving key equivalence across different elliptic curves
We can use the technique described in this answer to prove key equivalence across two elliptic curves of different order. I'm wondering if modifying the technique as described below would compromise ...
0
votes
1answer
57 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$
