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.

主权项

1. A method, comprising:
selecting a non-prime multiplier (R) in accordance with a formula R=P1wherein P is a prime number and I a number is selected such that PI is less than the number of bits in every packet of a plurality of packets, the plurality of packets corresponding to a message; generating a non-prime modulus (M) wherein M is generated in accordance a formula M=(PN*QT)−1, where N, Q and T are numbers selected such that M is greater than the number of bits in every packet of the plurality of packets and N>1, wherein M and R are relative prime numbers; employing M and R, in accordance with a cryptography system, to encrypt each packet of plurality of packets to generate a plurality of encrypted packets; aggregating the plurality of encrypted packets to generate an encrypted message; and transmitting the encrypted message.