**GLOSSARY.HTM**- Posted Dec 21, 1999
Crypto Glossary and Dictionary of Technical Cryptography

- SHA-256 |
`baf7b4cb94f88210381fcdfb4698d853b122f3e1540c86a815295fbc9142bef5`

- Download | Favorite | View

`<HTML>`

<HEAD>

<TITLE>Ritter's Crypto Glossary and Dictionary of Technical Cryptography</TITLE>

<META NAME = "DESCRIPTION"

CONTENT = "Hyperlinked definitions and discussions of many

cryptographic, mathematic, logic, statistics, and electronics terms

used in cipher construction and analysis.

A Ciphers By Ritter page.">

<META NAME = "KEYWORDS"

CONTENT = "cipher,crypto,cryptography,cryptographic,cryptology,

definition,dictionary,encryption,electronics,explain,explained,

explanation,glossary,information,learning,mathematics,statistics,

understanding">

</HEAD>

<BODY>

<H1 ALIGN = CENTER>Ritter's Crypto Glossary <I>and</I> <BR>

Dictionary of Technical Cryptography</H1>

<P><H2 ALIGN = CENTER>Technical Cryptographic Terms Explained</H2>

<BLOCKQUOTE><BIG><I>

Hyperlinked definitions and discussions of many cryptographic,

mathematic, logic, statistics, and electronics terms used in

cipher construction and analysis.</I></BIG>

</BLOCKQUOTE>

<H2 ALIGN = CENTER>A <A HREF="http://www.io.com/~ritter/"><I>Ciphers By Ritter</I></A> Page</H2>

<BR><H2 ALIGN = CENTER>Terry Ritter</H2>

<H2 ALIGN = CENTER>Current Edition: 1999 Jan 19</H2>

For a basic introduction to cryptography, see

<A HREF = "http://www.io.com/~ritter/LEARNING.HTM">Learning About Cryptography</A>.

Please feel free to send comments and suggestions for improvement to:

<A HREF = "mailto:ritter@io.com"> ritter@io.com</A>.

You may wish to help support this work by patronizing

<A TARGET = "Bshop"

HREF = "http://www.io.com/~ritter/BOOKSHOP.HTM">Ritter's Crypto Bookshop</A>.

<P><HR><H2>Contents</H2>

<DL>

<DT><BIG>A</BIG>

<DD>

<A HREF = "#Absolute">Absolute</A>,

<A HREF = "#AC">AC</A>,

<A HREF = "#AdditiveCombiner"><NOBR>Additive Combiner</NOBR></A>,

<A HREF = "#AdditiveRNG"><NOBR>Additive RNG</NOBR></A>,

<A HREF = "#Affine">Affine</A>,

<A HREF = "#AffineBooleanFunction"><NOBR>Affine Boolean Function</NOBR></A>,

<A HREF = "#Alphabet">Alphabet</A>,

<A HREF = "#AlternativeHypothesis"><NOBR>Alternative Hypothesis</NOBR></A>,

<A HREF = "#Amplifier">Amplifier</A>,

<A HREF = "#Amplitude">Amplitude</A>,

<A HREF = "#Analog">Analog</A>,

<A HREF = "#AND">AND</A>,

<A HREF = "#ASCII">ASCII</A>,

<A HREF = "#Associative">Associative</A>,

<A HREF = "#AsymmetricCipher"><NOBR>Asymmetric Cipher</NOBR></A>,

<A HREF = "#Attack">Attack</A>,

<A HREF = "#AugmentedRepetitions"><NOBR>Augmented Repetitions</NOBR></A>,

<A HREF = "#Authentication">Authentication</A>,

<A HREF = "#AuthenticatingBlockCipher"><NOBR>Authenticating Block Cipher</NOBR></A>,

<A HREF = "#Autokey">Autokey</A>,

<A HREF = "#Avalanche">Avalanche</A>,

<A HREF = "#AvalancheEffect"><NOBR>Avalanche Effect</NOBR></A>

<DT><BIG>B</BIG>

<DD>

<A HREF = "#BackDoor"><NOBR>Back Door</NOBR></A>,

<A HREF = "#Balance">Balance</A>,

<A HREF = "#BalancedBlockMixer"><NOBR>Balanced Block Mixer</NOBR></A>,

<A HREF = "#BalancedBlockMixing"><NOBR>Balanced Block Mixing</NOBR></A>,

<A HREF = "#BalancedCombiner"><NOBR>Balanced Combiner</NOBR></A>,

<A HREF = "#Base64">Base-64</A>,

<A HREF = "#Bel">Bel</A>,

<A HREF = "#BentFunction"><NOBR>Bent Function</NOBR></A>,

<A HREF = "#BernoulliTrials"><NOBR>Bernoulli Trials</NOBR></A>,

<A HREF = "#Bijective">Bijective</A>,

<A HREF = "#Binary">Binary</A>,

<A HREF = "#BinomialDistribution"><NOBR>Binomial Distribution</NOBR></A>,

<A HREF = "#BirthdayAttack"><NOBR>Birthday Attack</NOBR></A>,

<A HREF = "#BirthdayParadox"><NOBR>Birthday Paradox</NOBR></A>,

<A HREF = "#Bit">Bit</A>,

<A HREF = "#Block">Block</A>,

<A HREF = "#BlockCipher"><NOBR>Block Cipher</NOBR></A>,

<A HREF = "#BlockSize"><NOBR>Block Size</NOBR></A>,

<A HREF = "#Boolean">Boolean</A>,

<A HREF = "#BooleanFunction"><NOBR>Boolean Function</NOBR></A>,

<A HREF = "#BooleanFunctionNonlinearity"><NOBR>Boolean Function Nonlinearity</NOBR></A>,

<A HREF = "#BooleanLogic"><NOBR>Boolean Logic</NOBR></A>,

<A HREF = "#BooleanMapping"><NOBR>Boolean Mapping</NOBR></A>,

<A HREF = "#Break">Break</A>,

<A HREF = "#BruteForceAttack"><NOBR>Brute Force Attack</NOBR></A>,

<A HREF = "#Bug">Bug</A>,

<A HREF = "#Byte">Byte</A>

<DT><BIG>C</BIG>

<DD>

<A HREF = "#Capacitor">Capacitor</A>,

<A HREF = "#CBC">CBC</A>,

<A HREF = "#cdf">c.d.f.</A>,

<A HREF = "#CFB">CFB</A>,

<A HREF = "#Chain">Chain</A>,

<A HREF = "#Chaos">Chaos</A>,

<A HREF = "#ChiSquare">Chi-Square</A>,

<A HREF = "#Cipher">Cipher</A>,

<A HREF = "#CipherTaxonomy"><NOBR>Cipher Taxonomy</NOBR></A>,

<A HREF = "#Ciphering">Ciphering</A>,

<A HREF = "#Ciphertext">Ciphertext</A>,

<A HREF = "#CiphertextExpansion"><NOBR>Ciphertext Expansion</NOBR></A>,

<A HREF = "#Ciphony">Ciphony</A>,

<A HREF = "#Circuit">Circuit</A>,

<A HREF = "#Clock">Clock</A>,

<A HREF = "#Closed">Closed</A>,

<A HREF = "#Code">Code</A>,

<A HREF = "#Codebook">Codebook</A>,

<A HREF = "#CodebookAttack"><NOBR>Codebook Attack</NOBR></A>,

<A HREF = "#Combination">Combination</A>,

<A HREF = "#Combinatoric">Combinatoric</A>,

<A HREF = "#Combiner">Combiner</A>,

<A HREF = "#Commutative">Commutative</A>,

<A HREF = "#Complete">Complete</A>,

<A HREF = "#Component">Component</A>,

<A HREF = "#Computer">Computer</A>,

<A HREF = "#Conductor">Conductor</A>,

<A HREF = "#Confusion">Confusion</A>,

<A HREF = "#ConfusionSequence"><NOBR>Confusion Sequence</NOBR></A>,

<A HREF = "#Congruence">Congruence</A>,

<A HREF = "#Contextual">Contextual</A>,

<A HREF = "#ConventionalCipher"><NOBR>Conventional Cipher</NOBR></A>,

<A HREF = "#Convolution">Convolution</A>,

<A HREF = "#Correlation">Correlation</A>,

<A HREF = "#CorrelationCoefficient"><NOBR>Correlation Coefficient</NOBR></A>,

<A HREF = "#CRC">CRC</A>,

<A HREF = "#Cryptanalysis">Cryptanalysis</A>,

<A HREF = "#Cryptanalyst">Cryptanalyst</A>,

<A HREF = "#Cryptographer">Cryptographer</A>,

<A HREF = "#CryptographicMechanism"><NOBR>Cryptographic Mechanism</NOBR></A>,

<A HREF = "#Cryptography">Cryptography</A>,

<A HREF = "#CryptographyWar"><NOBR>Cryptography War</NOBR></A>,

<A HREF = "#Cryptology">Cryptology</A>,

<A HREF = "#Current">Current</A>

<DT><BIG>D</BIG>

<DD>

<A HREF = "#dB">dB</A>,

<A HREF = "#DC">DC</A>,

<A HREF = "#Debug">Debug</A>,

<A HREF = "#Decipher">Decipher</A>,

<A HREF = "#Decryption">Decryption</A>,

<A HREF = "#DeductiveReasoning"><NOBR>Deductive Reasoning</NOBR></A>,

<A HREF = "#DefinedPlaintextAttack"><NOBR>Defined Plaintext Attack</NOBR></A>,

<A HREF = "#DegreesOfFreedom"><NOBR>Degrees of Freedom</NOBR></A>,

<A HREF = "#DES">DES</A>,

<A HREF = "#Decibel">Decibel</A>,

<A HREF = "#Decimal">Decimal</A>,

<A HREF = "#DesignStrength"><NOBR>Design Strength</NOBR></A>,

<A HREF = "#Deterministic">Deterministic</A>,

<A HREF = "#DictionaryAttack"><NOBR>Dictionary Attack</NOBR></A>,

<A HREF = "#DifferentialCryptanalysis"><NOBR>Differential Cryptanalysis</NOBR></A>,

<A HREF = "#Diffusion">Diffusion</A>,

<A HREF = "#Digital">Digital</A>,

<A HREF = "#Diode">Diode</A>,

<A HREF = "#Distribution">Distribution</A>,

<A HREF = "#Distributive">Distributive</A>,

<A HREF = "#DivideAndConquer"><NOBR>Divide and Conquer</NOBR></A>,

<A HREF = "#Domain">Domain</A>,

<A HREF = "#Dyadic">Dyadic</A>,

<A HREF = "#DynamicKeying"><NOBR>Dynamic Keying</NOBR></A>,

<A HREF = "#DynamicSubstitutionCombiner"><NOBR>Dynamic Substitution Combiner</NOBR></A>,

<A HREF = "#DynamicTransposition"><NOBR>Dynamic Transposition</NOBR></A>

<DT><BIG>E</BIG>

<DD>

<A HREF = "#ECB">ECB</A>,

<A HREF = "#ElectricField"><NOBR>Electric Field</NOBR></A>,

<A HREF = "#ElectromagneticField"><NOBR>Electromagnetic Field</NOBR></A>,

<A HREF = "#Electronic">Electronic</A>,

<A HREF = "#Encipher">Encipher</A>,

<A HREF = "#Encryption">Encryption</A>,

<A HREF = "#Entropy">Entropy</A>,

<A HREF = "#Ergodic">Ergodic</A>,

<A HREF = "#Extractor">Extractor</A>,

<A HREF = "#ExclusiveOR">Exclusive-OR</A>

<DT><BIG>F</BIG>

<DD>

<A HREF = "#Factorial">Factorial</A>,

<A HREF = "#Fallacy">Fallacy</A>,

<A HREF = "#FastWalshTransform"><NOBR>Fast Walsh Transform</NOBR></A>,

<A HREF = "#FCSR">FCSR</A>,

<A HREF = "#FeistelConstruction"><NOBR>Feistel Construction</NOBR></A>,

<A HREF = "#FencedDES">Fenced DES</A>,

<A HREF = "#Fencing">Fencing</A>,

<A HREF = "#FencingLayer"><NOBR>Fencing Layer</NOBR></A>,

<A HREF = "#FFT">FFT</A>,

<A HREF = "#Field">Field</A>,

<A HREF = "#FiniteField"><NOBR>Finite Field</NOBR></A>,

<A HREF = "#FlipFlop"><NOBR>Flip-Flop</NOBR></A>,

<A HREF = "#FourierSeries"><NOBR>Fourier Series</NOBR></A>,

<A HREF = "#FourierTheorem"><NOBR>Fourier Theorem</NOBR></A>,

<A HREF = "#FourierTransform"><NOBR>Fourier Transform</NOBR></A>,

<A HREF = "#Frequency">Frequency</A>,

<A HREF = "#Function">Function</A>,

<A HREF = "#FWT">FWT</A>

<DT><BIG>G</BIG>

<DD>

<A HREF = "#Gain">Gain</A>,

<A HREF = "#GaloisField">Galois Field</A>,

<A HREF = "#Gate">Gate</A>,

<A HREF = "#GF2n">GF 2<SUP>n</SUP></A>,

<A HREF = "#GoodnessOfFit"><NOBR>Goodness of Fit</NOBR></A>,

<A HREF = "#Group">Group</A>

<DT><BIG>H</BIG>

<DD>

<A HREF = "#HammingDistance"><NOBR>Hamming Distance</NOBR></A>,

<A HREF = "#Hardware">Hardware</A>,

<A HREF = "#Hash">Hash</A>,

<A HREF = "#Hexadecimal">Hexadecimal (Hex)</A>,

<A HREF = "#Homophonic">Homophonic</A>,

<A HREF = "#HomophonicSubstitution"><NOBR>Homophonic Substitution</NOBR></A>

<DT><BIG>I</BIG>

<DD>

<A HREF = "#IDEA">IDEA</A>,

<A HREF = "#IdealSecrecy"><NOBR>Ideal Secrecy</NOBR></A>,

<A HREF = "#i.i.d.">i.i.d.</A>,

<A HREF = "#InductiveReasoning"><NOBR>Inductive Reasoning</NOBR></A>,

<A HREF = "#Inductor">Inductor</A>,

<A HREF = "#Injective">Injective</A>,

<A HREF = "#Insulator">Insulator</A>,

<A HREF = "#Integer">Integer</A>,

<A HREF = "#IntermediateBlock"><NOBR>Intermediate Block</NOBR></A>,

<A HREF = "#Interval">Interval</A>,

<A HREF = "#Into">Into</A>,

<A HREF = "#Inverse">Inverse</A>,

<A HREF = "#Invertible">Invertible</A>,

<A HREF = "#Involution">Involution</A>,

<A HREF = "#Irreducible">Irreducible</A>,

<A HREF = "#IV">IV</A>

<DT><BIG>J</BIG>

<DD>

<A HREF = "#Jitterizer">Jitterizer</A>

<DT><BIG>K</BIG>

<DD>

<A HREF = "#KB">KB</A>,

<A HREF = "#Kb">Kb</A>,

<A HREF = "#KerckhoffsRequirements"><NOBR>Kerckhoff's Requirements</NOBR></A>,

<A HREF = "#Key">Key</A>,

<A HREF = "#KeyDistributionProblem"><NOBR>Key Distribution Problem</NOBR></A>,

<A HREF = "#Keyspace">Keyspace</A>,

<A HREF = "#KeyedSubstitution"><NOBR>Keyed Substitution</NOBR></A>,

<A HREF = "#KnownPlaintextAttack"><NOBR>Known Plaintext Attack</NOBR></A>,

<A HREF = "#KolmogorovSmirnov"><NOBR>Kolmogorov-Smirnov</NOBR></A>

<DT><BIG>L</BIG>

<DD>

<A HREF = "#Latency">Latency</A>,

<A HREF = "#LatinSquare"><NOBR>Latin Square</NOBR></A>,

<A HREF = "#LatinSquareCombiner"><NOBR>Latin Square Combiner</NOBR></A>,

<A HREF = "#Layer">Layer</A>,

<A HREF = "#LFSR">LFSR</A>,

<A HREF = "#Linear">Linear</A>,

<A HREF = "#LinearComplexity"><NOBR>Linear Complexity</NOBR></A>,

<A HREF = "#LinearFeedbackShiftRegister"><NOBR>Linear Feedback Shift Register</NOBR></A>,

<A HREF = "#LinearLogicFunction"><NOBR>Linear Logic Function</NOBR></A>,

<A HREF = "#Logic">Logic</A>,

<A HREF = "#LogicFunction"><NOBR>Logic Function</NOBR></A>,

<A HREF = "#LSB">LSB</A>

<DT><BIG>M</BIG>

<DD>

<A HREF = "#MSequence">M-Sequence</A>,

<A HREF = "#MachineLanguage"><NOBR>Machine Language</NOBR></A>,

<A HREF = "#MagneticField"><NOBR>Magnetic Field</NOBR></A>,

<A HREF = "#ManInTheMiddleAttack"><NOBR>Man-in-the-Middle Attack</NOBR></A>,

<A HREF = "#Mapping">Mapping</A>,

<A HREF = "#MarkovProcess"><NOBR>Markov Process</NOBR></A>,

<A HREF = "#MathematicalCryptography"><NOBR>Mathematical Cryptography</NOBR></A>,

<A HREF = "#MaximalLength"><NOBR>Maximal Length</NOBR></A>,

<A HREF = "#MB">MB</A>,

<A HREF = "#Mb">Mb</A>,

<A HREF = "#Mechanism">Mechanism</A>,

<A HREF = "#MechanisticCryptography"><NOBR>Mechanistic Cryptography</NOBR></A>,

<A HREF = "#MersennePrime"><NOBR>Mersenne Prime</NOBR></A>,

<A HREF = "#MessageDigest"><NOBR>Message Digest</NOBR></A>,

<A HREF = "#MessageKey"><NOBR>Message Key</NOBR></A>,

<A HREF = "#MITM">MITM</A>,

<A HREF = "#Mixing">Mixing</A>,

<A HREF = "#MixingCipher">Mixing Cipher</A>,

<A HREF = "#Mod2"><NOBR>Mod 2</NOBR></A>,

<A HREF = "#Mod2Polynomial"><NOBR>Mod 2 Polynomial</NOBR></A>,

<A HREF = "#Mode">Mode</A>,

<A HREF = "#Modulo">Modulo</A>,

<A HREF = "#Monadic">Monadic</A>,

<A HREF = "#MonoalphabeticSubstitution"><NOBR>Monoalphabetic Substitution</NOBR></A>,

<A HREF = "#Monographic">Monographic</A>,

<A HREF = "#MultipleEncryption"><NOBR>Multiple Encryption</NOBR></A>

<DT><BIG>N</BIG>

<DD>

<A HREF = "#Nomenclator">Nominclator</A>,

<A HREF = "#Nominal">Nominal</A>,

<A HREF = "#Nonlinearity">Nonlinearity</A>,

<A HREF = "#NOT">NOT</A>,

<A HREF = "#NullHypothesis"><NOBR>Null Hypothesis</NOBR></A>

<DT><BIG>O</BIG>

<DD>

<A HREF = "#ObjectCode"><NOBR>Object Code</NOBR></A>,

<A HREF = "#Objective">Objective</A>,

<A HREF = "#Octal">Octal</A>,

<A HREF = "#Octave">Octave</A>,

<A HREF = "#OFB">OFB</A>,

<A HREF = "#OneTimePad"><NOBR>One Time Pad</NOBR></A>,

<A HREF = "#OneToOne">One-To-One</A>,

<A HREF = "#OneWayDiffusion"><NOBR>One Way Diffusion</NOBR></A>,

<A HREF = "#Onto">Onto</A>,

<A HREF = "#Opcode">Opcode</A>,

<A HREF = "#OperatingMode"><NOBR>Operating Mode</NOBR></A>,

<A HREF = "#Opponent">Opponent</A>,

<A HREF = "#OR">OR</A>,

<A HREF = "#Order">Order</A>,

<A HREF = "#Ordinal">Ordinal</A>,

<A HREF = "#Orthogonal">Orthogonal</A>,

<A HREF = "#OrthogonalLatinSquares"><NOBR>Orthogonal Latin Squares</NOBR></A>,

<A HREF = "#OTP">OTP</A>,

<A HREF = "#OverallDiffusion"><NOBR>Overall Diffusion</NOBR></A>

<DT><BIG>P</BIG>

<DD>

<A HREF = "#Padding">Padding</A>,

<A HREF = "#Password">Password</A>,

<A HREF = "#Patent">Patent</A>,

<A HREF = "#PatentInfringement"><NOBR>Patent Infringement</NOBR></A>,

<A HREF = "#PerfectSecrecy"><NOBR>Perfect Secrecy</NOBR></A>,

<A HREF = "#Permutation">Permutation</A>,

<A HREF = "#PGP">PGP</A>,

<A HREF = "#PhysicallyRandom"><NOBR>Physically Random</NOBR></A>,

<A HREF = "#PinkNoise"><NOBR>Pink Noise</NOBR></A>,

<A HREF = "#Plaintext">Plaintext</A>,

<A HREF = "#PoissonDistribution"><NOBR>Poisson Distribution</NOBR></A>,

<A HREF = "#PolyalphabeticCombiner"><NOBR>Polyalphabetic Combiner</NOBR></A>,

<A HREF = "#PolyalphabeticSubstitution"><NOBR>Polyalphabetic Substitution</NOBR></A>,

<A HREF = "#PolygramSubstitution"><NOBR>Polygram Substitution</NOBR></A>,

<A HREF = "#Polygraphic">Polygraphic</A>,

<A HREF = "#Polynomial">Polynomial</A>,

<A HREF = "#Polyphonic">Polyphonic</A>,

<A HREF = "#Population">Population</A>,

<A HREF = "#PopulationEstimation"><NOBR>Population Estimation</NOBR></A>,

<A HREF = "#Power">Power</A>,

<A HREF = "#Primitive">Primitive</A>,

<A HREF = "#PrimitivePolynomial"><NOBR>Primitive Polynomial</NOBR></A>,

<A HREF = "#Prime">Prime</A>,

<A HREF = "#PriorArt"><NOBR>Prior Art</NOBR></A>,

<A HREF = "#PRNG">PRNG</A>,

<A HREF = "#Process">Process</A>,

<A HREF = "#PseudoRandom">Pseudorandom</A>,

<A HREF = "#PublicKeyCipher"><NOBR>Public Key Cipher</NOBR></A>

<DT><BIG>R</BIG>

<DD>

<A HREF = "#Random">Random</A>,

<A HREF = "#RandomNumberGenerator"><NOBR>Random Number Generator</NOBR></A>,

<A HREF = "#RandomVariable"><NOBR>Random Variable</NOBR></A>,

<A HREF = "#Range">Range</A>,

<A HREF = "#ReallyRandom"><NOBR>Really Random</NOBR></A>,

<A HREF = "#Relay">Relay</A>,

<A HREF = "#ResearchHypothesis"><NOBR>Research Hypothesis</NOBR></A>,

<A HREF = "#Resistor">Resistor</A>,

<A HREF = "#Ring">Ring</A>,

<A HREF = "#Root">Root</A>,

<A HREF = "#RMS">RMS</A>,

<A HREF = "#RootMeanSquare">Root Mean Square</A>,

<A HREF = "#RNG">RNG</A>,

<A HREF = "#Round">Round</A>,

<A HREF = "#RSA">RSA</A>,

<A HREF = "#RunningKey"><NOBR>Running Key</NOBR></A>

<DT><BIG>S</BIG>

<DD>

<A HREF = "#Salt">Salt</A>,

<A HREF = "#Sample">Sample</A>,

<A HREF = "#S-Box">S-Box</A>,

<A HREF = "#Scalable">Scalable</A>,

<A HREF = "#Secrecy">Secrecy</A>,

<A HREF = "#SecretCode"><NOBR>Secret Code</NOBR></A>,

<A HREF = "#SecretKeyCipher"><NOBR>Secret Key Cipher</NOBR></A>,

<A HREF = "#Security">Security</A>,

<A HREF = "#SecurityThroughObscurity"><NOBR>Security Through Obscurity</NOBR></A>,

<A HREF = "#Semiconductor">Semiconductor</A>,

<A HREF = "#Semigroup">Semigroup</A>,

<A HREF = "#SessionKey"><NOBR>Session Key</NOBR></A>,

<A HREF = "#Set">Set</A>,

<A HREF = "#ShiftRegister"><NOBR>Shift Register</NOBR></A>,

<A HREF = "#Shuffle">Shuffle</A>,

<A HREF = "#SieveOfEratosthenes"><NOBR>Sieve of Eratosthenes</NOBR></A>,

<A HREF = "#Significance">Significance</A>,

<A HREF = "#SimpleSubstitution"><NOBR>Simple Substitution</NOBR></A>,

<A HREF = "#Software">Software</A>,

<A HREF = "#SourceCode"><NOBR>Source Code</NOBR></A>,

<A HREF = "#State">State</A>,

<A HREF = "#StationaryProcess"><NOBR>Stationary Process</NOBR></A>,

<A HREF = "#Statistic">Statistic</A>,

<A HREF = "#Statistics">Statistics</A>,

<A HREF = "#Steganography">Steganography</A>,

<A HREF = "#Stochastic">Stochastic</A>,

<A HREF = "#StreamCipher"><NOBR>Stream Cipher</NOBR></A>,

<A HREF = "#Strength">Strength</A>,

<A HREF = "#StrictAvalancheCriterion"><NOBR>Strict Avalanche Criterion (SAC)</NOBR></A>,

<A HREF = "#Subjective">Subjective</A>,

<A HREF = "#Substitution">Substitution</A>,

<A HREF = "#SubstitutionPermutation">Substitution-Permutation</A>,

<A HREF = "#SubstitutionTable"><NOBR>Substitution Table</NOBR></A>,

<A HREF = "#Superencryption">Superencryption</A>,

<A HREF = "#Surjective">Surjective</A>,

<A HREF = "#Switch">Switch</A>,

<A HREF = "#SwitchingFunction"><NOBR>Switching Function</NOBR></A>,

<A HREF = "#SymmetricCipher"><NOBR>Symmetric Cipher</NOBR></A>,

<A HREF = "#SymmetricGroup"><NOBR>Symmetric Group</NOBR></A>,

<A HREF = "#System">System</A>,

<A HREF = "#SystemDesign"><NOBR>System Design</NOBR></A>

<DT><BIG>T</BIG>

<DD>

<A HREF = "#TableSelectionCombiner"><NOBR>Table Selection Combiner</NOBR></A>,

<A HREF = "#TEMPEST">TEMPEST</A>,

<A HREF = "#Transformer">Transformer</A>,

<A HREF = "#Transistor">Transistor</A>,

<A HREF = "#Transposition">Transposition</A>,

<A HREF = "#TrapDoor"><NOBR>Trap Door</NOBR></A>,

<A HREF = "#TripleDES"><NOBR>Triple DES</NOBR></A>,

<A HREF = "#TrulyRandom"><NOBR>Truly Random</NOBR></A>,

<A HREF = "#Trust">Trust</A>,

<A HREF = "#TruthTable"><NOBR>Truth Table</NOBR></A>,

<A HREF = "#TypeIError"><NOBR>Type I Error</NOBR></A>,

<A HREF = "#TypeIIError"><NOBR>Type II Error</NOBR></A>

<DT><BIG>U</BIG>

<DD>

<A HREF = "#Unary">Unary</A>,

<A HREF = "#UnexpectedDistance"><NOBR>Unexpected Distance</NOBR></A>,

<A HREF = "#UnicityDistance"><NOBR>Unicity Distance</NOBR></A>,

<A HREF = "#UniformDistribution"><NOBR>Uniform Distribution</NOBR></A>

<DT><BIG>V</BIG>

<DD>

<A HREF = "#VariableSizeBlockCipher"><NOBR>Variable Size Block Cipher</NOBR></A>,

<A HREF = "#Voltage">Voltage</A>

<DT><BIG>W</BIG>

<DD>

<A HREF = "#WalshFunctions"><NOBR>Walsh Functions</NOBR></A>,

<A HREF = "#Weight">Weight</A>,

<A HREF = "#Whitening">Whitening</A>

<A HREF = "#WhiteNoise"><NOBR>White Noise</NOBR></A>

<A HREF = "#Wire">Wire</A>

<DT><BIG>X</BIG>

<DD>

<A HREF = "#XOR">XOR</A>

</DL>

<HR>

<DL>

<A NAME = "Absolute"></A>

<DT><B>Absolute</B>

<DD>In the study of

<A HREF = "#Logic">logic</A>, something observed similarly by

most observers, or something agreed upon, or which has the same

value each time measured. Something not in dispute, unarguable, and

independent of other

<A HREF = "#State">state</A>. As opposed to

<A HREF = "#Contextual">contextual</A>.

<A NAME = "AC"></A>

<P><DT><B>AC</B>

<DD>Alternating

<A HREF = "#Current">Current</A>:

Electrical power which repeatedly reverses direction of flow.

As opposed to

<A HREF = "#DC">DC</A>.

<P>Generally used for power distribution because the changing

current supports the use of

<A HREF = "#Transformer">transformers</A>. Utilities can thus

transport power at high

<A HREF = "#Voltage">voltage</A> and low

<A HREF = "#Current">current</A>, which minimize

"ohmic"

or I<SUP>2</SUP>R losses. The high voltages are then reduced

at power substations and again by pole transformers for delivery

to the consumer.

<A NAME = "AdditiveCombiner"></A>

<P><DT><B>Additive Combiner</B>

<DD>An additive

<A HREF = "#Combiner">combiner</A> uses numerical concepts similar

to addition to

<A HREF = "#Mixing">mix</A> multiple values into a single result.

<P>One example is

<A HREF = "#Byte">byte</A> addition

<A HREF = "#Modulo">modulo</A> 256, which simply adds

two byte values, each in the range 0..255, and produces the

remainder after division by 256, again a value in the byte range

of 0..255. Subtraction is also an "additive" combiner.

<P>Another example is bit-level

<A HREF = "#ExclusiveOR">exclusive-OR</A> which is addition

<A HREF = "#Mod2">mod 2</A>.

A byte-level exclusive-OR is a

<A HREF = "#Polynomial">polynomial</A> addition.

<A NAME = "AdditiveRNG"></A>

<P><DT><B>Additive RNG</B>

<DD>(Additive

<A HREF = "#RandomNumberGenerator">random number generator</A>.)

A <A HREF = "#LFSR">LFSR</A>-based

<A HREF = "#RNG">RNG</A> typically using multi-bit elements

and integer addition (instead of

<A HREF = "#XOR">XOR</A>) combining. References include:

<BLOCKQUOTE>

Knuth, D. 1981.

<I>The Art of Computer Programming,</I> Vol. 2,

<I>Seminumerical Algorithms.</I> 2nd ed. 26-31.

Addison-Wesley: Reading, Massachusetts.

</BLOCKQUOTE>

<BLOCKQUOTE>

Marsaglia, G. and L. Tsay. 1985. Matrices and the Structure

of Random Number Sequences.

<I>Linear Algebra and its Applications.</I> 67: 147-156.

</BLOCKQUOTE>

<P>Advantages include:

<UL>

<LI>A long, mathematically proven cycle length.

<LI>Especially efficient

<A HREF = "#Software">software</A> implementations.

<LI>Almost arbitrary initialization (some element must have its

least significant bit set).

<LI>A simple design which is easy to get right.

</UL>

<P>In addition, a vast multiplicity of independent cycles has the

potential of confusing even a "quantum computer," should such a

thing become possible.

<BIG><PRE>

For Degree-n Primitive, and Bit Width w

Total States: 2<SUP>nw</SUP>

Non-Init States: 2<SUP>n(w-1)</SUP>

Number of Cycles: 2<SUP>(n-1)(w-1)</SUP>

Length Each Cycle: (2<SUP>n</SUP>-1)2<SUP>(w-1)</SUP>

Period of LSB: 2<SUP>n</SUP>-1

</PRE></BIG>

<P>The binary addition of two bits with no carry input is just

XOR, so the

<A HREF = "#LSB">lsb</A> of an Additive RNG has

the usual <A HREF = "#MaximalLength">maximal length</A> period.

<P>A degree-127 Additive RNG using 127 elements of 32 bits each

has 2<SUP>4064</SUP> unique states. Of these, 2<SUP>3937</SUP>

are disallowed by initialization (the

<A HREF = "#LSB">lsb</A>'s are all "0") but this is just one

unusable state out of 2<SUP>127</SUP>. There are still

2<SUP>3906</SUP> cycles which <I>each</I> have almost 2<SUP>158</SUP>

steps. (The Cloak2

<A HREF = "#StreamCipher">stream cipher</A> uses an Additive RNG

with 9689 elements of 32 bits, and so has 2<SUP>310048</SUP> unique

states. These are mainly distributed among 2<SUP>300328</SUP>

different cycles with almost 2<SUP>9720</SUP> steps each.)

<P>Note that any LFSR, including the Additive RNG, is very weak

when used alone. But when steps are taken to hide the sequence

(such as using a

<A HREF = "#Jitterizer">jitterizer</A> and

<A HREF = "#DynamicSubstitutionCombiner">Dynamic Substitution

combining</A>) the result can have significant strength.

<A NAME = "Affine"></A>

<P><DT><B>Affine</B>

<DD>Generally speaking, <A HREF = "#Linear">linear</A>.

Sometimes <I>affine</I> generalizes "linearity" to expressions of

multiple independent variables, with only a single-variable

expression being called "linear."

From analytic and algebraic geometry.

<BLOCKQUOTE>

<P>Assume the flat plane defined by two arbitrary unit vectors

<B>e</B><SUB>1</SUB>, <B>e</B><SUB>2</SUB> and a common origin

<B>O</B>; this is a coordinate "frame." Assume a grid of lines

parallel to each frame vector, separated by unit lengths (a "metric"

which may differ for each vector). If the vectors happen to be

perpendicular, we have a Cartesian coordinate system, but in any

case we can locate any point on the plane by its position on the

grid.

<P>An affine transformation can change the origin, the angle between

the vectors, and unit vector lengths. Shapes in the original frame

thus become "pinched," "squashed" or "stretched" images under the

affine transformation. This same sort of thing generalizes to higher

degree expressions.

</BLOCKQUOTE>

<P>The <I>Handbook of Mathematics</I> says that if <B>e</B><SUB>1</SUB>,

<B>e</B><SUB>2</SUB>, <B>e</B><SUB>3</SUB> are linearly independent

vectors, any vector <B>a</B> can be expressed uniquely in the

form <B>a</B> = <B>a</B><SUB>1</SUB><B>e</B><SUB>1</SUB> +

<B>a</B><SUB>2</SUB><B>e</B><SUB>2</SUB> +

<B>a</B><SUB>3</SUB><B>e</B><SUB>3</SUB>

where the <B>a</B><SUB>i</SUB> are the <I>affine coordinates.</I>

(p.518)

<P><I>The VNR Concise Encyclopedia of Mathematics</I> says

"All transformations that lead to a uniquely soluble system of linear

equations are called <I>affine transformations</I>." (p.534)

<A NAME = "AffineBooleanFunction"></A>

<P><DT><B>Affine Boolean Function</B>

<DD>A

<A HREF = "#BooleanFunction">Boolean function</A>

which can be represented in the form:

<BIG><BLOCKQUOTE><TT>

a<SUB>n</SUB>x<SUB>n</SUB> + a<SUB>n-1</SUB>x<SUB>n-1</SUB>

+ ... + a<SUB>1</SUB>x<SUB>1</SUB> + a<SUB>0</SUB>

</TT></BLOCKQUOTE></BIG>

where the operations are

<A HREF = "#Mod2">mod 2</A>: addition is

<A HREF = "#ExclusiveOR">Exclusive-OR</A>, and multiplication is

<A HREF = "#AND">AND</A>.

<P>Note that all of the variables <BIG>x<SUB>i</SUB></BIG> are to

the first power only, and each coefficient <BIG>a<SUB>i</SUB></BIG>

simply enables or disables its associated variable.

The result is a single Boolean value, but the constant term

<BIG>a<SUB>0</SUB></BIG> can produce either possible output

polarity.

<P>Here are all possible 3-variable affine Boolean functions (each

of which may be inverted by complementing the constant term):

<PRE>

affine truth table

c 0 0 0 0 0 0 0 0

x0 0 1 0 1 0 1 0 1

x1 0 0 1 1 0 0 1 1

x1+x0 0 1 1 0 0 1 1 0

x2 0 0 0 0 1 1 1 1

x2+ x0 0 1 0 1 1 0 1 0

x2+x1 0 0 1 1 1 1 0 0

x2+x1+x0 0 1 1 0 1 0 0 1

</PRE>

<A NAME = "Alphabet"></A>

<P><DT><B>Alphabet</B>

<DD>The set of symbols under discussion.

<A NAME = "AlternativeHypothesis"></A>

<P><DT><B>Alternative Hypothesis</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, the statement formulated so

that the logically contrary statement, the

<A HREF = "#NullHypothesis">null hypothesis</A> <I>H</I><SUB>0</SUB>

has a test

<A HREF = "#Statistic">statistic</A> with a known

<A HREF = "#Distribution">distribution</A> for the case when there

is nothing unusual to detect. Also called the

<A HREF = "#ResearchHypothesis">research hypothesis</A>

<I>H</I><SUB>1</SUB>, and logically identical to

"NOT-<I>H</I><SUB>0</SUB>" or "<I>H</I><SUB>0</SUB>

is not true."

<A NAME = "Amplifier"></A>

<P><DT><B>Amplifier</B>

<DD>a

<A HREF = "#Component">component</A> or device intended to sense a

signal and produce a larger version of that signal. In general,

any amplifying device is limited by available power,

<A HREF = "#Frequency">frequency</A>

response, and device maximums for

<A HREF = "#Voltage">voltage</A>,

<A HREF = "#Current">current</A>, and

power dissipation.

<P><A HREF = "#Transistor">Transistors</A> are

<A HREF = "#Analog">analog</A> amplifiers which are basically

<A HREF = "#Linear">linear</A> over a reasonable range and so

require

<A HREF = "#DC">DC</A> power. In contrast,

<A HREF = "#Relay">Relays</A> are classically mechanical devices

with direct metal-to-metal moving connections, and so can handle

generally higher power and

<A HREF = "#AC">AC</A> current.

<A NAME = "Amplitude"></A>

<P><DT><B>Amplitude</B>

<DD>The signal level, or height.

<A NAME = "Analog"></A>

<P><DT><B>Analog</B>

<DD>Pertaining to continuous values. As opposed to

<A HREF = "#Digital">digital</A>

or discrete quantities.

<A NAME = "AND"></A>

<P><DT><B>AND</B>

<DD>A Boolean

<A HREF = "#LogicFunction">logic function</A> which is also

<A HREF = "#Mod2">mod 2</A> multiplication.

<A NAME = "ASCII"></A>

<P><DT><B>ASCII</B>

<DD>A public

<A HREF = "#Code">code</A> for converting between

7-<A HREF = "#Bit">bit</A> values 0..127 (or 00..7f

<A HREF = "#Hexadecimal">hex</A>) and text characters.

ASCII is an acronym for American Standard Code for Information

Interchange.

<PRE>

DEC HEX CTRL CMD DEC HEX CHAR DEC HEX CHAR DEC HEX CHAR

0 00 ^@ NUL 32 20 SPC 64 40 @ 96 60 '

1 01 ^A SOH 33 21 ! 65 41 A 97 61 a

2 02 ^B STX 34 22 " 66 42 B 98 62 b

3 03 ^C ETX 35 23 # 67 43 C 99 63 c

4 04 ^D EOT 36 24 $ 68 44 D 100 64 d

5 05 ^E ENQ 37 25 % 69 45 E 101 65 e

6 06 ^F ACK 38 26 & 70 46 F 102 66 f

7 07 ^G BEL 39 27 ' 71 47 G 103 67 g

8 08 ^H BS 40 28 ( 72 48 H 104 68 h

9 09 ^I HT 41 29 ) 73 49 I 105 69 i

10 0a ^J LF 42 2a * 74 4a J 106 6a j

11 0b ^K VT 43 2b + 75 4b K 107 6b k

12 0c ^L FF 44 2c , 76 4c L 108 6c l

13 0d ^M CR 45 2d - 77 4d M 109 6d m

14 0e ^N SO 46 2e . 78 4e N 110 6e n

15 0f ^O SI 47 2f / 79 4f O 111 6f o

16 10 ^P DLE 48 30 0 80 50 P 112 70 p

17 11 ^Q DC1 49 31 1 81 51 Q 113 71 q

18 12 ^R DC2 50 32 2 82 52 R 114 72 r

19 13 ^S DC3 51 33 3 83 53 S 115 73 s

20 14 ^T DC4 52 34 4 84 54 T 116 74 t

21 15 ^U NAK 53 35 5 85 55 U 117 75 u

22 16 ^V SYN 54 36 6 86 56 V 118 76 v

23 17 ^W ETB 55 37 7 87 57 W 119 77 w

24 18 ^X CAN 56 38 8 88 58 X 120 78 x

25 19 ^Y EM 57 39 9 89 59 Y 121 79 y

26 1a ^Z SUB 58 3a : 90 5a Z 122 7a z

27 1b ^[ ESC 59 3b ; 91 5b [ 123 7b {

28 1c ^\ FS 60 3c < 92 5c \ 124 7c |

29 1d ^] GS 61 3d = 93 5d ] 125 7d }

30 1e ^^ RS 62 3e > 94 5e ^ 126 7e

31 1f ^_ US 63 3f ? 95 5f _ 127 7f DEL

</PRE>

<A NAME = "Associative"></A>

<P><DT><B>Associative</B>

<DD>A

<A HREF = "#Dyadic">dyadic</A> operation in which two sequential

operations on three arguments can first operate on either the

first two or the last two arguments, producing the same result in

either case: <NOBR>(a + b) + c = a + (b + c).</NOBR>

<P>Also see:

<A HREF = "#Commutative">commutative</A> and

<A HREF = "#Distributive">distributive</A>.

<A NAME = "AsymmetricCipher"></A>

<P><DT><B>Asymmetric Cipher</B>

<DD>A

<A HREF = "#PublicKeyCipher">public key cipher</A>.

<A NAME = "Attack"></A>

<P><DT><B>Attack</B>

<DD>General ways in which a

<A HREF = "#Cryptanalyst">cryptanalyst</A> may try to

"<A HREF = "#Break">break</A>" or penetrate the secrecy of a

<A HREF = "#Cipher">cipher</A>. These are <B>not</B> algorithms;

they are just <I>approaches</I> as a starting place for constructing

specific algorithms.

<P>Classically, attacks were neither named nor classified; there

was just: "here is a cipher, and here is the attack." And while

this gradually developed into named attacks, there is no overall

attack taxonomy. Currently, attacks are often classified by the

information available to the attacker or <I>constraints</I> on the

attack, and then by strategies which use the available information.

Not only

<A HREF = "#Cipher">ciphers</A>, but also cryptographic

<A HREF = "#Hash">hash</A> functions can be attacked, generally

with very different strategies.

<H4>Informational Constraints</H4>

<P>We are to attack a cipher which

<A HREF = "#Encipher">enciphers</A>

<A HREF = "#Plaintext">plaintext</A> into

<A HREF = "#Ciphertext">ciphertext</A> or

<A HREF = "#Decipher">deciphers</A> the opposite way, under

control of a

<A HREF = "#Key">key</A>. The available information necessarily

constrains our attack strategies.

<UL>

<LI><B>Ciphertext Only:</B> We have only ciphertext to work with.

Sometimes the statistics of the ciphertext provide insight and

can lead to a break.

<LI><B>Known Plaintext:</B> We have some, or even an extremely

large amount, of plaintext and the associated ciphertext.

<LI><B>Defined Plaintext:</B> We can submit arbitrary messages to

be ciphered and capture the resulting ciphertext.

(Also Chosen Plaintext and Adaptive Chosen Plaintext.)

<LI><B>Defined Ciphertext:</B> We can submit arbitrary messages

to be deciphered and see the resulting plaintext.

(Also Chosen Ciphertext and Adaptive Chosen Ciphertext.)

<LI><B>Chosen Key:</B> We can specify a change in any particular

key bit, or some other relationship between keys.

<LI><B>Timing:</B> We can measure the duration of ciphering

operations and use that to reveal the key or data.

<LI><B>Fault Analysis:</B> We can induce random faults into the

ciphering machinery, and use those to expose the key.

<LI><B>Man-in-the-Middle:</B> We can subvert the routing capabilities

of a computer network, and pose as the other side to each of the

communicators. (Usually a key authentication attack on

<A HREF = "#PublicKeyCipher">public key</A> systems.)

</UL>

<H4>Attack Strategies</H4>

<P>The goal of an attack is to reveal some unknown plaintext, or the

key (which will reveal the plaintext). An attack which succeeds with

less effort than a brute-force search we call a

<A HREF = "#Break">break</A>.

An "academic" ("theoretical," "certificational") break may involve

impractically large amounts of data or resources, yet still be called

a "break" if the attack would be easier than brute force.

(It is thus possible for a "broken" cipher to be much stronger than

a cipher with a short key.) Sometimes the attack strategy is thought

to be obvious, given a particular informational constraint,

and is not further classified.

<UL>

<LI><A HREF = "#BruteForceAttack"><B>Brute Force</B></A>

(also Exhaustive Key Search): Try to decipher ciphertext under

every possible key until readable messages are produced.

(Also "brute force" any searchable-size <I>part</I> of a

cipher.)

<LI><A HREF = "#CodebookAttack"><B>Codebook</B></A> (the classic

"codebreaking" approach): Collect a

<A HREF = "#Codebook">codebook</A> of transformations

between plaintext and ciphertext.

<LI><A HREF = "#DifferentialCryptanalysis"><B>Differential

Cryptanalysis:</B></A> Find a statistical correlation between

key values and cipher transformations (typically the

Exclusive-OR of text pairs), then use sufficient defined

plaintext to develop the key.

<LI><B>Linear Cryptanalysis:</B></A> Find a linear approximation

to the keyed S-boxes in a cipher, and use that to reveal

the key.

<LI><B>Meet-in-the-Middle:</B> Given a two-level multiple encryption,

search for the keys by collecting every possible result for

enciphering a known plaintext under the first cipher, and

deciphering the known ciphertext under the second cipher; then

find the match.

<LI><B>Key Schedule:</B> Choose keys which produce known effects

in different rounds.

<LI><A HREF = "#BirthdayAttack"><B>Birthday</B></A> (usually a hash

attack): Use the

<A HREF = "#BirthdayParadox">birthday paradox</A>, the idea that

it is much easier to find two values which match than it is to

find a match to some particular value.

<LI><B>Formal Coding</B> (also Algebraic): From the cipher design,

develop equations for the key in terms of known plaintext,

then solve those equations.

<LI><B>Correlation</B>: In a

<A HREF = "#StreamCipher">stream cipher</A>, distinguish between

data and confusion, or between different confusion streams, from

a statistical imbalance in a

<A HREF = "#Combiner">combiner</A>.

<LI><A HREF = "#DictionaryAttack"><B>Dictionary</B></A>: Form a list

of the most-likely keys, then try those keys one-by-one (a way to

improve brute force).

<LI><B>Replay</B>: Record and save some ciphertext blocks or messages

(especially if the content is known), then re-send those blocks

when useful.

</UL>

<P>Many attacks try to isolate unknown small components or aspects

so they can be solved separately, a process known as

<A HREF = "#DivideAndConquer">divide and conquer</A>. Also see:

<A HREF = "#Security">security</A>.

<A NAME = "AugmentedRepetitions"></A>

<P><DT><B>Augmented Repetitions</B>

<DD>When sampling with replacement, eventually we again find some

object or value which has been found before. We call such an

occurrence a "repetition." A value found exactly twice is a

double, or "2-rep"; a value found three times is a triple or

"3-rep," and so on.

<P>For a known

<A HREF = "#Population">population</A>, the number of repetitions

expected at each level has long been understood to be a

<A HREF = "#BinomialDistribution">binomial</A> expression.

But if we are sampling in an attempt to <I>establish</I> the

effective size of an unknown population, we have two problems:

<OL><P>

<LI>The binomial equations which predict expected repetitions

do not reverse well to predict population, and

<LI>Exact repetitions discard information and so are less

accurate than we would like. For example, if we have a

double and then find another of that value, we now have

a triple, and one <I>less</I> double. So if we are using

doubles to predict population, the occurrence of a triple

influences the predicted population in exactly the wrong

direction.

</OL>

<P>Fortunately, there is an unexpected and apparently previously

unknown combinatoric relationship between the population and the

number of combinations of occurrences of repeated values. This

allows us to convert any number of triples and higher <I>n</I>-reps

to the number of 2-reps which have the same probability. So if we

have a double, and then get another of the same value, we have a

triple, which we can convert into three 2-reps. The total number

of 2-reps from all repetitions (the <I>augmented 2-reps</I> value)

is then used to predict population.

<P>We can relate the number of samples <I>s</I> to the population

<I>N</I> through the expected number of augmented doubles

<I>Ead</I>:

<PRE>

Ead(N,s) = s(s-1) / 2N .

</PRE>

This equation is <B>exact</B>, <I>provided</I> we interpret all

the exact n-reps in terms of 2-reps. For example, a triple is

interpreted as three doubles; the augmentation from 3-reps to 2-reps

is (3 C 2) or 3. The augmented result is the sum of the

contributions from all higher repetition levels:

<PRE>

n i

ad = SUM ( ) r[i] .

i=2 2

</PRE>

where <I>ad</I> is the number of augmented doubles, and <I>r[i]</I>

is the exact repetition count at the <I>i</I>-th level.

<P>And this leads to an equation for predicting population:

<PRE>

Nad(s,ad) = s(s-1) / 2 ad .

</PRE>

This predicts the population <I>Nad</I> as based on a mean value

of augmented doubles <I>ad</I>. Clearly, we expect the number of

samples to be far larger than the number of augmented doubles, but

an error in the augmented doubles <I>ad</I> should produce a

proportionally similar error in the predicted population <I>Nad.</I>

We typically develop <I>ad</I> to high precision by averaging the

results of many large trials.

<P>However, since the trials should have approximately a simple

<A HREF = "#PoissonDistribution">Poisson distribution</A> (which has

only a single parameter), we could be a bit more clever and fit the

results to the expected distribution, thus perhaps developing a bit

more accuracy.

<P>Also see the article:

<A HREF = "http://www.io.com/~ritter/ARTS/BIRTHDAY.HTM">Estimating

Population from Repetitions in Accumulated Random Samples</A>, and the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/POPWKSHT.HTM">Population

Estimation Worksheets in JavaScript</A> page of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<A NAME = "Authentication"></A>

<P><DT><B>Authentication</B>

<DD>One of the objectives of

<A HREF = "#Cryptography">cryptography</A>: Assurance that a

message has not been modified in transit or storage (<I>message</I>

authentication or message <I>integrity</I>). Also

<A HREF = "#Key">key</A> authentication for

<A HREF = "#PublicKeyCipher">public keys</A>. Also user or source

identification, which may verify the right to send the message in

the first place.

<A NAME = "MessageAuthentication"></A>

<H4>Message <A HREF = "#Authentication">Authentication</A></H4>

<P>One form of message authentication computes a

<A HREF = "#CRC">CRC</A>

<A HREF = "#Hash">hash</A> across the

<A HREF = "#Plaintext">plaintext</A> data, and appends the CRC

remainder (or <I>result</I>) to the plaintext data: this adds

a computed redundancy to an arbitrary message.

The CRC result is then

<A HREF = "#Encipher">enciphered</A> along with the data. When

the message is

<A HREF = "#Decipher">deciphered</A>, if a second CRC operation

produces the same result, the message can be assumed unchanged.

<P>Note that a CRC is a fast,

<A HREF = "#Linear">linear</A> hash. Messages with particular CRC

result values can be constructed rather easily. However, if the CRC

is hidden behind strong ciphering, an

<A HREF = "#Opponent">Opponent</A> is unlikely to be able

to change the CRC value systematically or effectively. In particular,

this means that the CRC value will need more protection than a simple

<A HREF = "#ExclusiveOR">exclusive-OR</A>

<A HREF = "#StreamCipher">stream cipher</A> or the exclusive-OR

approach to handling short last

<A HREF = "#Block">blocks</A> in a

<A HREF = "#BlockCipher">block cipher</A>.

<P>A similar approach to message authentication uses a nonlinear

cryptographic hash function. These also add a computed redundancy

to the message, but generally require significantly more computation

than a CRC. It is thought to be exceedingly difficult to

construct messages with a particular cryptographic hash result,

so the hash result perhaps need not be hidden by encryption.

<P>One form of cryptographic hash is

<A HREF = "#DES">DES</A>

<A HREF = "#CBC">CBC</A> mode: using a key different than that used

for encryption, the final block of ciphertext is the hash of the

message. This obviously doubles the computation when both encryption

and authentication are needed. And since any cryptographic hash is

vulnerable to

<A HREF = "#BirthdayAttack">birthday attacks</A>, the small 64-bit

block size implies that we should be able to find two different

messages with the same hash value by constructing and hashing "only"

about 2<SUP>32</SUP> different messages.

<P>Another approach to message authentication is to use an

<A HREF = "#AuthenticatingBlockCipher">authenticating block cipher</A>;

this is often a

<A HREF = "#BlockCipher">block cipher</A> which has a large

<A HREF = "#Block">block</A>, with some "extra data" inserted in

an "authentication field" as part of the plaintext before

enciphering each block.

The "extra data" can be some transformation of the key, the

plaintext, and/or a sequence number. This essentially creates a

<A HREF = "#Homophonic">homophonic</A> block cipher: If we know

the key, many different ciphertexts will produce the same plaintext

field, but only one of those will have the correct authentication

field.

<P>The usual approach to authentication in a

<A HREF = "#PublicKeyCipher">public key cipher</A> is to encipher

with the private key. The resulting ciphertext can then be

deciphered by the public key, which anyone can know. Since even

the wrong key will produce a "deciphered" result, it is also

necessary to identify the resulting plaintext as a valid message;

in general this will also require redundancy in the form of a hash

value in the plaintext. The process provides no

<A HREF = "#Secrecy">secrecy</A>, but only a person with access to

the private key could have enciphered the message.

<A NAME = "UserAuthentication"></A>

<H4>User <A HREF = "#Authentication">Authentication</A></H4>

<P>The classical approach to user authentication is a

<A HREF = "#Password">password</A>;

this is "something you know." One can also make use of "something

you have" (such as a secure ID card), or "something you are"

(biometrics).

<P>The classic problem with passwords is that they must be

remembered by ordinary people, and so carry a limited amount of

uniqueness. Easy-to-remember passwords are often common language

phrases, and so often fall to a

<A HREF = "#DictionaryAttack">dictionary attack</A>. More

modern approaches involve using a Diffie-Hellman key exchange,

<I>plus</I> the password, thus minimizing exposure to a dictionary

attack. This does require a program on the user end, however.

<A NAME = "KeyAuthentication"></A>

<H4>Key <A HREF = "#Authentication">Authentication</A></H4>

<P>In

<A HREF = "#SecretKeyCipher">secret key ciphers</A>,

<A HREF = "#Key">key</A> authentication is <I>inherent</I> in

<A HREF = "#Security">secure</A>

<A HREF = "#KeyDistributionProblem">key distribution</A>.

<P>In

<A HREF = "#PublicKeyCipher">public key ciphers</A>, public keys

are exposed and often delivered insecurely. But someone who uses

the wrong key may unknowingly have "secure" communications with an

<A HREF = "#Opponent">Opponent</A>, as in a

<A HREF = "#ManInTheMiddleAttack">man-in-the-middle attack</A>.

It is thus absolutely crucial that public keys be authenticated

or <I>certified</I> as a separate process. Normally this implies

the need for a Certification Authority or CA.

<A NAME = "AuthenticatingBlockCipher"></A>

<P><DT><B>Authenticating Block Cipher</B>

<DD>A

<A HREF = "#BlockCipher">block cipher</A>

<A HREF = "#Mechanism">mechanism</A> which inherently contains an

<A HREF = "#Authentication">authentication</A> value or field.

<A NAME = "Autokey"></A>

<P><DT><B>Autokey</B>

<DD>A cipher whose key is produced by message data. One common

form is "ciphertext feedback," where

<A HREF = "#Ciphertext">ciphertext</A> is "fed back" into the

<A HREF = "#State">state</A> of the

<A HREF = "#RandomNumberGenerator">random number generator</A>

used to produce the

<A HREF = "#ConfusionSequence">confusion sequence</A> for a

<A HREF = "#StreamCipher">stream cipher</A>.

<A NAME = "Avalanche"></A>

<P><DT><B>Avalanche</B>

<DD>The observed property of a

<A HREF = "#BlockCipher">block cipher</A> constructed in

<A HREF = "#Layer">layers</A> or

"<A HREF = "#Round">rounds</A>" with respect to a tiny change

in the input. The

change of a single input bit generally produces multiple

bit-changes after one round, many more bit-changes after another

round, until, eventually, about half of the block will change.

An analogy is drawn to an avalanche in snow, where a small

initial effect can lead to a dramatic result.

As originally described by Feistel:

<BLOCKQUOTE>

"As the input moves through successive layers the pattern of

1's generated is amplified and results in an unpredictable

avalanche. In the end the final output will have, on average,

half 0's and half 1's . . . ." [p.22]

</BLOCKQUOTE>

<P>Feistel, H. 1973. Cryptography and Computer Privacy.

<I>Scientific American.</I> 228(5): 15-23.

<P>Also see

<A HREF = "#Mixing">mixing</A>,

<A HREF = "#Diffusion">diffusion</A>,

<A HREF = "#OverallDiffusion">overall diffusion</A>,

<A HREF = "#StrictAvalancheCriterion">strict avalanche criterion</A>,

<A HREF = "#Complete">complete</A>,

<A HREF = "#S-Box">S-box</A>, and the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/BINOMPOI.HTM#BitChanges">bit changes</A>

section of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<A NAME = "AvalancheEffect"></A>

<P><DT><B>Avalanche Effect</B>

<DD>The result of

<A HREF = "#Avalanche">avalanche</A>.

As described by Webster and Tavares:

<BLOCKQUOTE>

"For a given transformation to exhibit the avalanche effect,

an average of one half of the output bits should change whenever

a single input bit is complemented." [p.523]

</BLOCKQUOTE>

<P>Webster, A. and S. Tavares. 1985. On the Design of

<A HREF = "#S-Box">S-Boxes</A>.

<I>Advances in Cryptology -- CRYPTO '85.</I> 523-534.

<P>Also see the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/BINOMPOI.HTM#BitChanges">bit changes</A>

section of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<A NAME = "BackDoor"></A>

<P><DT><HR><P><B>Back Door</B>

<DD>A

<A HREF = "#Cipher">cipher</A> design fault, planned or accidental,

which allows the apparent strength of the design to be easily

avoided by those who know the trick. When the design background

of a cipher is kept secret, a back door is often suspected.

Similar to <A HREF = "#TrapDoor">trap door</A>.

<A NAME = "Balance"></A>

<P><DT><B>Balance</B>

<DD>A term used in

<A HREF = "#S-Box">S-box</A> and

<A HREF = "#BooleanFunction">Boolean function</A> analysis. As

described by Lloyd:

<BLOCKQUOTE>

"A function is balanced if, when all input vectors are equally

likely, then all output vectors are equally likely."

</BLOCKQUOTE>

<P>Lloyd, S. 1990. Properties of binary functions.

<I>Advances in Cryptology -- EUROCRYPT '90.</I> 124-139.

<P>There is some desire to generalize this definition to describe

multiple-input functions. (Is a function "balanced" if, for one

value on the first input, all output values can be produced, but

for another value on the first input, only <I>some</I> output values

are possible?) Presumably a two-input balanced function would

be balanced for either input fixed at any value, which would

essentially be a

<A HREF = "#LatinSquare">Latin square</A> or a

<A HREF = "#LatinSquareCombiner">Latin square combiner</A>.

<A NAME = "BalancedBlockMixer"></A>

<P><DT><B>Balanced Block Mixer</B>

<DD>A process or any implementation (for example,

<A HREF = "#Hardware">hardware</A>,

<A HREF = "#Computer">computer</A>

<A HREF = "#Software">software</A>, hybrids, or the like) for performing

<A HREF = "#BalancedBlockMixing">Balanced Block Mixing</A>.

<A NAME = "BalancedBlockMixing"></A>

<P><DT><B>Balanced Block Mixing</B>

<DD>The

<A HREF = "#Block">block</A>

<A HREF = "#Mixing">mixing</A>

<A HREF = "#Mechanism">mechanism</A>

described in U.S. Patent 5,623,549 (see the

<A HREF = "http://www.io.com/~ritter/#BBMTech">BBM articles</A> on the

<A HREF = "http://www.io.com/~ritter/">Ciphers By Ritter</A> page).

<P>A

<A HREF = "#Balance">Balanced</A>

Block Mixer is an <I>m</I>-input-port <I>m</I>-output-port

mechanism with various properties:

<OL>

<P><LI>The overall mapping is one-to-one and invertible: Every

possible input value (over all ports) to the mixer produces

a different output value (including all ports), and every

possible output value is produced by a different input value;

<P><LI>Each output port is a function of every input port;

<P><LI>Any change to any one of the input ports will produce a

change to every output port;

<P><LI>Stepping any one input port through all possible values

(while keeping the other input ports fixed) will step every

output port through all possible values.

</OL>

<P>If we have a two port mixer, with input ports labeled <I>A</I>

and <I>B,</I> output ports labeled <I>X</I> and <I>Y,</I> and some

<A HREF = "#Irreducible">irreducible</A>

<A HREF = "#Mod2Polynomial">mod 2 polynomial</A>

<I>p</I> of degree appropriate to the port size, a Balanced Block Mixer

is formed by the equations:

<BLOCKQUOTE>

X = 3A + 2B (mod 2)(mod p),<BR>

Y = 2A + 3B (mod 2)(mod p).

</BLOCKQUOTE>

<P>This particular BBM is a self-inverse or

<A HREF = "#Involution">involution</A>, and so can be used without

change whether enciphering or deciphering.

One possible value for <I>p</I> for mixing 8-bit values is 100011011.

<P>Balanced Block Mixing functions probably should be thought of as

<A HREF = "#OrthogonalLatinSquares">orthogonal Latin squares</A>.

For example, here is a tiny nonlinear "2-bit" BBM:

<PRE>

3 1 2 0 0 3 2 1 30 13 22 01

0 2 1 3 2 1 0 3 = 02 21 10 33

1 3 0 2 1 2 3 0 11 32 03 20

2 0 3 1 3 0 1 2 23 00 31 12

</PRE>

<P>Suppose we wish to mix (1,3); 1 selects the second row up in both

squares, and 3 selects the rightmost column, thus selecting (2,0)

as the output. Since there is only one occurrence of (2,0) among

all entry pairs, this discrete mixing function is reversible, as well

as being balanced on both inputs.

<P>Cryptographic advantages of balanced block mixing include the fact

that each output is always balanced with respect to either input, and

that no information is lost in the mixing. This allows us to use

balanced block mixing as the "butterfly" operations in a

<A HREF = "#FastWalshTransform">fast Walsh-Hadamard transform</A>

or the well-known

<A HREF = "#FFT">FFT</A>. By using the mixing patterns of these

transforms, we can mix 2<SUP>n</SUP> elements such that each input

is guaranteed to affect each and every output in a balanced way.

And if we use

<A HREF = "#Key">keying</A> to generate the tables, we can have a

way to mix huge blocks in small nonlinear mixing tables with

overall mixing guarantees.

<P>Also see

<A HREF = "#MixingCipher">Mixing Cipher</A>,

<A HREF = "#DynamicSubstitutionCombiner">Dynamic Substitution Combiner</A>,

<A HREF = "#VariableSizeBlockCipher">Variable Size Block Cipher</A>, and the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/ACTIVBBM.HTM">Active

Balanced Block Mixing in JavaScript</A> page of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<A NAME = "BalancedCombiner"></A>

<P><DT><B>Balanced Combiner</B>

<DD>In the context of

<A HREF = "#Cryptography">cryptography</A>, a

<A HREF = "#Combiner">combiner</A>

<A HREF = "#Mixing">mixes</A> two input

values into a result value. A balanced combiner must provide a

<A HREF = "#Balance">balanced</A> relationship between each input

and the result.

<P>In a <I>statically-balanced</I> combiner, any particular result

value can be produced by any value on one input, simply by

selecting some appropriate value for the other input. In this way,

knowledge of only the output value provides no information -- not

even statistical information -- about either input.

<P>The common examples of cryptographic combiner, including byte

<A HREF = "#ExclusiveOR">exclusive-OR</A>

(<A HREF = "#Mod2">mod 2</A>

<A HREF = "#Polynomial">polynomial</A> addition), byte addition

(integer addition <A HREF = "#Modulo">mod</A> 256), or other

<A HREF = "#AdditiveCombiner">"additive" combining</A>, are

perfectly balanced. Unfortunately, these simple combiners are

also very weak, being inherently

<A HREF = "#Linear">linear</A> and without internal

<A HREF = "#State">state</A>.

<P>A <A HREF = "#LatinSquareCombiner">Latin square combiner</A>

is an example of a statically-balanced

reversible nonlinear combiner with massive internal state.

A <A HREF = "#DynamicSubstitutionCombiner">Dynamic Substitution

Combiner</A> is an example of a dynamically or

statistically-balanced reversible nonlinear combiner with

substantial internal state.

<A NAME = "Base64"></A>

<P><DT><B>Base-64</B>

<DD>A public

<A HREF = "#Code">code</A> for converting between

6-<A HREF = "#Bit">bit</A> values 0..63 (or 00..3f

<A HREF = "#Hexadecimal">hex</A>) and text symbols accepted

by most computers:

<PRE>

0 1 2 3 4 5 6 7 8 9 a b c d e f

0 A B C D E F G H I J K L M N O P

1 Q R S T U V W X Y Z a b c d e f

2 g h i j k l m n o p q r s t u v

3 w x y z 0 1 2 3 4 5 6 7 8 9 + /

use "=" for padding

</PRE>

<A NAME = "Bel"></A>

<P><DT><B>Bel</B>

<DD>The base-10 logarithm of the ratio of two

<A HREF = "#Power">power</A> values (which is also the same as

the difference between the log of each power value). The basis

for the more-common term

<A HREF = "#Decibel">decibel</A>: One bel equals 10 decibels.

<A NAME = "BentFunction"></A>

<P><DT><B>Bent Function</B>

<DD>A bent function is a

<A HREF = "#BooleanFunction">Boolean function</A> whose

<A HREF = "#FastWalshTransform">fast Walsh transform</A> has the same

absolute value in each term (except, possibly, the zeroth). This

means that the bent function has the same

<A HREF = "#HammingDistance">distance</A> from every possible

<A HREF = "#AffineBooleanFunction">affine Boolean function</A>.

<P>We can do FWT's in "the bottom panel" at the end of

<A HREF = "http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM">Active

Boolean Function Nonlinearity Measurement in JavaScript</A> page of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<P>Here is every bent sequence of length 4, first in {0,1} notation,

then in {1,-1} notation, with their FWT results:

<PRE>

bent {0,1} FWT bent {1,-1} FWT

0 0 0 1 1 -1 -1 1 1 1 1 -1 2 2 2 -2

0 0 1 0 1 1 -1 -1 1 1 -1 1 2 -2 2 2

0 1 0 0 1 -1 1 -1 1 -1 1 1 2 2 -2 2

1 0 0 0 1 1 1 1 -1 1 1 1 2 -2 -2 -2

1 1 1 0 3 1 1 -1 -1 -1 -1 1 -2 -2 -2 2

1 1 0 1 3 -1 1 1 -1 -1 1 -1 -2 2 -2 2

1 0 1 1 3 1 -1 1 -1 1 -1 -1 -2 -2 2 -2

0 1 1 1 3 -1 -1 -1 1 -1 -1 -1 -2 2 2 2

</PRE>

These sequences, like all true bent sequences, are <B>not</B>

<A HREF = "#Balance">balanced</A>, and the zeroth element of the

{0,1} FWT is the number of 1's in the sequence.

<P>Here are some bent sequences of length 16:

<PRE>

bent {0,1} 0 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0

FWT 6,-2,2,-2,2,-2,2,2,-2,-2,2,-2,-2,2,-2,-2

bent {1,-1} 1 -1 1 1 1 -1 1 1 -1 -1 1 -1 1 1 -1 1

FWT 4,4,-4,4,-4,4,-4,-4,4,4,-4,4,4,-4,4,4

bent {0,1} 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0

FWT 6,2,2,-2,-2,2,-2,2,-2,-2,-2,-2,2,2,-2,-2

bent {1,-1} 1 1 -1 1 1 -1 1 1 -1 1 1 1 -1 -1 -1 1

FWT 4,-4,-4,4,4,-4,4,-4,4,4,4,4,-4,-4,4,4

</PRE>

<P>Bent sequences are said to have the highest possible uniform

nonlinearity. But, to put this in perspective, recall that we

<I>expect</I> a random sequence of 16 bits to have 8 bits different

from any particular sequence, linear or otherwise. That is also

the <I>maximum possible</I> nonlinearity, and here we actually

<I>get</I> a nonlinearity of 6.

<P>There are various more or less complex constructions for these

sequences. In most cryptographic uses, bent sequences are modified

slightly to achieve balance.

<A NAME = "BernoulliTrials"></A>

<P><DT><B>Bernoulli Trials</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, observations or sampling

with replacement which has exactly two possible outcomes, typically

called "success" and "failure." Bernoulli trials have these

characteristics:

<UL>

<LI>Each trial is independent,

<LI>Each outcome is determined only by chance, and

<LI>The probability of success is fixed.

</UL>

<P>Bernoulli trials have a

<A HREF = "#BinomialDistribution">Binomial distribution</A>.

<A NAME = "Bijective"></A>

<P><DT><B>Bijective</B>

<DD>A <A HREF = "#Mapping">mapping</A> f: <I>X -> Y</I> which is

both

<A HREF = "#OneToOne">one-to-one</A> and

<A HREF = "#Onto">onto</A>.

For each unique <I>x</I> in <I>X</I> there is corresponding

unique <I>y</I> in <I>Y</I>.

An invertible mapping function.

<A NAME = "Binary"></A>

<P><DT><B>Binary</B>

<DD>From the Latin for "dual" or "pair." Dominantly used to indicate

"base 2": The numerical representation in which each digit has an

<A HREF = "#Alphabet">alphabet</A> of only two symbols: 0 and 1.

This is just one particular

<A HREF = "#Code">coding</A> or representation of a value which

might otherwise be represented (with the exact same value) as

<A HREF = "#Octal">octal</A> (base 8),

<A HREF = "#Decimal">decimal</A> (base 10), or

<A HREF = "#Hexadecimal">hexadecimal</A> (base 16). Also see

<A HREF = "#Bit">bit</A> and

<A HREF = "#Boolean">Boolean</A>.

<P>Possibly also the confusing counterpart to

<A HREF = "#Unary">unary</A> when describing the number of inputs

or arguments to a function, but

<A HREF = "#Dyadic">dyadic</A> is almost certainly a better choice.

<A NAME = "BinomialDistribution"></A>

<P><DT><B>Binomial Distribution</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, the probability of finding

exactly <I>k</I> successes in <I>n</I> independent

<A HREF = "#BernoulliTrials">Bernoulli trials</A>, when

each trial has success probability <I>p</I>:

<PRE>

n k n-k

P(k,n,p) = ( ) p (1-p)

k

</PRE>

<P>This ideal

<A HREF = "#Distribution">distribution</A> is produced by evaluating

the probability function for all possible <I>k,</I> from 0 to

<I>n.</I>

<P>If we have an experiment which we think <I>should</I> produce a

binomial distribution, and then repeatedly and systematically find

very improbable test values, we may choose to reject the

<A HREF = "#NullHypothesis">null hypothesis</A> that the experimental

distribution is in fact binomial.

<P>Also see the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/BINOMPOI.HTM#Binomial">binomial</A>

section of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<A NAME = "BirthdayAttack"></A>

<P><DT><B>Birthday Attack</B>

<DD>A form of

<A HREF = "#Attack">attack</A> in which it is necessary to obtain

two identical values from a large

<A HREF = "#Population">population</A>. The "birthday"

part is the realization that it is far easier to find an arbitrary

matching pair than to match any particular value. Often a

<A HREF = "#Hash">hash</A> attack.

<P>Also see:

<A HREF = "#BirthdayParadox">birthday paradox</A>.

<A NAME = "BirthdayParadox"></A>

<P><DT><B>Birthday Paradox</B>

<DD>The apparent paradox that, in a schoolroom of only 23 students,

there is a 50 percent probability that at least two will have the

same birthday. The "paradox" is that we have an even chance of

success with at most 23 different days represented.

<P>The "paradox" is resolved by noting that we have a 1/365 chance

of success for each possible <I>pairing</I> of students, and there

are 253 possible pairs or

<A HREF = "#Combination">combinations</A> of 23 things taken 2 at

a time. (To count the number of pairs, we can choose any of the 23

students as part of the pair, then any of the 22 remaining students

as the other part. But this counts each pair twice, so we have

<NOBR>23 * 22 / 2 = 253</NOBR> different pairs.)

<P>We can compute the overall probability of success from the

probability of <I>failure</I> <NOBR>(1 - 1/365 = 0.99726)</NOBR>

multiplied by itself for each pair. The overall probability of

failure is thus 0.99726<SUP>253</SUP> (0.99726 to the 253rd power)

or 0.4995. So the success probability for 253 pairs is 0.5005.

<P>We can relate the probability of finding at least one "double"

of some birthday (Pd) to the expected number of doubles (Ed) as:

<PRE>

<BIG><TTY>Pd = 1 - e<SUP>-Ed</SUP></TTY></BIG> ,

so

<BIG><TTY>Ed = -Ln( 1 - Pd )</TTY></BIG>

and

<BIG><TTY>365 * -Ln( 0.5 ) = 365 * 0.693 = 253</TTY></BIG> .

</PRE>

<P>Also see:

<A HREF = "ARTS/BIRTHDAY.HTM">Estimating Population from Repetitions

in Accumulated Random Samples</A>, my "birthday" article.

<A NAME = "Bit"></A>

<P><DT><B>Bit</B>

<DD>A contraction of

"<A HREF = "#Binary">binary</A> digit." The smallest possible unit

of information. A

<A HREF = "#Boolean">Boolean</A> value: True or False; Yes or No;

one or zero; Set or Cleared. Virtually all information to be

communicated or stored digitally is

<A HREF = "#Code">coded</A> in some way which

fundamentally relies on individual bits. Alphabetic characters

are often stored in eight bits, which is a

<A HREF = "#Byte">byte</A>.

<A NAME = "Block"></A>

<P><DT><B>Block</B>

<DD>Some amount of data treated as a single unit. For example, the

<A HREF = "#DES">DES</A>

<A HREF = "#BlockCipher">block cipher</A> has a

64-<A HREF = "#Bit">bit</A> block. So DES ciphers 64 bits (8

<A HREF = "#Byte">bytes</A> or typically 8

<A HREF = "#ASCII">ASCII</A> characters) at once.

<P>A 64-bit block supports 2<SUP>64</SUP> or about

<NOBR>1.8 x 10<SUP>19</SUP></NOBR> block values or code values.

Each different

<A HREF = "#Permutation">permutation</A> of those values can be

considered a complete

<A HREF = "#Code">code</A>. A block cipher has the ability to

select from among many such codes using a

<A HREF = "#Key">key</A>.

<P>It is not normally possible to block-cipher just a single

<A HREF = "#Bit">bit</A> or a single

<A HREF = "#Byte">byte</A> of a block.

An arbitrary stream of data can always be partitioned into one

or more fixed-size blocks, but it is likely that at least one

block will not be completely filled. Using fixed-size blocks

generally means that the associated system must support data

expansion in enciphering, if only by one block. Handling even

minimal data expansion may be difficult in some systems.

<A NAME = "BlockCipher"></A>

<P><DT><B>Block Cipher</B>

<DD>A

<A HREF = "#Cipher">cipher</A> which requires the accumulation

of data (in a

<A HREF = "#Block">block</A>) before ciphering can complete.

Other than simple

<A HREF = "#Transposition">transposition</A> ciphers, this seems

to be the province of ciphers designed to <I>emulate</I> a

<A HREF = "#Key">keyed</A>

<A HREF = "#SimpleSubstitution">simple substitution</A> with a

<A HREF = "#SubstitutionTable">table</A> of size far too large to

realize. A block cipher operates on a

<A HREF = "#Block">block</A> of data (for example, multiple

<A HREF = "#Byte">bytes</A>) in a single ciphering, as opposed to a

<A HREF = "#StreamCipher">stream cipher</A>, which operates on

bytes or

<A HREF = "#Bit">bits</A> as they occur. Block ciphers can be called

"<A HREF = "#Codebook">codebook</A>-style" ciphers. Also see

<A HREF = "#VariableSizeBlockCipher">Variable Size Block Cipher</A>.

<P>A <A HREF = "#BlockCipher">block cipher</A> is a transformation

between

<A HREF = "#Plaintext">plaintext</A> block values and

<A HREF = "#Ciphertext">ciphertext</A> block values, and is thus an

emulated

<A HREF = "#SimpleSubstitution">simple substitution</A> on huge

block-wide values. Within a particular block size, both plaintext

and ciphertext have the same set of possible values, and when the

ciphertext values have the same ordering as the plaintext, ciphering

is obviously ineffective. So <I>effective</I> ciphering depends upon

<I>re-arranging</I> the ciphertext values from the plaintext

ordering, and this is a

<A HREF = "#Permutation">permutation</A> of the plaintext values.

A block cipher is <A HREF = "#Key">keyed</A> by constructing a

<I>particular</I> permutation of ciphertext values.

<H4>Block Cipher Data Diffusion</H4>

<P>In an ideal block cipher, changing even a single bit of the

input block will change all bits of the ciphertext result, each

with independent probability 0.5. This means that about half of

the bits in the output will change for any different input block,

even for differences of just one bit. This is

<A HREF = "#OverallDiffusion">overall diffusion</A> and is

present in a block cipher, but not in a

<A HREF = "#StreamCipher">stream cipher</A>. Data diffusion is

a simple consequence of the keyed invertible simple substitution

nature of the ideal block cipher.

<P>Improper diffusion of data throughout a block cipher can have

serious strength implications. One of the functions of data

diffusion is to hide the different effects of different internal

components. If these effects are not in fact hidden, it may be

possible to attack each component separately, and break the

whole cipher fairly easily.

<H4>Partitioning Messages into Fixed Size Blocks</H4>

<P>A large message can be ciphered by partitioning the plaintext

into blocks of a size which can be ciphered. This essentially

creates a stream meta-cipher which repeatedly uses the same block

cipher transformation. Of course, it is also possible to re-key

the block cipher for each and every block ciphered, but this is

usually expensive in terms of computation and normally unnecessary.

<P>A message of arbitrary size can always be partitioned into some

number of whole blocks, with possibly some space remaining in the

final block. Since partial blocks cannot be ciphered, some

random

<A HREF = "#Padding">padding</A> can be introduced to fill out the

last block, and this naturally expands the ciphertext. In this

case it may also be necessary to introduce some sort of structure

which will indicate the number of valid bytes in the last block.

<H4>Block Partitioning without Expansion</H4>

<P>Proposals for using a block cipher supposedly <I>without</I>

data expansion may involve creating a tiny

<A HREF = "#StreamCipher">stream cipher</A> for the last block.

One scheme is to re-encipher the ciphertext of the preceding

block, and use the result as the

<A HREF = "#ConfusionSequence">confusion sequence</A>. Of course,

the cipher designer still needs to address the situation of files

which are so short that they <I>have</I> no preceding block.

Because the one-block version is <I>in fact</I> a stream cipher,

we must be very careful to never re-use a confusion sequence.

But when we only <I>have</I> one block, there <I>is</I> no prior

block to change as a result of the data. In this case, ciphering

several very short files could expose those files quickly.

Furthermore, it is dangerous to encipher a

<A HREF = "#CRC">CRC</A> value in such a block, because

exclusive-OR enciphering is transparent to the field of mod 2

polynomials in which the CRC operates. Doing this could allow an

Opponent to adjust the message CRC in a known way, thus avoiding

authentication exposure.

<P>Another proposal for eliminating data expansion consists of

ciphering blocks until the last short block, then re-positioning

the ciphering window to end at the last of the data, thus

re-ciphering part of the prior block. This is a form of chaining

and establishes a sequentiality requirement which requires that

the last block be deciphered <I>before</I> the next-to-the-last

block. Or we can make enciphering inconvenient and deciphering

easy, but one way will be a problem. And this approach cannot

handle very short messages: its minimum size is one block. Yet

any general-purpose ciphering routine <I>will</I> encounter short

messages. Even worse, if we have a short message, we still need

to somehow indicate the correct length of the message, and this

must expand the message, as we saw before. Thus, overall, this

seems a somewhat dubious technique.

<P>On the other hand, it does show a way to chain blocks for

authentication in a large-block cipher: We start out by

enciphering the data in the first block. Then we position the

next ciphering to start <I>inside</I> the ciphertext of the previous

block. Of course this would mean that we would have to decipher

the message in reverse order, but it would also propagate any

ciphertext changes through the end of the message. So if we add

an authentication field at the end of the message (a keyed value

known on both ends), and that value is recovered upon deciphering

(this will be the first block deciphered) we can authenticate the

whole message. But we still need to handle the last block

padding problem and possibly also the short message problem.

<H4>Block Size and Plaintext Randomization</H4>

<P>Ciphering raw plaintext data can be dangerous when the cipher

has a small block size. Language plaintext has a strong, biased

distribution of symbols and ciphering raw plaintext would

effectively reduce the number of possible plaintexts blocks.

Worse, some plaintexts would be vastly more probable than others,

and if some

<A HREF = "#KnownPlaintextAttack">known plaintext</A> were available,

the most-frequent blocks might already be known. In this way,

small blocks can be vulnerable to classic

<A HREF = "#CodebookAttack">codebook attacks</A> which

build up the ciphertext equivalents for many of the plaintext

phrases. This sort of attack confronts a particular block size,

and for these attacks Triple-DES is no stronger than simple DES,

because they both have the same block size.

<P>The usual way of avoiding these problems is to randomize

the plaintext block with an

<A HREF = "#OperatingMode">operating mode</A> such as

<A HREF = "#CBC">CBC</A>. This can ensure that the plaintext

data which is actually ciphered is evenly distributed across

all possible block values. However, this also requires an

<A HREF = "#IV">IV</A> which thus expands the ciphertext.

<P>Another approach is to apply data compression to the plaintext

before enciphering. If this is to be used <I>instead</I> of

plaintext randomization, the designer must be very careful that

the data compression does not contain regular features which

could be exploited by The Opponents.

<P>An alternate approach is to use blocks of sufficient size

for them to be expected to have a substantial amount of uniqueness

or "entropy." If we expect plaintext to have about one bit of

entropy per byte of text, we might want a block size of at

least 64 bytes before we stop worrying about an uneven

distribution of plaintext blocks. This is now a practical

block size.

<A NAME = "Boolean"></A>

<P><DT><B>Boolean</B>

<DD>TRUE or FALSE; one

<A HREF = "#Bit">bit</A> of information.

<A NAME = "BooleanFunction"></A>

<P><DT><B>Boolean Function</B>

<DD>A function which produces a

<A HREF = "#Boolean">Boolean</A> result</A>. The individual output

<A HREF = "#Bit">bits</A> of an

<A HREF = "#S-Box">S-box</A> can each be considered to be

separate Boolean functions.

<A NAME = "BooleanFunctionNonlinearity"></A>

<P><DT><B>Boolean Function Nonlinearity</B>

<DD>The number of

<A HREF = "#Bit">bits</A> which must change in the

<A HREF = "#TruthTable">truth table</A> of a

<A HREF = "#BooleanFunction">Boolean function</A> to reach the closest

<A HREF = "#AffineBooleanFunction">affine Boolean function</A>.

This is the

<A HREF = "#HammingDistance">Hamming distance</A> from the closest

"<A HREF = "#Linear">linear</A>" function.

<P>Typically computed by using a

<A HREF = "#FastWalshTransform">fast Walsh-Hadamard transform</A>

on the

<A HREF = "#Boolean">Boolean</A>-valued truth table of the function.

This produces the

<A HREF = "#UnexpectedDistance">unexpected distance</A> to every

possible affine Boolean function (of the given length). Scanning

those results for the maximum value implies the minimum distance

to some particular affine sequence.

<P>Especially useful in

<A HREF = "#S-Box">S-box</A> analysis, where the nonlinearity for

the

<A HREF = "#SubstitutionTable">table</A> is often taken to be the

minimum of the nonlinearity values computed for each output bit.

<P>Also see the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM">Active

Boolean Function Nonlinearity Measurement in JavaScript</A> page of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<A NAME = "BooleanLogic"></A>

<P><DT><B>Boolean Logic</B>

<DD>The

<A HREF = "#Logic">logic</A> which applies to variables which have

only two possible values. Also the

<A HREF = "#Digital">digital</A>

<A HREF = "#Hardware">hardware</A> devices which realize such

logic, and are used to implement a

<A HREF = "#Electronic">electronic</A> digital

<A HREF = "#Computer">computers</A>.

<A NAME = "BooleanMapping"></A>

<P><DT><B>Boolean Mapping</B>

<DD>A

<A HREF = "#Mapping">mapping</A> of some number <I>n</I>

<A HREF = "#Boolean">Boolean</A> variables into

some number <I>m</I> Boolean results.

For example, an

<A HREF = "#S-Box">S-box</A>.

<A NAME = "Break"></A>

<P><DT><B>Break</B>

<DD>The result of a successful

<A HREF = "#Cryptanalysis">cryptanalytic</A>

<A HREF = "#Attack">attack</A>.

To destroy the advantage of a

<A HREF = "#Cipher">cipher</A>

in hiding information.

<P>A

<A HREF = "#Cipher">cipher</A> is "broken" when the information in

a message can be extracted without the

<A HREF = "#Key">key</A>, or when the key itself can be recovered.

The <A HREF = "#Strength">strength</A> of a cipher can be considered

to be the minimum effort required for a break, by any possible

attack. A break is particularly significant when the work involved

need not be repeated on every message.

<P>The use of the term "break" can be misleading when an impractical

amount of work is required to achieve the break. This case might

be better described a "theoretical" or "certificational"

<I>weakness</I>.

<A NAME = "BlockSize"></A>

<P><DT><B>Block Size</B>

<DD>The amount of data in a

<A HREF = "#Block">block</A>. For example, the size of the

<A HREF = "#DES">DES</A> block is 64

<A HREF = "#Bit">bits</A> or 8

<A HREF = "#Byte">bytes</A> or 8 octets.

<A NAME = "BruteForceAttack"></A>

<P><DT><B>Brute Force Attack</B>

<DD>A form of

<A HREF = "#Attack">attack</A> in which each possibility is tried

until success is obtained. Typically, a

<A HREF = "#Ciphertext">ciphertext</A> is

<A HREF = "#Decipher">deciphered</A>

under different

<A HREF = "#Key">keys</A> until

<A HREF = "#Plaintext">plaintext</A> is recognized. On average,

this may take about half as many decipherings as there are keys.

<P>Recognizing plaintext may or may not be easy. Even when the

key length of a cipher is sufficient to prevent brute force attack,

that key will be far too small to produce every possible plaintext

from a given ciphertext (see

<A HREF = "#PerfectSecrecy">perfect secrecy</A>). Combined with

the fact that language is redundant, this means that very few of

the decipherings will be words in proper form. Of course, if the

plaintext is not language, but is instead computer code, compressed

text, or even ciphertext from another cipher, recognizing a correct

deciphering can be difficult.

<P>Brute force is the obvious way to attack a cipher, and the way

any cipher can be attacked, so ciphers are designed to have a large

enough

<A HREF = "#Keyspace">keyspace</A> to make this much too expensive

to use in practice. Normally, the design

<A HREF = "#Strength">strength</A> of a cipher is based on the

cost of a brute-force attack.

<A NAME = "Bug"></A>

<P><DT><B>Bug</B>

<DD>Technical slang for "error in design or implementation."

An unexpected

<A HREF = "#System">system</A> flaw.

<A HREF = "#Debug">Debugging</A> is a normal part of system

development and interactive

<A HREF = "#SystemDesign">system design</A>.

<A NAME = "Byte"></A>

<P><DT><B>Byte</B>

<DD>A collection of eight

<A HREF = "#Bit">bits</A>. Also called an "octet." A byte

can represent 256 different values or symbols. The common 7-bit

<A HREF = "#ASCII">ASCII</A> codes used to represent characters

in

<A HREF = "#Computer">computer</A> use are generally stored

in a byte; that is, one byte per character.

<A NAME = "Capacitor"></A>

<P><DT><HR><P><B>Capacitor</B>

<DD>A basic

<A HREF = "#Electronic">electronic</A>

<A HREF = "#Component">component</A>

which acts as a reservoir for electrical power in the form of

<A HREF = "#Voltage">voltage</A>.

A capacitor thus acts to "even out" the voltage across its terminals,

and to "conduct" voltage changes from one terminal to the other.

A capacitor "blocks"

<A HREF = "#DC">DC</A> and conducts

<A HREF = "#AC">AC</A> in proportion to

<A HREF = "#Frequency">frequency</A>.

Capacitance is measured in Farads: A

<A HREF = "#Current">current</A> of 1 Amp into a capacitance

of 1 Farad produces a voltage change of 1 Volt per Second across

the capacitor.

<P>Typically, two

<A HREF = "#Conductor">conductive</A> "plates" or metal foils

separated by a thin

<A HREF = "#Insulator">insulator</A>, such as air, paper, or

ceramic.

An electron charge on one plate attracts the opposite charge on the

other plate, thus "storing" charge.

A capacitor can be used to collect a small current over long time,

and then release a high current for a short time, as used in a

camera strobe or "flash."

<P>Also see

<A HREF = "#Inductor">inductor</A> and

<A HREF = "#Resistor">resistor</A>.

<A NAME = "CBC"></A>

<P><DT><B>CBC</B>

<DD>CBC or Cipher Block Chaining is an

<A HREF = "#OperatingMode">operating mode</A> for

<A HREF = "#BlockCipher">block ciphers</A>.

CBC mode is essentially a crude

meta-<A HREF = "#StreamCipher">stream cipher</A> which streams block

transformations.

<P>In CBC mode the

<A HREF = "#Ciphertext">ciphertext</A> value of the preceding

<A HREF = "#Block">block</A> is

<A HREF = "#ExclusiveOR">exclusive-OR</A> combined with the

<A HREF = "#Plaintext">plaintext</A> value for the current block.

This has the effect of distributing the combined block values

evenly among all possible block values, and so prevents

<A HREF = "#CodebookAttack">codebook attacks</A>.

<P>On the other hand, ciphering the <I>first</I> block generally

requires an

<A HREF = "#IV">IV</A> or initial value to start the process.

The IV necessarily expands the ciphertext, which may or may not

be a problem.

And the IV must be dynamically random-like so that statistics

cannot be developed on the first block of each message sent under

the same key.

<P>In CBC mode, each random-like confusing value is the ciphertext

from each previous block. Clearly this ciphertext is exposed to

The Opponent, so there would seem to be little benefit associated

with hiding the IV, which is just the first of these values.

But if The Opponent knows the first sent plaintext, and can

intercept and change the message IV, The Opponent can manipulate

the first block of received plaintext. Because the IV does not

represent a message enciphering, manipulating this value does not

also change any previous block.

<P>Accordingly, the IV may be sent enciphered or may be specifically

authenticated in some way. Alternately, the complete body of the

plaintext message may be

<A HREF = "#Authentication">authenticated</A>, often by a

<A HREF = "#CRC">CRC</A>. The CRC remainder should be block ciphered,

perhaps as part of the plaintext.

<A NAME = "cdf"></A>

<P><DT><B>c.d.f.</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, <I>cumulative

<A HREF = "#Distribution">distribution</A> function.</I>

A function which gives the probability of obtaining a particular

value or lower.

<A NAME = "CFB"></A>

<P><DT><B>CFB</B>

<DD>CFB or Ciphertext FeedBack is an

<A HREF = "#OperatingMode">operating mode</A> for a

<A HREF = "#BlockCipher">block cipher</A>.

<P>CFB is closely related to

<A HREF = "#OFB">OFB</A>, and is intended to provide some of the

characteristics of a

<A HREF = "#StreamCipher">stream cipher</A> from a block cipher.

CFB generally forms an

<A HREF = "#Autokey">autokey</A> stream cipher.

CFB is a way of using a block cipher to form a

<A HREF = "#RandomNumberGenerator">random number generator</A>.

The resulting

<A HREF = "#PseudoRandom">pseudorandom</A>

<A HREF = "#ConfusionSequence">confusion sequence</A> can be

<A HREF = "#Combiner">combined</A> with data as in the usual

stream cipher.

<P>CFB assumes a

<A HREF = "#ShiftRegister">shift register</A> of the block cipher

<A HREF = "#Block">block</A> size. An

<A HREF = "#IV">IV</A> or initial value first fills the register,

and then is ciphered. Part of the result, often just a single

<A HREF = "#Byte">byte</A>, is used to cipher data, and the

resulting

<A HREF = "#Ciphertext">ciphertext</A> is also

shifted into the register. The new register value is ciphered,

producing another confusion value for use in stream ciphering.

<P>One disadvantage of this, of course, is the need for a full

block-wide ciphering operation, typically for each data byte

ciphered. The advantage is the ability to cipher individual

characters, instead of requiring accumulation into a block

before processing.

<A NAME = "Chain"></A>

<P><DT><B>Chain</B>

<DD>An operation repeated in a sequence, such that each result

depends upon the previous result, or an

<A HREF = "#IV">initial value</A>.

One example is the

<A HREF = "#CBC">CBC</A> operating mode.

<A NAME = "Chaos"></A>

<P><DT><P><B>Chaos</B>

<DD>The unexpected ability to find numerical relationships in

physical processes formerly considered

<A HREF = "#Random">random</A>. Typically these take the form

of iterative applications of fairly simple computations.

In a chaotic system, even tiny changes in

<A HREF = "#State">state</A> eventually lead to major changes

in state; this is called "sensitive dependence on initial

conditions." It has been argued that every good computational

<A HREF = "#RandomNumberGenerator">random number generator</A>

is "chaotic" in this sense.

<P>In physics, the "state" of an

<A HREF = "#Analog">analog</A> physical system cannot be

fully measured, which always leaves some remaining uncertainty to

be magnified on subsequent steps. And, in many cases, a physical

system may be slightly affected by thermal noise and thus continue

to accumulate new information into its "state."

<P>In a

<A HREF = "#Computer">computer</A>, the state of the

<A HREF = "#Digital">digital</A>

<A HREF = "#System">system</A> is explicit and

complete, and there is no uncertainty. No noise is accumulated.

All operations are completely

<A HREF = "#Deterministic">deterministic</A>. This means that, in a

computer, even a "chaotic" computation is completely predictable

and repeatable.

<A NAME = "ChiSquare"></A>

<P><DT><B>Chi-Square</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, a

<A HREF = "#GoodnessOfFit">goodness of fit</A> test used for

comparing two

<A HREF = "#Distribution">distributions</A>. Mainly used on

<A HREF = "#Nominal">nominal</A> and

<A HREF = "#Ordinal">ordinal</A> measurements. Also see:

<A HREF = "#KolmogorovSmirnov">Kolmogorov-Smirnov</A>.

<P>In the usual case, many independent samples are counted by

category or separated into value-range "bins." The reference

distribution gives us the the number of values to expect in

each bin. Then we compute a X<SUP>2</SUP> test

<A HREF = "#Statistic">statistic</A> related to the difference

between the distributions:

<PRE>

X<SUP>2</SUP> = SUM( SQR(Observed[i] - Expected[i]) / Expected[i] )

</PRE>

<P>("SQR" is the squaring function, and we require that each

expectation not be zero.) Then we use a

tabulation of chi-square statistic values to look up the probability

that a particular X<SUP>2</SUP> value or lower (in the

<A HREF = "#cdf">c.d.f.</A>) would occur by random sampling if both

distributions were the same. The statistic also depends upon the

"<A HREF = "#DegreesOfFreedom">degrees of freedom</A>," which is

almost always one less than the final number of bins. See the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/NORMCHIK.HTM#ChiSquare">chi-square</A>

section of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages.

<P>The <A HREF = "#cdf">c.d.f.</A> percentage for a particular

chi-square value is the area of the statistic distribution to the

left of the statistic value; this is the probability of obtaining

that statistic value <I>or less</I> by random selection when testing

two distributions which are exactly the same. Repeated trials which

randomly sample two identical distributions should produce about the

same number of X<SUP>2</SUP> values in each quarter of the distribution

(0% to 25%, 25% to 50%, 50% to 75%, and 75% to 100%). So if we

repeatedly find only very high percentage values, we can assume that

we are probing different distributions. And even a single very high

percentage value would be a matter of some interest.

<P>Any statistic probability can be expressed either as the

proportion of the area to the <I>left</I> of the statistic value

(this is the "cumulative distribution function" or c.d.f.), or as

the area to the <I>right</I> of the value (this is the "upper tail").

Using the upper tail representation for the X<SUP>2</SUP> distribution

can make sense because the usual chi-squared test is a "one tail" test

where the decision is always made on the upper tail. But the

"upper tail" has an opposite "sense" to the c.d.f., where higher

statistic values always produce higher percentage values.

Personally, I find it helpful to describe all statistics by their

c.d.f., thus avoiding the use of a wrong "polarity" when interpreting

any particular statistic. While it is easy enough to convert from

the c.d.f. to the complement or vise versa (just subtract from 1.0),

we can base our arguments on either form, since the statistical

implications are the same.

<P>It is often unnecessary to use a statistical test if we just want

to know whether a function is producing something like the expected

distribution: We can <I>look</I> at the binned values and

generally get a good idea about whether the distributions change in

similar ways at similar places. A good rule-of-thumb is to expect

chi-square totals similar to the number of bins, but distinctly

different distributions often produce huge totals far beyond the

values in any table, and computing an exact probability for such

cases is simply irrelevant. On the other hand, it can be very

useful to perform 20 to 40 independent experiments to look for a

reasonable statistic distribution, rather than simply making a

"yes / no" decision on the basis of what might turn out to be a

rather unusual result.

<P>Since we are accumulating <I>discrete</I> bin-counts, any

fractional expectation will always differ from any actual count.

For example, suppose we expect an

<A HREF = "#UniformDistribution">even distribution</A>, but have many

bins and so only accumulate enough samples to observe about 1 count

for every 2 bins. In this situation, the absolute best sample

we could hope to see would be something like (0,1,0,1,0,1,...),

which would represent an even, balanced distribution over the range.

But even in this best possible case we would still be off by half

a count in each and every bin, so the chi-square result would not

properly characterize this best possible sequence. Accordingly, we

need to accumulate enough samples so that the quantization which

occurs in binning does not appreciably affect the accuracy of the

result. Normally I try to expect at least 10 counts in each bin.

<P>But when we have a reference distribution that trails off toward

zero, <I>inevitably</I> there will be some bins with few counts.

Taking more samples will just expand the range of bins, some of which

will be lightly filled in any case. We can avoid quantization error

by summing both the observations and expectations from multiple bins,

until we get a reasonable expectation value (again, I like to see 10

counts or more). In this way, the "tails" of the distribution can

be more properly (and legitimately) characterized.

<A NAME = "Cipher"></A>

<P><DT><B>Cipher</B>

<DD>In general, a

<A HREF = "#Key">key</A>-selected secret transformation between

<A HREF = "#Plaintext">plaintext</A> and

<A HREF = "#Ciphertext">ciphertext</A>.

Specifically, a secrecy

<A HREF = "#Mechanism">mechanism</A> or process which operates on

individual characters or

<A HREF = "#Bit">bits</A> independent of semantic content.

As opposed to a secret

<A HREF = "#Code">code</A>, which generally operates on words,

phrases or sentences, each of which may carry some amount of

complete meaning. Also see:

<A HREF = "#Cryptography">cryptography</A>,

<A HREF = "#BlockCipher">block cipher</A>,

<A HREF = "#StreamCipher">stream cipher</A>,

<A HREF = "#CipherTaxonomy"><NOBR>a cipher taxonomy</NOBR></A>, and

<A HREF = "#Substitution">substitution</A>.

<P>A good cipher can transform secret information into a multitude

of different intermediate forms, each of which represents the original

information. <I>Any</I> of these intermediate forms or ciphertexts

can be produced by ciphering the information under a particular key

value. The intent is that the original information only be exposed

by <I>one</I> of the many possible keyed interpretations of that

ciphertext. Yet the correct interpretation is available merely by

deciphering under the appropriate key.

<P>A cipher appears to reduce the protection of secret information

to enciphering under some key, and then keeping that key secret.

This is a great reduction of effort and potential exposure, and is

much like keeping your valuables in your house, and then locking

the door when you leave. But there are also similar limitations

and potential problems.

<P>With a good cipher, the resulting ciphertext can be stored or

transmitted otherwise exposed without also exposing the secret

information hidden inside. This means that ciphertext can be stored

in, or transmitted through, systems which have no secrecy protection.

For transmitted information, this also means that the cipher itself

must be distributed in multiple places, so in general the cipher

cannot be assumed to be secret. With a good cipher, only the

deciphering key need be kept secret.

<A NAME = "CipherTaxonomy"></A>

<P><DT><B>A Cipher Taxonomy</B>

<DD>For the analysis of cipher operation it is useful to collect

ciphers into groups based on their functioning (or <I>intended</I>

functioning). The goal is to group ciphers which are <I>essentially

similar,</I> so that as we gain an understanding of one cipher, we

can apply that understanding to others in the same group. We thus

classify <I>not</I> by the

<A HREF = "#Component">components</A> which make up the cipher, but

instead on the "black-box" operation of the cipher itself.

<P>We seek to hide distinctions of size, because <I>operation</I>

is independent of size, and because size effects are usually

straightforward. We thus classify serious

<A HREF = "#BlockCipher">block ciphers</A> as

<A HREF = "#Key">keyed</A>

<A HREF = "#SimpleSubstitution">simple substitution</A>, just like

newspaper amusement ciphers, despite their obvious differences in

strength and construction. This allows us to compare the results

from an ideal tiny cipher to those from a large cipher construction;

the grouping thus can provide <I>benchmark</I> characteristics for

measuring large cipher constructions.

<P>We <I>could</I> of course treat each cipher as an entity unto

itself, or relate ciphers by their dates of discovery, the tree of

developments which produced them, or by known strength. But each of

these criteria is more or less limited to telling us "this cipher is

what it is." We already know that. What we <I>want</I> to know is

what other ciphers function in a similar way, and then whatever is

known about <I>those</I> ciphers. In this way, every cipher need

not be an island unto itself, but instead can be judged and compared

in a related community of similar techniques.

<P>Our primary distinction is between ciphers which handle all the

data at once

(<A HREF = "#BlockCipher">block ciphers</A>), and those which handle

some, then some more, then some more

(<A HREF = "#StreamCipher">stream ciphers</A>). We thus see the

usual repeated use of a block cipher as a stream <I>meta-cipher</I>

which has the block cipher as a component.

It is also possible for a stream cipher to be re-keyed or re-originate

frequently, and so appear to operate on "blocks." Such a cipher,

however, would not have the

<A HREF = "#OverallDiffusion">overall diffusion</A> we normally

associate with a block cipher, and so might usefully be regarded as

a stream meta-cipher with a stream cipher component.

<P>The goal is not to give each cipher a label, but instead to seek

insight. Each cipher in a particular general class carries with it

the consequences of that class. And because these groupings ignore

size, we are free to generalize from the small to the large and so

predict effects which may be unnoticed in full-size ciphers. <P>

<OL TYPE = A>

<BIG><B>

<LI><A HREF = "#BlockCipher">BLOCK CIPHER</B></BIG></A>

<BR>A block cipher <I>requires</I> the accumulation of some amount

of data or multiple data elements for ciphering to complete.

(Sometimes stream ciphers accumulate data for convenience, as

in cylinder ciphers, which nevertheless logically cipher each

character independently.)

<P>(Note that this definition is somewhat

broader than the now common understanding of a huge, and thus

<I>emulated,</I> Simple Substitution. But there are ciphers

which require blocked plaintext and which do <I>not</I> emulate

Simple Substitution, and calling these something other than

"block" ciphers negates the advantage of a taxonomy.)

<P><OL TYPE = 1>

<B><LI><A HREF = "#Substitution">SUBSTITUTION</A> CIPHER</B>

<UL>

<LI>A "codebook" or "simple substitution."

<LI>Each code value becomes a distinguishable element.

Thus, substitution generally converts a collection of

independent elements to a single related unit.

<LI>Keying constitutes a <A HREF = "#Permutation">permutation</A>

or re-arrangement of the fixed set of possible

<A HREF = "#Code">code</A> values.

<LI><A HREF = "#Avalanche">Avalanche</A> or data

<A HREF = "#Diffusion">diffusion</A> is a natural

consequence of an arbitrary selection among all possible

code values.

<LI>The usual complete binary substitution distributes

bit-changes between code values binomially, and this

effect can be sampled and examined statistically.

<LI>Avalanche is two-way diffusion in the sense that "later"

plaintext can change "earlier" ciphertext.

<LI>A conventional block cipher is built from small components

with a design intended to <I>simulate</I> a substitution

table of a size vastly larger than anything which could be

practically realized.

</UL>

<P><OL TYPE = a>

<B><LI><A HREF = "#Transposition">Transposition</A> Cipher</B>

<UL>

<LI>Clearly, it is necessary for all message elements

which will be transposed to be collected before

operations begin; this is the block cipher signature.

<LI>Any possible transposition is necessarily a subset

of an arbitrary substitution; thus, transposition can

be seen as a particular keying subset of substitution.

<LI>Notice, however, that the usual avalanche signature

of substitution is not present, and of course the

actual data values are not changed at all by

transposition, just moved about.

<LI>Also notice that we are close to using the idea of

permutation in two very different ways: first as a

particular n-bit to n-bit substitution, and second as

a particular re-arrangement of characters in the block.

These have wildly different ciphering effects.

</UL>

</OL>

</OL>

<P><BIG><B>

<LI><A HREF = "#StreamCipher">STREAM CIPHER</A></B></BIG>

<UL>

<LI>A stream cipher does <I>not</I> need to accumulate some amount

of data or multiple data elements for ciphering to complete.

(Since we define only two main "types" of cipher, a stream cipher

is the opposite of a block cipher and vise versa. It is

extremely important that the definitions for block and stream

ciphering enclose the universe of all possible ciphers.)

<LI>A stream cipher has the ability to transform individual

elements one-by-one. The actual transformation usually is

a block transformation, and may be repeated with the same

or different keying.

<LI>In a stream cipher, data diffusion may or may not occur, but

if it does, it is necessarily one-way (from earlier to

later elements).

<LI>Since elements are ciphered one-by-one, changing part of

the plaintext can affect that part and possibly <I>later</I>

parts of the ciphertext; this is a stream cipher signature.

<LI>The simple re-use of a block transformation to cover more

data than a single block is a stream operation.

</UL>

<P><OL TYPE = 1>

<B><LI><A HREF = "#ConfusionSequence">CONFUSION SEQUENCE</A></B>

<UL>

<LI>With a truly random sequence, used once, we have a

<A HREF = "#OneTimePad">one time pad</A>.

<LI>With a pseudorandom confusion sequence and a simple

additive combiner, we have a Vernam cipher.

<LI>A simple additive transformation becomes weak upon the

second character ciphered, or immediately, under

<A HREF = "#KnownPlaintextAttack">known plaintext</A>,

making strength dependent on the confusion sequence.

<LI>More complex transformations imply the need for

correspondingly less strong confusion sequences.

</UL>

<P><OL TYPE = a>

<B><LI>Autokey</B>

<UL>

<LI>Normally the use of ciphertext, but also perhaps

plaintext, as the cipher key.

<LI>Can create a random-like confusion stream which will

re-synchronize after ciphertext data loss.

<LI>Under known-plaintext, the common "ciphertext feedback"

version exposes both the confusion sequence and the

input which creates that sequence. This is a lot of

pressure on a single transformation.

</UL>

</OL>

<P>

<B><LI><A HREF = "#MonoalphabeticSubstitution">MONOALPHABETIC</A></B>

(e.g., <A HREF = "#DES">DES</A> <A HREF = "#CBC">CBC</A>)

<UL>

<LI>The repeated use of a single fixed substitution.

<LI>A conventional block cipher <I>simulates</I> a large

substitution.

<LI>A substitution becomes weak when its code values are

re-used.

<LI>Code value re-use can be minimized by randomizing the

plaintext block (e.g., CBC). This distributes the

plaintext evenly across the possible block values, but

at some point the transformation itself must change or

be exposed.

<LI>Another alternative is to use a very large block so that

code value re-use is made exceedingly unlikely. A large

block also has room for a dynamic keying field which

would make code value re-use even more unlikely.

</UL>

<P>

<B><LI><A HREF = "#PolyalphabeticSubstitution">POLYALPHABETIC</A></B>

<UL>

<LI>The use of multiple fixed substitutions.

<LI>By itself, the use of multiple alphabets in a regular

sequence is inherently not much stronger than just a

single alphabet.

<LI>It is of course possible to select an alphabet or

transformation at pseudo-random, for example by

re-keying DES after every block ciphered. This brings

back sequence strength as an issue, and opens up the

sequence generator starting

<A HREF = "#State">state</A> as an

<A HREF = "#IV">IV</A>.

<LI>A related possibility is the use of a

<A HREF = "#LatinSquareCombiner">Latin square combiner</A>

which effectively selects among a balanced set of

different fixed substitution alphabets.

</UL>

<P><OL TYPE = a>

<B><LI>Cylinder</B>

<UL>

<LI>A cipher which has or simulates the use of a number

of different alphabet disks on a common rod.

<LI>Primary keying is the arrangement of the alphabet around

each disk, and the selection and arrangement of disks.

<LI>By entering the plaintext on one row, any of n-1 other

rows can be sent as ciphertext; this selection is an

<A HREF = "#IV">IV</A>.

<LI>If the plaintext data are redundant, it is possible to

avoid sending the IV by selecting the one of n-1

possible decipherings which shows redundancy. But this

is not generally possible when ciphering arbitrary

binary data.

<LI>If an IV is selected first, each character ciphering in

that "chunk" is independent of each other ciphering.

There is no data <A HREF = "#Diffusion">diffusion</A>.

<LI>In general, each disk is used at fixed periodic

intervals through the text, which is weak.

<LI>The ciphertext selection is

<A HREF = "#Homophonic">homophonic</A>, in the sense

that different ciphertext rows each represent exactly

the same plaintext.

<LI>Cylinder operation is <B>not</B>

<A HREF = "#Polyphonic">polyphonic</A> in the usual

sense: While a single ciphertext <I>can</I> imply any

other row is plaintext, generally only one row has a

reasonable plaintext meaning.

</UL>

</OL>

<P>

<B><LI><A HREF = "#DynamicSubstitutionCombiner">DYNAMIC</A></B>

<UL>

<LI>The use of one (monoalphabetic) or multiple

(polyalphabetic) substitutions which <I>change</I> during

ciphering.

</UL>

<P>

<B><LI>ITERATIVE</B>

<UL>

<LI>The iterative re-use of a stream cipher with a new random

<A HREF = "#IV">IV</A> on each iteration so as to eventually

achieve the effect of a

<A HREF = "#MessageKey">message key</A>.

<LI>Each iteration seemingly must expand the ciphertext by

the size of the IV, although this is probably about the

same expansion we would have with a message key.

<LI>Unfortunately, each iteration will take some time.

</UL>

</OL>

</OL>

<A NAME = "Ciphering"></A>

<P><DT><B>Ciphering</B>

<DD>The use of a

<A HREF = "#Cipher">cipher</A>.

The general term which includes both

<A HREF = "#Encipher">enciphering</A> and

<A HREF = "#Decipher">deciphering</A>.

<A NAME = "Ciphertext"></A>

<P><DT><B>Ciphertext</B>

<DD>The result of

<A HREF = "#Encipher">enciphering</A>. Ciphertext will contain the

same information as the original

<A HREF = "#Plaintext">plaintext</A>, but hide the original

information, typically under the control of a

<A HREF = "#Key">key</A>. Without the

key it should be impractical to recover the original information

from the ciphertext.

<A NAME = "CiphertextExpansion"></A>

<P><DT><B>Ciphertext Expansion</B>

<DD>When the

<A HREF = "#Ciphertext">ciphertext</A> is larger than the original

<A HREF = "#Plaintext">plaintext</A>.

<P>Ciphertext expansion is the general situation:

<A HREF = "#StreamCipher">Stream ciphers</A> need a

<A HREF = "#MessageKey">message key</A>, and

<A HREF = "#BlockCipher">block ciphers</A> with a small block

need some form of plaintext randomization, which generally

needs an

<A HREF = "#IV">IV</A> to protect the first block. Only block

ciphers with a large size block generally can avoid ciphertext

expansion, and then only if each block can be expected to hold

sufficient uniqueness or "entropy" to prevent a

<A HREF = "#CodebookAttack">codebook attack</A>.

<P>It is certainly true that in most situations of new construction

a few extra bytes are not going to be a problem. However, in some

situations, and especially when a cipher is to be installed into

an existing system, the ability to encipher data <I>without</I>

requiring additional storage can be a big advantage. Ciphering

data without expansion supports the ciphering of data structures

which have been defined and fixed by the rest of the system,

provided only that one can place the cipher at the interface

"between" two parts of the system. This is also especially

efficient, as it avoids the process of acquiring a different,

larger, amount of store for each ciphering. Such an installation

also can apply to the entire system, and not require the

re-engineering of all applications to support cryptography in

each one.

<A NAME = "Ciphony"></A>

<P><DT><B>Ciphony</B>

<DD>Audio or voice

<A HREF = "#Encryption">encryption</A>. A contraction of "ciphered

telephony."

<A NAME = "Circuit"></A>

<P><DT><B>Circuit</B>

<DD>The "circular" flow of electrons from a power source, through

<A HREF = "#Conductor">conductors</A> and

<A HREF = "#Component">components</A> and back to the power source.

Or the arrangement of components which allows such flow and

performs some function.

<A NAME = "Clock"></A>

<P><DT><B>Clock</B>

<DD>A repetitive or cyclic timing signal to coordinate

<A HREF = "#State">state</A> changes in a

<A HREF = "#Digital">digital</A> system. A clock can coordinate

the movement of data and results through various stages of

processing. Although a clock signal is digital, the source of the

repetitive signal is almost always an

<A HREF = "#Analog">analog</A>

<A HREF = "#Circuit">circuit</A>.

<P>In an analog system we might produce a known delay by slowly

charging a

<A HREF = "#Capacitor">capacitor</A> and measuring the

<A HREF = "#Voltage">voltage</A>

across it continuously until the voltage reaches the desired level.

A big problem with this is that the

<A HREF = "#Circuit">circuit</A> becomes increasingly susceptible

to noise at the end of the interval.

<P>In a digital system we create a delay by simply counting

clock cycles. Since all external operations are digital, noise

effects are virtually eliminated, and we can easily create

accurate delays which are as long as the count in any counter

we can build.

<A NAME = "Closed"></A>

<P><DT><B>Closed</B>

<DD>An operation on a

<A HREF = "#Set">set</A> which produces only elements in that set.

<A NAME = "Code"></A>

<P><DT><B>Code</B>

<DD>Symbols or values which stand for symbols, values, sequences,

or even operations (as in

<A HREF = "#Computer">computer</A>

"<A HREF = "#Opcode">opcodes</A>"). As opposed to a

<A HREF = "#Cipher">cipher</A>, which operates only on individual

characters or

<A HREF = "#Bit">bits</A>, classically, codes also represent words,

phrases, and entire sentences.

One application was to decrease the cost of telegraph messages.

In modern usage, a code is often simply a correspondence between

information (such as character symbols) and values (such as the

<A HREF = "#ASCII">ASCII</A> code or

<A HREF = "#Base64">Base-64</A>), although computer opcodes do have

independent meanings and variable lengths.

<P>Coding is a very basic part of modern computation and generally

implies no

<A HREF = "#Secrecy">secrecy</A> or information hiding. Some codes

are "secret codes," however, and then the transformation between the

information and the coding is kept secret. Also see:

<A HREF = "#Cryptography">cryptography</A> and

<A HREF = "#Substitution">substitution</A>.

<A NAME = "Codebook"></A>

<P><DT><B>Codebook</B>

<DD>Literally, the listing or "book" of

<A HREF = "#Code">code</A>

transformations. More generally, any collection of such

transformations. Classically, letters, common words and useful

phrases were numbered in a codebook; messages transformed into

those numbers were "coded messages." Also see

<A HREF = "#Nomenclator">nomenclator</A>.

A "codebook style cipher" refers to a

<A HREF = "#BlockCipher">block cipher</A>.

<A NAME = "CodebookAttack"></A>

<P><DT><B>Codebook Attack</B>

<DD>A form of

<A HREF = "#Attack">attack</A> in which The

<A HREF = "#Opponent">Opponent</A> simply tries to build or collect a

<A HREF = "#Codebook">codebook</A> of all the possible transformations

between

<A HREF = "#Plaintext">plaintext</A> and

<A HREF = "#Ciphertext">ciphertext</A> under a single

<A HREF = "#Key">key</A>. This is the classic approach we

normally think of as "codebreaking."

<P>The usual ciphertext-only approach depends upon the plaintext

having strong statistical biases which make some values far more

probable than others, and also more probable in the context of

particular preceding known values. Such attacks can be defeated if

the plaintext data are randomized and thus evenly and independently

distributed among the possible values. (This may have been the

motivation for the use of a

<A HREF = "#Random">random</A>

<A HREF = "#ConfusionSequence">confusion sequence</A> in a

<A HREF = "#StreamCipher">stream cipher</A>.)

<P>When a codebook attack is possible on a

<A HREF = "#BlockCipher">block cipher</A>, the complexity of the

attack is controlled by the size of the block (that is, the number

of elements in the codebook) and not the

<A HREF = "#Strength">strength</A> of the cipher.

This means that a codebook attack would be equally effective

against either

<A HREF = "#DES">DES</A> or

<A HREF = "#TripleDES">Triple-DES</A>.

<P>One way a block cipher can avoid a codebook attack is by having

a large

<A HREF = "#Block">block</A> size which will contain an unsearchable

amount of plaintext "uniqueness" or

<A HREF = "#Entropy">entropy</A>. Another approach is to randomize the

plaintext block, often by using an

<A HREF = "#OperatingMode">operating mode</A> such as

<A HREF = "#CBC">CBC</A>.

<A NAME = "Combination"></A>

<P><DT><B>Combination</B>

<DD>The mathematical term for any particular subset of symbols,

independent of order. (Also called the binomial coefficient.)

The number of combinations of <I>n</I> things, taken <I>k</I>

at a time, read "<I>n</I> choose <I>k</I>" is:

<PRE>

n

( ) = C(n,k) = n! / (k! (n-k)!)

k

</PRE>

<P>See the

<A HREF = "http://www.io.com/~ritter/JAVASCRP/PERMCOMB.HTM#Combinations">combinations</A>

section of the

<A HREF = "http://www.io.com/~ritter/#JavaScript">Ciphers By Ritter /

JavaScript</A> computation pages. Also see

<A HREF = "#Permutation">permutation</A>.

<A NAME = "Combinatoric"></A>

<P><DT><B>Combinatoric</B>

<DD>Combinatorics is a branch of mathematics, like analysis

or number theory. Combinatorics is often related to counting

the subsets of finite sets. One result is to help us to

understand the probability of a particular subset in the

universe of possible values.

<P>Consider a

<A HREF = "#BlockCipher">block cipher</A>:

For any given size block, there

is some fixed number of possible messages. Since every

enciphering must be reversible (deciphering must work), we

have a 1:1 mapping between

<A HREF = "#Plaintext">plaintext</A> and

<A HREF = "#Ciphertext">ciphertext</A> blocks.

The set of all plaintext values and the set of all ciphertext

values is the same set; particular values just have different

meanings in each set.

<P><A HREF = "#Key">Keying</A> gives us no more ciphertext values,

it only re-uses

the values which are available. Thus, keying a block cipher

consists of selecting a particular arrangement or

<A HREF = "#Permutation">permutation</A>

of the possible block values. Permutations are a combinatoric

topic. Using combinatorics we can talk about the number of

possible permutations or keys in a block cipher, or in cipher

components like substitution tables.

<P>Permutations can be thought of as the number of unique

arrangements of a given length on a particular set. Other

combinatoric concepts include

<A HREF = "#BinomialDistribution">binomials</A>

and

<A HREF = "#Combination">combinations</A>

(the number of unique given-length subsets of a given set).

<A NAME = "Combiner"></A>

<P><DT><B>Combiner</B>

<DD>In a cryptographic context, a combiner is a

<A HREF = "#Mechanism">mechanism</A> which

<A HREF = "#Mixing">mixes</A> two data sources into a single result.

A "combiner style cipher" refers to a

<A HREF = "#StreamCipher">stream cipher</A>.

<P><I>Reversible</I> combiners are used to

<A HREF = "#Encipher">encipher</A>

<A HREF = "#Plaintext">plaintext</A> into

<A HREF = "#Ciphertext">ciphertext</A> in a

<A HREF = "StreamCipher">stream cipher</A>. The ciphertext is then

<A HREF = "#Decipher">deciphered</A> into plaintext using a related

inverse or

<A HREF = "#Extractor">extractor</A> mechanism.

<P><I>Irreversible</I> or non-invertible combiners are often used to

mix multiple

<A HREF = "#RNG">RNG's</A> into a single

<A HREF = "#ConfusionSequence">confusion sequence</A>, also for

use in stream cipher designs.

<P>Also see

<A HREF = "#BalancedCombiner">balanced combiner</A>,

<A HREF = "#AdditiveCombiner">additive combiner</A> and

<A HREF = "#Complete">complete</A>, and

<A HREF = "http://www.io.com/~ritter/RES/COMBCORR.HTM">The Story

of Combiner Correlation: A Literature Survey</A>, in the

<A HREF = "http://www.io.com/~ritter/#LiteratureSurveys">Literature

Surveys and Reviews</A> section of the

<A HREF = "http://www.io.com/~ritter/">Ciphers By Ritter</A> page.

<A NAME = "Commutative"></A>

<P><DT><B>Commutative</B>

<DD>A

<A HREF = "#Dyadic">dyadic</A> operation in which exchanging the

two argument values must produce the same result:

<NOBR>a + b = b + a.</NOBR>

<P>Also see:

<A HREF = "#Associative">associative</A> and

<A HREF = "#Distributive">distributive</A>.

<A NAME = "Complete"></A>

<P><DT><B>Complete</B>

<DD>A term used in

<A HREF = "#S-Box">S-box</A> analysis to describe a property of

the value arrangement in an invertible

<A HREF = "#Substitution">substitution</A> or, equivalently, a

<A HREF = "#BlockCipher">block cipher</A>.

If we have some input value, and then change one bit in that

value, we expect about half the output bits to change; this is

the result of

<A HREF = "#Diffusion">diffusion</A>; when partial diffusion is

repeated we develop

<A HREF = "#Avalanche">avalanche</A>; and the ultimate result is

<A HREF = "#StrictAvalancheCriterion">strict avalanche</A>.

<I>Completeness</I> tightens this concept and requires that changing

a particular input bit produce a change in a particular output bit,

at some point in the transformation (that is, for at least one input

value). Completeness requires that this relationship occur at least

once for <I>every</I> combination of input bit and output bit.

It is tempting to generalize the definition to apply to multi-bit

element values, where this makes more sense.

<P>Completeness does <I>not</I> require that an input bit change

an output bit for <I>every</I> input value (which would not make

sense anyway, since <I>every</I> output bit must be changed at

<I>some</I> point, and if they all had to change at <I>every</I>

point, we would have <I>all</I> the output bits changing, instead

of the desired half). The inverse of a complete function is not

necessarily also complete.

<P>As originally defined in Kam and Davida:

<BLOCKQUOTE>

"For every possible key value, every output bit

<I>c<SUB>i</SUB></I> of the SP network depends upon all input

bits <I>p<SUB>1</SUB>,...,p<SUB>n</SUB></I> and not just a

proper subset of the input bits." [p.748]

</BLOCKQUOTE>

Kam, J. and G. Davida. 1979.

Structured Design of Substitution-Permutation Encryption Networks.

<I>IEEE Transactions on Computers.</I>

C-28(10): 747-753.

<A NAME = "Component"></A>

<P><DT><B>Component</B>

<DD>A part of a larger construction; a building-block in an overall

design or

<A HREF = "#System">system</A>. Modern

<A HREF = "#Digital">digital</A> design is based on the use of a few

general classes of pre-defined, fully-specified parts. Since even

digital logic can use or even require

<A HREF = "#Analog">analog</A> values internally, by enclosing these

values the logic component can hide complexity and present the

appearance of a fully digital device.

<P>The most successful components are extremely general and can be

used in many different ways. Even as a brick is independent of the

infinite variety of brick buildings, a

<A HREF = "#FlipFlop">flip-flop</A> is independent of the infinite

variety of logic machines which use flip-flops.

<P>The source of the ability to design and build a wide variety of

different electronic logic machines is the ability to interconnect

and use a few very basic but very general parts.

<P><A HREF = "#Electronic">Electronic</A>

components include

<UL>

<LI>passive components like

<A HREF = "#Resistor">resistors</A>,

<A HREF = "#Capacitor">capacitors</A>, and

<A HREF = "#Inductor">inductors</A>;

<LI>active components like

<A HREF = "#Transistor">transistors</A> and even

<A HREF = "#Relay">relays</A>, and

<LI>whole varieties of active electronic logic devices,

including

<A HREF = "#FlipFlop">flip-flops</A>,

<A HREF = "#ShiftRegister">shift registers</A>, and

<A HREF = "#State">state</A> storage, or memory.

</UL>

<P>Cryptographic system components include:

<UL>

<LI>Nonlinear transformations, such as

<A HREF = "#S-Box">S-boxes</A> /

<A HREF = "#SubstitutionTable">substitution tables</A>,

<LI><A HREF = "#Key">key</A>

<A HREF = "#Hash">hashing</A>, such as

<A HREF = "#CRC">CRC</A>,

<LI><A HREF = "#RandomNumberGenerator">random number generators</A>, such as

<A HREF = "#AdditiveRNG">additive RNG's</A>,

<LI>sequence isolators such as

<A HREF = "#Jitterizer">jitterizers</A>,

<LI><A HREF = "#Combiner">combiners</A>, such as

<A HREF = "#DynamicSubstitutionCombiner">Dynamic Substitution</A>,

<A HREF = "#LatinSquareCombiner">Latin squares</A>, and

<A HREF = "#ExclusiveOR">exclusive-OR</A>,

<LI><A HREF = "#Mixing">mixers</A>, such as

<A HREF = "#BalancedBlockMixer">Balanced Block Mixers</A>, or

<A HREF = "#OrthogonalLatinSquares">orthogonal Latin squares</A>.

</UL>

<A NAME = "Computer"></A>

<P><DT><B>Computer</B>

<DD>Originally the job title for a person who performed a laborious

sequence of arithmetic computations. Now a machine for performing

such calculations.

<P>A logic machine with:

<P><OL>

<LI>Some limited set of fundamental computations. Typical operations

include simple arithmetic and

<A HREF = "#BooleanLogic">Boolean logic</A>. Each operation is

selected by a particular operation code value or

"<A HREF = "#Opcode">opcode</A>." This is a

<A HREF = "#Hardware">hardware</A> interpretation of the opcode.

<P><LI>The ability to follow a list of instructions or commands,

performing each in sequence. Thus capable of simulating a wide

variety of far more complex "instructions."

<P><LI>The ability to execute or perform at least some instructions

conditionally, based on parameter values or intermediate results.

<P><LI>The ability to store values into a numbered "address space"

which is far larger than the instruction set, and later to recover

those values when desired.

</OL>

<P>Also see:

<A HREF = "#SourceCode">source code</A>,

<A HREF = "#ObjectCode">object code</A> and

<A HREF = "#Software">software</A>.

<A NAME = "Conductor"></A>

<P><DT><B>Conductor</B>

<DD>A material in which electron flow occurs easily. Typically a

metal; usually copper, sometimes silver, brass or even aluminum.

A

<A HREF = "#Wire">wire</A>. As opposed to an

<A HREF = "#Insulator">insulator</A>.

<A NAME = "Confusion"></A>

<P><DT><B>Confusion</B>

<DD>Those parts of a

<A HREF = "#Cipher">cipher</A>

<A HREF = "#Mechanism">mechanism</A> which change the

correspondence between input values and output values. In

contrast to

<A HREF = "#Diffusion">diffusion</A>.

<A NAME = "ConfusionSequence"></A>

<P><DT><B>Confusion Sequence</B>

<DD>The sequence combined with data in a

<A HREF = "#StreamCipher">stream cipher</A>. Normally produced

by a

<A HREF = "#RandomNumberGenerator">random number generator</A>,

it is also called a "running key."

<A NAME = "Contextual"></A>

<P><DT><B>Contextual</B>

<DD>In the study of

<A HREF = "#Logic">logic</A>, an observed fact dependent upon other

facts <I>not</I> being observed. Or a statement which is

conditionally true, provided other unmentioned conditions have the

appropriate

<A HREF = "#State">state</A>. As opposed to

<A HREF = "#Absolute">absolute</A>.

<A NAME = "ConventionalCipher"></A>

<P><DT><B>Conventional Cipher</B>

<DD>A

<A HREF = "#SecretKeyCipher">secret key cipher</A>.

<A NAME = "Congruence"></A>

<P><DT><B>Congruence</B>

<DD>Casually speaking, the remainder after a division of

<A HREF = "#Integer">integers</A>.

<P>In number theory we say than integer a (exactly) <I>divides</I>

integer b (denoted <NOBR>a | b</NOBR>) if and only if there is an

integer k such that <NOBR>ak = b.</NOBR>

<P>In number theory we say that integer a is <I>congruent</I> to

integer b

<A HREF = "#Modulo"><I>modulo</I></A> m, denoted

<NOBR>a = b (mod m),</NOBR>

if and only if <NOBR>m | (a - b).</NOBR> Here m is the divisor

or <I>modulus.</I>

<A NAME = "Convolution"></A>

<P><DT><B>Convolution</B>

<DD><A HREF = "#Polynomial">Polynomial</A> multiplication.

A multiplication of each term against each other term, with no

"carries" from term to term. Also see

<A HREF = "#Correlation">correlation</A>.

<P>Used in the analysis of signal processing to develop the response

of a processing system to a complicated real-valued input signal.

The input signal is first separated into some number of discrete

impulses. Then the system response to an impulse -- the output level

at each unit time delay after the impulse -- is determined. Finally,

the expected response is computed as the sum of the contributions

from each input impulse, multiplied by the magnitude of each impulse.

This is an approximation to the convolution integral with an infinite

number of infinitesimal delays. Although originally accomplished

graphically, the process is just polynomial multiplication.

<P>It is apparently possible to compute the convolution of two

sequences by taking the

<A HREF = "#FFT">FFT</A> of each, multiplying these results

term-by-term, then taking the inverse FFT. While there is an

analogous relationship in the

<A HREF = "#FWT">FWT</A>, in this case the "delays" between the

sequences represent

<A HREF = "#Mod2">mod 2</A> distance differences, which may or may

not be useful.

<A NAME = "Correlation"></A>

<P><DT><B>Correlation</B>

<DD>In general, the probability that two sequences of symbols

will, in any position, have the same symbol. We expect two

<A HREF = "#Random">random</A>

binary

sequences to have the same symbols about half the time.

<P>One way to evaluate the correlation of two real-valued sequences

is to multiply them together term-by-term and sum all results.

If we do this for all possible "delays" between the two sequences,

we get a "vector" or 1-dimensional array of correlations which is a

<A HREF = "#Convolution">convolution</A>. Then the maximum value

represents the delay with the best correlation.

<A NAME = "CorrelationCoefficient"></A>

<P><DT><B>Correlation Coefficient</B>

<DD>The value from -1 to +1 describing the

<A HREF = "#Correlation">correlation</A> of two binary sequences,

averaged over the length of interest.

Correlation coefficient values are related to the probability that,

given a symbol from one sequence, the other sequence will have that

same symbol. A value of:

<UL>

<LI>-1 implies a 0.0 probability (the second sequence is the

complement of the first),

<LI>0 implies a 0.5 probability (the sequences are

uncorrelated), and

<LI>+1 implies a 1.0 probability (the sequences are the same).

</UL>

<P>"The correlation coefficient associated with a pair of

<A HREF = "#BooleanFunction">Boolean functions</A>

<I>f(a)</I> and <I>g(a)</I> is denoted by C(f,g) and is given by

<BLOCKQUOTE><TT>

C(<I>f,g</I>) = 2 * prob(<I>f(a) = g(a)</I>) - 1 ."

</TT></BLOCKQUOTE>

<P>Daemen, J., R. Govaerts and J. Vanderwalle. 1994.

Correlation Matrices.

<I>Fast Software Encryption.</I>

276. Springer-Verlag.

<A NAME = "CRC"></A>

<P><DT><B>CRC</B>

<DD>Cyclic Redundancy Check: A fast error-check

<A HREF = "#Hash">hash</A> based on

<A HREF = "#Mod2Polynomial">mod 2 polynomial</A> operations.

<P>A CRC is essentially a fast remainder operation over

a huge numeric value which is the data. (For best speed, the

actual computation occurs as mod 2 polynomial operations.)

The CRC result is an excellent (but linear) hash value

corresponding to the data.

<P>No CRC has any appreciable

<A HREF = "#Strength">strength</A>,

but some applications -- even in cryptography -- <I>need</I> no

strength:

<UL>

<LI>One example is

<A HREF = "#Authentication">authentication</A>, provided the

linear CRC hash result is protected by a block cipher.

<LI>Another example is

<A HREF = "#Key">key</A> processing, where the uncertainty

in a User Key phrase of arbitrary size is collected into a

hash result of fixed size. In general, the hash result would

be just as good for The Opponent as the original key phrase,

so no strength shield could possibly improve the situation.

<LI>A third example is the accumulation of the uncertainty in

slightly uncertain

<A HREF = "#PhysicallyRandom">physically random</A> events.

When true randomness is accumulated, it is already as

unknowable as any strength shield could make it.

</UL>

<A NAME = "Cryptanalysis"></A>

<P><DT><B>Cryptanalysis</B>

<DD>That aspect of

<A HREF = "#Cryptology">cryptology</A> which concerns the

<A HREF = "#Strength">strength</A> analysis of a

<A HREF = "#Cryptography">cryptographic</A> system, and the

penetration or

<A HREF = "#Break">breaking</A> of a cryptographic system.

Also "codebreaking."

<P>Because there is no theory which guarantees strength for any

conventional cipher, ciphers traditionally have been considered

"strong" when they have been used for a long time with "nobody"

knowing how to break them easily. Cryptanalysis seeks to improve

this process by applying the known

<A HREF = "#Attack">attack</A> strategies to new

<A HREF = "#Cipher">ciphers</A>, and by actively seeking new ones.

It is normal to assume that at least

<A HREF = "#KnownPlaintextAttack">known-plaintext</A> is available;

often,

<A HREF = "#DefinedPlaintextAttack">defined-plaintext</A> is assumed.

The result is typically some value for the amount of "work" which will

achieve a "break" (even if that value is impractical); this is "the"

<A HREF = "#Strength">strength</A> of the cipher.

<P>But while cryptanalysis <I>can</I> prove "weakness" for a given

level of effort, cryptanalysis <I>cannot</I> prove that there is no

simpler attack:

<BLOCKQUOTE><BIG><B>Lack of proof of weakness is not proof of

strength.</B></BIG></BLOCKQUOTE>

<P>Indeed, when ciphers are used for real,

<A HREF = "#Opponent">The Opponents</A> can hardly be expected to

advertise a successful break, but will instead work hard to

reassure users that their ciphers are still secure. The fact that

<I>apparently</I> "nobody" knows how to break a cipher is somewhat

less reassuring from this viewpoint. In this context, using a wide

variety of different ciphers can make good sense: This reduces the

value of the information protected by any particular cipher, which

thus reduces the rewards from even a successful attack. Having a

numerous ciphers also requires The Opponents to field far greater

resources to identify, analyze, and automate breaking (when possible)

of each different cipher.

<P>Many academic attacks are essentially theoretical, involving huge

amounts of data and computation. But even when a direct technical

attack is <I>practical,</I> that may be the most difficult, expensive

and time-consuming way to obtain the desired information. Other

methods include making a paper copy, stealing a copy, bribery,

coercion, and electromagnetic monitoring. No cipher can keep secret

something which has been otherwise revealed. Information

<A HREF = "#Security">security</A> thus involves far more than just

<A HREF = "#Cryptography">cryptography</A>, and even a cryptographic

system is more than just a cipher. Even finding that information

has been revealed does not mean that a cipher has been broken.

<P>At one time it was reasonable to say: "Any cipher a man can

make, another man can break." However, with the advent of

serious

<A HREF = "#Computer">computer</A>-based cryptography, that

statement is no longer

valid, <I>provided</I> that every detail is properly handled.

This, of course, often turns out to not be the case.

<A NAME = "Cryptanalyst"></A>

<P><DT><B>Cryptanalyst</B>

<DD>Someone who

<A HREF = "#Attack">attacks</A>

<A HREF = "#Cipher">ciphers</A> with

<A HREF = "#Cryptanalysis">cryptanalysis</A>. A "codebreaker."

Often called the

<A HREF = "#Opponent">Opponent</A> by cryptographers, in

recognition of the (serious) game of thrust and parry between

these parties.

<A NAME = "Cryptographer"></A>

<P><DT><B>Cryptographer</B>

<DD>Someone who creates

<A HREF = "#Cipher">ciphers</A> using

<A HREF = "#Cryptography">cryptography</A>.

<A NAME = "CryptographicMechanism"></A>

<P><DT><B>Cryptographic Mechanism</B>

<DD>A process for enciphering and/or deciphering, or an

implementation (for example,

<A HREF = "#Hardware">hardware</A>,

<A HREF = "#Computer">computer</A>

<A HREF = "#Software">software</A>,

hybrid, or the like) for performing that process. See also

<A HREF = "#Cryptography">cryptography</A> and

<A HREF = "#Mechanism">mechanism</A>.

<A NAME = "Cryptography"></A>

<P><DT><B>Cryptography</B>

<DD>Greek for "hidden writing." The art and science of transforming

information into an intermediate form which

<A HREF = "#Security">secures</A> that information while in storage

or in transit. A part of

<A HREF = "#Cryptology">cryptology</A>, further divided into secret

<A HREF = "#Code">codes</A> and

<A HREF = "#Cipher">ciphers</A>.

As opposed to

<A HREF = "#Steganography">steganography</A>, which seeks to

hide the existence of any message, cryptography seeks to

render a message unintelligible <I>even when the message is

completely exposed</I>.

<P>Cryptography includes at least:

<UL>

<LI><A HREF = "#Secrecy">secrecy</A> (<I>confidentiality,</I> or

<I>privacy,</I> or <I>information security</I>) and

<LI><A HREF = "#Authentication">message authentication</A>

(<I>integrity</I>).

</UL>

Cryptography may also include:

<UL>

<LI><I>nonrepudiation</I> (the inability to deny sending a

message),

<LI><I>access control</I> (<I>user</I> or <I>source</I>

authentication), and

<LI><I>availability</I> (keeping security services available).

</UL>

<P>Modern cryptography generally depends upon translating a

message into one of an astronomical number of different

intermediate representations, or

<A HREF = "#Ciphertext">ciphertexts</A>, as selected by a

<A HREF = "#Key">key</A>. If all possible

intermediate representations have similar appearance, it may be

necessary to try all possible keys to find the one which

deciphers the message. By creating

<A HREF = "#Mechanism">mechanisms</A> with an

astronomical number of keys, we can make this approach

impractical.

<P>Cryptography may also be seen as a zero-sum game, where a

<A HREF = "#Cryptographer">cryptographer</A> competes against a

<A HREF = "#Cryptanalyst">cryptanalyst</A>. We might call

this the <A HREF = "#CryptographyWar">cryptography war</A>.

<A NAME = "CryptographyWar"></A>

<P><DT><B>Cryptography War</B>

<DD>

<A HREF = "#Cryptography">Cryptography</A> may be seen as a

dynamic <I>battle</I> between

<A HREF = "#Cryptographer">cryptographer</A> and

<A HREF = "#Cryptanalyst">cryptanalyst</A>. The cryptographer

tries to produce a

<A HREF = "#Cipher">cipher</A> which can retain

<A HREF = "#Secrecy">secrecy</A>. Then,

when it becomes worthwhile, one or more cryptanalysts try to

penetrate that secrecy by

<A HREF = "#Attack">attacking</A> the

cipher. Fortunately for the war, even after fifty years of

mathematical cryptology, not <I>one</I> practical cipher has

been accepted as <I>proven</I>

<A HREF = "#Security">secure</A> in practice. (See, for example, the

<A HREF = "#OneTimePad">one-time pad</A>.)

<P>Note that the successful cryptanalyst must keep good attacks

secret, or the opposing cryptographer will just produce a

<A HREF = "#Strength">stronger</A>

cipher. This means that the cryptographer is in the odd position

of never knowing whether his or her best cipher designs are

successful, or which side is winning.

<P>Cryptographers are often scientists who are trained to ignore

unsubstantiated claims. But there will <I>be</I> no substantiation

when a

<A HREF = "#Cipher">cipher</A>

<A HREF = "#System">system</A> is

<A HREF = "#Attack">attacked</A> and

<A HREF = "#Break">broken</A> for real, yet

continued use will endanger all messages so "protected." Thus,

it is a very reasonable policy to not adopt a widely-used cipher,

and to change ciphers periodically.

<A NAME = "Cryptology"></A>

<P><DT><B>Cryptology</B>

<DD>The field of study which generally includes

<A HREF = "#Steganography">steganography</A>,

<A HREF = "#Cryptography">cryptography</A> and

<A HREF = "#Cryptanalysis">cryptanalysis</A>.

<A NAME = "Current"></A>

<P><DT><B>Current</B>

<DD>The measure of electron flow, in amperes.

Current is analogous to the amount of water <I>flow,</I> as opposed

to <I>pressure</I> or

<A HREF = "#Voltage">voltage</A>.

A flowing electrical current will create a

<A HREF = "#MagneticField">magnetic field</A> around the

<A HREF = "#Conductor">conductor</A>.

A changing electrical current may create an

<A HREF = "#ElectromagneticField">electromagnetic field</A>.

<A NAME = "dB"></A>

<P><DT><HR><P><B>dB</B>

<DD><A HREF = "#Decibel">decibel</A>.

<A NAME = "DC"></A>

<P><DT><B>DC</B>

<DD>Direct

<A HREF = "#Current">Current</A>:

Electrical power which flows in one direction, more or less

constantly. As opposed to

<A HREF = "#AC">AC</A>.

<P>Most

<A HREF = "#Electronic">electronic</A> devices require DC -- at

least internally -- for proper operation, so a substantial part

of modern design is the "power supply" which converts 120 VAC wall

power into 12 VDC, 5 VDC and/or 3 VDC as needed by the

<A HREF = "#Circuit">circuit</A>

and active devices.

<A NAME = "Debug"></A>

<P><DT><B>Debug</B>

<DD>The interactive analytical process of correcting the design of a

complex

<A HREF = "#System">system</A>. A normal part of the development

process, although when

<A HREF = "#Bug">bugs</A> are not caught during development, they

can remain in production systems.

<P>Contrary to naive expectations, a complex system almost never

performs as desired when first realized. Both

<A HREF = "#Hardware">hardware</A> and

<A HREF = "#Software">software</A>

<A HREF = "#SystemDesign">system design</A> environments generally

deal with systems which are not working.

(When a system <I>really</I> works, the design and development

process is generally over.)

Debugging involves identifying problems, analyzing the source of

those problems, then changing the construction to fix the problem.

(Hopefully, the fix will not itself create new problems.)

This form of interactive analysis can be especially difficult because

the realized design may not actually be what is described in the

schematics, flow-charts, or other working documents: To some extent

the real system is unknown.

<P>When a system has many problems, the problems tend to interact,

which can make the identification of a particular cause very

difficult. This can be managed by "shrinking" the system: first

by partitioning the design into components and testing those

components, and then by temporarily disabling or removing sections

so as to identify the section in which the problem lies. Eventually,

with enough testing, partitioning and analysis, the source of any

problem can be identified. Some "problems,"

however, turn out to be the unexpected implications of a complex

design and are sometimes accepted as "features" rather than the

alternative of a complete design overhaul.

<A NAME = "Decipher"></A>

<P><DT><B>Decipher</B>

<DD>The process which can reveal the information

or <A HREF = "#Plaintext">plaintext</A> hidden in message

<A HREF = "#Ciphertext">ciphertext</A> (provided it is the

correct process, with the proper

<A HREF = "#Key">key</A>). The inverse of

<A HREF = "#Encipher">encipher</A>.

<A NAME = "Decryption"></A>

<P><DT><B>Decryption</B>

<DD>The general term for extracting information which was hidden

by <A HREF = "#Encryption">encryption</A>.

<A NAME = "DeductiveReasoning"></A>

<P><DT><B>Deductive Reasoning</B>

<DD>In the study of

<A HREF = "#Logic">logic</A>,

reasoning about a particular case from one or more general

statements; a proof. Also see:

<A HREF = "#InductiveReasoning">inductive reasoning</A> and

<A HREF = "#Fallacy">fallacy</A>.

<A NAME = "DefinedPlaintextAttack"></A>

<P><DT><B>Defined Plaintext Attack</B>

<DD>A form of

<A HREF = "#Attack">attack</A> in which the

<A HREF = "#Opponent">Opponent</A> can present arbitrary

<A HREF = "#Plaintext">plaintext</A> to be enciphered, and then

capture the resulting

<A HREF = "#Ciphertext">ciphertext</A>. The ultimate form of

<A HREF = "#KnownPlaintextAttack">known plaintext attack</A>.

<P>A defined plaintext attack can be a problem for systems which

allow unauthorized users to present arbitrary messages for

ciphering. Such attack can be made difficult by allowing only

authorized users to encipher data, by allowing only a few

messages to be enciphered between

<A HREF = "#Key">key</A> changes, by changing keys

frequently, and by enciphering each message in a different

random

<A HREF = "#MessageKey">message key</A>.

<A NAME = "DegreesOfFreedom"></A>

<P><DT><B>Degrees of Freedom</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, the number of completely

independent values in a sample. The number of sampled values or

observations or bins, less the number of defined or freedom-limiting

relationships or "constraints" between those values.

<P>If we choose two values completely independently, we have a

DF of 2. But if we must choose two values such that the second is

twice the first, we can choose only the first value independently.

Imposing a relationship on one of the sampled value means that we

will have a DF of one less than the number of samples, even though

we may end up with apparently similar sample values.

<P>In a typical

<A HREF = "#GoodnessOfFit">goodness of fit</A> test such as

<A HREF = "#ChiSquare">chi-square</A>, the reference

<A HREF = "#Distribution">distribution</A> (the expected counts) is

normalized to give the same number of counts as the experiment. This

is a constraint, so if we have N bins, we will have a DF of N - 1.

<A NAME = "DES"></A>

<P><DT><B>DES</B>

<DD>The particular

<A HREF = "#BlockCipher">block cipher</A> which is the U.S. Data

Encryption Standard. A 64-bit block cipher with a 56-bit key

organized as 16

<A HREF = "#Round">rounds</A> of operations.

<A NAME = "Decibel"></A>

<P><DT><B>Decibel</B>

<DD>Ten times the base-10 logarithm of the ratio of two

<A HREF = "#Power">power</A> values. Denoted by dB.

One-tenth of a

<A HREF = "#Bel">bel</A>.

<P>When

<A HREF = "#Voltage">voltages</A> or

<A HREF = "#Current">currents</A> are measured, power changes

as the square of these values, so a decibel is twenty times the

base-10 logarithm of the ratio of two voltages or currents.

<A NAME = "Decimal"></A>

<P><DT><B>Decimal</B>

<DD>Base 10: The numerical representation in which each digit has an

<A HREF = "#Alphabet">alphabet</A> of ten symbols, usually 0 through 9.

Also see:

<A HREF = "#Binary">binary</A>,

<A HREF = "#Octal">octal</A>, and

<A HREF = "#Hexadecimal">hexadecimal</A>.

<A NAME = "DesignStrength"></A>

<P><DT><B>Design Strength</B>

<DD>The

<A HREF = "#Keyspace">keyspace</A>; the effort required for a

<A HREF = "#BruteForceAttack">brute force attack</A>.

<A NAME = "Deterministic"></A>

<P><DT><B>Deterministic</B>

<DD>A process whose sequence of operations is fully determined

by its initial

<A HREF = "#State">state</A>. A mechanical or clockwork-like

process whose outcome is inevitable, given its initial setting.

<A HREF = "#PseudoRandom">Pseudorandom</A>.

<A NAME = "DictionaryAttack"></A>

<P><DT><B>Dictionary Attack</B>

<DD>Typically an

<A HREF = "#Attack">attack</A> on a secret password. A dictionary

of common passwords is developed, and a

<A HREF = "#BruteForceAttack">brute force attack</A> conducted

on the target with each common password.

<A NAME = "DifferentialCryptanalysis"></A>

<P><DT><B>Differential Cryptanalysis</B>

<DD>A form of

<A HREF = "#Attack">attack</A> in which the difference between

values (or keys) is used to gain some information about the

system.

<P>Also see

<A HREF = "http://www.io.com/~ritter/RES/DIFFANA.HTM">Differential

Cryptanalysis: A Literature Survey</A>, in the

<A HREF = "http://www.io.com/~ritter/#LiteratureSurveys">Literature

Surveys and Reviews</A> section of the

<A HREF = "http://www.io.com/~ritter/">Ciphers By Ritter</A> page.

<A NAME = "Diffusion"></A>

<P><DT><B>Diffusion</B>

<DD>Diffusion is the property of an operation such that changing

one

<A HREF = "#Bit">bit</A>

(or <A HREF = "#Byte">byte</A>) of the input will change adjacent

or near-by bits (or bytes) after the operation. In a

<A HREF = "#BlockCipher">block cipher</A>, diffusion propagates

bit-changes from one part of a block to other parts of the block.

Diffusion requires

<A HREF = "#Mixing">mixing</A>, and the step-by-step process of

increasing diffusion is described as

<A HREF = "#Avalanche">avalanche</A>.

Diffusion is in contrast to <A HREF = "#Confusion">confusion</A>.

<P>Normally we speak of <I>data</I> diffusion, in which changing

a tiny part of the plaintext data may affect the whole ciphertext.

But we can also speak of <I>key</I> diffusion, in which changing

even a tiny part of the

<A HREF = "#Key">key</A> should change each bit in the

ciphertext with probability 0.5.

<P>Perhaps the best diffusing

<A HREF = "#Component">component</A> is

<A HREF = "#SimpleSubstitution">substitution</A>, but

this diffuses only within a single substituted value.

<A HREF = "#SubstitutionPermutation">Substitution-permutation</A>

ciphers get around this by moving the bits of each substituted element

to other elements, substituting again, and repeating. But this only

provides guaranteed diffusion if particular substitution tables are

constructed. Another alternative is to use some sort of

<A HREF = "#BalancedBlockMixing">Balanced Block Mixing</A> which has

an inherently guaranteed diffusion, or a

<A HREF = "#VariableSizeBlockCipher">Variable Size Block Cipher</A>

construction.

Also see

<A HREF = "#OverallDiffusion">Overall Diffusion</A>.

<A NAME = "Digital"></A>

<P><DT><B>Digital</B>

<DD>Pertaining to discrete or distinct finite values. As

opposed to

<A HREF = "#Analog">analog</A>

or continuous quantities.

<A NAME = "Diode"></A>

<P><DT><B>Diode</B>

<DD>An

<A HREF = "#Electronic">electronic</A> device with two terminals

which allows

<A HREF = "#Current">current</A> to flow in only one direction.

<A NAME = "Distribution"></A>

<P><DT><B>Distribution</B>

<DD>In

<A HREF = "#Statistics">statistics</A>, the range of values which a

<A HREF = "#RandomVariable">random variable</A>, and the probability

that each value or range of values will occur. Also the probability

of test

<A HREF = "#Statistic">statistic</A> values for the case

"nothing unusual found," which is the

<A HREF = "#NullHypothesis">null hypothesis</A>.

<P>If we have a <I>discrete</I> distribution, with a finite number

of possible result values, we can speak of "frequency" and

"probability" distributions:

The "frequency distribution" is the expected <I>number</I> of

occurrences for each possible value, in a particular

<A HREF = "#Sample">sample</A> size.

The "probability distribution" is the <I>probability</I> of getting

each value, normalized to a probability of 1.0 over the sum of all

possible values.

<P>Here is a graph of a typical "discrete probability distribution"

or "discrete probability density function," which displays the

probability of getting a particular statistic value for the case

"nothing unusual found":

<PRE>

0.1| ***

| * * Y = Probability of X

Y | ** ** y = P(x)

| **** ****

0.0 -------------------

X

</PRE>

<P>Unfortunately, it is not really possible to think in the same way

about continuous distributions: Since continuous distributions have

an infinite number of possible values, the probability of getting

any <I>particular</I> value is zero. For continuous distributions,

we instead talk about the probability of getting a value in some

subrange of the overall distribution. We are often concerned with

the probability of getting a particular value or below, or the

probability of a particular value or above.

<P>Here is a graph of the related "cumulative probability distribution"

or "cumulative distribution function" (<A HREF = "#cdf">c.d.f.</A>)

for the case "nothing unusual found":

<PRE>

1.0| ******

| ** Y = Probability (0.0 to 1.0) of finding

Y | * a value which is x or less

| **

0.0 -******------------

X

</PRE>

<P>The c.d.f. is just the sum of all probabilities for a given value

or less. This is the usual sort of function used to interpret a

<A HREF = "#Statistic">statistic</A>: Given some result, we can

look up the probability of a lesser value (normally called

<I>p</I>) or a greater value (called <NOBR><I>q</I> =

1.0 - <I>p</I></NOBR>).

<P>Usually, a test statistic is designed so that extreme values are

not likely to occur by chance in the case "nothing unusual found"

which is the

<A HREF = "#NullHypothesis">null hypothesis</A>. So if we <I>do</I>

find extreme values, we have a strong argument that the results were

not due simply to random sampling or other random effects, and may

choose to reject the null hypothesis and thus accept the

<A HREF = "#AlternativeHypothesis">alternative hypothesis</A>.

<P>Common discrete distributions include the

<A HREF = "#BinomialDistribution">binomial distribution</A>, and the

<A HREF = "#PoissonDistribution">Poisson distribution</A>.

<A NAME = "Distributive"></A>

<P><DT><B>Distributive</B>

<DD>The case of a

<A HREF = "#Dyadic">dyadic</A> operation, which may be called

"multiplication," which can be applied to equations involving

another dyadic operation, which may be called "addition," such

that:

<NOBR>a(b + c) = ab + ac</NOBR> and

<NOBR>(b + c)a = ba + bc.</NOBR>

<P>Also see:

<A HREF = "#Associative">associative</A> and

<A HREF = "#Commutative">commutative</A>.

<A NAME = "DivideAndConquer"></A>

<P><DT><B>Divide and Conquer</B>

<DD>The general concept of being able to split a complexity into

several parts, each part naturally being less complex than the

total. If this is possible, The

<A HREF = "#Opponent">Opponent</A> may be able to solve all

of the parts far easier than the supposedly complex whole.

Often part of an <A HREF = "#Attack">attack</A>.

<P>This is a particular danger in cryptosystems, since most ciphers

are built from less-complex parts. Indeed, a major role of

cryptographic design is to combine small

<A HREF = "#Component">component</A> parts into a larger complex

<A HREF = "#System">system</A> which cannot be split apart.

<A NAME = "Domain"></A>

<P><DT><B>Domain</B>

<DD>The set of all arguments <I>x</I> which can be applied to a

<A HREF = "#Mapping">mapping</A>. Also see

<A HREF = "#Range">range</A>.

<A NAME = "Dyadic"></A>

<P><DT><B>Dyadic</B>

<DD>Relating to <I>dyad</I>, which is Greek for dual or having

two parts. In particular, a function with two inputs or arguments.

Also see:

<A HREF = "#Monadic">monadic</A>,

<A HREF = "#Unary">unary</A> and

<A HREF = "#Binary">binary</A>.

<A NAME = "DynamicKeying"></A>

<P><DT><B>Dynamic Keying</B>

<DD>That aspect of a cipher which allows a

<A HREF = "#Key">key</A> to be changed with

minimal overhead. A dynamically-keyed

<A HREF = "#BlockCipher">block cipher</A> might impose

little or no additional computation to change a key on a

block-by-block basis. The dynamic aspect of keying could be

just one of multiple keying mechanisms in the same cipher.

<P>One way to have a dynamic key in a block cipher is to include

the key value along with the

<A HREF = "#Plaintext">plaintext</A> data. But this is

normally practical only with blocks of huge size, or

<A HREF = "#VariableSizeBlockCipher">variable size</A> blocks.

<P>Another way to have a dynamic key in a block cipher is to add a

<A HREF = "#Confusion">confusion</A>

<A HREF = "#Layer">layer</A> which mixes the key value with the

block. For example, exclusive-OR could be used to mix a 64-bit

key with a 64-bit data block.

<A NAME = "DynamicSubstitutionCombiner"></A>

<P><DT><B>Dynamic Substitution Combiner</B>

<DD>The

<A HREF = "#Combiner">combining</A>

<A HREF = "#Mechanism">mechanism</A> described in U.S. Patent

4,979,832 (see the

<A HREF = "http://www.io.com/~ritter/#DynSubTech">Dynamic Substitution articles</A> on the

<A HREF = "http://www.io.com/~ritter/">Ciphers By Ritter</A> page).

<P>Dynamic Substitution is the use of an invertible

<A HREF = "#SubstitutionTable">substitution table</A>

in which the arrangement of the entries changes dynamically during

operation. This is particularly useful as a strong replacement for

the strengthless

<A HREF = "#ExclusiveOR">exclusive-OR</A> combiner in

<A HREF = "#StreamCipher">stream ciphers</A>.

<P>The arrangement of a

<A HREF = "#Key">keyed</A> table starts out unknown to an

<A HREF = "#Opponent">Opponent</A>. From the Opponent's point of

view, each table entry could be any possible value with uniform

probability.

But after the first value is mapped through that table, the used

transformation (table entry) is at least potentially exposed, and

no longer can be considered a completely unknown probability.

Dynamic Substitution acts to make the used transformation again

completely unknown and unbiased, by allowing it to take on any

possible mapping. As a first approximation, the amount of

information leaked about table contents is replaced by information

used to re-define each used entry.

<P>In the usual case, an invertible substitution table is keyed by

<A HREF = "#Shuffle">shuffling</A> under the control of a

<A HREF = "#RandomNumberGenerator">random number generator</A>.

One combiner input value is used to select a value from within

that table to be the result or output. The other combiner input

value is used simply to select an entry, and then the values at

the two selected entries are exchanged. So as soon as a

<A HREF = "#Plaintext">plaintext</A> mapping is used, it is

immediately reset to any possibility, and the more often any

plaintext value occurs, the more often that transformation changes.

<P>Also see

<A HREF = "#BalancedBlockMixing">Balanced Block Mixing</A>, and

<A HREF = "#VariableSizeBlockCipher">Variable Size Block Cipher</A>.

<A NAME = "DynamicTransposition"></A>

<P><DT><B>Dynamic Transposition</B>

<DD>A

<A HREF = "#BlockCipher">block cipher</A> which first creates an

exact bit-<A HREF = "#Balance">balance</A> within each

<A HREF = "#Block">block</A>, and then

<A HREF = "#Shuffle">shuffles</A> the bits within a block,

each block being

<A HREF = "#Permutation">permuted</A> independently from a

<A HREF = "#Key">keyed</A>

<A HREF = "#RandomNumberGenerator">random number generator</A>.

<P>Since each block --

<A HREF = "#Plaintext">plaintext</A> or

<A HREF = "#Ciphertext">ciphertext</A> --

contains exactly the same number of 1's and 0's, every possible

plaintext block is just some permutation of any possible

ciphertext block. And since any possible plaintext block can be

produced from any ciphertext block in a vast plethora of different

ways, the keying sequence is hidden even from

<A HREF = "#KnownPlaintextAttack">known plaintext</A>. And

<A HREF = "#DefinedPlaintextAttack">defined plaintext</A>

is easily defeated with the usual

<A HREF = "#MessageKey">message key</A>.

To the extent that

every possible plaintext block can be produced, the cipher approaches

<A HREF = "#PerfectSecrecy">perfect secrecy</A>.

<P>See the article

<A HREF = "http://www.io.com/~ritter/ARTS/DYNTRAN2.HTM">Transposition

Cipher with Pseudo-Random Shuffling: The Dynamic Transposition

Combiner</A>.

<A NAME = "ECB"></A>

<P><DT><HR><P><B>ECB</B>

<DD>ECB or Electronic Code Book is an

<A HREF = "#OperatingMode">operating mode</A> for

<A HREF = "#BlockCipher">block ciphers</A>. Presumably the name

comes from the observation that a block cipher under a fixed

<A HREF = "#Key">key</A>

functions much like a physical codebook: Each possible

<A HREF = "#Plaintext">plaintext</A>

<A HREF = "#Block">block</A> value has a corresponding

<A HREF = "#Ciphertext">ciphertext</A> value, and vise versa.

<P>ECB is the naive method of applying a block cipher, in that

the plaintext is simply partitioned into

appropriate size blocks, and each block is enciphered separately

and independently. When we have a small block size, ECB is

generally unwise, because language text has biased statistics which

will result in some block values being re-used frequently, and this

repetition will show up in the raw ciphertext.

This is the basis for a successful

<A HREF = "#CodebookAttack">codebook attack</A>.

<P>On the other hand, if we have a large block, we may expect it

to contain enough (at least, say, 64 bits) uniqueness or

"<A HREF = "#Entropy">entropy</A>"

to prevent a codebook attack. In that case, ECB mode

has the advantage of supporting independent ciphering of each

block. This, in turn, supports various things, like the use of

multiple ciphering hardware operating in parallel for higher speeds.

<P>As another example, modern packet-switching network technologies

often deliver raw packets out of order. The packets will be

re-ordered eventually, but having out-of-sequence packets can be a

problem for low-level ciphering if the blocks are not ciphered

independently.

<A NAME = "ElectricField"></A>

<P><DT><B>Electric Field</B>

<DD>The fundamental physical force resulting from the attraction

of opposing charges.

<A NAME = "ElectromagneticField"></A>

<P><DT><B>Electromagnetic Field</B>

<DD>The remarkable self-propagating physical field consisting of

energy distributed between

<A HREF = "#ElectricField">electric</A> and

<A HREF = "#MagneticField">magnetic</A> fields. Energy in

the electric or potential field collapses and creates or

"charges up" a magnetic field. Energy in the magnetic field

collapses and "charges up" an electric field.

This process allows physical electrical and magnetic fields --

two fairly short-range phenomena -- to "propagate" and thus carry

energy over relatively large distances at the speed of light.

Examples include light, "radio" waves (including TV, cell phones,

etc.), and microwave cooking.

<P>It is important to distinguish between a true electromagnetic

field, and the simpler and range-limited electric and magnetic fields

produced by an electrical clock, motor, or power lines. It is also

important to distinguish between the light-like expanding or

"radiating" property of an electromagnetic field, and the damaging

ionizing radiation produced by a radioactive source.

<P>As far as we know -- and a great many experiments have been

conducted on this -- electromagnetic waves are not life-threatening

(unless they transfer enough power to dangerously heat the water in

our cells).

The belief that electromagnetic fields are not dangerous is also

<I>reasonable,</I> since light itself is an electromagnetic wave,

and life on Earth developed in the context of the electromagnetic

field from the Sun. Indeed, plants actually use that field to their

and our great benefit.

<A NAME = "Electronic"></A>

<P><DT><B>Electronic</B>

<DD>Having to do with the control and use of physical electrons, as

electrical potential or

<A HREF = "#Voltage">voltage</A>, electrical flow or

<A HREF = "#Current">current</A>, and generally both. See

<A HREF = "#Hardware">hardware</A> and

<A HREF = "#Component">component</A>.

<A NAME = "Encipher"></A>

<P><DT><B>Encipher</B>

<DD>The process which will transform information or

<A HREF = "#Plaintext">plaintext</A> into

one of plethora of intermediate forms or

<A HREF = "#Ciphertext">ciphertext</A>, as selected

by a <A HREF = "#Key">key</A>. The inverse of

<A HREF = "#Decipher">decipher</A>.

Login or Register to add favorites

- ActiveX (932)
- Advisory (77,415)
- Arbitrary (15,085)
- BBS (2,859)
- Bypass (1,562)
- CGI (1,011)
- Code Execution (6,650)
- Conference (668)
- Cracker (797)
- CSRF (3,270)
- DoS (21,795)
- Encryption (2,330)
- Exploit (49,760)
- File Inclusion (4,146)
- File Upload (942)
- Firewall (821)
- Info Disclosure (2,546)
- Intrusion Detection (851)
- Java (2,781)
- JavaScript (793)
- Kernel (6,015)
- Local (13,990)
- Magazine (586)
- Overflow (12,140)
- Perl (1,410)
- PHP (5,039)
- Proof of Concept (2,278)
- Protocol (3,299)
- Python (1,394)
- Remote (29,636)
- Root (3,445)
- Ruby (574)
- Scanner (1,630)
- Security Tool (7,679)
- Shell (3,059)
- Shellcode (1,202)
- Sniffer (880)
- Spoof (2,082)
- SQL Injection (15,994)
- TCP (2,352)
- Trojan (672)
- UDP (866)
- Virus (659)
- Vulnerability (30,411)
- Web (8,997)
- Whitepaper (3,712)
- x86 (942)
- XSS (17,304)
- Other

- AIX (426)
- Apple (1,883)
- BSD (368)
- CentOS (55)
- Cisco (1,912)
- Debian (5,948)
- Fedora (1,690)
- FreeBSD (1,241)
- Gentoo (4,152)
- HPUX (878)
- iOS (318)
- iPhone (108)
- IRIX (220)
- Juniper (67)
- Linux (42,104)
- Mac OS X (683)
- Mandriva (3,105)
- NetBSD (255)
- OpenBSD (478)
- RedHat (11,497)
- Slackware (941)
- Solaris (1,607)
- SUSE (1,444)
- Ubuntu (7,786)
- UNIX (9,060)
- UnixWare (185)
- Windows (6,405)
- Other

- Site Links
- News by Month
- News Tags
- Files by Month
- File Tags
- File Directory

- Services
- Security Services
- Hosting By
- Rokasec