Implement a digital signature algorithm in c.

A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or documents. A valid digital signature gives a recipient reason to believe that the message was created by a known sender (authentication), that the sender cannot deny having sent the message was not altered in transit (integrity).

In this practical we are using ELGamal Signature Scheme.

Theory / Algorithm: -

ELGamal Signature:-

The ELGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms.

The ELGamal signature algorithm is rarely used in practice. A variant developed at NSA and known as the Digital Signature Algorithm is much more widely used. There are several other variants. The ELGamal signature scheme must not be confused with ELGamal encryption which was also invented by TaherELGamal.

The ELGamal signature scheme allows a third-party to confirm the authenticity of a message sent over on insecure channel.

System parameters:-

Let H be a collision-resistant hash function.

Let p be a large prime such that computing discrete logarithms modulo p is difficult.

Let g < p be a randomly chosen generator of the multiplicative group of integers modulo p Z*_P.

These system parameters may be shared between users.

Key generation:-

Randomly choose a secret key x with 1 < x < p-1.

Compute y = g x mod p.

The public key is y.

The secret key is x.

These steps are performed once by the singer.

Signature generation:-

To sign a message m the singer performs the following steps.

Choose a random k such that 1 < k < p-1 and gcd(k, p-1) = 1.

Compute s = (H(m)xr)k^-1 (mod p-1)

If s=0 start over again.

Then the pair (r, s) is the digital signature of n. The signer repeats these steps for every signature.

Verification:-

A signature (r, s) of a message m is verified as follows.

0 < r < p and 0 < s <p-1

g^H(m)= y^rr^s(mod p)

the verifier accepts a signature if all conditions are satisfied and rejects it otherwise.

Correctness:-

The algorithm is correct in the sense that a signature generated with the signing algorithm will always be accepted by the verifier.

The signature generation implies,

H(m) = xr + sk (mod p-1).

Hence Fermat’s little theorem implies

            G^H(m)=g^xrg^ks

                     = (g^x)r(g^k)s

                     = (y^r)(r^s) (mod p)

C Code:

// DSA

#include<stdio.h>

#include<conio.h>

#include<math.h>

long int ext_eucledian(long int m,long int b)

{

            int a1=1,a2=0,a3=m,b1=0,b2=1,b3=b,q,t1,t2,t3;

            while(1)

            {

                        if(b3==0)

                        {

                                    return 0;

                        }

                        if(b3==1)

                        {

                                    if(b2<0)

                                                b2+=m;

                                    return b2;

                        }

                        q=a3/b3;

                        t1=a1-(q*b1);

                        t2=a2-(q*b2);

                        t3=a3-(q*b3);

                        a1=b1;

                        a2=b2;

                        a3=b3;

                        b1=t1;

                        b2=t2;

                        b3=t3;

            }

}

long int power(long int a, long int j, long int c)

{

            int f,i;

            f=1;

            for(i=1;i<=j;i++)

            {

                        f=(f*a)%c;

            }

            f=f%c;

            return f;

}

void main()

{

            long int p,q,g,x,hm,k,y,r,s,s1,w,u1,u2,v,v1,v2,v3;

            clrscr();

            printf("enter the value of p:");

            scanf("%ld",&p);

            printf("enter the value of q:");

            scanf("%ld",&q);

            printf("enter the value of g:");

            scanf("%ld",&g);

            printf("enter the value of x:");

            scanf("%ld",&x);

            printf("enter the value of hm:");

            scanf("%ld",&hm);

            printf("enter the value of k:");

            scanf("%ld",&k);

            y=power(g,x,p);

            printf("\nvalue of y:%ld",y);

            r=power(g,k,p);

            r=r%q;

            printf("\nvalue of r:%ld",r);

            s=ext_eucledian(q,k);

            s1=(hm+(x*r));

            s=(s*s1)%q;

            printf("\nvalue of s:%ld",s);

            w=ext_eucledian(q,s);

            printf("\nsignature (r,s):%ld %ld",r,s);

            printf("\nvalue of w:%ld",w);

            u1=(hm*w)%q;

            printf("\nvalue of u1:%ld",u1);

            u2=(r*w)%q;

            printf("\nvalue of u2:%ld",u2);

            v=power(g,u1,p);

            v1=power(y,u2,p);

            v2=(v*v1)%p;

            v3=v2%q;

            printf("\nvalue of v:%ld",v3);

            getch();

}

Output:

 

THANK YOU!!!!