Show that if someone discovers the value of $k$ used in the ElGamal signature scheme, then $a$ can also be determined if $gcd(r\text{,}p-1)$ is small.

Alice signs the hash of a message. Suppose her hash function satisfies $h(x)\equiv 2^x(\mathrm{m}\mathrm{o}\mathrm{d}101)$ and $1\le h(x)\le 100$ for all $x$. Suppose $m$ is a valid signed message from Alice. Give another message $m_1$ for which the same signature is also valid.

Alice says that she is willing to sign a petition to save koala bears. Alice’s signing algorithm uses a hash function that has an output of 60 bits (and she signs the hash of the document). Describe how Eve can trick Alice into signing a statement allowing Eve unlimited withdrawals from Alice’s bank account.

Alice uses RSA signatures (without a hash function).

1. Eve wants to produce Alice’s signature on the document $m=123456789$. Why is this difficult? Explain this by saying what difficult cryptographic problem must be solved. (Do not say that it’s because Eve does not know the decryption exponent $d$. Why isn’t there another way to produce the signature?)

2. Since part (a) is too hard for Eve, she decides to produce Alice’s valid RSA signature on a document so that the signature is $s=112090305$ (= Alice, when $A=01$, $L=12$, etc.). How does Eve find an appropriate message?

Nelson thinks he has a new version of the signature scheme. He chooses RSA parameters $n$, $e$, and $d$. He signs by computing $s\equiv m^d(\mathrm{m}\mathrm{o}\mathrm{d}n)$. The verification equation is $(s-m)(s+m)\stackrel{?}{=}{s}^2-m^2$.

1. Show that if Nelson correctly follows the signing procedure, or if he doesn’t, then the signature is declared valid.

2. Show that Eve can forge Nelson’s signature on any document $m$, even though she does not know $d$.

(The point of this exercise is that the verification equation is important. All Eve needs to do is satisfy the verification equation. She does not need to follow the prescribed procedure for producing the signature.)

Alice has a long message $m$. She breaks $m$ into blocks of 256 bits: $m=m_1||m_2||\cdots ||m_N$. She regards each block as a number between 0 and $2^{256}-1$, and she signs the sum $t=m_1+m_2+\cdots +m_N$. This means her signed message is $(m\text{,}\mathrm{sig}(t))$, where sig is the signing function. Is this a good idea? Why or why not?

Suppose that $(m\text{,}r\text{,}s)$ is a message signed with the ElGamal signature scheme. Choose $h$ with $gcd(h\text{,}p-1)=1$ and let $r_1\equiv r^h(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Let $s_1\equiv s{r}_1{h}^{-1}{r}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

1. Find a message $m_1$ for which $(m_1\text{,}{r}_1\text{,}{s}_1)$ is a valid signature.

2. This method allows Eve to forge a signature on the message $m_1$. Why is it unlikely that this causes problems?

Let $p=11$, $q=5$, $\alpha =3$, and $k=3$. Show that $({\alpha }^k(\mathrm{m}\mathrm{o}\mathrm{d}p))(\mathrm{m}\mathrm{o}\mathrm{d}q)\ne ({\alpha }^k(\mathrm{m}\mathrm{o}\mathrm{d}q))(\mathrm{m}\mathrm{o}\mathrm{d}p)$. This shows that the order of operations in the DSA is important.

There are many variations to the ElGamal digital signature scheme that can be obtained by altering the signing equation $s\equiv k^{-1}(m-ar)(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$. Here are some variations.

1. Consider the signing equation $s\equiv a^{-1}(m-kr)(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$. Show that the verification ${\alpha }^m\equiv ({\alpha }^a{)}^s{r}^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$ is a valid verification procedure.

2. Consider the signing equation $s\equiv am+kr(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$. Show that the verification ${\alpha }^s\equiv ({\alpha }^a{)}^m{r}^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$ is a valid verification procedure.

3. Consider the signing equation $s\equiv ar+km(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$. Show that the verification ${\alpha }^s=({\alpha }^a{)}^r{r}^m(\mathrm{m}\mathrm{o}\mathrm{d}p)$ is a valid verification procedure.

Consider the following variant of the ElGamal Signature Scheme: Alice chooses a large prime $p$, a primitive root $\alpha$, and a secret integer $a$. She computes $h\equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The numbers $p\text{,}\alpha \text{,}h$ are made public and $a$ is kept secret. If $m<p-1$, Alice signs $m$ as follows: She chooses a random integer $k$ and computes $r\equiv {\alpha }^k(\mathrm{m}\mathrm{o}\mathrm{d}p)$, with $0<r<p-1$, and $s\equiv am-kr(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$. The signed message is $(m\text{,}r\text{,}s)$. Bob verifies the signature by checking that ${\alpha }^s{r}^r\equiv h^m(\mathrm{m}\mathrm{o}\mathrm{d}p)$. If $m\ge p-1$, she breaks $m$ into blocks and signs each block.

1. Show that if Alice signs correctly then the verification congruence is satisfied.

2. Suppose Eve has a document $m_1$ and she wants to forge Alice’s signature on $m_1$. That is, she wants to find $r_1$ and $s_1$ such that $(m_1\text{,}{r}_1\text{,}{s}_1)$ is valid. Eve chooses $r_1=2015$ and tries to find a suitable $s_1$. Why will it probably be hard to find $s_1$?

3. Suppose Alice has a very long message $m$ and wants to decrease the size of the signature. How can she use a hash function to do this? Explicitly give the modifications of the above equations that must be done to accomplish this.

The ElGamal signature scheme presented is weak to a type of attack known as existential forgery. Here is the basic existential forgery attack. Choose $u\text{,}v$ such that $gcd(v\text{,}p-1)=1$. Compute $r\equiv {\beta }^v{\alpha }^u(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and $s\equiv -r{v}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

1. Prove the claim that the pair $(r\text{,}s)$ is a valid signature for the message $m=su(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$ (of course, it is likely that $m$ is not a meaningful message).

2. Suppose a hash function $h$ is used and the signature must be valid for $h(m)$ instead of for $m$ (so we need to have $h(m)=su$). Explain how this scheme protects against existential forgery. That is, explain why it is hard to produce a forged, signed message by this procedure.

Alice’s RSA public key is $(n\text{,}e)$ and her private key is $d$. Recall that a document with an RSA signature $(m\text{,}s)$ is valid if $m\equiv s^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$. Bob wants Alice to sign a document $m$ but he does not want Alice to read the document. Assume $m<n$. They do the following:

1. Bob chooses a random integer $k$ with $gcd(k\text{,}n)=1$. He computes $m_1\equiv k^{e}m(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

2. Alice signs $m_1$ by computing $s_1\equiv m_1^d(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

3. Bob divides $s_1$ by $k$ mod $n$ to obtain $s\equiv k^{-1}{s}_1(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

1. Show that $(m\text{,}s)$ is valid.

2. Why is it assumed that $gcd(k\text{,}n)=1$?

Alice wants to sign a document using the ElGamal signature scheme. Suppose her random number generator is broken, so she uses $k=a$ in the signature scheme. How will Eve notice this and how can Eve determine the values of $k$ and $a$ (and thus break the system)?

Suppose Alice signs contracts using a 30-bit hash function $h$ (and $h$ is known to everyone). If $m$ is the contract, then $(m\text{,}sig(h(m)))$ is the signed contract (where sig is some public signature function). Eve has a file of $2^{20}$ fraudulent contracts. She finds a file with $2^{20}$ contracts with valid signatures (by Alice) on them. Describe how Eve can accomplish her goal of putting Alice’s signature on at least one fraudulent document.

1. In several cryptographic protocols, one needs to choose a prime $p$ such that $q=(p-1)/2$ is also prime. One way to do this is to choose a prime $q$ at random and then test $2q+1$ for primality. Suppose $q$ is chosen to have approximately 300 decimal digits. Assume $2q+1$ is a random odd integer of 300 digits. (This is not quite accurate, since $2q+1$ cannot be congruent to 1 mod 3, for example. But the assumption is good enough for a rough estimate.) Show that the probability that $2q+1$ is prime is approximately $1/345$ (use the prime number theorem, as in Section 9.3). This means that with approximately 345 random choices for the prime $q$, you should be able to find a suitable prime $p$.

2. In a version of the Digital Signature Algorithm, Alice needs a 256-bit prime $q$ and a 2048-bit prime $p$ such that $q|p-1$. Suppose Alice chooses a random 256-bit prime $q$ and a random 1792-bit even number $k$ such that $qk+1$ has 2048 bits. Show that the probability that $qk+1$ is prime is approximately 1/710. This means that Alice can find a suitable $q$ and $p$ fairly quickly.

Consider the following variation of the ElGamal signature scheme. Alice chooses a large prime $p$ and a primitive root $\alpha$. She also chooses a function $f(x)$ that, given an integer $x$ with $0\le x<p$, returns an integer $f(x)$ with $0\le f(x)<p-1$. (For example, $f(x)=x^7-3x+2(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$ for $0\le x<p$ is one such function.) She chooses a secret integer $a$ and computes $\beta \equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The numbers $p\text{,}\alpha \text{,}\beta$ and the function $f(x)$ are made public.

Alice wants to sign a message $m$:

1. Alice chooses a random integer $k$ with $gcd(k\text{,}p-1)=1$.

2. She computes $r\equiv {\alpha }^k(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

3. She computes $s\equiv k^{-1}(m-f(r)a)(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$.

The signed message is $(m\text{,}r\text{,}s)$.

Bob verifies the signature as follows:

1. He computes $v_1\equiv {\beta }^{f(r)}{r}^s(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

2. He computes $v_2\equiv {\alpha }^m(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

3. If $v_1\equiv v_2(\mathrm{m}\mathrm{o}\mathrm{d}p)$, he declares the signature to be valid.

1. Show that if all procedures are followed correctly, then the verification equation is true.

2. Suppose Alice is lazy and chooses the constant function satisfying $f(x)=0$ for all $x$. Show that Eve can forge a valid signature on every message $m_1$ (for example, give a value of $k$ and of $r$ and $s$ that will give a valid signature for the message $m_1$).

Alice wants to sign a long message $m=m_1||m_2||\cdots ||m_L$ that she has broken into blocks $m_1\text{,}\dots \text{,}{m}_L$. She knows that signing each block $m_i$ individually is wasteful, so she computes $g(m)=m_1\oplus m_2\oplus \cdots \oplus m_L$ and signs $g(m)$. Her signed message is $(m\text{,}si{g}_A(g(m)))$. Suppose Eve has a message that Alice signed. How can Eve put Alice’s signature on fraudulent messages?

In some scenarios, it is necessary to have a digital document signed by multiple participants. For example, a contract issued by a company might need to be signed by both the Issuer and the Supervisor before it is valid. To accomplish this, a trusted entity chooses $n=pq$ to be the product of two large, distinct primes and chooses integers $k_1\text{,}{k}_2\text{,}{k}_3>1$ with $k_1{k}_2{k}_3\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}(p-1)(q-1))$. The pair $(n\text{,}{k}_1)$ is given to the Issuer, the pair $(n\text{,}{k}_2)$ is given to the Supervisor, and the pair $(n\text{,}{k}_3)$ is made public.

1. Under the assumption that RSA is hard to decrypt, why should it be difficult for someone who knows at most one of $k_1\text{,}{k}_2$ to produce $s$ such that $s^{k_3}\equiv m(\mathrm{m}\mathrm{o}\mathrm{d}n)$?

2. Devise a procedure where the Issuer signs the contract first and gives the signed contract to the Supervisor, who then signs it in such a way that anyone can verify that the document was signed by both the Issuer and the Supervisor. Use part (a) to show why the verification convinces someone that both parties signed the contract.