Patent ID: 7957525
Filing Date: 2011-06-07
Classification: H04L

Abstract:
1. A computer method for performing an encryption or a signature verification using a first method which is either (i) an encryption method that provides at least ciphertexts at least of a length equal to a first predetermined length and of a smaller length, or (ii) a signature-verification method that verifies at least signatures of messages of a length equal to the first predetermined length and of a smaller length, the method comprising performing the encryption or the verification on a first message with a computer system, wherein the encryption or verification on the first message comprises: (1) determining by the computer system, for the first message, a first intermediate message in a predetermined set of messages which are either (i) encryptable with the first method into ciphertexts shorter than the first predetermined length, or (ii) comprise signatures of only those messages which are shorter than the first predetermined length; and (2) applying by the computer system the first method to perform encryption or signature verification on the first intermediate message with the first method; wherein all said messages are representable as integers modulo a predetermined composite modulus N, and the operation (2) comprises the computer system computing a square of a number obtained from the first intermediate message modulo N; wherein all said messages are representable as integers, and the operation (1) comprises: (1A) the computer system associating the first message to an interval (“first intermediate-message interval”) in a predetermined finite set of intervals; and (1B) the computer system selecting the first intermediate message to be an integer in the first intermediate-message interval; wherein said intervals are Farey intervals or Farey extended partition intervals; wherein the first message is in a predetermined first interval of messages, and the first intermediate message is in a predetermined second interval of messages, the second interval containing all said Farey intervals or all said Farey extended partition intervals; wherein the operation (1A) comprises using a predetermined mapping of the first interval into the second interval to determine the first intermediate-message interval as a Farey interval or Farey extended partition interval containing an image of the first message under said predetermined mapping; wherein the operation (1B) comprises selecting the first intermediate message as the first intermediate-message interval's integer whose enumeration in the first intermediate-message interval corresponds to an enumeration of the first message in the first interval.