Jump to content

Colossus computer

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 84.212.139.184 (talk) at 12:54, 7 October 2012 (External links). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Colossus MkI/MkII
A Colossus Mark 2 computer. The operators are (left to right) Dorothy Du Boisson and Elsie Booker. The slanted control panel on the left was used to set the pin patterns on the Lorenz. The "bedstead" paper tape transport is on the right.
DeveloperTommy Flowers
ManufacturerPost Office Research Station
TypeSpecial-purpose electronic digital programmable computer
GenerationFirst-generation computer
Release dateMk 1: December 1943 (1943-12); Mk 2: 1 June 1944 (1944-06-01)
Discontinued8 June 1945 (1945-06-08)
Units shipped10
MediaPaper tape, teleprinter output
CPUCustom circuits using valves and Thyratrons. A total of 1500 in each Mk I and 2400 in Mk II. Also uniselectors
MemoryNone (no RAM)
Storage≤ 20 000 × 5-bit characters in paper tape loop
DisplayIndicator lamp panel
Inputconsole switches and plug panel

Colossus was the world's first electronic, digital, computer that was at all programmable. Colossus and its successors were used by British codebreakers to help read encrypted German messages during World War II. They used thermionic valves (vacuum tubes) to perform the calculations.

Colossus was designed by engineer Tommy Flowers with input from Sidney Broadhurst, William Chandler, Allen Coombs and Harry Fensom,[1] at the Post Office Research Station, located at Dollis Hill, to solve a problem posed by mathematician Max Newman at Bletchley Park. The prototype, Colossus Mark 1, was shown to be working in December 1943 and was operational at Bletchley Park by 5 February 1944.[2] An improved Colossus Mark 2 first worked on 1 June 1944,[3] just in time for the Normandy Landings. Ten Colossus computers were in use 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—British codebreakers referred to encrypted German teleprinter traffic as "Fish" and called the SZ40/42 machine and its traffic "Tunny". 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 sent as output to an electric typewriter.

The Colossus was used to find possible key combinations for the Lorenz machines – rather than decrypting an intercepted message in its entirety. For more information see Cryptanalysis of the Lorenz cipher.

In spite of the destruction of most of the Colossus hardware and blueprints as part of the effort to maintain a project secrecy that was kept up into the 1970s—a secrecy that deprived some of the Colossus creators of credit for their pioneering advancements in electronic digital computing during their lifetimes—a functional replica of a Colossus computer was completed in 2007.

Purpose and origins

The Lorenz machine was used by the Germans to encrypt high-level teleprinter communications. It contained 12 wheels with a total of 501 pins.

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 electromechanical 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 keystream was generated using twelve pinwheels: five were termed (by the British) χ ("chi") wheels, another five ψ ("psi") wheels, and the remaining two the "motor wheels". The χ wheels stepped regularly with each letter that was encrypted, while the ψ 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 developed for the Newmanry, the section at Bletchley Park responsible for machine methods against the Lorenz machine, headed by the mathematician Max Newman. It arose out of a prior project which produced a special purpose opto-mechanical comparator and counting machine called "Heath Robinson".

The main problems with the Heath Robinson were the relative slowness of electro-mechanical relays and the difficulty of synchronising two paper tapes, one punched with the enciphered message, the other representing the patterns produced by the wheels of the Lorenz machine. The tapes tended to stretch when being read at some 2000 characters per second, resulting in unreliable counts. Tommy Flowers of the Post Office Research Station at Dollis Hill was called in to look into the design of the Robinson's combining unit. He was not impressed with the machines and, at his own initiative, designed an electronic machine which stored the data from one of the tapes internally. He presented this design to Max Newman in February 1943, but the idea that the one to two thousand thermionic valves (vacuum tubes) proposed, could work together reliably was greeted with scepticism, so more Robinsons were ordered from Dollis Hill. Flowers, however, persisted with the idea and obtained support from the Director of the Research Station.

Construction

Tommy Flowers spent eleven months (early February to December 1943) designing and building Colossus at the Post Office Research Station, Dollis Hill, in northwest London. After a functional test in December 1943, Colossus was dismantled and shipped north to Bletchley Park, where it was delivered on 18 January 1944 and assembled by Harry Fensom and Don Horwood,[4] and attacked its first message on 5 February.[5]

The first Colossus, Mark 1, was followed by nine Mark 2 machines, the first being commissioned in June 1944, and the original Mark 1 machine was converted into a Mark 2. An eleventh Colossus was essentially finished at the end of the war. Colossus Mark 1 contained 1,500 electronic valves (tubes). Colossus Mark 2 with 2,400 valves was both 5 times faster and simpler to operate than Mark 1, greatly speeding the decoding process. Mark 2 was designed while Mark 1 was being constructed. Allen Coombs took over leadership of the Colossus Mark 2 project when Tommy Flowers moved on to other projects.[citation needed] For comparison, later stored-program computers such as the Manchester Mark 1 of 1949 used 4,050 valves.[6] In comparison, ENIAC (1946) used 17,468 valves.

