/*************************************************************************
**                                                                      **
**  zrsa.cxx                                                            **
**                                                                      **
**  RSA ENCRYPTION, DECRYPTION AND SIGNATURE ROUTINES                   **
**                                                                      **
**  Copyright (c)1996 Markku-Juhani O. Saarinen <mjos@math.jyu.fi>      **
**                                                                      **
*************************************************************************/

// ladataan prototyypit

#include "kbn.h"
#include "rc4.h"
#include "sha.h"
#include <stdio.h>
#include <string.h>
#include <stream.h>
#include <fstream.h>

//           b 
//  laskee  a  mod n

kbn& modexp (kbn a, kbn b, kbn n)
{
    static kbn r;
    int i, explen;
    
    r = 1;  
    explen = b.log2();
    
    for(i=0; i<=explen; i++)
    { 
        if ( b.testbit(i) )
            r = (r*a) % n;
        a = a.sqr() % n;
    }
    return r;
}

//  laskee syt(a, b)

kbn gcd(kbn a, kbn b)
{
    static kbn g0, g1, g2, zero; 

    g0 = a;
    g1 = b;
    zero = 0;
    
    while ( g1 != zero )
    { 
        g2 = g0 % g1;
        g0 = g1;
        g1 = g2; 
    }
    
    return g0;
}

//  laskee b:n joka toteuttaa  ab mod n = 1  (jos mahdollista)

kbn& inverse (kbn a, kbn n)
{
    // nämä on pidettävä staattisina, sillä muuten ne söisivät koko
    // pinon ja kaataisivat ohjelman

    static kbn u1, u3, v1, v3, t1, t3, q, w, zero;
    int sign;

    // alustetaan nollavakio ja kiertomuuttajat

    zero = 0;

    // alustetaan muuttujat

    u1 = 1;
    u3 = a;
    v1 = 0;
    v3 = n;
    
    // laajennettu euklideen algoritmi
    // (muunnettu negatiivisten lukujen välttämiseksi)

    sign = 0;

    while( v3 != zero )
    {       
        q = u3 / v3;
        t3 = u3 % v3;
        w = q * v1;
        t1 = u1 + w;
        u1 = v1;
        v1 = t1;
        u3 = v3;
        v3 = t3;
        
        sign = !sign;
    }
    
    // käännetään merkin mukaisesti
    
    if (sign)
        u1 = n - u1;
        
    return u1;
}

//  luodaan satunnaisluku, suuruudeltaan välillä 0..max-1

kbn& rc4rand(kbn *max)
{
    static rc4 r;
    unsigned char p[1024];
    static kbn x;
    int len;

    len = (max->log2() >> 3) + 1;
    r.rand(p, len);
    x.load(p, len);
    bzero(p, len);          // vektori nollataan, jotta muistiin ei jäisi
    x %= *max;

    return x;
}

//  testaa, onko annettu luku (todennäköisesti) alkuluku

int prob_primetest (kbn *n)
{
    static kbn q, y, one;
    int j, k;
         
    one = 1;
    j = 0;
   
    //                                           k
    // (p0) hajoitetaan n luvuiksi (k, q) s.e.  2 q + 1 = n, q mod 2 = 1
    for(k=1; !(n->testbit(k)); k++);
    q = *n >> k;
    
    y = rc4rand( n );                   // y satunnaisluku välillä 0..n-1
    
    //                    q
    // (p2) j <- 0, y <- y  mod n

    y = modexp( y, q, *n );
 
    // jos y = 1, luku saattaa olla alkuluku

    if ( y == one )
        return 1;        
    do 
    {            
        // jos y = n-1, luku saattaa olla alkuluku
        if ( y == (*n-one) )
            return 1;            
        //                  2
        // asetetaan  y <- y  mod n
        y = y.sqr() % *n;

        // y = 1, luku EI ole alkuluku
        if ( y == one )
            return 0;
        j++;

    } while ( j < k );
    
    return 0;
}

//  tuottaa satunnaisen alkuluvun, jossa bits bittiä

