*This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week, we describe the key generation, signing and verification algorithms of*

**DSA**,**Schnorr**and**RSA**-**FDH**.

**1. DSA**

The

*Digital Signature Scheme (DSA)*, also known as the*Digital Signature Standard (DSS)*, was proposed by*the National Institute of Standards and Technology (NIST)*in 1991 [1]. Security of DSA is based on the difficult of computing discrete logarithms. But there is no known proof of its security under a standard assumption (like DL), even in the*.***random oracle model**

*Domain Parameter Generation*- Select a prime number $p$, where $2^{L-1}<p<2^L$ and $L$ is a multiple of 64 and $512 \leq L \leq 1024$.
- Select a prime divisor $q$ of $p-1$, where $2^{159}<q<2^{160}$.
- Compute a generator $g$ of the subgroup of order $q$: choose a random integer $r$, where $1<r<p-1$ such that $g=r^{(p-1)/q} \ mod \ p$ and $g \neq 1$.

*Key Generation*- Select a random integer $x$, where $0<x<q$.
- Compute $y = g^x \ mod \ p$.

Then the public key is $y$ and the private key is $x$.

**Signing**- Select a random integer $k$, where $0<k<q$.
- Compute $r = (g^k \ mod \ p)\ mod \ q$.
- Compute $s = (h(m)+x\cdot r)\cdot k^{-1}\ mod \ q$, where $h(m)$ is hash of $m$ using SHA-1

**Verification**- Compute $u_1 = h(m) \cdot s^{-1}\ mod \ q$.
- Compute $u_2 = r \cdot s^{-1}\ mod \ q$.
- Compute $v = (g^{u_1} \cdot y^{u_2}\ mod \ p)\ mod \ q$.
- Output $1$ if $v = r$, otherwise output $0$.

**Correctness**
If $(r,s)$ is a valid signature on $m$, then we have

$v = g^{u_1}\cdot y^{u_2}=g^{h(m)\cdot (h(m)+x\cdot r)^{-1}\cdot k}\cdot {g^{x \cdot r \cdot (h(m)+x\cdot r)^{-1}\cdot k}} \ mod \ p$

$= g^{(h(m)+x\cdot r)\cdot (h(m)+x \cdot r)^{-1}\cdot k}\ mod \ p$

$= g^k \ mod \ p$

Thus the verification succeeds.

**2. Schnorr**

The Schnorr signature is an important

**signature scheme. It works in any prime order group and its security is proven in***DLP-based**under***the random oracle model***assumption [2].***DL**

*Domain Parameter Generation*- Select a prime number $p$.
- Select a prime divisor $q$ of $p-1$.
- Select a generator $g$ of the subgroup of order $q$.

*Key Generation*- Select a random integer $x$, where $0<x<q$.
- Compute $y=g^x \ mod \ p$.

The public key is $y$ and the private key is $x$.

**Signing**- Select a random integer $k$, where $0<x<q$.
- Compute $a = g^k \ mod \ p$.
- Compute $r = h(m \| a)$, where $m$ is the message to be signed and $h:\{0,1\}^* \rightarrow \mathcal{Z}_{q}$ is a hash function.
- Compute $s = (k + r\cdot x)\ mod \ q$

The signature on $m$ is the pair $(r,s)$.

**Verification**- Compute $v = g^s \cdot y^{-r}\ mod \ p$
- Output $1$ if $v = r$, otherwise output $0$.

**Correctness**
If $(r,s)$ is a valid signature on $m$, then we have

$v=g^s\cdot y^{-r}=g^{k+r\cdot x}\cdot g^{-r\cdot x}=g^k=r$

Thus the verification succeeds.

**3. RSA-FDH**

The

*RSA-FDH (full domain hash)*scheme was introduced by*Bellare*and*Rogaway*in [3]. It is a**RSA-based**signature scheme and follows the*paradigm. It makes use of the hash function (the image size of the hash function equals to RSA modulus) to generate random-looking output for the plain RSA signature scheme. Thus it prevents the algebraic attacks on the plain RSA signature scheme and it is able to sign messages of arbitrary length. But it is hard to create such hash function in practice. RSA-FDH can be proven EU-CMA secure in***hash-then-sign****the random oracle model**.

*Key Generation*- Select two large primes $p$ and $q$.
- Compute $N=p\cdot q$.
- Select a random integer $e$, where $1<e<\phi(N)$, such that $gcd(e,\phi(N))=1$.
- Compute the integer $d$, where $1<d<\phi(N)$, such that $e\cdot d = 1\ mod \ \phi(N)$.

The public key is $(N,e)$ and the private key is $(d,p,q)$.

**Signing**- Compute $s=h(m)^d\ mod \ N$, where $m$ is the message to be signed and $h:\{0,1\}^* \rightarrow \mathcal{Z}_N$ is a hash function.

The signature on $m$ is $s$.

**Verification**- Output $1$ if $s^e = h(m)\ mod \ N$, otherwise output $0$.

**Correctness**
If $s$ is a valid signature on $m$, then we have

$s^e=h(m)^{d\cdot e} mod \ N=h(m)\ mod \ N$

Thus the verification succeeds.

[1]http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

[2]http://eprint.iacr.org/2012/029.pdf

[3]http://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf

any links to explain how the r-th root of y is calculated in the Schnorr's algorithm?

ReplyDeleteIt is just y to the power minus r. So we just need to exponentiate by q-y

Delete