All Questions
Tagged with cryptography discrete-logarithms
49
questions
0
votes
0
answers
108
views
Assuming secp256k1 curve and given fixed (but random) $h$ and $d$ values, is it possible to calculate a $k$ such that $h\equiv(k\,G)_X\,(k-d)\pmod n$?
For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that:
$$h\equiv(k\,G)_X\,(k-d)\pmod n$$
where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) ...
0
votes
1
answer
281
views
Discrete Logarithm Problem as Period finding of a function
The discrete logarithm problem (DLP) : Find $b$ knowing $s,a$ and $p$ such that $$b=a^s\mod p$$
where $p$ is a prime number and $a$ is a generator of the group defined by $p$.
It is stated that the ...
- 7,674
0
votes
0
answers
56
views
Discrete Logarithm Problem used in currently used cryptosystems
Is it incorrect to say "Many important algorithms in public-key cryptosystems used at present have their security based on the assumption that the Discrete Logarithm Problem (DLP) over some ...
- 201
1
vote
0
answers
25
views
In $Z_{p^e}^*$, why is $p$-adic presentation of $x = \sum_{i=0}^{e-1} x_i p^{i}$, why is $g^{p_e(x_1 + \dots + x_{e_1} p^{e-2})} = 1$
During studying for a cryptography course, I encountered the following formula in a section about calculating discrete logarithm in a group $\mathbb{Z}_n^*$. Assume that $n= p^e$ for some prime. Let $...
1
vote
2
answers
149
views
Determine dlog in quotient rings of polynomial rings
Question:
Determine $\operatorname{dlog}_x (x^2 + 1)$ in $\Bbb Z_5[x]/\langle\,x^3 + x + 1\,\rangle$
So I know the elements of $F = \Bbb Z_5[x]/\langle\,x^3 + x + 1\,\rangle $ are of the form $ax^2 +...
- 1,874
1
vote
1
answer
147
views
Definition of finite field with fixed characteristic
In this article Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic the term finite fields of fixed characteristic is not defined and I couldn't find it on the ...
- 1,637
1
vote
1
answer
457
views
What is discrete logarithm?
Can someone help me out with explaining what discrete logarithm is in layman's term. Here's the Wikipedia article: https://en.wikipedia.org/wiki/Discrete_logarithm
- 27
0
votes
1
answer
131
views
Hardness to solve DL-Problem
I was wondering why some groups provide more security to cryptosystems relying on DL-Problem.
It is not clear to me wether it is just due to the known attacks or if there are some other reasons. So ...
1
vote
1
answer
145
views
When will the random bit sequence start to repeat in pseudo random number generator
Let's say we have the Blum-Micali pseudorandom number generator.
from wikipedia:
Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ ...
- 113
6
votes
2
answers
188
views
Can irreversibility of trapdoor functions generally not be proved?
The German Wikipedia article on asymmetric cryptography states that asymmetric cryptography is always based on assumptions which can not be proven:
Die Sicherheit aller asymmetrischen Kryptosysteme ...
- 163
0
votes
1
answer
209
views
Discrete Logarithm is Homomorphic
Recall that $l_g(h) ($mod$ p)$ is the discrete log to base $g$ mod $p$, that is, $g^{l_g(h)} \equiv h($mod$ p)$.
Let $p$ be prime, and $g$ a primitive root $($mod$ p)$. Show that: $l_g(h_1h_2)$ = $...
- 57
0
votes
1
answer
87
views
DLP - formulae for length of $G_{list}$ in terms of prime $p$ for $g=2,3,...$
The DLP is defined as:
$$g^x \cong h \pmod{p}$$
Using $g=2$ and $g=3$ I've found that the size of list of unique $h$ values (I call the $G_{list}$) for primes from $p=3$ upto $p=19$ are of the form ...
- 788
3
votes
1
answer
526
views
Solving DLP using the method of Pohlig-Hellman
I want to solve the DLP for $p=29$, $a=2$ and $b=5$ using the method of Pohlig-Hellman.
$$$$
I have done the following:
We have that $p-1=28=2^2\cdot 7$.
We get \begin{align*}&x_2= x\pmod {...
- 14k
1
vote
1
answer
4k
views
Solving DLP by Baby Step, Giant Step
I want to solve the DLP $6\equiv 2^x\pmod {101}$ using Baby Step, Giant Step.
$$$$
I have done the following:
We have that $n=\phi (101)=100$, since $101$ is prime.
$m=\lceil \sqrt{100}\rceil=...
- 14k
3
votes
2
answers
240
views
Discrete Log solve using Index-Calculus producing incorrect 'r' value.
I have a discrete log that I need to solve to aid in a Cryptography problem, that deals with both programming and mathematics, so I was unsure where to post this problem, feel free to move me if ...
