Parallel-External Computation of the Cycle Structure of Invertible Cryptographic Functions

We present an algorithm to compute the cycle structure of large directed graphs where each node has exactly one outgoing edge. Such graphs appear as state diagrams of finite state machines such as pseudorandom number generators in cryptography. The size of the graphs necessitates that the adjacency list is kept on hard disks. Our algorithm uses multiple processing units, so that a parallel storage system has to be employed to store the graph. We present experimental results for randomly chosen graphs, and for the graph of the A5/1 generator used in GSM mobile phones