#include <iostream>
#include <list>
#include <cstring>
#include <crypt.h>

using namespace std;


string target_salt = "$6$SQaRdxYU$";
string target_pw_hash   = "$6$SQaRdxYU$5aZhtfRTrel3MsHoOek5ZZYZfY6/wiw4lPf3iw2yTXVQJEmwPMnadlQPh09RCkH/cMSnAbGhdH3.GvqjG.6w0.";

#define MAX_LEN 30

list<char*> pwlist;

int check_password(char* pw, char* salt, char* hash)
{
char* res = crypt(pw, salt);
cout << "password " << pw << "\n";
 //cout << "hashes to " << res << "\n";
 for (int i = 0; i<strlen(hash); i++)
    if (res[i]!=hash[i])
    return 0;
 cout << "match !!!" << "\n";
 return 1;
}

char* exhaustive_search(char* charset, char* salt, char* target)
{
char* current_password;
char* new_password;
char* cst_pass;
int i, current_len;
int cnta=0,cnts=0,cntr=0,k;

cst_pass=new char[9];
strcpy(cst_pass,"Luni16:00");
cst_pass[9]='\0';
current_len=strlen(cst_pass);
for(i = 0; i<strlen(charset); i++)
    {
    new_password = new char[current_len+2];
    strcpy(new_password,cst_pass);
    new_password[current_len] = charset[i];
    new_password[current_len+1] = '\0';
    pwlist.push_back(new_password);
    }

while(true){

if (pwlist.empty())
    return NULL;
current_password = pwlist.front();
current_len = strlen(current_password);


 k=1;
 cnta=0;
 cnts=0;
 cntr=0;
 for(int j=0;j<current_len;j++)
 {
    if(current_password[j]=='a')
        cnta++;
    if(current_password[j]=='s')
        cnts++;
    if(current_password[j]=='r')
        cntr++;
    if(cnta>1 or cntr>1 or cnts >1)
    {
        k=0;
        break;
    }
}
if(k==1)
    if (check_password(current_password,    salt,   target))
        return current_password;

if(current_len < MAX_LEN)
{
    for (i = 0; i < strlen(charset); i++)
    {
    new_password = new char[current_len + 2];
    memcpy(new_password, current_password, current_len);
    new_password[current_len] = charset[i];
    new_password[current_len+1] = '\0';
    current_len=strlen(new_password);
    pwlist.push_back(new_password);
    }
}
pwlist.pop_front();
}
}

int main()
{
 char* salt;  char* target;  char* password;
 char charset[] = {'a', 'e', 'r', 't', 's', '\0'};
 salt = new char[target_salt.length()+1];
 copy(target_salt.begin(), target_salt.end(), salt);
 target = new char[target_pw_hash.length()+1];
 copy(target_pw_hash.begin(), target_pw_hash.end(), target);

 password = exhaustive_search(charset, salt, target);
 if (strlen(password)!= 0) cout << "Password successfuly recovered: " << password << "  \n";
 else cout << "Failure to find password, try distinct character set of size \n";
}