Patent Description:
A secure communication in an in-vehicle network highly depends on how cryptographic keys are stored, especially in the case of secure software updates, which need verification before updating from a (backend) server. For instance, cryptographic keys for secure on-board communication are typically stored in Hardware Security Module (HSM). However, if these cryptographic keys are public (cryptographic) keys used for verification, then these cryptographic keys need to be updated time to time. Usually, the public (cryptographic) keys must be updated frequently to prevent unexpected "Key Expired" situation. To perform updates on public (cryptographic) keys are quite costly and cumbersome due to extra operations that involves generation of public keys, making public key exchanges, and the like. Furthermore, storing public (cryptographic) keys require large amount of memory space, which may not be feasible.

For instance, <CIT> provides a method and apparatus for determining key pair (i.e., public-private key pair) and for generating Rivest Shamir Adleman (RSA) keys. This prior art discusses method to improve security of RSA cryptosystem using longer prime numbers and limiting the computation time. However, this prior art fails to address the issue of storage space required for storing the key pairs.

Document <CIT> suggests a computing device which has a processor and a first memory, e.g., a fuse-based memory, storing a first cryptographic key. The processor is configured to receive information related to a second cryptographic key from a cryptographic key provisioning system. The processor derives the second cryptographic key from the information related to a second cryptographic key. The first cryptographic key has fewer bits than the second cryptographic key. The processor is also configured to encrypt the second cryptographic key using the first cryptographic key, and store the encrypted second cryptographic key in a second memory, e.g., a flash memory. Document <CIT> relates to an apparatus for ciphering, including a non-volatile memory, which stores a number from which a private cryptographic key, having a complementary public cryptographic key, is derivable, wherein the number is shorter than the private cryptographic key, and a processor, which is configured to receive an instruction indicating that the private cryptographic key is to be applied to data and, responsively to the instruction, to compute the private cryptographic key using the stored number and to perform a cryptographic operation on the data using the private cryptographic key. Document <CIT> relates to procedures and a system for the ECUs within the vehicle to securely create and exchange session keys for further secure communication are disclosed. The procedures and system eliminate the need for securely tracking and storing all secret keys used on all vehicles. The procedures and system utilize public key cryptography to establish and maintain at least one session key and a set of shared secrets and challenges to facilitate use of private key cryptography within vehicle networks.

The information disclosed in this background of the disclosure section is for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person skilled in the art.

In an embodiment, the present disclosure relates to a method for retrieving public keys in a memory constrained system. The method includes generating a plurality of public cryptographic keys and private cryptographic keys using a cryptographic technique and characterizing each of the plurality of public cryptographic keys and corresponding private cryptographic keys into an associated first cryptographic component and a second cryptographic component. Thereafter, the method comprising creating at least one relationship matrix comprising the first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys. The at least one relationship matrix is created for each of the second cryptographic component of the private cryptographic keys based on predetermined rules. Subsequently, the method comprising receiving a first cryptographic component and a second cryptographic component of a private cryptographic key from a cryptographic system associated with an ECU of the vehicle when a public cryptographic key is required. Lastly, the method comprising retrieving the public cryptographic key based on the first cryptographic component and the second cryptographic component of the private cryptographic key using the relationship matrix corresponding to the second cryptographic component of the private cryptographic key and the predetermined rules, thereby, minimizing memory required for storing the plurality of public cryptographic keys and private cryptographic keys.

In an embodiment, the present disclosure relates to a system for retrieving public keys in a memory constrained system. The system includes a cryptographic system and an Electronic Control Unit (ECU) of a vehicle. The cryptographic system comprising a processor and a memory communicatively coupled to the processor, wherein the memory stores processor-executable instructions, which on execution, cause the processor to generate a plurality of public cryptographic keys and private cryptographic keys using a cryptographic technique and characterize each of the plurality of public cryptographic keys and corresponding private cryptographic keys into an associated first cryptographic component and a second cryptographic component. Thereafter, the cryptographic system is configured to create at least one relationship matrix comprising the first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys. The at least one relationship matrix is created for each of the second cryptographic component of the private cryptographic keys based on predetermined rules. In the subsequent step, the ECU of the vehicle is configured to receive a first cryptographic component and a second cryptographic component of a private cryptographic key from the cryptographic system associated with the ECU of the vehicle when a public cryptographic key is required. Lastly, the cryptographic system is configured to retrieve the public cryptographic key based on the first cryptographic component and the second cryptographic component of the private cryptographic key using the relationship matrix corresponding to the second cryptographic component of the private cryptographic key and the predetermined rules, thereby, minimizing memory required for storing the plurality of public cryptographic keys and private cryptographic keys.

Embodiments of the disclosure according to the above-described method and system may bring about several advantages.

In present disclosure, a relationship matrix comprising one or more of the first cryptographic component for each of the plurality of public cryptographic keys and corresponding private cryptographic keys is stored in an Electronic Control Unit of a vehicle. Since the present disclosure makes use of the relationship between private cryptographic key and public cryptographic key, storage size required for the relationship matrix is small.

Furthermore, the relationship matrix involves simple mapping logic to re-generate public cryptographic keys from private cryptographic keys.