kbn& random_prime (int bits)
{
    static kbn n;
    int i, primefound;
   
    // luodaan aloituspiste, jonka 2 ylintä bittiä ja alin on päällä
    // (luku on pariton)

    n = 0;
    n.setbit( bits-1, 1 );
    n = rc4rand( &n );    
    n.setbit( bits-1, 1 );
    n.setbit( bits-2, 1 );
    n.setbit( 0, 1 );   
    
    do {
        ++n; ++n;                           // siirrytään seuraavaan parittomaan lukuun
        primefound = 1;
       
        for(i=0; i<25 && primefound; i++)   // testataan 25 kertaa
        {
            primefound = prob_primetest(&n);
         
            // PGP-mäinen edistymisindikaattori
            cout << (primefound ? '*' : '.') << flush;
        }
    } while (!primefound);
    cout << " prime!" << endl;

    // jos 25 testin mukaan n on alkuluku, palautetaan se

    return n;
}

// luodaan rsa-avaimet ja tallennetaan ne tiedostoihin

int rsa_keygen(int bits)
{
    ofstream pubkey, privkey;
    char filen[100];
    static kbn phi, p, q, e, d, n, one;

    cout << "Julkisen ja salaisen avaimen luominen." << endl << endl;

    // avataan yleisen avaimen tiedosto

    cout << "Julkinen avaintiedosto :" << flush;
    cin >> filen;    
    pubkey.open( filen, ios::out, 0644 );   // moodi 644; muidenkin luettava

    if ( pubkey.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }

    // avataan yksityisen avaimen tiedosto

    cout << "Salainen avaintiedosto :" << flush;
    cin >> filen;
    privkey.open( filen, ios::out, 0600 );  // moodi 600; ei muiden luettava

    if ( privkey.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }

    // luodaan kaksi alkulukua p ja q
    
    cout << "odota hetki " << flush;
    
    p = random_prime( bits / 2 );      
    q = random_prime( bits / 2 );
     
    // lasketaan n = pq  ja phi(n) = (p-1)(q-1)
        
    n = p * q;
    --p;
    --q;
    phi = p * q;
    one = 1;

    // tuotetaan julkinen eksponentti e >= 17, jolle syt(e, phi(n)) = 1     

    e = 17;
    while ( gcd( e, phi ) != one )
        { ++e; ++e; }
       
    // tuotetaan salainen eksponentti d, jolle  ed mod phi = 1 
    
    d = inverse( e, phi );

    // kirjoitetaan julkisen avaimen tiedosto
    
    pubkey << n << endl;        // n
    pubkey << e << endl;        // e
    
    // kirjoitetaan salainen avain tiedostoon
    
    privkey << n << endl;       // n
    privkey << d << endl;       // d
    
    return 0;
}

// salakirjoitetaan viesti

int rsa_crypt ()
{
    static kbn n, e, m;
    rc4 *rndkey;
    ifstream pubkey;
    FILE *mof;
    char filen[100];
    unsigned char key[256], *msg;
    unsigned long m_len, keylen;
    
    cout << "Tiedoston salaaminen." << endl << endl;

    // avataan yleisen avaimen tiedosto

    cout << "Julkinen avaintiedosto :" << flush;
    cin >> filen;    
    pubkey.open( filen );
    if ( pubkey.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }
  
    // luetaan tiedostosta julkinen avain (e, n)
  
    pubkey >> n;                // n
    pubkey >> e;                // e

    // avataan viestin sisältävä tiedosto 
    
    cout << "Salattava tiedosto     :" << flush;
    cin >> filen;

    if ( (mof = fopen(filen, "rb")) == NULL )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);    
    }
    
    // haetaan tiedoston pituus
    
    fseek( mof, 0, SEEK_END );
    m_len = ftell( mof );
    fseek( mof, 0, SEEK_SET );

    // varataan muistilohko ja luetaan tiedosto sinne
    
    if ( (msg=(unsigned char *) malloc(m_len)) == NULL )
        exit(1);
    bzero( msg, m_len );
    fread( msg, 1, m_len, mof );
    fclose( mof );

    // muodostetaan 256-bittinen kertakäyttöavain 96-bittisesta 
    // satunnaisluvusta ja 160-bittisestä SHA-hashista

    rndkey = new rc4;
    sha( msg, m_len, (void *) key ); 
    rndkey->rand( &key[20], 12 );    

    // kryptataan (rc4) lohko kertakäyttöavaimella
    
    rndkey->init( key, 32 );
    rndkey->crypt( msg, m_len );
  
    // suoritetaan kertakäyttöavaimelle RSA-koodaus julkisella avaimella
    
    m.load ( key, 32 );
    m = modexp( m, e, n );
    
    // avataan viestin sisältävä tiedosto 
    
    cout << "Salattu tiedosto       :" << flush;
    cin >> filen;
    if ( (mof = fopen(filen, "wb")) == NULL )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);    
    }

    keylen = m.save ( key );
 
    // kirjoitetaan avaimen pituus, avain ja lopuksi itse viesti
    
    fwrite( &keylen, sizeof( unsigned long ), 1, mof );
    fwrite( key, 1, keylen, mof );
    fwrite( msg, 1, m_len, mof );

    fclose (mof );
    
    delete rndkey;
    free( msg );

    // 
    
    cout << "ok!" << endl;

    return 0;
}

