Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pohlig-hellman]

In cryptography, Pohlig-Hellman is a symmetric cipher. In number theory, the Pohlig–Hellman algorithm sometimes is a special-purpose algorithm for computing discrete logarithms in a multiplicative group whose order is a smooth integer. The cipher builds upon the number theory algorithm.

0
votes
0answers
51 views

Are the Baby-step/Giant-step, Pohlig–Hellman, Index Calculs, and NFS algorithms to compute a discrete log modulo n effective with a composite modulus?

I've read different posts about the effectiveness of Baby-step/Giant-step on computing DLP with a composite modulus. This one seems to indicate that Baby-step/Giant-step is for use with a prime ...
5
votes
0answers
54 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily. In some cases where the ...
2
votes
1answer
97 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,...
2
votes
1answer
101 views

Understanding the Pohlig-Hellman algorithm

The paper has the following relation: $$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$ where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation ...
0
votes
1answer
85 views

Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

The Commutative Cipher Setup Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime. Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) =...
3
votes
0answers
103 views

Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve ...
0
votes
1answer
46 views

Discrete logarithm problem - Pohlig Hellman $GF(2^p)$

I would like to ask how to modify Pohlig Hellman algorithm if I need to work with polynomials $GF(2^{60})$ I know how this algorithm works with numbers, but I am not able to imagine how to do some ...
6
votes
1answer
350 views

Can Pohlig-Hellman encryption be done over elliptic curves?

Following a bunch of questions on the topic of Pohlig-Hellman encryption. I was wondering if this could be trivially adapted to be done over elliptic curves just like we create EC-DH instead of DH. ...
1
vote
1answer
153 views

Implementing Pohlig-Hellman Exponentiation chiper

I need to use Pohlig-Hellman exponentiation cipher for reasons explained here. However, I can't seem to find an implementation of this cipher anywhere. It doesn't seem to be too difficult to implement ...
10
votes
1answer
268 views

Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
0
votes
1answer
35 views

Generalised DLPC

Been reading about Pohlig Hellman algo to solve DLP. But can't seem to get an example based on the following: So if modulus, n is composite (i.e. non-prime) and the base is NOT a generator of Zn. ...
3
votes
1answer
360 views

Discrete logarithm weak group

I'm looking for weak groups in discrete logarithm, that $x$ can be extracted from $Y$ in polynomial time where $Y \equiv g^x \pmod{p}$ . I thought one way is to produce a prime $p$ that $p-1$ is an ...
1
vote
1answer
550 views

Pohlig-Hellman algorithm

I'm trying to use the Pohlig-Hellman algorithm to solve for $x$ where $15^x=131 \bmod 337$. This is what I have so far: Prime factors of $p-1$: $336=2^4\cdot3\cdot7$ $q=2$: $x=2^0\cdot x_0+2^1\cdot ...
3
votes
1answer
831 views

Encryption and decryption example using the Pohlig-Hellman Exponentiation Cipher

Let $n=11, d=3, e=7$ and $M=3$. Encryption: ...
3
votes
1answer
196 views

RSA Duplicate-Signature Attack

I'm trying to duplicate an RSA signature, and am having trouble at the last couple of steps. I'll detail what I've tried. I used OpenSSL to generate some 128-bit RSA parameters. Here are my public ...
2
votes
1answer
487 views

Pollard's Lambda algorithm ecdlp with Pohlig Hellman

I'm trying to solve the ECDLP problem given an elliptic curve defined over a prime field. This prime is large (about 256 bits). I managed to factor the order of the curve, and most of the prime ...
3
votes
0answers
47 views

Security aspects of a splitted Pohlig-Hellman system

