During the Pacific campaign, American commanders began to realise that cipher machines ... had a fundamental drawback. Although electromechanical encryption offered relatively high levels of security, it was painfully slow. Messages had to be typed into the machine letter by letter, the output had to be noted down letter by letter, and then the completed ciphertext had to be transmitted by the radio operator. The radio operator who received the enciphered message then had to pass it on to a cipher expert, who would carefully select the correct key, and type the ciphertext into a cipher machine, to decipher it letter by letter. The time and space required for this delicate operation is available at headquarters or on board a ship, but machine encryption was not ideally suited to more hostile and intense environments, such as the islands of the Pacific....
One of the first to react to this problem was Philip Johnston, an engineer based in Los Angeles, who was too old to fight but still wanted to contribute to the war effort. At the beginning of 1942 he began to formulate an encryption system inspired by his childhood experiences. The son of a Protestant missionary, Johnston had grown up on the Navajo reservations of Arizona, and as a result he had become fully immersed in Navajo culture. He was one of the few people outside the tribe who could speak their language fluently .... Fully aware of how impenetrable the language was for those outside the tribe, Johnston was struck by the notion that Navajo, or any other Native American language, could act as a virtually unbreakable code. If each battalion in the Pacific employed a pair of Native Americans as radio operators, secure communication could be guaranteed.
He took his idea to Lieutenant Colonel James E. Jones, the area signal officer at Camp Elliott, just outside San Diego ... [and] was able to persuade him that the idea was worthy of serious consideration. A fortnight later he returned with two Navajos, ready to conduct a test demonstration in front of senior marine officers ... The game of Navajo whispers proved to be flawless, and the marine officers authorised a pilot project and ordered recruitment to begin immediately.
Before recruiting anybody, however, Lieutenant Colonel Jones and Philip Johnston had to decide whether to conduct the pilot study with the Navajo, or select another tribe .... The most important selection criterion was simply a question of numbers; the marines needed to find a tribe capable of supplying a large number of men who were fluent in English and literate. The lack of government investment meant that the literacy rate was very low on most of the reservations, and attention was therefore focused on the four largest tribes: the Navajo, the Sioux, the Chippewa and the Pima-Papago.
....There was little to choose between the four tribes, and ultimately the decision rested on another critical factor. According to the official report on Johnston's idea:
The Navajo is the only tribe in the United States that has not been infested with German students during the past twenty years. These Germans, studying the various tribal dialects under the guise of art students, anthropologists, etc., have undoubtedly attained a good working knowledge of all tribal dialects except Navajo. For this reason the Navajo is the only tribe available offering complete security for the type of work under consideration. It should also be noted that the Navajo tribal dialect is completely unintelligible to all other tribes and all other people, with the possible exception of as many as 28 Americans who have made a study of the dialect. This dialect is equivalent to a secret code to the enemy, and admirably suited for rapid, secure communication.
At the time of America's entry into the Second World War, the Navajo were living in harsh conditions and being treated as inferior people. Yet their tribal council supported the war effort and declared their loyalty .... The Navajos were so eager to fight that some of them lied about their age, or gorged themselves on bunches of bananas and swallowed great quantities of water in order to reach the minimum weight requirement of 55 kg. Similarly, there was no difficulty in finding suitable candidates to serve as Navajo code talkers .... Within four months of the bombing of Pearl Harbor, 29 Navajos, some as young as fifteen, began an eight-week communications course with the Marine Corps.
....[T]he Marine Corps planned to construct a lexicon of Navajo terms to replace otherwise untranslatable English words, thus removing any ambiguities. The trainees helped to compile the lexicon, tending to choose words describing the natural world to indicate specific military terms. Thus the names of birds were used for planes, and fish for ships. Commanding officers became "war chiefs", platoons were "mud-clans", fortifications turned into "cave dwellings" and mortars were known as "guns that squat".
Even though the complete lexicon contained 274 words, there was still the problem of translating less predictable words and the names of people and places. The solution was to devise an encoded phonetic alphabet for spelling out difficult words .... Within eight weeks, the trainee code talkers had learnt the entire lexicon and alphabet, thus obviating the need for codebooks which might fall into enemy hands. Fot the Navajos, committing everything to memory was trivial because traditionally their language had no written script, so they were used to memorising their folk stories and family histories....
At the end of their training, the Navajos were put to the test .... The results were word-perfect. To check the strength of the system, a recording of the transmissions was given to Navy Intelligence, the unit that had cracked Purple, the toughest Japanese cipher. After three weeks of intense cryptanalysis, the Naval codebreakers were still baffled by the messages .... The Navajo code was judged a success. Two Navajo soldiers ... were asked to stay and train the next batch of recruits, while the other 27 Navajo code talkers were assigned to four regiments and sent to the Pacific.
....The Japanese planned to consolidate their control of the Pacific by building an airfield on Guadalcanal, creating a base for bombers which would enable them to destroy Allied supply lines, thus making any Allied counterattack almost impossible. Admiral Ernest King, Chief of American Naval Operations, urged an attack on the island before the airfield was completed, and on 7 August  the 1st Marine Division spearheaded an invasion of Guadalcanal. The initial landing parties included the first group of code talkers to see action.
....The code talkers soon proved their worth on the battlefield. During one episode on the island of Saipan, a battalion of marines took over positions previously held by Japanese soldiers, who had retreated. Suddenly a salvo exploded nearby. They were under friendly fire from fellow Americans who were unaware of their advance. The marines radioed back in English explaining their position, but the salvos continued because the attacking American troops suspected that the messages were from Japanese impersonators trying to fool them. It was only when a Navajo message was sent that the attackers saw their mistake and halted the assault. A Navajo message could never be faked, and could always be trusted.
The reputation of the code talkers soon spread, and by the end of 1942 there was a request for 83 more men. The Navajos were to serve in all six Marine Corps divisions, and were sometimes borrowed by other American forces. Their war of words soon turned the Navajos into heroes. Other soldiers would offer to carry their radios and rifles, and they were even given personal bodyguards ....
The impenetrability of the Navajo code was all down to the fact that Navajo belongs to the Na-Dene family of languages, which has no link with any Asian or European language. For example, a Navajo verb is conjugated not solely according to its subject, but also according to its object. The verb ending depends on which category the object belongs to: long (e.g. pipe, pencil), slender and flexible (e.g. snake, thong), granular (e.g. sugar, salt), bundled (e.g. hay), viscous (e.g. mud, feces) and many others. The verb will also incorporate adverbs, and will reflect whether or not the speaker has experienced what he or she is talking about, or whether it is hearsay. Consequently, a single verb can be equivalent to a whole sentence, making it virtually impossible for foreigners to disentangle its meaning.
Despite its strengths, the Navajo code still suffered from two significant flaws. First, words that were neither in the natural Navajo vocabulary nor in the list of 274 authorised codewords had to be spelt out using the special alphabet. This was time-consuming, so it was decided to add another 234 common terms to the lexicon ....
The second problem concerned those words that would still have to be spelt out. If it became clear to the Japanese that words were being spelt out, they would realise that they could use frequency analysis to identify which Navajo words represented which letters. It would soon become obvious that the most commonly used word was dzeh, which means "elk" and which represents e, the most commonly used letter of the English alphabet. Just spelling out the name of the island Guadalcanal and repeating the word wol-la-chee (ant) four times would be a big clue as to what word represented the letter a. The solution was to add more words to act as extra substitutes (homophones) for the commonly used letters. Two extra words were introduced as alternatives for each of the six commonest letters (e, t, a, o, i, n) and one extra word for the six next commonest letters (s, h, r, d, l, u). The letter a, for example, could now also be substituted by the words be-la-sana (apple) or tse-nihl (axe). Thereafter, Guadalcanal could be spelt with only one repetition: klizzie, shi-da, wol-la-chee, lha-cha-eh, be-la-sana, dibeh-yazzie, moasi, tse-nihl, nesh-chee, tse-nihl, ah-jad (goat, uncle, ant, dog, apple, lamb, cat, axe, nut, axe, leg).
As the war in the Pacific intensified, and as the Americans advanced from the Solomon Islands to Okinawa, the Navajo code talkers played an increasingly vital role. During the first days of the attack on Iwo Jima, more than eight hundred Navajo messages were sent, all without error. According to Major General Howard Conner, "without the Navajos, the marines would never have taken Iwo Jima." The contribution of the Navajo code talkers is all the more remarkable when you consider that, in order to fulfil their duties, they often had to confront and defy their own deeply held spiritual fears. The Navajo believe that the spirits of the dead, chindi, will seek revenge on the living unless ceremonial rites are performed on the body. The war in the Pacific was particularly bloody, with corpses strewn across the battlefields, and yet the code talkers summoned up the courage to carry on regardless of the chindi that haunted them. In Doris Paul's book The Navajo Code Talkers, one of the Navajo recounts an incident which typifies their bravery, dedication and composure:
If you so much as held up your head six inches you were gone, the fire was so intense. And then in the wee hours, with no relief on our side or theirs, there was a dead standstill. It must have gotten so that this one Japanese couldn't take it anymore. He got up and yelled and screamed at the top of his voice and dashed over our trench, swinging a long samurai sword. I imagine he was shot from 25 to 40 times before he fell.
There was a buddy with me in the trench. But that Japanese had cut him across the throat, clear through to the cords on the back of his neck. He was still gasping through his windpipe. He died, of course. When the Jap struck, warm blood spattered all over my hand that was holding a microphone. I was calling in code for help. They tell me that in spite of what happened, every syllable of my message came through.
Altogether, there were 420 Navajo code talkers. Although their bravery as fighting men was acknowledged, their special role in securing communications was classified information. The government forbade them to talk about their work, and their unique contribution was not made public .... Eventually, in 1968, the Navajo code was declassified, and the following year the code talkers held their first reunion. Then, in 1982, they were honoured when the US Government named 14 August "National Navajo Code Talkers Day." However, the greatest tribute to the work of the Navajo is the simple fact that their code is one of very few throughout history that was never broken. Lieutenant General Seizo Arisue, the Japanese chief of intelligence, admitted that, although they had broken the American Air Force code, they had failed to make any impact on the Navajo code.