Patent ID: 7936874

Claim:
An information transfer system for transferring information in secrecy using an elliptic curve discrete logarithm problem as a basis for security, the information transfer system comprising an encryption device and a decryption device, wherein the encryption device comprises: a storage unit storing a plaintext that is a scalar; an encryption unit including: a random number generation unit operable to generate a random number that is a scalar; a first calculation unit operable to multiply a base point on an elliptic curve by the random number, the elliptic curve being defined over a finite field GF(p) by an equation y 2 =x 3 +a×x+b, where p is a prime; a second calculation unit operable to multiply a public key point on the elliptic curve by the random number; a conversion unit operable to apply, to the plaintext, a conversion function, which converts a scalar to a corresponding point on the elliptic curve, to generate a plaintext point on the elliptic curve; a third calculation unit operable to judge whether a y coordinate of a result of the multiplying of the base point is smaller than (p−1)/2, and operable to set, as a sum point, (i) a sum of the plaintext point and a result of the multiplying of the public key point, when the judgment by the third calculation unit is affirmative, and (ii) a corresponding negative point of the sum of the plaintext point and the result of the multiplying of the public key point, when the judgment by the third calculation unit is negative; and a generation unit operable to generate a ciphertext that includes the sum point and an x coordinate of the result of the multiplying of the base point, which is an encryption point; and an output unit operable to output the generated ciphertext, and wherein the decryption device comprises: an acquisition unit operable to acquire the ciphertext from the encryption device; and a decryption unit including: a square root calculation unit operable to substitute the x coordinate included in the acquired ciphertext into the equation y 2 =x 3 +a×x+b to find two solutions y, operable to select one of the two solutions y that is smaller than (p−1)/2, and operable to generate a first decryption point, which is made up of the x coordinate included in the acquired ciphertext and the selected solution, as a y coordinate; a scalar multiplication unit operable to multiply the first decryption point by a secret key that is a scalar, to generate a second decryption point, the public key point having been generated by multiplying the base point on the elliptic curve by the secret key; and a decrypted text calculation unit operable to subtract the second decryption point from the sum point included in the acquired ciphertext, and operable to apply an inverse conversion function, which converts a point on the elliptic curve to a corresponding scalar, to a point obtained as a result of the subtraction by the decrypted text calculation unit, to generate a decrypted text.