Colossus dispensed with the second tape of the Heath Robinson design by generating the wheel patterns electronically, and processing 5,000 characters per second with the paper tape moving at 40 ft/s (12.2 m/s or 27.3 mph). The circuits were synchronized by a clock signal generated by the sprocket holes of the punched tape. The speed of calculation was thus limited by the mechanics of the tape reader. Tommy Flowers tested the tape reader up to 9,700 characters per second (53 mph) before the tape disintegrated. He settled on 5,000 characters/second as the desirable speed for regular operation. Sometimes, two or more Colossus computers tried different possibilities simultaneously in what now is called parallel computing, speeding the decoding process by perhaps as much as doubling the rate of comparison.

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 2 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.

Design and operation

In 1994, a team led by Tony Sale (right) began a reconstruction of a Colossus at Bletchley Park. Here, in 2006, Sale supervises the breaking of an enciphered message with the completed machine.

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 when powering up, so the Colossus machines, once turned on, were never powered down unless they malfunctioned.[7]

Colossus was the first of the electronic digital machines with programmability, albeit limited by modern standards:[8]

  • it had no internally stored programs. To set it up for a new task, the operator had to set up plugs and switches to alter the wiring.
  • Colossus was not a general-purpose machine, being designed for a specific cryptanalytic task involving counting and Boolean operations.

It was thus not a fully general Turing-complete computer, even though Alan Turing worked at Bletchley Park. It was not then realized that Turing completeness was significant; most of the other pioneering modern computing machines were also not Turing complete (e.g. the Atanasoff–Berry Computer, the Bell Labs relay machines (by George Stibitz et al.), or the first designs of Konrad Zuse). The notion of a computer as a general purpose machine—that is, as more than a calculator devoted to solving difficult but specific problems—did not become prominent for several years.

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 Atanasoff–Berry Computer was electronic and binary (digital) but not programmable. Assorted analog computers were semiprogrammable; some of these much predated the 1930s (e.g., Vannevar Bush). Babbage's Analytical engine design predated all these (in the mid-19th century), it was a decimal, programmable, entirely mechanical construction—but was only partially built and never functioned during Babbage's lifetime (the first complete mechanical Difference engine No. 2, built in 1991, does work however). Colossus was the first combining digital, (partially) programmable, and electronic. The first fully programmable digital electronic computer was the ENIAC which was completed in 1946.

Influence and fate

The use to which the Colossus computers 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 the United Kingdom and probably in the US. A number of people who were associated with the project and knew all about Colossus played significant roles in early computer work in the UK. 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.[9]

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 1 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.[10]

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 Royal Society Computing Machine Laboratory at Manchester University.[11] The Colossus Mark 1 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.[12] One of the Colossi, known as Colossus Blue, was dismantled in 1959; the other in 1960.[12] 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.[13] Jack Good relates how he was the first to use it after the war, persuading NSA that Colossus could be used to perform a function for which they were planning to build a special purpose machine.[12] Colossus was also used to perform character counts on one-time pad tape to test for non-randomness.[12]

Throughout this period the Colossus remained secret, long after any of its technical details were of any importance. This was due to the UK's intelligence agencies use of Enigma-like machines which they promoted and sold to other governments, and then broke the codes using a variety of methods. Had the knowledge of the codebreaking machines been widely known, no one would have accepted these machines; rather, they would have developed their own methods for encryption, methods that the UK services might not have been able to break[citation needed]. The need for such secrecy ebbed away as communications moved to digital transmission and all-digital encryption systems became common in the 1960s.

Information about Colossus began to emerge publicly in the late 1970s, after the secrecy imposed was broken when Colonel Winterbotham published his book The Ultra Secret. 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,[14] 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.[15]

Reconstruction

Colossus rebuild seen from the rear

Construction of a fully functional replica[16] of a Colossus Mark 2 was undertaken by a team led by Tony Sale. In spite of the blueprints and hardware being destroyed, a surprising amount of material survived, mainly in engineers' notebooks, but a considerable amount of it in the U.S. The optical tape reader might have posed the biggest problem, but Dr. Arnold Lynch, its original designer, was able to redesign it to his own original specification. The reconstruction is on display, in the historically correct place for Colossus No. 9, at The National Museum of Computing, in H Block Bletchley Park in Milton Keynes, Buckinghamshire.

In November 2007, to celebrate the project completion and to mark the start of a fundraising initiative for The National Museum of Computing, a Cipher Challenge[17] pitted the rebuilt Colossus against radio amateurs worldwide in being first to receive and decode three messages enciphered using the Lorenz SZ42 and transmitted from radio station DL0HNF in the Heinz Nixdorf MuseumsForum computer museum. The challenge was easily won by radio amateur Joachim Schüth, who had carefully prepared[18] for the event and developed his own signal processing and code-breaking code using Ada.[19] The Colossus team were hampered by their wish to use World War II radio equipment,[20] delaying them by a day because of poor reception conditions. Nevertheless the victor's 1.4 GHz laptop, running his own code, took less than a minute to find the settings for all 12 wheels. The German codebreaker said: "My laptop digested ciphertext at a speed of 1.2 million characters per second—240 times faster than Colossus. If you scale the CPU frequency by that factor, you get an equivalent clock of 5.8 MHz for Colossus. That is a remarkable speed for a computer built in 1944."[21]

