WGBPDUU0WGBPD b lSlBl JWU'il GBPD lSWlB Li J U $ J $ II OO $GBPD l $ 6J OOGBPD I1WW l NOV - DEC -1985 I SEMESTER A QUANTUM LEAP FORWARD U o o o o -- 1 BULLETIN BOARD U o o o o o o o o o o o o o o o o o o oooo 6 WHY DO WE NEED THOSE FUNNY ALPHABETS U 7 SHELL GAME HYPHENATION U o o o o o o o o WES o o o o o o o o o 10 BOOK REVIEW KRYPTOLOGIE U o o 11 1 I 1 LETTER TO THE EDITOR U OPPORTUNITY U o o o o PUZZLE U o o o o o o o Declassified and Approved for Release o o o o o o o o o o o o o by NSA on 10 NOT RELEASABLE TO CONTRACTORS HA DL VIA CQMI JT CPi P- P-jELS OP-dlY I I o o o o o o o o o o o o o o o o oo oo 12 o o 12 o 13 16-2012 pursuant to E O 13526 MDR Case # 54 CLASSIFIED BY PdSA CSSM 123 2 DECLASSlf V O L Ori iFlatin net A eneyts DeteHAiFlatioFl Re l liFeel aCID 4012016 eONFIBEN'fIAL Published by PI Techniques and Standards VOl XII Nos 11-12 November December 1985 P L 86-36 PUZZLE MAKERS PUZZLE SOLVERS u PUBLISHER o L- - BOARD OF EDITORS J1 963 tt 3 J Editor Collection 1 It9 6 3 ' oo 5 '7 7 Computer Security 1 968'8141 Computer Systems I 963' J I 03 Cryptanalysis 1 9631-4740 Cryptolinguistics 9f -1596 Index 1 9 3-S330 Information Science 1 963-1145 Intelligence Research J'63 3095 Language 963-3057 Mathematics 1 f 963-S566 Science and Technology 1 f 91i3-4191 Special Research Vera R Filby 968-8014 Traffic Analysis Robert J Hanyok 963-5734 r Illustrator 1 f 963-3057 To submit articles or letters by mail send to Editor CRYPTOLOG PI If you used a word processor please include the mag card floppy or diskette along with' your hard copy with a notation as to what equipment operating system and software you used via PLATFORM mail send to cryptolg at barlcOS bar-one-c-zero-fi vel note no '0' in 'log' Always include your full name organization and secure phone number ------ U David H William5 '-Puzzle Editor and former Editor in-Chi f of CRYPTOLOG retired in November He IS better known as DHW the compiler of those fiendish NSA-Crostics that challenge even the most successful of NSA's renowned puzzle solve 'S Those puzzles have been a popular feature of thl magazine and will be missed by the many subscnbers who always turn to the back pages first DHW in his person as Dave linguist telemetnst punster a nd walking encyclopedia will also be missed by his colleagues and especially by the present editor He was a favorite source of informat on for he presented facts with witty explanations and humorous illustrations even on sober and arcane subjects a small circle David H Williams will always be empmbP'p U Now a word of comfort for the busman's holiday puzzle solvers who abound in this Agency Take heart We'll see to it that there's a puzzle of 0n 'e kind or another in the back pages And we inVite puzzle makers among the readers to contribute their concoctions U About solutions to the puzzl s all the news that fits we print to quote the motto of this editor's high school newspaper We expect to catch up in the next issue But we do solicit comments from readers on whether the solution should appear in the same issue as the puzzle or in the next issue P L 86-36 o 1 4 For Change of Address send name and old and new organizations to Editor CRYPTOLOG PI Contents of CRYPTOLOG should not be reproduced or fu rther dissemmated outside the National Security Agency Without the permission of the Publisher Inquiries regarding reproduction and dissemination should be directed to the Editor CONF B8 'f AL r c P S for DHW fans find the pun I 4012016 CONFIB8N'i'lAL 86-36 L 86-36 1 4 c r ' i I I tif 'e i' e 'aS5 flee C ceQ R it e t r9t ' Computer-supported transcription has taken a quantum leaS forward Now under the Droiect name SEME TERI 'Iov-Dec 1985 CRYPTOLOG page 1 IIA 'JDL6 VlA OOMm'i' OilAUKRLS or LY CONl'm8Pt'i'IAL GCID 4012016 Virtual Terminals Nov-Dec 1935 page 2 aCID L 4012016 COl JFIQ l ITIAL 'ov-Dec 1985 CRYP'I'OLOG page 3 IIAtWbEl JPYfA GOl Hl'f'f' GIIAl'Jl'H H 'S OnLY CONFIQ NTIAL 86-36 aCID 4012016 C CCO L DISTRIBUTION OF SEMESTER SYSTEMS SYSTEMS OPERATIONAL Active Budgeted Budgeted 1 I EO 1 4 Td EO 1 4 c P L 86-36 --- 1 c L 6-26 I 1 1 TOTAL DEVELOPMENTAL I GRAND TOTAL '---- Q P L Nov-Dec 1985 CRYPTOLOG page 4 IIA tDL S VIA COMlH'f CIIA HlELS onLY COr FltlIilPHIAL 86-36 86-36 aCID OJPYZd16 CONI ml'jt l1'lAL Nov-Dec 1985 CRYPTOLOG page IIAUBbE InA COMUIT 5 GRAPnn jg o rbJPY eorn'ml p IAb L 86-36 L 86-36 D 4012016 C6Nnf I3P 'f'IAL Editor's Note Readers may be interested in the article 'Computer-Aided Transcription by the same author that appeared in the April 1976 issue o CRYPTOLOG BULLETIN BOARD 'Ifov-Dec 1985 o CRYPTOLOG o page 6 HANDLE VIA GOMTHT CIIAnP'fELS OP'fLY EO 1 4 c CONFIIJFJNHAL P L 86-36 aCID 4012016 I1q J German Dutch English Norwegian _ _ Arabic Kurdish Farsi--- 1110 Urdu J lashto Dari q9Ci oSy Polish Slovene Slovak Czecn 1 o'edish SerbQ J Q lt n Danish Italian French Romanian Spanish J Qrtu9uese Russian Bulgarian P L '-- 86-36 G - - - Amharic Lao PROTO-SEMITIC e have reached the level of technology in j L which we plan supercom puting research 71' centers fill the basement with Crays and strain our electrical circuits to the breaking point with ASTW's ASH's HPW's and every kind of advanced electronic equipment we can find With such great advances in the state of the art do we still have to use that good old 26-letter English alphabet to represent all of our foreign language material on computers What Can We Do With Foreign Scripts oreign scripts and diacritical marks on Roman letters convey useful information to Ct the translator which is sometimes missed in transliterations into Roman letters lacking those marks Because of the variety of transliteration schemes transliterations are often ambiguous and sometimes confusing and lack the subtle distinctions of a language written in its own script In addition our linguists usually come to NSA trained in reading the native script and having to learn a new representation for the language delays their effectiveness C The same problem arises in creating on-line working aids for linguists and here the correct representation of the language is even more important The transliteration is often a cruder version of the language and therefore transliteration systems vary from target to target and even from analyst to analyst so that transliterations are less useful for dictionaries glossaries bookbreaker's tools etc Without the proper tools to build a glossary some linguists at NSA are building on-line working aids with idiosyncratic transliterations which make them difficult to use by anyone but the authors When the authors transfer to new assignments their experience and insight are lost because other people cannot find the terms they have recorded Where Did All Those Foreign Alphabets Come From ddly enough they all came from the same place Considering how useful an alphabet o is for representing a language it is surprising that the alphabet was invented only once about 3500 years ago in the Fertile Crescent All of the many other alphabets in the world either borrowed an alphabet descended from this early iliov-Dec 1985 o CRYPTOLOG 1 0It OIT'SlAb page 7 S O LY ero 4012016 Semitic alphabet or borrowed the idea of an alphabet and invented their own script as apparently the Koreans did The Roman alphabet was adopted by many languages from different linguistic groups so it is not surprising that many changes had to be made In adapting the Roman alphabet to their The Greeks received the Semitic alphabet from the languages most people combined letters or added ' Phoenicians when trade brought them into contact diacritical marks The result of all these The Greeks recognized the potential of an alphaadaptations is that the extended Roman alphabet bristles with diacritics predominately on the bet although the Phoenician alphabet was not suitable for Greek because it did not contain signs vowels The 5 vowels of the Roman alphabet are its for Greek vowels In the Semitic languages vowels most glaring weakness in representing a language are not very important for distinguishing words as English has approximately 12 vowels depending they are in Indo-European languages because on the dialect so we have to overcome this they usually denote inflections and different parts shortage by combining vowel sounds under a single of speech which can be understood from context vowel representation Anyone who has worked' with a child learning to spell English is aware of The Greeks added vowels a very important the confusion which this can cause innovation to the alphabet Greek words stripped The Roman Alphabet A Gift from the Gods of their vowels as is the case with many languages are indistinguishable from other words or Just Another Script with different meanings In English the consonants ct could stand for act cat cut e received the upper case letters of the cute acute etc Roman alphabet literally carved in stone The Romans had a penchant for building The Greeks took letters of the Phoenician alphabet monuments and chiselling inscriptions on them which they didn't need because their language They therefore modified their alphabet to forms didn't have the same sounds as Phoenician and which could be carved easily into stone and would at the same time provide a grand and elegant used them for the Greek vowels This adaptation by the Greeks made their alphabet a reasonable display representation for European languages and the two alphabets now found in use in Europe Roman Centuries later after the invention of the and Cyrillic can both be traced to the Greek computer by English-speaking people these same alphabet letters proved to be easy to display with a small matrix of dots by a printer or later on a CRT The The other alphabets in the world can be traced to lower case Roman letters evolved differently In other Semitic variations of the alphabet The only addition to writing on stone the Romans wrote on surviving descendent of South Semitic is the wax tablets papyrus and later parchment These media with stylus or ink demanded a different Amharic script Aramaic a North Semitic alphabet was as productive as the Phoenician style ofletters which could be written more quickly alphabet giving rise to Arabic and the Arabicthan the capital letters This need gave rise to the related scripts used for Urdu Farsi DarLand cursive style and lower case letters Pashto The Indian and Southeast Asian scripts probably also came Aramaic The Nagari The lower case letters are not as easy to print and Devanagari and Gurmukhi scripts among others display on a computer because some of them extend in India are descended from the Indian branch of be ow the base line and the enclosed spaces are the Aramaic-based scripts while another very smaller requiring higher resolution that is more productive branch the South Indian has given rise dots to represent them clearly to the Southeast Asian scripts Burmese Karen Shan Lao Thai Khmer etc Nevertheless lower case letters have been added to computer character codes and ASCII the How is an Alphabet Adapted American Standard Code for Information to a New Language Interchange now has both upper and lower case Roman letters to represent English Lower case he sound pattern ofeach language is letters are therefore available on a growing unique as distinct as a fingerprint Some number of computers type of adjustment must always be made to fit an existing alphabet to a new language A In terms of the development of the computer the variety of techniques can be used for this task English version of the Roman alphabet has been a including dropping unneeded letters or using them gift from the Gods providing the simplest writing for other sounds which are needed in the new lansystem in tJ1e modern world for displaying text on a guage combining two or more letters to represent computer and thereby facilitating the a new sound inventing new symbols or borrowing development of the computer symbols from another alphabet to represent a new sound using diacritical marks small marks above 'In terms of representing text or understanding or below the letter such as accents or using one natural languages however it is important to symbol for two or more sounds W m W Nov-Dec 1985 It QK CRYPTOLOG page 8 QFFIClAL USI J O 'LY 4012016 ALPHABETS ON THE XEROX STAR Afrikaans Albanian Amharic Arabic Armenian BangIa Bulgarian Burmese Cebuano Chinese Czech Danish Dari Dutch English Farsi French German Greek Haitian Creole Hebrew Hindi Hungarian Ilocano Indonesian Italian Japanese Khmer Korean Kurdish Lao Lingala Maghrebi Arabic Malagasy Norwegian Pampangan Pashto Polish Portuguese Romanian Russian Serbo-Croatian Slovak Slovene Spanish Swahili Swedish Tagalog Thai Turkish Urdu Vietnamese u P L 86-36 remember that the English version of the Roman alphabet is just another script How Can We Represent the Other Scripts on the Computer he standard ASCII character codeof7 bits gives us 27 or 128 characters to work with This is only enough for English and is the character code size of the ASTW and other UNIXbased systems The extended ASCII code of 8 bits gives us 28 or 256 characters and is displayable under DOS and other operating systems The extended ASCII code gives us some vowels with diacritical marks and two consonants with diacritics so that we can represent the Scandinavian and West European languages The extended ASCII code is not sufficient for representing the East European or Asian languages which are written in the Roman alphabet It contains a few Greek letters used in mathematical or scientific notation but does not contain the entire Greek alphabet In order to complete the Roman alphabet and to add all of the other alphabets and the Chinese and Japanese syllabaries we obviously need a far larger character code than we can get using a single computer word of8 bits Xerox has solved this problem by building a double word for the Xerox STAR character code The 16bit character code gives us 216 or 65 536 characters ov-Dec 1985 I'QR to use in representing our alphabets and syll baries which is ample pace necj tb varIOUS characters for alll _ _ __ __I languages The code expan s to 1 Its on y were needed for the language fonts so space is not wasted in processing text in the standard ASCn code In addition to developing an operating system and character code which is capable of displaying all of these foreign languages Xerox has already built many foreign-Iangauge character fants With the 1986 software release a total of 52 languages will be available on the new faster fully-programmable Xerox STAR Should NSA Abandon the 7-bit ASCII Standard for Language Processing es The l6-bit extended ASCII code is compatible with the 7-bit or 8-bitASCII codes so our data bases in English will be fully compatible with the l6-bit character code as has been demonstrated by connecting the Xerox terminals to CARILLON and other computer systems Now that computer processing has developed to the point where we are talking about massively parallel processing and millions ofoperations per second do our linguists still need to be shackled by a writing system devised by Roman stonecutters 2000 years ago 0 CRYPTOLOG page QI' l ICIAb 9 USB OP LY aCID 4012016 SHELL hyphen-ation GAME P L 86-36 wes The other day I wanted to check the hyphenating done by nroff on a document I'm getting ready to produce If you've worked with nroff or almost any other hyphenating system you know that it tries hard but has a few flaws some of them genuine howlers Nroff allows you to force the hyphens wherever you want for any given word but you have to know which words it botches And every now and then one finds a new one Line 3 puts the first line into file hyck out a reminder of the content of the file -- I get forgetful sometimes So I decided to build a little shell that would pull out those lines ending with a hyphen along with the line followin and print them onto a separate file for examinatIOn I decided to use the stream editor sed mostly because it is rather fast It zips through long files with great ease I don't know in want to check the hyphens in a REALLY long file but I'll worry about that if ever get one Line 5 gives me a count of words and lines Line 4 does the work running the sed according to the commands listed in the companion file hyck lib located in my lib directory The output is added to file hyck out if the were a the file would first be erased Line 6 puts the output file into the screen editor for me The companion file hyck lib looks like this tn Pr hyphen lines and Eol lines c - -$ The shell file is called hyck and looks like this loop if x $l x goto usage 1 $s lib echo hyck of file $1 hyck out sed -f $l hyek lib $1 hyek out we hyek out e hyek out -exit usage echo Usage hyck filename Line 1 checks for a filename in the command line and bails out with an error message if it doesn't find any Line 2 assigns the variable I letter L a string which equates to my directory lib at top level I have top level directories named bin for my executable files including shells and lib for my library files It is my habit in my profile to assign my bin directory the shell variable b and to assign my lib directory the variable I This shell hyck is kept in my bin and a companion file called hyck lib is kept in my lib The variable s on line 2 is a standard shell variable which always expands to my home login directory p n rc - -$ b loop p Line 1 says don't print any line unless asked to Line 2 looks for a line ending with a '-' but not preceded by a space or another '-' Note on some UNIX systems the c will be a 'hat' or circumflex Line 3 prints the line number Line 5 prints the line Line 6 moves to the following line Line 7 branches back to Line 4 Cb loop' if this is another line ending with a hyphen Line 8 prints this line presumably one that doesn't end with a hyphen Your own private bells and whistles can be added 0 Nov-Dec 1985 o CRYPTOLOG FOR Ol'FIGlAb YS page 10 ONbY 4012016 CO FnHi TI u BOOK REVIEW byl by PATRICK HORSTER P L 86-36 ----I 12 composite codes He defines an SP-system of whic D S is an example a s a product of ' substItutlOns and permutations Huffman coding also appears here He says that composite ciphers can be very hard to break giving an example in which three operations are performed Rheinisch-Westfiilische Technische Hochschule Aachen published by Bibliographisches Institut Wissenschaftsverlag February 1985 Editor's note In order to make it easier for readers to distinguish between the unclassified published material and the classified reviewer's remarks the latter are shown in boldface 1 addition mod 36 the st ndard al ph bet followe d by the ten digits 0-9 usmg a perIodIC k y In hIS example the key is TEXT and the plamtext SCHUTZ is enciphered SCHUTZ TEXTTE BG4DC3 2 conversion to digraphs from the alphabet A B C D E F by use of a 6x6 matrix with the 36 alphanumeric elements in scrambled order in the matrix 3 finally application of a fixed 6-long permutation to the resulting stream in blocks of six FOUO This is a textbook on cryptography which is elementary by our standards and U Horster gi es a se ond composite scheme breaks no new ground But a few of the examples are novel they will he emphasized in WhICh he aSSOCIates WIth the Russian spy Reino Hayhanen the paragraphs which follow The text follows notes which the author has apparently used for a l encipherment with a course monome-dinome matrix with the resulting stream entered into a 9-wide matrix U The first five chapters are introductory The next three concern classical cryptology 2 application of a including DES in Chapter 8 There follow three permutation key foll wed by extrs ction by columns chapters on public-key cryptosystems Then two from the 9-wlde m trIx th resultIng text is then chapters summarize needed results in number entered mto a 6-wlde matrIX not horizontally but theory and elementary algebra The last chapter following a staircase design contains a brief sketch of rotor machines and the McEliece public-key system based on old Goppa codes We shall treat only the six central chapters 6-11 which deal with classical and public-key systems U Chapter 6 starts with substitution methods Some of the examples are harbingers one finds a keyed P-Box which permutes inputs a matrix which later will implement a Hill system appears too The familiar Vigenere and Caesar systems are also discussed as are one-time pads and periodic additive systems Linear feedback shift registers make an appearance as do Playfair systems and an old system which I didn't recall it had appeared in a 1902 book in French by Dellastelle U Moving quickly through transposition methods he closes the chapter with a section on 4012016 EO 1 4 d P L 86-36 L 86-36 linear n-stage shift register will allow solution He uses Gaussian elimination to solve the system ofn equations Finally he explains a chosen plaintext attack on the Hill system LETTER FOUO Chapter 8 is devoted to DES It contains the usual description a section on modes of operation and an inconclusive section on security I could find nothing new in this chapter TO THE EDITOR EO GeO Chapter 9 deals with the public k y distribution system attributed in the outside Ii r r 0 PohIi and Hellman Thank-you for publishing the help-wanted ad for A331 This was a quick way to put the word out to the cryptanalytic community it was faster than going through normal personnel channels As a result we found a cryptanalyst to fill the - -- - the encipherment of a message x is x e mod p decipherment is performed by an operation of the same form exponent d with ed 1 mod p-1 Horster discusses known methods for taking logarithms mod p but does not get into the exciting recent work ofOdlyzko and Coppersmith position I r t 1Itu ll gilli B8EURRE'f' 4 0 660 In Chapter 10 we find a description of the RSA Rivest-Shamir-Adleman al orithm Horster L s o w s o w -r re c o v e r e pr a l n e x r ' 'w entwo identical messages are enciphered with different exponents but the same compound modulus He discusses the attack on RSA which arises from the iteration of the encipherment operator One section is allotted for a discussion of the modification attributed to Hugh Williams recall that one of the two primes whose product yields the modulus n is congruent to 3 mod 8 the other to 7 mod 8 and the proof that this modification makes solving the RSA scheme as difficult as factoring FOUO tI'he longest chapter in the book is Chapter 11 presenting systems based on knapsacks Although all of the knapsacks had appeared in the literature I confess to an unfamiliarity with a few of them He defines the usual superincreasing knapsack simpel or extra simpel if the knapsack elements are not permuted and shows how a modular transformation provides a trapdoor in the system The Graham-Shamir system is introduced A knapsack attributed to C Leung 1978 and another designed by Willett 1983 are described Both of these had escaped my attention Others who may have seen them have quite reasonably ignored them The attack ofShamir which destroyed the Merkle-Hellman knapsack is sketched but the recent developments due to Brickell and Lagarias which showed the weakness of the iterated Merkle-Hellman scheme are not mentioned Signatures via knapsacks receive cursory consideration FOUO In summary this book is an elementary summary of known results I find that it is well written but it is neither as complete nor as advanced as for example the recent book of Konheim 0 - _ 9' -1' OPPORTUNITY ONE-OF-A-KIND JOB FOR I a technically-oriented SR IR or linguist I I a literate cryppie or computer scientist I I as a team member on a high-visibility project involving G4's enciphered speech mission to document software engineering development I must be able to communicate with highly creative managers programmers and analysts I will be expected to develop a coherent document from the writings of several authors will have a chance to publish independent papers I I must be able to meet deadlines For further information contact -Jov-Dcc 1985 CRYP1'OLOG o page 12 CO Hnf CIIAN fELS O l fLY 9fc3EURlH 'f' IIAUDLE YIA I I 434 963-1499 P L 86-36 aCID 4012016 L PUZZLE IN PURPLE CONTRIBUTED BY M W flOANNyfl WALTZ o -Dec 1985 o CRYPTOLOG page 13 fOR OFI'ICIAL USE ONLY 86-36 This document is from the holdings of The National Security Archive Suite 701 Gelman Library The George Washington University 2130 H Street NW Washington D C 20037 Phone 202 994-7000 Fax 202 994-7005 nsarchiv@gwu edu