ElGamal is a public key encryption scheme with security based on the discrete logarithm problem.

learn more… | top users | synonyms

1
vote
1answer
52 views

ECC - ElGamal with Montgomery or Edwards type curves (curve25519, ed25519) - possible?

I know the usual way of using getting shared secrets for encryption with ECC is DH, however, this only works with two keypairs of exactly the same kind, for example two curve25519- or two ...
0
votes
1answer
51 views

how to represent message as an integer between $1$ and $n-1$ [closed]

I am trying to implement simple El-Gamal cryptosystem. And I can't understand how to represent message as an integer between $1$ and $n-1$. The only thing that comes to my mind is: if $n$ bit length ...
-1
votes
0answers
39 views

Encryption using elliptic curves

What is currently the best way to actually encrypt a message using elliptic curves? I'm looking for an algorithm like ElGamal, but more efficient, since ElGamal outputs a tuple of two points for every ...
-2
votes
0answers
33 views

Real life RSA/El Gamal examples

Can someone direct me to examples of El Gamal and RSA that would be similar to real life (i.e. large primes). I wrote a code for encryption and decryption, but I wanted to test it against some larger ...
-1
votes
1answer
26 views

El gamal correctness

I tried to find online for the correctness of El-Gamal, but I couldn't find any good resource that will teach me how to show the correctness of El-Gamal, could any body show me how is it done?
1
vote
1answer
47 views

Proving correctness of a decryption of a homomorphically summed ciphertext?

I would like to take some additively homomorphic cryptosystem - don't care much which one for now - and encrypt a series of numbers with it. I would then like to (in public) take these numbers, add ...
0
votes
0answers
40 views

How many characters per block in an El Gamal ECC cryptosystem?

While I look for how many characters that can be encrypted using the The elliptic curve ElGamal cryptosystem. of each block found for these lines. But I can not understand Actually in our case we ...
0
votes
0answers
54 views

How does chosen ciphertext attack on Elgamal work?

Can it be proven that attacker can obtain the full message if he knows some plain-ciphertext pairs?
1
vote
0answers
81 views

How represent message in Menezes–Vanstone elliptic curve cryptography

I ask about represent message in Menezes–Vanstone elliptic curve cryptography I now encrypt function as follow $C_1 = (M_1 * K_1) mod\ P$ $C_2=(M2 * k_2) mod\ P$ My question is about how much the ...
2
votes
1answer
64 views

Use of ElGamal encryption for signature generation

If RSA (textbook RSA that is) generates a digital signature by using the sender's private key, couldn't any cryptosystem (the only two that come to mind are RSA and ElGamal) capable of asymmetric ...
1
vote
2answers
102 views

How do RSA and ElGamal key sizes compare?

I have a rather silly question regarding the comparison of RSA with ElGamal over integers. If you want to compare their performance in the same level of security, does the modulus of both of them need ...
1
vote
1answer
49 views

What does OIW stand for

There seem to be many OID's that have been put in the ASN.1 tree that have the following ISO identified organization: OIW. One example is SHA-1 (ElGamal seems to be another): ...
3
votes
3answers
148 views

Why are we not using multiple ciphers per message?

I am aware of at least rsa, elgamal-encryption, and variations of elliptic-curves relying on different problems and that those problems are considered hard. However, if someone figures out a way to ...
2
votes
1answer
75 views

Prevent MITM attack while encrypting data by using ElGamal ECC?

I am using ElGamal ECC to encrypt my plain text data. I want to ensure that my data is safe from a Man-In-The-Middle attack. What methodology I can adopt to achieve this goal? How can we prevent a ...
0
votes
2answers
146 views

Homomorphic Encryption: how does the equality test on ciphertexts work?

Let's suppose we have a asymmetric crypto-system $H$ which is homomorphic with respect to some function $F$. Alice encrypts a message $m$ with her private key $e$ in the crypto-system $H$ and ...
0
votes
1answer
211 views

Known plaintext attack on ElGamal encryption

Assume that Alice uses Bob’s ElGamal public key ( = 2, Yb = 8) to send two messages $M = 17$ and $M' = 37$ using the same random integer $k = 9$. Eve intercepts the ciphertext and somehow she finds ...
2
votes
1answer
150 views

How to calculate complexity of ElGamal cryptosystem?

How to calculate time and space complexity of ElGamal encryption and decryption as there are two exponentiation operation during encryption and one during decryption? Here is my code for encryption: ...
1
vote
1answer
113 views

