Cryptography-Digest Digest #790, Volume #10 Fri, 24 Dec 99 16:13:00 EST
Contents:
DES Problem! ("Daniel Suberviola")
----------------------------------------------------------------------------
From: "Daniel Suberviola" <[EMAIL PROTECTED]>
Subject: DES Problem!
Date: Fri, 24 Dec 1999 14:45:47 -0600
Hello, everyone.
I am a high school senior writing a modified implementation of DES as a
science project. The work is being done in binary for now on a fixed 64-bit
data chunk and a fixed 64-bit key (both very simple), and I will add support
for real-world files once I am able to successfully get the fixed data and
key to encrypt and decrypt. Which brings me to my problem...
The DES algorithm, from what I have read, is supposed to work in both
directions, as long as the key order is reversed during decryption. I have
written and tested functions to handle the various permutations; as far as I
can tell, they work as designed. However, when I attempt to have my program
decrypt the 64-bit block it has just encrypted, I get a completely different
result from what I initially started with.
Below is a copy the current output:
*** ENCRYPTION
Round 0: 00000000111111110000000011111111 11111111000000001111111100000000
(Round 0 is the original plaintext after the initial permutation.)
Round 1: 11111111000000001111111100000000 11101011000010100000011101000101
USING KEY 010011110110110100110101001010101111110110101011
Round 2: 11101011000010100000011101000101 10001101100011111100010011100110
USING KEY 010011111110010100101101001011100111110110101011
Round 3: 10001101100011111100010011100110 01110011110100101001001100001100
USING KEY 110010111000010110101111101011100101100101110011
Round 4: 01110011110100101001001100001100 10000000011001110010011010001101
USING KEY 111110011000101010101011110001111100101101110010
Round 5: 10000000011001110010011010001101 11001101110011001111111001100100
USING KEY 101100011011101010101010110101011000111101011000
Round 6: 11001101110011001111111001100100 00100010000111010010010010111111
USING KEY 101100000011111011010110110110011001011001011100
Round 7: 00100010000111010010010010111111 01100110010001001010010100111000
USING KEY 011101000111111001010100010110011111011010101100
Round 8: 01100110010001001010010100111000 00111100010001000000111110111001
USING KEY 010001101111010101110100001110000111110010101101
Round 9: 00111100010001000000111110111001 01001000100011010100000000101101
USING KEY 110001101110010101110101001110100111110010110101
Round 10: 01001000100011010100000000101101 00101111101000010000101111001110
USING KEY 110011111100011100110011101010110110100110110011
Round 11: 00101111101000010000101111001110 00101010110100010000000111000001
USING KEY 111011111001001110101011101001110110101100010011
Round 12: 00101010110100010000000111000001 00111110110010110100000110010010
USING KEY 101110111001001011001011111101110000001101010110
Round 13: 00111110110010110100000110010010 11110101011110011010011110100001
USING KEY 001110010101101011011010110101011000001111001110
Round 14: 11110101011110011010011110100001 00001101011110100100111101000100
USING KEY 001101000111100111011100010101001011011011001101
Round 15: 00001101011110100100111101000100 00111100101110100000001100000011
USING KEY 000101100110110101010101011110101011010011101101
Round 16: 00111100101110100000001100000011 11011111101010111010100101100011
USING KEY 010111100110110101010101011010101111010010101111
*** DECRYPTION
Round 0: 00111100101110100000001100000011 11011111101010111010100101100011
(Round 0 is the original ciphertext after the initial permutation.)
Round 1: 11011111101010111010100101100011 11000101101111100001110001010111
USING KEY 010111100110110101010101011010101111010010101111
Round 2: 11000101101111100001110001010111 11011110111010010000111100110011
USING KEY 000101100110110101010101011110101011010011101101
Round 3: 11011110111010010000111100110011 10011110111110101111101100111001
USING KEY 001101000111100111011100010101001011011011001101
Round 4: 10011110111110101111101100111001 10111111110101111010110101010110
USING KEY 001110010101101011011010110101011000001111001110
Round 5: 10111111110101111010110101010110 01101110011101111111000111001000
USING KEY 101110111001001011001011111101110000001101010110
Round 6: 01101110011101111111000111001000 11100100100011010001011010111000
USING KEY 111011111001001110101011101001110110101100010011
Round 7: 11100100100011010001011010111000 00011100000100000001001100011111
USING KEY 110011111100011100110011101010110110100110110011
Round 8: 00011100000100000001001100011111 11010101011101100101100100101101
USING KEY 110001101110010101110101001110100111110010110101
Round 9: 11010101011101100101100100101101 10010000110000010011101111101100
USING KEY 010001101111010101110100001110000111110010101101
Round 10: 10010000110000010011101111101100 00011001010110100000000110101110
USING KEY 011101000111111001010100010110011111011010101100
Round 11: 00011001010110100000000110101110 11111110101111011100010111000110
USING KEY 101100000011111011010110110110011001011001011100
Round 12: 11111110101111011100010111000110 01111010110101000111011110001001
USING KEY 101100011011101010101010110101011000111101011000
Round 13: 01111010110101000111011110001001 11011010001011111110101000110010
USING KEY 111110011000101010101011110001111100101101110010
Round 14: 11011010001011111110101000110010 10000001101100101000001001101000
USING KEY 110010111000010110101111101011100101100101110011
Round 15: 10000001101100101000001001101000 10111011100001000100010000100100
USING KEY 010011111110010100101101001011100111110110101011
Round 16: 10111011100001000100010000100100 11011110011001000100111101100011
USING KEY 010011110110110100110101001010101111110110101011
Plaintext: 01001010110010101011110111001000 11000000011000111010111011010000
Clearly, this end result does not equal the initial plaintext.
Could someone please examine my source code (reproduced in full below) and
let me know where my error(s) lie and/or post fixes here or e-mail me at
[EMAIL PROTECTED]? Please focus your efforts on Main.cc and DES.cc; the use of
class LargeInt may be awkward, but it does function correctly.
Please note that the files below were written on Red Hat Linux 5.2 and
compiled with g++. I have been unable to get them to compile on other
platforms: Microsoft Visual C++ 5.0 gives me multiple initialization errors
and errors when dimensioning an array with a variable.
Thank you very much for your time!!!
Daniel Suberviola
[EMAIL PROTECTED]
=========================
Main.cc
// Main.cc
// Main function of the DES Project
// Includes
#include <iostream.h>
#include <math.h>
#include "LargeInt.h"
#include "LargeIntMisc.h"
#include "DES.h"
// Definitions
#define KEY
"1010101010101010101010101010101010101010101010101010101010101010"
#define TXT
"1001100110011001100110011001100110011001100110011001100110011001"
#define STRING32 "00000000000000000000000000000000"
// Function Prototypes
int main(void);
void PreCalcEncKeys(LargeInt keys[][16], LargeInt startkey[]);
void PreCalcDecKeys(LargeInt keys[][16], LargeInt startkey[]);
int main(void)
{
/***** START ENCRYPTION *****/
// Variable declarations
LargeInt startkey[3], keys[3][16], enckeys[3][16], deckeys[3][16];
LargeInt text, left[17], right[17];
// Initial permutation
text = TXT;
text = ip(text);
// Split into two halves
left[0] = text.segment(1, 32);
right[0] = text.segment(33, 64);
// Temporary fixed values; will need to be altered later
for(int i = 0; i < 3; i++)
startkey[i] = KEY;
// Pre-calculate the keys that will be needed
PreCalcEncKeys(enckeys, startkey);
cout << "Round 0:\t" << text.segment(1, 32) << ' ' << text.segment(33, 64)
<< endl;
// Encrypt
for(int i = 1; i <= 16; i++) {
left[i] = right[i-1];
right[i] = left[i-1] ^ (pbox(sboxes(ep(right[i-1]) ^ enckeys[0][i-1])));
LargeInt temp = left[i] + right[i];
cout << "Round " << i << ":\t" << temp.segment(1, 32) << ' '
<< temp.segment(33, 64) << endl;
cout << "USING KEY\t" << enckeys[0][i-1] << endl << endl;
}
LargeInt concatenated = left[16] + right[16];
LargeInt ciphertext = fp(concatenated);
/***** END ENCRYPTION *****/
/***** START DECRYPTION *****/
// Initial permutation
text = ciphertext;
text = ip(text);
// Split into two halves
left[0] = text.segment(1, 32);
right[0] = text.segment(33, 64);
// Temporary fixed values; will need to be altered later
for(int i = 0; i < 3; i++)
startkey[i] = KEY;
// Pre-calculate the keys that will be needed
PreCalcDecKeys(deckeys, startkey);
cout << "Round 0:\t" << text.segment(1, 32) << ' ' << text.segment(33, 64)
<< endl;
// Decrypt
for(int i = 1; i <= 16; i++) {
left[i] = right[i-1];
right[i] = left[i-1] ^ (pbox(sboxes(ep(right[i-1]) ^ deckeys[0][i-1])));
LargeInt temp = left[i] + right[i];
cout << "Round " << i << ":\t" << temp.segment(1, 32) << ' '
<< temp.segment(33, 64) << endl;
cout << "USING KEY\t" << deckeys[0][i-1] << endl << endl;
}
concatenated = left[16] + right[16];
ciphertext = fp(concatenated);
cout << "Plaintext:\t" << ciphertext.segment(1, 32) << ' '
<< ciphertext.segment(33, 64) << endl;
/***** END DECRYPTION *****/
return 0;
}
// ************************************************************************
// Function Name: PreCalcEncKeys
//
// Task --
// Perform the encryption of the plaintext
//
// Input --
// LargeInt keys[][16]: The two-dimensional array of all keys.
// LargeInt startkey[]: The array of starting keys.
//
// Output --
// None.
// ************************************************************************
void PreCalcEncKeys(LargeInt keys[][16], LargeInt startkey[])
{
LargeInt basekey[3];
for(int i = 0; i < 1; i++) {
// Reduce the initial key from 64 to 56 bits
basekey[i] = reduce(startkey[i]);
// Perform the shifting
for(int j = 0; j < 16; j++) {
int shiftval;
switch(j+1)
case 1:
case 2:
case 9:
case 16:
shiftval = 1;
break;
default:
shiftval = 2;
break;
};
// permute the basekey, set it as base in the next round
basekey[i] = kp(basekey[i], shiftval);
// compress it for this round
keys[i][j] = cp(basekey[i]);
}
}
}
// ************************************************************************
// Function Name: PreCalcDecKeys
//
// Task --
// Perform the decryption of the plaintext
//
// Input --
// LargeInt keys[][16]: The two-dimensional array of all keys.
// LargeInt startkey[]: The array of starting keys.
//
// Output --
// None.
// ************************************************************************
void PreCalcDecKeys(LargeInt keys[][16], LargeInt startkey[])
{
LargeInt basekey[3];
for(int i = 0; i < 1; i++) {
// Reduce the initial key from 64 to 56 bits
basekey[i] = reduce(startkey[i]);
// Perform the shifting
for(int j = 0; j < 16; j++) {
int shiftval;
switch(j+1)
case 1:
shiftval = 0;
break;
case 2:
case 9:
case 16:
shiftval = -1;
break;
default:
shiftval = -2;
break;
};
// permute the basekey, set it as base in the next round
basekey[i] = kp(basekey[i], shiftval);
// compress it for this round
keys[i][j] = cp(basekey[i]);
}
}
}
=========================
DES.h
// DES.h
// Function prototypes for the DES implementation.
#ifndef ___DES___
#define ___DES___
// Includes
#include <iostream.h>
#include "LargeInt.h"
// Function prototypes -- see DES.cc for descriptions.
LargeInt reduce(const LargeInt &x);
LargeInt ip(const LargeInt &x);
LargeInt kp(const LargeInt &x, int c);
LargeInt cp(const LargeInt &x);
LargeInt ep(const LargeInt &x);
LargeInt sboxes(const LargeInt &x);
LargeInt pbox(const LargeInt &x);
LargeInt fp(const LargeInt &x);
#endif ___DES___
=========================
DES.cc
// DES.cc
// Implementation of DES functions
// Includes
#include <iostream.h>
#include "DES.h"
#include "LargeInt.h"
#include "LargeIntMisc.h"
// Definitions
#define STRING64
"0000000000000000000000000000000000000000000000000000000000000000"
#define STRING56 "00000000000000000000000000000000000000000000000000000000"
#define STRING48 "000000000000000000000000000000000000000000000000"
#define STRING32 "00000000000000000000000000000000"
#define STRING28 "0000000000000000000000000000"
#define TEXTSIZE 64
#define KEYSIZE 56
#define COMPSIZE 48
#define HALFSIZE 28
// Global variables -- undesirable generally, but practical here
const int IP[64] = {58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20,
12,
4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24,
16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27,
19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39,
31, 23, 15, 7};
const int KP[56] = {57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4};
const int CP[48] = {14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32};
const int EP[48] = {32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1};
const int SBOX[8][64] = {{14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0,
7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13},
{15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 3,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9},
{10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12},
{7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14},
{2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3},
{12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13},
{4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12},
{13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}};
const int PBOX[32] = {16, 7, 20, 21, 29, 12, 28, 17,
1, 15, 23, 26, 5, 18, 31, 10,
2, 8, 24, 14, 32, 27, 3, 9,
19, 13, 30, 6, 22, 11, 4, 25};
const int FP[64] = {40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23,
63,
31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21,
61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51,
19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9,
49, 17, 57, 25};
// ************************************************************************
// Function Name: reduce
//
// Task --
// Reduce the DES key from 64 bits to 56 bits while also rearranging the
// bit order.
//
// Input --
// const LargeInt &x: The key, passed by reference. Its value is protected
// with const.
//
// Output --
// LargeInt r: The resultant key.
// ************************************************************************
LargeInt reduce(const LargeInt &x)
{
LargeInt r = STRING56; // Create a 56-number LargeInt
for(int i = 0; i < KEYSIZE; i++)
r.setVal(i+1, x.getVal(KP[i])); // Rearrange as indicated by KP[]
return r; // Return the new LargeInt
}
// ************************************************************************
// Function Name: ip
//
// Task --
// Perform the initial permutation on the plaintext.
//
// Input --
// const LargeInt &x: The plaintext, passed by reference. Its value is
// protected with const.
//
// Output --
// LargeInt r: The resultant text.
// ************************************************************************
LargeInt ip(const LargeInt &x)
{
LargeInt r = STRING64; // Create a 64-number LargeInt
for(int i = 0; i < TEXTSIZE; i++)
r.setVal(i+1, x.getVal(IP[i])); // Rearrange as indicated by IP[]
return r; // Return the new LargeInt
}
// ************************************************************************
// Function Name: kp
//
// Task --
// Perform the key permutation on the DES key. This involves breaking up
// the key into two halves and then left-shifting the bits of each half
// either once or twice, depending on the round.
//
// Input --
// const LargeInt &x: The key, passed by reference. Its value is protected
// with const.
// int c: The number of times to left-shift the bits. This
// value will be either 1 or 2 for DES.
//
// Output --
// LargeInt r: The resultant key.
// ************************************************************************
LargeInt kp(const LargeInt &x, int c)
{
LargeInt r = STRING56; // Create a 56-number LargeInt
// Cycle the first half of the key, placing the results in r
for(int
i = 0; i < KEYSIZE / 2; i++)
etVal(
(i-c+KEYSIZE / 2) % (KEYSIZE / 2) + 1, x.getVal(i+1) );
}
// Cycle the second half of the key, pl
acing the results in r
for(int i = KEYSIZE / 2; i < KEYSIZE; i++)
r.setVal( (i-c) % (KEYSIZE / 2) + KEYSIZE / 2 + 1, x.getVal(i+1) );
}
return r; // Return the LargeInt
}
// ************************************************************************
// Function Name: cp
//
// Task --
// Perform the compression permutation on the DES key. This involves
// reducing the shifted key from 56 to 48 bits while also rearranging the
// bit order.
//
// Input --
// const LargeInt &x: The shifted key, passed by reference. Its value is
// protected with const.
//
// Output --
// LargeInt r: The resultant key.
// ************************************************************************
LargeInt cp(const LargeInt &x)
{
LargeInt r = STRING48; // Create a 48-number LargeInt
for(int i = 0; i < COMPSIZE; i++)
r.setVal(i+1, x.getVal(CP[i])); // Rearrange as indicated by CP[]
return r; // Return the LargeInt
}
// ************************************************************************
// Function Name: ep
//
// Task --
// Perform the expansion permutation on the text. This involves repetition
// of certain bits in order to increase the number of bits.
//
// Input --
// const LargeInt &x: The text, passed by reference. Its value is protected
// with const.
//
// Output --
// LargeInt r: The resultant text.
// ************************************************************************
LargeInt ep(const LargeInt &x)
{
LargeInt r = STRING48; // Create a 48-number LargeInt
for(int i = 0; i < COMPSIZE; i++)
r.setVal(i+1, x.getVal(EP[i])); // Rearrange as indicated by EP[]
return r; // Return the LargeInt
}
// ************************************************************************
// Function Name: sboxes
//
// Task --
// Perform the
S-Box substitution on
the ciphertext.
//
// Input --
// const LargeInt &x: The text, passed by reference. Its value is protected
// with const.
//
// Output --
// LargeInt r: The resultant ciphertext.
// ************************************************************************
LargeInt sboxes(const LargeInt &x)
{
char y[8][5]; // declare the binary strings
for(int i = 0; i < 8; i++) // set null character at end
y[i][4] = '\0';
for(int i = 1; i <= 8; i++) {
for(int j = 0; j < 4; j++) // zero the strings
y[i-1][j] = '0';
static char row[3] = {'\0'}, col[5] = {'\0'};
// get the values from the LargeInt which determine the new values
// output by the S-Boxes
itoc(x.getVal(6*i-5), row[0]);
itoc(x.getVal(6*i), row[1]);
itoc(x.getVal(6*i-4), col[0]);
itoc(x.getVal(6*i-3), col[1]);
itoc(x.getVal(6*i-2), col[2]);
itoc(x.getVal(6*i-1), col[3]);
// binary --> integer conversion for use in array subscripting
int srow = bin2int(row);
int scol = bin2int(col);
// convert S-Box output values to binary
int2bin(SBOX[i-1][16*srow+scol], y[i-1], 3);
}
// concatenate all of the binary values onto y[0]
for(int i = 1; i <= 7; i++)
strcat(y[0], y[i]);
LargeInt r(y[0]); // create LargeInt r to return
return r; // return r
}
// ************************************************************************
// Function Name: pbox
//
// Task --
// Perform the initial permutation on the plaintext.
//
// Input --
// const LargeInt &x: The ciphertext, passed by reference. Its value is
// protected with const.
//
// Output --
// LargeInt r: The resultant ciphertext.
// ************************************************************************
LargeInt pbox(const LargeInt &x)
{
LargeInt r = STRING32; // Create a 32-number LargeInt
for(int i = 0; i < 32; i++)
r.setVal(i+1, x.getVal(PBOX[i]))
; // Rearrange
as indicated by PBOX[]
return r; // Return the new LargeInt
}
// *******************************************************************
*****
// Function Name: fp
//
// Task --
// Perform the final permutation on the ciphertext.
//
// Input --
// const LargeInt &x: The ciphertext, passed by reference. Its value is
// protected with const.
//
// Output --
// LargeInt r: The resultant text.
// ************************************************************************
LargeInt fp(const LargeInt &x)
{
LargeInt r = STRING64; // Create a 64-number LargeInt
for(int i = 0; i < TEXTSIZE; i++)
r.setVal(i+1, x.getVal(FP[i])); // Rearrange as indicated by FP[]
return r; // Return the new LargeInt
}
=========================
LargeInt.h
// LargeInt.h
// Header file for implementation of a large integer as an array of integers.
// Size is limited only by available memory.
#ifndef ___LargeInt___
#define ___LargeInt___
// Includes
#include <iostream.h>
#include <string.h>
class LargeInt {
public:
// CONSTRUCTORS AND DESTRUCTOR
LargeInt(); // Constructor: default, initialize to zero
LargeInt(const char *q); // Constructor: initialize to q (char*)
LargeInt(const int q); // Constructor: initialize to q (int)
LargeInt(const LargeInt &q); // Constructor: initialize to q (LargeInt)
~LargeInt(); // Destructor
// ACCESSORS
int getLength(void) const; // Return length
int getVal(int x) const; // Return position x
void setVal(int x, int n) const; // Set position x
LargeInt segment(int a, int b) const; // Return section [a,b] of LargeInt
// OVERLOADED OPERATORS
LargeInt& LargeInt::operator = (const LargeInt &q);
LargeInt LargeInt::operator + (const LargeInt &q) const;
LargeInt LargeInt::operator ^ (const LargeInt &q) const;
private:
int length; // length of the LargeInt
int *value; // pointer to start of the LargeInt
};
inline ostream& operator << (ostream &os,
const LargeInt &s)
{
for(int i = 1; i <= s.getLength(); i++)
os << s.getVal(i);
return(os);
}
#endif ___LargeInt___
=========================
LargeInt.cc
// LargeInt.cc
// Implementation of LargeInt class.
// Includes
#include <iostream.h>
#include <math.h>
#include "LargeInt.h"
#include "LargeIntMisc.h"
// CONSTRUCTORS AND DESTRUCTORS
// ************************************************************************
// Function Name: LargeInt::LargeInt
//
// Task --
// Default constructor. Creates a LargeInt with value 0 and length 1.
//
// Input --
// None.
//
// Output --
// None.
// ************************************************************************
LargeInt::LargeInt()
{
length = 1;
value = new int[length];
value[0] = 0;
}
// ************************************************************************
// Function Name: LargeInt::LargeInt
//
// Task --
// Character string constructor. Creates a LargeInt with length equal to the
// number of characters in the string and value equal to the characters in
// the string. Both values ignore the '\0' null terminator.
//
// Input --
// const char *q: The null-terminated string of integers.
//
// Output --
// None.
// ************************************************************************
LargeInt::LargeInt(const char *q)
{
// Assign the private variables their appropriate values.
length = strlen(q);
value = new int[length];
// Loop through the string, converting each character into an integer.
for(int i = 0; i < length; i++)
ctoi(q[i], value[i]);
}
// ************************************************************************
// Function Name: LargeInt::LargeInt
//
// Task --
// Integer constructor. Creates a LargeInt with length equal to the number
// of characters in the integer and value equal to the integer itself.
//
// Input --
// const int q: The integer.
//
// Output --
// None.
// ************************************************************************
LargeInt::LargeInt(const int q)
{
// Workaround to prevent a segmentation fault caused by log10(0) = undef.
if(q == 0)
length = 1;
// If no problem, proceed normally, using logs to determine the length of
// the integer.
else
length = (int)(log10(q)+1);
value = new int[length];
// Convert the integer into an array of integers, with each cell a place
// value. See LargeIntMisc.cc for details.
itoai(q, value, length);
}
// ************************************************************************
// Function Name: LargeInt::LargeInt
//
// Task --
// LargeInt copy constructor. Duplicates another LargeInt.
//
// Input --
// const LargeInt &q: The LargeInt to be copied, passed by reference. Its
// value is protected by const.
//
// Output --
// None.
// ************************************************************************
LargeInt::LargeInt(const LargeInt &q)
{
length = q.length;
value = new int[length];
// Copy over the values.
for(int i = 0; i <= length; i++)
value[i] = q.value[i];
}
// ************************************************************************
// Function Name: LargeInt::~LargeInt
//
// Task --
// Destructor. Frees the memory allocated to the array of ints by new.
//
// Input --
// None.
//
// Output --
// None.
// ************************************************************************
LargeInt::~LargeInt()
{
delete [] value;
}
// ACCESSORS
// ************************************************************************
// Function Name: LargeInt::getLength
//
// Task --
// Return the length of the LargeInt. The values of private data members
// are protected by const.
//
// Input --
// None.
//
// Output --
// int length: The length of the LargeInt.
// ************************************************************************
int LargeInt::getLength(void) const
{
return length;
}
// ************************************************************************
// Function Name: LargeInt::getVal
//
// Task --
// Return the integer at a given position in the LargeInt. The values of
// private data members are protected by const.
//
// Input --
// int x: The position in the LargeInt. The first position is 1, NOT 0
// as in an array.
//
// Output --
// int value[x-1]: The value at position x, with 1 subtracted for
// compatibility with the 0-based array subscript.
// ************************************************************************
int LargeInt::getVal(int x) const
{
return value[x-1];
}
// ************************************************************************
// Function Name: LargeInt::setVal
//
// Task --
// Set a given position in the LargeInt to an integer value. The values of
// private data members are protected by const.
//
// Input --
// int x: The position in the LargeInt. The first position is 1, NOT 0
// as in an array.
// int n: The integer to place in position x.
//
// Output --
// None.
// ************************************************************************
void LargeInt::setVal(int x, int n) const
{
value[x-1] = n;
}
// ************************************************************************
// Function Name: LargeInt::segment
//
// Task --
// Return a defined segment of the LargeInt. Private data values are
// protected by const.
//
// Input --
// int a: The lower bound of the segment.
// int b: The upper bound of the segment.
//
// Output --
// LargeInt r: The resultant LargeInt.
// ************************************************************************
LargeInt LargeInt::segment(int a, int b) const
{
// Set up the string used to create the resultant LargeInt.
char dummy[b-a+2];
for(int i = 0; i < b-a+1; i++)
dummy[i] = '5';
dummy[b-a+1] = '\0';
LargeInt r = dummy;
// Copy the appropriate values into the resultant LargeInt.
for(int i = 1; i <= b-a+1; i++)
r.setVal(i, getVal(a+i-1));
return r; // Return the LargeInt.
}
// ************************************************************************
// Function Name: LargeInt::operator + const
//
// Task --
// Combine self with another LargeInt. The values of the data members are
// protected by const.
//
// Input --
// const LargeInt &x: The LargeInt to be added, passed by reference, value
// protected by const.
//
// Output --
// LargeInt r: The resultant LargeInt.
// ************************************************************************
// OVERLOADED OPERATORS
LargeInt LargeInt::operator +(const LargeInt &x) const
{
// Set up the string used to create the resultant LargeInt.
int newlength = length + x.getLength();
char dummy[newlength + 1];
for(int i = 0; i < newlength; i++)
dummy[i] = '5';
dummy[newlength] = '\0';
LargeInt r = dummy;
// Copy over the values from self.
for(int i = 1; i <= length; i++)
r.setVal(i, getVal(i));
// Copy over the values from x.
for(int i = length + 1; i <= newlength; i++)
r.setVal(i, x.getVal(i - length));
return r; // Returns the LargeInt.
}
// ************************************************************************
// Function Name: LargeInt::operator =
//
// Task --
// Overload the XOR operator ^ to permit X1 ^ X2 bit-by-bit XORing of
// LargeInts.
//
// Input --
// const LargeInt &q: The LargeInt to XORed with, passed by reference. Its
// value is protected by const.
//
// Output --
// LargeInt r: The resultant LargeInt.
// ************************************************************************
LargeInt LargeInt::operator ^ (const LargeInt &q) const
{
LargeInt r(q); // Create an appropriately-sized LargeInt (contents
// are irrelevant because they will be replaced
// momentarily. length = r.length at all times,
// so the two values are interchangeable.
for(int i = 1; i <= length; i++)
r.setVal(i, getVal(i) ^ q.getVal(i));
return r;
}
// ************************************************************************
// Function Name: LargeInt::operator =
//
// Task --
// Overload the assignment operator = to permit X1 = X2 copying of
// LargeInts. However, it also works for integers and strings. It is
// unclear at this time why it is so powerful, even though this anomoly
// is certainly beneficial.
//
// Input --
// const LargeInt &q: The LargeInt to be copied, passed by reference. Its
// value is protected by const.
//
// Output --
// LargeInt&: The address of the LargeInt just created, so that the =
// operator can support chaining.
// ************************************************************************
LargeInt& LargeInt::operator = (const LargeInt &q)
{
length = q.length;
value = new int[length];
for(int i = 0; i <= length; i++)
value[i] = q.value[i];
return *this;
}
=========================
LargeIntMisc.h
// LargeIntMisc.h
// Function prototypes for LargeInt miscellaneous utility functions.
#ifndef __LargeIntMisc___
#define __LargeIntMisc___
// Includes
#include <iostream.h>
// Function Prototypes -- see LargeIntMisc.cc for descriptions.
void itoc(int x, char &y);
void itoai(int x, int *y, int l);
void ctoi(char x, int &y);
int extractFromInt(int x, int l, int d);
void int2bin(int x, char *y, int max);
int bin2int(char *x);
#endif ___LargeIntMisc___
=========================
LargeIntMisc.cc
// LargeIntMisc.cc
// Implementation of LargeInt miscellaneous utility functions that are
// not member functions.
// Includes
#include <iostream.h>
#include <math.h>
#include "LargeIntMisc.h"
// ************************************************************************
// Function Name: itoc
//
// Task --
// Convert an integer into a character.
// Example: int 9 --> char '9'
//
// Input --
// int x: The integer.
// char &y: The character, passed by reference.
//
// Output --
// None.
// ************************************************************************
void itoc(int x, char &y)
{
y = (char)(x+48);
}
// ************************************************************************
// Function Name: itoai
//
// Task --
// Convert an integer into an array of integers.
// Example: int 98765 --> int[5] = {9, 8, 7, 6, 5}
//
// Input --
// int x: The integer.
// int *y: The pointer to the array of integers.
// int l: The length of the array.
//
// Output --
// None.
// ************************************************************************
void itoai(int x, int *y, int l)
{
for(int i = 0; i < l; i++)
y[i] = extractFromInt(x, l, i+1);
}
// ************************************************************************
// Function Name: ctoi
//
// Task --
// Convert a character into an integer.
// Example: char '9' --> int 9
//
// Input --
// char x: The character.
// int &y: The integer, passed by reference.
//
// Output --
// None.
// ************************************************************************
void ctoi(char x, int &y)
{
y = (int)x-48;
}
// ************************************************************************
// Function Name: extractFromInt
//
// Task --
// Extracts a given digit of an integer.
// Example: int 98765, digit 2 --> 8
//
// Input --
// int x: The integer.
// int l: The length of the integer.
// int d: The digit of the integer requested.
//
// Output --
// int interim: The digit requested.
// ************************************************************************
int extractFromInt(int x, int l, int d)
{
// Divide the number by a power of 10 such that only one number precedes
// the decimal point.
double interim = (double) x / pow(10, l-1);
// If there are numbers beyond the decimal point, subtract the integer
// portion of the number and multiply by 10 so that a new number is
// formed that has only one digit preceding the decimal point. This
// process is repeated until no digits follow the decimal point.
for(int i = d-1; i > 0; i--) {
interim -= (int) interim;
interim *= 10.0;
}
// Workaround for a bizarre anomaly that floor(x) = x-1 on occasion, and
// only for the last digit in the integer. The problem has been observed
// on both my home Red Hat Linux 5.2 system and on UWM's DEC Alphas. The
// problem may be due to internal rounding of the doubles. The workaround
// is to average the number, the number rounded down, and the number
// rounded up. Since two of those numbers are always correct, the average
// can be rounded to the nearest integer to yield the correct value.
if(d == l && l > 1) {
double a = interim, b = floor(interim), c = ceil(interim);
return (int) (floor( (a+b+c) / 3 + 0.5));
}
else
return (int) interim;
}
// ************************************************************************
// Function Name: int2bin
//
// Task --
// Convert an integer into a binary string.
//
// Input --
// int x: The integer.
// char *y: The character string. It is assumed that the array has been
// set up appropriately and initialized with zeroes.
// int max: The highest power of 2 less than or equal to x.
//
// Output --
// None.
// ************************************************************************
void int2bin(int x, char *y, int max)
{
for(int i = 0; i <= max; i++) {
int k = (int) pow(2, max - i);
if(x >= k) {
y[i] = '1';
x -= k;
}
if(x == 0)
break;
}
}
// ************************************************************************
// Function Name: bin2int
//
// Task --
// Convert a binary string into an integer.
//
// Input --
// char *x: The binary string.
//
// Output --
// int r: The resultant integer.
// ************************************************************************
int bin2int(char *x)
{
int r = 0, max = 0, t;
for(max = 0; ; max++)
if(x[max] == '\0')
break;
for(int i = 0; i < max; i++) {
ctoi(x[i], t);
r += (int) pow(2, max - i - 1) * t;
}
return r;
}
=========================
END
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
