RSA Laboratories

Appendix B Glossary

In this glossary brief descriptions of the most important concepts are given. Mathematical concepts are treated in more detail in Appendix A. For more information, we refer to earlier chapters in this document.

abelian group
An abstract group with a commutative binary operation; see Section A.3.
A version of the chosen-ciphertext attack where the cryptanalyst can choose ciphertexts dynamically. A cryptanalyst can mount an attack of this type in a scenario in which he or she has free use of a piece of decryption hardware, but is unable to extract the decryption key from it.
A special case of the chosen-plaintext attack in which the cryptanalyst is able to choose plaintexts dynamically, and alter his or her choices based on the results of previous encryptions.
Commonly used to refer to the opponent, the enemy, or any other mischievous person that desires to compromise one's security.
The Advanced Encryption Standard that will replace DES (The Data Encryption Standard) around the turn of the century.
algebraic attack
A method of cryptanalytic attack used against block ciphers that exhibit a significant amount of mathematical structure.
A series of steps used to complete a task.
The name traditionally used for the first user of cryptography in a system; Bob's friend.
American National Standards Institute.
Application Programming Interface.
Either a successful or unsuccessful attempt at breaking part or all of a cryptosystem. See algebraic attack, birthday attack, brute force attack, chosen ciphertext attack, chosen plaintext attack, differential cryptanalysis, known plaintext attack, linear cryptanalysis, middleperson attack.
The action of verifying information such as identity, ownership or authorization.
big-O notation
Used in complexity theory to quantify the long-term time dependence of an algorithm with respect to the size of the input. See Section A.7.
The science of using biological properties to identify individuals; for example, finger prints, a retina scan, and voice recognition.
birthday attack
A brute-force attack used to find collisions. It gets its name from the surprising result that the probability of two or more people in a group of 23 sharing the same birthday is greater than 1/2.
A binary digit, either 1 or 0.
blind signature scheme
Allows one party to have a second party sign a message without revealing any (or very little) information about the message to the second party.
A sequence of bits of fixed length; longer sequences of bits can be broken down into blocks.
block cipher
A symmetric cipher which encrypts a message by breaking it down into blocks and encrypting each block.
block cipher based MAC
MAC that is performed by using a block cipher as a keyed compression function.
The name traditionally used for the second user of cryptography in a system; Alice's friend.
boolean expression
A mathematical expression in which all variables involved are either 0 or 1; it evaluates to either 0 or 1. See Section A.6.
brute force attack
This attack requires trying all (or a large fraction of all) possible values till the right value is found; also called an exhaustive search.
See certifying authority
Cryptographic Application Programming Interface.
The U.S. government's project to develop a set of standards for publicly available cryptography, as authorized by the Computer Security Act of 1987. See Clipper, DSA, DSS, and Skipjack.
In cryptography, an electronic document binding some pieces of information together, such as a user's identity and public-key. Certifying Authorities (CA's) provide certificates.
certificate revocation list
A list of certificates that have been revoked before their expiration date.
Certifying Authority (CA)
A person or organization that creates certificates.
Used in error detection, a checksum is a computation done on the message and transmitted with the message; similar to using parity bits.
chosen ciphertext attack
An attack where the cryptanalyst may choose the ciphertext to be decrypted.
chosen plaintext attack
A form of cryptanalysis where the cryptanalyst may choose the plaintext to be encrypted.
An encryption-decryption algorithm.
Encrypted data.
ciphertext-only attack
A form of cryptanalysis where the cryptanalyst has some ciphertext but nothing else.
Clipper is an encryption chip developed and sponsored by the U.S. government as part of the Capstone project.
Two values x and y form a collision of a (supposedly) one-way function F if x ¹ y but F(x) = F(y).
A hash function is collision-free if collisions are hard to find. The function is weakly collision-free if it is computationally hard to find a collision for a given message x. That is, it is computationally infeasible to find a message y ¹ x such that H(x) = H(y). A hash function is strongly collision-free if it is computationally infeasible to find any messages x, y such that x ¹ y and H(x) = H(y).
collision search
The search for a collision of a one-way function.
When a mathematical operation yields the same result regardless of the order the objects are operated on. For example, if a, b are integers, then a+b = b+a, that is, addition of integers is commutative.
computational complexity
Refers to the amount of space (memory) and time required to solve a problem. Space refers to spatial (memory) constraints involved in a certain computation, while time refers to the temporal constraints involved in the computation.
compression function
A function that takes a fixed length input and returns a shorter, fixed length output. See also hash functions.
The unintended disclosure or discovery of a cryptographic key or secret.
To place two (or more) things together one directly after the other. For example, treehouse is the concatenation of the words tree and house.
covert channel
A hidden communication medium.
Certificate Revocation List.
The art and science of breaking encryption or any form of cryptography. See attack.
The art and science of using mathematics to secure information and create a high degree of trust in the electronic realm. See also public key, secret key, symmetric-key, and threshold cryptography.
The branch of mathematics concerned with cryptography and cryptanalysis.
An encryption-decryption algorithm (cipher), together with all possible plaintexts, ciphertexts and keys.
Data Encryption Standard
See DES.
The inverse (reverse) of encryption.
Data Encryption Standard, a block cipher developed by IBM and the U.S. government in the 1970's as an official standard. See also block cipher.
dictionary attack
A brute force attack that tries passwords and or keys from a precompiled list of values. This is often done as a precomputation attack.
Diffie-Hellman key exchange
A key exchange protocol allowing the participants to agree on a key over an insecure channel.
differential cryptanalysis
A chosen plaintext attack relying on the analysis of the evolution of the differences between two plaintexts.
Commonly used to refer to the output of a hash function, e.g. message digest refers to the hash of a message.
digital cash
See electronic money
digital envelope
A key exchange protocol that uses a public-key cryptosystem to encrypt a secret key for a secret-key cryptosystem.
digital fingerprint
See digital signature.
digital signature
The encryption of a message digest with a private key.
digital timestamp
A record mathematically linking a document to a time and date.
discrete logarithm
Given two elements d, g in a group such that there is an integer r satisfying gr = d, r is called the discrete logarithm of d in the ``base'' g.
discrete logarithm problem
The problem of finding r such that gr = d, where d and g are elements in a given group. For some groups, the discrete logarithm problem is a hard problem used in public-key cryptography.
distributed key
A key that is split up into many parts and shared (distributed) among different participants. See also secret sharing.
Defense Messaging Service.
Department of Defense.
Digital Signature Algorithm. DSA is a public-key method based on the discrete logarithm problem.
Digital Signature Standard. DSA is the Digital Signature Standard.
Export Administration Regulations.
Elliptic Curve Cryptosystem; A public-key cryptosystem based on the properties of elliptic curves.
See elliptic curve discrete logarithm.
Electronic (business) Data Interchange.
electronic commerce (e-commerce)
Business transactions conducted over the Internet.
electronic mail (e-mail)
Messages sent electronically from one person to another via the Internet.
electronic money
Electronic mathematical representation of money.
elliptic curve
The set of points (x, y) satisfying an equation of the form

