CODEWITHSUNDEEP
hashcryptographycryptojscryptographic-hash-function
Wor Chan
Wor Chan

Reputation: 169

Generate strong password from a Big Integer

I have a big integer in javascript, having 128 single digit numbers. I generated this big integer from the hex sum of SHA3-512.

I would like to derive a password from this big integer, following the rules for a strong pasword:

Now, I would like to generate a password of at least 20 characters from this big integer. How can I do that? I would like to make this function so that whenever I pass the same big integer, it gives me the same password everytime (just like hashing algorithms).

Upvotes: 1

Views: 81

Answers (1)

Maarten Bodewes
Maarten Bodewes

Reputation: 93948

So you have this huge number X in the range [0, 2^512). Surely you can get a password from it, and you can use something like base conversion.

What you first want to do is to create a range for each character position starting from 0, which could e.g. be the character A, say [0, Mi) where M is the amount of characters and i is the index in the password. The number of characters at a certain position is called an alphabet (the English ABC is one specific alphabet, usually called the alphabet).

Now if you create the product over all the Mi, giving you the value N. Now you get the remainder of X over N, let's call this Y. Now you have a number that is reasonably unbiased as long as 2^512 is much larger than N. It and represents all of the passwords possible by index. Nice, but how do you get a password by index, you cannot list them all.

This is where we need to do some more number magic. What you do need to do is to calculate the remainder of Y over Mi, then divide Y by Mi, giving you Ci. You then lookup character Ci within the alphabet for position i, and put it into the password string.

Here's an example I created before in Java (sorry, conversion necessary):

import java.math.BigInteger;
import java.security.MessageDigest;

public class CreatePasswordFromLargeRandom {

    private static final String ALPHABET_UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final String ALPHABET_LOWER = "abcdefghijklmnopqrstuvwxyz";
    private static final String ALPHABET_UPPERLOWER = ALPHABET_UPPER + ALPHABET_LOWER;
    private static final String ALPHABET_DIGITS = "0123456789";
    
    private static final BigInteger SHA512_RANGE = BigInteger.TWO.pow(512);
    
    public static char[] createPassword(BigInteger rangeOfX, BigInteger x, char[]... alphabets) {
        // n is the amount of passwords possible
        var n = BigInteger.ONE;
        for (int i = 0; i < alphabets.length; i++) {
            n = n.multiply(BigInteger.valueOf(alphabets[i].length));
        }
        
        if (rangeOfX.bitLength() - n.bitLength() < 64) {
            throw new IllegalArgumentException("Range of X value too small compared with the number of possible passwords, bias would be introduced");
        }
        
        // y is an index into all the possible passwords
        var y = x.remainder(n);
        
        var password = new char[alphabets.length];
        // using least significant values for digits on the right
        for (int i = alphabets.length - 1; i >= 0; i--) {
            var yc  = y.divideAndRemainder(BigInteger.valueOf(alphabets[i].length));
            y = yc[0];
            // c is the index in the current alphabet
            var c = yc[1].intValueExact();
            password[i] = alphabets[i][c];
        }
        return password;
    }
    
    public static void main(String[] args) throws Exception {
        var sha512 = MessageDigest.getInstance("SHA-512");
        var digest = sha512.digest(new byte[0]);
        var x = new BigInteger(1, digest);
        
        var upperLower = ALPHABET_UPPERLOWER.toCharArray();
        var digits = ALPHABET_DIGITS.toCharArray();
        
        var password = createPassword(SHA512_RANGE, x, upperLower, digits, upperLower, digits);
        System.out.println(new String(password));
    }
}

which simply outputs h5g6.

To get an idea how this works: if you input zero for X then you'd get password "A0A0", the password that has the lowest index. You'd get the same value if you'd input K times N for any K, as that will produce the same index. Any X that is N - 1 (mod N) will produce the last password possible, "z9z9" in this case.

Upvotes: 1

Related Questions