27

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid ...


13

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, then it is chosen a prime $p$ of the form $p=2\,q\,r+1$ for some $r\ge1$, which insures that $p-1$ has large prime factor $q$. Sometime, we want $r=1$, in which ...


8

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 integer $k > 0$ such that $g^k = 1 \pmod p$. Group theory states that the powers of an element $g$, i.e. $1$, $g$, $g^2$... are collectively a subgroup of the ...


7

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 of lobby work. The main technical advantage of RSA is speed. With RSA you only need to do a small-exponent exponentation to verify a signature, where as with ...


7

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 either random uniform selection in the proper range, or an appropriate derandomization process such as the one described in RFC 6979. If the very same $k$ value is used in ...


7

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 primes $p$ is typically difficult, and so that's not what we do. Instead, we usually do one of these two things: Search for a large prime $p$ such that $(p-1)/2$...


6

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 to deduce $\operatorname{Sig}(50)$, by using the general fact that in textbook RSA signature, if $x$ and $y$ are positive integers (with $xy$ below the limit ...


5

The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to the Pohlig-Hellman algorithm. If you are not familiar with the Pohlig-Hellman algorithm, you can peruse for example Section 2.9 of the book by Hoffstein, Pipher ...


4

It seems that you mix things up. ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function. Given the type of forgery in your question that works, you compute your $m$...


4

As an alternative solution to the correct answer that Barack has posted, if you have $p=7 \bmod 8$, then the selection $g=2$ works just fine. In this case, $g=2$ is a quadratic residue (and hence has order $(p-1)/2$). In addition, you can show that if you can decrypt ElGamal messages with $g=2$, then you can decrypt ElGamal messages with any $g$; hence we ...


4

If $q$ is prime (which is a common additional constraint) then the possible orders for a random $F_p$ between $2$ and $p-2$ inclusive is either $q$ or $2q$ so you can avoid having to check the order by picking one at random, squaring it and using the result.


4

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 invalid curve relative to $E$. Since formulae for adding and doubling points on $E$ does not involve coefficient $b$ thus addition law for $E$ and $E'$ is same. In ...


4

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 algorithm. The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything. Hashing the ...


4

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 public key pair. Because I chose it, only I know both keys. I then send a message and sign it by using my private key, typically by encrypting a digest, hash, or ...


4

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; they only have to be coprime to the two large primes that make up $N$), we can compute $$k^{r_1} = S_1 \cdot {D_1}^{-1}$$ $$k^{r_2} = S_2 \cdot {D_2}^{-1}$$ ...


4

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 $(\mathcal{C}, G, n)$ for $\mathcal{C}$ a curve, $G$ a base point of prime order $n$ of $\mathcal{C}$, a private key integer $d$ and a public key point $Q = d\...


4

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 $S_1 = g^2$, in which case $K$ happen to be 2. So as $K =3$, $K= 4$ and so on so forth. As you can see, 1 is not that special. The reason why they are not ...


3

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\}$ is a pair $(r,s)$ satisfying $g^m \equiv y^r \cdot r^s \pmod p$. With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$ for random integers $...


3

With your proposed modification of the ElGamal signature scheme you can produce forgeries for arbitrary (hashed) messages $m$. By looking at the verification equation $$g^m = yr^s$$ you just have to set $r$ to $r=(g^my^{-1})^{s^{-1}}$ (just by rearranging the verification equation) which you can do for any $s$ from $\mathbb{Z}_{p-1}^*$, i.e., every $s$ ...


3

Basically because of Fermat's little theorem: if $a$ is not divisible by $p$ then $a^{p-1} = 1$ $mod$ $p$. A part of the expression for $\delta$ appears as a power of $a$ in the ElGamal signature verification equation, which "happens" to work because it is reduced modulo $p-1$ so Fermat's little theorem applies.


3

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 are not isomorphic and your question is wrong. If $\#E(\mathbb{F}_p)=p$ the curve is called anomalous and we can find the map $\psi : E(\mathbb{F}_p) \to \...


3

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 byproduct. ISO/IEC 9796-2 is an RSA or Rabin signature scheme, also requiring a hash. Depending on options, the "recoverable" message (that is, embedded ...


2

I assume that the deadline for the homework is passed, so I will provide an answer: Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$. Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to: choosing $k\in Z_p^*$ $r\equiv g^k \pmod p$ $s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to $m\equiv ...


2

It depends. It depends on a lot of things. For example a generator of 2 is great for encryption, but makes for awful signatures. If you use a generator of 2, then no. Your signatures will get broken. Then the encryption will. Elgamal signatures are pretty controversial. They're tetchy to get right (see above) and there are many things you can get wrong. ...


2

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable. Let $p = 2p_1 + 1$ where both $...


2

There seem to be no standardized ElGamal test vectors available in the public domain. However, there are some ElGamal test vectors generated with libgcrypt 1.5.0 available in this fork of the pycrypto project.


2

In ElGamal Signature Scheme we have: $$\beta=\alpha^a \bmod p$$ The values $p,\alpha$ and $\beta$ are public key, and $a$ is private key. $$\operatorname{sig_k}(x,k)=(\gamma , \delta)$$ where $\gamma = \alpha^k \bmod p $ and $\delta = (x-a\gamma)k^{-1} \bmod {p-1}$.


2

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 that $H(m)=xr+sk+(p-1)d\;\text{ (equ. 1)}$. Fermat's little theorem is that for $p$ prime and $g\not\equiv0\pmod p$, it holds that $g^{p-1}\equiv1\pmod p\;\text{...


2

Thanks to fgrieu's comment above and the following quote from here (PDF): Theorem: Let $p$ be a prime and let $a$ be a number not divisible by $p$. Then if $$ r \equiv s \pmod {p − 1} $$ we have $$ a^r \equiv a^s \pmod p$$ In brief, when we work $\mod p$, exponents can be taken $\mod{p − 1}$. I (think i) understood, how the first (implicit) ...


2

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 historically support ElGamal due to patent restrictions with RSA. Other than that it sees little use due to RSA being better promoted, supported and standardized. ...


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