y2 = x3 + ax + b

for variables x, y and constants a, b Î F, where F is a field.
elliptic curve cryptosystem
See ECC.
elliptic curve discrete logarithm (ECDL) problem
The problem of finding m such that m ·P = Q, where P and Q are two points on an elliptic curve.
elliptic curve (factoring) method
A special-purpose factoring algorithm that attempts to find a prime factor p of an integer n by finding an elliptic curve whose number of points modulo p is divisible by only small primes.
The transformation of plaintext into an apparently less readable form (called ciphertext) through a mathematical process. The ciphertext may be read by anyone who has the key that decrypts (undoes the encryption) the ciphertext.
See XOR.
exhaustive search
Checking every possibility individually till the right value is found. See also attack.
expiration date
Certificates and keys may have a limited lifetime; expiration dates are used to monitor this.
exponential function
A function where the variable is in the exponent of some base, for example, bx where x is the variable, and b > 0 is some constant.
exponential running time
A running time of an algorithm that is approximately exponential as a function of the length of the input.
export encryption
Encryption, in any form, which leaves its country of origin. For example, encrypted information or a computer disk holding encryption algorithms that is sent out of the country.
Given an integer n, any number that divides it is called a factor of n. For example, 7 is a factor of 91, because 91/7 is an integer.
The breaking down of an integer into its prime factors. This is a hard problem.
factoring methods
See elliptic curve method, multiple polynomial quadratic sieve, number field sieve, Pollard p-1 and Pollard p+1 method, Pollard rho method, quadratic sieve.
Federal Bureau of Investigation, a U.S. government law enforcement agency.
Feistel cipher
A special class of iterated block ciphers where the ciphertext is calculated from the plaintext by repeated application of the same transformation called a round function.
A mathematical structure consisting of a finite or infinite set F together with two binary operations called addition and multiplication. Typical examples include the set of real numbers, the set of rational numbers, and the set of integers modulo p. See Section A.4 for more detailed information.
Federal Information Processing Standards. See NIST.
flat key space
See linear key space.
A mathematical relationship between two values called the input and the output, such that for each input there is precisely one output. For example, f defined on the set of real numbers as f(x) = x2 is a function with input any real number x and with output the square of x.
Galois field
A field with a finite number of elements. The size of a finite field must be a power of prime number.
generalpurpose factoring algorithm
An algorithm whose running time depends only on the size of the number being factored. See special purpose factoring algorithm.
Goppa code
A class of error correcting codes, used in the McEliece public-key cryptosystem.
In mathematics, a set of elements called vertices or nodes together with a set of unordered pairs of vertices called edges. Intuitively speaking, an edge is a line joining two vertices.
graph coloring problem
The problem of determining whether a graph can be colored with a fixed set of colors such that no two adjacent vertices have the same color and producing such a coloring. Two vertices are adjacent if they are joined by an edge.
A mathematical structure consisting of a finite or infinite set together with a binary operation called group multiplication satisfying certain axioms; see Section A.3 for more information.
generic security service application program interface.
A person who tries and/or succeeds at defeating computer security measures.
Hamiltonian path problem
Determine whether a given graph contains a Hamiltonian graph. A Hamiltonian path is a path in a graph that passes through each vertex exactly once. This is a hard problem.
A protocol two computers use to initiate a communication session.
hard problem
A computationally-intensive problem; a problem that is computationally difficult to solve.
hash-based MAC
MAC that uses a hash function to reduce the size of the data it processes.
hash function
A function that takes a variable sized input and has a fixed size output.
see MAC.
A mathematical object which may be thought of as an extension (into higher dimensions) of a 2-dimensional plane passing through the point (0,0,0) in a 3-dimensional vector space. See Appendix A.
Institute of Electrical and Electronics Engineers, a body that creates some cryptography standards.
Internet Engineering Task Force.
A process through which one ascertains the identity of another person or entity.
Internet Keyed Payments Protocol.
Occurs when an entity pretends to be someone or something it is not.
import encryption
Encryption, in any form, coming into a country.
index calculus
A method used to solve the discrete logarithm problem.
integer programming problem
The problem is to solve a linear programming problem where the variables are restricted to integers.
interactive proof
A protocol between two parties in which one party, called the prover, tries to prove a certain fact to the other party, called the verifier. This is usually done in a question response format, where the verifier asks the prover questions that only the prover can answer with a certain success rate.
The connection of computer networks from all over the world forming a worldwide network.
In complexity theory, referring to a problem with no efficient means of deriving a solution.
International Standards Organization, creates international standards, including cryptography standards.
International Telecommunications Union - Telecommunications standardization sector.
An authentication service developed by the Project Athena team at MIT.
A string of bits used widely in cryptography, allowing people to encrypt and decrypt data; a key can be used to perform other mathematical operations as well. Given a cipher, a key determines the mapping of the plaintext to the ciphertext. See also distributed key, private key, public key, secret key, session key, shared key, sub key, symmetric key, weak key.
key agreement
A process used by two or more parties to agree upon a secret symmetric key.
key escrow
The process of having a third party hold onto encryption keys.
key exchange
A process used by two more parties to exchange keys in cryptosystems.
key expansion
A process that creates a larger key from the original key.
key generation
The act of creating a key.
key management
The various processes that deal with the creation, distribution, authentication, and storage of keys.
key pair
The full key information in a public-key cryptosystem, consisting of the public key and private key.
key recovery
A special feature of a key management scheme that allows messages to be decrypted even if the original key is lost.
key schedule
An algorithm that generates the subkeys in a block cipher.
key space
The collection of all possible keys for a given cryptosystem. See also flat key space, linear key space, nonlinear key space, and reduced key space.
knapsack problem
A problem that involves selecting a number of objects with given weights from a set, such that the sum of the weights is maximal but less than a pre-specified weight.
known plaintext attack
A form of cryptanalysis where the cryptanalyst knows both the plaintext and the associated ciphertext.
A lattice can be viewed as a grid in an n-dimensional vector space. See Section A.5.
Law Enforcement Agency Field a component in the Clipper Chip.
life cycle
The length of time a key can be kept in use and still provide an appropriate level of security.
linear complexity
Referring to a sequence of 0's and 1's, the size of the smallest linear feedback shift register (LFSR) that would replicate the sequence. See also linear feedback shift register.
linear cryptanalysis
A known plaintext attack that uses linear approximations to describe the behavior of the block cipher. See known plaintext attack.
linear key space
A key space where each key is equally strong.
linear feedback shift register. Used in many keystream generators because of its ability to produce sequences with certain desirable properties.
See message authentication code.
meet-in-the-middle attack
A known plaintext attack against double encryption with two separate keys where the attacker encrypts a plaintext with a key and ``decrypts'' the original ciphertext with another key and hopes to get the same value.
Message Authentication Code(MAC)
A MAC is a function that takes a variable length input and a key to produce a fixed-length output. See also hash-based MAC, stream-cipher based MAC, and block-cipher based MAC.
message digest
The result of applying a hash function to a message.
Message Handling System.
middleperson attack
A person who intercepts keys and impersonates the intended recipients.
Multipurpose Internet Mail Extensions.
Millions of Instructions Per Second, a measurement of computing speed.
One year's worth of time on a MIPS machine.
mixed integer programming
The problem is to solve a linear programming problem where some of the variables are restricted to being integers.
modular arithmetic
A form of arithmetic where integers are considered equal if they leave the same remainder when divided by the modulus. See Section A.2.
The integer used to divide out by in modular arithmetic.
multiple polynomial quadratic sieve(MPQS)
A variation of the quadratic sieve that sieves on multiple polynomials to find the desired relations. MPQS was used to factor RSA-129.
National Institute of Standards and Technology, a United States agency that produces security and cryptography related standards (as well as others); these standards are published as FIPS documents.
A property of a cryptosystem. Non-repudiation cryptosystems are those in which the users cannot deny actions they performed.
Not determined or decided by previous information.
nondeterministic computer
Currently only a theoretical computer capable of performing many computations simultaneously.
nonlinear key space
A key space comprised of strong and weak keys.
Nondeterministic polynomial running time. If the running time, given as a function of the length of the input, is a polynomial function when running on a theoretical, nondeterministic computer, then the algorithm is said to be NP.
An NP problem is NP-complete if any other NP problem can be reduced to it in polynomial time.
National Security Agency. A security-conscious U. S. government agency whose mission is to decipher and monitor foreign communications.
number field sieve
A method of factoring, currently the fastest general purpose factoring algorithm published. It was used to factor RSA-130.
number theory
A branch of mathematics that investigates the relationships and properties of numbers.
Optimal Asymmetric Encryption Padding; a provably secure way of encrypting a message.
one-time pad
A secret-key cipher in which the key is a truly random sequence of bits that is as long as the message itself, and encryption is performed by XORing the message with the key. This is theoretically unbreakable.
one-way function
A function that is easy to compute in one direction but quite difficult to reverse compute (compute in the opposite direction.)
one-way hash function
A one-way function that takes a variable sized input and creates a fixed size output.
Polynomial running time. If the running time, given as a function of the length of the input is bounded by a polynomial, the algorithm is said to have polynomial running time. Polynomial running time algorithms are sub-exponential, but not all sub-exponential algorithms are polynomial running time; one example is eÖx.
The sole right, granted by the government, to sell, use, and manufacture an invention or creation.
Public-key Infrastructure. PKIs are designed to solve the key management problem. See also key management.
Extra bits concatenated with a key, password, or plaintext.
A character string used as a key to control access to files or encrypt them.
Public-key cryptography Standards. A series of cryptographic standards dealing with public-key issues, published by RSA Laboratories.
The data to be encrypted.
A geometric object in 3-dimensional space defined by an equation of the form Ax + By + Cz = D (A, B, C not all 0), that is, the plane contains every point (x,y,z) satisfying this equation. For example, z = 0 gives the (x,y) plane.
Pollard p-1 and Pollard p+1 methods
Algorithms that attempt to find a prime factor p of a number n by exploiting properties of p-1 and p+1, respectively. See also factoring, prime factor, prime number.
Pollard Rho method
A method for solving the discrete logarithm and elliptic curve discrete logarithm.
An algebraic expression written as a sum of constants multiplied by different powers of a variable, that is, an expression of the form

