idea.cpp

1、对于凯撒密文

// Idea.cpp: implementation of the CIdea class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "030300816.h"
#include "Idea.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CIdea::CIdea()
{
	TWOPOWER16 = 65536;
	TWOPOWER161 = 65537;
}

CIdea::~CIdea()
{

}

void CIdea::Decipher()
{
    promptForKey();
    calcEKeys(origkeychar);
    calcDKeys();
    unsigned char ciphertext[MAXINPUTSIZE+1];
    unsigned char decipheredtext[MAXINPUTSIZE+1];
    unsigned char plaintext[MAXINPUTSIZE+1];
    ciphertext[MAXINPUTSIZE] = '\0';
    decipheredtext[MAXINPUTSIZE] = '\0';
	plaintext[MAXINPUTSIZE]='\0';
	CString temp = _T("");
	static bool bit[64];
	int length = m_cipherString.GetLength();
	int round = length / 64;
	int i = 0 , j = 0;

	while ( i < round )
	{
		for ( j = 0 ; j < 64 ; j ++ )
		{
			if ( m_cipherString.GetAt(64*i+j) == '0' )
				bit[j] = 0;
			else
				bit[j] = 1;
		}
		BitToByte(ciphertext,bit,64);
		decrypt(ciphertext,decipheredtext);
		for ( j = 0 ; j < 8 ; j ++ )
		{
			temp += CString ( decipheredtext[j] );
		}
		i ++;
	}
	m_plainString = temp;
}

void CIdea::Encipher()
{
	promptForKey();
    calcEKeys(origkeychar);
    calcDKeys();
    unsigned char ciphertext[MAXINPUTSIZE+1];
    unsigned char decipheredtext[MAXINPUTSIZE+1];
    unsigned char plaintext[MAXINPUTSIZE+1];
    ciphertext[MAXINPUTSIZE] = '\0';
    decipheredtext[MAXINPUTSIZE] = '\0';
	plaintext[MAXINPUTSIZE]='\0';
	CString temp = _T("");
	static bool bit[64];

	int length = m_plainString.GetLength();
	int round = (length-1) / 8;
	int i = 0 , j = 0;

	//start here
	while ( i < round )
	{
		promptForText(plaintext,1,i++);
		encrypt(plaintext,ciphertext);
		ByteToBit(bit,ciphertext,64);
		for ( j = 0 ; j < 64 ; j ++ )
		{
			if ( bit[j] == 0 )
				temp += _T("0");
			else
				temp += _T("1");
		}
	}
	
	//the last round
	for ( j = 0 ; j < length-i*8 ; j ++ )
	{
		plaintext[j] = m_plainString.GetAt(8*i+j);
	}
	while ( j < 8 )
	{
		plaintext[j] = ' ';
		j ++;
	}
	encrypt(plaintext,ciphertext);
	ByteToBit(bit,ciphertext,64);
	for ( j = 0 ; j < 64 ; j ++ )
	{
		if ( bit[j] == 0 )
			temp += _T("0");
		else
			temp += _T("1");
	}
	m_cipherString = temp;
}

//****************************************
// This is the core encryption and decryption
// engine which does all the rounds and does
// all the arithmetic operations (add,mult,xor,swap,inverse)
//****************************************

