I am new to coding and I wanted some help with understanding what could be the problem with my DES encryption implementation. I keep getting an Abort trap: 6 error but am unsure about the cause.
My tries have included: - going through with print statements to determine errors.
I have an idea that my encrypt function is the culprit, for when I run other functions by themselves they work just fine. every statement executes before the return function of encrypting; However, after the return statement, I get the abort trap: 6 error.
'''
BEFORE ENDING TO ENCRYPT
/bin/sh: line 1: 39098 Abort trap: 6 ./DES
[Finished in 1.9s with exit code 134]
[cmd: pwd && g -c src/*.cpp -I /usr/local/include -I /Users/username/Desktop/coding_stuff/dev/DES/include -std=c 14 -g -Wall -m64 && g *.o -o bin/debug/DES -L /usr/local/lib && cd bin/debug && ./DES]
[dir: /Users/username/Desktop/coding_stuff/dev/DES]
[path: /Library/Frameworks/Python.framework/Versions/3.9/bin:/usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/share/dotnet:~/.dotnet/tools:/Library/Apple/usr/bin:/Library/Frameworks/Mono.framework/Versions/Current/Commands]
'''
I am on Mac OS Monterey and am using Sublime Text editor for my project.
I apologize if my code seems to be a bit messy, Thank you!!
My DES.h file
'''
#include <iostream>
#include <string>
#ifndef _DES_
#define _DES_
class DES
{
public:
DES(){}; // default constructor
std::string shiftbits(std::string bits, int n /* number of shifts*/, char dir);
std::string xOr(std::string s1, std::string s2); // does XOR of two std::strings
std::string expansion_ri(std::string s1, std::string input32bit); // expansion of 32_bit
std::string encrypt(std::string plain_txt, std::string key);
std::vector<std::string> key_sched_des(std::string key);
std::string F(std::string subkey, std::string right_block);
private:
// This is the PC_1 vector
const int pc_1[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 };
int num_leftShift[16] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; // number of bits to shift for each iteration
// This is the PC_2 vector that shrinks 64_bit input to 56 bits
const int pc_2[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 };
// This vector is the inital permutatinon table
const int IP_t[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 };
// expansion table for F function
const int E_t[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 };
// these are the S-boxes in a 3d array where the first value is the number of S-boxes, second is the rows and third is the columns for the S-boxes
int S[8][4][16] = { // S-box
{
{ 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,5 },
{ 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 }
}
};
// The permutation table for the F funciton
const int P[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 };
// This is the final permutation table for the end of the encryption/decryption
const int P_1[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 };
};
#endif
'''
This is my DES.cpp file
'''
#include "DES.h"
#include <vector>
#include <math.h>
#include <sstream>
int bit_to_dec(std::string num);
std::string Dec_to_Bin(int n);
std::string DES::shiftbits(std::string bits, int n, char dir)
{
std::string temp = "";
if(dir =='l') // shift to left
{
for(std::size_t i = n; i < bits.size();i ) // prints bits from n to length of std::string
temp = bits[i];
for(std::size_t i = 0; i < n;i ) // then prints from 0 to n
temp = bits[i];
} else //shift to the right
{
int diff = bits.length() - n;
//cout << diff;
for(std::size_t i = diff; i < bits.length(); i )
temp = bits[i];
//cout << temp;
for(std::size_t i = 0; i < diff; i )
temp = bits[i];
}
return temp;
}
std::string DES::xOr(std::string x1, std::string x2)
{
std::string Xor = "";
int bigest;
if(x1.size() > x2.size())
bigest = x1.size();
else
bigest = x2.size();
for(int i = 0; i < bigest; i )
{
if((x2[i] == '0' && x1[i] == '1')||(x2[i] == '1' && x1[i] == '0'))
Xor = '1';
else if(x2[i] == '0' && x1[i] == '0')
Xor = '0';
else if(x2[i] == '1' && x1[i] == '1')
Xor = '0';
}
return Xor;
}
std::string DES::expansion_ri(std::string s1, std::string input32bit)
{
std::string str_temp = "";
for(int i = 0; i < 48 /*The expansion of bits*/; i )
str_temp = input32bit[E_t[i] - 1]; // go through every bit position in table
return str_temp;
}
std::vector<std::string> DES::key_sched_des(std::string key) // key schedule for des. returns a vector of subkeys
{
std::string key64 = key;
std::string key56;
for(int i = 0; i < 56; i )
key56 = key64[pc_1[i] - 1];
// splits key into left and right
std::string left;
for(int i = 0; i < 28; i )
left = key56[i];
std::string right;
for(int i = 28; i < 56; i )
right = key56[i];
// first left shift in key schedule
std::vector<std::string> lef_key(16), rig_key(16);
rig_key[0] = shiftbits(right, num_leftShift[0], 'l');
lef_key[0] = shiftbits(left, num_leftShift[0], 'l');
for(int i = 1; i < 16; i ) // fills up the keys and the bits are shifted by corresponding shift table
{
rig_key[i] = shiftbits(rig_key[i - 1], num_leftShift[i], 'l');
lef_key[i] = shiftbits(lef_key[i - 1], num_leftShift[i], 'l');
}
// merge left and right previous keys to enject into pc_2
std::vector<std::string> merge(16), subkey(16);
for(int i = 0; i < 16; i )
{
merge[i] = "";
merge[i] = lef_key[i] rig_key[i];
}
// permutates merged left and right boxes
for(int i = 0; i < 16; i )
{
for(int z = 0; z < 48; z )
{
subkey[i] = merge[i][pc_2[z] - 1];
}
}
return subkey;
}
std::string DES::F(std::string subkey, std::string right_block) //F function
{
std::string expand = "";
for(int i = 0; i < 48; i )
expand = right_block[E_t[i] - 1];
// std::cout << "expanded right block:" << expand << std::endl;
// std::cout << "*****************************\n";
std::string exceptOR;
exceptOR = xOr(expand, subkey);
// std::cout << "xor value:" << exceptOR << std::endl;
// std::cout << "*****************************\n";
// take S box calculation by 6 bits at a time
int z = 0;
std::string comb_sbox = "";
for(int i = 0; i < 48; i = 6)
{
std::string row_bits = "";
std::string column_bits = "";
row_bits = exceptOR[i];
row_bits = exceptOR[i 5];
for(int j = i 1; j < i 5; j )
column_bits = exceptOR[j];
// std::cout << "row:" << row_bits << std::endl;
// std::cout << "*****************************\n";
// std::cout << "column:" << column_bits << std::endl;
// std::cout << "*****************************\n";
// take bits and map to each S box
int row = bit_to_dec(row_bits);
int column = bit_to_dec(column_bits);
int sbox = S[z][row][column];
// std::cout << "number:" << sbox << std::endl;
std::string sbox_bin = Dec_to_Bin(sbox);
// std::cout << sbox_bin << std::endl;
// std::cout << "*****************************\n";
// need to combine sbox values and then use permutaiton
// switch up values
comb_sbox = sbox_bin;
z ;
}
//std::cout << comb_sbox << std::endl;
std::string permutate;// permutate the Sbox combination
for(int i = 0; i < 32; i )
permutate = comb_sbox[P[i] - 1];
return permutate;
}
std::string DES::encrypt(std::string plain_txt, std::string key)
{
// set up keys
std::vector<std::string> sub_strs;
sub_strs = key_sched_des(key);
// do inital permutations
std::string IP = "";
for (int i = 0; i < 64; i )
IP = plain_txt[IP_t[i] - 1];
std::string left[16], right[16];
// stores bits into left and right
for(int i = 0; i < 32; i )
{
left[0] = IP[i];
}
for(int i = 32; i < 64; i )
{
right[0] = IP[i];
}
for(int i = 0; i < 16; i ) //16 rounds
{
std::string sub_key = F(sub_strs[i], right[i]);
right[i 1] = xOr(left[i], sub_key); // l - 1 because previous left was used
left[i 1] = right[i];
}
//combine the std::strings of bits into one 64 bit block
std::string combined = "";
for(int i = 0; i < 32;i )
combined = right[15][i];
for(int i = 0; i < 32;i )
combined = left[15][i];
//do final permutation of block
std::string final_perm = "";
for(int i = 0; i < 64; i )
final_perm = combined[P_1[i] - 1];
std::cout << "BEFORE ENDING TO ENCRYPT" << std::endl;
return final_perm;
}
std::string Dec_to_Bin(int n)
{
std::string binary = "";
while (n > 0)
{
std::string temp;
std::stringstream tmp;
tmp << (n % 2);
tmp >> temp;
binary = temp binary;
n /= 2;
}
while(binary.size() < 4)
binary = '0' binary;
return binary;
}
int bit_to_dec(std::string num)
{
int sum = 0;
for(int i = 0; i < num.size(); i )
{
int value = num.size() - 1;
value -= i;
if(num[i] == '1')
{
sum = 1 * pow(2, value);
}else // then is 0
{
sum = 0 * pow(2, value);
}
}
return sum;
}
'''
This is my main.cpp
'''
#include <iostream>
#include <string>
#include <bitset>
#include "DES.h"
#include <vector>
#include <math.h>
using namespace std;
string txttoBits(string str); // turns string into a string of bits
int bit_to_dec(std::string num);
// This program implments the DES symmetric encryption protocol
int main()
{
DES obj;
// key needs to be 64 bits
string temp = obj.encrypt("1010101011010100000011111101000101000100100101001001000010100000", "0100111111111111000010111111011110001110101100110100000000000000");
std::cout << "AFTER ENDING OF ENCRYPT" << std::endl;
//obj.F("110101000000111111010001010001001101111101010111","00010001010111111111001010010010");
// cout << "would you like to encrypt or decrypt your text?(E for encrypt, D for Decrypt):";
// char encOrdec;
// cin >> encOrdec;
// if(encOrdec == 'E')
// {
// cout << "please enter the text you would like to Encrypt:" << endl;
// cin.ignore();
// string plain_txt;
// getline(cin, plain_txt)
// vector<string> enc_text = obj.encrypt(/*value of the string*/)
// cout << "The encrypted text is:" << enc_text[0] << endl;
// cout << "The key is:" << enc_text[1] << endl;
// }
// else if(encOrdec == 'D')
// {
// cout << "please enter the text you would like to Decrypt:" << endl;
// cin.ignore();
// string cipher_txt;
// getline(cin, cipher_txt)
// vector<string> enc_text = obj.decrypt(/*value of the string*/)
// cout << "The decrypted text is:" << enc_text[0] << endl;
// cout << "The key is:" << enc_text[1] << endl;
// }
return 0;
}
string txttoBits(string str)
{
string bitstring = "";
for(std::size_t i = 0; i < str.size(); i )
{
bitstring = bitset<8>(str[i]).to_string();
}
return bitstring;
}
'''
For my main obj.Encrypt(), the 0's and 1's are just random binary. This is just a test on 64 bit binary an a 64 bit key to determined if the function worked.
CodePudding user response:
Here is at least one of the issues. You are overwriting the bounds of the string array here:
std::string left[16], right[16];
//...
for (int i = 0; i < 16; i ) //16 rounds
{
std::string sub_key = F(sub_strs[i], right[i]);
right[i 1] = xOr(left[i], sub_key); // <-- What happens when i == 15?
....
}
The commented line basically points out the issue. You are accessing right[16]
, which is out-of-bounds.
As to the bit_to_dec
function, that could be done in a single line of code:
#include <bitset>
//...
int bit_to_dec(std::string num)
{
return static_cast<int>(std::bitset<32>(num).to_ulong());
}
This removes the usage of pow()
, which is a floating point function. If you introduce floating point into a program that clearly is all integer-based, you risk introducing floating point issues such as rounding, etc.
CodePudding user response:
The problem is that for the last iteration(when i = 15
) of the for
loop(shown below) inside encrypt
member function, you are going out of bounds of the std::string
named right
and left
which leads to undefined behavior.
for(int i = 0; i < 16; i ) //16 rounds
{
std::string sub_key = F(sub_strs[i], right[i]);
right[i 1] = xOr(left[i], sub_key); // out of bounds here on the left hand side
left[i 1] = right[i]; //out of bound here on the left hand side
}
Undefined behavior means anything1 can happen including but not limited to the program giving your expected output. But never rely(or make conclusions based) on the output of a program that has undefined behavior.
So the output that you're seeing(maybe seeing) is a result of undefined behavior. And as i said don't rely on the output of a program that has UB. The program may just crash.
For example, here the program executes without giving any output while here the same program executes with your expected output.
So the first step to make the program correct would be to remove UB (which in your case means taking care that you don't go out of bounds of the array). Then and only then you can start reasoning about the output of the program.
1For a more technically accurate definition of undefined behavior see this where it is mentioned that: there are no restrictions on the behavior of the program.