Given a Polig-Hellman (is that really the name for that?) system with $$C = M^k \bmod p$$ where $M$ is the message, $C$ is the ciphertext, $k$ is a (secret) key (any integer relatively prime to $p-1$...
-1
votes
1answer
77 views

Finding greatest integer m satisfying modular relation

I solved (c). I want to know (a) and (b) For (a), what i have done is that p-1=t2^s(t is odd) = 2^s (mod 2^m) And for m=1,2,...s, both sides are 0. So, m is s or more than s. For m= s+1, s+2,... what ...
2
votes
1answer
1k views

Pohlig-Hellman and Shanks algorithm on ECC

First, sorry for my english which is not my natural language and secondly, I hope I am posting on the right section. So let's explain my problem. I am trying to implement the Pohlig-Hellman ...
4
votes
1answer
126 views

Combining Hellman Pohlig with Sieve

Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes. Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find $z\bmod\phi(m)...
2
votes
1answer
123 views

Factors of the group order to secure against Pohlig-Hellman

I am looking into the security of Diffie-Hellman and the discrete log in general. To make sure an attacker can not use Pohlig-Hellman to solve the discrete log quickly we need to make sure that the ...
0
votes
2answers
358 views

Solve the congruence using Pohlig-Hellman algorithm

Use the Pohlig-Hellman algorithm to compute a solution to: $3^x\equiv 2 \pmod {65537}$ My attempt: $p-1 = 65537-1 = 65536= 2^{16}$ $x= 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$ For $x_0$: $2^{65536/...
3
votes
1answer
1k views

Discrete logarithm modulo a smooth number

I am solving the discrete logarithm problem modulo $N$. $N$ is a composite number, I found its factors — lots of small primes and two big primes ($> 2^{50}$). Does the factorization of $N$ somehow ...
1
vote
1answer
312 views

Pohlig-Hellman Algorithm: Adding up the solution via CRT

I have a question about the Pohlig-Hellman Algorithm for the discrete log problem. I understand the concept, but doing the exact calculations I get confused at one point; to illustrate, let's look at ...
1
vote
0answers
277 views

Pohlig-Hellman exponentiation block cipher

Let $G$ be a group of order $n$ and let $e,d$ be integers such that $ed\equiv 1 \pmod{n}$. Then the exponentiation maps $x \mapsto x^e$ and $y \mapsto y^d$ are inverse maps on $G$. These maps give us ...
2
votes
1answer
1k views

How to protect from Silver–Pohlig–Hellman algorithm

I read that Silver–Pohlig–Hellman algorithm solves the discrete logarithm with prime module $p$ in $O(\log^2(p))$ if $p-1$ is a smooth number. This seems pretty fatal for cryptography, since it is a ...
6
votes
1answer
1k views

Security of Pohlig-Hellman exponentation cipher?

I am looking into implementing Pohlig-Hellman exponentation cipher and I would like to know how secure that algorithm is? I am guessing it's security relates greatly to the prime number used in it. ...
3
votes
2answers
280 views

iterated discrete log problem

Consider the following problem: given $g_1 \ldots g_i,h_1 \ldots h_i \in G$, $\forall i$ find $x_i$ such that $g_i^{x_i}=h_i$ For $i=1$ this is the discrete log problem and is assumed to to have ...
5
votes
3answers
628 views

Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$? Obviously the proof must not be too long and it ...
4
votes
1answer
1k views

What's the main difference between Pohlig-Hellman and RSA?

Both Pohlig-Hellman and RSA perform encryption and decryption by exponentiation modulo some integer ($p$ prime for PH, $n$ composite for RSA). They both use a key $e$ as the exponent to encrypt a ...
8
votes
5answers
2k views

Software implementation of a commutative cipher?

I've got an application (detailed below) that calls for the use of a cipher that is commutative. I've been doing some googling & reading, and there are two algorithms that seem to get mentioned ...
7
votes
5answers
1k views

Applications of Group Ciphers

I've been reading a paper [1], and I've ran across something called a "Group Cipher", which is similar to homomorphic encryption, with an important difference. In homomorphic encryption we have an ...