In the preceding sections, we have seen ways to convert a message consisting of binary bits into either base-26 or base-10 for transmission. Since it is intended that the message ultimately be read by its legitimate recipient, it is necessary that the conversion be invertible.
People working with simulation problems on computers have developed techniques for base conversion that are simplified because they do not need to take this constraint into account.
One could have a standard pseudorandom number generation routine, and it might produce numbers from 0 to 32,767 each time it is run. And for a particular problem, one needs uniformly distributed integers from 0 to 922.
The simplest way of doing this is to note that 15 times 923 is 32,305. So, when you generate a pseudorandom number, if it is from 0 to 32,304, take the remainder when it is divided by 923 as your number from 0 to 922, otherwise, discard the result.
This isn't invertible, as more than one sequence of numbers from 0 to 32,768 will lead to the same sequence of numbers from 0 to 922, but that is not a concern for such an application. But because it throws away information, it is somewhat wasteful: particularly worrying is the chance of a long run of pseudorandom numbers from 32,305 to 32,767, which could cause delays.
Essentially, when a number is generated, a random number from 0 to 34 is being thrown away, and when one is not being generated, a number from 0 to 462 is being thrown away. One can improve the efficiency of the conversion process by keeping these numbers, and treating them the same way, in essence, as we treated the output of our binary pseudorandom number generator.
To illustrate this technique with a more useful example:
Let's say you want to convert a stream of random bits into uniformly distributed numbers from 0 to 999.
Then, you start by taking the bits 10 at a time to give you a number from 0 to 1023. If that number is less than 1000, you've got a number. (Note that here one does not have a multiple of 1000, so there is nothing to save when a number is generated. In general, this will always be true if we start from a stream of bits which we can use in groups of any size, since if we are using enough bits to give us a number twice as large as the desired number, we are using one bit too many.)
Otherwise, subtract 1000 from the number, to give you a number from 0 to 23. Treat that as a base-24 digit, and introduce it into another accumulator (acc = acc*24 + new_digit) that holds numbers up to 24^3, or 13824.
When this has happened three times, if the number in the accumulator is from 0 to 12999, take the last three digits as your number.
If you want, you can now repeat the process by taking the first few digits, as a number from 0 to 12, and therefore a base-13 digit, and save them in an accumulator; and, if you get a result you can't use, a number from 13000 to 13824, you can subtract 13000 and save that result as a base-824 digit.Since 1000 is a multiple of 8, however, we could simplify the process, at least by requiring smaller accumulators for the calculations, and thus potentially avoiding multiprecision multiplications, by modifying it as follows: take the stream of bits seven bits at a time, and convert it into numbers from 0 to 124, that is, base-125 digits. When the process has successfully produced such a number, then take three more bits from the keystream to make it a number from 0 to 999.
The process for that case follows the same scheme as the direct process for producing numbers from 0 to 999, but because the omitted powers of two change the size of the numbers involved, an exact analogy between the digit sizes involved breaks down at later steps.
Take seven bits from the keystream, giving a number from 0 to 127. If that number is from 0 to 124, it is the result. Otherwise, subtract 125 from the number, giving a number from 0 to 2. Introduce this base-3 digit into an accumulator that holds numbers up to 3^5, or 243.
When that accumulator has 5 digits in it, it contains a random number from 0 to 242. If it is from 0 to 124, accept it as the result. Otherwise, subtract 125, and put the resulting number, from 0 to 117, in another accumulator, and so on.
Where you want to stop, and just throw away unusable results, depends on how efficiently you want to convert the random bit stream to a random digit stream.
This can certainly be used in cryptography to allow a binary stream cipher to encipher a plaintext composed of digits into a ciphertext also composed of digits.
If one is enciphering binary plaintext to binary ciphertext, one could use two keystream generators, for example, one designed to produce pseudorandom base-7 digits from 0 to 6, and another designed to produce pseudorandom base-23 digits from 0 to 22, independently converting the outputs of each to, say, base 256 using the technique given above, and using the XOR of the two converted keystreams on the plaintext. The use of two different bases to produce binary bits, which are then combined in the binary world, would make many forms of analysis much more complicated. However, this type of cryptography is vulnerable to timing attacks and related techniques such as monitoring the power consumption of a chip, because sometimes extra steps are required to produce the output in a new base.