Maria Kirch was a very early female human computer. Working in the late 1600s into the early 1700s, with her husband, she created astronomical tables that while mainly used for astrological purposes were also useful for navigation. They computed the future times of sunrises, the phases of the moon, the positions of planets, eclipses and the like for calendars. This was part of his job as astronomer for the Royal Academy of Sciences in Berlin. Along the way she became the first woman to discover a comet. When her husband died, she asked to take over his job – it was common for widows to take over a family business in this way. Having done the work with her husband she was of course eminently qualified. However, she was refused, despite having support from the great mathematician and scientist, Gottfried Leibnitz. A less qualified man was given the job instead. She did continue her work, however, doing astronomical observations and calculations almost to her death in 1720
20th century human computers (working for NASA, for example) moved on to become programmers once they were invented so capable of doing the actual calculations, However, no computers existed in the 1600s and 1700s. If they had perhaps Maria would have naturally become a programmer, too, coding the computations needed to take over her work. She certainly had the skills. Charles Babbage who also worked as a human computer a century or so later computing similar tables for shipping navigation, went on to try to create a mechanical computer to do the job for him. Mathematician Ada Lovelace, of course, then became interested in writing algorithms for it and is sometimes called “the first programmer”. In fact, Kirch’s supporter, Leibnitz, did actually design a computer. It worked using a Binary system of marble runs. However, it was really only a thought experiment and he did not, as far as we know, attempt to build it. He did create mechanical calculators including the first massed produced one. They would have helped take some of the tedium of this kind of calculation, but they were not programmable. If only he had built his computer maybe Maria Kirch would have become the first programmer…
Chatbots are now everywhere. You seemingly can’t touch a computer without one offering its opinion, or trying to help. This explosion is a result of the advent of what are called Large Language Models: sophisticated programs that in part copy the way human brains work. Chatbots have been around far longer than the current boom, though. The earliest successful one, called ELIZA, was, built in the 1960s by Joseph Weizenbaum, who with his Jewish family had fled Nazi Germany in the 1930s. Despite its simplicity ELIZA was very effective at fooling people into treating it as if it were a human.
Weizenbaum was interested in human-computer interaction, and whether it could be done in a more human-like way than just by typing rigid commands as was done at the time. In doing so he set the ball rolling for a whole new metaphor for interacting with computers, distinct from typing commands or pointing and clicking on a desktop. It raised the possibility that one day we could control computers by having conversations with them, a possibility that is now a reality.
His program, ELIZA, was named after the character in the play Pygmalion and musical My Fair Lady. That Eliza was a working class women who was taught to speak with a posh accent gradually improving her speech, and part of the idea of ELIZA was that it could gradually improve based on its interactions. At core though it was doing something very simple. It just looked for known words in the things the human typed and then output a sentence triggered by that keyword, such as a transformation of the original sentence. For example, if the person typed “I’m really unhappy”, it might respond “Why are you unhappy?”.
In this way it was just doing a more sophisticated version of the earliest “creative” writing program – Christopher Strachey’s Love Letter writing program. Strachey’s program wrote love letters by randomly picking keywords and putting them into a set of randomly chosen templates to construct a series of sentences.
The keywords that ELIZA looked for were built into its script written by the programmer and each allocated a score. It found all the keywords in the person’s sentence but used the one allocated the highest score. Words like “I” had a high score so were likely to be picked if present. A sentence starting “I am …” can be transformed into a response “Why are you …?” as in the example above. to make this seem realistic, the program needed to have a variety of different templates to provide enough variety of responses, though. To create the response, ELIZA broke down the sentence typed into component parts, picked out the useful parts of it and then built up a new response. In the above example, it would have pulled out the adjective, “happy” to use in its output with the template part “Why are you …”, for example.
If no keyword was found, so ELIZA had no rule to apply, it could fall back on a memory mechanism where it stored details of the past statements typed by the person. This allowed it to go back to an earlier thing the person had said and use that instead. It just moved on to the next highest scoring keyword from the previous sentence and built a response based on that.
ELIZA came with different “characters” that could be loaded in to it with different keywords and templates of how to respond. The reason ELIZA gained so much fame was due to its DOCTOR script. It was written to behave like a psychotherapist. In particular, it was based on the ideas of psychologist Carl Rogers who developed “person-centred therapy”, where a therapist, for example, echos back things that the person says, always asking open-ended questions (never yes/no ones) to get the patient talking. (Good job interviewers do a similar thing!) The advantage of it “pretending” to be a psychotherapist like this is that it did not need to be based on a knowledge bank of facts to seem realistic. Compare that with say a chatbot that aims to have conversations about Liverpool Football Club. To be engaging it would need to know a lot about the club (or if not appear evasive). If the person asked it “Who do you think the greatest Liverpool manager was?” then it would need to know the names of some former Liverpool managers! But then you might want to talk about strikers or specific games or … A chatbot aiming to have conversations about any topic the person comes up with convincingly needs facts about everything! That is what modern chatbots do have: provided by them sucking up and organising information from the web, for example. As a psychotherapist, DOCTOR never had to come up with answers, and echoing back the things the person said, or asking open-ended questions, was entirely natural in this context and even made ti seem as though it cared about what the people were saying.
Because Eliza did come across as being empathic in this way, the early people it was trialled on were very happy to talk to it in an uninhibited way. Weizenbaum’s secretary even asked him to leave while she chatted with it, as she was telling it things she would not have told him. That was despite the fact, or perhaps partly because, she knew she was talking to a machine. Others were convinced they were talking to a person just via a computer terminal. As a result it was suggested at the time that it might actually be used as a psychotherapist to help people with mental illness!
Weizenbaum was clear though that ELIZA was not an intelligent program, and it certainly didn’t care about anyone, even if it appeared to be. It certainly would not have passed the Turing Test, set previously by Alan Turing that if a computer was truly intelligent people talking to it would be indistinguishable from a person in its answers. Switch to any knowledge-based topic and the ELIZA DOCTOR script would flounder!
ELIZA was also the first in a less positive trend, to make chatbots female because this is seen as something that makes men more comfortable. Weizenbaum chose a female character specifically because he thought it would be more believable as a supportive, emotional female. The Greek myth Pygmalion from which the play’s name derives is about a male sculptor falling in love with a female sculpture he had carved, that then comes to life. Again this fits a trend of automaton and robots in films and reality being modelled after women simply to provide for the whims of men. Weizenbaum agreed he had made a mistake, saying that his decision to name ELIZA after a woman was wrong because it reinforces a stereotype of women. The fact that so many chatbots have then copied this mistake is unfortunate.
Because of his experiences with ELIZA he went on to become a critic of Artificial Intelligence (AI). Well before any program really could have been called intelligent (the time to do it!), he started to think about the ethics of AI use, as well as of the use of computers more generally (intelligent or not). He was particularly concerned about them taking over human tasks around decision making. He particularly worried that human values would be lost if decision making was turned into computation, beliefs perhaps partly shaped by his experiences escaping Germany where the act of genocide was turned into a brutally efficient bureaucratic machine, with human values completely lost. Ultimately, he argued that computers would be bad for society. They were created out of war and would be used by the military as a a tool for war. In this, given, for example, the way many AI programs have been shown to have built in biases, never mind the weaponisation of social media, spreading disinformation and intolerance in recent times, he was perhaps prescient.
by Paul Curzon, Queen Mary University of London
Fun to do
If you can program why not have a go at writing an ELIZA-like program yourself….or perhaps a program that runs a job interview for a particular job based on the person specification for it.
Back in its early days, after the war, women played a pivotal role in the computing industry, originally as skilled computer operators. Soon they started to be taken on as skilled computer programmers too. The myth that programming is boys thing came much later. Originally it was very much a job for women too. Dina St Johnston was one such early programmer. And she personally went on to kick-start the whole independent UK software industry!
On leaving school, interested in maths, science and machines, she went to work for a metallurgy research company, and in parallel gained a University of London external Maths degree, but eventually moved on to get a job ultimately as a programmer at an early computer manufacturer, Elliot Brothers in 1053. Early software she was involved in writing was very varied, but whatever the application she excelled. For example, she was responsible for writing an in-house payroll program, as well as code for a dedicated direction finding computer of the Royal Navy. The latter was a system that used the direction of radio signals picked up by receivers at different listening stations to work out where the source was (whether friend or foe). She also wrote software for the first computer to be used by a local government, Norwich City Council. She had the kind of attention to detail and logical thinking skills that meant she quickly became an incredibly good programmer, able to write correct code. Bugs for others to find in her code were rare. “Whereas the rest of us tested programs to find the faults, she tested them to demonstrate that they worked.”
Towards the end of the 1960s though she realised there was a big opportunity, a gap in the market, for someone with programming skills and a strong entrepreneurial spirit like her. All UK application software at the time was developed either by computer manufacturers like Elliot Brothers, by service companies selling time on their computers, by consultancy firms or in-house by people working directly for the companies who bought the computers. There was, she saw, potential to create a whole new industry: an applications software industry. What there was a need for, were independent software companies whose purpose was to write bespoke application programs that were just what a client company needed, for any who needed it, big or small. She therefore left Elliot Brothers and founded her own company (named after her maiden name), Vaughan Programming Services, to do just that.
Despite starting out working from her dining room table, it was a big success, working in a lot of different application areas over the subsequent decades, with clients including massive organisations such as the BBC, BAA, Unilever, GEC, the nuclear industry (she wrote software for what is now called Sellafield, then the first ever industrial nuclear power plant), the RAF and British Rail. Part of the reason she made it work was she was a programmer who was “happy to go round a steel works in a hard hat”, She made sure she understood her clients needs in a direct hands-on way.
Eventually, Dina’s company started to specialise in transport information systems and that is where it really made its name…with early work for example on the passenger display boards at London Bridge, but eventually to hundreds of stations, driven from a master timetable system. So next time you are in a train station or airport, looking at the departure board, think of Dina, as it was her company that wrote the code driving the forerunner of the display you are looking at.
More than that though, the whole idea of a separate software industry to create whatever programs were needed for whoever needed them, started with her. If you are a girl wondering about whether a software industry job is for you, as she showed, there is absolutely no reason why it should not be. Dina excelled, so can you.
Computer Scientists talk about “Syntactic Sugar” when talking about programming languages. But in what way might a program be made sweet? It is all about how necessary a feature of a language is, and the idea and phrase was invented by Computer Scientist and gay activist, Peter Landin. He realised it made it easier to define the meaning of languages in logic and made the definitions more elegant.
Peter Landin was involved in the development of several early and influential programming languages but also a pioneer of the use of logic to define exactly what each construct of a programming language did: the language’s “semantics”. He realised there was a fundamental difference between different parts of a language. Some were absolutely fundamental to the language. If you removed them then programs would have to be written in a different way, if at all, as a result. Remove the assignment construct that allows a program to change the value of variables, for example, and there are things your programs can no longer do, or at least it would need to do it in very different way. Remove the feature that allows someone to write i++ instead of i = i + 1, on the other hand, and nothing much changes about how you write code. They were just abbreviations for common uses of the more core things.
As another example, suppose you didn’t like using curly brackets to start and end blocks of code (perhaps having learnt to program using Pascal) then if programming in C or Java you could add a layer of syntactic sugar by replacing { by BEGIN and } by END. Your programs might look different and make you feel happier, but were not really any different.
Peter called these kinds of abbreviations “syntactic sugar”. They were superficial, just there to make the syntax (the way things were written at the level of spelling and punctuation) a little bit nicer for the programmers: sometimes more readable, sometimes just needing less typing.
It is now recognised, of course, that writing readable code is a critically important part of programming. Code has to be maintainable: easily understood and modified by others long after it was written. Well thought out syntactic sugar can help with this as well as making it easier to avoid mistakes when writing code in the first place. For example, syntactic sugar is used in many languages to give special syntax to core datatypes, where they are called sugared types. Common example include using quotes to represent a String value like “abc” or square brackets like [1,2,3] to stand for an array value, rather than writing out the underpinning function calls of the core language to construct a value.
People now sometimes deride the idea of syntactic sugar, but it had a clear use for Peter beyond just readability. He was interested in logically defining languages: saying in logic exactly what each construct meant. The syntactic sugar distinction made his life doing that easier. The fundamental things were the things that he had to define directly in logic. He had to work out exactly what the semantics of each was and how to say what they meant mathematically. Syntactic sugar could be defined just by adding rewrite rules that convert the syntactic sugar to the core syntax. i++, for example does not need to be defined logically, just converted to i = i + 1 to give its meaning. If assignment was defined in terms of logic then the abbreviation is ultimately too as a result.
Peter discussed this in relation to treating a kind of logic called the lambda calculus as the basis for a language. Lambda Calculus is a logic based on functions. Everything consists of lambda expressions, though he was looking at a version which included arithmetic too. For example, in this logic, the expression:
(λn.2+n)
defines a function that takes a value n and returns the value resulting from adding 2 to that value. Then the expression:
(λn.2+n) [5]
applies that function to the value 5, meaning 5 is substituted for the n that comes after the lambda, so it simplifies to 2+5 or further to 7. Lambda expressions, therefore, have a direct equivalence to function call in a programming language. The lambda calculus has a very simple and precise mathematical meaning too, in that any expression is just simplified by substituting values for variables as we did to get the answer 7 above. It could be used as a programming language in itself. Logicians (and theoretical computer scientists) are perfectly happy reading lambda calculus statements with λ’s, but Peter realised that as a programming language it would be unreadable to non-logicians. However with a simple change, adding syntactic sugaring, it could be made much more readable. This just involved replacing the Greek letter λ by the word “where” and altering the order and throwing in an = sign..
Now instead of writing
(λn.2+n) [5]
in his programming language you would write
2 + n where n = 5
Similarly,
(λn.3n+2) [a+1]
became
3n+2 where n = a + 1
This made the language much more readable but did not complicate the task of defining the semantics. It is still just directly equivalent to the lambda calculus so the lambda calculus can still be used to define its semantics in a simple way (just apply those transformations backwards). Overall this work showed that the group of languages called functional programming languages could be defined in terms of lambda calculus in a very elegant way.
Syntactic sugar is at one level a fairly trivial idea. However, in introducing it in the context of defining the semantics of languages it is very powerful. Take the idea to its extreme and you define a very small and elegant core to your language in logic. Then everything else is treated as syntactic sugar with minimal work to define it as rewrite rules. That makes a big difference in the ease of defining a programming language as well as encouraging simplicity in the design. It was just one of the ways that Peter Landin added elegance to Computer Science.
Designing software that is inclusive for global markets is easy. All you have to do is get an AI to translate everything in the interface into multiple languages…or perhaps to do it properly it is harder than that! Not everyone thinks like you do.
Suppose you are the successful designer of a satellite navigation system. You’ve made lots of money selling it in the UK and the US and are now ready to take on the world. You want to be inclusive. It should be natural and easy to use by all. You therefore aim to produce versions for every known language. It should be easy shouldn’t it. The basic system is fine. It can use satellite signals to work out where it is. You already have maps of everywhere based on Google Earth that you have been selling to the English Speakers. It can work out routes and gives perfectly good directions just as the user needs them – like “Turn Left 200 meters ahead”. It is already based on Unicode, the International standard for storing characters so can cope with characters from all languages. All you need to do now is get a team of translators to come up with the equivalent of the small number of phrases used by the device (which, of course will also involve switching units from eg meters to yards and the like, but that is easy for a computer) and add a language selection mechanism. You have thought of everything. Simple…
Not so simple, actually. You may need more than just translators, and you may need more than just to change the words. As linguists have discovered, for example, a third of known languages have no concept of left and right. Since language helps determine the way we think, that also suggests the people who speak those languages don’t use the concepts. “Turn right” is meaningless. It has no equivalent.
So how do such people give directions or otherwise describe positions. Well it turns out many use a method that for a long time some linguists suggested would never occur. Experiments have also shown that not only do they talk that way, but they also may think that way.
Take Tzeltal. It is spoken very widely in Mexico. A dialect of it that is spoken by about 15 000 people in the Indian community of Tenejapa has been studied closely by Stephen Levinson and Penelope Brown. It is a large area roughly covering one slope of a mountainous region. The language has no general notion of left or right. Unlike in European languages where we refer to directions based on the way we are facing (known as a relative frame of reference), in Tzeltal directions use what is known as an absolute frame of reference. It is as though they have a compass in their heads and do the equivalent of referring to North, South, East and West all the time. Rather than “The cup is to the left of the teapot”, they might say the equivalent of “The cup is North of the teapot”. How did this system arise? Well they don’t actually refer to North and South directly, but more like uphill and downhill, even when away from the mountain side: they subconsciously keep track of where uphill would be. So they are saying something more like “The cup is on the uphill side of the teapot”.
In Tenejapa they think diferently about direction too
Experiments have suggested they think differently too – Show Europeans a series of objects ordered so “pointing” to their left on a table, turn them through 180 degrees and ask them to order the same objects on the table in front of them, and they will generally put them “pointing” to their left. In experiments with native Tzeltal speakers and they tended to put them “pointing” to their right (Still pointing uphill or whatever). Similar things apply when they make gestures. Its not just the words they use that are different, it is the way they internally represent the world that differs.
So back to the drawing board with the navigation system. If you really want it to be completely natural for all, then for each language you need more than just translators. You need linguists who understand the way people think and speak about directions in each language. Then you will have to do more than just change the words the system outputs, but recode the navigation system to work the way they think. A natural system for the Tzeltal would need to keep track of the Tenejapan uphill and give directions relative to that.
It isn’t just directions of course, there are many ways that our language and cultures lead to us thinking and acting differently. Design metaphors are also used a lot in interactive systems but they only work if they fit their users’ culture. For example, things are often ordered left to right as that as the way we read…except who is we there? Not everyone reads left to right!
Writing software for International markets isn’t as easy as it seems. You have to have good knowledge not just of local languages but also differences in culture and deep differences in the way different people see the world… If you want to be an International success then you will be better at it if you work in a way that shows you understand and respect those from elsewhere.
by Paul Curzon, Queen Mary University of London, adapted from the archive
Thousands of programming languages have been invented in the many decades since the first. But what makes a good language? A key idea behind language design is that they should make it easy to write complex algorithms in simple and elegant ways. It turns out that logic is key to that. Through his work on programming language design, Peter Landin as much as anyone, promoted both elegance and the linked importance of logic in programming.
Peter was an eminent Computer Scientist who made major contributions to the theory of programming languages and especially their link to logic. However, he also made his mark in his stand against war, and support of the nascent LGBTQ+ community in the 1970s as a member of the Gay Liberation Front. He helped reinvigorate the annual Gay Pride marches as a result of turning his house into a gay commune where plans were made. It’s as a result of his activism as much as his computer science that an archive of his papers has been created in the Oxford Bodleian Library.
However, his impact on computer science was massive. He was part of a group of computing pioneers aiming to make programming computers easier, and in particular to move away from each manufacturer having a special programming language to program their machines. That approach meant that programs had to be rewritten to work on each different machine, which was a ridiculous waste of effort! Peter’s original contribution to programming languages was as part of the team who developed the programming language, ALGOL which most modern programming languages owe a debt to.
ALGOL included the idea of recursion, allowing a programmer to write procedures and functions that call themselves. This is a very mathematically elegant way to code repetition in an algorithm (the code of the function is executed each time it calls itself). You can get an idea of what recursion is about by standing between two mirrors. You see repeated versions of your reflection, each one smaller than the last. Recursion does that with problem solving. To solve a problem convert it to a similar but smaller version of the same problem (the first reflection). How do you solve that smaller problem? In the same way, as a smaller version of the same problem (the second reflection)… You keep solving those similar but smaller problems in the same way until eventually the problem is small enough to be trivial and so solved. For example, you can program a factorial method (multiplying all numbers from 1 to n together),in this way. You write that to compute factorial of a number, n, it just calls itself and computes the factorial of (n-1). It just multiply that result by n to get the answer. In addition you just need a trivial case eg that factorial of 1 is just 1.
Peter was an enthusiastic and inspirational teacher and taught ALGOL to others. This included teaching one of the other, then young but soon to be great, pioneers of Programming Theory, Tony Hoare. Learning about recursion led Hoare to work out a way, using recursion, to finally explain the idea that made his name in a simple and elegant way: the fast sorting algorithm he invented called Quicksort. The ideas included in ALGOL had started to prove their worth.
The idea of including recursion in a programming language was part of the foundation for the idea of functional programming languages. They are mathematically pure languages that use recursion as the way to repeat instructions. The mathematical purity makes them much easier to understand and so write correct programs in. Peter ran with the idea of programming in this way. He showed the power that could be derived from the fact that it was closely linked to a kind of logic called the Lambda Calculus, invented by Alonso Church. The Lambda Calculus is a logic built around mathematical functions. One way to think about it is that it is a very simple and pure way to describe in logic what it means to be a mathematical function – as something that takes arguments and does computation on them to give results. This Church showed was a way to define all possible computation just as Turing’s Turing machine is. It provides a simple way to express anything that can be computed.
Peter showed that the Lambda Calculus could be used as a way to define programming languages: to define their “semantics” (and so make the meaning of any program precise).
Having such a precise definition or “semantics” meant that once a program was written it would be sure to behave the same way whatever actual computer it ran on. This was a massive step forward. To make a new programming language useful you had to write compilers for it: translators that convert a program written in the language to a low level one that runs on a specific machine. Programming languages were generally defined by the compiler up till then and it was the compiler that determined what a program did. If you were writing a compiler for a new machine you had to make sure it matched what the original compiler did in all situations … which is very hard to do.
So having a formal semantics, a mathematical description of what a compiler should do, really makes a difference. It means anyone developing a new compiler for a different machines can ensure the compiler matches that semantics. Ultimately, all compilers behave the same way and so one program running on two different manufacturer’s machines are guaranteed to behave the same way in all situations too.
Peter went on to invent the programming language ISWIM to illustrate some of his ideas about the way to design and define a programming language. ISWIM stands for “If you See What I Mean”. A key contribution of ISWIM was that the meaning of the language was precisely defined in logic following his theoretical work. The joke of the name meant it was logic that showed what he meant, very precisely! ISWIM allowed for recursive functions, but also allowed recursion in the definition of data structures. For example, a List is built from a List with a new node on the end. A Tree is built from two trees forming the left and right branches of a new node. They are defined in terms of themselves so are recursive.
Building on his ideas around functional programming, Peter also invented something he called the SECD machine (named after its components: a Stack, Environment, Control and Dump). It effectively implements the Lambda calculus itself as though it is a programming language.ISWIM provided a very simple but useful general-purpose low level language. It opened up a much easier way to write compilers for functional programming languages for different machines. Just one program needed to be written that compiled the language into SECD. Then you had a much simpler job of writing a compiler to convert from the low level SECD language to the low level assembly language of each actual computer. Even better, once written, that low level SECD compiler could be used for different functional programming languages on a single machine. In SECD, Peter also solved a flaw in ALGOL that prevented functions being fully treated as data. Functions as Data is a powerful feature of the best modern programming languages. It was the SECD design that first provided a solution. It provided a mechanism that allowed languages to pass functions as arguments and return them as results just as you could do with any other kind of data without problem.
In the later part of his life Peter focussed much more on his work supporting the LGBTQ+ community having decided that Computer Science was not doing the good for humanity he once hoped. Instead, he thought it was just supporting companies making profit, ahead of the welfare of people. He decided that he could do more good as part of the LGBTQ+ community. Since his death there has been an acceleration in the massing of wealth by technology companies, whereas support for diversity has made a massive difference for good, so in that he was prescient. His contributions have certainly, though, provided a foundation for better software, that has changed the way we live in many ways for the better. Because of his work they are less likely to cause harm because of programming mistakes, for example, so in that at least he has done a great deal of good.
Ayo wants to send her friends Guang and Elham who live together secret messages that only the person she sends the message to can read. She doesnt want Guang to read the messages to Elham and vice versa.
Guang buys them all small lockable notebooks for Christmas. They are normal notebooks except that they have a lock that can be locked shut using a small in-built padlock. Each padlock can be opened with a different single key. Guang suggests that they write messages in their notebook and post it and the key separately to the person who they wish to send the message to. After reading the message that person tears that page out and destroys it, then returns the notebook and key. They try this and it appears to be working, apparently preventing the others from reading the messages that aren’t for them. They exchange lots of secrets…until one day Guang gets a letter from Ayo that includes a note with an extra message added on the end by Elham in the locked notebook. It says “I can read your messages. I know all your secrets – Elham”. She has been reading Ayo’s messages to Guang all along and now knows all their secrets. She now wants them to know how clever she has been.
How did she do it? (And what does it have to do with the beheading of Mary Queen of Scots?)
Breaking the system
Elham has, of course, been getting to the post first, steaming open the envelopes, getting the key and notebook, reading the message (and for the last one adding her own note). She then seals them back in the envelopes and leaves them for Guang.
A similar thing happened to betray Mary Queen of Scots to her cousin Queen Elizabeth I. It led to Mary being beheaded.
Is there a better way?
Ayo suggests a solution that still uses the notebooks and keys, but in which no keys are posted anywhere. To prove her method works, she sends a secret message to Guang, that Elham fails to read. How does she do it? See if you can work it out before reading on…and what is the link to computer science?
The girls face a similar problem to that faced by Mary Queen of Scots and countless spies and businesses with secrets to exchange before and since…how to stop people intercepting and reading your messages. Mary was beheaded because she wasn’t good enough at it. The girls in the puzzle discovered, just like Mary, that weak encryption is worse than no encryption as it gives false confidence that messages are secret.
There are two ways to make messages secret – hide them so no one realises there is a message to read or disguise the message so only people in the know, are aware it exists (or both). Hiding the message is called Steganography. Disguising a message so it cannot be read even if known about is called encryption. Mary Queen of Scots did both and ultimately lost her life because her encryption was easy to crack, when she believed the encryption would protect her, it had given her the confidence to write things she otherwise would not have written.
House arrest
Mary had been locked up – under house arrest – for 18 years by Queen Elizabeth I, despite being captured only because she came to England asking her cousin Elizabeth to give her refuge after losing her Scottish crown. Elizabeth was worried that Mary and her allies would try to overthrow her and claim the English crown if given the chance. Better to lock her up before she even thought of treason? Towards the end of her imprisonment, in 1586 some of Mary’s supporters were in fact plotting to free her and assassinate Elizabeth. Unfortunately, they had no way of contacting Mary as letters were allowed neither in nor out by her jailors. Then, a stroke of good fortune arose. A young priest called Gilbert Gifford turned up claiming he had worked out a way to smuggle messages to and from Mary. He wrapped the messages in a leather package and hid them in the hollow bungs of barrels of beer. The beer was delivered by the brewer to Chartley Hall where Mary was held and the packages retrieved by one of Mary’s servants. This, a form of steganography, was really successful allowing Mary to exchange a long series of letters with her supporters. Eventually the plotters decided they needed to get Mary’s agreement to the full plot. The leader of the coup, Anthony Babington, wrote a letter to Mary outlining all the details. To be absolutely safe he also encrypted the message using a cipher that Mary could read (decipher). He soon received a reply in Mary’s hand also encrypted that agreed to the plot but also asked for the names of all the others involved. Babington responded with all the names. Unfortunately, unknown to Babington and Mary the spies of Elizabeth were reading everything they wrote – and the request for names was not even from Mary.
Spies and a Beheading
Unfortunately for Mary and Babington all their messages were being read by Sir Francis Walsingham, the ruthless Principal Secretary to Elizabeth and one of the most successful Spymasters ever. Gifford was his double agent – the method of exchanging messages had been Walsingham’s idea all along. Each time he had a message to deliver, Gifford took it to Walsingham first, whose team of spies carefully opened the seal, copied the contents, redid the seal and sent it on its way. The encrypted messages were a little more of a problem, but Walsingham’s codebreaker could break the cipher. The approach, called frequency analysis, that works for simple ciphers, involves using the frequency of letters in a message to guess which is which. For example, the most common letter in English is E, so the most common letter in an encrypted message is likely to be E. It is actually the way people nowadays solve crossword like code-puzzles know as Cross References that can be found in puzzle books and puzzle columns of newspapers.
When they read Babington’s letter they had the evidence to hang him, but let the letter continue on its way as when Mary replied, they finally had the excuse to try her too. Up to that point (for the 18 years of her house arrest) Elizabeth had not had strong enough evidence to convict Mary – just worries. Walsingham wanted more though, so he forged the note asking for the names of other plotters and added it to the end of one of Mary’s letters, encrypted in the same code. Babington fell for it, and all the plotters were arrested. Mary was tried and convicted. She was beheaded on February 8th 1587.
Private keys…public keys
What is Ayo’s method to get round their problems of messages being intercepted and read? Their main weakness was that they had to send the key as well as the locked message – if the key was intercepted then the lock was worthless. The alternative way that involves not sending keys anywhere is the following…
Image by Paul Curzon
Suppose Ayo wants to send a message to Guang. She first asks Guang to post her notebook (without the key but left open) to her. Ayo writes her message in Guang’s book then snaps it locked shut and posts it back. Guang has kept the key safe all along. She uses it to open the notebook secure in the knowledge that the key has never left her possession. This is essentially the same as a method known by computer scientist’s as public key encryption – the method used on the internet for secure message exchange, including banking, that allows the Internet to be secure. In this scheme, keys come in 2 halves a “private key” and a “public key”. Each person has a secret “private key” of their own that they use to read all messages sent to them. They also have a “public key” that is the equivalent to Guang’s open padlock.
If someone wants to send me a message, they first get my public key – which anyone who asks for can have as it is not used to decrypt messages, just for other people to to encrypt them (close the padlock) before sending them to me. It is of no use to decrypt any message (reopen the padlock). Only the person with the private key (the key to the padlock) can get at the message. So messages can be exchanged without the important decryption key going anywhere. It remains safe from interception.
Saving Mary
Would this have helped Mary? No. Her problem was not in exchanging keys but that she used a method of encryption that was easy to crack – in effect the lock itself was not very strong and could easily be picked. Walsingham’s code breakers were better at decryption than Babington was at encryption.
by Paul Curzon, Queen Mary University of London, updated from the archive
cs4fn 