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.
2
votes
2answers
235 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
69 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
44 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
69 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
25 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
28 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
173 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
0answers
60 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
43 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
109 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
49 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
84 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
68 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
278 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
90 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
36 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
65 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
60 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
123 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
59 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
63 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
122 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
226 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
84 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
224 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
51 views
Elliptical Curve Actual Encryption
Im havirng a had time understanding ECC. For example, I have the equation below:
...
2
votes
0answers
61 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
95 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
152 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
13 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
80 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
74 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
151 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
174 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
51 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
50 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$
0
votes
0answers
38 views
Algorithm to compute DLOG for elliptic curve $E(F_p)$ with order p
I was reading about elliptic curves in this pdf. Page 55 of the pdf states that if number of points on elliptic curve #$E(F_p) = p$, then there exists a p-adic logarithmic map that homomorphically ...
2
votes
1answer
129 views
Solving discrete log in partially known group
Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,...
0
votes
4answers
99 views
Diffie-Hellman key exchange: Why is $(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
In a Diffie-Hellman key exchange, with a generator $g$ and a modulo $n$, and two keys $k_1$ and $k_2$, why is
$(g^{k_1} \bmod n )^{k_2} \bmod n \equiv (g^{k_2} \mod n)^{k_1} \bmod n$
4
votes
0answers
86 views
Use of randomness in an Elgamal like encryption
Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
1
vote
0answers
80 views
Security of BLS under additional information on the secret key
Question A
Is the BLS signature scheme still secure if an adversary in addition to the public key $ pk = g_2 \, sk \in \mathbb{G}_2 $ also obtains additional information on the private key $ sk $, ...
-1
votes
1answer
79 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 ...
2
votes
1answer
85 views
Pedersen commitments, what happens if I choose $H$ such that $H = a\times G$?
For Pedersen commitments of the form $C = x\times G + r\times H$, what is the worst thing I can do if I already know $H$ such that $H = a\times G$ ?
For standard curves, there are specifications for ...
4
votes
1answer
178 views
Is there a group where CDH is easy but DLog is hard?
The question is quite simple:
Is there a group where solving the CDH problem can be shown to be easy but solving the discrete logarithm problem is assumed to be hard?
Refresher on the problems:
CDH:...
0
votes
1answer
159 views
What math should I learn to get in depth with Elliptic Curve Cryptography research?
My background is computer scientist. I have done applied cryptography research for a while. Currently, I'm working on Elliptic curve cryptography.
To understand the idea and how to use Elliptic curve ...
0
votes
0answers
49 views
Discrete logarithm for a range
I previously asked this question on the math site but didn't get a response.
Are there any efficient algorithms for solving the following problem?
Let $b\leq m<n$, what is the smallest value for $...
