US 2004/0062390 A1 · Public key cryptography using matrices

Abstract

The invention provides techniques for secure messages transmission using a public key system to exchange secret keys. A first entity creates public and private keys by generating a product n of two large, randomly chosen prime numbers, and then generating random matrices {A, C}, in the group GL(r,Zn) with a chosen matrix rank r such that AC is not equal to CA, and then generating a matrix B=CAC, and finding a matrix G that commutes with C. Matrices A, B, G and the integers n and r are then published as the public key and matrix C is then kept as the private key. A second entity then obtains the public key and calculates a secret matrix D that commutes with G, and further calculates the matrices K=DBD and E=DAD. The message to be sent is then encrypted using matrix K as the secret key and then sent to the first entity with matrix E. First entity then retrieves secret matrix K using K=CEC and then decrypts the received encrypted message using the retrieved secret matrix K.

Claims41

Dependent claims

A method of generating a public key for secure data transmission, comprising:

finding two unique randomly chosen secret prime numbers p and q;
generating a modulus n by using the product of p and q;
generating matrices A and C of rank r with each matrix element in the integers modulo n such that AC is not equal to CA;
generating a matrix B by using the generated matrices A and C such that B≡CAC;
generating a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C;
keeping the generated matrix C as a private key;
forming a public key using the generated matrices A, B, and G, the modulus n, and rank r;
and
publishing the formed public key for encrypting messages to be transmitted.

6 more elements

A cryptographic method of the type using matrices to encode and decode messages, comprising:

finding two unique randomly chosen secret prime numbers p and q;
generating a modulus n by multiplying p and q;
generating matrices A and C of rank r with each matrix element in the integers modulo n such that AC is not equal to CA;
generating a matrix B by using the generated matrices A and C such that B=CAC;
generating a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C;
keeping the generated matrix C as a private key;
forming a public key using the generated matrices A, B, and G, and the modulus n, and rank r;
publishing the formed public key for encrypting messages to be transmitted;
obtaining the published public key including matrices A, B, G, and modulo n and matrix rank r for encrypting a message to be transmitted;
generating a first random secret matrix D that is multiplicatively commutative with the obtained matrix G;
generating a second secret matrix K such that K=DBD;
generating a message matrix E such that E=DAD;
obtaining a message to be sent securely;
encrypting the obtained message using a symmetric-key algorithm by using the generated second secret matrix K as the key;
transmitting the generated message matrix E along with the encrypted matrices;
receiving a transmitted message matrix E along with encrypted message;
retrieving the second secret matrix K using the received message matrix E and the kept private key matrix C;
and
decrypting the encrypted message using the retrieved second secret matrix K with a symmetric-key decryption algorithm to decrypt the received encrypted message.

16 more elements

A method for secure message transmission, comprising:

finding two unique randomly chosen secret prime numbers p and q;
generating a modulus n by using the product of p and q;
generating matrices A and C of a predetermined matrix rank r and with each matrix element in the integers modulo n such that AC is not equal to CA;
generating a matrix B by using the generated matrices A and C such that B CAC;
generating a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C;
keeping the generated matrix C as a private key;
forming a public key using the generated matrices A, B, and G, and the modulus n;
publishing the formed public key for encrypting messages to be transmitted;
obtaining the published public key including matrices A, B, G, and modulo n for encrypting a message to be transmitted;
generating a first random secret matrix D that is multiplicatively commutative with the obtained matrix G;
generating a second secret matrix K such that K=DBD;
generating a message matrix E such that E=DAD;
obtaining a message to be sent securely;
encrypting the obtained message using a symmetric-key algorithm by using the generated second secret matrix K as the key;
transmitting the generated message matrix E along with the encrypted matrices;
receiving a transmitted message matrix E along with the encrypted message;
retrieving the second secret matrix K=CEC using the received message matrix E and the kept private key matrix C;
and
decrypting the encrypted message using the retrieved second secret matrix K with a symmetric-key decryption algorithm to decrypt the received encrypted message.

16 more elements

A computer-readable medium having computer-executable instructions for transmitting a message using a public key system, comprising:

finding two unique randomly chosen secret prime numbers p and q;
generating a modulus n by using the product of p and q;
generating matrices A and C of a predetermined matrix rank r with each matrix element in the integers modulo n such that AC is not equal to CA;
generating a matrix B by using the generated matrices A and C such that B CAC;
generating a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C;
keeping the generated matrix C as a private key;
forming a public key using the generated matrices A, B, and G, and the modulus n;
publishing the formed public key for encrypting messages to be transmitted;
obtaining the published public key including matrices A, B, G, and modulo n for encrypting a message to be transmitted;
generating a first random secret matrix D that is multiplicatively commutative with the obtained matrix G;
generating a second secret matrix K such that K=DBD;
generating a message matrix E such that E=DAD;
obtaining a message to be sent securely;
encrypting the obtained message using a symmetric-key algorithm by using the generated second secret matrix K as the key;
transmitting the generated message matrix E along with the encrypted matrices;
receiving a transmitted message matrix E along with the encrypted message;
retrieving the second secret matrix K=CEC using the received message matrix E and the kept private key matrix C;
and
decrypting the encrypted message using the retrieved second secret matrix K with a symmetric-key decryption algorithm to decrypt the received encrypted message.