// puretaan salakirjoitettu viesti

int rsa_decrypt ()
{
    static kbn n, d, c;
    ifstream privkey;
    rc4 *seskey;
    FILE *mof;
    char filen[100];
    unsigned char key[256], digest[20], *msg, *rkey;
    unsigned long m_len, keylen;
    int offset;
    
    cout << "Salauksen purkamien." << endl << endl;

    // avataan yleisen avaimen tiedosto

    cout << "Salainen avaintiedosto :" << flush;
    cin >> filen;    
    privkey.open( filen );
    if ( privkey.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }
  
    // luetaan tiedostosta salainen avain (d, n)
  
    privkey >> n;                // n
    privkey >> d;                // d

    // avataan viestin sisältävä tiedosto 
    
    cout << "Salattu tiedosto       :" << flush;
    cin >> filen;

    if ( (mof = fopen(filen, "rb")) == NULL )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);    
    }

    // haetaan tiedoston pituus
    
    fseek( mof, 0, SEEK_END );
    m_len = ftell( mof );
    fseek( mof, 0, SEEK_SET );

    // varataan muistilohko ja luetaan tiedosto sinne
    
    if ( (msg=(unsigned char *) malloc(m_len)) == NULL )
        exit(1);
    bzero( msg, m_len );
    fread( msg, 1, m_len, mof );
    fclose( mof );

    if ( m_len < 36 )
    {
        cerr << "Salattu tiedosto liian pieni" << endl;
        exit(1);
    }
    
    // luetaan avaimen pituus ja asetetaan se
    
    keylen = *((unsigned long *) msg);
    c.load( &msg[4], keylen);
    
    // puretaan avain
    
    c = modexp( c, d, n );
    
    // puretaan sillä lohko

    bzero(key, sizeof(key));
    rkey = &key[ c.save(&key[8])-24 ];    

    seskey = new rc4( rkey, 32 );
    offset = keylen + sizeof(unsigned long);
    m_len -= offset;    
    seskey->crypt( msg+offset, m_len );
    delete seskey;

    // tarkastetaan, täsmääkö hashit
    
    sha( msg+offset, m_len, (void *) digest ); 

    if ( bcmp( digest, rkey, 20 ) )
    {
        cerr << "Virheellinen viesti tai väärä avain" << endl;
        exit (1);
    }
    
    // kirjoitetaan tiedosto
        
    cout << "Purettu tiedosto       :" << flush;
    cin >> filen;
    if ( (mof = fopen(filen, "wb")) == NULL )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);    
    }
    fwrite( msg+offset, 1, m_len, mof );

    fclose( mof );
    free( msg );
    
    cout << "ok!" << endl;

    return 0;
}

// digitaalinen allekirjoitus

int rsa_sign ()
{
    static kbn n, d, s;
    ifstream seckey;
    ofstream sig;
    FILE *mof;
    char filen[100];
    unsigned char key[20], *msg;
    unsigned long m_len;
    
    cout << "Tiedoston allekirjoituksen luominen." << endl << endl;

    // avataan yleisen avaimen tiedosto

    cout << "Salainen avaintiedosto :" << flush;
    cin >> filen;    
    seckey.open( filen );
    if ( seckey.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }
  
    // luetaan tiedostosta salainen avain (d, n)
  
    seckey >> n;                // n
    seckey >> d;                // d

    // avataan viestin sisältävä tiedosto 
    
    cout << "Allekirjoitettava tied :" << flush;
    cin >> filen;
    if ( (mof = fopen(filen, "rb")) == NULL )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);    
    }
    
    // haetaan tiedoston pituus
    
    fseek( mof, 0, SEEK_END );
    m_len = ftell( mof );
    fseek( mof, 0, SEEK_SET );

    // varataan muistilohko ja luetaan tiedosto sinne
    
    if ( (msg=(unsigned char *) malloc(m_len)) == NULL )
        exit(1);
    bzero( msg, m_len );
    fread( msg, 1, m_len, mof );
    fclose( mof );

    // lasketaan 160-bittinen SHA-hash

    sha( msg, m_len, (void *) key ); 

    // suoretaan modulaarieksponentaatio salaisella avaimella d
    
    s.load ( key, 20 );
    s = modexp( s, d, n );
    
    // kirjoitetaan signatuuri
    
    cout << "Signatuuritiedosto     :" << flush;
    cin >> filen;    
    sig.open( filen );
    if ( sig.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }
    sig << s;

    // ok!
    
    cout << "ok!" << endl;

    free ( msg );
    return 0;
}

