International Business Machines Corporation

Puvichakravarthy Ramachandran

Arun C Ramachandran

Lakshmanan Velusamy

The disclosed technology generates two relative prime numbers and, then, using the relative prime numbers converts a super-increasing (SI) knapsack into a non-super-increasing (NSI) knapsack. The NSI knapsack becomes a public key and the corresponding SI knapsack, along with the two relative prime numbers, becomes a private key. A message is encrypted using a subset S of the private key that totals a number N. The message, the public key and the number N are transmitted to a recipient, who knows the value of the two relative prime numbers. The recipient uses the relative prime numbers to convert the public key into the private key and, then, generates the subset S by solving the private key with respect to the number N. Using the subset, the message is decrypted.

Generation of relative prime numbers for use in cryptography

The disclosed technology generates two relative prime numbers and, then, using the relative prime numbers converts a super-increasing (SI) knapsack into a non-super increasing (NSI) knapsack. The NSI knapsack becomes a public key and the corresponding SI knapsack, along with the two relative prime numbers, becomes a private key. A message is encrypted using a subset S of the private key that totals a number N. The message, the public key and the number N are transmitted to a recipient, who knows the value of the two relative prime numbers. The recipient uses the relative prime numbers to convert the public key into the private key and, then, generates the subset S by solving the private key with respect to the number N. Using the subset, the message is decrypted.

An Eroot unit is configured to compute an Eroot of a number A with a machine. The Eroot unit locates a value E, which is even, in a first entry of a plurality of entries of a structure. The Eroot unit is configured to read a product of the pair of prime numbers from the first entry. The Eroot unit is configured to read a second of the pair of key values in the first entry. The Eroot unit is configured to encrypt the number A using the product of the pair of prime numbers to generate an encrypted value. The Eroot unit is configured to apply a decryption operation to the encrypted value using the second of the pair of key values to generate an intermediate value. The Eroot unit is configured to compute a square root of the intermediate value.

Growing community of inventors

Nagamalai, India

Puvichakravarthy Ramachandran