16 more elements

A computer system for secure message transmission, comprising:

a processor;
an output device;
and
a storage device to store instructions that are executable by the processor to perform secure message transmission, comprising:
finding two unique randomly chosen secret prime numbers p and q;
generating a modulus n by using the product of p and q;
generating matrices A and C of a predetermined matrix rank r with each matrix element in the integers modulo n such that AC is not equal to CA;
generating a matrix B by using the generated matrices A and C such that B=CAC;
generating a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C;
keeping the generated matrix C as a private key;
forming a public key using the generated matrices A, B, and G, and the modulus n;
publishing the formed public key for encrypting messages to be transmitted;
obtaining the published public key including matrices A, B, G, and modulo n for encrypting a message to be transmitted;
generating a first random secret matrix D that is multiplicatively commutative with the obtained matrix G;
generating a second secret matrix K such that K=DBD;
generating a message matrix E such that E=DAD;
obtaining a message to be sent securely;
encrypting the obtained message using a symmetric-key algorithm by using the generated second secret matrix K as the key;
transmitting the generated message matrix E along with the encrypted matrices;
receiving a transmitted message matrix E along with the encrypted message;
retrieving the second secret matrix K=CEC using the received message matrix E and the kept private key matrix C;
and
decrypting the encrypted message using the retrieved second secret matrix K with a symmetric-key decryption algorithm to decrypt the received encrypted message.

20 more elements

A cryptographic communication system, comprising:

a receiver computing platform comprises:
a processor to generate two matrices A and C of rank r with each matrix element in the integers modulo n such that AC does not equal to CA, wherein modulo n is obtained by using two unique randomly chosen secret prime numbers p and q, wherein r is a matrix rank of the two matrices A and C, wherein the processor generates a matrix B by using the generated matrices A and C such that B≡CAC, wherein the processor further generates a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C, and wherein the processor publishes the generated matrices A, B, G, and modulo n and matrix rank r as the public key, and retains the generated matrix C as the private key;
a sender coupled to the receiver computing platform through a network comprises:
an encoder to obtain the published matrices A, B, G, and modulo n and matrix rank r for encrypting a message to be transmitted, wherein the encoder generates a first random secret matrix D that is multiplicatively commutative with the obtained matrix G, wherein the encoder generates a second secret matrix K=DBD using the generated matrices B and D, wherein the encoder generates a message matrix E=DAD using the generated matrices A and D, wherein the encoder obtains a message to be sent securely and encrypts the obtained message using a symmetric-key algorithm by using the generated second secret matrix K as the key, and wherein the encoder transmits the generated message matrix E along with the encrypted message;
and
a receiver coupled to the sender through the network and further coupled to the receiver computing platform comprises:
a decoder to receive the transmitted message matrix E and the encrypted message, wherein the decoder retrieves the second secret matrix K=CEC using the received message matrix E and the kept matrix C as the private key, and wherein the decoder decrypts the encrypted message uses the retrieved second secret matrix K with a symmetric-key decryption algorithm to obtain the transmitted message.

4 more elements

A system for secure messages transmission, comprising:

a first entity computing platform comprises:
a processor to generate two matrices A and C of a predetermined matrix rank r and with each matrix element in the integers modulo n such that AC does not equal to CA, wherein modulo n is obtained by using two unique randomly chosen secret prime numbers p and q, wherein r is a matrix rank of the two matrices A and C, wherein the processor generates a matrix B by using the generated matrices A and C such that B=CAC, wherein the processor further generates a matrix G such that the generated matrix G is in the same multiplicatively commutative subgroup as C, and wherein the processor publishes the generated matrices A, B, G, and modulo n as the public key, and retains the generated matrix C as the private key;
a second entity desiring to send a secure message is coupled to the first entity computing platform through a network comprises:
an encoder to obtain the published matrices A, B, G, and modulo n for encrypting a message to be transmitted, wherein the encoder generates a first random secret matrix D that is multiplicatively commutative with the obtained matrix G, wherein the encoder generates a second secret matrix K using the generated matrices B and D, wherein the encoder generates a message matrix E=DAD using the generated matrices A and D, wherein the encoder obtains a message to be sent securely and encrypts the obtained message using a symmetric-key algorithm by using the generated second secret matrix K as the key, and wherein the encoder transmits the generated message matrix E along with the encrypted message;
and
a first entity desiring to receive the encrypted message is coupled to the second entity through the network and further coupled to the first entity computing platform comprises:
a decoder to receive the transmitted message matrix E and the encrypted message, wherein the decoder retrieves the second secret matrix K=CEC using the received message matrix E and the kept matrix C as the private key, and wherein the decoder decrypts the encrypted message using the retrieved second secret matrix K with a symmetric-key decryption algorithm to obtain the transmitted message.

4 more elements

Dependencies are inferred from the claim text.

Public key cryptography using matrices

Life of this patent

Public key cryptography using matrices

Life of this patent

Abstract

Claims41