DECODING DEVICE AND DECODING PROGRAM, AND KEY GENERATING DEVICE AND KEY GENERATING PROGRAM

摘要

PROBLEM TO BE SOLVED: To provide a key generating device and a key generating program, and a decoding device and a decoding program that use a new trap door of knapsack encryption. SOLUTION: A ciphertext C is modular-multiplied to generate an intermediate plaintext I. A residue T for a divisor bi is found for the intermediate plaintext I and the number of bits below bi is decrypted together. Then T is subtracted from the intermediate plaintext I and division by the divisor bi is performed to find a residue for a next divisor. Thus, the new trap door of knapsack encryption can be provided. COPYRIGHT: (C)2008,JPO&INPIT