Cryptographical pseudo-random number generation apparatus and program

A cryptographical pseudo-random number generation apparatus functioning as a calculation device for word length of w bits, comprising:

• an input unit inputting natural numbers c, o, and a (c+o≦p where p indicates a prime number, and 2p−1 also indicates a prime number) and three bit strings (on condition that each character string includes a bit of 0 and a bit of 1) of a bit length p;
• an internal status storage unit storing a first bit string of the bit length p input by said input unit;
• a generator storage unit storing a second bit string of the bit length p input by said input unit;
• an irreducible polynomial storage unit storing an irreducible polynomial f (t) (=tp+bp-1tp-1+bp-2tp-2+ . . . +b1t+b0) of a p-th {0, 1} coefficient depending on a p-bit bit string of {0, 1} coefficient bp-1bp-2 . . . b1b0;
• and
• a base point storage unit storing a third bit string of a bit length p input by said input unit;
• and
• an arithmetic unit, wherein
• said arithmetic unit computes gs (modf(t)) using a value g of p bits stored in said generator storage unit, a value x of the p bits stored in said base point storage unit, and a value s of low order c bits of the p bits stored in said internal status storage unit, an arithmetic result of the p bits is stored in said internal status storage unit, low order o bits of the p bits are output, and a series of which processes are repeated a times, thereby generating a pseudo-random number.

A cryptographical pseudo-random number generation apparatus functioning as a calculation device for word length of w bits, comprising:

• an input unit inputting natural numbers c, o, and a (c+o≦p where p indicates a prime number, and 2p−1 also indicates a prime number) and three bit strings (on condition that each character string includes a bit of 0 and a bit of 1) of a bit length p;
• an internal status storage unit storing a first bit string of the bit length p input by said input unit;
• a generator storage unit storing a second bit string of the bit length p input by said input unit;
• an irreducible polynomial storage unit storing an irreducible polynomial f (t) (=tp+bp-1tp-1+bp-2tp-2+ . . . +b1t+b0) of a p-th {0, 1} coefficient depending on a p-bit bit string of {0, 1} coefficient bp-1bp-2 . . . b1b0;
• a base point storage unit storing a third bit string of a bit length p input by said input unit;
• a multiple length adder unit;
• and
• an arithmetic unit, wherein
• said arithmetic unit computes gs (modf(t)) using a value g of p bits stored in said generator storage unit, a value x of the p bits stored in said base point storage unit, and a value s of low order c bits of the p bits stored in said internal status storage unit, an arithmetic result of the p bits is stored in said internal status storage unit, low order o bits of an calculation result of the p bits are output, said multiple length adder unit assumes the value x of the p bits stored in said base point storage unit as a multiple length, adds d to the value x, and stores the addition result in said base point storage unit, and a series of which processes are repeated a times, thereby generating a pseudo-random number.

A cryptographical pseudo-random number generation apparatus functioning as a calculation device for word length of w bits, comprising:

