IGNOU CS-13 PROJECTS
1

Study and implement the following algorithms using C/C++ programming language.

  • RSA algorithm
  • Lamport’s Bakery Algorithm for Interprocess synchronization.
 
 
 

RSA algorithm

The RSA algorithm was invented in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman.

Here's the relatively easy to understand math behind RSA public key encryption.

  1. Find P and Q, two large (e.g., 1024-bit) prime numbers.
  2. Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.
  3. Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.
  4. The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.
  5. The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation.

Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.

You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence can factor your modulus into P and Q.

  

(from this site http://ftp.gnupg.zone-h.org/contrib/rsa.c)
/* How to compile:
 *
         gcc -Wall -O2 -shared -fPIC -o rsa rsa.c
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
/* configuration stuff */
#ifdef __alpha__
  #define SIZEOF_UNSIGNED_LONG 8
#else
  #define SIZEOF_UNSIGNED_LONG 4
#endif
 
#if defined(__mc68000__) || defined (__sparc__) || defined (__PPC__) \
    || (defined(__mips__) && (defined(MIPSEB) || defined (__MIPSEB__)) ) \
    || defined(__hpux__)  /* should be replaced by the macro for the PA */
  #define BIG_ENDIAN_HOST 1
#else
  #define LITTLE_ENDIAN_HOST 1
#endif
 
typedef unsigned long  ulong;
typedef unsigned short ushort;
typedef unsigned char  byte;
 
typedef unsigned short u16;
typedef unsigned long  u32;
 
/* end configurable stuff */
 
 
const char * const gnupgext_version = "RSA ($Revision: 1.10 $)";
 
#ifndef DIM
  #define DIM(v) (sizeof(v)/sizeof((v)[0]))
  #define DIMof(type,member)   DIM(((type *)0)->member)
#endif
 
#define is_RSA(a) ((a)>=1 && (a)<=3)
 
#define BAD_ALGO  4
#define BAD_KEY   7
#define BAD_SIGN  8
 
struct mpi_struct { int hidden_stuff; };
typedef struct mpi_struct *MPI;
 
extern int g10c_debug_mode;
extern int g10_opt_verbose;
 
 
 
typedef struct {
    MPI n;         /* modulus */
    MPI e;         /* exponent */
} RSA_public_key;
 
 
typedef struct {
    MPI n;         /* public modulus */
    MPI e;         /* public exponent */
    MPI d;         /* exponent */
    MPI p;         /* prime  p. */
    MPI q;         /* prime  q. */
    MPI u;         /* inverse of p mod q. */
} RSA_secret_key;
 
/* imports */
void *g10_malloc( size_t n );
void *g10_calloc( size_t n );
void g10_free( void *p);
void g10_log_fatal( const char *fmt, ... );
void g10_log_error( const char *fmt, ... );
void g10_log_info( const char *fmt, ... );
void g10_log_debug( const char *fmt, ... );
void g10_log_hexdump( const char *text, char *buf, size_t len );
void g10_log_mpidump( const char *text, MPI a );
MPI  g10c_generate_secret_prime( unsigned nbits );
char *g10c_get_random_bits( unsigned nbits, int level, int secure );
MPI  g10m_new( unsigned nbits );
MPI  g10m_new_secure( unsigned nbits );
void g10m_release( MPI a );
void g10m_set( MPI w, MPI u);
void g10m_set_ui( MPI w, unsigned long u);
void g10m_set_buffer( MPI a, const char *buffer, unsigned nbytes, int sign );
MPI  g10m_copy( MPI a );
void g10m_swap( MPI a, MPI b);
unsigned g10m_get_nbits( MPI a );
unsigned g10m_get_size( MPI a );
int  g10m_cmp( MPI u, MPI v );
void g10m_add_ui(MPI w, MPI u, unsigned long v );
void g10m_sub_ui(MPI w, MPI u, unsigned long v );
void g10m_mul( MPI w, MPI u, MPI v);
void g10m_fdiv_q( MPI quot, MPI dividend, MPI divisor );
void g10m_powm( MPI res, MPI base, MPI exp, MPI mod);
int  g10m_gcd( MPI g, MPI a, MPI b );
int  g10m_invm( MPI x, MPI u, MPI v );
 
/* local prototypes */
static void test_keys( RSA_secret_key *sk, unsigned nbits );
static void generate( RSA_secret_key *sk, unsigned nbits );
static int  check_secret_key( RSA_secret_key *sk );
static void public(MPI output, MPI input, RSA_public_key *skey );
static void secret(MPI output, MPI input, RSA_secret_key *skey );
 
 
static void
test_keys( RSA_secret_key *sk, unsigned nbits )
{
    RSA_public_key pk;
    MPI test = g10m_new( nbits );
    MPI out1 = g10m_new( nbits );
    MPI out2 = g10m_new( nbits );
 
    pk.n = sk->n;
    pk.e = sk->e;
    {   char *p = g10c_get_random_bits( nbits, 0, 0 );
        g10m_set_buffer( test, p, (nbits+7)/8, 0 );
        g10_free(p);
    }
 
    public( out1, test, &pk );
    secret( out2, out1, sk );
    if( g10m_cmp( test, out2 ) )
        g10_log_fatal("RSA operation: public, secret failed\n");
    secret( out1, test, sk );
    public( out2, out1, &pk );
    if( g10m_cmp( test, out2 ) )
        g10_log_fatal("RSA operation: secret, public failed\n");
    g10m_release( test );
    g10m_release( out1 );
    g10m_release( out2 );
}
 
/****************
 * Generate a key pair with a key of size NBITS
 * Returns: 2 structures filles with all needed values
 */
static void
generate( RSA_secret_key *sk, unsigned nbits )
{
    MPI p, q; /* the two primes */
    MPI d;    /* the private key */
    MPI u;
    MPI t1, t2;
    MPI n;    /* the public key */
    MPI e;    /* the exponent */
    MPI phi;  /* helper: (p-a)(q-1) */
    MPI g;
    MPI f;
 
    /* select two (very secret) primes */
    p = g10c_generate_secret_prime( nbits / 2 );
    q = g10c_generate_secret_prime( nbits / 2 );
    if( g10m_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
        g10m_swap(p,q);
    /* calculate Euler totient: phi = (p-1)(q-1) */
    t1 = g10m_new_secure( g10m_get_size(p) );
    t2 = g10m_new_secure( g10m_get_size(p) );
    phi = g10m_new_secure( nbits );
    g   = g10m_new_secure( nbits  );
    f   = g10m_new_secure( nbits  );
    g10m_sub_ui( t1, p, 1 );
    g10m_sub_ui( t2, q, 1 );
    g10m_mul( phi, t1, t2 );
    g10m_gcd(g, t1, t2);
    g10m_fdiv_q(f, phi, g);
    /* multiply them to make the private key */
    n = g10m_new( nbits );
    g10m_mul( n, p, q );
    /* find a public exponent  */
    e = g10m_new(6);
    g10m_set_ui( e, 17); /* start with 17 */
    while( !g10m_gcd(t1, e, phi) ) /* (while gcd is not 1) */
        g10m_add_ui( e, e, 2);
    /* calculate the secret key d = e^1 mod phi */
    d = g10m_new( nbits );
    g10m_invm(d, e, f );
    /* calculate the inverse of p and q (used for chinese remainder theorem)*/
    u = g10m_new( nbits );
    g10m_invm(u, p, q );
 
    if( g10c_debug_mode ) {
        g10_log_mpidump("  p= ", p );
        g10_log_mpidump("  q= ", q );
        g10_log_mpidump("phi= ", phi );
        g10_log_mpidump("  g= ", g );
        g10_log_mpidump("  f= ", f );
        g10_log_mpidump("  n= ", n );
        g10_log_mpidump("  e= ", e );
        g10_log_mpidump("  d= ", d );
        g10_log_mpidump("  u= ", u );
    }
 
    g10m_release(t1);
    g10m_release(t2);
    g10m_release(phi);
    g10m_release(f);
    g10m_release(g);
 
    sk->n = n;
    sk->e = e;
    sk->p = p;
    sk->q = q;
    sk->d = d;
    sk->u = u;
 
    /* now we can test our keys (this should never fail!) */
    test_keys( sk, nbits - 64 );
}
 
 
/****************
 * Test wether the secret key is valid.
 * Returns: true if this is a valid key.
 */
static int
check_secret_key( RSA_secret_key *sk )
{
    int rc;
    MPI temp = g10m_new( g10m_get_size(sk->p)*2 );
 
    g10m_mul(temp, sk->p, sk->q );
    rc = g10m_cmp( temp, sk->n );
    g10m_release(temp);
    return !rc;
}
 
 
 
/****************
 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
 *
 *      c = m^e mod n
 *
 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
 */
static void
public(MPI output, MPI input, RSA_public_key *pkey )
{
    if( output == input ) { /* powm doesn't like output and input the same */
        MPI x = g10m_new( g10m_get_size(input)*2 );
        g10m_powm( x, input, pkey->e, pkey->n );
        g10m_set(output, x);
        g10m_release(x);
    }
    else
        g10m_powm( output, input, pkey->e, pkey->n );
}
 
/****************
 * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
 *
 *      m = c^d mod n
 *
 * Where m is OUTPUT, c is INPUT and d,n are elements of PKEY.
 *
 * FIXME: We should better use the Chinese Remainder Theorem
 */
static void
secret(MPI output, MPI input, RSA_secret_key *skey )
{
    g10m_powm( output, input, skey->d, skey->n );
}
 
 
/*********************************************
 **************  interface  ******************
 *********************************************/
 
static int
do_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
{
    RSA_secret_key sk;
 
    if( !is_RSA(algo) )
        return BAD_ALGO;
 
    generate( &sk, nbits );
    skey[0] = sk.n;
    skey[1] = sk.e;
    skey[2] = sk.d;
    skey[3] = sk.p;
    skey[4] = sk.q;
    skey[5] = sk.u;
    /* make an empty list of factors */
    *retfactors = g10_calloc( 1 * sizeof **retfactors );
    return 0;
}
 
 
static int
do_check_secret_key( int algo, MPI *skey )
{
    RSA_secret_key sk;
 
    if( !is_RSA(algo) )
        return BAD_ALGO;
 
    sk.n = skey[0];
    sk.e = skey[1];
    sk.d = skey[2];
    sk.p = skey[3];
    sk.q = skey[4];
    sk.u = skey[5];
    if( !check_secret_key( &sk ) )
        return BAD_KEY;
 
    return 0;
}
 
 
 
static int
do_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
{
    RSA_public_key pk;
 
    if( algo != 1 && algo != 2 )
        return BAD_ALGO;
 
    pk.n = pkey[0];
    pk.e = pkey[1];
    resarr[0] = g10m_new( g10m_get_size( pk.n ) );
    public( resarr[0], data, &pk );
    return 0;
}
 
static int
do_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
{
    RSA_secret_key sk;
 
    if( algo != 1 && algo != 2 )
        return BAD_ALGO;
 
    sk.n = skey[0];
    sk.e = skey[1];
    sk.d = skey[2];
    sk.p = skey[3];
    sk.q = skey[4];
    sk.u = skey[5];
    *result = g10m_new_secure( g10m_get_size( sk.n ) );
    secret( *result, data[0], &sk );
    return 0;
}
 
static int
do_sign( int algo, MPI *resarr, MPI data, MPI *skey )
{
    RSA_secret_key sk;
 
    if( algo != 1 && algo != 3 )
        return BAD_ALGO;
 
    sk.n = skey[0];
    sk.e = skey[1];
    sk.d = skey[2];
    sk.p = skey[3];
    sk.q = skey[4];
    sk.u = skey[5];
    resarr[0] = g10m_new( g10m_get_size( sk.n ) );
    secret( resarr[0], data, &sk );
 
    return 0;
}
 
static int
do_verify( int algo, MPI hash, MPI *data, MPI *pkey,
           int (*cmp)(void *opaque, MPI tmp), void *opaquev )
{
    RSA_public_key pk;
    MPI result;
    int rc;
 
    if( algo != 1 && algo != 3 )
        return BAD_ALGO;
    pk.n = pkey[0];
    pk.e = pkey[1];
    result = g10m_new(160);
    public( result, data[0], &pk );
    /*rc = (*cmp)( opaquev, result );*/
    rc = g10m_cmp( result, hash )? BAD_SIGN:0;
    g10m_release(result);
 
    return rc;
}
 
 
static unsigned
do_get_nbits( int algo, MPI *pkey )
{
    if( !is_RSA(algo) )
        return 0;
    return g10m_get_nbits( pkey[0] );
}
 
 
/****************
 * Return some information about the algorithm.  We need algo here to
 * distinguish different flavors of the algorithm.
 * Returns: A pointer to string describing the algorithm or NULL if
 *          the ALGO is invalid.
 * Usage: Bit 0 set : allows signing
 *            1 set : allows encryption
 */
static const char *
rsa_get_info( int algo,
              int *npkey, int *nskey, int *nenc, int *nsig, int *usage,
    int (**r_generate)( int algo, unsigned nbits, MPI *skey, MPI **retfactors ),
    int (**r_check_secret_key)( int algo, MPI *skey ),
    int (**r_encrypt)( int algo, MPI *resarr, MPI data, MPI *pkey ),
    int (**r_decrypt)( int algo, MPI *result, MPI *data, MPI *skey ),
    int (**r_sign)( int algo, MPI *resarr, MPI data, MPI *skey ),
    int (**r_verify)( int algo, MPI hash, MPI *data, MPI *pkey,
                                   int (*)(void *, MPI), void *),
    unsigned (**r_get_nbits)( int algo, MPI *pkey ) )
{
    *npkey = 2;
    *nskey = 6;
    *nenc = 1;
    *nsig = 1;
    *r_generate        = do_generate       ;
    *r_check_secret_key = do_check_secret_key;
    *r_encrypt         = do_encrypt        ;
    *r_decrypt         = do_decrypt        ;
    *r_sign            = do_sign           ;
    *r_verify          = do_verify         ;
    *r_get_nbits       = do_get_nbits      ;
 
    switch( algo ) {
      case 1: *usage = 2|1; return "RSA";
      case 2: *usage = 2  ; return "RSA-E";
      case 3: *usage =  1; return "RSA-S";
      default:*usage = 0; return NULL;
    }
}
 
 
static struct {
    int class;
    int version;
    int  value;
    void (*func)(void);
} func_table[] = {
    { 30, 1, 0, (void(*)(void))rsa_get_info },
    { 31, 1, 1 }, /* RSA */
    { 31, 1, 2 }, /* RSA encrypt only */
    { 31, 1, 3 }, /* RSA sign only */
};
 
 
 
/****************
 * Enumerate the names of the functions together with informations about
 * this function. Set sequence to an integer with a initial value of 0 and
 * do not change it.
 * If what is 0 all kind of functions are returned.
 * Return values: class := class of function:
 *                        10 = message digest algorithm info function
 *                        11 = integer with available md algorithms
 *                        20 = cipher algorithm info function
 *                        21 = integer with available cipher algorithms
 *                        30 = public key algorithm info function
 *                        31 = integer with available pubkey algorithms
 *               version = interface version of the function/pointer
 */
void *
gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
{
    void *ret;
    int i = *sequence;
 
    do {
        if( i >= DIM(func_table) || i < 0 ) {
            return NULL;
        }
        *class = func_table[i].class;
        *vers  = func_table[i].version;
        switch( *class ) {
          case 11:
          case 21:
          case 31:
            ret = &func_table[i].value;
            break;
          default:
            ret = func_table[i].func;
            break;
        }
        i++;
    } while( what && what != *class );
 
    *sequence = i;
    return ret;
}