Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
13 votes
Accepted

What is largest prime factor in Diffie-Hellman?

How to determine if the largest prime factor of $p-1$ is in fact large? Most often, it is not determined from $p$ that $p-1$ has a large prime factor. Rather, a large prime factor $q$ is chosen, ...
fgrieu's user avatar
  • 142k
11 votes
Accepted

Is it insecure to sign the value 0 with ElGamal?

Is it insecure to sign the plaintext 0 with ElGamal signature algorithm? It is insecure to verify the plaintext that hashes to 0 with the ElGamal signature algorithm, because anyone can generate such ...
poncho's user avatar
  • 148k
8 votes

Recovering private key from Secp256k1 signatures

In ECDSA, each signature has its own ephemeral key $k$. If $k$ is generated properly, then no amount of signatures will help you recover the private key. "Proper" generation here means ...
Thomas Pornin's user avatar
8 votes

primitive root of a very big prime number (Elgamal DS)

When considering a big prime $p$, the group of invertible integers modulo $p$ are all integers from $1$ to $p-1$. There are $p-1$ of them. The order of an integer $g$ modulo $p$ is the smallest ...
Thomas Pornin's user avatar
7 votes
Accepted

RSA Digital Signature vs Elgamal Digital Signature

TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot ...
SEJPM's user avatar
  • 46.1k
7 votes

What is largest prime factor in Diffie-Hellman?

My question is the following: how to determine if the largest prime factor of $p-1$ is in fact large? Yes, showing that $p-1$ is not smooth (terminology for "has a large prime factor") for random ...
poncho's user avatar
  • 148k
6 votes

Is it possible to combine digital signature to provide message addition?

No, in textbook RSA signature with $\operatorname{Sig}(x)=x^d\bmod N$, there is no method to deduce $\operatorname{Sig}(15)$ from $\operatorname{Sig}(5)$ and $\operatorname{Sig}(10)$. It is possible ...
fgrieu's user avatar
  • 142k
5 votes
Accepted

Why is the El Gamal commitment scheme information theoretically binding?

How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r'$ that with $g^r = g^{r'}$, or am I overseeing something? Yes, you're probably thinking the ...
tylo's user avatar
  • 12.7k
4 votes

How does hash function in Elgamal signature scheme prevent existential forgery attack?

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack ...
Raymond Smith's user avatar
4 votes
Accepted

Attacks on schemes based on elliptic curves when the transmitted points are not on the curve

In this state we have well known attack that is called invalid-curve attack. Let $E:y^2=x^3+ax+b$ and $E':y^2=x^3+ax+b'$ be two elliptic curves with reduced Weierstrass form. $E'$ is called an ...
Meysam Ghahramani's user avatar
4 votes
Accepted

What can I do if I get private key of signing algorithm in Digital signiture

When talking about digital signatures, the private key is what proves the authenticity of the signature, precisely because it is private. The use case proceeds like this: I choose a private and ...
Tim's user avatar
  • 186
4 votes

Recovering private key from Secp256k1 signatures

