Jump to content
Tuts 4 You

Brute-Force Polynomial for Coefficients.


1 Screenshot

Here is a keygen challenge I got recently. This one requires to find the coefficients of a 26th degree polynomial that sums up to a specific value. A valid serial is also provided. The challenge is to code a keygen with least / reasonable time complexity without patching anything.

Update: Added my initial code that barely works. Please let me have your suggestions to improve the code.

Edited by Benten

void ValidateKeyClick(object sender, EventArgs e)
		{
			// ValidKey: AD5FYOQAR96ROSE7O770STARFM
			char[] SerialKeyStr = SerialText.Text.Trim().ToUpper().ToCharArray();
			decimal[] PolyVector = new decimal[SerialKeyStr.Length + 1];
			decimal[] SerialCoeff = System.Array.ConvertAll(SerialKeyStr, c => (decimal)(c));
			
            PolyVector[0] = -31387554184462;
            SerialCoeff.CopyTo(PolyVector, 1);
            
			if(Math.Truncate(horner(PolyVector, 2.75M)) == 0)
				MessageBox.Show("Key Accepted: Please post your Keygen at Tuts4You");
			else
				MessageBox.Show("Invalid Key: Please keep trying");
		}
		static decimal horner(decimal[] coeff, decimal var)
        {
            decimal result = 0;
            for(int i = coeff.Length - 1; i >= 0 ; i--)
            {
                result = result * var + coeff[i];
            }
            return result;
        }

Brute-Forcing all possible combinations would take forever. My proposal is to put all coefficients to an arbitrary value, get the polynomial sum with those coefficients at a0 = 0. Now we can factorize the new sum to powers of x [2.75] cause the value outside the character set is now acceptable. Once we find the factors those can be added to right arbitrary coefficient updating the polynomial and recurse. Please find my initial code below, this needs heavy improvements but should get you started. Please give me your suggestions to improve it.

List<decimal> LRootPowers = new List<decimal>
            {
                2.75M , 7.5625M , 20.796875M , 57.19140625M , 157.2763671875M , 432.510009765625M , 1189.40252685546M , 3270.85694885253M , 8994.85660934448M , 24735.8556756973M ,
68023.6031081676M , 187064.908547461M , 514428.498505518M , 1414678.37089017M , 3890365.51994798M , 10698505.1798569M , 29420889.2446066M , 80907445.4226681M ,
222495474.912337M , 611862556.008928M , 1682622029.02455M , 4627210579.81752M , 12724829094.4982M , 34993280009.87M , 96231520027.1424M , 264636680074.642M
            };

List<int> Charlist = new List<int>
            {
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
            'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
            'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
            'U', 'V', 'W', 'X', 'Y', 'Z'
            };

static decimal FindCoeff(decimal[] Coeff, List<int> Charlist, decimal PolySum, List<decimal> LRootPowers, decimal total)
        {
            // Initialize the Offset & CurrentFactor.
            int CharOffset = 0;
            decimal CurrFactor = 0;
            // Check for success condtion.
            if (Math.Truncate(PolySum) == 0)
                return 0;
            // Update the NewSum.
            decimal NewSum = total - PolySum;
            // Base case - Can't go any further.
            if (NewSum < LRootPowers[0])
                return NewSum;
            // Find a power that could factorize the new sum.
            CurrFactor = LRootPowers.Where(DRootP => Math.Truncate(NewSum / DRootP) > 0).Max();
            // Get the index of new found power.
            int currindex = LRootPowers.IndexOf(CurrFactor);
            // Calculate the Offset.
            CharOffset = (int)(NewSum / CurrFactor);
            // Calculate the new coefficient.
            int NewCoeff = (int)Coeff[currindex + 1] + CharOffset;
            // Validate and Update NewCoefficient.
            if (Charlist.Any(c => c == NewCoeff))
                Coeff[currindex + 1] = NewCoeff;
            else
            {
                // Stick to CharList
                if (NewCoeff > '9' && NewCoeff < 'A')
                    Coeff[currindex + 1] = '9';
                else if (NewCoeff > 'Z')
                    Coeff[currindex + 1] = 'Z';
                // BackTracking
                LRootPowers.Remove(CurrFactor);
            }
            // Evaluate the new polynomial sum.
            NewSum = horner(Coeff, LRootPowers[0]);
            // Recursive call.
            NewSum = FindCoeff(Coeff, Charlist, NewSum, LRootPowers, total);
            // Return.
            return NewSum;
        }
        static decimal horner(decimal[] coefficients, decimal root)
        {
            decimal accumulator = 0;
            for(int i = coefficients.Length - 1; i >= 0 ; i--)
            {
                accumulator = accumulator * root + coefficients[i];
            }
            return accumulator;
        }


User Feedback

Recommended Comments

There are no comments to display.

×
×
  • Create New...