Due to small storage size for relationship matrix and a simple mapping logic to re-generate public cryptographic keys from private cryptographic keys, the cost of updating public cryptographic keys from time to time as a requirement for any application based on cryptographic system is reduced significantly.

The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and together with the description, serve to explain the disclosed principles. The same numbers are used throughout the figures to reference like features and components. Some embodiments of system and/or methods in accordance with embodiments of the present subject matter are now described below, by way of example only, and with reference to the accompanying figures.

It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative systems embodying the principles of the present subject matter. Similarly, it will be appreciated that any flowcharts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and executed by a computer or processor, whether or not such computer or processor is explicitly shown.

While the disclosure is susceptible to various modifications and alternative forms, specific embodiment thereof has been shown by way of example in the drawings and will be described in detail below. It should be understood, however that it is not intended to limit the disclosure to the particular forms disclosed, but on the contrary, the disclosure is to cover all modifications, equivalents, and alternatives falling within the scope of the disclosure.

The terms "comprises", "comprising", or any other variations thereof, are intended to cover a non-exclusive inclusion, such that a setup, device or method that comprises a list of components or steps does not include only those components or steps but may include other components or steps not expressly listed or inherent to such setup or device or method. In other words, one or more elements in a system or apparatus proceeded by "comprises. a" does not, without more constraints, preclude the existence of other elements or additional elements in the system or method.

In the following detailed description of the embodiments of the disclosure, reference is made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the disclosure may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the disclosure, and it is to be understood that other embodiments may be utilized and that changes may be made without departing from the scope of the present disclosure. The following description is, therefore, not to be taken in a limiting sense.

Embodiments of the present disclosure provide a solution for generating, storing and retrieving public keys in a memory constrained system. In the present disclosure, the memory constrained system may refer, but not limited, to the Electronic Control Unit (ECU) of a vehicle. However, the memory constrained system may be applicable to a system involved in applications from the field of embedded security and cyber security. The present disclosure reveals a method to create/generate at least one relationship matrix comprising mapping between components of public cryptographic keys and corresponding private cryptographic keys. The generated/created relationship matrix is then stored in an ECU of a vehicle. The stored relationship matrix in the ECU of the vehicle is used to retrieve correct corresponding public cryptographic key by knowing only some parts of private cryptographic key received from a cryptographic system associated with the vehicle. The technical advantage of the present disclosure is three-fold: (<NUM>) reduces storage size significantly as components of public cryptographic keys and corresponding private cryptographic keys are stored in the form of (relationship) matrix, (<NUM>) provides a simple mapping logic to re-generate/retrieve public cryptographic keys from the components of private cryptographic keys, and (<NUM>) reduces the cost significantly of updating public cryptographic keys from time to time as a requirement.

<FIG> illustrates an exemplary environment for generating, storing and retrieving public keys in a memory constrained system in accordance with some embodiments of the present disclosure.

As shown in the <FIG>, the system <NUM> includes a cryptographic system <NUM>, a communication network <NUM> and an ECU <NUM> of a vehicle (hereinafter referred as ECU <NUM>). The cryptographic system <NUM> may be present on a local server or on a cloud server. The cryptographic system <NUM> may create at least one relationship matrix comprising first cryptographic component of each of a plurality of public cryptographic keys and corresponding private cryptographic keys using a plurality of public cryptographic keys and private cryptographic keys. In brief, the relationship matrix contains mapping of first cryptographic component of each of a plurality of public cryptographic keys with corresponding private cryptographic keys based on predetermined rules (creation of relationship matrix is described later). Furthermore, the cryptographic system <NUM> may update stored at least one relationship matrix with at least one new relationship matrix in the ECU <NUM> of the vehicle when a change in a public cryptographic key is required. The cryptographic system <NUM> may store and/or update the relationship matrix in the ECU <NUM> through the communication network <NUM>. In one embodiment, there may be a plurality of ECUs <NUM> instead of a single ECU <NUM> (not shown in <FIG>). Each ECU <NUM> may be associated with a single vehicle. The communication network <NUM> may include, but is not limited to, a direct interconnection, an e-commerce network, a Peer-to-Peer (P2P) network, Local Area Network (LAN), Wide Area Network (WAN), wireless network (for example, using Wireless Application Protocol), Internet, Wi-Fi, Bluetooth and the like.

In the embodiment, the cryptographic system <NUM> may use a plurality of public cryptographic keys and private cryptographic keys to create at least one relationship matrix comprising first cryptographic component for each of the plurality of public cryptographic keys and corresponding private cryptographic keys based on predetermined rules (discussed later in the section). The cryptographic system <NUM> may include an I/O interface <NUM>, a memory <NUM> and a processor <NUM>. The I/O interface <NUM> may be configured to communicate with the ECU <NUM>. The I/O interface <NUM> may employ communication protocols/methods such as, without limitation, audio, analog, digital, monoaural, Radio Corporation of America (RCA) connector, stereo, IEEE®-<NUM> high speed serial bus, serial bus, Universal Serial Bus (USB), infrared, Personal System/<NUM> (PS/<NUM>) port, Bayonet Neill-Concelman (BNC) connector, coaxial, component, composite, Digital Visual Interface (DVI), High-Definition Multimedia Interface (HDMI®), Radio Frequency (RF) antennas, S-Video, Video Graphics Array (VGA), IEEE® <NUM>. 11b/g/n/x, Bluetooth, cellular e.g., Code-Division Multiple Access (CDMA), High-Speed Packet Access (HSPA+), Global System for Mobile communications (GSM®), Long-Term Evolution (LTE®), Worldwide interoperability for Microwave access (WiMax®), or the like.

The relationship matrix created by the cryptographic system <NUM> may be stored in the memory <NUM>. The memory <NUM> may be communicatively coupled to the processor <NUM> of the cryptographic system <NUM>. The memory <NUM> may, also, store processor instructions which may cause the processor <NUM> to execute the instructions for generating and storing public keys in a memory constrained system. The memory <NUM> may include, without limitation, memory drives, removable disc drives, etc. The memory drives may further include a drum, magnetic disc drive, magneto-optical drive, optical drive, Redundant Array of Independent Discs (RAID), solid-state memory devices, solid-state drives, etc..

The processor <NUM> may include at least one data processor for generating and storing public keys in a memory constrained system. The processor <NUM> may include specialized processing units such as integrated system (bus) controllers, memory management control units, floating point units, graphics processing units, digital signal processing units, etc..

In the embodiment, the cryptographic system <NUM> may store and/or update the at least one relationship matrix in the ECU <NUM> through the communication network <NUM>. The ECU <NUM> may be any embedded electronic device. The ECU <NUM> may be populated or stored with the at least one relationship matrix that includes first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys created based on predetermined rules. The stored at least one relationship matrix in the ECU <NUM> may be updated by the cryptographic system <NUM> with a new relationship matrix in the ECU <NUM> when a change in a public cryptographic key is required.

Hereafter, the operation of the cryptographic system <NUM> for generating and storing public cryptographic keys in a memory constrained system is described.

