Patent ID: 8433065
Filing Date: 2013-04-30
Classification: H04L

Abstract:
1. A method comprising performing a cryptographic operation by an apparatus comprising: one or more computer processors programmed to execute the cryptographic operation by executing computer instructions stored in a computer readable medium; and/or hardwired circuitry for executing the cryptographic operation; wherein performing the cryptographic operation comprises performing, by executing the computer instructions and/or by the hardwired circuitry, operations of: obtaining a first message representable as an integer modulo a predetermined composite modulus N, the first message being in a first sub-range of a set Z submitting the first message as an input to a process which determines, from each input which is an integer in the first sub-range, a corresponding output in a set of messages whose squares modulo N are in a second sub-range of the set Z (1) associating the input to an interval (“second-message interval”) in a predetermined finite set of Farey intervals or Farey extended partition intervals; and (2) selecting the corresponding output to be an integer in the second-message interval; wherein the method further comprises: performing said process on the first message as the input, to obtain a second message as the corresponding output; squaring the second message modulo N; wherein the composite modulus N has a secret factorization to provide security to the cryptographic operation, the cryptographic operation's security depending on hardness of computing square roots modulo N.