Help with algorithms
Results 1 to 7 of 7

Thread: Help with algorithms

  1. #1
    Member
    Join Date
    Feb 2006
    Location
    Canada
    Posts
    58

    Help with algorithms

    Im new to algorithms and am not haveing much luck on google, dont think im useing the right terms but here goes:

    Im solveing a crackme, for fun. I've studied the code and determined the serial must add to 2F2 along with some other constraints. It is 6 chars long.

    First I figured i could write a nested loop that counts from
    1, 1, 1, 1, 1, 1 to 256, 256, 256, 256, 256, 256

    That would take way too long, so I come up with an algorithm, it almost works except keeps returning to 256, were everything started. And thats where I need help.

    It does not get much further then 255, 255, 127, 4, 1, 1

    To descirbe my algorithm, I would first test for sum == target then,

    if sum < target I would increase the current value by value = value + (max - value)/2
    if sum > target I would reduce the curent value by value = value - (value - min)/2

    max would equal 256, and min 0, but once sum < target, I set min equal to curent value since if the current value results in a sum less then what I want, reduceing it further makes no sence.

    I think this is called divide and conquer but not sure. Where can I learn more about these type of algorithms?
    MyBox:

    Asus P5VDC-MX
    Celeron 2.8GHz
    512MB DDR 400
    WD 250GB SATA
    DVD-ROM, CD-RW
    Thermaltake 430W PSU
    Netgear WGT624 Router

  2. #2
    Senior Member
    Join Date
    Mar 2004
    Posts
    557
    Hi

    A general note:

    R. Sedgewick has written a book about Algorithms[1], which I still use frequently.
    Also check the web for keywords like "backtracking[2]" and "dynamic programming[3]".
    Have also a look at the webpage of the International Olympiad in Informatics[4] - an
    excellent resource for algorithmic problems, often with documented solutions.

    Note that it is a very crucial conceptual difference whether you need one solution
    or all solutions - the right choice for the right algorithms is of utmost importance.



    More specific about this kind of problems:

    It seems not valid here, but in general, "serial-numbers" consist of letters A-Z (a-z) and
    numbers 0-9. A nested loop (with jumps from 58 to 65 and 91 to 97) often is a reasonable
    approach.

    A boost in performance can be achieved by a clever way of doing the "checks": in the innermost
    loop, to the computationally least intensiv checks first, and break after each check if not
    successful.

    If you have such a nice thing like a "additive checksum", you can do what you do: break
    a loop as soon as the partial sum is larger than the intended checksum.



    about this problem

    You have the classic problem that you have to "reinitialise" a value. Backtracking comes
    to my mind, but clearly is too much of an overhead here. Hence, you can do this "manually".
    To illustrate this idea, here is a (in principle useless, and yes I know one could use For-Loops
    as well ...) example just looking at 2 chars:
    Code:
            A = 0
            B = 0
            sum = 240
            While (A <= 255)
                While (B <= Min(sum - A, 255))
                    If (A + B = sum) Then
                        ...
                    End If
                    B += 1
                End While
                B = 0   ' <--
                A += 1
            End While

    Certainly there are some more ways to decrease the space of possible "configurations", where
    a configuration is defined as a 6-dimensional vector in the 6-dimensional discrete finite
    space of your problem. However, you have to be very careful while reducing since often,
    the dimensions are not permuteable, ie. you cannot exchange the chars A,B,C,D,E,F.

    If the only condition to be satisfied is the "additive checksum" to be 754 (2F2) then you
    can exchange the chars, hence you can demand that A <= B <= C <= D <= E <= F, which greatly
    reduces the candidate configuration space. Furthermore, once you have found one "solution",
    you have actually found 6!/(sim)=720/(sim) valid solutions (where sim is a factor coming
    from repetitions in the solution, ie if you have 2x "250" but the other 4 values are unique,
    this would be a factor 2. if you have 3x "250" and 2x "15" this number sim would be 3!*2! etc.).


    Be careful when you increase a value by more than "1" as you do. If you are not careful
    enough, you may miss a/the solution.

    I may have misunderstood your current problem - if so, please paraphrase


    Cheers

    [1]
    http://www.amazon.com/gp/product/020...956113?ie=UTF8
    [2] http://en.wikipedia.org/wiki/Backtracking
    [3] http://en.wikipedia.org/wiki/Dynamic_programming
    [4] http://olympiads.win.tue.nl/ioi/
    If the only tool you have is a hammer, you tend to see every problem as a nail.
    (Abraham Maslow, Psychologist, 1908-70)

  3. #3
    rebmeM roineS enilnOitnA steve.milner's Avatar
    Join Date
    Jul 2003
    Posts
    1,018
    This may be stating the obvious, but you could cut down loop work by a dimension by calculating 'F'...

    F == 754 - (A + B + C + D + E)
    IT, e-commerce, Retail, Programme & Project Management, EPoS, Supply Chain and Logistic Services. Yorkshire. http://www.bigi.uk.com

  4. #4
    Member
    Join Date
    Feb 2006
    Location
    Canada
    Posts
    58
    sec_ware That was extreamly helpfull, I am well on my way to solveing this problem now.

    I am so greatfull for all this information I am adding it to my documentation, and notes. Your explanations are easy for me to understand compared to other sites I viewed.

    PS Id give you more AP points but system refuses
    MyBox:

    Asus P5VDC-MX
    Celeron 2.8GHz
    512MB DDR 400
    WD 250GB SATA
    DVD-ROM, CD-RW
    Thermaltake 430W PSU
    Netgear WGT624 Router

  5. #5
    Member
    Join Date
    Feb 2006
    Location
    Canada
    Posts
    58

    UPDATE :)

    I am glad to announce I have completed that chalenge. My final progie was able to calculate the corect answer in 2.12 minutes This was achived after realizeing the three conditons

    A was determined by value of F, D by C, and E by B
    I also noted they problably only used printable characters, reduceing my search futher.

    Your secret of A<=B<=C<=D<=E<=F though didnt help this puzzel, I did try this technique of counting and it amazeingly reduces the range by half. Thanks for this great tip!

    Your idea Min(sum - A, 255) realy helped me, I realize this meant B would never go larger then needed to develop target sum. So I calculated sum in inner loop, and checked for sum &gt; target

    I cannot thank you enough.
    MyBox:

    Asus P5VDC-MX
    Celeron 2.8GHz
    512MB DDR 400
    WD 250GB SATA
    DVD-ROM, CD-RW
    Thermaltake 430W PSU
    Netgear WGT624 Router

  6. #6
    Senior Member
    Join Date
    Mar 2004
    Posts
    557
    Hi

    Congratulation!

    Your secret of A&lt;=B&lt;=C&lt;=D&lt;=E&lt;=F though didnt help this puzzel, I did try this technique of counting and it amazeingly reduces the range by half. Thanks for this great tip!
    This was to be expected - the 6 chars are not interchangeable, which is a necessary
    condition for this restriction to be valid.

    I also noted they problably only used printable characters, reduceing my search futher.
    As said, this makes perfectly sense - now you understand (However, I guess you already
    know that) why people say use special characters in your passwords

    Continue with the next challenge Have you seen these: crackits[1] by white_scorpion,
    formerly known here as lepricaun (there is a thread about them[2]).


    Cheers

    [1] http://www.white-scorpion.nl/crackits/index.html
    [2] http://www.antionline.com/showthread...hlight=secware
    If the only tool you have is a hammer, you tend to see every problem as a nail.
    (Abraham Maslow, Psychologist, 1908-70)

  7. #7
    Member
    Join Date
    Feb 2006
    Location
    Canada
    Posts
    58
    Thanks so much, I love these chalenges. Gona try them next.

    I did notice, while trying the A&lt;=B trick, that I could use an algortihm next_predicate from the STL library, only after trying to code one my self. I noticed it was extramly fast with a set of 6.
    MyBox:

    Asus P5VDC-MX
    Celeron 2.8GHz
    512MB DDR 400
    WD 250GB SATA
    DVD-ROM, CD-RW
    Thermaltake 430W PSU
    Netgear WGT624 Router

Posting Permissions

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