Ciphers By Ritter: Cryptography and Technology (original) (raw)

[Logo: Ciphers By Ritter -- Ritter Labs]

[[Mixing Core]](#MixTech) [[VSBC Core]](#VSBCTech)

Novel Encryption Technology

Available Nowhere Else

[[Balanced Block Mixing]](#BBMTech)
Orthogonal Latin Squares Balanced Block Mixing

Questions, Comments or HTML Problems? ContactTerry Ritter (About the Author), at ritter@ciphersbyritter.com.Last Update: 2010 November 22(Update Log). Also see:Net Links.

Search engines often find older articles and miss the newer summaries in theGlossary. For the latest information, always check theGlossary!

Ritter Labs Offers:

Ciphers By Ritter Contents

Technology Overview

We own and control novelcryptographic technologies:

Our novel ciphering technologies provide unique system-level advantages, including:

Available for license within The United States.

Dynamic Substitution: U.S. Patent 4,979,832

Invertible Substitution and Changes Controller A nonlinear yet reversible, dynamicallybalanced datacombiner with memory or "state."

The figure shows at the top a left data input and a right confusion or "running key" input. A plaintext data byte is transformed through the invertible substitution table into ciphertext and output to the right. Then the changes controller re-arranges the table.

Dynamic Substitution can replace theexclusive-OR(XOR)combiner instream ciphers. Underknown-plaintextconditions, XOR combining has absolutely no strength at all. Good ciphers are expected to defeat known-plaintext.

Typically, Dynamic Substitution tables are initialized bykeying, and are verynonlinear. Several strength opportunities not available with XOR combiners can be exploited with DynSub:

The improved strength of multiple DynSub combiner systems acts to protect the confusion sequence generator (RNG) at the system level. Since most technical attacks on stream ciphers involve exposing the state of the RNG, complicating or eliminating such attacks is a significant strength advantage.

Dynamic Substitution Summary Show in HTML Pseudo-Slides

Dynamic Substitution in Stream Cipher Cryptography (30K), the current HTML article.

Dynamic Substitution 1990 (38K), the original refereed article.

Cloak2: a Dynamic Substitution file cipher for DOS

Cloak2 Features (7K): A general introduction

The Cloak2 Cipher User's Manual (93K)

Cloak2 Quick Start (10K): Simple installation and use of the Cloak2 program

The Cloak2 Cipher Design (26K): A technical description and strength analysis

Penknife: a Dynamic Substitution email cipher for DOS

Penknife Features (7K): A general introduction

The Penknife Cipher User's Manual (105K)

Penknife Quick Start (11K): Simple installation and use of the Penknife program

The Penknife Cipher Design (32K): A technical description and strength analysis

Balanced Block Mixing: U.S. Patent 5,623,549 (also seeMixing Ciphers)

Two Orthogonal Latin Squares An orthogonal pair ofLatin squares which reversibly mix two inputblocks or values of some power-of-2 size into two output blocks of the original size.

The figure shows at the top a left input block with a value of 1 selecting row 1 (of 0..3) in both squares, and a right input value of 3 selecting column 3 in both squares. Each selected element, here 2 and 0, becomes an output value at the bottom. Practical BBM components typically mix two input bytes into two output bytes.FFT-like networks of BBM's essentially become BBM's with some power-of-2 inputs and outputs.

A BBM component has strong guarantees of balance and equal distribution. It performs an arguably "perfect" mixing of _n_elements using log n mixing sublevels of n operations each.

There are three classes of realization:

A BBM can be seen as a way of emulating larger tables using small ones. This is interesting because a conventionalblock ciphermerely emulates a table far too large to build. A construction based on small keyable tables makes sense. Currently, the table-only realization seems most desirable, because that avoids the linear transformations of the other models. Tables hold the maximum amount of keyed and nonlinear state, and that state is what an opponent must unravel to break the cipher. The cipher is keyed by constructing a particularorthogonal Latin square pairfor each mixing element, which is fairly easy to do.

Balanced Block Mixers for Block Cipher Cryptography (23K), the current HTML article.

Active Balanced Block Mixing in JavaScript (21K): The Balanced Block Mixing computation in mod 2 polynomials, with the ability to calculate results and show the whole table. Also 4-element FFT-style block mixing.

Keyed Balanced Size-Preserving Block Mixing Transforms (now Balanced Block Mixers) (26K): the original ASCII article.

Large Block DES mixing development (18K) the overall development project.

Mixing Ciphers: UsingBalanced Block Mixing

A 64-bit Hybrid Mixing Cipher Scalable and fast block cipher designs with guaranteed diffusion and dynamically variable block size in power-of-2 steps.

Here we have a typical hybrid realization: The figure shows connections from ablock of 8 input bytes at the top, which are each substituted through keyed "8-bit" invertible tables orS-boxes.Each table represents about 1684 bits of keying.

Each yellow diamond represents half of a linearBBMcomponent. Each mixing takes two bytes in, and produces a 2-byte result. The mixings are arranged in anFFT-style pattern which mixes every byte across the entire block using only byte mixings.

We have a top row of substitutions, then a complete mixing. Then we have another row of substitutions and another complete mixing. Then we have a final substitution row, which produces 8 bytes of ciphertext out the bottom.

FFT-style mixing patterns can be computed at ciphering time, so blocks of dynamically arbitrary power-of-2 size can be ciphered. Extremely large blocks can be ciphered almost as fast (per byte) as smaller blocks, thus possibly avoidingCBCchaining, and providing room for authentication and dynamic keying fields.

A 64-bit Table Mixing Cipher

Here we have a typical hardware table-only realization: This is again an 8-byte block, but the 16 input lines are4-bit nybbles instead of 8-bit bytes. Each BBM mixing is a key-selectedorthogonal Latin square pairin a RAM table. Since the mixing is inherently nonlinear, substitution tables are unnecessary.

There are four sublayers, each consisting of eight BBM tables, that mix every input bit to every output bit. Each table holds an order-16 oLs in 256 bytes. Thus, each sublayer needs 8 * 256 = 2048 bytes of store. Since there are 4 sublayers, the total store is2048 * 4 = 8192 bytes for the whole cipher.

In hardware, mixing ciphers can be much faster than most other block cipher approaches because all mixings can operate simultaneously. Table mixings are just table look-ups with a single RAM read each. Chip layout consists almost entirely of RAM and data bus.

Hardware bandwidth typically is a full block per clock cycle, with a different block being processed in each mixing sublayer. With a 450MHz clock, 8-byte block designs do 3,600 megabytes/sec. Doubling the block size doubles the processing bandwidth, but also doubles the number of tables, plus adding another mixing sublayer.

It is possible to save RAM by using order-4oLsmixings, which need only 8 bytes of store (16 entries of 4 bits each). Since they mix only 2-bit pairs, we need 16 tables per8-byte block. Then we need another sublayer, for a total of 5, and thus5 * 16 = 80 mixings. That implies 80 * 8 = 640 bytes of store for the whole 8-byte block cipher. This cipher still has 80 * 12.75 = 1020 bits of keying, but the advantage is in larger block widths.

At the 64-byte block size, we start to reaphuge block cipher advantages, while running at 28,800 megabytes/sec. With order-4 tables, we need 128 tables per sublayer, with 8 sublayers, and 128 * 8 * 12.75 = 13,056 bits of keying. This design needs only 128 * 8 * 8 = 8192 bytes of RAM (in 1024 independent 8-byte RAM blobs) for the full cipher.

Mixing Cipher Summary Show in HTML Pseudo-Slides

A Mixing Core for Block Cipher Cryptography (35K): description, figures, and discussion.

A Keyed Shuffling System for Block Cipher Cryptography (17K): key hashing and RNG, figures and discussion.

Active Balanced Block Mixing in JavaScript (21K): The Balanced Block Mixing computation in mod 2 polynomials, with the ability to calculate results and show the whole table. Also 4-element FFT-style block mixing.

Measured Boolean Function Nonlinearity in Mixing Cipher Constructions (24K): Experimental nonlinearity distributions for random 5-bit tables, 10-bit tables, and 10-bit mixing constructions.

Efficient FFT-Style Mixing for Block Cipher Cryptography (10K), description, figures, and routines in both Pascal and C for a straightforward and efficient mixing pattern.

Extreme Hardware Speed in Large Block Mixing Ciphers (8K), a sketch of a practical chip realization of a 64-byte block cipher operating at up to 12.8 GB/sec.

Hardware Blowfish and Mixing Ciphers Compared (6K), a sketch comparing chip area and functionality between several 64-bit Blowfish and Mixing cipher realizations.

Fencing and Mixing Ciphers (11K), prototype implementations and tests. Experimental realizations initialize the full 128K table store in 76 msec.

Fenced DES (24K), the technology in action.

Variable Size Block Ciphers: U.S. Patent 5,727,062

A Variable Size Mixing Cipher Scalable and fast cipher designs with good block cipher diffusion and dynamically variable block size to the byte.

The figure shows at the top connections from 5 plaintext bytes (of a presumably larger block) which are each substituted, and then participate in a right-going one-way diffusion. The hourglass shapes areBBMcomponents, which mix in the direction of the arrow two input values into two output values. Subsequent substitutions and diffusions eventually produce 5 ciphertext bytes on the bottom connections.

The use of large blocks can avoid the need for CBC chaining, and provide room for authentication and dynamic keying fields. The ability to cipher blocks of odd size supports the ciphering of_existing_ data structures without re-design of the existing system. The use of random-size blocks in file ciphering provides an unexpected new level of strength, since the bytes composing any particular block are unknown to an attacker.

A Variable Size Core for Block Cipher Cryptography (37K): description, figure, and discussion.

A Keyed Shuffling System for Block Cipher Cryptography (17K): key hashing and RNG, figures and discussion.

Active Balanced Block Mixing in JavaScript (21K): The Balanced Block Mixing computation in mod 2 polynomials, with the ability to calculate results and show the whole table. Also 4-element FFT-style block mixing.

Measured Boolean Function Nonlinearity in Variable Size Block Ciphers (29K) Experimental nonlinearity distributions for random 4-bit tables, random 12-bit tables, and 12-bit VSBC constructions.

Efficient One-Way Mixing Diffusions (10K), description, figures, and routines in both Pascal and C for straightforward and efficient one-way mixing layers.

Defined Plaintext Attack on a Simplified BBM VSBC (12K + 5 .GIF), a currently unsuccessful approach

Variable Size Block Ciphers (24K), the older HTML article (with .GIF graphics).

Variable Size Block Cipher Designs (Realized Prototypes) (13K), the newer article (with ASCII graphics), showing actual experience with VSBC designs.

VSBC Newsgroup Discussion (6K), the original sci.crypt discussions.

Technical Articles

Attempts at attacking, solving and explaining some aspects of cryptographic design.

Dynamic Transposition Revisited Again (2001) (40K)

A block cipher based on transposition, using stream cipher techniques, generates aperfect secrecytransformation on a block-by-block basis. The second, expanded version of the "revisited" article.
**Dynamic Transposition Ciphering (2001) (730K)**The original "revisited" article, with controversial sci.crypt conversations on serious Dynamic Transposition ciphering.

**Cryptography: Is Staying with the Herd Really Best? (Copyright 1999, IEEE.)**A guest "Internet Watch" column in the IEEE Computer Society magazine for August, 1999. (Computer. 32(8): 94-95.)

The commonly-accepted argument that cryptography is too important to allow the use of "unproven" ciphers is shown to be fundamentally flawed. Also see:Comments on Staying with the Herd (1999) (295k).

Experimental Characterization of Recorded Noise (1999) (11K index into 25 subpages with 3 .GIF graphs each)

Characteristics of experimental noise generators are calculated and graphed.

Random Noise Sources (1999) (25K + many .GIF's and .JPG's)

Modern, simple, tested, battery-powered designs produce "unknowable" analog noise to be digitized by a sound card.

Orthogonal Latin Squares, Nonlinear Balanced Block Mixers, and Mixing Ciphers (1998) (31K)

The construction of nonlinear orthogonal Latin squares of order 16, and 8-bit nonlinear BBM's, with experimental results. The sci.crypt article.

Practical Latin Square Combiners (1998) (22K)

The construction of nonlinear Latin squares of order 16 for combining 4-bit nybbles. The sci.crypt article.

Break This 8-Bit Block Mixing Cipher (1998) (57K)

An 8-bit cipher model which uses keyed 4-bit tables is presented to explore the strength of the structure. The sci.crypt article.

Break This 4-Bit Block Mixing Cipher (1998) (8K)

A 4-bit cipher model which uses keyed 2-bit tables is presented as a challenge to explore the strength of the structure. The sci.crypt article.

Measured Distant Avalanche in Large Block Ciphers (1998) (34K)

The possibility of mixing locality is explored experimentally in Mixing and Variable Size Block Ciphers. The sci.crypt article.

Measured Boolean Function Nonlinearity in Feistel Cipher Constructions (1998) (32K)

The experimental nonlinearity distributions for random 5-bit tables, random 10-bit tables, and 10-bit Feistel constructions are developed and compared. The sci.crypt article.

Measured Boolean Function Nonlinearity in Variable Size Block Ciphers (1998) (29K)

The experimental nonlinearity distributions for random 4-bit tables, random 12-bit tables, and 12-bit VSBC constructions are developed and compared. The sci.crypt article.

Measuring Boolean Function Nonlinearity by Walsh Transform (1998) (20K)

How to compute the distance to an affine Boolean function by hand. How to compute a Fast Walsh Transform (FWT) by hand, or by Pascal routine. The sci.crypt article.

Measured Boolean Function Nonlinearity in Mixing Cipher Constructions (1997) (25K)

The experimental nonlinearity distributions for random 5-bit tables, random 10-bit tables, and 10-bit Mixing constructions are developed and compared. The sci.crypt article.

Chi-Square Bias in Runs-Up/Down RNG Tests (1997) (13K)

Correct expectation values for runs-up and runs-down RNG testing. The sci.crypt article.

Fenced DES (1994) (24K)

"A larger and better DES." A 256-bit block cipher using DES as a trusted component. Four separate DES operations are Balanced Block Mixed, and protected by outer layers of substitution operations.

Estimating Population from Repetitions in Accumulated Random Samples (1994) (82K)

The Birthday Paradox: By repeatedly drawing values from a given population, eventually some values will appear again or "repeat." A new relationship _exactly_predicts population from the average number of repetitions. (Population estimation can be used to check the amount of effective state in a really-random generator and the number of keys in a block cipher.) The published refereed article, with many .GIF graphics. Also see thePopulation Estimation Worksheets in JavaScript, for an implementation.

Voice and Video Cryptography in a DSP Environment (1992) (27K)

An "Intro to Crypto" for DSP designers. Presented at The Second Annual Texas Instruments TMS320 Educators Conference, August 5-7 1992, Houston, Texas. The published article.

The Efficient Generation of Cryptographic Confusion Sequences (1991) (168K):

A survey of the various techniques used to build the running-key "confusion" generators used in stream ciphers. 51 pp., 213 refs. The published article.

The Politics of Software Patents (1991) (30K)

A response to the November, 1990 Dr. Dobb's Journal article by "The League for Programming Freedom." (The LPF paper "Against Software Patents"http://lpf.ai.mit.edu/Patents/against-software-patents.htmlappears to be the same as the DDJ article.) The published article.

Transposition Cipher with Pseudo-Random Shuffling: The Dynamic Transposition Combiner (1991) (44K)

A way of partitioning arbitrary _data_with padding to produce blocks of a fixed size with an exact balance of 1's and 0's. Bit-permutation is then used to encipher and decipher. The result is that any enciphered block can be deciphered into any possible plaintext block, in a way which strongly hides the enciphering sequence. This approaches ideal secrecy. The published refereed article.

Substitution Cipher with Pseudo-Random Shuffling: The Dynamic Substitution Combiner (1990) (38K)

A nonlinear mechanism for reversibly combining a data stream with confusion, thus replacing the usual stream-cipher exclusive-OR with substitution tables. Typically, the content of the tables is permuted after every character ciphered, thus preventing the usual known-plaintext attack. Multiple-level combinings become reasonable, as do selections among many different combiners. The published refereed article, with .GIF graphics.

The Great CRC Mystery (1986) (34K, plus 6K+14K in listings)

Discussion of Cyclic Redundancy Check (CRC) with six different CRC implementations spanning two orders of magnitude in throughput. The published article, with published listings.

JavaScript

Technical articles which actually function.

Normal, Chi-Square and Kolmogorov-Smirnov Statistics Functions in JavaScript (50K)

Computations of combinatoric and statistics functions and inverses which deliver good accuracy over a wide range of values. Accuracy tests allow the functions to be checked in any computing environment.

Base Conversion, Logs, Powers, Factorials, Permutations and Combinations in JavaScript (27K)

Computations of combinatoric and statistics functions and inverses which deliver good accuracy over a wide range of values. Accuracy tests allow the functions to be checked in any computing environment.

Binomial and Poisson Statistics Functions in JavaScript (24K)

Computations of combinatoric and statistics functions and inverses which deliver good accuracy over a wide range of values. Accuracy tests allow the functions to be checked in any computing environment.

Active Boolean Function Nonlinearity Measurement in JavaScript (41K)

A detailed discussion of cryptographic Boolean function nonlinearity, what it means and how it is computed, with active JavaScript panels to perform the computation.

Active Balanced Block Mixing in JavaScript (21K)

The Balanced Block Mixing computation in mod 2 polynomials, with the ability to calculate results and show the whole table. Also 4-element FFT-style block mixing.

Population Estimation Worksheets in JavaScript UPDATED 2005 Feb 22 (28K)

Estimate the effective "population" (the number of unique values) produced by "really random" generators, or the number of keys in (small) ciphers. You run the experiments and enter the numbers, the worksheets do the computations.

Usenet Discussions

Various interesting discussions from Usenet, typically from thesci.crypt newsgroup.

CIPHERS (seeglossary andsurveys)

Stream Ciphers Using Variable Amounts of RNG State (2001) (74K)

Can a newbie with an idea get a fair reception on sci.crypt? Apparently not.

The IV in Block Cipher CBC Mode (2001) (186K)

Can a non-crippie with a simple question get a simple authoritative answer on sci.crypt? Apparently not.

Dynamic Transposition Ciphering (2001) (730K)

The original "revisited" article, with controversial sci.crypt conversations on serious Dynamic Transposition ciphering.

Padding and Bijection (2000) (121K)

What is all this stuff about "bijective" ciphering?

Latin Square Combining (2000) (121K)

Conventional stream ciphers need data combining, and a Latin square is a good choice. Now, can we get the same effect with less memory?

Cascade Ciphering (2000) (72K)

What are the consequences of using multiple ciphers?

Salts (2000) (36K)

A "salt" is a value used to modify a hash of a password.

The Illusion of Security (2000) (162K)

Everyone trusts our well-known ciphers, but they should not.

Is Hardware More Trustable than Software? (2000) (46K)

A short conversation on the difficulty of trusting hardware.

Can We Trust Our Cipher? (2000) (41K)

We trust bridges; why not trust ciphers?

MacLaren-Marsaglia Again (2000) (40K)

Does the MacLaren-Marsaglia combiner (described in Knuth II) make a secure stream cipher?

Triple-DES is Proven to be very Secure? (1999) (90K)

In a discussion about AES, we find the statement made and agreed that "Triple-DES is proven to be very secure." That was enough for me, since there is no such "proof," either in mathematics or in practice.

Can We Trust the Experts? (1999) (105K)

If we trust doctors, why not trust crypto experts?

Can Cryptanalysis Give Us Confidence? (1999) (168K)

If cryptanalysis does not give us confidence in the strength of our ciphers, what does?

Risks of Relying on Cryptography Discussion (1999) (840K)

Discussions triggered by Schneier's article "Risks of Relying on Cryptography." Some people want AES to have multiple ciphers, which leads to conversations on my multiple ciphers and multiciphering proposal.

Comments on Staying with the Herd (1999) (295k)

Discussions triggered by my article "Cryptography: Is Staying with the Herd Really Best?" in the August 1999 IEEE Computer.

Fixing Strength Problems in Cipher Use (1999) (644K)

A sci.crypt conversation on fundamental problems in cryptography.

Block Cipher Modes for One-Block Messages? (1999) (17K)

If we use a block cipher, how can we avoid causing the message to expand when ciphering? And what do we do when the message is shorter than a block?

The Britannica Stream Cipher (1999) (61K)

The secret "other type" of stream cipher.

Random Access to Encrypted Data (1998) (32K)

Chaining modes are a virtual requirement for the secure use of ciphers with small blocks. But then how do we get random access?

Combiner-Type Algorithms (1998)

Comments on codebook and combiner algorithms.

The Homophonic Block Cipher Construction (1998) (213K)

A discussion of noise in plaintext, homophonic ciphers, large blocks and other constructions.

Ritter's Comments on the One Time Pad (1997)

Is it the best possible cipher?

Generalized Feistel Networks (1995)

DES uses two subblocks, and at each level one subblock is confused and combined with the other. What happens if we have many subblocks?

SAFER K-64 (1994, 1995)

Massey's block cipher which uses a sort of unbalanced block mixing component.

Modified RC4 is a Dynamic Substitution Cipher (1994)

An idea whose time is coming?

Is Triple-DES Stronger than DES? (1994)

Yes, probably, but is this proven?

Simon's Braided Stream Cipher (1991, 1992)

Sort of like a One Time Pad which transports both data and new keying material

CRYPTANALYSIS (seeglossary andsurveys)

Multiciphering and Random Cipher Selection in Shannon (2001) (40K)

Using more than one cipher (with independent keys), and selecting among many ciphers for use, are concepts which trace to the very beginning of mathematical cryptography.

Known-Plaintext and Compression (2001) (270K)

Anyone who has actually attacked a real cipher in practice will know the irreplaceable advantage of known-plaintext.

Hidden Markov Models (2000) (16K)

Some information on HMM's.

The Redundancy of English (2000) (12K)

Everybody always wants to know.

Differential Cryptanalysis (1999) (7K)

What the heck is Differential Cryptanalysis anyway?

What is a "Group" in Block Cipher Analysis? (1998) (13K)

We assume that Triple-DES is stronger than plain DES because DES is not a group. So what does that mean?

The Value of Cryptanalysis (1998) (949K)

A major discussion starting from Schneier's "Memo to the Amateur Cipher Designer" and continuing from there.

The Meaning of "Break" (1998) (35K)

A discussion of what it means to claim a cipher is "broken."

Teledyne Crypto Patent (2000) (17k)

The magic words: Dynamic Substitution.

What's the Meaning of "Invent"? (1999) (37K)

What does it take to be "first to invent," and what does it take to prove it?

Patent Notebook Consequences (1998) (13K)

Needing to fill in a lab notebook -- and get witness signatures -- is a hassle which leads to omissions. Can we avoid this?

Software Patents? (1998) (278K)

A discussion of software intellectual property, inevitably drifting into a discussion of software patents, and their impact on free or "open" software.

Software, Patents and Algorithms (1998) (213K)

"Software patents," starting out with the infamous XOR cursor patent and ending with "what is an algorithm." A discussion of software protection, infringement, and the LZW patent.

Patents and Personal Use (1998) (68K)

What are the limits of making and using a patented thing?

AES and Patent Rights (1998) (306K)

A major discussion about the Advanced Encryption Standard and individual patent rights.

RANDOMNESS -- PROCESSING

Hashing and CRC (1998-2000) (254K)

Discussions on hashing and CRC.

Randomness and the CRC (1997)

Is the CRC really useless?

Unbiased Range Reduction for RNG's (1994, 1995)

Suppose we have a good 16-bit-wide RNG: This is a range of 0..65535. But suppose we want to choose uniformly on a range of 0..39999: What do we do?

Improving Randomness (1990-1992)

Physical randomness is processed before use

RANDOMNESS -- PSEUDO (seesurveys and relatedlinks)

Simple Seed Selection in BB&S (2001) (226K)

We finally have a reasonable way to provably eliminate the (extremely low) possibility of using a short cycle in BB&S.

Proof and Strength in the BB&S RNG (2000) (635K)

Essentially a continuation of the previous BB&S battle, with perhaps a little more support this time.

Is a BB&S System "Proven Secure"? (2000) (217K)

A BB&S RNG construction inherently has short cycles which are weak keys. The BB&S article shows how avoid such cycles, but modern cryptography does not bother. In what way can the result be called "proven secure"?

Random Numbers in C (1999) (159K)

Random number generators (_pseudo_-random, of course) in C; mostly fast one-liners for "inline" use (to eliminate call / return overhead).

Blum, Blum & Shub (1994, 1995)

The famous "unpredictable" x^2 Mod N RNG. But is it really as easy as it looks? (Also see myRNG article.)

RANDOMNESS -- REAL (seesurveys and relatedlinks)

Allan Variance and Deviation (2001) (13K)

Allan Variance: what is it, and what does it mean?

FM Radio Noise (2000) (65K)

Is an FM radio a good source of noise?

The Hardware Random Number Generator (1999) (390K)

The conversation starts with a particular prescription for a physically-random generator. It then breaks into mostly theory, with a few comments on alternate approaches.

The Pentium III RNG (1999) (100K)

Most of this discussion concerns the privacy aspects of having a serial number on a processor chip. But there are a few articles about hardware random number generation technology.

Random Numbers from a Sound Card (1999) (94K)

Everybody has a sound card, so we all have a physically-random noise generator -- a source of absolute randomness -- right? A discussion starting with sound cards recording noise, and ending with theories of randomness.

The Several Types of Random (1998)

A discussion of the term "truly random."

Junction Noise Experiments (1994)

An account of experiments in semiconductor noise.

Nico's Software "Really Random" Generator for PC's (1992)

What is it, how does it work, and how could it work?

Really Random Generators (1990, 1992)

Electronic hardware for generating really-random values

"Essential" Randomness (1991)

Is there any?

RANDOMNESS -- TESTS (see relatedlinks)

Birthday Attack Calculations (1998-99) (57K)

How can we relate the number of elements in a population and the number of random samples needed before we expect to find a duplicate or match?

Tests for Randomness (1998)

A discussion about distinguishing a random sequence from a non-random sequence.

General References on Testing RNG's (1995)

A short bibliography.

Testing Hardware RNG's (1994)

Nico's RNG helped show we had a problem. (Also see myBirthday article.)

Randomness Tests (1993, 1994)

Fewer comments than I expected.

Maurer's Test (1993, 1994)

It is claimed to be "universal," but does that mean it will detect all possible RNG problems?

OTHER PAGES

Latin Squares in Cryptography (2001) (10K)

So how are Latin squares used in cryptography?

Bit Counting and Similar Instructions (1998-99) (48K)

Population count and binary logarithm comments.

Ritter's Latest Comments (1997-1998)

Saving the good stuff from extinction: "counter mode" for random sequences, "prior art" in patents, backdoors in tables, scalable ciphers, randomness testing.

Literature Surveys and Reviews

Most modern cryptography exists somewhere amidst thousands of published academic articles. No current texts do justice to this huge body of work, and there are too many references for an individual to know where to start. Here I select some of my favorite research stories, outline the coverage of the most important articles, and occasionally suggest directions for the future. Obviously, this will be totally non-controversial.

Send any and all suggestions by e-mail, but to contribute to the discussion, start or join a thread in the sci.crypt Newsgroup. Articles with particularly incisive comments will be archived here as alternate views of reality.

CIPHERS (seeglossary and relateddiscussions)

S-Box Design: A Literature Survey (59K)

Linear and Differential Cryptanalysis depend upon various characteristics of cipher S-boxes. So what is known about S-box design?

The Story of Combiner Correlation: A Literature Survey (58K)

Once upon a time, a stream cipher was just a simple random number generator (RNG) confusion generator, and an exclusive-OR data / confusion combiner. This was easily broken with a small amount of known-plaintext, so it was thought useful to combine multiple simple RNG's to get a far more complex confusion sequence. This turns out to be_much_ harder than it looks.

CRYPTANALYSIS (seeglossary and relateddiscussions)

Differential Cryptanalysis: A Literature Survey (35K)

Differential Cryptanalysis has been used to "break" or at least "bend" a whole list of ciphers. What is it, and what can it do?

Linear Cryptanalysis: A Literature Survey (20K)

Linear Cryptanalysis has been used to attack DES. What is it?

Walsh-Hadamard Transforms: A Literature Survey (26K) (seearticle)

The "poor man's FFT," the WHT gives us a way of analyzing and measuring the correlation in combining functions and random generators. "Butterfly" computations with a similar structure are useful in mixing block ciphers. There seems to be some sort of WHT equivalence to LFSR maximal-length sequences.

Linear Complexity: A Literature Survey (25K)

The linear complexity (LC) of a sequence is the length of the shortest linear feedback shift register (LFSR) which will produce that sequence. Clearly, LC represents a particular form of Kolmogorov-Chaitin algorithmic randomness. Typically, the Berlekamp-Massey algorithm is used to measure the LC, and various RNG construction techniques will guarantee some minimum value.

RANDOMNESS -- PSEUDO (seeglossary, relatedlinks anddiscussions)

RNG Surveys: A Literature Survey (16K)

References to surveys which discuss various software RNG designs.

RNG Implementations: A Literature Survey (26K)

References to design articles which have an obvious software implementation or which give actual computer source code examples.

RANDOMNESS -- REAL (seeglossary, relatedlinks, anddiscussions)

Random Electrical Noise: A Literature Survey (66K)

References to the theory and statistics of random electrical noise. Comments on what may be necessary to correctly generate, condition and sample the noise for randomness.

Random Number Machines: A Literature Survey (62K)

References to designs for "physically-random" or "really random" RNG's.

RANDOMNESS -- TESTS (see relatedlinks, anddiscussions)

Randomness Tests: A Literature Survey (39K)

We have a sequence -- is it random? We cannot know absolutely -- there is no proof of randomness -- but we can develop the probability that a sequence was produced at random, under various assumptions.

LATIN SQUARES (seeglossary)

Latin Squares: A Literature Survey (67K)

References to Latin squares, orthogonal Latin squares, orthogonal arrays, etc.

A Note from the Owner

These pages are published property, just like a book or magazine. Most of this material has been previously published. Many of the articles in this collection were released to Usenet News for general computer distribution.

This work was privately conducted without governmental, educational or commercial support.

Terry Ritter, and hiscurrent address.