So, let me recall a few details about ECDSA: An ECDSA signature is a pair of integers $(r,s)$. In order to generate a signature for a given message $m$, a given hash function $H$, curve parameters $(\...
Lery's user avatar
  • 7,699
4 votes
Accepted

Signature Scheme with proof of data possession

If the document is short enough, then its ISO/IEC 9796-2 signature proves data possession, for a simple reason: in so-called total recovery mode, signature verification recovers the document as a ...
fgrieu's user avatar
  • 142k
4 votes
Accepted

Given 2 Digital Signature generated by $S=D\times k^r$ how do you solve for $k$?

Given that $\gcd(r_1, r_2) = 1$, using the extended Euclidean algorithm we can find $a,b$ such that $a \cdot r_1 + b \cdot r_2 = 1$. If $D_1$ and $D_2$ are invertible $\mod N$ (which is quite likely; ...
knbk's user avatar
  • 865
4 votes
Accepted

Is K=1 a valid random integer in ElGamal signature?

Why $K=1$ is not excluded? You can also ask why $K=2$ is not excluded. It always possible to calculate $g^2$ and by keeping $(g^2,2)$ in a lookup table, you can also recover the secret key if you see $...
Changyu Dong's user avatar
  • 4,178
4 votes

Using ElGamal instead of RSA in FDH

This had been reiterated many times before in this community. Digital signature is NOT encrypt with private key. RSA is the only bijection we know where both the public and the private operations are ...
DannyNiu's user avatar
  • 9,409
3 votes

Base Point on elliptic curve

The "base point" is conventional. When using El Gamal or similar algorithms with an elliptic curve, you want to work inside a group with a prime order (either the complete curve has a prime order, or ...
Thomas Pornin's user avatar
3 votes
Accepted

How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?

In the question you said that $a^x\equiv b\ (mod\ p)$ and $P,Q\in E(\mathbb{F}_p)$. In general case, the number of elliptic curve points $\#E(\mathbb{F}_p)$ is not equal to $p$. So these two groups ...
Meysam Ghahramani's user avatar
3 votes
Accepted

El Gamal existential forgery using Pointcheval–Stern signature algorithm

The scheme you consider is the original ElGamal signature. This scheme is known to be existentially forgeable. By definition, a valid original ElGamal signature on a message $m \in \{1, \dots, p-1\...
user94293's user avatar
  • 1,779
3 votes

Role of Fermat's little theorem in the proof of correctness of ElGamal signature

For $c\ne0$, the definition of $a\equiv b\pmod c$ is: $\exists d\in\mathbb Z$ such that $a=b+cd$. Applying that definition to $H(m)\equiv xr+sk\pmod{p-1}$, we have that $\exists d\in\mathbb Z$ such ...
fgrieu's user avatar
  • 142k
3 votes
Accepted

Using ElGamal instead of RSA in FDH

In order to try what's attempted, we'd have to define $H$ with output on the set of all ElGamal ciphertexts. This is possible, and I assume this in the next paragraph. Contrary to textbook RSA, ...
fgrieu's user avatar
  • 142k
2 votes

ElGamal Signatures

I wonder, is there any real-world applications of ElGamal signatures and encryption? Rarely. ElGamal encryption is used very rarely, with GPG being nearly the only common tool, not library, to ...
SEJPM's user avatar
  • 46.1k
2 votes
Accepted

What is wrong with my Elgamal signature example?

Main problem is: in the question, a generator $g$ of order $q$ is used in the computation of [2.]. Thus if that computation and verification is in $\mathbb Z_{23}^*$ as in the attempted computations, ...
fgrieu's user avatar
  • 142k
2 votes

Length of ElGamal signature compared to RSA signature

Mistakes happen. The author's scheme adds a signature about twice as large as $p$, when RSA signature (of the textbook variety of the reference) adds a signature about as large as $n$. It is clearly ...
fgrieu's user avatar
  • 142k
2 votes
Accepted

Any scenario for using ElGamal-SIGNATURE over RSA?

ElGamal signature works as follows. Define a large prime $p = 2qs + 1$ where $q$ is a prime. Let $g$ be an element of order $q$ and a hash function $H\colon \{0,1\}^* \to \mathbb{Z}_q$. The public ...
user94293's user avatar
  • 1,779
2 votes
Accepted

Does ElGamal authentication exist?

You can turn any public-key encryption or signature system into an authentication protocol, and that includes both ElGamal encryption and the ElGamal signature scheme. Protocols for this can be found ...
otus's user avatar
  • 32.1k
2 votes

What can I do if I get private key of signing algorithm in Digital signiture

"what is use of encryption with private key and decryption with public key" The sender can sign a message with their private key (not encrypt it). This creates a signature, which is a blob with the ...
AndyM's user avatar
  • 21
2 votes
Accepted

Whats wrong with my El Gamal signature example

In general case, $k^{-1}$ is equal to $x$ such that $x \cdot k=1$. In your question, to computing $11^{-1}$, you must find $x$ such that $x\cdot11=1 \pmod {8368}$. You can compute $x$ by using the ...
Meysam Ghahramani's user avatar
2 votes

How to compute ElGamal decryption by hand

We're not trying to compute $3^{-5}\ast 2$, but instead we're trying to compute $3^{-5}\ast 2\mod p$ for some prime $p$. This is notation for $(3^{-1})^5\ast 2\mod p$, so if we can compute what $3^{-1}...
Mark Schultz-Wu's user avatar
  • 13.3k
1 vote

Find private key from knowing random exponents are an arithmetic series

We don't know if $s_1r_2−s_2r_1$ is coprime to $p−1$ so we can't immediately get $u$, but is it true that it would be coprime? I don't believe coprimality is guarranteed, however we don't need it. ...
poncho's user avatar
  • 148k

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