• an input unit inputting natural numbers c1,c2, . . . ,cu,o1,o2, . . . ,ov, a (u+v≦p (p indicates a prime number, and 2p−1 also indicates a prime number) and ci≦p, oi≦p, and ci≠oj for all i's) and a bit string of a bit length p (on condition that each bit string includes a bit of 0 and a bit of 1);
• an internal status storage unit storing the bit string of the bit length p input by said input unit;
• and
• an arithmetic unit performing arithmetic f including a logical operation and a shifting operation on the bit string of the bit length p stored in said internal status storage unit, wherein
• said arithmetic unit calculates fs (x) by performing the operation f on the value x of the bit string of the bit length p stored in the internal status storage unit for the number of times of the value s of the bit string prescribed by c1,c2 . . . ,cu bits of the bit string of the bit length p stored in the internal status storage unit, stores the calculation result represented by p bits in the internal status storage unit, and outputs o1,o2 . . . ,ov bits of the calculation result of the bit string of the p bits, and a series of which processes are repeated a times, thereby generating a pseudo-random number.

A cryptographical pseudo-random number generation apparatus functioning as a calculation device for word length of w bits, comprising:

• an input unit inputting natural numbers c1,c2, . . . ,cu,o1,o2, . . . ,ov, a, d (u+v≦p (p indicates a prime number, and 2p−1 also indicates a prime number) and ci≦p, oi≦p, and ci≠oj for all i's) and a bit string of a bit length p (on condition that each bit string includes a bit of 0 and a bit of 1);
• an internal status storage unit storing the bit string of the bit length p input by said input unit;
• an arithmetic unit performing arithmetic f including a logical operation and a shifting operation on the bit string of the bit length p stored in said internal status storage unit;
• and
• a multiple length adder unit, wherein
• said arithmetic unit calculates fs (x) by performing the operation f on the value x of the bit string of the bit length p stored in the internal status storage unit for the number of times of value s of the bit string prescribed by c1,c2 . . . ,cu bits of the bit string of the bit length p stored in the internal status storage unit, stores the calculation result represented by p bits in the internal status storage unit, and outputs o1,o2 . . . ,ov bits of the calculation result of the bit string of the p bits, said multiple length adder unit adds the value x of the bit string of the p bits stored in said internal status storage unit to d(mod 2p−1), and stores the addition result in said internal status storage unit, and a series of which processes are repeated a times, thereby generating a pseudo-random number.

A cryptographical pseudo-random number generation apparatus functioning as a calculation device for word length of w bits, comprising:

• an input unit inputting natural numbers c1,c2, . . . ,cu,o1,o2, . . . ,ov, a (u+v≦p (p indicates a prime number, and 2p−1 also indicates a prime number) and ci≦p, oi≦p, and ci≠oj for all i's) and a bit string of a bit length p (on condition that each bit string includes a bit of 0 and a bit of 1);
• an internal status storage unit storing the bit string of the bit length p input by said input unit;
• a first arithmetic unit performing an operation f1 including a logical operation and a shifting operation;
• and
• a second arithmetic unit performing an operation f2 including a logical operation and a shifting operation, wherein
• said first arithmetic unit calculates f1s (x) by performing the operation f1 on the value x of the bit string of the bit length p stored in the internal status storage unit for the number of times of the value s of the bit string prescribed by c1,c2 . . . ,cu bits of the bit string of the bit length p stored in the internal status storage unit, stores the calculation result represented by p bits in the internal status storage unit, and outputs o1,o2 . . . ,ov bits of the calculation result of the bit string of the p bits, said second arithmetic unit calculates f2s (x′) by performing the operation f2 on the value x′ of the bit string of the p bits stored in the internal status storage unit, and stores the calculation result of the p bits in said internal status storage unit, and a series of which processes are repeated a times, thereby generating a pseudo-random number.

A program executed by a computer for processing a word length of w bits, comprising the functions of:

• inputting natural numbers c, o, and a (c+o≦p where p indicates a prime number, and 2p−1 also indicates a prime number) and two bit strings (on condition that each bit string includes a bit of 0 and a bit of 1) of a bit length p;
• storing a first bit string of the input bit length p in an internal status storage unit;
• storing a second bit string of the input bit length p in a generator storage unit;
• storing an irreducible polynomial f (t) (=tp+bp-1tp-1+bp-2tp-2+ . . . +b1t+b0) of a p-th {0, 1} coefficient depending on a p-bit bit string of {0, 1} coefficient bp-1bp-2 . . . b1b0 in an irreducible polynomial storage unit;
• and computing gs (modf(t)) using a value g of p bits stored in said generator storage unit, a value s of low order c bits of the p bits stored in said internal status storage unit, and a bit string of the p bits stored in said irreducible polynomial storage unit, storing an arithmetic result of the p bits of the arithmetic unit in said internal status storage unit, outputting low order o bits of the arithmetic result of the p bits, and repeating a series of which processes a times, thereby generating a pseudo-random number.

A program executed by a computer for processing a word length of w bits, comprising the functions of:

• inputting natural numbers c, o, and a (c+o≦p where p indicates a prime number, and 2p−1 also indicates a prime number) and three bit strings (on condition that each character string includes a bit of 0 and a bit of 1) of a bit length p;
• storing a first bit string of the input bit length p in an internal status storage unit;
• storing a second bit string of the input bit length p in a generator storage unit;
• storing an irreducible polynomial f (t) (=tp+bp-1tp-1+bp-2tp-2+ . . . +b1t+b0) of a p-th {0, 1} coefficient depending on a p-bit bit string of {0, 1} coefficient bp-1bp-2 . . . b1b0 in an irreducible polynomial storage unit;
• storing a third bit string of the input bit length p in a base point storage unit;
• and
• computing gs (modf(t)) using a value g of p bits stored in said generator storage unit, a value x of the p bits stored in said base point storage unit, and a value s of low order c bits of the p bits stored in said internal status storage unit, storing an arithmetic result of the p bits in said internal status storage unit, outputting low order o bits of the p bits, and repeating a series of which processes a times, thereby generating a pseudo-random number.

A program executed by a computer for processing a word length of w bits, comprising the functions of:

• inputting natural numbers c, o, and a (c+o≦p where p indicates a prime number, and 2p−1 also indicates a prime number) and three bit strings (on condition that each character string includes a bit of 0 and a bit of 1) of a bit length p;
• storing a first bit string of the input bit length pin an internal status storage unit;
• storing a second bit string of the input bit length p in a generator storage unit;
• storing an irreducible polynomial f (t) (=tp+bp-1tp-1+bp-2tp-2+ . . . +b1t+b0) of a p-th {0, 1} coefficient depending on a p-bit bit string of {0, 1} coefficient bp-1bp-2 . . . b1b0 in an irreducible polynomial storage unit;
• storing a third bit string of the input bit length p in a base point storage unit;
• and
• computing gs (modf(t)) using a value g of p bits stored in said generator storage unit, a value x of the p bits stored in said base point storage unit, and a value s of low order c bits of the p bits stored in said internal status storage unit, storing an arithmetic result of the p bits in said internal status storage unit, outputting low order o bits of an calculation result of the p bits, assuming the value x of the p bits stored in said base point storage unit as a multiple length by a multiple length adder unit, adding d to the value x, storing the addition result in said base point storage unit, and repeating a series of which processes a times, thereby generating a pseudo-random number.

A program executed by a computer for processing a word length of w bits, comprising the functions of:

• inputting natural numbers c1,c2, . . . cu,o1,o2, . . . ov, a (u+v≦p (p indicates a prime number, and 2p−1 also indicates a prime number) and ci≦p, oi≦p, and ci≠oj for all i's) and a bit string of a bit length p (on condition that each bit string includes a bit of 0 and a bit of 1);
• storing the input bit string of the bit length p in an internal status storage unit;
• and
• calculating fs (x) by performing the operation f including a logical operation and a shifting operation on the value x of the bit string of the bit length p stored in the internal status storage unit for the number of times of the value s of the bit string prescribed by c1,c2, . . . ,cu bits of the bit string of the bit length p stored in the internal status storage unit, storing the calculation result represented by p bits in the internal status storage unit, outputting o1,o2, . . . ,ov bits of the calculation result of the bit string of the p bits, and repeating a series of which processes a times, thereby generating a pseudo-random number.

A program executed by a computer for processing a word length of w bits, comprising the functions of:

• inputting natural numbers c1,c2, . . . ,cu,o1,o2, . . . ,ov, a, d (u+v≦p (p indicates a prime number, and 2p−1 also indicates a prime number) and ci≦p, oi≦p, and ci≠oj for all i's) and a bit string of a bit length p (on condition that each bit string includes a bit of 0 and a bit of 1);
• storing the bit string of the bit length p input by said input unit in an internal status storage unit;
• performing arithmetic f including a logical operation and a shifting operation on the bit string of the bit length p stored in said internal status storage unit;
• and
• performing a multiple length add, wherein
• fs (x) is calculated by performing the operation f including a logical
• operation and a shifting operation on the value x of the bit string of the bit length p stored in the internal status storage unit for the number of times of the value s of the bit string prescribed by c1,c2, . . . ,cu bits of the bit string of the bit length p stored in the internal status storage unit, the calculation result represented by p bits is stored in the internal status storage unit, o1,o2, . . . ,ov bits of the calculation result of the bit string of the p bits are output, said multiple length add adds the value x of the bit string of the p bits stored in said internal status storage unit to d(mod 2p−1), and stores the addition result in said internal status storage unit, and a series of which processes are repeated a times, thereby generating a pseudo-random number.

A program executed by a computer for processing a word length of w bits, comprising the functions of:

• inputting natural numbers c1,c2, . . . ,cu,o1,o2, . . . ,ov, a (u+v≦p (p indicates a prime number, and 2p−1 also indicates a prime number) and ci≦p, oi≦p, and ci≠oj for all i's) and a bit string of a bit length p (on condition that each bit string includes a bit of 0 and a bit of 1);
• storing the input bit string of the bit length p in an internal status storage unit;
• performing a first operation f1 including a logical operation and a shifting operation;
• performing a second operation f2 including a logical operation and a shifting operation;
• calculating f1s (x) by performing the first operation f1 including a logical operation and a shifting operation on the value x of the bit string of the bit length p stored in the internal status storage unit for the number of times of the value s of the bit string prescribed by c1,c2, . . . ,cu bits of the bit string of the bit length p stored in the internal status storage unit, storing the calculation result represented by p bits in the internal status storage unit, outputting o1,o2, . . . ,ov bits of the calculation result of the bit string of the p bits, calculating f2s (x′) by performing the second operation f2 including a logical operation and a shifting operation on the value x′ of the bit string of the p bits stored in the internal status storage unit, storing the calculation result of the p bits in said internal status storage unit, and repeating a series of which processes a times, thereby generating a pseudo-random number.

A cryptographical pseudo-random number generation apparatus which functions as a calculation device for processing a word length of w, comprising:

• a unit inputting natural numbers c, o, and a (where c+o≦p);
• an input unit inputting a plurality of p-bit character strings (on condition that each bit string includes a bit of 0 and a bit of 1) in n and r defined as p=nw−r (where r<w) for a Mersenne prime number (2p−1);
• an internal status storage unit storing one of a plurality of p-bit input character strings;
• a generator storage unit storing another p-bit input character string;
• an irreducible polynomial storage unit storing an irreducible polynomial f(t) of a p-th {0, 1} coefficient;
• an arithmetic unit comprising a polynomial multiplier and a remainder arithmetic unit calculating a remainder of a division using the irreducible polynomial f(t) stored in said irreducible polynomial storage unit when consecutive p bits bp-1bp-2 . . . b1b0 are recognized as a polynomial bp-1tp-1+bp-2tp-2+ . . . +b1t+b0;
• and
• an output result unit outputting the arithmetic result, wherein
• gs (mod f(t)) is calculated by said arithmetic unit using the value g of the p bits stored in said generator storage unit, and the value s of low order c bits of the p bits stored in said internal status storage unit, the calculation result is stored in said internal status storage unit, high order o bits of the p bits stored in said internal status storage unit are output, and a series of which processes are repeated a times, thereby generating a pseudo-random number.