of personal credentials (in contrast to consumable The price of this feature is an even higher compu-

credentials) can neither be detected nor prevented tational complexity of the showing of credentials.

by referring only to the digital activity of individ- It appears that detecting a cheating individ-

uals. There must be some mechanism that can ual who has lent his personal credentials to an-

distinguish whether the individual who shows a other individual, or who has borrowed a personal

personal credential is the same as the individ- credential from another individual is technically

ual to whom that credential has been issued be- possible, but is often unacceptable in practice.

fore. Since personal devices as well as personal Unauthorized access may lead to disastrous or

access information such as PINs and passwords hard-to-quantify damage, which cannot be com-

can easily be transferred from one individual to pensated after the access has been made regard-

another, there is no other way to make this dis- less how individuals are persecuted and what

tinction but by referring to hardly transferable measures of retaliation are applied.

characteristics of the individuals themselves, for The wisdom of more than 20 years of research

example, through some kind of (additional) bio- on credentials is that in of¬‚ine consumable creden-

metric identi¬cation (see biometrics) of individu- tials overspender detection can be achieved by dig-

als. Then, illegitimate showing can be recognized ital means alone while overspending prevention

during the attempt and thus can be prevented can only be achieved by relying on tamper resis-

effectively, however, at the price of assuming tant hardware. In online consumable credentials,

tamper resistant biometric veri¬cation hardware. both overspender detection and overspending pre-

Bleumer proposed to enhance the wallet-with- vention can be achieved without relying on tamper

observer architecture of Chaum and Pedersen [15] resistant hardware.

by a biometric recognition facility embedded into In personal credentials, one is interested in

the tamper resistant observer in order to achieve transfer prevention, which we have called non-

transfer prevention [1]. transferability. Considering a separate integrity

Camenisch and Lysyanskaya [5] have proposed requirement of transferer detection makes lit-

a personal credential scheme which enforces non- tle sense in most applications because the po-

transferability by deterring individuals who are tential damage caused by illegitimately trans-

willing to transfer, pool, or share their creden- ferring credentials is hard to compensate for.

112 Credentials

Nontransferability can be achieved in a strict Quisquater and J. Vandewalle. Springer-Verlag,

Berlin, 288“293.

sense only by relying on tamper resistant biomet-

[10] Chaum, David (1990). “Showing credentials with-

ric veri¬cation technology, regardless if it is an

out identi¬cation: Transferring signatures be-

online or of¬‚ine scheme. Nontransferability can

tween unconditionally unlinkable pseudonyms.”

be approximated by deterrence mechanisms inte-

Advances in Cryptology”AUSCRYPT™90, Sydney,

grated into the personal credential schemes, but it

Australia, January 1990, Lecture Notes in Com-

remains to be analyzed for each particular appli- puter Science, vol. 453. Springer-Verlag, Berlin,

cation how effective those deterrence mechanisms 246“264.

can be. [11] Chaum, David (1992). “Achieving electronic pri-

vacy.” Scienti¬c American 267 (2), 96“101.

Gerrit Bleumer [12] Chaum, David, Bert den Boer, Eugene van Heyst,

Stig Mjlsnes, and Adri Steenbeek (1990). “Ef¬cient

References of¬‚ine electronic checks.” Advances in Cryptology”

EUROCRYPT™89, Lecture Notes in Computer

Science, vol. 434, eds. J.-J. Quisquater and J.

[1] Bleumer, Gerrit (1998). “Biometric yet privacy pro-

Vandewalle. Springer-Verlag, Berlin, 294“301.

tecting person authentication.” Information Hid-

[13] Chaum, David and Jan-Hendrik Evertse (1987). “A

ing, Lecture Notes in Computer Science, vol.

secure and privacy-protecting protocol for trans-

1525, ed. D. Aucsmith. Springer-Verlag, Berlin, 99“

mitting personal information between organiza-

110.

tions.” Advances in Cryptology”CRYPTO™86, Lec-

[2] Brands, Stefan (1994). “Untraceable off-line

ture Notes in Computer Science, vol. 263, ed. A.

cash in wallet with observers.” Advances in

Odlyzko. Springer-Verlag, Berlin, 118“167.

Cryptology”CRYPTO™93, Lecture Notes in Com-

[14] Chaum, David, Amos Fiat, and Moni Naor

puter Science, vol. 773, ed. D.R. Stinson. Springer-

(1990). “Untraceable electronic cash.” Advances in

Verlag, Berlin, 302“318.

Cryptology”CRYPTO™88, Lecture Notes in Com-

[3] Brands, Stefan and David Chaum (1994).

puter Science, vol. 403, ed. S. Goldwasser. Springer-

“Distance-bounding protocols.” Advances in

Verlag, Berlin, 319“327.

Cryptology”EUROCRYPT™93, Lecture Notes in

[15] Chaum, David and Torben Pedersen (1993).

Computer Science, vol. 765, ed. T. Helleseth.

“Wallet databases with observers.” Advances in

Springer-Verlag, Berlin, 344“359.

Cryptology”CRYPTO™92, Lecture Notes in Com-

[4] Brickell, Ernie, Peter Gemmell, and David Kravitz

puter Science, vol. 740, ed. E.F. Brickell. Springer-

(1995). “Trustee-based tracing extensions to

Verlag, Berlin, 89“105.

anonymous cash and the making of anonymous

[16] Chen, Lidong (1996). “Access with pseudonyms.”

change.” 6th ACM-SIAM Symposium on Discrete

Cryptography: Policy and Algorithms, Lecture

Algorithms (SODA) 1995. ACM Press, New York,

Notes in Computer Science, vol. 1029, eds. E.

457“466.

Dawson and J. Golic. Springer-Verlag, Berlin, 232“

[5] Camenisch, Jan and Anna Lysyanskaya (2001).

243.

“Ef¬cient non-transferable anonymous multishow

[17] Cramer, Ronald and Torben Pedersen (1994).

credential system with optional anonymity revo-

“Improved privacy in wallets with observers

cation.” Advances in Cryptology”EUROCRYPT

(extended abstract).” Advances in Cryptology”

2001, Lecture Notes in Computer Science, vol.

EUROCRYPT™93, Lecture Notes in Computer Sci-

2045, ed. B. P¬tzmann. Springer-Verlag, Berlin,

ence, vol. 765, ed. T. Helleseth. Springer-Verlag,

93“118.

Berlin, 329“343.

[6] Camenisch, Jan and Anna Lysyanskaya (2002).

˚

[18] Damard, Ivan B. (1990). “Payment systems

“Dynamic accumulators and application to ef¬-

and credential mechanisms with provable secu-

cient revocation of anonymous credentials.” Ad-

rity against abuse by individuals.” Advances in

vances in Cryptology”CRYPTO 2002, Lecture

Cryptology”CRYPTO™88, Lecture Notes in Com-

Notes in Computer Science, vol. 2442, ed. M. Yung.

puter Science, vol. 403, ed. S. Goldwasser. Springer-

Springer-Verlag, Berlin, 61“76.

Verlag, Berlin, 328“335.

[7] Camenisch, Jan, Ueli Maurer and Markus Stadler

[19] Even, Shimon, Oded Goldreich, and Yacov

(1996). “Digital payment systems with passive

Yacobi (1984). “Electronic wallet.” Advances in

anonymity-revoking trustees.” ESORICS™96, Lec-

Cryptology”CRYPTO™83, Lecture Notes in Com-

ture Notes in Computer Science, vol. 1146, ed. V.

puter Science, ed. D. Chaum. Plenum Press, New

Lotz. Springer-Verlag, Berlin, 33“43.

York, 383“386.

[8] Chaum, David (1985). “Security without identi¬ca-

[20] Frankel, Yair, Yannis Tsiounis, and Moti Yung

tion: Transaction systems to make Big Brother ob-

(1996). “Indirect discourse proofs: Achiev-

solete.” Communications of the ACM 28 (10), 1030“

ing ef¬cient fair off-line e-cash.” Advances in

1044.

Cryptography”ASIACRYPT™96, Lecture Notes in

[9] Chaum, David (1990). “Online cash checks.” Ad-

Computer Science, vol. 1163, eds. K. Kim and T.

vances in Cryptology”EUROCRYPT™89, Lecture

Matsumoto. Springer-Verlag, Berlin, 286“300.

Notes in Computer Science, vol. 434, eds. J.-J.

