Colossus computer

From Free net encyclopedia

The Colossus machines were early computing devices used by British codebreakers to read encrypted German messages during World War II. Colossus was an early electronic digital computer.

Colossus was designed by engineer Tommy Flowers at the Post Office Research Station, Dollis Hill. The prototype, Colossus Mark I, was operational at Bletchley Park in February 1944. An improved Colossus Mark II was first installed in June 1944, and ten Colossi had been constructed by the end of the war.

The Colossus computers were used to help decipher teleprinter messages which had been encrypted using the Lorenz SZ40/42 machine. Colossus compared two data streams, counting each match based on a programmable boolean function. The encrypted message was read at high speed from a paper tape. The other stream was generated internally, and was an electronic simulation of the Lorenz machine at various trial settings. If the match count for a setting was above a certain threshold, it would be output on an electric typewriter.

1 Purpose and origins
2 The construction of Colossus
3 Design and operation
4 Influence and fate
5 Reconstruction
6 See also
7 Footnotes
8 References
9 Further reading
10 Other meanings
11 External links

[edit]

Purpose and origins

Image:SZ42-6-wheels.jpg The Colossus computers were used in the cryptanalysis of high-level German communications, messages which had been encrypted using the Lorenz SZ 40/42 cipher machine; part of the operation of Colossus was to emulate the mechanical Lorenz machine electronically. To encrypt a message with the Lorenz machine, the plaintext was combined with a stream of key bits, grouped in fives. The key stream was generated using twelve pinwheels: five were termed (by the British) <math>\chi</math> ("chi") wheels, another five <math>\psi</math> ("psi") wheels, and the remaining two the "motor wheels". The <math>\chi</math> wheels stepped regularly with each letter that was encrypted, while the <math>\psi</math> wheels stepped irregularly, controlled by the motor wheels.

Bill Tutte, a cryptanalyst at Bletchley Park, discovered that the keystream produced by the machine exhibited statistical biases deviating from random, and that these biases could be used to break the cipher and read messages. In order to read messages, there were two tasks that needed to be performed. The first task was wheel breaking, which was discovering the pin patterns for all the wheels. These patterns were set up once on the Lorenz machine and then used for a fixed period of time and for a number of different messages. The second task was wheel setting, which could be attempted once the pin patterns were known. Each message encrypted using Lorenz was enciphered at a different start position for the wheels. The process of wheel setting found the start position for a message. Initially Colossus was used to help with wheel setting, but later it was found it could also be adapted to the process of wheel breaking as well.

Colossus was operated in the Newmanry, the section at Bletchley Park responsible for machine methods against the Lorenz machine, headed by the mathematician Max Newman.

Colossus developed out of a prior project which produced a special purpose opto-mechanical comparator machine called "Heath Robinson". The main problem with Robinson was synchronising two paper tapes, one punched with the enciphered message, the other representing the patterns produced by the wheels of the Lorenz machine, that tended to stretch when being read at over 1000 characters per second, resulting in unreliable counts. Colossus solved this problem by reproducing one of the tapes electronically. The remaining single tape could be fed through Colossus at a higher speed and could be counted much more reliably.

[edit]

The construction of Colossus

Tommy Flowers, an engineer brought in to assist with machinery to break the Enigma machine, spent ten months building Colossus at the Post Office Research Station, Dollis Hill, North London. Work on the design of the Mark I started early in February 1943, and the machine was assembled at Bletchley Park and tested on 8 December 1943. By February 1944, the Colossus was in operational use by the codebreakers. It was followed into service by nine Mark II Colossus machines, the first installed in June 1944. An eleventh Colossus was under construction at the end of the war.

Colossus Mark I contained 1,500 electronic valves – by comparison, early stored program computers like the Manchester Mark I used about 4,000 and ENIAC about 18,000. The Colossus Mark II was simpler to operate as well as being more advanced, and so greatly speeded the deciphering process, which was largely still carried out by hand.