Use ElGamal to solve Diffie-Hellman problem

Say we are able to decrypt a Elgamal ciphertext $c$ using only the public key. Apparantly it is now possible to solve the Diffie-Hellman problem (given $g^a, g^b$ calculate $g^{ab}$). How? I know how ...
5
votes
1answer
111 views

Condensed ElGamal + AES

In normal ElGamal encryption, the encrypted message is a pair (gb, gabM) - that is, the actual "encryption" is simply multiplication by the shared secret ...
1
vote
1answer
51 views

How to prove NIZK proof of knowledge?

Assuming we have an El-Gamal pk tuple $(G,q,g,g^s)$. Someone, knows only the first three parameters. In round $i$, I send him $X_i=(g^s)^{t_i}$ (the $t_i$ values are chosen randomly for each round), ...
3
votes
1answer
154 views

What differences between Menezes–Vanstone ECC and ElGamal ECC?

After researching ECC encryption, I found that we can use ElGamal cryptosystem with elliptic curve and can we use Menezes-Vanstone cryptosystem with elliptic curve. What is the essential difference ...
3
votes
1answer
112 views

Multiplication-homomorphic schemes

I'm looking into multiplication-homomorphic schemes now and basically I see that there are 3 options: RSA, Boneh-Goh-Nissim and ElGamal. RSA was proved to be insecure unless message is randomly ...
1
vote
2answers
148 views

weaknesses in ElGamal with public key of small order

Suppose $p=29$, $\alpha = 2 \in F_p^*$ is a generator of $F_p^*$. Bob picks $d \in \{2,...,27\}$ such that $\beta = \alpha ^d=28 \pmod{29}$. He then sends his $(p,\alpha ,\beta)$ to Alice who herself ...
4
votes
2answers
160 views

How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for?

Imagine Alice wants to encrypt for Bob and post this encryption publicly, so that only Bob can decrypt but no one can other than Alice or Bob tell that the message was encrypted for Bob. The naive ...
0
votes
1answer
36 views

Is the private key static or variable key in the elgamal algorithm?

I read about elgamal algorithm it work like the follow steps Bashir chooses a large random prime p and a primitive root α modulo p. Bashir then chooses a random integer a with 2 ≤ a < p - 1 and ...
0
votes
2answers
160 views

Why is ElGamalEngine in bouncy castle restricting input data to be less than the length of the group parameter p?

I am currently using the ElGamalEngine of bouncy castle to implement exponential ElGamal for the purpose of making ElGamal additively homomorphic. To do this i raise the message to be encrypted to the ...
0
votes
2answers
102 views

Size of p in ElGamal cryptosystem?

In the ElGamal cryptosystem, I was wondering whether the $m$ (message) should be less than $p$ (large prime). Because on decryption, we are getting $m \bmod p$. For $m \bmod p$ to be equal to $m$, ...
1
vote
1answer
39 views

Undefined $E_y(1,r_{i,j,1})$ notation in cryptography paper, suspect ElGamal-like

I'm trying to understand a paper that uses the notation $E_y(1,r_{i,j,1})$ (full text available in link, used just once on Page #35, 6th page of pdf, Section 3.3, Step 1c) in the context of an ...
3
votes
1answer
78 views

In Pedersen Key Distribution, can the public key be persistent?