void CIdea::runIdea(unsigned char* msg, unsigned char* outmsg,unsigned short* keysbit16)
{
    unsigned short x1,x2,x3,x4;        
    unsigned short y1,y2,y3,y4;        
    unsigned short x5,x6,x7,x8,x9,x10; 
    unsigned short x11,x12,x13,x14;  

    // msg is 1 byte.  make 2 byte ptr to facilitate copying for
    // 16 bit fields
    // 2 bytes go into x1, 2 bytes go into x2,etc
    unsigned short* msgbit16 = (unsigned short*) msg;
    //cout << "msg is " << *msg <<endl; 
    x1 = *msgbit16++;
    x2 = *msgbit16++;
    x3 = *msgbit16++;
    x4 = *msgbit16++;


    //x1 = (x1 >>8) | (x1<<8);
    //x2 = (x2 >>8) | (x2<<8);
    //x3 = (x3 >>8) | (x3<<8);
    //x4 = (x4 >>8) | (x4<<8);
    

    // this is for debug purposes. make greater than 8
    // if don't want debugs
    int tst=9;


    // note that mod 2^16+1 could yield a value which is 2^16.
    // this is greater than space for 16 bits, so i think
    // the mod operation makes 2^16 mod 2^16+1 equal to 0.

    for (int i=0; i<NUMROUNDS;i++)
    {
	//IY
      
    	if (i==tst )
	    cout << "STEP 1:  x1 is " << x1 << ", key is " << *keysbit16 << endl;
	//STEP 1 of 14
        x1 = (x1* (*keysbit16++)) % TWOPOWER161;
    	//IY
    	if (i==tst )
            cout << "\tAfter mul, x1 is " << x1 << endl;


        //IY
        if (i==tst )
            cout << "STEP 2:  x2 is " << x2 << ", key is " << *keysbit16 << endl;

	//STEP 2 of 14
        x2 = (x2 + *keysbit16++) % TWOPOWER16;

        //IY
        if (i==tst )
            cout << "\tAfter add, x2 is " << x2 << endl;

        //IY
        if (i==tst )
           cout << "STEP 3:  x3 is " << x3 << ", key is " << *keysbit16 << endl;
	//STEP 3 of 14
        x3 = (x3 + *keysbit16++) % TWOPOWER16;

        //IY
        if (i==tst )
           cout << "\tAfter add, x3 is " << x3 << endl;

        //IY
        if (i==tst )
           cout << "STEP 4:  x4 is " << x4 << ", key is " << *keysbit16 << endl;

	//STEP 4 of 14
        x4 = (x4* (*keysbit16++)) % TWOPOWER161;
        //IY
        if (i==tst )
           cout << "\tAfter mul, x4 is " << x4 << endl;

        //IY
        if (i==tst)
           cout << "STEP 5:  x3 is " << x3 << ", x1 is " << x1 << endl;


	//STEP 5 of 14
        x5 = x1^x3;
        if (i==tst)
           cout << "\tAfter XOR, x5 is " << x5 << endl;
    
        //IY
        if (i==tst)
           cout << "STEP 6(outorder):  x2 is " << x2 << ", x4 is " << x4 << endl;

	//STEP 6 of 14
 	x6 = x2^x4;

        //IY
        if (i==tst)
           cout << "\tAfter XOR, x6 is " << x6 << endl;

        //IY
        if (i==tst)
           cout << "STEP 7(outorder):  x5 is " << x5 << ", key is " << *keysbit16 << endl;

	//STEP 7 of 14
        x7 = (x5* (*keysbit16++)) % TWOPOWER161;

       	if (i==tst)
           cout << "\tAfter mul, x7 is " << x7 << endl;

    	//IY
    	if (i==tst)
           cout << "STEP 8:  x6 is " << x6 << ", x7 is " << x7 << endl;

	//STEP 8 of 14
        x8 = (x6+x7) % TWOPOWER16;

   	//IY
    	if (i==tst)
           cout << "\tAfter ADD, x8 is " << x8 << endl;

        //IY
    	if (i==tst)
            cout << "STEP 9:  x8 is " << x8 << ", key is " << *keysbit16 << endl;

	//STEP 9 of 14
        x9 = (x8* (*keysbit16++)) % TWOPOWER161;

        //IY
        if (i==tst)
            cout << "\tAfter mul, x9 is " << x9 << endl;

        //IY
        if (i==tst)
            cout << "STEP 10:  x7 is " << x7 << ", x9 is " << x9 << endl;

	//STEP 10 of 14
        x10 = (x7+x9) % TWOPOWER16;
        //IY
        if (i==tst)
           cout << "\tAfter add, x10 is " << x10 << endl;

	//STEP 11,12,13,14 of 14
        x11=x1^x9;
	x12=x3^x9;
	x13=x2^x10;
	x14=x4^x10;


        if (i==tst ) {
           cout << "\tSTEP11: After XOR, x11 is " << x11 << endl;
           cout << "\tSTEP12: After XOR, x12(after swap) is " << x12 << endl;
           cout << "\tStep13: After XOR, x13(after swap) is " << x13 << endl;
           cout << "\tStep14: After XOR, x14 is " << x14 << endl;
        }

	//new values for next iteration
        x1=x11;
  	x2=x12;
	x3=x13;
	x4=x14;

    } // foreach round


    //final output transformation.  modify 4 subkeys like so:
    y1 = (x11 * (*keysbit16++))  % TWOPOWER161;
    //flip flop these two!
    y3 = (x13 + *keysbit16++) % TWOPOWER16;
    y2 = (x12 + *keysbit16++) %TWOPOWER16;
    y4 = (x14 * (*keysbit16))  % TWOPOWER161;


    // put new data into the buffer
    msgbit16=(unsigned short*)outmsg;

    *msgbit16++ = y1;
    *msgbit16++ = y3;
    *msgbit16++ = y2;
    *msgbit16 = y4;

    //*msgbit16++ = (y1 >>8) | (y1<<8);
    //*msgbit16++ = (y3 >>8) | (y3<<8);
    //*msgbit16++ = (y2 >>8) | (y2<<8);
    //*msgbit16 = (y4 >>8) | (y4<<8);
} // end runIdea