The cryptographic system <NUM> generates a plurality of public cryptographic keys and private cryptographic keys using a cryptographic technique. As an example, the cryptographic technique used for generating the plurality of public cryptographic keys and private cryptographic keys is a Rivest Shamir Adleman (RSA) technique. Alternatively, the cryptographic technique used for generating the plurality of public cryptographic keys and private cryptographic keys may be Elliptic-Curve Cryptography (ECC) technique or modular exponentiation-based on logarithm technique. According to the requirements of RSA technique, the plurality of public cryptographic keys and private cryptographic keys must be prime numbers. Each of the plurality of public cryptographic keys and private cryptographic keys is characterized into an associated first cryptographic component and a second cryptographic component by the cryptographic system <NUM>. In detail, the first cryptographic component is a multiple of <NUM>, and the second cryptographic component is a reminder of each of the plurality of public cryptographic keys and private cryptographic keys modulus <NUM>. For instance, each of public cryptographic keys and private cryptographic keys, which are prime numbers, is expressed as <NUM>*k±<NUM>, <NUM>*k±<NUM>, <NUM>*k+<NUM>, or <NUM>*k±<NUM>. Here, k ∈ (<NUM>, <NUM>, <NUM>, <NUM>. In the present disclosure, the term 'k' is referred as the first cryptographic component and the reminder i.e., ±<NUM>, ±<NUM>, ±<NUM>, or ±<NUM> is referred as the second cryptographic component. An example of a public cryptographic key into the associated first cryptographic component (k's value) and the second cryptographic component (reminder value) is shown in <FIG>. Analogously, a private cryptographic key into the associated first cryptographic component (k's value) and the second cryptographic component (reminder value) is expressed. According to the RSA technique, the generation of the public cryptographic keys and private cryptographic keys are as follows:.

Choose two different large random prime numbers 'p' and 'q'.

Calculate n = p * q. Here n is the modulus for the public cryptographic key and the private cryptographic key.

Calculate the totient φ(n) = (p-<NUM>) * (q-<NUM>).

Choose an integer 'e' such that <NUM> < e < φ(n), and 'e' is co-prime to φ(n). For example, 'e' and φ(n) share no factors other than <NUM> i.e., GCD of (e, φ(n)) = <NUM>. Here, 'e' is released as the public key exponent.

Compute 'd' to satisfy the congruence relation d * e ≡ <NUM> (mod φ(n)). For example, d * e = <NUM> + k * φ(n) for some integer 'm' i.e., for instance, if (d * e) equals (<NUM> + m * φ(n)), then the value of m is decided. Thereafter, calculate d = (<NUM>+ m * φ(n))/e. Here, 'd' is kept as the private key exponent.

An example based on the above-mentioned steps is shown below.

Choosing two random prime numbers i.e., p = <NUM> and q = <NUM>.

Computing n = p * q i.e., n = <NUM> * <NUM> = <NUM>.

Computing the totient φ(n) = (p - <NUM>) * (q - <NUM>) i.e., φ(n) = (<NUM> - <NUM>) * (<NUM> - <NUM>) = <NUM>.

Choosing 'e' such that <NUM> < e < <NUM> and 'e' is co-prime to <NUM>.

Based on the above-mentioned steps according to the RSA technique, the plurality of public cryptographic keys and private cryptographic keys are generated as shown in <FIG> shows a plurality of public cryptographic key values and corresponding private cryptographic key values characterized into their respective first cryptographic component and the second cryptographic component. The different prime numbers 'p' and 'q' generate different pairs of private cryptographic key and public cryptographic key. Each of the public cryptographic key value and the private cryptographic key value is expressed into an associated first cryptographic component (where kpub is k's value for a public cryptographic key and kpriv is k's value for a private cryptographic key) and a second cryptographic component (where Rpub is a reminder value for a public cryptographic key and Rpriv is a reminder value for a private cryptographic key) by the cryptographic system <NUM>. Thereafter, the cryptographic system <NUM> identifies one or more the first cryptographic component for each of the plurality of public cryptographic keys and private cryptographic keys based on the second cryptographic component of each of the plurality of private cryptographic keys.

For instance, for the public cryptographic key value of <NUM>, the first cryptographic component is <NUM> and the second cryptographic component value is -<NUM>. Analogously, for the private cryptographic key value of <NUM>, the first cryptographic component is <NUM> and the second cryptographic component value is -<NUM>. Based on the second cryptographic component of the private cryptographic key i.e., -<NUM>, the cryptographic system <NUM> identifies the public cryptographic key value i.e., <NUM> and its components (the first cryptographic component i.e., <NUM> and the second cryptographic component i.e., -<NUM>) with the private cryptographic key value i.e., <NUM> and its components (the first cryptographic component i.e., <NUM> and the second cryptographic component i.e., -<NUM>). Similarly, based on the second cryptographic component of the private cryptographic key i.e., -<NUM>, the cryptographic system <NUM> identifies the public cryptographic key value i.e., <NUM> and its components (the first cryptographic component i.e., <NUM> and the second cryptographic component i.e., -<NUM>) with the private cryptographic key value i.e., <NUM> and its components (the first cryptographic component i.e., <NUM> and the second cryptographic component i.e., -<NUM>). Subsequently, the cryptographic system <NUM> creates at least one relationship matrix comprising the first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys. The at least one relationship matrix is created for each of the second cryptographic component of the private cryptographic keys based on predetermined rules. The predetermined rules comprise of (<NUM>) if the second cryptographic component (Rpriv) of a private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component (Rpub) of a public cryptographic key is +<NUM> or -<NUM> respectively, (<NUM>) if the second cryptographic component (Rpriv) of the private cryptographic key is -<NUM>, then the second cryptographic component (Rpub) of the public cryptographic key is -<NUM>, (<NUM>) if the second cryptographic component (Rpriv) of the private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component (Rpub) of the public cryptographic key is +<NUM> or -<NUM> respectively, and (<NUM>) if the second cryptographic component (Rpriv) of the private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component (Rpub) of the public cryptographic key is +<NUM> or -<NUM> respectively. Based on the above-mentioned predetermined rules, an example of a relationship matrix created by the cryptographic system <NUM> for the rule if the second cryptographic component (Rpriv) of a private cryptographic key is +<NUM>, then the second cryptographic component (Rpub) of a public cryptographic key is +<NUM> is shown in <FIG>. Analogously, the cryptographic system <NUM> creates a relationship matrix for each of the second cryptographic component (Rpriv) of the private cryptographic key equalling to "-<NUM>", "±<NUM>" and "±<NUM>". After creating the relationship matrix, the cryptographic system <NUM> stores the created relationship matrix in the ECU <NUM>.

Hereafter, the operation of the ECU <NUM> for retrieving public cryptographic is described. One example for which retrieval of public cryptographic is performed is when software associated with the ECU <NUM> requires an update.

The ECU <NUM> checks whether usage of a public cryptographic key is required or change in a public cryptographic key is required. When the usage of the public cryptographic key is required, the ECU <NUM> receives a first cryptographic component (kpriv) and a second cryptographic component (Rpriv) of a private cryptographic key from the cryptographic system <NUM> associated with the ECU <NUM>. Thereafter, the ECU <NUM> retrieves the public cryptographic key based on the first cryptographic component and the second cryptographic component of the private cryptographic key using the relationship matrix corresponding to the second cryptographic component of the private cryptographic key and the predetermined rules. For instance, suppose the ECU <NUM> receives a first cryptographic component (kpriv) as <NUM> and corresponding second cryptographic component (Rpriv) as <NUM> of a private cryptographic key. Using the stored relationship matrix shown in <FIG> for the second cryptographic component (Rpriv) of a private cryptographic key +<NUM>, the ECU <NUM> determines corresponding the first cryptographic component (kpub), which in this case is <NUM>. In this case, the ECU <NUM> uses first predetermined rule to determine the second cryptographic component (Rpub) of the public cryptographic key i.e., if the second cryptographic component (Rpriv) of a private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component (Rpub) of a public cryptographic key is +<NUM> or -<NUM> respectively. The ECU <NUM> retrieves the public cryptographic key using the expression <NUM>+<NUM>, which gives the public cryptographic key value as <NUM>. When the change in a public cryptographic key is required, the ECU <NUM> receives at least one new relationship matrix from the cryptographic system <NUM> associated with the ECU <NUM>. Thereafter, the ECU <NUM> updates the stored at least one relationship matrix with the at least new relationship matrix in the ECU <NUM>.

<FIG> shows a detailed block diagram of a system in accordance with some embodiments of the present disclosure.

The system <NUM> comprises of the cryptographic system <NUM> and the ECU <NUM> wherein the cryptographic system <NUM> is associated with the ECU <NUM>. The ECU <NUM> may, also, be referred as the ECU <NUM> shown in <FIG>.

The cryptographic system <NUM>, in addition to the I/O interface <NUM> and the processor <NUM> described above, may include data <NUM> and one or more modules <NUM>, which are described herein in detail. In the embodiment, the data <NUM> may be stored within the memory <NUM>. The data <NUM> may include, for example, relationship matrix data <NUM> and other data <NUM>.

The relationship matrix data <NUM> may include at least one relationship matrix created by the cryptographic system <NUM>. For instance, the relationship matrix shown in <FIG> may be stored in the relationship matrix data <NUM>. Similarly, a relationship matrix for each of the second cryptographic component equalling to "-<NUM>", "-<NUM>", "±<NUM>" and "±<NUM>" may be stored in the relationship matrix data <NUM>.

The other data <NUM> may store data, including temporary data and temporary files, generated by one or more modules <NUM> for performing the various functions of the cryptographic system <NUM>.

In the embodiment, the data <NUM> in the memory <NUM> are processed by the one or more modules <NUM> present within the memory <NUM> of the cryptographic system <NUM>. In the embodiment, the one or more modules <NUM> may be implemented as dedicated hardware units. As used herein, the term module refers to an Application Specific Integrated Circuit (ASIC), an electronic circuit, a Field-Programmable Gate Arrays (FPGA), Programmable System-on-Chip (PSoC), a combinational logic circuit, and/or other suitable components that provide the described functionality. In some implementations, the one or more modules <NUM> may be communicatively coupled to the processor <NUM> for performing one or more functions of the cryptographic system <NUM>. The said modules <NUM> when configured with the functionality defined in the present disclosure will result in a novel hardware.

In one implementation, the one or more modules <NUM> may include, but are not limited to, a generating module <NUM>, a characterizing module <NUM>, an identifying module <NUM>, and a creating module <NUM>. The one or more modules <NUM> may, also, include other modules <NUM> to perform various miscellaneous functionalities of the cryptographic system <NUM>.

The generating module <NUM> may generate a plurality of public cryptographic keys and private cryptographic keys using a cryptographic technique. The cryptographic technique may be a Rivest Shamir Adleman (RSA) technique. The plurality of public cryptographic keys and private cryptographic keys may be different prime numbers.

The characterizing module <NUM> may characterize each of the plurality of public cryptographic keys and corresponding private cryptographic keys into an associated first cryptographic component and a second cryptographic component. The first cryptographic component may a multiple of <NUM>, and the second cryptographic component may be a reminder of each of the plurality of public cryptographic keys and private cryptographic keys modulus <NUM>. For instance, each of public cryptographic keys and private cryptographic keys, which are different prime numbers, may be expressed as <NUM>*k ± <NUM>, <NUM>*k ± <NUM>, <NUM>*k ± <NUM>, or <NUM>*k ± <NUM>. Here, k ∈ (<NUM>, <NUM>, <NUM>, <NUM>. Here, the term 'k' may be referred as the first cryptographic component and the reminder i.e., ±<NUM>, ±<NUM>, ±<NUM>, or ±<NUM> may be referred as the second cryptographic component. An example of a public cryptographic key into the associated first cryptographic component (k's value) and the second cryptographic component (reminder value) is shown in <FIG>. Similarly, a private cryptographic key into the associated first cryptographic component (k's value) and the second cryptographic component (reminder value) may be expressed. The plurality of public cryptographic key values and its corresponding private cryptographic key values characterized into their respective first cryptographic component and the second cryptographic component is shown in <FIG>.

The identifying module <NUM> may identify one or more the first cryptographic component for each of the plurality of public cryptographic keys and private cryptographic keys based on the second cryptographic component of each of the plurality of private cryptographic keys. For example, with reference to <FIG>, for the public cryptographic key value of <NUM>, the first cryptographic component is <NUM> and the second cryptographic component value is -<NUM>. Analogously, for the private cryptographic key value of <NUM>, the first cryptographic component is <NUM> and the second cryptographic component value is -<NUM>. Based on the second cryptographic component of the private cryptographic key i.e., -<NUM>, the identifying module <NUM> of the cryptographic system <NUM> may identify the public cryptographic key value i.e., <NUM> and its components (the first cryptographic component i.e., <NUM> and the second cryptographic component i.e., -<NUM>) with the private cryptographic key value i.e., <NUM> and its components (the first cryptographic component i.e., <NUM> and the second cryptographic component i.e., -<NUM>) and sort the public cryptographic key value i.e., <NUM> and the private cryptographic key value i.e., <NUM> based on common second cryptographic component i.e., -<NUM>.

The creating module <NUM> may create at least one relationship matrix comprising first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys based on predetermined rules. An example of the relationship matrix created by the creating module <NUM> of the cryptographic system <NUM> for the rule if the second cryptographic component (Rpriv) of a private cryptographic key is +<NUM>, then the second cryptographic component (Rpub) of a public cryptographic key is +<NUM> is shown in <FIG>. Thereafter, the creating module <NUM> may store the created relationship matrix in the ECU <NUM>.

The ECU <NUM> may check whether usage of a public cryptographic key is required or change in a public cryptographic key is required. When the usage of a public cryptographic key is required, the ECU <NUM> may receive a first cryptographic component and a second cryptographic component of a private cryptographic key from the cryptographic system <NUM> associated with the ECU <NUM>. For instance, with reference to the <FIG>, suppose the ECU <NUM> receives a first cryptographic component (kpriv) as <NUM> and corresponding second cryptographic component (Rpriv) as <NUM> of a private cryptographic key. Using the stored relationship matrix shown in <FIG> for the second cryptographic component (Rpriv) of a private cryptographic key +<NUM>, the ECU <NUM> determines corresponding the first cryptographic component (kpub), which in this case is <NUM>. Thereafter, the ECU <NUM> may retrieve the public cryptographic key based on the first cryptographic component and the second cryptographic component of the private cryptographic key using the relationship matrix corresponding to the second cryptographic component of the private cryptographic key and the predetermined rules. For instance, the ECU <NUM> retrieves the public cryptographic key using the expression <NUM>*k + <NUM>, which gives the public cryptographic key value as <NUM>. When the change in a public cryptographic key is required the ECU <NUM> may receive at least one new relationship matrix from the cryptographic system <NUM> associated with the ECU <NUM>. Subsequently, the ECU <NUM> may update the stored at least one relationship matrix with the at least one new relationship matrix in the ECU <NUM>.

<FIG> illustrates a flowchart showing a method for retrieving public keys in a memory constrained system in accordance with some embodiments of present disclosure.

As illustrated in <FIG>, the method <NUM> includes one or more blocks for retrieving public keys in a memory constrained system. The method <NUM> may be described in the general context of computer executable instructions. Generally, computer executable instructions can include routines, programs, objects, components, data structures, procedures, modules, and functions, which perform particular functions or implement particular abstract data types.

The order in which the method <NUM> is described is not intended to be construed as a limitation, and any number of the described method blocks can be combined in any order to implement the method. Additionally, individual blocks may be deleted from the methods without departing from the scope of the subject matter described herein. Furthermore, the method can be implemented in any suitable hardware, software, firmware, or combination thereof.

At block <NUM>, the generating module <NUM> may generate a plurality of public cryptographic keys and private cryptographic keys using a cryptographic technique. The cryptographic technique may be a Rivest Shamir Adleman (RSA) technique. The plurality of public cryptographic keys and private cryptographic keys may be prime numbers.

At block <NUM>, the characterizing module <NUM> may characterize each of the plurality of public cryptographic keys and corresponding private cryptographic keys into an associated first cryptographic component and a second cryptographic component. The first cryptographic component may be a multiple of <NUM>. The second cryptographic component may be a reminder of each of the plurality of public cryptographic keys and private cryptographic keys modulus <NUM>.

At block <NUM>, the creating module <NUM> may create at least one relationship matrix comprising the first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys. The at least one relationship matrix is created for each of the second cryptographic component of the private cryptographic keys based on predetermined rules. The predetermined rules may comprise of (<NUM>) if the second cryptographic component of a private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component of a public cryptographic key is +<NUM> or -<NUM> respectively, (<NUM>) if the second cryptographic component of the private cryptographic key is -<NUM>, then the second cryptographic component of the public cryptographic key is -<NUM>, (<NUM>) if the second cryptographic component of the private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component of the public cryptographic key is +<NUM> or -<NUM> respectively, and (<NUM>) if the second cryptographic component of the private cryptographic key is +<NUM> or -<NUM>, then the second cryptographic component of the public cryptographic key is +<NUM> or -<NUM> respectively.

At block <NUM>, the ECU <NUM> of the vehicle associated with the cryptographic system <NUM> may receive a first cryptographic component and a second cryptographic component of a private cryptographic key from the cryptographic system <NUM> associated with the ECU <NUM> of the vehicle when the usage of a public cryptographic key is required.

At block <NUM>, the ECU <NUM> of the vehicle may retrieve the public cryptographic key based on the first cryptographic component and the second cryptographic component of the private cryptographic key using the relationship matrix corresponding to the second cryptographic component of the private cryptographic key and the predetermined rules.

Some of the technical advantages of the present disclosure are listed below.

<FIG> illustrates a block diagram of an exemplary computer system <NUM> for implementing embodiments consistent with the present disclosure. In an embodiment, the computer system <NUM> may be used to implement the cryptographic system <NUM>. The computer system <NUM> may include a central processing unit ("CPU" or "processor") <NUM>. The processor <NUM> may include at least one data processor for generating, storing and retrieving public keys in a memory constrained system. The processor <NUM> may include specialized processing units such as, integrated system (bus) controllers, memory management control units, floating point units, graphics processing units, digital signal processing units, etc..

The processor <NUM> may be disposed in communication with one or more input/output (I/O) devices (not shown) via I/O interface <NUM>. The I/O interface <NUM> employ communication protocols/methods such as, without limitation, audio, analog, digital, monoaural, Radio Corporation of America (RCA) connector, stereo, IEEE®-<NUM> high speed serial bus, serial bus, Universal Serial Bus (USB), infrared, Personal System/<NUM> (PS/<NUM>) port, Bayonet Neill-Concelman (BNC) connector, coaxial, component, composite, Digital Visual Interface (DVI), High-Definition Multimedia Interface (HDMI®), Radio Frequency (RF) antennas, S-Video, Video Graphics Array (VGA), IEEE® <NUM>. 11b/g/n/x, Bluetooth, cellular e.g., Code-Division Multiple Access (CDMA), High-Speed Packet Access (HSPA+), Global System for Mobile communications (GSM®), Long-Term Evolution (LTE®), Worldwide interoperability for Microwave access (WiMax®), or the like.

Using the I/O interface <NUM>, the computer system <NUM> may communicate with one or more I/O devices such as input devices <NUM> and output devices <NUM>. For example, the input devices <NUM> may be an antenna, keyboard, mouse, joystick, (infrared) remote control, camera, card reader, fax machine, dongle, biometric reader, microphone, touch screen, touchpad, trackball, stylus, scanner, storage device, transceiver, video device/source, etc. The output devices <NUM> may be a printer, fax machine, video display (e.g., Cathode Ray Tube (CRT), Liquid Crystal Display (LCD), Light-Emitting Diode (LED), plasma, Plasma Display Panel (PDP), Organic Light-Emitting Diode display (OLED) or the like), audio speaker, etc..

In some embodiments, the computer system <NUM> consists of the cryptographic system <NUM>. The processor <NUM> may be disposed in communication with the communication network <NUM> via a network interface <NUM>. The network interface <NUM> may communicate with the communication network <NUM>. The network interface <NUM> may employ connection protocols including, without limitation, direct connect, Ethernet (e.g., twisted pair <NUM>/<NUM>/<NUM> Base T), Transmission Control Protocol/Internet Protocol (TCP/IP), token ring, IEEE® <NUM>. 11a/b/g/n/x, etc. The communication network <NUM> may include, without limitation, a direct interconnection, Local Area Network (LAN), Wide Area Network (WAN), wireless network (e.g., using Wireless Application Protocol), the Internet, etc. Using the network interface <NUM> and the communication network <NUM>, the computer system <NUM> may communicate with an ECU <NUM> of a vehicle. The network interface <NUM> may employ connection protocols include, but not limited to, direct connect, Ethernet (e.g., twisted pair <NUM>/<NUM>/<NUM> Base T), Transmission Control Protocol/Internet Protocol (TCP/IP), token ring, IEEE® <NUM>. 11a/b/g/n/x, etc..

The communication network <NUM> includes, but is not limited to, a direct interconnection, a Peer to Peer (P2P) network, Local Area Network (LAN), Wide Area Network (WAN), wireless network (e.g., using Wireless Application Protocol), the Internet, Wi-Fi and such.

In some embodiments, the processor <NUM> may be disposed in communication with a memory <NUM> (e.g., RAM, ROM, etc. not shown in <FIG>) via a storage interface <NUM>. The storage interface <NUM> may connect to memory <NUM> including, without limitation, memory drives, removable disc drives, etc., employing connection protocols such as, Serial Advanced Technology Attachment (SATA), Integrated Drive Electronics (IDE), IEEE®-<NUM>, Universal Serial Bus (USB), fiber channel, Small Computer Systems Interface (SCSI), etc. The memory drives may further include a drum, magnetic disc drive, magneto-optical drive, optical drive, Redundant Array of Independent Discs (RAID), solid-state memory devices, solid-state drives, etc..

The memory <NUM> may store a collection of program or database components, including, without limitation, user interface <NUM>, an operating system <NUM>, etc. In some embodiments, computer system <NUM> may store user/application data, such as, the data, variables, records, etc., as described in this disclosure. Such databases may be implemented as fault-tolerant, relational, scalable, secure databases such as Oracle or Sybase.

The operating system <NUM> may facilitate resource management and operation of the computer system <NUM>. Examples of operating systems include, without limitation, APPLE® MACINTOSH® OS X®, UNIX®, UNIX-like system distributions (E. , BERKELEY SOFTWARE DISTRIBUTION® (BSD), FREEBSD®, NETBSD®, OPENBSD, etc.), LINUX® DISTRIBUTIONS (E. , RED HAT®, UBUNTU®, KUBUNTU®, etc.), IBM®OS/<NUM>®, MICROSOFT® WINDOWS® (XP®, VISTA®/<NUM>/<NUM>, <NUM> etc.), APPLE® IOS®, GOOGLE™ ANDROID™, BLACKBERRY® OS, or the like.

In some embodiments, the computer system <NUM> may implement web browser <NUM> stored program components. Web browser <NUM> may be a hypertext viewing application, such as MICROSOFT® INTERNET EXPLORER®, GOOGLE™ CHROME™, MOZILLA® FIREFOX®, APPLE® SAFARI®, etc. Secure web browsing may be provided using Secure Hypertext Transport Protocol (HTTPS), Secure Sockets Layer (SSL), Transport Layer Security (TLS), etc. Web browsers <NUM> may utilize facilities such as AJAX, DHTML, ADOBE® FLASH®, JAVASCRIPT®, JAVA®, Application Programming Interfaces (APIs), etc. The computer system <NUM> may implement a mail server (not shown in <FIG>) stored program component. The mail server may be an Internet mail server such as Microsoft Exchange, or the like. The mail server may utilize facilities such as ASP, ACTIVEX®, ANSI® C++/C#, MICROSOFT®,. NET, CGI SCRIPTS, JAVA®, JAVASCRIPT®, PERL®, PHP, PYTHON®, WEBOBJECTS®, etc. The mail server may utilize communication protocols such as Internet Message Access Protocol (IMAP), Messaging Application Programming Interface (MAPI), MICROSOFT® exchange, Post Office Protocol (POP), Simple Mail Transfer Protocol (SMTP), or the like. The computer system <NUM> may implement a mail client (not shown in <FIG>) stored program component. The mail client may be a mail viewing application, such as APPLE® MAIL, MICROSOFT® ENTOURAGE®, MICROSOFT® OUTLOOK®, MOZILLA® THUNDERBIRD®, etc..

Examples include Random Access Memory (RAM), Read-Only Memory (ROM), volatile memory, non-volatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.

The described operations may be implemented as a method, system or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The described operations may be implemented as code maintained in a "non-transitory computer readable medium", where a processor may read and execute the code from the computer readable medium. The processor is at least one of a microprocessor and a processor capable of processing and executing the queries. A non-transitory computer readable medium may include media such as magnetic storage medium (e.g., hard disk drives, floppy disks, tape, etc.), optical storage (CD-ROMs, DVDs, optical disks, etc.), volatile and non-volatile memory devices (e.g., EEPROMs, ROMs, PROMs, RAMs, DRAMs, SRAMs, Flash Memory, firmware, programmable logic, etc.), etc. Further, non-transitory computer-readable media include all computer-readable media except for a transitory. The code implementing the described operations may further be implemented in hardware logic (e.g., an integrated circuit chip, Programmable Gate Array (PGA), Application Specific Integrated Circuit (ASIC), etc.).

The terms "an embodiment", "embodiment", "embodiments", "the embodiment", "the embodiments", "one or more embodiments", "some embodiments", and "one embodiment" mean "one or more (but not all) embodiments of the invention(s)" unless expressly specified otherwise.

The terms "including", "comprising", "having" and variations thereof mean "including but not limited to", unless expressly specified otherwise.

The enumerated listing of items does not imply that any or all of the items are mutually exclusive, unless expressly specified otherwise.

The terms "a", "an" and "the" mean "one or more", unless expressly specified otherwise.

A description of an embodiment with several components in communication with each other does not imply that all such components are required. On the contrary, a variety of optional components are described to illustrate the wide variety of possible embodiments of the invention.

When a single device or article is described herein, it will be readily apparent that more than one device/article (whether or not they cooperate) may be used in place of a single device/article. Similarly, where more than one device or article is described herein (whether or not they cooperate), it will be readily apparent that a single device/article may be used in place of the more than one device or article or a different number of devices/articles may be used instead of the shown number of devices or programs. The functionality and/or the features of a device may be alternatively embodied by one or more other devices which are not explicitly described as having such functionality/features. Thus, other embodiments of the invention need not include the device itself.

The illustrated operations of <FIG> show certain events occurring in a certain order. In alternative embodiments, certain operations may be performed in a different order, modified or removed. Moreover, steps may be added to the above-described logic and still conform to the described embodiments. Further, operations described herein may occur sequentially or certain operations may be processed in parallel. Yet further, operations may be performed by a single processing unit or by distributed processing units.

Finally, the language used in the specification has been principally selected for readability and instructional purposes, and it may not have been selected to delineate or circumscribe the inventive subject matter. It is therefore intended that the scope of the invention be limited not by this detailed description, but rather by any claims that issue on an application based here on. Accordingly, the disclosure of the embodiments of the invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.

While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art. The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.

Claim 1:
A method (<NUM>) for retrieving public cryptographic keys in a memory constrained system (<NUM>), the method comprising:
Generating (<NUM>), by a cryptographic system (<NUM>), a plurality of public cryptographic keys and private cryptographic keys using a cryptographic technique;
Characterizing (<NUM>), by the cryptographic system, each of the plurality of public cryptographic keys and corresponding private cryptographic keys into an associated first cryptographic component and a second cryptographic component;
Creating (<NUM>), by the cryptographic system, at least one relationship matrix comprising the first cryptographic component of each of the plurality of public cryptographic keys and corresponding private cryptographic keys, wherein the at least one relationship matrix is created for each of the second cryptographic component of the private cryptographic keys based on predetermined rules;
Receiving (<NUM>), by an Electronic Control Unit, ECU, (<NUM>, <NUM>) of a vehicle associated with the cryptographic system, a first cryptographic component and a second cryptographic component of a private cryptographic key from the cryptographic system when a public cryptographic key is required; and
Retrieving (<NUM>), by the ECU of the vehicle, the public cryptographic key based on the first cryptographic component and the second cryptographic component of the private cryptographic key using the relationship matrix corresponding to the second cryptographic component of the private cryptographic key and the predetermined rules, thereby, minimizing memory required for storing the plurality of public cryptographic keys and private cryptographic keys.