string generation

Discussion in 'C Programming' started by Ken Human, May 22, 2005.

  1. Ken Human

    Ken Human Guest

    I want to generate every possible 16 character combination of the
    characters 0-9, A-Z, and a-z programatically. My current code follows:

    #include <stdio.h>
    #include <ctype.h>

    int main() {
    char strBuf[17] = {0};
    int i, j;

    for(i = 0; i < 16; i++) {
    for(j = '0'; j <= 'z'; j++) {
    if(!isalnum(j)) continue;
    strBuf = j;
    printf("%s\n", strBuf);
    }
    }

    return 0;
    }

    Only the last character increments. I understand my problem and I can
    fix it with a for loop for each space in the array, but I'd like to know
    if there's a better solution.
     
    Ken Human, May 22, 2005
    #1
    1. Advertising

  2. Ken Human <> writes:

    >I want to generate every possible 16 character combination of the
    >characters 0-9, A-Z, and a-z programatically. My current code follows:


    Really, every one?
    And on what computer are you hoping to run this?

    --
    Chris.
     
    Chris McDonald, May 22, 2005
    #2
    1. Advertising

  3. Ken Human wrote:
    > I want to generate every possible 16 character combination of the
    > characters 0-9, A-Z, and a-z programatically.


    Are you sure? That's pow(62,16), which is a lot of combinations.
    About 4.8e28, I think.

    > My current code follows:
    >
    > #include <stdio.h>
    > #include <ctype.h>
    >
    > int main() {
    > char strBuf[17] = {0};
    > int i, j;
    >
    > for(i = 0; i < 16; i++) {
    > for(j = '0'; j <= 'z'; j++) {
    > if(!isalnum(j)) continue;
    > strBuf = j;
    > printf("%s\n", strBuf);
    > }
    > }
    >
    > return 0;
    > }
    >
    > Only the last character increments. I understand my problem and I can
    > fix it with a for loop for each space in the array, but I'd like to know
    > if there's a better solution.


    untested code block:
    {
    char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "abcdefghijklmnopqrstuvwxyz";
    unsigned nfoos = sizeof foo/sizeof *foo;
    unsigned ndx[16] = {0}, i;
    while(ndx[15] != nfoos)
    {
    for (i = 0; i < 16; i++) putchar(foo[ndx]);
    putchar('\n');
    for(i = 0; i < 16; i++)
    {
    ndx++;
    if (ndx < nfoos) break;
    ndx = 0;
    }
    }
    }
     
    Martin Ambuhl, May 22, 2005
    #3
  4. Ken Human

    Ken Human Guest

    Chris McDonald wrote:
    > Ken Human <> writes:
    >
    >
    >>I want to generate every possible 16 character combination of the
    >>characters 0-9, A-Z, and a-z programatically. My current code follows:

    >
    >
    > Really, every one?
    > And on what computer are you hoping to run this?
    >


    I was never very good at math, is the number of possible combinations
    62^16? Thank you for your concern. I'm running it on the Plasmo Mag-8,
    which can calculate this exact amount of data in 1 second. Needless to
    say, it also has an unlimited amount of memory.

    Let's say that I want a 4 character combination.
     
    Ken Human, May 22, 2005
    #4
  5. Ken Human

    Ken Human Guest

    Martin Ambuhl wrote:
    > Ken Human wrote:
    >
    >> I want to generate every possible 16 character combination of the
    >> characters 0-9, A-Z, and a-z programatically.

    >
    >
    > Are you sure? That's pow(62,16), which is a lot of combinations.
    > About 4.8e28, I think.
    >

    [...]
    >
    > untested code block:
    > {
    > char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    > "abcdefghijklmnopqrstuvwxyz";
    > unsigned nfoos = sizeof foo/sizeof *foo;
    > unsigned ndx[16] = {0}, i;
    > while(ndx[15] != nfoos)
    > {
    > for (i = 0; i < 16; i++) putchar(foo[ndx]);
    > putchar('\n');
    > for(i = 0; i < 16; i++)
    > {
    > ndx++;
    > if (ndx < nfoos) break;
    > ndx = 0;
    > }
    > }
    > }


    Thanks, Martin. That was what I was looking for.
     
    Ken Human, May 22, 2005
    #5
  6. In article <>,
    Ken Human <> wrote:
    >I want to generate every possible 16 character combination of the
    >characters 0-9, A-Z, and a-z programatically.


    Are you sure????

    That's 62 symbols, and you want 16 of them, so that's pow(62,16)
    combinations, which is 47672401706823533450263330816
    If you are able to generate them at the rate of 1 GHz
    then even presuming you have storage system able to handle
    17 gigabyte/second, it would take 1.5E12 years.

    At a 1 GHz production rate, you could get through 8 positions
    worth in just over a day... and that alone would require over 1.3
    petabytes of storage.


    > My current code follows:


    >#include <stdio.h>
    >#include <ctype.h>


    >int main() {
    > char strBuf[17] = {0};
    > int i, j;


    > for(i = 0; i < 16; i++) {
    > for(j = '0'; j <= 'z'; j++) {
    > if(!isalnum(j)) continue;
    > strBuf = j;
    > printf("%s\n", strBuf);
    > }
    > }
    > return 0;
    >}


    I would suggest that instead of testing for isalnum, that
    you create an array of the valid choices and index it by
    the current j (which would range over 0 to the number of choices minus 1
    instead of '0' to 'z'). That will save you from the conditional
    test at each point.

    This won't save you from the problem of only incrementing the
    last byte. There are various ways of handling that situation,
    but we have to leave you -something- to be inventive over ;-)
    --
    Oh, to be a Blobel!
     
    Walter Roberson, May 22, 2005
    #6
  7. Ken Human wrote on 22/05/05 :
    > I want to generate every possible 16 character combination of the characters
    > 0-9, A-Z, and a-z programatically. My current code follows:


    Really ? It may take hours or days to print them out... Sounds like a
    cracking device...


    > #include <stdio.h>
    > #include <ctype.h>
    >
    > int main() {
    > char strBuf[17] = {0};
    > int i, j;
    >
    > for(i = 0; i < 16; i++) {
    > for(j = '0'; j <= 'z'; j++) {


    Don't make assumptions on characters values. It only works with digits.
    Use an array of char

    static char const
    characters[]="0123456789ABCDE<...>XYZ<...>abc<...>xyz";


    > if(!isalnum(j)) continue;
    > strBuf = j;
    > printf("%s\n", strBuf);
    > }
    > }
    >
    > return 0;
    > }
    >
    > Only the last character increments. I understand my problem and I can fix it
    > with a for loop for each space in the array, but I'd like to know if there's
    > a better solution.


    You probably want 16 nested loops... or a smart recursive function with
    a huge automatic memory...

    --
    Emmanuel
    The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
    The C-library: http://www.dinkumware.com/refxc.html

    ..sig under repair
     
    Emmanuel Delahaye, May 22, 2005
    #7
  8. Martin Ambuhl wrote on 22/05/05 :
    > untested code block:
    > {
    > char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    > "abcdefghijklmnopqrstuvwxyz";
    > unsigned nfoos = sizeof foo/sizeof *foo;
    > unsigned ndx[16] = {0}, i;
    > while(ndx[15] != nfoos)
    > {
    > for (i = 0; i < 16; i++) putchar(foo[ndx]);
    > putchar('\n');
    > for(i = 0; i < 16; i++)
    > {
    > ndx++;
    > if (ndx < nfoos) break;
    > ndx = 0;
    > }
    > }
    > }


    Very smart. A little fix:

    #include <stdio.h>

    int main (void)
    {
    static char const foo[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "abcdefghijklmnopqrstuvwxyz";
    unsigned const nfoos = strlen(foo);
    #define N 3
    unsigned ndx[N] =
    {0};

    while (ndx[N-1] != nfoos)
    {
    {
    unsigned i;

    for (i = 0; i < N; i++)
    {
    putchar (foo[ndx]);
    }
    putchar ('\n');
    }

    {
    unsigned i;

    for (i = 0; i < N; i++)
    {
    ndx++;
    if (ndx < nfoos)
    {
    break;
    }
    ndx = 0;
    }
    }
    }
    return 0;
    }

    --
    Emmanuel
    The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
    The C-library: http://www.dinkumware.com/refxc.html

    I once asked an expert COBOL programmer, how to
    declare local variables in COBOL, the reply was:
    "what is a local variable?"
     
    Emmanuel Delahaye, May 22, 2005
    #8
  9. Ken Human wrote:


    > Thanks, Martin. That was what I was looking for.


    Quickly looking back, I see that I have at least an off-by-one error in:
    >> char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    >> "abcdefghijklmnopqrstuvwxyz";
    >> unsigned nfoos = sizeof foo/sizeof *foo;


    Other errors may be lurking there as well. That's what happens when I
    code on the fly while asleep.
     
    Martin Ambuhl, May 22, 2005
    #9
  10. "Emmanuel Delahaye" <> writes:
    > Ken Human wrote on 22/05/05 :
    >> I want to generate every possible 16 character combination of the
    >> characters 0-9, A-Z, and a-z programatically. My current code
    >> follows:

    >
    > Really ? It may take hours or days to print them out... Sounds like a
    > cracking device...


    Hours or days? You'd better buy a sweater; it's going to get chilly
    after the sun burns out (which will happen long before this thing is
    finished).

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, May 22, 2005
    #10
  11. Ken Human

    Ken Human Guest

    Martin Ambuhl wrote:
    > Ken Human wrote:
    >
    >
    >> Thanks, Martin. That was what I was looking for.

    >
    >
    > Quickly looking back, I see that I have at least an off-by-one error in:
    > >> char foo[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    > >> "abcdefghijklmnopqrstuvwxyz";
    > >> unsigned nfoos = sizeof foo/sizeof *foo;

    >
    > Other errors may be lurking there as well. That's what happens when I
    > code on the fly while asleep.
    >


    I caught that, yes. Your idea was a good base to finish what I was
    working on, thanks.
     
    Ken Human, May 22, 2005
    #11
  12. Ken Human

    Ken Human Guest

    Keith Thompson wrote:
    > "Emmanuel Delahaye" <> writes:
    >
    >>Ken Human wrote on 22/05/05 :
    >>
    >>>I want to generate every possible 16 character combination of the
    >>>characters 0-9, A-Z, and a-z programatically. My current code
    >>>follows:

    >>
    >>Really ? It may take hours or days to print them out... Sounds like a
    >>cracking device...

    >
    >
    > Hours or days? You'd better buy a sweater; it's going to get chilly
    > after the sun burns out (which will happen long before this thing is
    > finished).
    >


    I'm afraid I worded my post badly. I picked the number 16 as to
    demonstrate why a large nested-loop would not look good. It's usually
    stopping at 4 - 6 digits and it'll never go past 8 at the moment.
     
    Ken Human, May 22, 2005
    #12
  13. Ken Human

    Malcolm Guest

    "Ken Human" <> wrote
    >
    > I was never very good at math, is the number of possible combinations
    > 62^16? Thank you for your concern. I'm running it on the Plasmo Mag-8,
    > which can calculate this exact amount of data in 1 second. Needless to
    > say, it also has an unlimited amount of memory.
    >

    Wow. Can I have your old Plasmo Mag-8, when you upgrade to the next model?
    >
    > Let's say that I want a 4 character combination.
    >

    Martin Ambuhl's code should work. Just replace the 16 with a 4.

    What do you need these 16-character permutations for? I suspect that there
    may be a much more efficient way of achieving it than setting the Plasmo
    Mag-8 on absolutely every combination. However I can't be certain.
     
    Malcolm, May 22, 2005
    #13
  14. On Sat, 21 May 2005 19:13:09 -0500, in comp.lang.c , Ken Human
    <> wrote:

    >I want to generate every possible 16 character combination of the
    >characters 0-9, A-Z, and a-z programatically.


    Thats a lot of combinations.

    > for(j = '0'; j <= 'z'; j++) {


    this isn't guaranteed to include all the characters you want. There's
    nothing in C that requires the characters to be in order from 0 to z.
    --
    Mark McIntyre
    CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
    CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

    ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
    http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
    ----= East and West-Coast Server Farms - Total Privacy via Encryption =----
     
    Mark McIntyre, May 22, 2005
    #14
  15. Ken Human

    Ken Human Guest

    Malcolm wrote:
    >
    > Martin Ambuhl's code should work. Just replace the 16 with a 4.
    >
    > What do you need these 16-character permutations for? I suspect that there
    > may be a much more efficient way of achieving it than setting the Plasmo
    > Mag-8 on absolutely every combination. However I can't be certain.
    >
    >


    It's for a game, actually. During a part of the game the user is asked
    to develop a way to crack a random password that consists of those 62
    characters. I provide a scripting language and this particular tool,
    they have to figure out how to use it in the most efficient way. The
    user usually won't actually try every possible combination, unless he
    doesn't understand what he's supposed to be doing.

    Basically there's a rule set that's similiar to: 5 - 7 digits and must
    not start with a capital letter or number.

    I needed the best way to find every combination because it's possible
    that the user will want to try every combination, and 16 just happens to
    be the longest length of password I want to use for the game. If the
    user chooses to try every combination on a 16 digit password he'll most
    likely not advance.
     
    Ken Human, May 22, 2005
    #15
  16. Ken Human

    CBFalconer Guest

    Emmanuel Delahaye wrote:
    > Ken Human wrote on 22/05/05 :
    >
    >> I want to generate every possible 16 character combination of
    >> the characters 0-9, A-Z, and a-z programatically. My current
    >> code follows:

    >
    > Really ? It may take hours or days to print them out... Sounds
    > like a cracking device...


    I don't think any of you, he, or I will live to see the program run
    to completion.

    --
    Some informative links:
    news:news.announce.newusers
    http://www.geocities.com/nnqweb/
    http://www.catb.org/~esr/faqs/smart-questions.html
    http://www.caliburn.nl/topposting.html
    http://www.netmeister.org/news/learn2quote.html
     
    CBFalconer, May 22, 2005
    #16
  17. Ken Human

    Simon Biber Guest

    Keith Thompson wrote:
    > Hours or days? You'd better buy a sweater; it's going to get chilly
    > after the sun burns out (which will happen long before this thing is
    > finished).


    If computer speeds double every 3 years, and the fastest computer at the
    beginning of 2005 can run 2^30 iterations per second, then the earliest
    completion date is January 20, 2124. You would buy the computer on
    August 22, 2119, and it would run for 4 years, 3 months, 29 days.

    Mathematica expression used:
    Minimize[2005 + 3 * Log[62^16 / (2^30 * 31556952 * length)]
    / Log[2] + length, {length}]

    (where 2005 is the date at which computers have the given speed,
    3 is the number of years to double,
    62^16 is the number of computations,
    2^30 is the number of computations per second,
    31556952 is the number of seconds per year,
    length is how long the computation will take in years)

    The length of computation for the first possible completion date is
    3 / Log[2]

    Interestingly, this is merely a function of the rate of speed growth,
    and is entirely independent of the complexity of the problem.

    The start date is: 2005 + 3 / Log[2] * Log[
    31^16 / (3 / Log[2] * 31556952 * 2^14)]

    As an even sillier aside, keeping the same assumptions and working
    backwards, for such a "standard" computer to iterate those combinations
    of length 7 was first possible in 1963, length 8 was first possible in
    1981, length 9 in 1999, and length 10 will be possible in 2016.

    --
    Simon.
     
    Simon Biber, May 22, 2005
    #17
  18. In article <429072d3$0$8120$>,
    Simon Biber <> wrote:
    >If computer speeds double every 3 years, and the fastest computer at the
    >beginning of 2005 can run 2^30 iterations per second, then the earliest
    >completion date is January 20, 2124. You would buy the computer on
    >August 22, 2119, and it would run for 4 years, 3 months, 29 days.


    Heh ;-)


    >As an even sillier aside, keeping the same assumptions and working
    >backwards, for such a "standard" computer to iterate those combinations
    >of length 7 was first possible in 1963, length 8 was first possible in
    >1981, length 9 in 1999, and length 10 will be possible in 2016.


    I am quite not sure here what you mean by "possible". Length 10
    at 2^30 per second would take about 24 3/4 years, but that's
    -possible-.
    --
    Look out, there are llamas!
     
    Walter Roberson, May 22, 2005
    #18
  19. Ken Human

    Malcolm Guest

    "Ken Human" <> wrote
    >
    > It's for a game, actually. During a part of the game the user is asked to
    > develop a way to crack a random password that consists of those 62
    > characters. I provide a scripting language and this particular tool, they
    > have to figure out how to use it in the most efficient way. The user
    > usually won't actually try every possible combination, unless he doesn't
    > understand what he's supposed to be doing.
    >
    > Basically there's a rule set that's similiar to: 5 - 7 digits and must not
    > start with a capital letter or number.
    >
    > I needed the best way to find every combination because it's possible that
    > the user will want to try every combination, and 16 just happens to be the
    > longest length of password I want to use for the game. If the user
    > chooses to try every combination on a 16 digit password he'll most likely
    > not advance.
    >

    Why not write these functions

    /*
    return true if a string is a valid password.
    */
    int validpassword(char *str)

    /*
    store a password entered by the user
    */
    int storepassword(char *pass)

    /*
    return true if the password has already been tried
    */
    int paswordtried(char *pass)

    /*
    clear the list of stored passwords
    */
    void clearattemptlist(void)

    I think with these functions you can achieve what you want, without any need
    for an exhaustive iteration. The whole point of a password is that it is too
    difficult to enumerate all possibilities, anyway.
     
    Malcolm, May 22, 2005
    #19
  20. Ken Human

    Ken Human Guest

    Malcolm wrote:
    > "Ken Human" <> wrote
    >
    >>It's for a game, actually. During a part of the game the user is asked to
    >>develop a way to crack a random password that consists of those 62
    >>characters. I provide a scripting language and this particular tool, they
    >>have to figure out how to use it in the most efficient way. The user
    >>usually won't actually try every possible combination, unless he doesn't
    >>understand what he's supposed to be doing.
    >>
    >>Basically there's a rule set that's similiar to: 5 - 7 digits and must not
    >>start with a capital letter or number.
    >>
    >>I needed the best way to find every combination because it's possible that
    >>the user will want to try every combination, and 16 just happens to be the
    >>longest length of password I want to use for the game. If the user
    >>chooses to try every combination on a 16 digit password he'll most likely
    >>not advance.
    >>

    >
    > Why not write these functions
    >
    > /*
    > return true if a string is a valid password.
    > */
    > int validpassword(char *str)
    >
    > /*
    > store a password entered by the user
    > */
    > int storepassword(char *pass)
    >
    > /*
    > return true if the password has already been tried
    > */
    > int paswordtried(char *pass)
    >
    > /*
    > clear the list of stored passwords
    > */
    > void clearattemptlist(void)
    >
    > I think with these functions you can achieve what you want, without any need
    > for an exhaustive iteration. The whole point of a password is that it is too
    > difficult to enumerate all possibilities, anyway.
    >
    >


    I'm very interested in the possibility of not having to use this type of
    code on the end user's machine, but the point of this part of the game
    is to write a working brute force attack that won't take forever. I
    want to keep the scripting language itself as simple as possible.

    To demonstrate exactly what the problem is, I'll explain the problem in
    the game: The user is given an MD5 hash of a password to gain access to
    a privileged part of the program. The user has an idea of how the
    password is formed, and an idea of the size. So say that information is
    4 - 6 digits, and the password looks like 00Ab(A?)(b?) (he got this
    information by walking around in a building and looking at people typing
    in their passwords).

    So in the scripting language he'd write something like:

    bool BruteForce(string MD5, string format) {
    if(format) while(MD5 != crack(format));
    else while(MD5 != crack());
    }

    int main(void) {
    bool found = BruteForce(hash, "%N%N%L%l%?L%?l");
    if(!found) return errorCode();
    return 0;
    }

    and crack() is the previously posted code
    (news://news.comcast.giganews.com:119/dSUje.5646$)
    that checks every combination of those 62 characters with the
    modification of knowing what to do with a "string format". The actual
    script does not resemble C as much and would look more complex.

    My scripting language can not accomplish what crack() would, as I'm
    trying to keep it minimalistic. Unfortunatley I don't really think the
    ideas you posted could apply, but if you see something I don't, I'd love
    to hear it.
     
    Ken Human, May 22, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mladen Adamovic
    Replies:
    0
    Views:
    767
    Mladen Adamovic
    Dec 4, 2003
  2. James Arnold

    String Generation using Mask Parsing

    James Arnold, Sep 21, 2008, in forum: C Programming
    Replies:
    3
    Views:
    780
    Ben Bacarisse
    Sep 21, 2008
  3. John W. Long

    HTML Generation (Next Generation CGI)

    John W. Long, Nov 22, 2003, in forum: Ruby
    Replies:
    4
    Views:
    377
    John W. Long
    Nov 24, 2003
  4. Derek Fountain

    Fast random string generation

    Derek Fountain, Oct 24, 2004, in forum: Perl Misc
    Replies:
    16
    Views:
    303
    Michele Dondi
    Oct 28, 2004
  5. petrucci

    String generation

    petrucci, Sep 21, 2005, in forum: Perl Misc
    Replies:
    8
    Views:
    87
    Matija Papec
    Sep 21, 2005
Loading...

Share This Page