//****************************************
// each block is 8 bytes (64 bits), so
// we loop until all blocks have been encrypted
// essentially hands over work to runIdea
//****************************************

void CIdea::encrypt (unsigned char* msg,unsigned char* outmsg)
{
	unsigned char* inptr=msg;
    unsigned char* outptr=outmsg;
	runIdea(inptr,outptr,esubkeys);
}

//****************************************
// each block is 8 bytes (64 bits), so
// we loop until all blocks have been decrypted
// essentially hands over work to runIdea
//****************************************
void CIdea::decrypt (unsigned char* msg,unsigned char* outmsg)
{
	unsigned char* inptr=msg;
    unsigned char* outptr=outmsg;
	runIdea(inptr,outptr,dsubkeys);
} //end of decrypt





//****************************************
// Finds the inverse of a 16 bit number mod 2^16+1
//    uses extended euclidean algorithm
//****************************************

//unsigned short inv(unsigned short b)
short CIdea::inv(unsigned short b)
{

    // what book said to do if taking mod of 0 or 1
    if (b==0 || b==1)
	return b;

    // initial variables
    int a = 65536+1;  // 2^16 + 1
    int g0 = a;
    int g1 = b;
    int v0 = 0;
    int v1 = 1;
    int savev0;
    int q;
    int rem;
    int numloops = 0;

    // start of extended euglidean algorithm
    while (g1 != 0) {
	numloops++;
	q = g0/g1;
	rem = g0 % g1;
	g0=g1;
	g1 = rem;
	savev0=v0;
	v0 = v1;
	v1 = savev0 - (v1*q);
    }
    assert (g0==1);

    //IMPORTANT - since we're dealing wih signs, if we end up with a negative
    // number, for some reason the positive equivalent was off by 1.  so add
    // 1 to value if negative result was found.  Not sure why.
    if (v0 >1)
       return v0;
    else
       return 1+v0;
} // end inv


//****************************************
// based on the 52 encryption subkeys, find
// tje 52 decryption subkeys (16 bit)
//****************************************
void CIdea::calcDKeys ()
{

    //*** 1st,4th  subkey for each round
    for (int i=0;i<NUMSUBKEYS;i+=6) {
    	dsubkeys[i] = inv(esubkeys[48-i]);
    	dsubkeys[i+3] = inv(esubkeys[48-i+3]);
    }


    //*** 2nd, 3rd  subkey for each round
    dsubkeys[1] = -1 * esubkeys[49]; //first round
    dsubkeys[2] = -1 * esubkeys[50]; //first round

    for (int p =7; p<NUMSUBKEYS;p+=6) {
    	dsubkeys[p] = -1 * esubkeys[51-p]; 
    	dsubkeys[p+1] = -1 * esubkeys[50-p]; 
    }
    dsubkeys[49] = -1 * esubkeys[1]; //last round
    dsubkeys[50] = -1 * esubkeys[2]; //last round



    //*** 5th, 6th subkey for each round
    for (int u=4; u< (NUMSUBKEYS) ; u+=6) {
	dsubkeys[u] = esubkeys[50-u];
	dsubkeys[u+1] = esubkeys[51-u];
    }


    int count=1;
    for (int k=0; k<NUMSUBKEYS;k++) {
        if (k%6 ==0) {
	    //IY cout <<"\nDSUBKEYS FOR ROUND " << count << endl;
            count++;
        }
        //IY cout <<"subkey "  << k << " = " << dsubkeys[k]<<endl;
    }
} //end calcDKeys