I am implementing a key distribution protocol described by Torben Pedersen in A Threshold Cryptosystem without a Trusted Party (EUROCRYPT'91). In the protocol, the $n$ parties distribute a public key ...
1
vote
0answers
99 views

El Gamal encryption scheme and symmetric encryption scheme

Consider the El Gamal encryption scheme, a symmetric encryption scheme (KG,E,D), and the following hybrid encryption scheme having an encryption algorithm that, on input a public key (G,q,g,h), where ...
-2
votes
1answer
120 views

Zero Knowledge Proof for Correctness of the product of additive ElGamal Ciphers [duplicate]

Suppose we use Additive ElGamal defined as follows: Let $(K,E,D)$ be a triple. The key-generator $K$ outputs the description of a finite multiplicative group $G$ of prime order $q$, with three ...
2
votes
1answer
439 views

Mapping of message onto elliptic curve and reverse it

I would like to perform a variant of Elliptic Curve ElGamal in java using the BouncyCastle libraries. I currently face the difficulty of mapping a message $m$ onto the elliptic curve $E_p$. I have so ...
1
vote
2answers
296 views

why inverse in diffie-hellman protocol will not give same value?

Security of diffie hellman protocol is $K=g^{ab}$.if sender want to calculate value of $b$(given $a$) he can do $g^{{{ab}^b}^{-1}}$(where K=$g^{ab}$) which will give $g^{a}$ as we are cancelling value ...
0
votes
0answers
46 views

Private Set Intersection Polynomial Computation [duplicate]

I am trying to implement the protocol mentioned in Section 3.4 of “Efficient Robust Private Set Intersection” in Java. In the Second Step, the Client computes a polynomial of degree $n$ over the ...
0
votes
0answers
60 views

Plaintext patterns leaked based on single bit

Assuming that Elgamal is used as an encryption cipher, where lets say $p$ is 2048bit prime. Is it possible for an attacker to figure out $x$, a secret key, if any part of 2048 bits ciphertext and ...
2
votes
1answer
147 views

ElGamal with elliptic curves I

It is very interesting to see @tylo's answer on ElGamal with elliptic curves. Instead of mapping the message to the elliptic curve point it just reduces an elliptic curve point to its $x$ coodrinate. ...
1
vote
0answers
46 views

ElGamal Homomorphic Encryption Formula Question [duplicate]

With Pubic Key $(G, q, g, h)$ where $G$ is a group, $q$ prime, $g$ a generator of $G$, Am I right in thinking that: $$\mathrm{Enc}(m;r) := (g^r, h^r \cdot g^m)$$
0
votes
1answer
90 views

Efficient Robust Private Set Intersection Questions

I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal. I am trying to run the full protocol mentioned in Section 3.4 on the following inputs: $p = 17$ (prime) $g ...
1
vote
1answer
354 views

Z*p Generator (Cyclic Group) in java

I am trying to implement ElGamal in java without using the in-built libraries. The problem occurs when I am trying to find the generators of the number(in this case 11). Everything works perfectly ...
0
votes
1answer
99 views

ElGamal encryption with private key [closed]

Does the encryption with a private key and decryption with a public key works in ElGamal likewise what is done when we use RSA for sender authentication?
1
vote
0answers
59 views

Efficient Robust Private Set Intersection Additive ElGamal [duplicate]

I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal. I am trying to run the full protocol mentioned in Section 3.4 on the following inputs: $p = 17$ (prime) $g ...
1
vote
1answer
53 views

when to do elgamal exponentiation computation

Recetly while studying about cryptographic primtives, I have come across below line in wiki : http://en.wikipedia.org/wiki/ElGamal_encryption Encryption under ElGamal requires two exponentiations; ...
3
votes
2answers
155 views

ElGamal in private set intersection: how to handle negative numbers?

I am trying to implement the Efficient Robust Private Set Intersection using Additive ElGamal. For this, from the client side, my inputs are $C = \{1, 2\}$. So, the polynomial is $(x-1)(x-2)$ which ...
5
votes
1answer
1k views

Advantages using Diffie-Hellman or Elgamal

For what kind of usage should we prefer using Diffie-Hellman in order to exchange keys instead of Elgamal, and most important why should we use one or the other? I do not see a clear difference ...
4
votes
1answer
245 views

EC ElGamal versus static+ephemeral ECDH

A client application needs to encrypt a UDP datagram for a server with known EC public key $P$. Performing a full ECDH key exchange would defeat the benefit of using UDP as a connectionless protocol. ...
1
vote
2answers
219 views

Attacks against El Gamal private key

El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know. What are some efficient and strong algorithms ...
2
votes
1answer
275 views

Difference between Pedersen commitment and commitment based on ElGamal

Does any of you know what is the difference between the Pedersen commitment and the commitment that uses the ElGamal encryption scheme? For the sake of completeness, I recall what both of them look ...
1
vote
1answer
136 views

Recovering the random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
1
vote
0answers
143 views

About Elliptic Curve ElGamal, 3 simple problems I have trouble with

In Elliptic Curve ElGamal, why are a=b=1 always legal for primes whose lengths are no shorter than 11(2) bits long? Is there any reason why the Point at Infinity can always be encoded as (0,0)? ...
0
votes
2answers
236 views

In Elgamal, the generator g is always quadratic non-residue modulo p where p is a safe prime and inverse of g can be also generator?

In Elgamal, the generator $g$ is always quadratic non-residue modulo $p$, where $p$ is a safe prime and the inverse of $g$ can also be generator? Can I prove it? I can't come up with it at all.