<?php
/*
* A5/1 Implementation
*
* Information: http://en.wikipedia.org/wiki/A5/1
* Released:    28th September 2008
* App Options: Debugging mode: -d
*
* Written By: Brett Gervasoni (brett.gervasoni [at] gmail.com)
*
* Notes: 
* - Debugging mode will show step by step processes
* - If order matters then put things in order to begin with!
*   Polynomials, clocking bits, and maximum register lengths.
* - If data is not in order the application will try its best to make
*   the cipher work. 
* - Polynomials for each register are chosen based on their largest exponent
*   being less than register length. 
*/

$registersCount = 3; //Number of registers to use

function slowText($message)
{
    $textArray = str_split($message);
    foreach ($textArray as $char)
    {
        usleep(80000);
        echo $char;
    }
}

function intro()
{
    print "#################################################################
#                      A5/1 Implementation                      #
#                                                               #
# Information: http://en.wikipedia.org/wiki/A5/1                #
# Released:    28th September 2008                              #
# App Options: Debugging mode: -d                               #
#                                                               #
# Written By: Brett Gervasoni (brett.gervasoni [at] gmail.com)  #
#################################################################\n\n";

    $message = " You take the blue pill the story ends, nothing happens and you\n believe whatever you want to believe.\n";
    $message .= " You take the red pill you stay in wonderland and I show you how\n deep the rabbit hole goes...\n";
    $message .= " Choice [blue/red]: ";
    slowText($message);

    $choice = trim(fgets(STDIN));
    if ($choice != "red")
    {
        $message = "Goodbye.\n";
        slowText($message);

        exit;
    }

    $message = " Now you will see how deep the rabbit hole really goes.\n\n";
    slowText($message);
    sleep(1);

    echo "Algorithm output: \n";
    sleep(1);
}

function getMaxRegLensTotal($maxRegLens)
{
    $total = 0;
    foreach ($maxRegLens as $len)
    $total += $len;

    return $total;
}

function xorValues($val1, $val2)
{
    $res = 0;

    if ($val1 != $val2)
        $res = 1;

    return $res;
}

function xorRegValues($valuesTX)
{
    $final = 0;

    if (sizeof($valuesTX) > 0)
        $final = $valuesTX[0]; //Sets $final with real value

    for ($i=1; $i<sizeof($valuesTX); $i++)
        $final = xorValues($final, $valuesTX[$i]);

    return $final;
}

//Finds the largest value in an integer array
function findLargestInt($intArray)
{
    $largest = 0;

    foreach ($intArray as $int)
    {
    if ($int > $largest)
        $largest = $int;
    }

    return $largest;
}

//Extracts exponent values from a given polynomial array
function extractPolyExponents($polynomialsArray)
{
    $exponents = array();

    for ($i=0; $i<sizeof($polynomialsArray); $i++)
    {
    preg_match_all("/x\^([0-9]{1,})/is", $polynomialsArray[$i], $matches);

    for ($x=0; $x<sizeof($matches[1]); $x++)
        $exponents[$i][$x] = $matches[1][$x];
    }

    return $exponents;
}

//Selects an appropriate set of polynomials to use
//Returns the respective exponents
function polySelection($polynomialsArray, $numRegisters)
{
    $usingPolynomials = array();
    $exponents = extractPolyExponents($polynomialsArray);

    $counter = 0;
    for ($i=0; $i<sizeof($polynomialsArray); $i++)
    {
    if ($counter == 3) //Each register will now have a polynomial selected
        break;

        $largest = findLargestInt($exponents[$i]);

    //Just making sure polynomial exponents are in range of register length
        if ($largest < $GLOBALS['maxRegLens'][$counter])
    {
            $usingPolynomials[] = $exponents[$i];

        unset($exponents[$i]); //Remove polynomial from picking feild
        $exponents = array_values($exponents);
        $i = -1; //Reset loop counter

        $counter++;
        }
    }

    if ($counter != 3)
    $usingPolynomials = array();

    return $usingPolynomials;
}

//Copies data from source to a register
//regNum is an integer which indicates to a current register
function registerFill($sourceArray, $offset, $regNum)
{
    $outArray = array();

    for ($i=0; $i<$GLOBALS['maxRegLens'][$regNum]; $i++)
        $outArray[] = $sourceArray[$offset+$i];

    return $outArray;
}

//Calls registerFill on each register & preforms polynomial selection
function createRegisters($sourceArray, $polynomialsArray, $numRegisters)
{
    $filledRegisters = array();
    $offset = 0;

    if ($GLOBALS['maxRegLensTotal'] <= sizeof($sourceArray))
    {
    //Therefore our sourceArray does hold enough data and we can begin copying

    for ($i=0; $i<$numRegisters; $i++)
    {
        $filledRegisters[$i] = registerFill($sourceArray, $offset, $i);
        $offset += $GLOBALS['maxRegLens'][$i];
    }
    }

    $usingExponents = polySelection($polynomialsArray, $numRegisters);

    return array($filledRegisters, $usingExponents);
}

//Gets the values associated with clocking function index
function getIndexValues($registersArray)
{
    $indexValues = array();

    for ($i=0; $i<sizeof($registersArray); $i++)
    $indexValues[$i] = $registersArray[$i][$GLOBALS['regIndexes'][$i]];

    return $indexValues;
}

function findFrequency($sourceArray)
{
    $tally = array();

    foreach ($sourceArray as $element)
    {
        if (array_key_exists($element, $tally))
            $tally[$element]++;
        else
            $tally[$element] = 1;
    }

    return $tally;
}

//Determines which registers to shift (or dequeue)
function registersToShift($registersArray)
{
    $indexValues = getIndexValues($registersArray);

    $tally = findFrequency($indexValues);

    if (isset($argv[1]) == "-d")
    {
        echo "Tally: ";
        print_r($tally);
    }

    $highest = 0;

    foreach ($tally as $count)
    {
        if ($count > $highest)
            $highest = $count;
    }

    $movVal = 0;
    $keyChain = array_keys($tally);

    for ($i=0; $i<sizeof($keyChain); $i++)
    {
        if (array_key_exists($keyChain[$i], $tally))
        {
            if ($tally[$keyChain[$i]] == $highest)
                $movVal = $keyChain[$i];
        }
    }

    $regTS = array(); //Formally regTP
    for ($i=0; $i<sizeof($indexValues); $i++)
    {
        if ($indexValues[$i] == $movVal)
            $regTS[] = $i;
    }

    return $regTS;
}

//Shifts the register along
function registerShift($registersArray, $regTS)
{
    $shiftedElements = array();

    foreach ($regTS as $regIndex)
    $shiftedElements[] = array_shift($registersArray[$regIndex]); //drop element from front

    return (array($registersArray, $shiftedElements)); //returns registersArray and shifted values
}

//Pushs feedback values onto registers
function registerPush($registersArray, $feedbackValues)
{
    $keyChain = array_keys($feedbackValues);

    foreach ($keyChain as $key)
    {
    if (array_key_exists($key, $registersArray))
        $registersArray[$key][] = $feedbackValues[$key];
    //maybe else if registersSrray is empty then error
    }

    return $registersArray;
}

//Determines feedback values from polynomial
function getFeedbackValues($registersArray, $usingExponents, $regTS)
{
    $regTSFBV = array(); //Reg To Shift Feed Back Values (regTSFBV)

    for ($i=0; $i<sizeof($regTS); $i++)
    {
    $feedbackSet = array();

    if (array_key_exists($regTS[$i], $registersArray) && array_key_exists($regTS[$i], $usingExponents))
    {
        foreach ($usingExponents[$regTS[$i]] as $exponent)
        $feedbackSet[] = $registersArray[$regTS[$i]][$exponent];

        $regTSFBV[$regTS[$i]] = xorRegValues($feedbackSet);
    }
    }

    return $regTSFBV;
}