The Cipher Challenge verified the successful completion of the rebuild project. "On the strength of today's performance Colossus is as good as it was six decades ago", commented Tony Sale. "We are delighted to have produced a fitting tribute to the people who worked at Bletchley Park and whose brainpower devised these fantastic machines which broke these ciphers and shortened the war by many months."[22]

See also

Footnotes

  1. ^ Bletchley's code-cracking Colossus http://news.bbc.co.uk/1/hi/technology/8492762.stm
  2. ^ Copeland 2006a, p. 75
  3. ^ Copeland 2006, p. 427 harvnb error: multiple targets (2×): CITEREFCopeland2006 (help)
  4. ^ The Colossus Rebuild http://www.tnmoc.org/colossus-rebuild.aspx
  5. ^ Copeland 2006a, p. 75.
  6. ^ Lavington, S. H. (July 1977), The Manchester Mark 1 and Atlas: a Historical Perspective (PDF), University of Central Florida, retrieved 8 February 2009 {{citation}}: Check date values in: |accessdate= (help)
  7. ^ Copeland 2006a, p. 72
  8. ^ A Brief History of Computing. Jack Copeland, June 2000
  9. ^ Goldstine, Herman H. (1980), The Computer from Pascal to von Neumann (New Ed edition (1 Oct 1980) ed.), Princeton University Press, p. 321, ISBN 978-0-691-02367-0
  10. ^ B. Randell, "The Colossus", in A History of Computing in the Twentieth Century (N. Metropolis, J. Howlett and G. C. Rota, Eds.), pp.47–92, Academic Press, New York, 1980., p. 87
  11. ^ "A Brief History of Computing". alanturing.net. Retrieved 26 January 2010.
  12. ^ a b c d Copeland, 2006, p. 173-175
  13. ^ Horwood, 1973
  14. ^ Jack Good (1945). "General Report on Tunny". {{cite web}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  15. ^ "http://www.alanturing.net/turing_archive/archive/t/t17/TR17-003.html". {{cite web}}: External link in |title= (help)
  16. ^ "The Colossus Rebuild Project – by Tony Sale". Retrieved 30 October 2011
  17. ^ "Cipher Challenge". Archived from the original on 1 August 2008. Retrieved 1 February 2012.
  18. ^ "SZ42 Codebreaking Software".
  19. ^ "Cracking the Lorenz Code (interview with Schüth)".
  20. ^ Ward, Mark (16 November 2007). "BBC News Article". Retrieved 2 January 2010.
  21. ^ "German Codebreaker receives Bletchley Park Honours".
  22. ^ "Latest Cipher Challenge News 16.11.2007".

References

Further reading

  • Cragon, Harvey G. From Fish to Colossus: How the German Lorenz Cipher was Broken at Bletchley Park (Cragon Books, Dallas, 2003; ISBN 0-9743045-0-6) – A detailed description of the cryptanalysis of Tunny, and some details of Colossus (contains some minor errors)
  • Copeland, B. Jack, ed. (2006), Colossus: The Secrets of Bletchley Park's Codebreaking Computers, Oxford: Oxford University Press, ISBN 978-0-19-284055-4
  • Enever, Ted Britain's Best Kept Secret: Ultra's Base at Bletchley Park (Sutton Publishing, Gloucestershire, 1999; ISBN 0-7509-2355-5) – A guided tour of the history and geography of the Park, written by one of the founder members of the Bletchley Park Trust
  • Gannon, Paul (2007), Colossus: Bletchley Park's Greatest Secret, Atlantic Books, ISBN 978-1-84354-331-2
  • Rojas, R., Hashagen U., (eds.): The First Computers: History and Architectures. MIT Press 2000. ISBN 0-262-18197-5. – Comparison of the first computers, with a chapter about Colossus and its reconstruction by Tony Sale.
  • Sale, Tony, The Colossus Computer 1943–1996: How It Helped to Break the German Lorenz Cipher in WWII (M.&M. Baldwin, Kidderminster, 2004; ISBN 0-947712-36-4) – A slender (20 page) booklet, containing the same material as Tony Sale's website (see below)
  • Smith, Michael (2007) [1998], Station X: The Codebreakers of Bletchley Park, Pan Grand Strategy Series (Pan Books ed.), London: Pan McMillan Ltd, ISBN 978-0-330-41929-1

Other meanings

There was a fictional computer named Colossus in the movie Colossus: The Forbin Project. Also see List of fictional computers. Neal Stephenson's novel Cryptonomicon (1999) also contains a fictional treatment of the historical role played by Turing and Bletchley Park.