Cryptanalysis 113

CRYPTANALYSIS

[21] Franklin, Matthew and Moti Yung (1993). “Se-

cure and ef¬cient off-line digital money.” 20th In-

ternational Colloquium on Automata, Languages

Cryptanalysis is the discipline of deciphering a ci-

and Programming (ICALP), Lecture Notes in

phertext without having access to the keytext (see

Computer Science, vol. 700, eds. A. Lingas, R.G.

cryptosystem), usually by recovering more or less

Karlsson, and S. Carlsson. Springer-Verlag, Berlin,

directly the plaintext or even the keytext used, in

265“276.

cases favorable for the attacker by reconstructing

[22] Lysyanskaya, Anna, Ron Rivest, A. Sahai, and

the whole cryptosystem used. This being the worst

Stefan Wolf (1999). “Pseudonym systems.” Selected

case possible for the attacked side, an acceptable

Areas in Cryptography, Lecture Notes in Computer

Science, vol. 1758, eds. H.M. Heys and C.M. Adams. level of security should rest completely in the key

Springer-Verlag, Berlin, 302“318. (see Kerckhoffs™ and Shannon™s maximes). “A sys-

[23] Naccache, David and Sebastiaan von Solms (1992). tematic and exact reconstruction of the encryp-

“On blind signatures and perfect crimes.” Comput- tion method and the key used” (Hans Rohrbach,

ers & Security, 11 (6), 581“583.

1946) is mandatory if correctness of a cryptana-

[24] Stadler, Markus, Jean-Marc Piveteau, and Jan Ca-

lytic break is a to be proved, e.g., when a cryptan-

menisch (1995). “Fair blind signatures.” Advances

alyst is a witness to the prosecution.

in Cryptology”EUROCRYPT™95, Lecture Notes in

Computer Science, vol. 921, eds. L.C. Guillou and

J.-J. Quisquater. Springer-Verlag, Berlin, 209“219.

TERMINOLOGY: Cryptanalysis can be passive,

which is the classical case of intercepting the mes-

sage without giving any hint that this was done,

CROSS-CORRELATION or active, which consists of altering the message

or retransmitting it at a later time, or even of in-

Let {at } and {bt } be two sequences of period n (so serting own messages (some of these actions may

at = at+n and bt = bt+n for all values of t) over an be detected by the recipient).

alphabet being the integers mod q (see modular A compromise is the loss (or partial loss) of se-

arithmetic). The cross-correlation between the se- crecy of the key by its exposure due to crypto-

quences {at } and {bt } at shift „ is de¬ned as graphic faults. We shall describe various kinds of

key compromises.

n’1

ωat+„ ’bt ,

C(„ ) = A plaintext-ciphertext compromise is caused by

a transmission of a message in ciphertext followed

t=0

where ω is a complex qth root of unity. Note that (e.g., because the transmission was garbled) by

in the special case of binary sequences, q = 2 and transmission of the same message in plaintext. If

ω = ’1. information on the encryption method is known

or can be guessed, this results in exposure of the

In the special case when the two sequences are

key. This attack may be successful for a plaintext

the same, the cross-correlation is the same as

of several hundred characters.

the auto-correlation. Many applications in stream

A plaintext-plaintext compromise is a transmis-

ciphers and communication systems require large

sion of two isologs, i.e., two different plaintexts,

families of cyclically distinct sequences with a low

encrypted with the same keytext. If the encryp-

maximum nontrivial value of the auto- and cross-

tion method is such that the encryption steps form

correlation between any two sequences in the

a group (see key group and pure crypto-system),

family.

then a “difference” p1 ’ p2 of two plaintexts p1 , p2

Tor Helleseth and a “difference” c1 ’ c2 of two plaintexts c1 , c2

may be de¬ned and the role of the keytext is can-

References celled out: c1 ’ c2 = p1 ’ p2 . Thus, under suitable

guesses on the plaintext language involved, e.g.,

[1] Golomb, S.W. (1982). Shift Register Sequences. on probable words and phrases, a “zig-zag” method

Aegean Park Press, Laguna Hills, CA. (see below), decomposing c1 ’ c2 , gives the plain-

[2] Helleseth, T. and P.V. Kumar (1999). “Pseudonoise

texts and then also the keytext. This compromise

sequences.” The Mobile Communications Hand-

is not uncommon in the case of a shortage of key-

book, ed. J.D. Gibson. CRC Press, Boca Raton, FL,

ing material. It is even systemic if a periodic key

Chapter 8.

is used.

[3] Helleseth, T. and P.V. Kumar (1998). “Sequences

A ciphertext-ciphertext compromise is a trans-

with low correlation.” Handbook of Coding Theory,

mission of two isomorphs, i.e., the same plain-

eds. V.S. Pless and W.C. Huffman. Elsevier, Amster-

text, encrypted with two different keytexts.

dam, Chapter 21.

114 Cryptanalysis

Exchanging the role of plaintext and keytext, this an example: the frequency pro¬le of the English

case is reduced to and can be treated as a plaintext- language looks like

plaintext compromise. This compromise is even

systematic in message sets, where the same mes-

sage is sent in different encryption to many

places, such as it is common in public key crypto-

systems.

One speaks of a brute force attack or exhaus-

tive key search if all possible keytexts are tried

out to decrypt a ciphertext (knowing or guessing abcde f gh i j k lmnop q r s t uvwxyz

the cryptosystem used). At present, with the still

growing speed of supercomputers, every 10 years If a ciphertext of 349 characters has the follow-

the number of trial and error steps that is feasible ing distribution:

is increased by a factor of roughly 25 .

Further commonly used terminology will be

given now. In a ciphertext-only attack, only one

or more ciphertexts under the same keytext

are known. In a known-plaintext attack one

knows one or more matching pairs of plaintext“

ciphertext. Frequently, this attack is carried out

with rather short fragments of the plaintext 1 0 5 36 9 10 9 54 9 10 2123 1 8 8 10 41 3 4 0 19 22 24 18 0 4

A B C D E F G H I J K L MN O P Q R S T U V W X Y Z

(e.g., probable words and phrases). In a chosen-

plaintext attack one can choose plaintexts and

it is easy to guess a C¦sar encryption that counts

obtain the corresponding ciphertexts. Sometimes

.

down three letters in the standard alphabet: a =

this can be done with the proviso that the plain-

. . .

D, b = E, c = F, . . . , z = C. More dif¬cult is the

texts may be chosen in a way that depends on

situation if a mixed alphabet is to be expected.

the previous encryption outcomes. How to foist the

Then the ¬rst step is to group the letters in cliques:

plaintext on the adversary is not a cryptographer™s

the most frequent ones, the very rare ones, and

problem, but is a problem of misleading the adver-

some in between

sary and is to be executed by the secret services.

Finally, in a chosen-ciphertext attack there is the

{etaoin} {srh} {ld} {cumfpgwyb} {vk} {xjqz},

possibility to choose different ciphertexts to be de-

crypted, with the cryptanalyst having access to the

decrypted plaintext. An example may be the inves- and to re¬ne the decryption within these cliques

tigation of a tamperproof decryption box, with the by trial and error.

hope of ¬nding the key. Depth is a notion used in connection with the

cryptanalysis of polyalphabetic encryptions. It

means the arrangement of a number of ciphertexts

STATISTICAL APPROACHES TO CLASSICAL

supposedly encrypted with the same keytext”for

CRYPTOSYSTEMS: We shall now discuss some

periodic polyalphabetic encryption broken down

statistical methods that can be used by the

according to the assumed period.

cryptanalist.

Example: a depth of ¬ve lines:

T CCVL ES KPT X MP VW HY MVG XB O RV C WA RF

V L L BV C K WF P E H ECF CGNZE KK K VI HD DI D

MY Y RD MJ WMC UI GLO KMX LR EWH X M T J HAS

B KQTZ B Z WK W Z X GZ O V T B AT KWMGM RJ KLP

MY Y VH B WJ D X CP CZO HV T S I VME BS O H R A U.

Frequency matching is a cryptanalytic method The lines of a depth are isologs: they are en-

for breaking monoalphabetic (C¦sar type) encryp- crypted with the same key text and represent a

tions. One determines the frequency of the char- plaintext“plaintext compromise.

acters in a ciphertext and compares them with the By forming differences of the elements in se-

frequency of the characters in a language known lected columns, a reduction of depth to a monoal-

