[an error occurred while processing this directive]
BBC News
watch One-Minute World News
Last Updated: Monday, 21 June, 2004, 09:47 GMT 10:47 UK
Breaking codes: An impossible task?

By Paul Reynolds
BBC News Online world affairs correspondent

Recent reports that the United States had broken codes used by the Iranian intelligence service have intrigued experts on cryptology because a modern cipher should be unbreakable.

Four leading British experts told BBC News Online that the story, if true, points to an operating failure by the Iranians or a backdoor way in by the National Security Agency (NSA) - the American electronic intelligence organisation.

The biggest prime number yet found
The longest prime number discovered so far would stretch 20km if written down

The reports, from Washington, suggested that the Iranians had been tipped off by Ahmed Chalabi, an Iraqi political leader with links to Iran.

He is said to have learned about the code-breaking from an American official who was drunk.

Simon Singh, author of "The Code Book", a history of codes, said: "Modern codes are effectively unbreakable, very cheap and widely available. I could send an email today and all the world's secret services using all the computers in the world would not be able to break it. The code maker definitely has a huge advantage over the codebreaker."

The reason for this is that an encoded text is so complex that it can resist all efforts to break it.

The key to codes

It is probable, though not certain of course, that Iran was using what's called public-private key or asymmetric cryptography. In this system, the message is encoded by someone using a freely distributed public key. This can be decoded only by someone using a different private key.
Modern codes are effectively unbreakable, very cheap and widely available
Simon Singh

The public-private key method has largely taken over from the purely private or symmetric system in which the sender and receiver use the same key to encrypt and decrypt a message.

Some ciphers use a mixture. A private key encrypts and decrypts the message because this way is less complicated and therefore quicker but the key itself is sent by the public-private method.

Professor Alistair Fitt, head of the School of Mathematics at Southampton University, said: "The private-private key is seen as obsolete. The public-private key is better. It does away with the problem of transporting the key between the two parties."

I asked Professor Fitt if he would feel confident of using it if he was an intelligence chief. He replied "Yes."

Too hard to crack

Take a public key based on a huge number which is the result of two prime numbers multiplied together (a prime number being one which can be divided only by itself or by one). You use this number to encode your message but you do not need to know the two original prime numbers. Only the person decoding the message needs to know, because the text was encoded using an equation and both numbers are needed to reverse that equation.

You design the numbers so that if you have more computers than there are in the world and you run them for ever, they are not enough
Professor Alistair Fitt
The system is safe because it is a curious feature of mathematics that when two prime numbers are multiplied, it is very difficult to factor, that is to work out, the two original numbers. Mathematicians have been trying to find a way to do this quickly for hundreds of years and have failed so far.

Since even computers take time to wade their way through all prime numbers to find the correct ones, it has been estimated that, if the number is big enough, the world could end before they succeed. A guess would have a better chance.

A large key

The text to be enciphered is basically converted into numbers to which a numerical key is applied in a mathematical formula. It is important that the key has enough numbers to keep it safe but not enough to slow the whole process down too much.

Professor Fitt commented: "If you are making a code, you design the numbers so that if you have more computers than there are in the world and you run them for ever, they are not enough."

Ahmed Chalabi
Did Ahmed Chalabi tell Iran?

Seeking another answer

The code breakers, or cryptanalysts, therefore have to find some other solution.

Ross Anderson of the Computer Laboratory at Cambridge University pointed to some of them: "As the former chief scientist of the NSA once remarked at one of our security workshops, almost all breaks of cipher systems are due to implementation errors, operational failures, burglary, blackmail and bribery.

There is a difference between breaking a code and breaking a system
Professor Fred Piper
"As for cryptanalysis, it happens, but very much less often than most people think."

Professor Fred Piper of the Royal Holloway College made the same point strongly: "There is a difference between breaking a code and breaking a system.

"In general it is true that a system using a practically unbreakable cipher might be broken though a management fault."

The three B's

Such faults might include lazy operating procedures or even leaving your key around on a CD which someone else could read.

This is reminiscent of one of the ways the German Enigma codes were broken during World War II. One German operator always used the name of his girlfriend Cillie to send a test message. Thereafter the British code-breakers called all such vulnerable messages "cillies."

The three "Bs" - burglary, blackmail and bribery - might have to be employed if there is no other way of getting at the key. We are back to the world of spies.

Perhaps the need to find keys was what lay behind the former British MI5 agent Peter Wright's revelation in his book "Spycatcher" that he "bugged and burgled" his way across London.

Hidden software

Simon Singh says that sometimes there is a backdoor way in through deliberately corrupted software: "There is always the chance of human error. Encryption requires a key, and if I get hold of your key then I can read your messages. Or if I plant some software in I get to see the message before you encrypt it."

Software allowing decryption is known to have been implanted in some ciphers in the past. In his book "Security Engineering", Ross Anderson tells the story of how this happened in Sweden: "The Swedish government got upset when they learned that the 'export version' of Lotus Notes which they used widely in public service had its cryptography deliberately weakened to allow NSA access."
The Gramn Enigma coding machine
The Enigma: Bad habits cost codes

In another case, intriguingly involving Iran, Ross Anderson reported: "A salesman for the Swiss firm Crypto AG was arrested in Iran in 1992 and the authorities accused him of selling them cipher machines which had been tampered with so that the NSA could get at the plaintext. After he had spent some time in prison, Crypto AG paid about a $1m to bail him but then fired him once he got back to Switzerland."

Whether something similar happened in this case involving Iran is simply not known.

The internet - is it secure?

All this has important implications, incidentally, for internet security. When you enter a secure area on the internet, to buy something for example, you are using an encryption system.

Professor Alistair Fitt says that the internet codes are safe: "I do not understand why some people do not trust the internet yet they give their credit card to some waiter who disappears with it into a back room."

You can also use 128-bit encryption for your e-mails. This used not to be the case. It was only in 2000 that the United States lifted most export controls on strong encryption programmes.

Using such encryption, your e-mails should be safe. Unless what apparently happened to the Iranians happens to you.

Largest Prime Number discovered
07 Jun 04 |  Science/Nature
Chalabi denies leaking US secrets
03 Jun 04 |  Middle East
Iran scoffs at Chalabi spy claims
02 Jun 04 |  Middle East
US spy coup 'leaked' by Chalabi
02 Jun 04 |  Middle East
New puzzle for war code breakers
11 May 04 |  Staffordshire

The BBC is not responsible for the content of external internet sites


News Front Page | Africa | Americas | Asia-Pacific | Europe | Middle East | South Asia
UK | Business | Entertainment | Science/Nature | Technology | Health
Have Your Say | In Pictures | Week at a Glance | Country Profiles | In Depth | Programmes
Americas Africa Europe Middle East South Asia Asia Pacific