I am trying to understand the basic TMTO by Diffie Hellman as described here. I am having trouble understanding this passage here:
Hellman had the idea of storing the dictionary in the form of long chains. A randomly chosen key, with which a specific message is encrypted, stands at the beginning of such a chain. The result of the first pass is used as a key for encrypting the original message during the next pass. The result of this pass provides the key for the next one, and so on, until the chain has reached a predefined length. In order to save space, Hellman stored only the first and last values in the chain. The dictionary thus compressed is a two-column table sorted by end value.
What does the author mean by first and by last value? If I use a key a (from a set A of keys) on a certain cipher, it should give me a result b (from a set B of possible results). Now what exactly are the middle values in this process?
Also, do I get it right: in order to save memory the sets A and B are conjuncted? So when a 64-bit key a1 produces a 64-bit b1, in the next step we have b1=a2 (so in the image above, it should be 77CF=22CB)? But how does that work in ciphers where key and output length are not the same length? Also why does the author speak of a table, if the data structure here would obviously is a list? it would especially be no lookup-table, as the keys/values would be in a random order, so you could not look up a certain key/value by its bit-order (00001 00010 00011 ...) and would have to go through the entire database to find the entry you are looking for.