Is my password generating function inefficient?

Question

I have this javascript password generating function. Right now I'm discarding passwords that don't match the selected specifications. For example if the password doesn't contain numbers, I discard it and generate a new one hopping that one will have a number in it. This however doesn't seem to be efficient performance vise, at least not to me.

Is there a better way to implement the forcing of specific characters in the generated password?

Also i'm planning to add so that the password can be forced to contain special characters. If I do this the current way, I would have to have some regex to check if the password contains special characters and if not throw it way (again doesn't seem very efficient to me).

function generatePassword(length, charset, nosimilar) {
    // default parameters
    length = (typeof length === "undefined") ? 8 : length;
    charset = (typeof charset === "undefined") ? 'abcdefghjknpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ123456789' : charset;
    nosimilar = (typeof similar === "undefined") ? true : nosimilar;

    var gen;
    retVal = "";
    for (var i = 0, n = charset.length; i < length; ++i) {
        gen = charset.charAt(Math.floor(Math.random() * n))
        if ( (retVal.charAt( retVal.length-1 ) == gen) && (nosimilar)) {
            retVal = retVal.substring(0, retVal.length - 1)
            retVal += charset.charAt(Math.floor(Math.random() * n))
            console.log('Generated character same as the last one. Trunkated and regenerated.');
        }
        retVal += gen;
    }

    // if charset contains numbers make sure we get atleast one number
    if ( (retVal.match(/\d+/g) == null) && (charset.match(/\d+/g) != null)) {
    console.log('Password generated but no numbers found. Regenerating.');
    generatePassword(length, charset, nosimilar);
    }

    return retVal;
}

if ($("#chLetters").prop('checked')) charset += 'abcdefghjknpqrstuvwxyz';
if ($("#chNumbers").prop('checked')) charset += '123456789';
if ($("#chMixedCase").prop('checked')) charset += 'ABCDEFGHJKLMNPQRSTUVWXYZ';
if ($("#chSpecial").prop('checked')) charset += '!@$%&?+*-_';

$("#passgen").text(generatePassword($("#maxLength").val(), charset, $("#chNoSimilar").prop('checked')));

Answer 1

If you have a password n characters long and the requirement is that it has at least one letter, one number and one special character, it means that it will have between 1 and n-2 characters of each. For example (simplified):

function generatePassword( length ) {
    var letters = 'abcdefghjknpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ',
        special = '{}()#%&',
        characters = [],
        amountOfLetters = Math.floor( Math.random() * ( length - 2 ) ) + 1,
        amountOfNumbers = Math.floor( Math.random() * ( length - 1 - amountOfLetters ) ) + 1,
        amountOfSpecial = length - ( amountOfLetters + amountOfNumbers );

    // pick letters
    for (var i = 0, n = letters.length; i < amountOfLetters; ++i) {
        characters.push( letters.charAt( Math.floor( Math.random() * n ) ) );
    }

    // pick numbers
    for ( i = 0; i < amountOfNumbers; ++i) {
        characters.push( ''+( Math.floor( Math.random() * 9 ) + 1 ) );
    }

    // pick special characters
    for ( i = 0, n = special.length; i < amountOfSpecial; ++i) {
        characters.push( special.charAt( Math.floor( Math.random() * n ) ) );
    }

    // sort the array and concatenate elements into a string
    return characters.sort( function( a, b ) {
        return Math.random() - 0.5;
    } ).join( '' );
}

Demo: http://jsfiddle.net/gGwyM/

The function picks between 1 and n-2 letters, then between 1 and n-L-1 numbers (where L is the amount of letters), and the rest are special characters. This guarantees that the password contains at least one character from each group.

(Note that you should use a better function than what I have here to randomize the array, see e.g. How to randomize (shuffle) a JavaScript array?)

Answer 2

You could use something like this. Using this method allows you to create multiple key sets and by using a simple option attribute you can switch these keysets in and out of the the password generation, along with setting a length or even choosing to generate a hex password.

function isObject(value) {
  return Object.prototype.toString.call(value) === '[object Object]';
}

function assign(target, source) {
  for (var prop in source) {
    if (source.hasOwnProperty(prop)) {
      target[prop] = source[prop];
    }
  }

  return target;
}

function shuffle(obj) {
  var i = obj.length;
  var rnd, tmp;

  while (i) {
    rnd = Math.floor(Math.random() * i);
    i -= 1;
    tmp = obj[i];
    obj[i] = obj[rnd];
    obj[rnd] = tmp;
  }

  return obj;
}

function generatePassword(options) {
  var opts = isObject(options) ? assign({}, options) : {};
  var keyspace = '';
  if (opts.hex) {
    keyspace = '0123456789abcdef';
    if (opts.uppercase) {
      keyspace = keyspace.toUpperCase();
    }
  } else {
    if (opts.alpha) {
      keyspace += 'abcdefghijklmnopqrstuvwxyz';
    }

    if (opts.uppercase) {
      keyspace += 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    }

    if (opts.numeric) {
      keyspace += '0123456789';
    }

    if (opts.punctuation) {
      keyspace += "`!\"?$?%^&*()_-+={[}]:;@'~#|\\<,>.?/";
    }
  }

  if (keyspace.length - 1 < 0) {
    return '';
  }

  opts.size = opts.size >>> 0 || 16;
  if (opts.size < 5) {
    opts.size = 5;
  } else if (opts.size > 100) {
    opts.size = 100;
  }

  return shuffle(keyspace.split('')).join('').slice(0, opts.size);
}