or assumed to be used for the plaintext. To give phabetic (C¦sar type) encryption is accomplished.

Cryptanalysis 115

This makes it possible to derive the keytext belong. For suf¬ciently long texts, it is statistically

roughly equal to 1/15 = 6.67% for the English lan-

TRUTH ISSOP RECIO USTHA TITNE EDSAB guage and 1/12.5 = 8% for the French language

and the German language. Most importantly, it

which decrypts the depth (by means of the

remains invariant if the two texts are polyalpha-

Vigen` re table) to

e

betically encrypted with the same keytext. If, how-

al i c e wa sb e g i nni ng t og et ve r yt i re ever, they are encrypted with different keytexts

c ur i o u s er a ndc ur i o use rcri e dal i c

or with the same key sequence, but with differ-

t he yw e r ei n dee da q ue er l ooki ngpar

ent starting positions, the character coincidence

i t was t hewh i tera bbi tt r ot t i ngs l o

is rather random and the value of Kappa is sta-

t he c a t erp i l l ar a nda l i c el o o k e d a t.

tistically close to 1/N, where N is the size of the

vocabulary. The Kappa test applied to a ciphertext

Forming a depth is possible as soon as the value

C and cyclically shifted versions C (u) of the cipher-

of the period of the periodic polyalphabetic encryp-

text, where u denotes the number of shifts, yields

tion has been found, for instance by the Kasiski

the value κ(C, C (u) ). If the keytext is periodic with

method below. Forming a depth is not possible,

period d, then for u = d and for all multiples of d,

if the key is non-periodic. But even for periodic

a value signi¬cantly higher than 1/N will occur,

polyalphabetic encryptions, forming a depth of suf-

while in all other cases a value close to 1/N will be

¬ciently many elements (usually more than six) is

found. This is the use of the Kappa examination

not possible if the keytext is short enough.

for ¬nding the period; it turned out to be a more

When the alphabets used in a polyalphabetic

accurate instrument than the Kasiski method.

periodic substitution are a mixed alphabet and a

The Kappa test may also be used for adjust-

shifted version of it, symmetry of position is the

ing two ciphertexts C, C which are presumably

property that for any pair of letters their distance

encrypted with the same keytext, but with dif-

is the same in all rows of the encryption table.

ferent starting positions (called superimposition).

For a known period, it may allow, after forming a

By calculating κ(C (u) , C ), a shift d, determined

depth, the complete reconstruction of the substi-

as a value of u, for which κ(C (u) , C ) is high,

tution (Auguste Kerckhoffs, 1883).

brings the two ciphertexts C (d) and C “in phase”,

Kasiski™s method. If in a periodic polyalphabetic

i.e., produces two isologs. In this way, a depth of

encryption the same plaintext sequence of char-

n texts can be formed by superimposition from

acters happens to be encrypted with the same

a ciphertext“ciphertext compromise of n cipher-

sequence of key characters, the same ciphertext

texts.

sequence of characters will occur. Thus, in order

The De Viaris attack is a cryptanalytic method

to determine the period of a periodic polyalpha-

invented by Ga¨ tan Henri L´ on de Viaris in 1893

e e

betic encryption, the distance between two “par-

to defeat a polyalphabetic cryptosystem proposed

allels” in the ciphertext (pairs, triples, quadru-

´

by Etienne Bazeries, in which the alphabets did

ples etc. of characters) is to be determined; the

not form a Latin square. (A Latin square for a vo-

distance of genuine parallels will be a multiple

cabulary of N characters is an N — N matrix over

of the period. The greatest common divisor of

this alphabet such that each character occurs just

these distances is certainly a period”it may, how-

once in every line and in every column.)

ever, not be the smallest period. Moreover, the pe-

Pattern ¬nding is a cryptanalytic method that

riod analysis may be disturbed by faked parallels.

can be applied to monoalphabetic encryptions. It

Kasiski developed this fundamental test for key

makes use of patterns of repeated symbols. For ex-

periodicity in 1863 and shattered the widespread

ample, the pattern 1211234322 with “signature”

belief that periodic polyalphabetic encryption is

4 + 3 + 2 + 1 (four twos, three ones, two threes and

unbreakable.

one four) most likely allows in English nothing

The Kappa test is based on the relative fre-

quency κ(T, T ) of pairs of text segments T = but peppertree, the pattern 1213143152 with the

signature 4 + 2 + 2 + 1 + 1 nothing but initiation

(t1 , t2 , t3 , . . . , t M ), T = (t1 , t2 , t3 , . . . , t M ) of equal

length, M ≥ 1, with the same characters at the (Andree 1982, based on Merriam-Webster™s Dictio-

nary).

same positions (that is why this method is also

Noncoincidence exhaustion. Some cryptosys-

called the index of coincidence, often abbreviated

tems show peculiarities: genuine self-reciprocal

to I.C., William F. Friedman, 1925). The value

permutations never encrypt a letter by itself. Porta

of Kappa is rather typical for natural languages,

N

since the expected value of κ(T, T ) is 2

encryptions even always encrypt a letter from the

i=1 pi ,

¬rst half of the alphabet by a letter from the

where pi is the probability of occurrence of the

second half of the alphabet and vice versa. Such

ith character of the vocabulary to which T and T

116 Crypto machines

Reference

properties may serve to exclude many positions

of a probable word (a probable word is a word or

phrase that can be expected to be present in a mes- [1] Bauer, F.L. (1997). “Decrypted secrets.” Methods

sage according to the context; it may form the basis and Maxims of Cryptology. Springer-Verlag, Berlin.

for a known-plaintext attack).

Zig-zag exhaustion. For encryptions with a key

group (see key), the difference of two plaintexts

CRYPTO MACHINES

is invariant under encryption: it equals the dif-

ference of the corresponding ciphertexts. Thus in

These are machines for automatic encryption us-

case of a plaintext“plaintext compromise (with a

ing a composition of mixed alphabet substitutions

depth of 2), the difference of the ciphertexts can be

often performed by means of rotors. Examples

decomposed into two plaintexts by starting with

are: Enigma (Germany), Hebern Electric Code

probable words or phrases in one of the plaintexts

Machine (USA), Typex (Great Britain), SIGABA = ˆ

and determining the corresponding plaintext frag-

M-134-C (USA), and NEMA (Switzerland).

ment in the other plaintext, and vice versa. This

Rotor: wheel, sitting on an axle and having on

may lead in a zig-zag way (“cross-ruff ”) to complete

both sides a ring of contacts that are internally

decryption.

wired in such a way that they implement a per-

Theoretically, the decomposition is unique pro-

mutation.

vided the sum of the relative redundancies of the

The Enigma machine (Figures 1 and 2) was in-

two texts is at least 100%. For the English lan-

vented by the German Arthur Scherbius. In 1918,

guage, the redundancy (see information theory) is

he ¬led a patent application for an automatic,

about 3.5 [bit/char] or 74.5% of the value 4.7 ≈

keyboard-operated electric encryption machine

log2 26 [bit/char].

performing a composition of a ¬xed number of

Multiple anagramming is one of the very few

polyalphabetic substitution (see substitutions and

general methods for dealing with transposition ci-

permutations) steps (four in the early commercial

phers, requiring nothing more than two plaintexts

models) with shifted mixed alphabets performed

of the same length that have been encrypted with

by wired keying wheels (called rotors).

the same encryption step (so the encrypting trans-

The key sequence was generated by the cyclo-

position steps have been repeated at least once).

metric, “counter-like” movement of the wheels.

Such a plaintext“plaintext compromise suggests a

The ¬xed substitutions of the rotors were to be

parallel to Kerkhoffs™ method of superimposition.

kept secret, the starting point of the key sequence

The method is based on the simple fact that equal

was to be changed at short intervals. Later “im-

encryption steps perform the same permutation of

provements” were a re¬‚ector (Willi Korn, 1925)

the plaintext letters. The ciphertexts are therefore

which made the encryption self-reciprocal (and

written one below the other and the columns thus

opened a way of attack) and (by request from

formed are kept together.

the German Armed Forces Staff) a plugboard per-

Friedrich L. Bauer forming a substitution that could be changed at

e E

m

M

+4V

Fig. 1. Electric current through a three-rotor Enigma

Crypto machines 117

a more independent line of rotor machines, lead-

ing in 1933 to the M-134-T2, then to the M-134-A

(SIGMYC), and in 1936 to the M-134-C (SIGABA)

of the Army, named CSP889 (ECM Mark II) by the

Navy. The Germans obviously did not succeed in

breaking SIGABA, which had ¬ve turning cipher

rotors with irregular movement. It had been made

watertight by Frank Rowlett (1908“1998), an aide

of Friedman since 1930.

An interesting postwar variant of the ENIGMA

with seven rotors and a ¬xed re¬‚ector was built

and marketed by the Italian company Ottico Mec-

canica Italiana (OMI) in Rome.

The Swiss army and diplomacy used from 1947

on an ENIGMA variant called NEMA (˜Neue Mas-

chine™) Modell 45. It was developed by Hugo

Hadwiger (1908“1981), Heinrich Weber (1908“

1997), and Paul Glur, and built by Zellweger A.G.,

Uster. It had ten rotors, six of which were active

ones, while the others served for rotor movement

only. The use of a re¬‚ector was unchanged.

Based on US-American experiences and simi-

lar to TYPEX was the rotor machine KL-7 of the

Fig. 2. Cipher machine Enigma (four-rotor version)

NATO, in use until the 1960s.

The Swedish inventor Boris Hagelin created the

short intervals (which in fact helped to avoid cer-

Hagelin machine (Figure 3) in 1934. It was an

tain manifest attacks). The German Wehrmacht

Enigma had three rotors (to be selected out of up

to eight) and a re¬‚ector (to be selected out of two).

In the Navy variant of 1942 the re¬‚ector was not

¬xed. Certain weaknesses of the Enigma encryp-

tion were not caused by the machine itself, but by

cryptographic blunders in operating it.

An exceptional role was played by the German

Abwehr, the Intelligence Service of the German

Armed Forces, as far as ENIGMA goes: It used a

variant of the old ENIGMA D with a pinion/tooth

wheel movement of the rotors, with 11, 15, and 17

notches on the wheels (˜11-15-17 ENIGMA™), and

naturally without plugboard”following rather

closely Willi Korn™s German Patent No. 534 947,

¬led November 9, 1928, US Patent No. 1,938,028

of 1933.

A few specimens of a three-rotor-ENIGMA

(˜ENIGMA T™), likewise without plugboard, but

with ¬ve-notched rotors, were destined for the

Japanese Navy, but did not get out of the harbor

and were captured by the Allies near Lorient, in

Brittany.

In England, too, rotor machines were built dur-

ing the Second World War: TYPEX was quite

an improved ENIGMA (instead of the plugboard

there was an entrance substitution performed by

two ¬xed rotors which was not self-reciprocal).

In the USA, under the early in¬‚uence of William

Friedman (1891“1969) and on the basis of the

Hebern development, there was in the early 1930s Fig. 3. The M-209 Hagelin machine

118 Cryptology

automatic mechanical encryption machine, with

alphabet-wheel input and a printing device, per-

forming by a “lug cage” adder a Beaufort substi-

tution (see Beaufort encryption) controlled by ¬ve

keying wheels with 17, 19, 21, 23, and 25 teeth

according to a pre-chosen “step ¬gure.” The lug

matrix and the step ¬gure can be changed by acti-

vating suitable pins. This model, called C-35, was

followed by a C-36, with six keying wheels and 17,

19, 21, 23, 25, and 26 teeth. Under the cover name

M-209, C-36 was built by Smith-Corona for the US

Army, Navy and Air Forces, altogether accounting

for 140 000 machines. The Hagelin machines were

less secure than the Enigma.

Friedrich L. Bauer Fig. 1. Semagram. The message is in Morse code, formed

by the short and long stalks of grass to the left of

the bridge, along the river bank and on the garden

Reference

wall. It reads: “compliments of CPSA MA to our chief

Col. Harold R. Shaw on his visit to San Antonio May

[1] Bauer, F.L. (1997). “Decrypted secrets.” Meth-

11, 1945.” (Shaw had been head of the Technical Oper-

ods and Maxims of Cryptology. Springer-Verlag,

ations Division of the US government™s censorship divi-

Berlin.

sion since 1943)

ment ciphers (veiled secret writings, like the

CRYPTOLOGY null cipher and grilles (see substitutions and

permutations)). Linguistic steganography has

Cryptology is the discipline of cryptography and close connections with cryptography, e.g., the

cryptanalysis and of their interaction. Its aim is uses of grilles and transposition ciphers (see

secrecy or con¬dentiality: the practice of keep- substitutions and permutations) are related.

ing secrets, maintaining privacy, or concealing Semagram: a picture or grapheme hiding a mes-

valuables. A further goal of cryptology is in- sage behind innocent looking, frequently minute

tegrity and authenticity, usually given by a mes- graphic details (Figure 1).

sage authentication code (see MAC algorithms) or Open code: a class of linguistic steganography, se-

digital signature unique to the sender and serving lected words or phrases made to appear innocent

for his identi¬cation. in the surrounding text.

Cryptography: the discipline of writing a message Cue: a short, prearranged jargon-code message,

in ciphertext (see cryptosystem), usually by a usually a word or phrase. The importance of the

translation from plaintext according to some message is strongly linked to the time of trans-

(frequently changing) keytext, with the aim of mission. Famous is the encrypted Japanese mes-

protecting a secret from adversaries, intercep- sage HIGASHI NO KAZE AME (“east wind, rain”) on

tors, intruders, interlopers, eavesdroppers, op- December 7, 1941, a cue with the meaning “war

ponents or simply attackers, opponents, ene- with the USA.”

mies. Professional cryptography protects not Null cipher, where only certain letters are sig-

only the plaintext, but also the key and more ni¬cant (the others being nulls):

r

generally tries to protect the whole crypto- encryption rules of the type “the nth charac-

system. ter after a particular character,” speci¬cally “the

Steganography: counterpart of cryptography, com- next character after a space” (acrostics),

r

prising technical steganography (working with or rules for inserting a null between syllables

invisible inks and hollow heels, etc.) and linguis- (Tut Latin: TUT) or after phonetic consonants

(Javanais: chaussure ’ CHAVAUSSAVURAVE)

tic steganography, the art of hiding information

r or rules for suf¬xing nulls, e.g., un fou ’

by linguistic means. Of the later, we mention

semagrams, open code, comprising jargon code UNDREQUE FOUDREQUE (Metz 1670), also com-

(masked secret writing, e.g., cues), and conceal- bined with shuf¬‚ing of some letters (largonjem:

Cryptrec 119

boucher ’ LOUCHERBEM, pig Latin: third ’

™ Reference

™™

r

IRDTHAY);

a borderline case is pure transposition: revers- [1] Bauer, F.L. (1997). “Decrypted secrets.” Methods

ing letters of a word (back slang), e.g., tobacco and Maxims of Cryptology. Springer-Verlag, Berlin.

’ OCCABOT).

Friedrich L. Bauer

CRYPTREC

Reference

CRYPTREC was initially an abbreviation of

[1] Bauer, F.L. (1997). “Decrypted secrets.” Meth- Cryptography Research and Evaluation Commit-

ods and Maxims of Cryptology. Springer-Verlag, tee, which was set up in 2000 by METI (Ministry

Berlin. of Economy, Trade and Industry, Japan) for the

purpose of evaluating cryptographic techniques to

assure their security for e-Government applica-

tions. However, since the CRYPTREC Advisory

CRYPTOSYSTEM Committee was founded by MPHPT (Ministry

of Public Management, Home Affairs, Posts and

Telecommunications, Japan) and METI in 2001 to

A cryptosystem (or cipher system) is a system con-

perform a policymaking study on the application of

sisting of an encryption algorithm, a decryption

cryptographic techniques, it has been interpreted

algorithm, and a well-de¬ned triple of text spaces:

as the name of the organization of committees

plaintexts, ciphertexts, and keytexts. For a given

involved in the project for evaluation of crypto-

keytext the encryption algorithm will map a plain-

graphic techniques available for the Japanese e-

text to a (usually uniquely determined) ciphertext.

Government. The project itself is now referred

For the corresponding keytext, the decryption al-

to as CRYPTREC. From 2000 to 2002 the main

gorithm will map the ciphertext to the (usually

goal of CRYPTREC was to publish a list of recom-

uniquely determined) plaintext. The cryptosystem

mended ciphers for e-Government use. In March

may be performed by hand methods (“hand ci-

2003 the list was published and established as

pher”), by machine methods (“machine cipher”),

the guiding principle in the usage of cryptographic

or by software (see also Shannon™s model).

techniques in the Japanese government ministries

Plaintext: text in an open language that is com-

and agencies.

monly understood among a larger group of peo-

ple.

EVALUATION TARGETS: In the ¬scal years 2000

Ciphertext: text (“cryptogram”) in a secret lan-

and 2001, CRYPTREC Evaluation Commit-

guage that is understood only by few, autho-

tee called for the submission of the cryptographic

rized people, usually after decryption by hand or

techniques in order to compile a list of crypto-

machine.

graphic techniques that could be employed for e-

We mention two special properties: an endomor-

Government. In the public request for proposals,

phic cryptosystem is a cryptosystem with iden-

the CRYPTREC Evaluation Committee did not

tical plaintext and ciphertext space. Example:

impose any restrictions on the national origin or

{a, b, c, . . . , z} ’’ {a, b, c, . . . , z}. A pure cryptosys-

the organization of the applicant in order to pro-

tem is a cryptosystem that has the following prop-

vide an opportunity for impartial evaluation for

erty: whenever enciphering Ek with key k, followed

all applicants.

by deciphering D j with key j, followed by encipher-

The CRYPTREC Evaluation Committee

ing Ei with key i is performed, there is a key

speci¬ed several cryptographic techniques as

such that E has the same effect: Ei D jEk = E . In

“indispensable cryptographic techniques.” The

a pure cryptosystem, the mappings D jEk (“Ek fol-

CRYPTREC Evaluation Committee also evalu-

lowed by D j”) form a group, with Dk Ek being the

ated several cryptographic techniques as “speci¬c

identity.

evaluation” target ciphers for special reasons such

An endomorphic cryptosystem is pure if and

as requests from standardization organizations

only if its encipherings are closed under compo-

and the Law concerning Electronic Signatures

sition (Shannon), that is if its keys form a group,

and Certi¬cation.

the key group (see key).

Basically, the evaluation targets can be catego-

Friedrich L. Bauer rized into the following three types: “submitted

120 Cryptrec

cryptographic techniques,” “cryptographic tech- cryptographic techniques that satisfy the level of

niques for speci¬c evaluation,” and “indispensable security suf¬cient for e-Government usage. CRYP-

cryptographic techniques.” TREC has also performed software and hardware

implementation evaluations to measure the pro-

cessing speed and amount of system resources

Submitted Cryptographic Techniques

required.

In order to ensure that the technical evalu-

Cryptographic techniques in the categories of

ations are impartial and adequate, CRYPTREC

(1) digital signature, authentication, con¬dential-

has requested several specialists, besides its own

ity, and key agreement for public-key cryptogra-

members, to conduct evaluations (referred to as

phy, (2) 64-bit block ciphers, 128-bit block ciphers,

external evaluations).

and stream ciphers for symmetric-key cryptogra-

In order to ensure that evaluations are fair for

phy, and (3) hash functions and pseudorandom

all the cryptographic techniques in the same cat-

number generators were sought for evaluation.

egory, CRYPTREC has applied the same evalua-

The applicants who submitted techniques were

tion methods as much as possible to allow relative

asked to make their cryptographic techniques

comparisons.

procurable by the end of the ¬scal year 2002.

CRYPTREC Evaluation Committee received a to-

Evaluation Items

tal of 63 applications in both ¬scal years 2000 and

2001.

The evaluation in CRYPTREC progressed gradu-

ally and in parallel to get a good understanding

Indispensable Cryptographic Techniques

of algorithm properties and characteristics such

as security and performance; the evaluation also

In addition to the cryptographic techniques sub-

assessed how easy it was to develop ef¬cient im-

mitted by the applicants, the CRYPTREC Evalua-

plementations. There were four stages of the eval-

tion Committee has selected techniques that were

uation:

considered to be indispensable in the construc-

(1) Screening evaluation. Submitted documents

tion of e-Government systems. Such cryptographic

were studied to investigate whether the tar-

techniques must have either comparatively long

get cryptographic technique had any problems

track records of use and evaluation, or have a long

in the design concept, design policies, security,

history of usage. These targets were selected for

or implementation.

evaluation as “indispensable cryptographic tech-

(2) Full evaluation. The following items were in-

niques” whether or not an applicant submitted

vestigated: (a) whether known attacks are ap-

them.

plicable or not, (b) computational cost required

for a known attack to succeed, (c) validity of

Cryptographic Techniques for provable security, (d) validity of parameter/

Speci¬c Evaluation key generating methods, (e) selection of auxil-

iary functions and methods used to implement

“Cryptographic techniques for speci¬c evaluation” them in the scheme, (f) anticipated problems

are the cryptographic techniques that were eval- of submitted cryptographic techniques in real

uated by CRYPTREC on the basis of a special re- systems, and (g) whether any attack can be

quest, independent of their submission by an ap- mounted or not using the evaluators™ expertise.

plication and independent from a speci¬cation as The techniques were also compared with

“indispensable cryptographic techniques.” Crypto- other cryptographic techniques in order to as-

graphic techniques for speci¬c evaluation in the sess relative strengths and weaknesses.

¬scal years 2000 and 2001 are classi¬ed into (3) Software implementation evaluation. The com-

the following three categories: (1) cryptographic patibility and portability with respect to

techniques speci¬ed in Guidelines on the Law computing resources and environments was

concerning Electronic Signatures and Certi¬ca- veri¬ed by checking whether the software op-

tion Services, (2) cryptographic techniques used in erated as described in the submitted docu-

SSL3.0/TLS1.0, and (3) contributions to ISO/IEC ments in the following environments: (a) gen-

JTC1/SC27. eral PC environment, (b) most popular server

environment, and (c) high-performance, high-

EVALUATION AND SELECTION OF CRYPTO- end environment.

GRAPHIC TECHNIQUES: CRYPTREC has per- (4) Hardware implementation evaluation. It was

formed security evaluations in order to select investigated whether a third party could

Cryptrec 121

design the hardware using the submitted doc- of different input values with the same out-

put value is 2128 or more.

uments only.

(b) Widely used hash functions that have no

Evaluation Criteria security problems in realistic systems and

with a hash length of 160 bits or more are

selected.

The following criteria were set for evaluation

(4) Pseudorandom number generators: Pseudo-

of cryptographic techniques according to the

random number generators must satisfy all

categories.

the following conditions:

(1) Public-key cryptographic techniques. If a

(a) The statistical properties are close to that

public-key cryptographic technique has a solid

of a true random number. A past or future

track record of operation and evaluation over a

unknown output bit is hard to predict from

relatively long period of time and its speci¬ca-

the known output bit history.

tions cannot be changed easily from the stand-

(b) The seed size must be large enough to be

point of interoperability, the following condi-

secure against an exhaustive key search

tions must be satis¬ed:

of the system that uses a pseudorandom

(a) The cryptographic techniques must have

number generator.

been evaluated and researched thoroughly

(c) The statistical properties of pseudorandom

by a number of researchers.

number generators must pass a typical sta-

(b) No security problem has been reported in

tistical test suite for randomness such as

a realistic system.

SP800-22.

Relatively new public-key cryptographic

techniques were required to have at least

“provable security.” A comprehensive secu-

Requirements for the Draft of the

rity evaluation was carried out in addition

e-Government Recommended

to checking the provable security, including

Ciphers List

issues such as the validity of number theo-

retic problems, the method of selecting recom-

The CRYPTREC Advisory Committee has re-

mended parameters, and the method of using

quested the CRYPTREC Evaluation Committee to

auxiliary functions in a scheme.

evaluate the candidates for e-Government ciphers,

(2) Symmetric cryptography techniques. Sym-

cryptographic techniques that allow authentica-

metric-key cryptographic techniques must

tion, key agreement, con¬dentiality, and electronic

satisfy either of the following conditions:

signature functions in the e-Government sys-

(a) Even with the best attacking technique

tem, and prepare an e-Government recommended

available to date, a computational cost

ciphers list considering the following three

of 2128 or more (i.e., exhaustive search

points:

for a secret key) is required to break

(1) Select several cryptographic techniques with

symmetric-key cryptographic techniques.

suf¬cient security for use in the e-Government

It is necessary to show at the techniques

system (security guaranteed roughly 10

are secure against typical cryptanalytic at-

years).

tacks such as differential and linear crypt-

(2) Select for each category at least one crypto-

analysis.

graphic technique that is being-incorporated

(b) Widely used symmetric-key cryptographic

or likely to be incorporated in commercial soft-

techniques that have been evaluated in de-

ware (to be used by the general public).

tails and have no security problems in a

(3) Con¬rm the speci¬cations of cryptographic

realistic system are selected. In this case,

techniques recommended for e-Government to

a computational cost of 2100 or more is re-

guarantee that ciphers satisfying these speci-

quired to break them.

¬cations can be procured.

(3) Hash functions. Hash functions must satisfy

either of the following conditions:

RECOMMENDED CIPHERS

(a) Even with the best attacking technique E-GOVERNMENT

LIST: As a three-year comprehensive project, the

available to date, the computational cost

to ¬nd the input value for a speci¬c output “e-Government recommended ciphers list

value is not less than the computational (draft)” authored by the CRYPTREC Evaluation

cost required for an exhaustive search. Committee was submitted to the CRYPTREC

Also, even if the best attacking technique is Advisory Committee for review. Then, MPHPT

used, the computational cost to ¬nd a pair and METI invited comments from the general

122 Cryptrec

Table 1. e-Government recommended ciphers list (draft) (prepared in November 2002)

Category Name

Public-key Signature DSA

ciphers ECDSA

RSASSA-PKCS1-v1 5

RSA-PSS

Con¬dentiality RSA-OAEP

RSAES-PKCS1-v1 51

Key agreement DH

ECDH

PSEC-KEM2

64-bit block ciphers3

Symmetric-key CIPHERUNICORN-E

ciphers Hierocrypt-L1

MISTY1

3-key Triple DES4

128-bit block ciphers AES

Camellia

CIPHERUNICORN-A

Hierocrypt-3

SC2000

Stream ciphers MUGI

MULTI-S01

128-bit RC45

RIPEMD-1606

Others Hash function

SHA-16

SHA-256

SHA-384

SHA-512

Pseudorandom number PRNG based on SHA-1 in ANSI X9.42-2001 Annex C.1

generator7 PRNG based on SHA-1 for general purpose in FIPS 186-2

(+ change notice 1) Appendix 3.1

PRNG based on SHA-1 for general purpose in FIPS 186-2

(+ change notice 1) revised Appendix 3.1

Notes:

1

Use of this is permitted for the time being because it was used in SSL3.0/TLS1.0.

2

On the assumption that this is used in the KEM (Key Encapsulation Mechanism)-DEM (Data Encapsulation

Mechanism) construction.

3

When constructing a new e-Government system, 128-bit block ciphers are preferable if possible.

4

Using 3-key Triple DES is permitted for the time being under the following conditions:

(1) It is speci¬ed as FIPS 46-3.

(2) It is positioned as the de facto standard.

5

It is assumed that the 128-bit RC4 will be used only in SSL3.0/TLS(1.0 or later). If any other cipher listed

above is available, it should be used instead.

6

If any hash functions with a longer hash value are available when constructing a new e-Government system,

it is preferable that a 256-bit (or more) hash function be selected. However, this does not apply in cases where

the hash function to be used has already been designated according to the public-key cryptographic

speci¬cations.

7

Since pseudorandom number generators do not require interoperability due to their usage characteristics, no

problems will be created by using a cryptographically secure pseudorandom number generating algorithm.

Therefore, these algorithms are examples.

public. Finally, the draft was authorized as the remind uses that some cryptographic techniques

“e-Government recommended ciphers list”. require in employing them for e-Government ap-

In Table 1, we show the e-Government rec- plications. For more details, the reader is referred

ommended ciphers list. The notes are added to to the CRYPTREC Web site [1].

Cut-and-choose protocol 123

OTHER ACTIVITIES CUT-AND-CHOOSE

PROTOCOL

Revision of Guidelines on the Law

Concerning Electronic Signatures

and Certi¬cation Services CUT-AND-CHOOSE PROTOCOLS: A cut-and-

choose protocol is a two-party protocol in which

Guidelines on the Law concerning Electronic Sig- one party tries to convince another party that

natures and Certi¬cation Services were revised some data he sent to the former was honestly con-

corresponding to the CRYPTREC evaluation re- structed according to an agreed upon method. Im-

sults in the ¬scal year 2001. portant examples of cut-and-choose protocols are

interactive proofs [4], interactive arguments [1],

zero-knowledge protocols [1, 3, 4] and witness in-

SSL/TLS Evaluation Report distinguishable and witness hiding protocols [2]

for proving knowledge of a piece of information

CRYPTREC evaluated the security of SSL/TLS that is computationally hard to ¬nd. Such a pro-

(see Secure Socket Layer (SLS) and Transport tocol usually carries a small probability that it is

Layer Security (TLS)) and reported as follows: successful despite the fact that the desired prop-

SSL/TLS is secure against all known attacks. Us- erty is not satis¬ed.

ing SSL/TLS, one needs to ensure that patches The very ¬rst instance of such a cut-and-choose

are applied and that parameters are properly se- protocol is found in the protocol of Rabin [5] where

lected. SSL/TLS is considered to offer an adequate the cut-and-choose concept is used to convince a

security level for practical use. The functionality party that the other party sent him an integer n

of TLS is still being extended. New security weak- that is a product of two primes p, q, each of which

nesses can emerge as a result of these extensions. is congruent to 1 modulo 4. Note that this protocol

Therefore, it is necessary to monitor the status was NOT zero-knowledge.

and progress of TLS and to keep investigating its The expression cut-and-choose was later intro-

security. duced by Chaum [1] in analogy to a popular cake

sharing problem: given a complete cake to be

shared among two parties distrusting each other

Publicizing External Evaluation Reports

(for reasons of serious appetite). A fair way for

them to share the cake is to have one of them cut

CRYPTREC considers it important to publicize

the cake in two equal shares, and let the other one

the cryptographic technique evaluation results in

choose his favourite share. This solution guaran-

order to improve the reliability of security evalu-

tees that it is in the former™s best interest to cut

ations. All external evaluation reports that were

the shares as evenly as possible.

compiled as a part of the evaluation activities of

CRYPTREC are available on the CRYPTREC Web

site [1].

Monitoring and Other Evaluations

After publishing the e-Government recommended

ciphers list, the main responsibility of CRYPTREC

has moved to monitoring the security of crypto-

graphic techniques in the list. CRYPTREC also

has started the evaluation of cryptographic mod-

Claude Cr´ peau

e

ules and protocols.

References

Hideki Imai

Atsuhiro Yamagishi

[1] Brassard, G., D. Chaum, and C. Cr´ peau (1988).

e

“Minimum disclosure proofs of knowledge.” JCSS,

Reference 37, 156“189.

[2] Feige, U. and A. Shamir (1990). “Witness indis-

[1] CRYPTREC Web site, http://www.shiba.tao.go.jp/ tinguishable and witness hiding protocols.” Pro-

kenkyu/CRYPTREC/index.html and http://www. ceedings of the 22nd Annual ACM Symposium on

ipa.go.jp/security/enc/CRYPTREC/index.html the Theory of Computing, Baltimore, MD, May

124 Cyclic codes

est distance between different codewords; it de-

1990, ed. Baruch Awerbuch. ACM Press, New York,

416“426. termines the error correcting capabilities of C. In-

deed, C can correct t = (d ’ 1)/2 errors. Since

[3] Goldreich, Oded, Silvio Micali, and Avi Wigderson

(1991). “Proofs that yield nothing but their validity we focus on cyclic codes and on the most useful of

or all languages in NP have zero-knowledge proof them, the alphabet A will be a ¬nite ¬eld Fq of

systems.” Journal of the Association for Computing

characteristic 2, i.e., q = 2e for some integer e ≥ 1.

Machinery, 38 (3), 691“729.

Moreover, the length of the codes will be generally

[4] Goldwasser, Sha¬, Silvio Micali, and Charles Rack-

2m ’ 1, where e divides m; these codes are said

off (1989). “The knowledge complexity of interactive

primitive.

proof systems.” SIAM Journal on Computing, 18 (1),

186“208.

n

DEFINITION 1. Consider the linear space Fq of all

[5] Rabin, M.O. (1977). “Digitalized signatures.” Foun-

n-tuples over the ¬nite ¬eld Fq . An [n, k, d] linear

dations of Secure Computation. Papers presented

n

at a 3 day workshop held at Georgia Institute of code C over Fq is a k-dimensional subspace of Fq

Technology, Atlanta, October 1977, eds. Richard A. with minimum distance d.

DeMillo et al. Academic Press, New York, 155“166.

By de¬nition, a k-dimensional linear code C is

fully determined by a basis over Fq . When we put

the k vectors of a basis as rows in a k — n matrix G,

CYCLIC CODES we get a generator matrix of C. Indeed, C is given

by {avG | a ∈ Fq }.

k

INTRODUCTION: For a general presentation of The Hamming weight wt(u) of any word u in

cyclic codes, our main reference is the Handbook n

Fq is the number of its nonzero coordinates. Note

of Coding Theory, especially the ¬rst chapter [4] that wt(u) = d(u, 0). Obviously, for linear codes,

(but also Chapters 11, 13, 14, and 19). the minimum distance is exactly the minimum

Cyclic codes were introduced as a particular weight of nonzero codewords.

practical class of error-correcting codes (ECC).

Codes are devoted to the following fundamental PROPOSITION 1. Let C be any [n, k, d] linear code

problem: how to determine what message has been over Fq . Then

sent when only an approximation is received, due

to a noisy communication channel. Cyclic codes d = min{wt(c) | c ∈ C \ {0}}.

belong to the class of block codes since here all

messages have the same length k. Each of them The dual code of C is the [n, n ’ k] linear code:

is encoded into a codeword of length n = k + r. A

C ⊥ = {y ∈ Fq | c · y = 0, for all c ∈ C},

t-error-correcting code is a well-chosen subset C of n

An . Its elements are called codewords and have the

property that each pair of them differs in at least where “·” denotes the ordinary inner product of

2t + 1 coordinates. If the noisy channel generates n’1

vectors: c · y = i=0 ci yi . An (n ’ k) — n generator

matrix of C ⊥ is called a parity check matrix H for

not more than t errors during one transmission,

C. Note that C = {y ∈ Fq | HyT = 0T }.

the received vector will still lie closer to the orig- n

inally transmitted codeword than any other code- When studying cyclic codes, it is convenient

word. This means that code C is able to correct t to view the labeling of the coordinate posi-

tions 0, 1, . . . , n ’ 1 as integers modulo n (see

positions in each codeword.

A codeword will be denoted by modular arithmetic). In other words, viewing

these coordinate positions as forming a cycle with

c = (c0 , c1 , . . . , cn’1 ), ci ∈ A.

n ’ 1 being followed by 0.

When the encoder is systematic, the ¬rst k sym-

bols are called information symbols (they are the DEFINITION 2. A linear code C of length n over

message) and the last r symbols are the redun- Fq is cyclic if and only if it satis¬es for all c =

dancy symbols (added to help recover the mes- c0 · · · cn’2 cn’1 in C:

sage if errors occur). We consider here linear codes,

meaning that A is a ¬nite ¬eld and that C is a (c0 , . . . , cn’2 , cn’1 ) ∈ C =’ (cn’1 , c0 , . . . , cn’2 ) ∈ C.

k-dimensional linear subspace of An .

The vector cn’1 c0 · · · cn’2 is obtained from c by the

The (Hamming) distance between two code-

cyclic shift of coordinates i ’ i + 1.

words, c and c , is de¬ned by:

d(c, c ) = card {i ∈ [0, n ’ 1] | ci = ci }.

EXAMPLE 1. The generator matrix G below de¬nes

The minimum distance d of a code C is the small- an [8, 4, 2] binary cyclic code (length 8, dimension

Cyclic codes 125

4, and minimum weight 2): where m is the smallest positive integer such that

n divides q m ’ 1 (so ± ∈ Fq m ).

®

The minimal polynomial of ± s over Fq is

1 0 0 0 1 0 0 0

0 0

1 0 0 0 1 0

G= .

°0 0» M±s (x) = (x ’ ± i ),

0 1 0 0 0 1

i∈c (s)

0 0 0 1 0 0 0 1

where the ± i , i ∈ c (s), are called the conjugates

Cyclic codes are some of the most useful

of ± s .

codes known. The involvement of Reed“Solomon

(RS) codes and of Bose“Chaudhury“Hocquen-

If ω is a primitive element of Fq m , then one can

ghem (BCH) codes in a number of applications is

take ± = ω(q ’1)/n . Note that M±s (x) is a polynomial

m

well known. On the other hand, the Golay codes

over Fq while ± ∈ Fq m .

and the Reed“Muller (RM) codes, which are fun-

damental linear codes, can be represented as cyclic

THEOREM 1. Let C be a nonzero cyclic code of

codes.

length n over Fq . There exists a polynomial g(x) ∈

C, called the generator polynomial of C, with the

CONSTRUCTIVE DEFINITION: It seems dif¬cult following properties:

to construct a cyclic code C by means of De¬nition (i) g(x) is the unique monic polynomial of mini-

2. So, useful de¬nitions of cyclic codes are now con- mum degree in C;

sidered. (ii) g(x) is a generator of the ideal C in Rn :

An ef¬cient de¬nition is established by identify-

ing each vector c = (c0 , c1 , . . . , cn’1 ) with the poly- C = g(x) = {a(x)g(x) (mod x n ’ 1) |

nomial c(x) = c0 + c1 x + · · · + cn’1 x n’1 . The fact a(x) ∈ Fq [x]};

that C is invariant under a cyclic shift is then ex-

(iii) g(x) divides x n ’ 1.

pressed as follows:

Let r = deg(g), and let g(x) = r gi xi where

i=0

c(x) ∈ C =’ xc(x) (mod x n ’ 1) ∈ C. gr = 1. Then

(iv) the dimension of C is k = n ’ r ; moreover the

Thus the proper context for studying cyclic codes

polynomials

of length n over Fq is the residue class ring

g(x), xg(x), . . . , x k’1 g(x)

Rn = Fq [X]/(x n ’ 1).

It is well known that Rn is a principal ideal ring. form a basis of C. The corresponding generator

This means that any ideal I in Rn is generated matrix is given by:

by a single element g in I, i.e., I = {ag | a ∈ Rn }. ®

g0 g1 · · · gn’k ···

(An ideal in Rn is a subset I of Rn satisfying the 0 0

0 g0 g1 0

· · · gn’k

properties: (1) for all i1 , i2 in I also i1 ’ i1 ∈ I and

G= . . .

(2) for any i ∈ I and a ∈ Rn also ai ∈ I.) .. .. ..

°. .»

. . .

. .

An alternative de¬nition of a cyclic code can now

··· ···

0 0 g0 g1 gn’k

be given.

(v) Let ± be a primitive nth root of unity in some

DEFINITION 3. A cyclic code C of length n over Fq extension ¬eld of Fq . Denote by M±s the mini-

is a principal ideal of the ring Rn . The codewords mal polynomial of ± s over Fq ; then

are polynomials in Fq [x] of degree less than n. Mul-

tiplication is carried out modulo x n ’ 1. g(x) = M±s (x)

s∈I

The next theorem, which is given in [4, Theorem

where I is a subset of representatives of the

5.2], allows to determine the main parameters of

q-cyclotomic cosets modulo n.

any cyclic code of Rn . We ¬rst recall some basic

de¬nitions.

The dual code of any cyclic code is cyclic too. The

description of C ⊥ can be directly obtained from

DEFINITION 4. Let ± be a primitive nth root of

Theorem 1.

unity in some extension ¬eld of Fq . This means

that 1, ±, . . . , ± n’1 are all different and ± n = 1. For

COROLLARY 1. Let C be a cyclic code of length n

each integer s with 0 ¤ s < n, denote by c (s) the

over Fq , with generator polynomial g(x). Let h(x)

q-cyclotomic coset of s modulo n:

denote the parity check polynomial of C, de¬ned by

c (s) = {s, qs, . . . , q m’1 s (mod n)}, x n ’ 1 = h(x)g(x). Then the generator polynomial

126 Cyclic codes

of C ⊥ is the polynomial SOME CYCLIC CODES: From now on q = 2e and

n = q m ’ 1. Let C be any cyclic code of length n

k

x

h(x ’1 ),

h(x) = where k = n ’ deg(g). over Fq with generator polynomial g(x). The roots

h0 of g(x) are called the zeros of the cyclic code C.

Thus, the code C is fully de¬ned by means of its

EXAMPLE 2. Construction of the binary Hamming

zero™s set; this leads to the classical de¬nition of

code of length n = 15.

the BCH codes and of other important families.

x 15 ’ 1 = (x 4 + x 3 + 1)(x 4 + x + 1)(x 4 + x 3

DEFINITION 5. Let q = 2 and n = 2m ’ 1; denote

+ x 2 + x + 1)(x + 1)(x 2 + x + 1).

by ± a primitive nth root of unity in F2m . Let δ be

Since x 4 + x + 1 is a primitive polynomial (mean- an integer with 2 ¤ δ ¤ n.

ing that its zeros are primitive elements), its root The binary BCH code of length n and de-

± is a generator of the cyclic group of the ¬eld F16 . signed distance δ is the cyclic code with zero™s set:

±, ± 2 , . . . , ± δ’1 and their conjuguates. In other

The polynomial x 4 + x + 1 is the minimal polyno-

mial of ± and has ± and its conjugates as zeros. words, the generator polynomial of this code is

Consider the cyclic code C with generator polyno-

g(x) = l cm{M± (x), M±2 (x), . . . , M±δ’1 (x)}.

mial:

g(x) = (x ’ ±)(x ’ ± 2 )(x ’ ± 4 )(x ’ ± 8 )

EXAMPLE 3. Binary BCH codes of length 15. As in

= x 4 + x + 1.

Example 2, we denote by ± any root of the primi-

The dimension of C is 15 ’ deg(g) = 11. Thus the tive polynomial x 4 + x + 1. Now the factorization

of x 15 ’ 1 into minimal polynomials is as follows:

code C is a [15, 11, 3] cyclic code. The minimum

distance of C is exactly 3 since wt(g) = 3 and no

x 15 ’ 1 = (x ’ 1) (x 4 + x + 1) (x 4 + x 3 + x 2 + x + 1)

smaller weight can appear, as can be checked us-

ing a generator matrix G of C. According to Theo- M(±) M(± 3 )

rem 1, G is an 11 — 15 binary matrix whose lines (x 2 + x + 1) (x 4 + x 3 + 1) .

are g(x)

M(± 5 ) M(± 7 )

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

xxxxxxxxxxx x x x x

There are three nontrivial BCH codes, whose

g(x) 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0

zero™s sets Sδ are as follows:

r S3 = {± i | i = 1, 2, 4, 8} for the [15, 11, 3] BCH

and the 10 shifts of g(x). The parity check polyno-

mial of C and the generator polynomial of C ⊥ are code;

r S5 = S3 ∪ {± i | i = 3, 6, 9, 12} for the [15, 7, 5]

given by:

BCH code;

r

x 15 ’ 1

S7 = S5 ∪ {± i | i = 5, 10} for the [15, 5, 7] BCH

h(x) =

x4 + x + 1 code.

= x 11 + x 8 + x 7 + x 5 + x 3 + x 2 + x + 1. For these codes, the designed distance δ is exactly

the minimum distance; this property does not hold

resp.

for any BCH code.

11

h(x) = h11’i xi

DEFINITION 6. A Reed“Solomon code over Fq is a

i=0

BCH code of length n = q ’ 1.

=x + x 10 + x 9 + x 8 + x 6 + x 4 + x 3 + 1.

11

We then obtain a parity check matrix for C: RS codes appear in several cryptosystems. They

determine, for instance, some secret-sharing sch-

x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x 10 x 11 x 12 x 13 x 14

emes [3]. It is important to note that for RS codes,

1 0 0 1 1 0 1 0 1 1 1 1 0 0 0

the designed distance is exactly the minimum

0.

0 1 0 0 1 1 0 1 0 1 1 1 1 0

distance. Moreover, the RS code with designed dis-

0 0 1 0 0 1 1 0 1 0 1 1 1 1 0

tance δ is an [n, k, δ] code with k = n ’ δ + 1. Since

0 0 0 1 0 0 1 1 0 1 0 1 1 1 1

this k attains the maximum value by the Single-

We explained here, by means of an example, the ton bound (see [4]), one says that RS codes are

general de¬nition of the binary Hamming code of maximum distance separable (MDS) code.

length 2m ’ 1. It is a code whose parity check ma-

DEFINITION 7. Let ± be a primitive root of F2m .

trix has as columns all the nonzero vectors of Fm .

2

It is a [2m ’ 1, 2m ’ m ’ 1, 3] code. Any integer s ∈ [0, 2m ’ 1] can be identi¬ed by its

Cyclic codes 127

binary expansion in Fm : EXAMPLE 4. Consider any binary cyclic code of

2

length n = 2m ’ 1 whose generator polynomial

m’1

is the product of two minimal polynomials,

s= si 2i , si ∈ {0, 1} =’ s = (s0 , . . . , sm’1 ).

say M±r (x)M±s (x). These codes are said to be

i=0

cyclic codes with two zeros and usually denoted

The cyclic Reed“Muller code of length 2m ’ 1 and by Cr,s .

order r , usually denoted by R— (r, m), is the binary Now assume that r = 1 and gcd(s, 2m ’ 1) = 1.

cyclic code with zero set: Then C1,s is an [n, 2m, d] cyclic code; the dual

Sr = { ± s | 1 ¤ wt(s) < m ’ r }, of C1,s is a cyclic code which has two nonzeros

only: ± n’1 and ± n’s (apart from their conjugates).

where wt(s) is the Hamming weight of s. ⊥

According to (1), C1,s is the set of binary codewords

of length n de¬ned as follows: each pair (a, b) of

Note that if one extends all codewords in the

elements of F2m provides the ordered sequence of

cyclic Reed“Muller code above with an overall-

values

parity check symbol, one obtains the regular

x ∈ {1, ±, . . . , ± n’1 } ’’ Tr(ax + bx s ),

Reed“Muller code.

Binary cyclic codes are related to the study

where the Trace function Tr is de¬ned by Tr(β) =

and the construction of cryptographic primitives, m’1

β + β 2 + · · · + β 2 . The power function x ’ x s is

mainly through Reed“Muller codes because of the

a permutation on F2m . It is said to be almost per-

large ¬eld of applications of Boolean functions and

fect nonlinear [1] when C1,s has minimum dis-

binary sequences in cryptography. They play a

tance 5. It is said to be an AB function when the

role in the study of cryptographic mapping on ¬- ⊥

nonzero weights of codewords of C1,s are either

nite ¬elds in general. One well-known application

2m’1 or 2m’1 ± 2(m’1)/2 ; this is possible for odd m

is the construction of almost bent (AB) mappings

only.

(see nonlinearity of Boolean functions), which re-

sist both differential and linear cryptanalysis [1,2]

Pascale Charpin

(see next example). These connections are more

explicit when using the trace representation of bi-

nary codewords of length n = 2m ’ 1. We now la-

References

bel the coordinate positions by ± 0 , ± 1 , . . . , ± n’1 ,

where ± is a primitive nth root of unity. Let c(x)

[1] Canteaut, A., P. Charpin, and H. Dobbertin (1999).

be any codeword of some binary cyclic code C of

“A new characterization of almost bent functions.”

length n. De¬ne Fast Software Encryption (FSE6), Lecture Notes

n’1 in Computer Science, vol. 1636, ed. L.R. Knudsen.

Tc (x) = c(± n’s )x s . (1) Springer-Verlag, Berlin, 186“200.

s=0 [2] Carlet, C., P. Charpin, and V. Zinoviev (1998).

“Codes, bent functions and permutations suitable

This commonly known Fourier transform of c is

for DES-like cryptosystems.” Designs Codes and

called the Mattson“Solomon polynomial of c in al-

Cryptography, 15 (2), 125“156.

gebraic coding theory. It follows that Tc (± j) = c j

[3] McEliece, R.J. and D.V. Sarwarte (1981). “On shar-

and Tc (x) is a sum of traces from some sub¬elds of

ing secrets and Reed“Solomon codes.” Comm. ACM,

F2m to F2 . 24, 583“584.

The mapping x ’ Tc (x) is a Boolean function. [4] Pless, V.S., W.C. Huffman, and R.A. Brualdi (1998).

On the other hand, any binary sequence of pe- “An introduction to algebraic codes.” Handbook of

riod n can be represented in this way (see entries Coding Theory, Part 1: Algebraic Coding. Elsevier,

Boolean functions and Sequences). Amsterdam, The Netherlands, Chapter 1.