//****************************************
// Takes original 128 bit key which is
// passed in as array of bytes and
// calculate encryption subkeys (52 total - 16 bits)
//****************************************
void CIdea::calcEKeys(unsigned char* userkey)
{


    //keys from example
    //char userkey[16];

    //for(int i=0; i<16; i++)
        //userkey[i] = i+1;


    int firstbyte = 0;


    //merge two 8-bit sections into one 16 bit!!!
    // this is done by bitwise shifting.  most of logic in this
    // funciton is because of this



    for (int j=0; j<8;j++) {
        esubkeys[j] = (userkey[firstbyte] <<8) + userkey[firstbyte+1];
        firstbyte = firstbyte+2; 
    }


    for (int f=8; f<NUMSUBKEYS-4;f+=8) {
        //shift 25 bits. 
        //if we're on subkey 1, then get last 7 bits of subkey 2, and
        //first 9 bits of subkey 2
    
        // first 6 subkeys
        for (int n=0;n<6;n++) {
            esubkeys[f+n] = (short) ((esubkeys[f+n-7] <<9) | (esubkeys[f+n-6] >>7));
        }

        // next 2 esubkeys
        esubkeys[f+6] = (short) ((esubkeys[f+6-7] <<9) | (esubkeys[f+6-6-8]>>7));
        esubkeys[f+7] = (short) ((esubkeys[f+7-7-8] <<9) | (esubkeys[f+7-6-8]>>7));
    }

    // subkeys 48-51
    esubkeys[NUMSUBKEYS-4] = (short) ((esubkeys[NUMSUBKEYS-4-7] <<9) | (esubkeys[NUMSUBKEYS-4-6] >>7));
    esubkeys[NUMSUBKEYS-4+1] = (short) ((esubkeys[NUMSUBKEYS-4+1-7] <<9) | (esubkeys[NUMSUBKEYS-4+1-6] >>7));
    esubkeys[NUMSUBKEYS-4+2] = (short) ((esubkeys[NUMSUBKEYS-4+2-7] <<9) | (esubkeys[NUMSUBKEYS-4+2-6] >>7));
    esubkeys[NUMSUBKEYS-4+3] = (short) ((esubkeys[NUMSUBKEYS-4+3-7] <<9) | (esubkeys[NUMSUBKEYS-4+3-6] >>7));
    

    int count=1;
    for (int k=0; k<NUMSUBKEYS;k++) {
        if (k%6 ==0) {
	     //cout <<"\nSUBKEYS FOR ROUND " << count << endl;
            count++;
        }
        //cout <<"subkey "  << k<< " = " << esubkeys[k]<<endl;
    }
} //end calcEKeys


//****************************************
// prompt the user to enter either plaintext
// or ciphertext. puts value in array
// that is passed in 
//****************************************
void CIdea::promptForText(unsigned char* ptext,int encryptionflag,int i)
{
	for ( int j = 0 ; j < 8 ; j ++ )
	{
		ptext[j] = m_plainString.GetAt(8*i+j);
	}
} //prompt for plaintext


//****************************************
// We have to prompt user to enter 128 bit
// key.  since we only have 1 byte chars
// make the user enter 16 characters, which
// we convert to 128 bit key 
//****************************************
void CIdea::promptForKey()
{
    for (int i=0;i<16;i++) {
	//origkeychar[i] = str[i];
	origkeychar[i] = m_key.GetAt(i);
        
    }
    origkeychar[16]='\0';
    //translate to hex
    int firstbyte = 0;
    for (int j=0; j<4;j++) {
        //merge two 8-bit sections into one 16 bit
        origkeyint[j] = (origkeychar[firstbyte] <<24) + (origkeychar[firstbyte+1]<<16)
			+ (origkeychar[firstbyte+2]<<8) + (origkeychar[firstbyte+3]);
        firstbyte = firstbyte+4;
    }
} //end promptForKey
void CIdea::ByteToBit(bool *Out, const unsigned char *In, int bits)
{
    for(int i=0; i<bits; i++)
        Out[i] = (In[i/8]>>(i%8)) & 1;
}
void CIdea::BitToByte(unsigned char *Out, const bool *In, int bits)
{
    memset(Out, 0, (bits+7)/8);
    for(int i=0; i<bits; i++)
        Out[i/8] |= In[i]<<(i%8);
}