Results 1 to 5 of 5

Thread: crypto thought crackme #4

  1. #1
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491

    crypto thought crackme #4

    Continued fractions of the square roots of non-square integers are periodic. The period itself is a palindrome followed by twice the first term:

    sqrt(5) = [2; 2,4, 2,4, 2,4,...]
    sqrt(13) = [3; 1,1,1,1,6, 1,1,1,1,6, ...]
    sqrt(29) = [5; 2,1,1,2,10, 2,1,1,2,10, ...]
    sqrt(31) = [5; 1,1,3,5,3,1,1,10, 1,1,3,5,3,1,1,10, ...]

    See http://mathworld.wolfram.com/ContinuedFraction.html for more details about continued fractions.

    This proggy uses that fact to check serial numbers. The code takes an integer and verifies that the continued fraction representation of its square root matches the following checks:

    Each term in the continued fraction except the first and last must be a number between 1 and 27, where 27 indicates a space, and 1-26 are A-Z. The first five are CACCG, while the last five are (of course) GCCAC. The middle ones encode the username forwards and backwards.

    For example,

    sqrt(serial) =
    [(x); C,A,C,C,G,M,I,K,E,E,K,I,M,G,C,C,A,C,(2*x), ...]

    In order to win this one, you've got to post a serial with your handle in it.

    Easy question: Why CACCG?
    Last edited by mike; January 16th, 2003 at 22:39.

  2. #2
    Two words.... yay Mathematica!

    Serial for Kythen = 1375676437308924001678248151500557858
    ContinuedFraction = [1172892338328170682; 3, 1, 3, 3, 7, 11, 25, 20, 8, 5, 14, 14, 5, 8, 20, 25, 11, 7, 3, 3, 1, 3, 2345784676656341364, ...]

    BTW... mike, the serial for your nick is 20285330574668271999128210 and the Continued Fraction is [4503923908623; 3, 1, 3, 3, 7, 13, 9, 11, 5, 5, 11, 9, 13, 7, 3, 3, 1, 3, 9007847817246, ...]

    Thanks to a couple of my math professors for their book/course on number theory!

  3. #3
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    What functions did you use? Did you bruteforce something, or solve it explicitly in Mma.?

  4. #4
    Well, I originally tried bruteforcing with FromContinuedFraction[], but of course that wasn't very efficient or necessary. What I ended up doing was plugging in x and 2x and solving for what the serial must look like. Of course, it always ends up being a quadratic formula. Now, you figure out a value for x that will make this quadratic formula result in a integer. The second degree coefficient appears to always be 1, so it ends up reducing the problem to finding an x value that will make the (Bx + C) component of the quadratic formula an integer. Most, if not all of the time, B and C will be fractions with the same denominator. Let the numerator of B be r, the numerator of C be s, and the denominator be t. Solve the linear congruence rx = -s mod t to find the value of x. Plug this x back into the quadratic formula to get the serial.

    I didn't write the functions I used to do this. My number theory book included a Mathematica package that has a function to find the form of N given the continued fraction of sqrt(N).

  5. #5
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    Cool! I wasn't aware you could solve it that way, though it makes sense now. You might like to look at the paper I got the idea from. It's by J McLaughlin, multivariate polynomial solutions to pell's equation. Google search on "polypel2c" to find it. It gives a closed form solution (I suspect it's the one your book used). It also shows that there are patterns which can't occur.

Similar Threads

  1. crypto thought crackme #6
    By mike in forum Mini Project Area
    Replies: 18
    Last Post: May 29th, 2006, 00:40
  2. crypto thought crackme #5
    By mike in forum Mini Project Area
    Replies: 12
    Last Post: January 22nd, 2003, 17:52
  3. crypto thought crackme #3
    By mike in forum Mini Project Area
    Replies: 7
    Last Post: January 15th, 2003, 15:32
  4. crypto thought crackme #2
    By mike in forum Mini Project Area
    Replies: 9
    Last Post: January 13th, 2003, 19:25
  5. crypto crackme thought experiment
    By mike in forum Mini Project Area
    Replies: 12
    Last Post: January 8th, 2003, 22:43

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •