Cryptography using multi-factor key system and finite state machine

• US 10,320,758 B2
• Filed: 04/25/2017
• Issued: 06/11/2019
• Est. Priority Date: 04/25/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jawaharlal, Samuel M., Narayanan, Arunachalam, Santhar, Sathya, Sivaramalingam, Balamurugaramanathan
• Primary Examiner(s): Garcia, Gary S
• Application Number:
  US15/496,020
• Publication Number:
  US 20180309737A1
• Time in Patent Office: 777 Days
• Field of Search: None
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3006 underlying computational problems or public-key parameters

Abstract

A process selects a public key from a plurality of public keys provided by a message recipient that is to receive an encrypted message. The process establishes an input alphabet for a finite-state machine. The process further constructs the finite-state machine and a language over the input alphabet such that the finite-state machine accepts the language, where the language includes language elements. The process encrypts a language element of the language using the selected public key to provide an encrypted language element. The process electronically transmits the encrypted language element and a specification of the finite-state machine to the message recipient for securely identifying the selected public key to the message recipient. The process encrypts a message using the selected public key to provide the encrypted message. The process also electronically transmits the encrypted message to the message recipient.

Claims

1. A computer-implemented method comprising:

selecting, by a first computing device, a public key from a plurality of public keys provided by a message recipient that is to receive an encrypted message over a communication network;

establishing an input alphabet for a finite-state machine;

constructing the finite-state machine and a language over the input alphabet such that the finite-state machine accepts the language, wherein the language comprises language elements;

encrypting a language element of the language using the selected public key to provide an encrypted language element;

electronically transmitting the encrypted language element and a specification of the finite-state machine to the message recipient for securely identifying the selected public key to the message recipient, wherein the message recipient comprises a second computing device;

encrypting a message using the selected public key to provide the encrypted message to the first computing device; and

electronically transmitting the encrypted message to the message recipient.

2. The method of claim 1, wherein the language is a regular language and the finite-state machine accepts only the elements of the language.

3. The method of claim 1, further comprising randomly selecting the language element from the plurality of language elements of the language.

4. The method of claim 1, wherein the electronically transmitting the encrypted message to the message recipient is based on receiving an indication from the message recipient that electronic transmission of the encrypted message is to commence.

5. The method of claim 4, wherein the receiving the indication from the message recipient is based on the message recipient identifying the selected public key from the plurality of public keys and identifying a private key corresponding to the selected public key.

6. The method of claim 1, further comprising performing an initial attempt to securely identify an initial public key of the plurality of public keys to the message recipient, wherein based on an initial constructed finite-state machine and initial encrypted language element, decryption of the initial encrypted language element using each private key of a plurality of private keys corresponding to the plurality of public keys provides a plurality of initial decrypted language elements that are accepted by the initial finite-state machine, thereby indicating multiple candidate public keys, of the plurality of public keys, that could be the initial public key.

7. The method of claim 6, wherein based on receiving an indication from the message recipient that a definitive identification of the initial public key to the message recipient has failed, the method performs the selecting the public key, the establishing the input alphabet, and the constructing the finite-state machine and language over the input alphabet.

8. The method of claim 1, further comprising initially determining whether to encrypt the message using a first encryption technique including a single cryptographic key pair or using a second encryption technique, the second encryption technique comprising the selecting the public key, the establishing the input alphabet, the constructing the finite-state machine and language over the input alphabet, the encrypting the language element, and the electronically transmitting the encrypted language element and specification of the finite-state machine to the message recipient.

9. The method of claim 8, wherein the determining whether to use the first encryption technique or the second encryption technique is based on weighing an anticipated length of data transfer of the encrypted message against resource consumption anticipated to be consumed in identifying, for the message recipient a public key, of the plurality of public keys, to be used to encrypt the message.

10. A computer program product comprising:

a non-transitory computer readable storage medium readable by a processor and storing instructions for execution by the processor for performing a method comprising;

selecting, by a first computing device, a public key from a plurality of public keys provided by a message recipient that is to receive an encrypted message over a communication network;

establishing an input alphabet for a finite-state machine;

constructing the finite-state machine and a language over the input alphabet such that the finite-state machine accepts the language, wherein the language comprises language elements;

encrypting a language element of the language using the selected public key to provide an encrypted language element;

electronically transmitting the encrypted language element and a specification of the finite-state machine to the message recipient for securely identifying the selected public key to the message recipient, wherein the message recipient comprises a second computing device;

encrypting a message using the selected public key to provide the encrypted message to the first computing device; and

electronically transmitting the encrypted message to the message recipient.

11. The computer program product of claim 10, wherein the language is a regular language and the finite-state machine accepts only the elements of the language.

12. The computer program product of claim 10, wherein the electronically transmitting the encrypted message to the message recipient is based on receiving an indication from the message recipient that electronic transmission of the encrypted message is to commence.

13. The computer program product of claim 12, wherein the receiving the indication from the message recipient is based on the message recipient identifying the selected public key from the plurality of public keys and identifying a private key corresponding to the selected public key.

14. The computer program product of claim 10, wherein the method further comprises initially determining whether to encrypt the message using a first encryption technique including a single cryptographic key pair or using a second encryption technique, the second encryption technique comprising the selecting the public key, the establishing the input alphabet, the constructing the finite-state machine and language over the input alphabet, the encrypting the language element, and the electronically transmitting the encrypted language element and specification of the finite-state machine to the message recipient.

15. The computer program product of claim 14, wherein the determining whether to use the first encryption technique or the second encryption technique is based on weighing an anticipated length of data transfer of the encrypted message against resource consumption anticipated to be consumed in identifying, for the message recipient a public key, of the plurality of public keys, to be used to encrypt the message.

16. A computer system comprising:

a memory device; and

a hardware processor in communications with the memory, wherein the computer system is configured to perform a method comprising;

selecting, by a first computer system, a public key from a plurality of public keys provided by a message recipient that is to receive an encrypted message over a communication network;

establishing an input alphabet for a finite-state machine;

constructing the finite-state machine and a language over the input alphabet such that the finite-state machine accepts the language, wherein the language comprises language elements;

encrypting a language element of the language using the selected public key to provide an encrypted language element;

electronically transmitting the encrypted language element and a specification of the finite-state machine to the message recipient for securely identifying the selected public key to the message recipient, wherein the message recipient comprises a second computer device;

encrypting a message using the selected public key to provide the encrypted message to the first computing device; and

electronically transmitting the encrypted message to the message recipient.

17. The computer system of claim 16, wherein the language is a regular language and the finite-state machine accepts only the elements of the language.

18. The computer system of claim 16, wherein the electronically transmitting the encrypted message to the message recipient is based on receiving an indication from the message recipient that electronic transmission of the encrypted message is to commence.

19. The computer system of claim 18, wherein the receiving the indication from the message recipient is based on the message recipient identifying the selected public key from the plurality of public keys and identifying a private key corresponding to the selected public key.

20. The computer system of claim 16, wherein the method further comprises initially determining whether to encrypt the message using a first encryption technique including a single cryptographic key pair or using a second encryption technique, the second encryption technique comprising the selecting the public key, the establishing the input alphabet, the constructing the finite-state machine and language over the input alphabet, the encrypting the language element, and the electronically transmitting the encrypted language element and specification of the finite-state machine to the message recipient, and wherein the determining whether to use the first encryption technique or the second encryption technique is based on weighing an anticipated length of data transfer of the encrypted message against resource consumption anticipated to be consumed in identifying, for the message recipient a public key, of the plurality of public keys, to be used to encrypt the message.