// allekirjoituksen tsekkaus

int rsa_checksign ()
{
    static kbn n, e, s, h;
    ifstream pubkey;
    ifstream sig;
    FILE *mof;
    char filen[100];
    unsigned char key[20], *msg;
    unsigned long m_len;
    
    cout << "Tiedoston allekirjoituksen tarkastaminen." << endl << endl;

    // avataan yleisen avaimen tiedosto

    cout << "Julkinen avaintiedosto :" << flush;
    cin >> filen;    
    pubkey.open( filen );
    if ( pubkey.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }
  
    // luetaan tiedostosta julkinen avain (e, n)
  
    pubkey >> n;                // n
    pubkey >> e;                // e

    // avataan viestin sisältävä tiedosto 

    cout << "Allekirjoitettu tied.  :" << flush;
    cin >> filen;
    if ( (mof = fopen(filen, "rb")) == NULL )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);    
    }

    // luetaan signatuuri
        
    cout << "Signatuuritiedosto     :" << flush;
    cin >> filen;    
    sig.open( filen );
    if ( sig.rdstate() )
    {
        cerr << "Tiedoston avaus epäonnistui: " << filen << endl;
        exit(1);
    }
    sig >> s;
    
    // haetaan tiedoston pituus
    
    fseek( mof, 0, SEEK_END );
    m_len = ftell( mof );
    fseek( mof, 0, SEEK_SET );

    // varataan muistilohko ja luetaan tiedosto sinne
    
    if ( (msg=(unsigned char *) malloc(m_len)) == NULL )
        exit(1);
    bzero( msg, m_len );
    fread( msg, 1, m_len, mof );
    fclose( mof );

    // lasketaan 160-bittinen SHA-hash

    sha( msg, m_len, (void *) key ); 

    // suoretaan modulaarieksponentaatio julkisella avaimella e
    
    h.load ( key, 20 );
    s = modexp( s, e, n );
    
    // vertaillaan
    
    if ( s == h )
        cout << endl << "Allekirjoitus on ok." << endl;
    else
        cout << endl << "Allekirjoitus ei täsmää!" << endl;

    free( msg );
    return 0;
}

// pääohjelma

int main (int argc, char **argv)
{
    // lyhyt apu

    const char help[] = 
    "ZenRSA 0.0 (c)1996 Markku-Juhani O. Saarinen <mjos@math.jyu.fi>\n"
    "Kopiointi ja levittäminen sallittu vain tekijän luvalla.\n" 
    "\n"
    "Käyttö: zrsa <toiminto>, jossa toiminto on yksi seuraavista:\n"
    "\n"
    " g  RSA-Avainparin luominen\n"
    " e  Tiedoston salaus julkisella avaimella\n"
    " d  Salauksen purkaminen salaisella avaimella\n"
    " s  Tiedoston digitaalinen allekirjoitus salaisella avaimella\n"
    " c  Allekirjoituksen tarkistaminen julkisella avaimlla\n\n";

    // onko parametrejä ?

    if ( argc != 2 )
    {
        cout << help;
        return 1;
    }
        
    // totellaan komentorivikäskyä
        
    switch ( argv[1][0] )
    {
        case 'g':
            rsa_keygen(1024);
            break;
            
        case 'e':
            rsa_crypt();
            break;
            
        case 'd':
            rsa_decrypt();
            break;

        case 's':
            rsa_sign();
            break;

        case 'c':
            rsa_checksign();
            break;
           
        default:
            cout << help;
            return 1;
    }

    return 0;
}