Skip to main content
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 ...
poncho's user avatar
  • 148k
6 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 ...
CurveEnthusiast's user avatar
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'...
fgrieu's user avatar
  • 142k
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,\...
Shan Chen's user avatar
  • 2,725
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 ...
CurveEnthusiast's user avatar
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 ...
CurveEnthusiast's user avatar
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 ...
poncho's user avatar
  • 148k
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 ...
fgrieu's user avatar
  • 142k
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 ...
puzzlepalace's user avatar
  • 4,042
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:...
abacabadabacaba's user avatar
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 ...
meshcollider's user avatar
  • 1,583
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 ...
CryptoPerson's user avatar
2 votes

Discrete log problem - does luck exist?

Examples that use very small parameter and key sizes are mainly provided to let students understand the system. Of course they do provide the same security as expected for the algorithm. The thing is ...
Maarten Bodewes's user avatar
  • 93.2k
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 ...
kodlu's user avatar
  • 22.7k
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 ...
SSA's user avatar
  • 640
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 ...
kelalaka's user avatar
  • 48.9k
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$ ...
kodlu's user avatar
  • 22.7k
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 ...
poncho's user avatar
  • 148k

Only top scored, non community-wiki answers of a minimum length are eligible