ENCRYPTION/DECORDING APPARATUS AND PUBLIC KEY ENCRYPTION SYSTEM AS WELL AS ENCRYPTION/DECRYPTION METHOD AND PUBLIC KEY ENCRYPTION METHOD

摘要

PROBLEM TO BE SOLVED: To unequivocally decrypt plaintext from ciphertext, to make the ciphertext strong to a selected cipher attack and to make the ciphertext usable for digital signature by selecting the output of a second selector or third multiplier by the output of a comparator and outputting the same as the ciphertext. SOLUTION: The multiplier 131 calculates the remainder 2y mod N when the output y of a square circuit 120 subjected to division of twice y by N. The selector 132 produces the output of the multiplier 131 in the case of a Jacobi symbol (M|N)=-1 and outputs y in other cases. The comparator 142 compares the magnitude of the output (N-1)/2 of a shifter 141 and the output z of the selector 132. The multiplier 143 calculates the remainder -z mod N when -1 times the output z of the selector 132 is divided by N. The selector 144 selects and output the output -z mod N of the multiplier 143 when the output of the comparator 142 indicates z>(N-1)/2. The selector selects the output z of the selector 132 in other cases and outputs the same as the ciphertext C from an output terminal 153.