Colossus dispensed with the second tape of the Heath Robinson design by generating the wheel patterns electronically, and could process 5,000 characters (40 feet / 12m of tape) per second. The circuits were synchronized by a clock signal generated by the punched tape. The speed of calculation was thus limited by the mechanics of the tape reader.

Colossus included the first ever use of shift registers and systolic arrays, enabling five simultaneous tests, each involving up to 100 Boolean calculations, on each of the five channels on the punched tape (although in normal operation only one or two channels were examined in any run).

Initially Colossus was only used to determine the initial wheel positions used for a particular message (termed wheel setting); the Mark II included mechanisms intended to help determine pin patterns (wheel breaking). Both models were programmable using switches and plug panels, in a way the Robinsons had not been.

[edit]

Design and operation

Image:Colossus-rebuild.jpg Colossus used state-of-the-art vacuum tubes (thermionic valves), thyratrons and photomultipliers to optically read a paper tape and then applied a programmable logical function to every character, counting how often this function returned "true". Although machines with many valves were known to have high failure rates, it was recognised that valve failures occurred most frequently with the current surge at power on, so the Colossus machines, once turned on, were never powered down unless they malfunctioned.

Colossus was the first of the electronic digital machines to feature limited programmability. However, it was not a fully general purpose computer, not being Turing-complete, even though Alan Turing on whose research this definition was based, worked at Bletchley Park where Colossus was put into operation. It was not then realized that Turing-completeness was significant; most of the other pioneering modern computing machines were not either (e.g. the Atanasoff-Berry Computer, the Harvard Mark I electro-mechanical relay machine, the Bell Labs relay machines (by George Stibitz et al), Konrad Zuse's first two designs, and so on). The notion of a computer as a general purpose machine, and not simply a massive calculator devoted to solving difficult but single-minded problems, did not become prominent until a few years later.

Colossus was preceded by several computers, many of them first in some category. Zuse's Z3 was the first functional fully program-controlled computer, and was based on electromechanical relays, as were the (less advanced) Bell Labs machines of the late 1930s (George Stibitz, et al). The ABC Computer was electronic and binary (digital) but not programmable. Assorted analog computers were semiprogrammable, some of these much predated the 1930s (eg, Vannevar Bush). Babbage's Analytical engine antedated all these (in the mid-1800s), and was both digital and programmable, but was only partially constructed and never functioned at the time (a replica of his Difference engine No. 2, built in 1991 does work, however). Colossus was the first combining digital, (partially) programmable, and electronic.

[edit]

Influence and fate

The use to which the Colossi were put was of the highest secrecy, and the Colossus itself was highly secret, and remained so for many years after the War. Thus, Colossus could not be included in the history of computing hardware for many years, and Flowers and his associates also were deprived of the recognition they were due.

Being not widely known, it therefore had little direct influence on the development of later computers; EDVAC was the early design which had the most influence on subsequent computer architecture.

However, the technology of Colossus, and the knowledge that reliable high-speed electronic digital computing devices were feasible, had a significant influence on the development of early computers in Britain. A number of people who were associated with the project and knew all about Colossus played significant roles in early computer work in Britain. In 1972, Herman Goldstine wrote that:

"Britain had such vitality that it could immediately after the war embark on so many well-conceived and well-executed projects in the computer field"<ref>The Computer from Pascal to von Neuman (pp. 321)</ref>.

In writing that, Goldstine was unaware of Colossus, and its legacy to those projects of people such as Alan Turing (with the Pilot ACE and ACE), and Max Newman and I. J. Good (with the Manchester Mark I and other early Manchester computers). Brian Randell later wrote that:

"the COLOSSUS project was an important source of this vitality, one that has been largely unappreciated, as has the significance of its places in the chronology of the invention of the digital computer"<ref>The COLOSSUS, pp. 87</ref>.

Colossus documentation and hardware were classified from the moment of their creation and remained so after the War, when Winston Churchill specifically ordered the destruction of most of the Colossus machines into 'pieces no bigger than a man's hand'; Tommy Flowers personally burned blueprints in a furnace at Dollis Hill. Some parts, sanitised as to their original use, were taken to Newman's Computing Machine Laboratory at Manchester University. The Colossus Mark I was dismantled and parts returned to the Post Office. Two Colossus computers, along with two replica Tunny machines, were retained, moving to GCHQ's new headquarters at Eastcote in April 1946, and moving again with GCHQ to Cheltenham between 1952 and 1954<ref name="copeland173-175">Copeland, 2006, p. 173-175</ref>. One of the Colossi, known as Colossus Blue, was dismantled in 1959; the other in 1960<ref name="copeland173-175"/>. In their later years, the Colossi were used for training, but before that, there had been attempts to adapt them, with varying success, to other purposes<ref>Horwood, 1973</ref>. Jack Good relates how he was the first to use it after the war, persuading the NSA that Colossus could be used to perform a function for which they were planning to build a special purpose machine<ref name="copeland173-175"/>. Colossus was also used to perform character counts on one-time pad tape to ensure their randomness<ref name="copeland173-175"/>.

Information about Colossus began to emerge publicly in the late 1970s, after the secrecy imposed by the Official Secrets Act ended in 1976. More recently, a 500-page technical report on the Tunny cipher and its cryptanalysis – entitled General Report on Tunny – was released by GCHQ to the national Public Record Office in October 2000; the complete report is available online [1], and it contains a fascinating paean to Colossus by the cryptographers who worked with it:

It is regretted that it is not possible to give an adequate idea of the fascination of a Colossus at work; its sheer bulk and apparent complexity; the fantastic speed of thin paper tape round the glittering pulleys; the childish pleasure of not-not, span, print main header and other gadgets; the wizardry of purely mechanical decoding letter by letter (one novice thought she was being hoaxed); the uncanny action of the typewriter in printing the correct scores without and beyond human aid; the stepping of the display; periods of eager expectation culminating in the sudden appearance of the longed-for score; and the strange rhythms characterizing every type of run: the stately break-in, the erratic short run, the regularity of wheel-breaking, the stolid rectangle interrupted by the wild leaps of the carriage-return, the frantic chatter of a motor run, even the ludicrous frenzy of hosts of bogus scores. [2]

[edit]

Reconstruction

A construction of a replica of a Colossus Mark II has been undertaken by a team led by Tony Sale. The reconstruction is on display in the Bletchley Park Museum in Milton Keynes, Buckinghamshire.

[edit]

Footnotes

[edit]

References

W. W. Chandler, The Installation and Maintenance of Colossus (IEEE Annals of the History of Computing, Vol. 5 (No. 3), 1983, pp. 260–262)
Allen W. M. Coombs, The Making of Colossus (Annals of the History of Computing, Vol. 5 (No. 3), 1983, pp.253-259)
Jack Copeland, Colossus: Its Origins and Originators (IEEE Annals of the History of Computing, 26(4), October–December 2004, pp. 38–45).
Jack Copeland, Colossus and the Dawning of the Computer Age, in Action This Day, 2001, ISBN 0593049829.
B. Jack Copeland (editor), Colossus: The Secrets of Bletchley Park's Codebreaking Computers, 2006, Oxford University Press, ISBN 019284055X.
I. J. Good, Early Work on Computers at Bletchley (IEEE Annals of the History of Computing, Vol. 1 (No. 1), 1979, pp. 38–48)
I. J. Good, Pioneering Work on Computers at Bletchley (in Nicholas Metropolis, J. Howlett, Gian-Carlo Rota, (editors), A History of Computing in the Twentieth Century, Academic Press, New York, 1980)
T. H. Flowers, The Design of Colossus (Annals of the History of Computing, Vol. 5 (No. 3), 1983, pp. 239–252)
D C Horwood, A technical description of COLOSSUS I, August 1973, PRO HW 25/24.
Brian Randell, Colossus: Godfather of the Computer, 1977 (reprinted in The Origins of Digital Computers: Selected Papers, Springer-Verlag, New York, 1982)
Brian Randell, The COLOSSUS (in A History of Computing in the Twentieth Century)
Albert W. Small, The Special Fish Report (December, 1944) describe the operation of Colossus to break Tunny messages