Any Idea On How Should I Analyze This Algorithm?

I was wondering if I could get some help on how to analyze an algorithm, my teacher gave us the validation code for some strings. and out project is that we must create a keygen fo

Solution 1:

OK, what's going on inside checkdata? Well, whatever it's doing before the end, after dig = mod(dig, 9) it's got a number from 0 to 8, and it's comparing that to the last character (code.charAt(code.length-1))). Notice that the for loop above does i<code.length-1 rather than i<code.length, so that last character isn't included in the calculation. And (other than the check for length 15+) there's nothing else going on here.

So, you don't even have to understand what the whole for loop is doing. If you can generate 14 or more random characters, run the exact same code on them, and append the result to the end, it'll pass.

One quick and dirty way to do that is to just add an alert (or, maybe better, use console.log and run in node instead of a browser…) right before the end of checkdata that shows you what dig is:

functioncheckdata(code) { 
  var dig = 0; 
  var test = 1; 
  for(var i=0; i<code.length-1;i++) { 
    dig=dig+(char2number(code.charAt(i))*test);
    test*=2;
  }
  dig = mod(dig,9);
  alert(dig);
  if(dig==code.charAt(code.length-1)) returntrue; 
  elsereturnfalse;}

So now, take some random string of 15 or more characters, like "ABC123DEF456GHI789". An alert will pop up saying "2", and it'll fail because 2 and 9 aren't the same. So just use "ABC123DEF456GHI782" instead, and it'll pass.

Now all you have to do is port that checkdata function to Python, change the alert(dig) to return code[:-1] + dig, write the code to generate 15-character random strings, and of course write the code that calls the service. But that's it.

By the way, porting to Python isn't always quite as trivial as it seems; for example:

• JS, 2 is a 64-bit floating point number; Python 2 is an unlimited-bit integer.
• JS strings are Unicode; Python 2.x strings are not (but 3.x are).
• JS strings in some browsers are actually UTF-16, not Unicode.
• JS % is sign-preserving; Python % is always-positive.

Fortunately, for writing a keygen, you can generate something that doesn't stray beyond the limits of where any of these things matters, but you should think things through to make sure you do so.

I should add that your teacher may want you to understand what's going on inside the for loop, instead of treating it like a black box. Also, in real life, whoever wrote this silly algorithm would figure out how you cracked it, and make a trivial change that made at least partially understanding the loop necessary (e.g., if they change the <code.length-1 to <code.length).