/* Main */
$sourceArray = array(
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1", 
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1",
                "1", "0", "0", "1", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "0", "1",
                "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1", "1", "0", "1", "1", "0", "1"
                );
$polynomialsArray = array(
        "x^18+x^17+x^16+x^13+1", //Current A5/1 polynomial (reg1)
        "x^21+x^20+1", //Current A5/1 polynomial (reg2)
        "x^22+x^21+x^20+x^7+1", //Current A5/1 polynomial (reg3)
        "x^100+x^200+1", 
        "x^3+x^2+x^1+1"
        );

//Below integer values must be in register order ie: reg1, reg2, reg3, etc
$regIndexes = array("8", "10", "10"); //Clocking bits
$maxRegLens = array(19, 22, 23); //Register lengths
$maxRegLensTotal = getMaxRegLensTotal($maxRegLens);

if (!isset($argv[1]))
    intro();

//Initialisation
$initSetup = createRegisters($sourceArray, $polynomialsArray, $registersCount);

$totalSize = 0;
foreach ($initSetup[0] as $reg)
    $totalSize += sizeof($reg);

if ($totalSize < $maxRegLensTotal)
    die("[-] Error: Cannot fill registers; not enough source data\n");

if (sizeof($initSetup[1]) < 1)
    die("[-] Error: Not enough valid polynomials!\n");
if (sizeof($initSetup[1]) != $registersCount)
    die("[-] Error: Largest polynomial exponent is larger than maximum register length!\n");

//Alias main data components
$registersArray = $initSetup[0];
$usingExponents = $initSetup[1];

if (isset($argv[1]) == "-d")
{
    echo "Using Exponents: \n";
    print_r($usingExponents);

    echo "Registers sizes (1, 2, 3, etc): ";
    for ($i=0; $i<sizeof($registersArray); $i++)
        echo ($i == (sizeof($registersArray)-1)) ? sizeof($registersArray[$i])."\n" : sizeof($registersArray[$i]).", ";

    echo "Registers initially: \n";
    foreach ($registersArray as $reg)
        print_r($reg);
}

$counter = 0;
while (1)
{
    if (isset($argv[1]) == "-d")
        echo "Preparing values to XOR\n";

    $valuesTX = array();
    for ($i=0; $i<sizeof($registersArray); $i++)
        $valuesTX[$i] = $registersArray[$i][0];

    $outValue = xorRegValues($valuesTX);

    $regTS = array();
    $regTS = registersToShift($registersArray);
    if (isset($argv[1]) == "-d")
    {
        echo "regTS: \n"; print_r($regTS);
    }

    $feedbackValues = getFeedbackValues($registersArray, $usingExponents, $regTS);
    if (sizeof($feedbackValues) != sizeof($regTS))
    die("[-] Error: When attempting to get regTS feedback values! Sizes do not match!\n");

    if (isset($argv[1]) == "-d")
    {
        echo "Feedback values: "; print_r($feedbackValues);
    }

    //registerShift
    $nRegisters = array();
    $nRegisters = registerShift($registersArray, $regTS);

    //Reassign
    $registersArray = $nRegisters[0];

    if (isset($argv[1]) == "-d")
    {
        echo "Registers after shift\n";
        print_r($registersArray);
    }

    //Now do feedback! Put the values into end of registers (push)
    $registersArray = registerPush($registersArray, $feedbackValues);

    if (isset($argv[1]) == "-d")
    {
        echo "Registers after feedback values pushed\n";
        print_r($registersArray);
    }

    if (!isset($argv[1]))
    {
    usleep(20000);
        echo $outValue;
    }

    $counter++;

    //Debugging purposes
    if (isset($argv[1]) == "-d")
    {
        if ($counter == 10)
            break;
    }
}
?>