7
votes
Accepted
Discrete logarithm weak group
Is there any better algorithm ?
Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You ...
- 145k
5
votes
Accepted
Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp
The question's example asks finding the solutions $x$ of equation $a^x\equiv b\pmod p$ given $p$, $a$, $b$, with $p=8101$, $a=6$, $b=7531$. It's stated $a$ is a generator of $\mathbb Z_{8101}$, but it'...
- 138k
5
votes
32-bit or 16-bits elliptic curves
Here is an example curve with smooth order $E/\mathbb{F}_p:y^2=x^3+ax+b$, generated with Magma.
\begin{align*}
p &= 2^{31}-1 \\
a &= 1456400922 \\
b &= 2005615003 \\
n &= 2^5\cdot 3^7 ...
- 3,459
3
votes
Accepted
Understanding the Pohlig-Hellman algorithm
Note that $\alpha$ is a primitive element in $GF(p)$ and $\gamma_i$ is a generator of a subgroup $G_i\subseteq GF(p)$ with order $p_i$, i.e., $G_i=\{\alpha^{(p-1)/p_i},\alpha^{2(p-1)/p_i},\ldots,\...
- 2,695
3
votes
Accepted
Pohlig-Hellman and Shanks algorithm on ECC
Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment.
You are indeed right that the ...
- 3,459
3
votes
Combining Hellman Pohlig with Sieve
I'm not sure if I understand the question correctly, but let's try anyway.
By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete ...
- 3,459
3
votes
Accepted
RSA Duplicate-Signature Attack
You forgot step 4:
$m$ and $s$ should each be primitive roots mod $p$ and mod $q$
$m$ is not a primitive root mod $p$. We can easily deduce that (without the bother of actually performing ...
- 145k
3
votes
Accepted
Implementing the Pohlig-Hellman cipher
Choice of public modulus $p$
Using for $p$ a large safe prime (that is, a prime $p=2q+1$ with $q$ also prime) is the way to go for the Pohlig-Hellman cipher, because that
simplifies the choice of ...
- 138k
2
votes
Pohlig-Hellman algorithm
When solving for $x$ in the equation $g^x \equiv h \text{ mod } p$ the idea behind Pohlig Hellman is to solve discrete logs on group elements with smaller orders and then recombine those results to ...
- 4,012
2
votes
Accepted
Solving discrete log in partially known group
Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows:...
- 426
2
votes
Accepted
Why are there different versions of the Pohlig-Hellman attack?
Actually, the method using the Chinese Remainder Theorem is the more general version. The one representing $k_i$ as $z_0 + z_1p_i + z_2p_i^2 + ...$ is only useful in the situation that the group order ...
- 1,573
2
votes
Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp
The group we are considering is $\mathbb{Z}_p^\times$, so every operation in that group (that includes operations in subgroups of that group) follow the same rule, namely computation mod $p$.
When we ...
- 121
1
vote
Proof of Pohlig-Hellman Algorithm on Elliptic Curve
This is the case of the chinese remainder theorem (CRT) for the relatively prime moduli $m_i=p_i^{e_i}.$ They have decomposed the group order $p-1$ into $p-1=m=m_1 m_2 \cdots m_k.$
There are many ...
- 21.2k
1
vote
Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp
as we know that DLP is finding x in : ${y \equiv g^x (mod p)}$, we use pohlig-hellman when order of group G is B smooth, when B is relatively small. We assume that g is a generator.
In real cases when ...
- 630
1
vote
How to factorize the group order in Pohlig-Hellman algorithm
I will mostly talk about the Elliptic Curve since here the field size is around $2^{255}, 2^{448},2^{512}$ for secure curves. With Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ the number of points is ...
- 47.6k
1
vote
Discrete logarithm problem - Pohlig Hellman $GF(2^p)$
A field like $GF(2^n)$ is represented by the residue classes of polynomials modulo $f(x)$ where $f \in GF(2)[x]$ is an irreducible polynomial of degree $n$ with binary coefficients. There are $2^n$ ...
- 21.2k
1
vote
Generalised DLPC
So if modulus, n is composite (i.e. non-prime) and the base is NOT a generator of Zn.
Actually, if $n$ is has two distinct odd primes as factors, there will never be a generator; that is, there will ...
- 145k
Only top scored, non community-wiki answers of a minimum length are eligible