Question

You are safeguarding a gate; anybody passing the gate has to tell you his/her name and password. Since there is no sound protection, anybody nearby can hear what they say and get the passwords. To solve that problem, you are requesting that each password can be used only once. Initially, you give each authorized person a list of passwords, and ask them to cross one out each time when a password is used, so each password is used only once. It is important to use the list of passwords in order. However, you do not want to maintain such a list yourself. You only want to remember one password for each person. Note that all passwords are HEX numbers (each number is up to 32 bytes). You do not mind changing this number each time when a secret password is used. Basically, each time you generate the next number in the list and replace the current number. Describe how you can do this.

Answer 1

Random number generators typically work on bits, so the range of numbers they can generate is a power of two. A range of characters like [0-9a-zA-Z] has 62 characters, which is two shy of a power of two (64), so the computer has to do some conversion between the ranges.

That can be done, but it's easy to get it wrong. The "standard" way is to take the actual number, divide it by the range you want, and take the remainder as your random number. That introduces bias though. For a simple example, say you generate numbers in [0-3] but you want them in [0-2] instead. The [0-3] range would map to the [0-2] range like so:

0 => 0 mod 3 => 0
1 => 1 mod 3 => 1
2 => 2 mod 3 => 2
3 => 3 mod 3 => 0
Note how you can get a 0 in two different ways: 0 and 3 both go to 0. The approach is biased toward generating 0s, which will make your password easier to guess.

The correct way involves computing the right padding to make what you generated fit evenly into the range, which is tricky and could potentially make your password a lot longer depending on how your output range compares to that of the random number generator.

An easier approach is to just use a range that's already a power of two so you can ignore the bias entirely. Most have problems.

Base-2 (binary) produces extremely long strings.
Base-4 (quaternary) isn't much better.
Base-8 (octal) is better but still lengthy.
Base-16 (hex) is a little long, but reasonable. It also encodes 4 bits per character, which is pretty convenient when computers prefer multiples of 8.
Base-32 encodes 5 bits per character, which is not convenient when computers prefer multiples of 8.
Base-64 encodes 6 bits per character, which is still awkward (but slightly less since at least it's an even number).
Base-96 is popular, but not a power of 2 so it has the same problem as [0-9a-zA-Z].
Base-128 and above all involve symbols you can't easily type on a typical querty keyboard.
To expand a little on why base-64 is a problem, consider what happens when you try to encode a single byte (8 bits). You can't do it with a single base-64 character since that only gets 6 of the 8 bits. But if you use two characters, you have to figure out how to pad your 8-bit byte to a 12-bit output without introducing bias or suggesting there might be an extra byte.

Hex, in contrast, is almost trivial to encode bytes in. Just look up each byte in a 256 element table to get two characters and spit them out. It gives reasonably short passwords, doesn't use weird symbols, and it's simple to implement. It's the best choice for security conscious password generators.