It's possible this might be more documented on old warez/cracking/serial # generation tutorials if they're still around anywhere. This is only speculation but I imagine the process would be something like breaking a CD-key into multiple parts (a unit#, salt, hash of the unit#+salt)
1. Using unit# + some known/random salt, compute a hash
2. Mix-in the unit# + salt to the resulting hash in some deterministic fashion (prefix, suffix, or maybe inserting/replacing into a known/random location)
3. Convert the hash result into a CD-key format
Generate one for each unit produced, print on a label and attach to the distributed product. When installing, the process to verify the key would be
1. Extract the unit# from the entered CD-key (or if randomly inserted/replaced just do this for each possibly bytes assuming its the unit# + salt)
2. Using the unit# follow the same 3 steps above to get a CD-key
3. Compare the generated CD-key to the one entered for validity
Using hash is fast, produces an output with a very large output range (not easily guessed) and unlikely to have collisions, while also limiting the possibly valid keys to (roughly) however many bits necessary for a unit#. This method also allows for offline validation since the key to the hash is being shipped as part of the CD-key, and this was back in the days when a constant-connection to internet wasn't available or necessary for licensing.
The downside, which was the bane of most producers, is that a reverse-engineer who acquires a copy of the software can use a debugger or disassembler to extract out the first 3 steps above to create a keygen. Once the keygen was out though basically anyone could generate their own valid keys. In order to combat this software makers started requiring an additional step that after validating the key it contacts a central server to see if anyone else has used it or not...
> How did the authentication system work? How difficult was it to brute force? Does it simply involve a master key creating individual subkeys? Is it RSA?
Producing individual builds/images to burn onto CD's was unlikely as it would make the CD production process impractical -- a single build/image for burning CD's was likely used until they ran out of stock and/or wanted to ship updated versions of the software. Using RSA would otherwise be a great solution as the software producer could generate private keys for each sold license. Many newer software licensing schemes have this approach.
Edit: Related answer on StackOverflow:
https://stackoverflow.com/questions/3002067/how-are-software...