Ntt Docomo, Inc.

Rsa Security Inc.

Rsa Data Security, Inc.

Yiqun Lisa Yin

Burton S Kaliski, Jr

Alejandro Hevia

Anand Desai

Ronald L Rivest

Atsushi Takeshita

Jeffrey Hoffstein

Matthew John Robshaw

Satomi Okazaki

Peng Ning

Matthew John Barton Robshaw

Raymond Mark Sidney

Daniel Bennett Lieman

Aki Yokote

Disclosed herein are apparatuses and methods for generating pseudorandom numbers by making the existing ANSI and FIPS PRNGs forward secure and eliminating the need for re-keying them. A forward secure ANSI PRNG is created which includes an enhanced block cipher that is non-invertible even if the key becomes known and a function of the block cipher used in the existing ANSI PRNG. Additionally, the forward secure ANSI PRNG includes an enhanced next state that allows previous states to remain secret even when the key and the current state become known. A forward secure FIPS PRNG is created which includes a computation of an enhanced next state that is noninvertible.

Enhanced ANSI X9.17 and FIPS 186 pseudorandom number generators with forward security

Networks consist of administrative domains each including an administrative server and at least one mobility agent deployed therein. The mobility agents offer connectivity to a mobile node via Advertisement messages in a form verifiable by the mobile node. Each Advertisement message is signed by a private key of the advertising mobility agent and accompanied by a certificate that contains a public key of the advertising mobility agent and is signed by a private key of the administrative server of the advertising mobility agent. Thus, if the mobile node has the public key of the administrative server, it can authenticate the Advertisement message. If the mobile node does not have the public key, it requests the public key when it registers with the mobility agent. The public key of the administrative server is sent in a certificate signed by the private key of the administrative server ultimately responsible for authentication of the mobile node.

Method for securing access to mobile IP network

Enhanced ANSI X9.17 pseudorandom number generators with forward security

The invention provides improved techniques for multiplication of signals represented in a normal basis of a finite field. An illustrative embodiment includes a first rotator which receives a first input signal representative of a first normal basis field element (a a . . . a ), and a second rotator which receives a second input signal representative of a second normal basis field element (b b . . . b ). A word multiplier receives output signals from the first and second rotators, corresponding to rotated representations of the first and second elements, respectively, and processes the rotated representations w bits at a time to generate an output signal representative of a product of the first and second elements, where w is a word length associated with the word multiplier. The rotated representation of the first element may be given by A&lsqb;i&rsqb;&equals;(a a . . . a ), the rotated representation of the second element may be given by B&lsqb;i&rsqb;&equals;(b b . . . b ), and the product may be given by c&equals;(C&lsqb;0&rsqb;, C&lsqb;w&rsqb;, C&lsqb;2w&rsqb;, . . . , C&lsqb;m&minus;w&rsqb;), where C&lsqb;i&rsqb;&equals;(c C . . . c ), m is the degree of the finite field, w is the word length, and i&equals;0, 1, . . . m&minus;1. The invention is particularly well suited for implementation in software, and can provide performance advantages for both general normal basis and optimal normal basis.

Efficient finite field multiplication in normal basis

A plaintext message to be encrypted is segmented into a number of words, e.g., four words stored in registers A, B, C and D, and an integer multiplication function is applied to a subset of the words, e.g., to the two words in registers B and D. The integer multiplication function may be a quadratic function of the form &fnof;(x)&equals;x(ax&plus;b) or other suitable function such as a higher-order polynomial. The results of the integer multiplication function are rotated by lg w bits, where lg denotes log base,and w is the number of bits in a given word, to generate a pair of intermediate results t and u. An exclusive-or of another word, e.g., the word in register A, and one of the intermediate results, e.g., t, is rotated by an amount determined by the other intermediate result u. Similarly, an exclusive-or of the remaining word in register D and the intermediate result u is rotated by an amount determined by the other intermediate result t. An element of a secret key array is applied to each of these rotation results, and the register contents are then transposed. This process is repeated for a designated number of rounds to generate a ciphertext message. Pre-whitening and post-whitening operations may be included to ensure that the input or output does not reveal any internal information about any encryption round. Corresponding decryption operations may be used to decrypt the ciphertext message.

Enhanced block ciphers with data-dependent rotations

Methods and apparatus for providing secure user identification or digital signatures based on evaluation of constrained polynomials. In an exemplary user identification technique, a prover sends a verifier a commitment signal representative of a first polynomial satisfying a first set of constraints. The verifier sends the prover a challenge signal representative of a second polynomial satisfying a second set of constraints. The prover generates a response signal as a function of (i) information used to generate the commitment signal, (ii) a challenge signal, and (iii) a private key polynomial of the prover, such that the response signal is representative of a third polynomial satisfying a third set of constraints. The verifier receives the response signal from the prover, and authenticates the identity of the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover. In a digital signature technique, the challenge signal may be generated by the prover applying a hash function to (i) a message and (ii) information used to generate the commitment signal, and the prover sends the message to the verifier. The verifier uses a result of applying the hash function to the message and the commitment signal to authenticate a digital signature of the prover. The constraints on the polynomials are selected such that an attacker will find it very difficult to recover the private key polynomial from the partial information sent between the prover and verifier.

Secure user identification based on constrained polynomials

Methods and apparatus for converting a value A representing in a first basis an element of a finite field GF(q.sup.m) to a value B representing the element in a second basis, where q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and where the value B includes a vector of m coefficients from a finite field GF(q). An exemplary apparatus, particularly well-suited for exporting the value A in an internal basis representation to the value B in an external basis representation, includes an externally shifted sequence generator for generating from the value A a sequence of intermediate values representing in the first basis elements of the finite field GF(q.sup.m) whose representations in the second basis are related to the value B by a predetermined external shift operation. An extractor coupled to the externally shifted sequence generator receives and processes the sequence of intermediate values to generate each coefficient of the value B.

Methods and apparatus for efficient finite field basis conversion

Growing community of inventors

San Mateo, CA, United States of America

Yiqun Lisa Yin