var password = generatePassword({
  alpha: true,
  uppercase: true,
  numeric: true,
  punctuation: true
});

console.log(password);

Other options are hex generation an size for length

You could modify it to take a string of special characters you want to use.

Update: Here is a more complex example that enforces a number of each type of chosen characters and works similar to the above simple example.

function isObject(value) {
  return Object.prototype.toString.call(value) === '[object Object]';
}

function assign(target, source) {
  for (var prop in source) {
    if (source.hasOwnProperty(prop)) {
      target[prop] = source[prop];
    }
  }

  return target;
}

function shuffle(obj) {
  var i = obj.length;
  var rnd, tmp;

  while (i) {
    rnd = Math.floor(Math.random() * i);
    i -= 1;
    tmp = obj[i];
    obj[i] = obj[rnd];
    obj[rnd] = tmp;
  }

  return obj;
}

function getXChars(string, number) {
  var str = typeof string === 'string' ? string : '';
  var num = typeof number === 'number' && number > 0 ? number : 0;
  var array = [];
  var i = str.length;
  var rnd;

  while (i && array.length < num) {
    rnd = Math.floor(Math.random() * i);
    i -= 1;
    array.push(str.charAt(rnd));
  }

  return array;
}

function generatePassword(opts) {
  var opts = isObject(opts) ? assign({}, opts) : {};
  var keyspace = '';
  var result = [];
  var i = 0;
  var tmp;

  if (typeof opts.hex === 'number' && opts.hex > 0) {
    i += opts.hex;
    keyspace = '0123456789abcdef';
    if (opts.uppercase === true) {
      keyspace = keyspace.toUpperCase();
    }

    result = result.concat(getXChars(keyspace, opts.hex));
  } else {
    if (typeof opts.alpha === 'number' && opts.alpha > 0) {
      i += opts.alpha;
      tmp = 'abcdefghijklmnopqrstuvwxyz';
      keyspace += tmp;
      result = result.concat(getXChars(tmp, opts.alpha));
    }

    if (typeof opts.uppercase === 'number' && opts.uppercase > 0) {
      i += opts.uppercase;
      tmp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
      keyspace += tmp;
      result = result.concat(getXChars(tmp, opts.uppercase));
    }

    if (typeof opts.numeric === 'number' && opts.numeric > 0) {
      i += opts.numeric;
      tmp = '0123456789';
      keyspace += tmp;
      result = result.concat(getXChars(tmp, opts.numeric));
    }

    if (typeof opts.punctuation === 'number' && opts.punctuation > 0) {
      i += opts.punctuation;
      tmp = "`!\"?$?%^&*()_-+={[}]:;@'~#|\\<,>.?/";
      keyspace += tmp;
      result = result.concat(getXChars(tmp, opts.punctuation));
    }
  }

  if (keyspace.length === 0) {
    return keyspace;
  }

  opts.size = opts.size >>> 0 || 16;
  if (opts.size < 5) {
    opts.size = 5;
  } else if (opts.size > 100) {
    opts.size = 100;
  }

  result = result.concat(getXChars(keyspace, opts.size - i));

  return shuffle(result).join('');
}

var password = generatePassword({
  alpha: 1,
  uppercase: 1,
  numeric: 1,
  punctuation: 1
});

console.log(password);

Update: As promised here is a possible replacement for Math.random. If window.crypto.getRandomValues is available then it will use it, otherwise it falls back to Math.random.

function random() {
  if (window.crypto && typeof window.crypto.getRandomValues === 'function') {
    console.log('Using crypto');
    var array = new Uint32Array(1);
    window.crypto.getRandomValues(array);
    return array[0] / (Math.pow(2, 32) + 1);
  }

  console.log('Using random');
  return Math.random();
}

console.log(random());

Answer 3

I think you need to pick you characters from different arrays depending on the requirements for the array. This is my solution:

var alphas = "abcdefghjknpqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ";
var specials = "!#$%&/()=`";
var numbers = "1234567890";

var requiredSpecials = 1;
var requiredNumbers = 2;

function pickRandom(str, count){
    var remaining = str;
    var result = "";
    while (remaining.length > 0 && count > 0){
        // pick random char from remaining
        var char = remaining.charAt(Math.floor(Math.random() *remaining.length));

        // remove char from remaining. (Just replace with empty string)
        remaining = remaining.replace(char, "");

        // add char to result
        result += char;

        // decrement count
        count -= 1;
    }

    return result;
}

function shuffleString(str){
    var arr = str.split(''); // Convert to array
    arr.sort(function(){ // Sort by random
        return 0.5-Math.random()
    })
    return arr.join(''); // Join back to string
}

function generate(length){
    var specialCount = requiredSpecials;
    var numberCount = requiredNumbers;
    var alphaCount = length - specialCount - numberCount;

    var tmp = pickRandom(alphas, alphaCount) + pickRandom(specials, specialCount) + pickRandom(numbers, numberCount);

    // Shuffle and return
    return shuffleString(tmp);
}

alert(generate(9))

You can also play around with it at jsFiddle