Copyright protection system, modular exponentiation operation apparatus, and modular exponentiation operation method

A modular exponentiation operation apparatus comprising:

• a storing unit storing therein an operand S, which is a natural number;
• a reading unit that reads the operand S from the storing unit;
• a selecting unit that selects prime numbers expressed by
• ∑
• m
• =
• 1
• a
• -
• 1
• ⁢
• C
• m
• -
• 1
• a
• -
• 1
• where a is a natural number being 2 or larger and m is a variable natural number being any number from 1 through a−1, from among 2a−2 prime numbers that are mutually different;
• and
• a calculating unit that performs a modular exponentiation operation over a finite field, the modular exponentiation operation seeking a value expressed by
• S′=S1/P mod N
• where N is a product of a prime number p and a prime number q, the prime numbers p and q are larger than a predetermined value, and P is a product of all of the prime numbers selected by the selecting unit,
• wherein the selecting unit includes:
• a prime number storing subunit storing therein the 2a−2 prime numbers that are in one-to-one correspondence with all possible combinations in which a number of branches equal to all of the numbers from 1 through (a−1) are selected from among a branches each connecting to one of nodes in an a-ary tree;
• and
• a branch obtaining subunit that obtains branch information specifying one branch out of the a branches;
• and
• a prime number selecting subunit that selects all prime numbers being in correspondence with combinations that each include the branch specified in the branch information, from among the 2a−2 prime numbers stored in the prime number storing subunit, and
• wherein the modular exponentiation operation apparatus further comprises:
• a reversible operation unit that performs a reversible operation on the calculated value S′ to obtain a reversible operation result value;
• a writing unit that overwrites the operand S stored in the storing unit with the reversible operation result value such that the reversible operation result value is stored as the operand S;
• and
• a repetition control unit that controls the branch obtaining subunit, the prime number selecting subunit, the calculating unit, the reversible operation unit, and the writing unit so that, on each of branches positioned on a path from a root to a leaf in the a-ary tree, starting from the root and ending with the leaf, the obtainment of branch information specifying the branch, the selection of all prime numbers being in correspondence with combinations that each include the specified branch, the modular exponentiation operation based on S′=S1/P mod N, the reversible operation on the calculated value S′, and the writing of the reversible operation result value into the storing unit are repeatedly performed.

A modular exponentiation operation apparatus comprising:

• a storing unit storing therein an operand S′, which is a natural number;
• a prime number storing unit storing therein 2a−2prime numbers that are in one-to-one correspondence with all possible combinations in which a number of branches equal to all of the numbers from 1 through (a−1) are selected from among a branches each connecting to one of nodes in an a-ary tree;
• an obtaining unit that obtains specification information that specifies one or more prime numbers out of the prime numbers stored in the prime number storing unit;
• and
• a calculating unit that performs a modular exponentiation operation over a finite field, the modular exponentiation operation being defined by
• (S′)Q mod N
• where N is a product of a prime number p and a prime number q, the prime numbers p and q are larger than a predetermined value, and Q is a product of all of the prime numbers specified in the specification information;
• a storage unit storing therein an operand S, which is a natural number;
• a reading unit that reads the operand S from the storage unit;
• a branch obtaining unit that obtains branch information that specifies one branch out of the a branches;
• a prime number selecting unit that selects all prime numbers being in correspondence with combinations that each include the branch specified in the branch information, from among the 2a−2prime numbers stored in the prime number storing unit;
• a generating unit that performs a modular exponentiation operation over a finite field, the modular exponentiation operation seeking a value expressed by
• R=SP mod N
• where N is the product of the prime number p and the prime number q, the prime numbers p and q are larger than the predetermined value, and P is a product of all of the prime numbers selected by the prime number selecting unit;
• a first writing unit that overwrites the operand S stored in the storage unit with the calculated value R such that the calculated value R is stored as the operand S;
• a repetition control unit that controls the branch obtaining unit, the prime number selecting unit, the generating unit, and the first writing unit so that, on each of branches positioned on a path from a leaf to a node in the a-ary tree, starting from the leaf and ending with the node, the obtainment of branch information specifying the branch, the selection of all prime numbers being in correspondence with combinations that each include the specified branch, the modular exponentiation operation based on R=SP mod N, and the writing of the calculated value R into the storage unit are repeatedly performed;
• and
• a second writing unit that writes, after the repetition control unit finishes performing the control, the calculated value R such that the calculated value R is stored as S′ in the storing unit.