an xn + an-1 xn-1 + ¼+ a1 x + a0,

where the aj are the constants and x is the variable. A polynomial can be interpreted as a function with input value x.
precomputation attack
An attack where the adversary precomputes a look-up table of values used to crack encryption or passwords. See also dictionary attack.
primality testing
A test that determines, with varying degree of probability, whether or not a particular number is prime.
prime factor
A prime number that is a factor of another number is called a prime factor of that number.
prime number
Any integer greater than 1 that is divisible only by 1 and itself. The first twelve primes are 2,3,5,7,11,13,17,19,23,29,31, and 37.
The state or quality of being secluded from the view and or presence of others.
private exponent
The private key in the RSA public-key cryptosystem.
private key
In public-key cryptography, this key is the secret key. It is primarily used for decryption but is also used for encryption with digital signatures.
proactive security
A property of a cryptographic protocol or structure which minimizes potential security compromises by refreshing a shared key or secret.
probabilistic signature scheme (PSS)
A provably secure way of creating signatures using the RSA algorithm.
A series of steps that two or more parties agree upon to complete a task.
provably secure
A property of a digital signature scheme stating that it is provably secure if its security can be tied closely to that of the cryptosystem involved. See also digital signature scheme.
pseudo-random number
A number extracted from a pseudo-random sequence.
pseudo-random sequence
A deterministic function which produces a sequence of bits with qualities similar to that of a truly random sequence.
See probabilistic signature scheme.
public exponent
The public key in the RSA public-key cryptosystem.
public key
In public-key cryptography this key is made public to all, it is primarily used for encryption but can be used for verifying signatures.
public-key cryptography
Cryptography based on methods involving a public key and a private key.
quadratic sieve
A method of factoring an integer, developed by Carl Pomerance.
quantum computer
A theoretical computer based on ideas from quantum theory; theoretically it is capable of operating nondeterministically.
RSA algorithm
A public-key cryptosystem based on the factoring problem. RSA stands for Rivest, Shamir and Adleman, the developers of the RSA public-key cryptosystem and the founders of RSA Data Security (now RSA Security).
random number
As opposed to a pseudo-random number, a truly random number is a number produced independently of its generating criteria. For cryptographic purposes, numbers based on physical measurements, such as a Geiger counter, are considered random.
reduced key space
When using an n bit key, some implementations may only use r < n bits of the key; the result is a smaller (reduced) key space.
relatively prime
Two integers are relatively prime if they have no common factors. For example, 14 and 25 are relatively prime, while 14 and 91 are not; 7 is a common factor.
reverse engineer
To ascertain the functional basis of something by taking it apart and studying how it works.
The number of times a function, called a round function, is applied to a block in a Feistel cipher.
running time
A measurement of the time required for a particular algorithm to run as a function of the input size. See also exponential running time, nondeterministic polynomial running time, polynomial running time, sub-exponential running time, and Section A.7.
Secure HyperText Transfer Protocol, a secure way of transferring information over the World Wide Web.
Secure Multipurpose Internet Mail Extensions.
Secure Socket Layer. A protocol used for secure Internet communications.
Society for Worldwide Interbank Financial Telecommunications.
A string of random (or pseudo-random) bits concatenated with a key or password to foil precomputation attacks.
satisfiability problem
Given a Boolean expression determine if there is an assignment of 1's and 0's such that the expression evaluates to 1. This is hard problem.
secret key
In secret-key cryptography, this is the key used both for encryption and decryption.
secret sharing
Splitting a secret (e.g. a private key) into many pieces such that any specified subset of k pieces may be combined to form the secret, but k-1 pieces are not enough.
secure channel
A communication medium safe from the threat of eavesdroppers.
A typically random bit sequence used to generate another, usually longer pseudo-random bit sequence.
self-shrinking generator
A stream cipher where the output of an LFSR is allowed to feed back into itself.
Referring to a stream cipher, when the keystream is dependent on the data and its encryption.
session key
A key for symmetric-key cryptosystems which is used for the duration of one message or communication session
Secure Electronic Transaction. MasterCard and Visa developed (with some help from industry) this standard jointly to insure secure electronic transactions.
shared key
The secret key two (or more) users share in a symmetric-key cryptosystem.
shrinking generator
A stream cipher built around the interaction of the outputs of two LFSRs. See also stream cipher and linear feedback shift register.
The block cipher contained in the Clipper chip designed by the NSA.
Simple Mail Transfer Protocol.
smart card
A card, not much bigger than a credit card, that contains a computer chip and is used to store or process information.
special-purpose factoring algorithm
A factoring algorithm which is efficient or effective only for some numbers. See also factoring and prime factors.
Conditions and protocols set forth to allow uniformity within communications and virtually all computer activity.
stream cipher
A secret-key encryption algorithm that operates on a bit at a time.
stream cipher based MAC
MAC that uses linear feedback shift registers (LFSRs) to reduce the size of the data it processes.
strong prime
A prime number with certain properties chosen to defend against specific factoring techniques.
sub-exponential running time
The running time is less than exponential. Polynomial running time algorithms are sub-exponential, but not all sub-exponential algorithms are polynomial running time.
A value generated during the key scheduling of the key used during a round in a block cipher.
subset sum problem
A problem where one is given a set of numbers and needs to find a subset that sums to a particular value.
Secure Wide Area Network.
symmetric cipher
An encryption algorithm that uses the same key is used for encryption as decryption.
symmetric key
See secret key.
A property of a stream cipher, stating that the keystream is generated independently of the plaintext and ciphertext.
tamper resistant
In cryptographic terms, this usually refers to a hardware device that is either impossible or extremely difficult to reverse engineer or extract information from.
Trusted Computer System Evaluation Criteria.
threshold cryptography
Splitting a secret (for example a private key) into many pieces such that only certain subsets of the n pieces may be combined to form the secret.
See digital timestamp
A property of a problem, stating that it can be solved in a reasonable amount of time using a reasonable amount of space.
trapdoor one-way function
A one-way function that has an easy-to-compute inverse if you know certain secret information. This secret information is called the trapdoor.
traveling salesman problem
A hard problem. The problem is: given a set of cities, how does one tour all the cities in the minimal amount of distance traveled.
A common term for escrow agents.
Turing machine
A theoretical model of a computing device, devised by Alan Turing.
The act of recognizing that a person or entity is who or what it claims to be.
Vernam cipher
See one-time pad.
weak key
A key giving a poor level in security, or causing regularities in encryption which can be used by cryptanalysts to break codes.
World Wide Web.
A binary bitwise operator yielding the result one if the two values are different and zero otherwise. XOR is an abbreviation for exclusive-OR.
zero knowledge proofs
An interactive proof where the prover proves to the verifier that he or she knows certain information without revealing the information.