Patent ID: 12231562

DETAILED DESCRIPTION

Aspects of the present disclosure are directed to improving efficiency and security of cryptographic operations. More specifically, aspects of the present disclosure are directed to optimization of processor and memory utilization and to improving protection of cryptographic computations against power analysis attacks.

FIG.1illustrates an example network architecture100in which various implementation of the present disclosure may operate. In public-key cryptography systems, computing devices may have various components/modules used for cryptographic operations on output or input messages. Computing devices may include a receiving device102that establishes a private key108and a public key109and provides the public key109to a sending device110, which uses the public key109to encrypt a message112before sending the encrypted message (ciphertext) to receiving device102over a public communication channel118. Cryptographic algorithms often involve modular arithmetic operations with modulus N (mod N operations) in which the set of all integers Z is wrapped around a circle of length N (the set ZN), with any two numbers that differ by N (or by any integer multiple of N) treated as representing the same number (e.g., 16=5 mod 11 and 122=1 mod 11). Input messages used in such operations are often large binary numbers whose processing can be computationally expensive, in particular, when division operations are executed. Because cryptographic operations are often performed on devices having modest computational capabilities (e.g., microprocessors, smart card readers, wireless sensor nodes, etc.), it is important to optimize utilization of hardware (e.g., processor and memory) resources in such operations.

Examples of cryptographic applications that employ asymmetric public key/private key cryptography include Diffie-Hellman (DH) key exchanges, digital signature algorithms (DSA) to authenticate transmitted messages, various elliptic curve cryptography schemes, Rivest-Shamir-Adelman (RSA) public key/private key applications, and the like. For example, a cryptographic application (of an intended recipient of an encoded message) may perform private/public key generation106by selecting two (or more) large prime numbers, e.g., p and q, adopting a public exponent e (often e=3, 17, or 216+1) and computing a secret (decryption) exponent d based on the public (encryption) exponent e and the selected numbers p and q. The numbers e and N=p·q are revealed as part of the public key109whereas p, q, and d are stored in secret by the recipient as parts of the private key108. A sender of message m112may convert (block114) the message into a ciphertext using modular exponentiation, c=memod N, and send the encrypted ciphertext c over the public communication channel118. The recipient of the ciphertext may then decipher the ciphertext by applying another modular exponentiation, m=cdmod N, provided that the value of the decryption exponent d is selected is such a way that e·d=1 mod N*, where N*=(p−1)·(q−1) (Euler's totient function). Alternatively, as often used, N* may be taken as the least common multiplier of p−1 and q−1 (Carmichael's totient function). Because recovering the private exponent d requires factorizing a large public number N into its prime number multipliers p and q—a prohibitively-heavy computational task for large N—the encrypted message m remains safe even if its ciphertext c becomes known to others.

Instead of directly computing cdmod N, it is more economical to determine it from two related values cp=cdmod p and cq=cdmod q. For example, from the second condition it follows that cd=j·q+cq, with some integer j. From the first condition, written as j·q+cq=cpmod p, it then follows that the integer j is j=(cp−cq)·(q−1mod p) mod p resulting in the following representation (herein referred to as “asymmetric representation”) for the decrypted message, known as the Chinese remainder theorem:
m=cdmodN=q·[(cp−cq)·(q−1modp) modp]+cq.

The values cpand cqmay be computed efficiently by using exponentiation to reduced powers dp=d mod (p−1) and dq=d mod (q−1) as follows:
cp=cdpmodp, cq=cdqmodq,
as a consequence of Fermat's little theorem, cp−1=1 mod p (for any p) and the fact that d can be represented via d=k(p−1)+d mod (p−), with some integer k.

Alternatively, in some applications, an equivalent representation (herein referred to as “symmetric representation”) for the decrypted message may be computed:
m≡cdmodN=q·(cp·q−1modp)+p·(cq·p−1modq) modN,
which can be verified to yield the correct identity, cdmod p=cp, since [p·(cq·p−1mod q)] mod p=0 (and similarly for cq).

Decryption that uses the symmetric or the asymmetric representation involves computing at least one inverse value q−1mod p (and, possibly, p−1mod q, if the symmetric representation is used). Because inverse operations are computationally expensive, any such inverse values may be precomputed and stored for future use during decryption. Precomputation may be performed as part of private/public key generation106. For example, key generation may include selecting prime numbers p and q, choosing a public exponent e, computing d, and determining values dp, dq, q−1mod p (and, possibly, p−1mod q), and storing the selected and determined values as part of the private key108.

Aspects and implementations of the present disclosure address the inefficiencies of storing (or generating, during the decryption process) of the inverse value q−1mod p (and/or p−1mod q) by disclosing a method of performing decryption operations in cryptographic applications that avoid storing (or computing) the inverse values. Advantages of the disclosed implementations include, but are not limited to, more optimal utilization of processor and/or memory resources of one or more computing devices that perform decryption. In particular, disclosed is inverse-free decryption120that avoids computing q−1mod p and/or p−1mod q. Also disclosed are implementations that enable randomization protection122of computational operations against side-channel attacks used by an adversarial attacker attempting to access secret information (e.g., private key). Additionally, disclosed are implementations that enable fast prime number generation104that may be used for private/public key generation106and for efficient decryption of encrypted messages.

In some disclosed implementations, after the receiving device102has obtained an encrypted ciphertext c, a processor of the receiving device102may access stored values p, q, dp, dq(but not q−1mod p or p−1mod q) and compute a first intermediate value αpby multiplying ciphertext c by a first power of number q, such as
αp=c·qe−1modp.
Although, in the exemplary implementation, the first power is chosen as e−1, numerous other exponents may be used instead, as explained in more detail below. Additionally, the processing device may compute a second intermediate value βp, by rescaling the first intermediate value αpby an additional power of number q and computing a second power of the rescaled first intermediate value:
βp=(αp·q)dp−2modp.
Although, in the exemplary implementation, the chosen second power is dp−2, numerous other exponents can be used instead, as explained in more detail below. The processing device may now compute a first combined value
γp=αp2·βp=cdp·q−1modp=cp·q−1modp.
which combines the first intermediate value cdpwith the inverse q−1mod p. The proof of the last formula involves Fermat's little theorem, which posits that cedp=ced·c−k(p−1)=1 mod p and, therefore,
αp2·βp≡(c·qe−1)2·(c·qe)dp−2≡cdp·qedp−2≡cdp·q−1modp.
As a result, the first combined value γpis determined with no inverse numbers computed, thus reducing processing and/or memory computations costs. A second set of similar computations may be carried out for the second number q, e.g., with intermediate values αq=c·pe−1mod q and βq=(αq·p)dp−2mod q used to compute the second combined value γq=p−1mod q. In the symmetric representation, the received message can now be decrypted using a pair of multiplications as follows:
m=q·γp+p·γqmodN.
The terms “first power,” “second power,” etc., should be understood throughout this disclosure to indicate exponents that can be any numbers and should not be narrowly construed to only mean “power one,” “power two,” and so on. Some or all modular multiplications described in the present disclosure may be performed using Montgomery multiplication methods, including Montgomery reduction.

The described method of replacing computation of inverse values with products and positive powers may be performed using various additional realizations. In one implementation, the method can be performed using a different set of exponents, for example:
αp=c·qe−2modp, βp=(αp·q2)dp−1modp, γp=αp·βpmodp,
(and analogously for αq, βq, and γq) with the decrypted message still provided by m=q·γp+p·γqmod N.

In another implementation, the method can compute the number γp(and similarly, the number γq) using a different set of intermediate values of αpand βp, such as:
αp=(c·q)e−1modp, βp=(αp·q)p−1−2pmodp, γp=βp·cmodp.
Because the decryption exponent dpis defined modulo p−1, the difference p−1−dpis non-negative, so the computations do not require performing division operations. Specifically, the computations lead to the same result as other implementations disclosed above, since
γp≡((c·q)e−1·q)p−1−dp·c≡(ce−1·qe)p−1·(ce−1·qe)−dp·c≡cdp·q−1modp,
as, per Fermat's little theorem, (ce−1·qe)p−1mod p=1 and edp mod p=1.

In some implementations, the method can be performed with the first intermediate value αpobtained by multiplying the ciphertext c by a power of q that is different from either e−1 or e−2, for example:
αp=c·qe−nmodp, ≢p=(αp·qn)dp−smodp, γp=αps·βp.
(and analogously for αq, βq, and γq) and with message decrypted using multiplication of the combined values by appropriately selected powers of the respective prime numbers:
m=q·(γp·qns−2modp)+p·(γq·pns−2modq) modN.

In some implementations, the value of N is computed as a product of more than two prime numbers, e.g., p, q, s, etc. In such implementations, the intermediate values may be computed similarly to various methods described above, enabling to replace inverse values by products and positive powers. In particular, in implementations that use N=p·q·s, the intermediate values can be computed as follows,
αp=(c·q·s)e−1modp, βp=(αp·q·s)p−1−dpmodp, γp=βp·cmodp
and analogously for the combined values γqand γs. Using the computed combined values, the decrypted message can be determined according to:
m=γp·q·s+γq·p·s+γs·p·qmodN

In some implementations, the value of N is computed as a product of one prime number by a power of another prime number, or as a product of several powers of several prime numbers, for example N=pk·q. In such implementations, the intermediate value γpk=m·q−1mod pkmay be computed by treating γpkas a solution to the equation (γpk·q)e≡c mod pk. The solution may be computed by solving the equation modulo p and lifting the result to a solution mod pkusing Hensel's lemma or an analogous process. For example, the Hensel lifting process computes
γpi+1=γpi+δ·(c−(γpi·q)e) modpi+1,
where δ=(qe℠γp1e−1·e)−1mod p is the inverse of the derivative of the equation at γp1. The value of δ may be determined (e.g., in parallel to the value γp1) by computing:
α=(e·c·q)e−1modp, δ=α2·(e·q·α)p−1−dmodp, γp1δ·e·cmodp.

Optimization of decryption operations described above can be combined with randomization (blinding) of computations to protect against power analysis attacks. Even though factorization of a large number N may be a prohibitively difficult task, decryption operations may be vulnerable to side-channel attacks. A side-channel attack may be performed by monitoring emissions (signals) produced by electronic circuits of the target's (e.g., victim's) computer. Such signals may be acoustic, electromagnetic, optical, thermal, and so on. By recording emissions, a hardware troj an and/or malicious software may be capable of correlating specific processor (and/or memory) activity with operations carried out by the processor. For example, an attacker employing a troj an may be able to detect emissions corresponding to multiple decryption operations where different known ciphertexts are decrypted with the same private key. As a result, by analyzing (e.g., using methods of statistical analysis) hardware emissions of the processing device, the attacker may be able to determine the private key.

Aspects of the present disclosure enable protection of cryptographic operations by implementing intermediate randomization that does not change the ultimate outcome of the computation (e.g., the value of the decrypted message m) but decreases the amount of correlations between different instances of decryption. For example, one or more random numbers can be used to make results of intermediate computations less predictable even when the same ciphertext is being decrypted. Such randomized protective measures improve security of cryptographic operations by making it more difficult for side-channel attackers to correlate signals emitted by the processing device. In some implementations, during computation of the first combined value γp, the processing device can select (e.g., generate or pick from a previously generated list) a random number rpand rescale the number q by the selected random number rpduring computation of the first intermediate number:
αp=c·(rp·q)e−1modp.
The similar rescaling is performed during the computation of the second intermediate value:
β=(αp·rp·q)dp−2modp.
The first combined value now has the extra multiplier of rp−1mod p:
γp=cp·rp−1·q−1modp,
The extra multiplier can be compensated with multiplication by rpduring the final determination of the message m. Likewise, a random number rqcan be used during computation of the second combined value γq, using the same expressions as above, in which the replacement p↔q is made. The message being decrypted can now be determined using,
m=(rp·q·γpmodp)+(rq·p·γqmodq) modN
In some implementations, the two random numbers can be selected equal, rp=rq=r. In this case, the message can be decrypted using,
m=r·((q·γpmodp)+(p·γqmodq)) modN
In this way, all calculations modulo either p or q may be protected by the randomized blinding method.

Similarly, the randomization can be performed with any other powers, e.g.,
αp=c·(rp·q)e−nmodp, βp=(αp·(rp·q)n)dp−2modp, γp=αps·βp,
(and analogously for αq, βq, and γq) and with message decrypted using multiplication of the combined values by appropriately selected powers of the respective prime numbers:
m=rp·q·((rp·q)ns−·γpmodp)+rq·p·((rq·p)ns−2γqmodq) modN.

Likewise, the randomization can also be performed in implementations that use exponentiation to the power p−1−dp. More specifically (and similarly for αq, βq, and βq):
αp=(c·rp·q)e−1modp, βp=(αp·rp·q)p−1−dpmodp, γp=βp·cmodp.
The decrypted message can then be computed in the same way as above:
m=(rp·q·γpmodp)+(rq·p·γqmodq) modN

FIG.2is a block diagram illustrating an example computer system200in which various implementations of the present disclosure may operate. The example computer system200may be a desktop computer, a tablet, a smartphone, a server (local or remote), a thin/lean client, and the like. The example computer system200may be a smart a card reader, a wireless sensor node, an embedded system dedicated to one or more specific applications (e.g., cryptographic applications210), and so on. The example computer system200may include, but not be limited to, a computer device202having one or more processors220(e.g., central processing units (CPUs)) capable of executing binary instructions, and one or more system memory230devices. “Processor” refers to a device capable of executing instructions encoding arithmetic, logical, or I/O operations. In one illustrative example, a processor may follow Von Neumann architectural model and may include an arithmetic logic unit (ALU), a control unit, and a plurality of registers.

The computer device202may further include an input/output (I/0) interface204to facilitate connection of the computer device202to peripheral hardware devices206such as card readers, terminals, printers, scanners, internet-of-things devices, and the like. The computer device202may further include a network interface208to facilitate connection to a variety of networks (Internet, wireless local area networks (WLAN), personal area networks (PAN), public networks, private networks, etc.), and may include a radio front end module and other devices (amplifiers, digital-to-analog and analog-to-digital converters, dedicated logic units, etc.) to implement data transfer to/from the computer device202. Various hardware components of the computer device202may be connected via a bus212which may have its own logic circuits, e.g., a bus interface logic unit.

The computer device202may support one or more cryptographic applications210, such as an embedded cryptographic application210-1and/or external cryptographic application210-2. The cryptographic applications210may be secure authentication applications, encrypting applications, decrypting applications, secure storage applications, and so on. The external cryptographic application210-2may be instantiated on the same computer device202, e.g., by an operating system executed by the processor220and residing in the system memory230. Alternatively, the external cryptographic application210-2may be instantiated by a guest operating system supported by a virtual machine monitor (hypervisor) executed by the processor220. In some implementations, the external cryptographic application210-2may reside on a remote access client device or a remote server (not shown), with the computer device202providing cryptographic support for the client device and/or the remote server.

The processor220may include one or more processor cores having access to a single or multi-level cache and one or more hardware registers. In implementations, each processor core may execute instructions to run a number of hardware threads, also known as logical processors. Various logical processors (or processor cores) may be assigned to one or more cryptographic applications210, although more than one processor core (or a logical processor) may be assigned to a single cryptographic application for parallel processing. A multi-core processor220may simultaneously execute multiple instructions. A single core processor220may typically execute one instruction at a time (or process a single pipeline of instructions). The processor220may be implemented as a single integrated circuit, two or more integrated circuits, or may be a component of a multi-chip module.

The system memory230may refer to a volatile or non-volatile memory and may include a read-only memory (ROM)232, a random-access memory (RAM)234, as well as (not shown) electrically erasable programmable read-only memory (EEPROM), flash memory, flip-flop memory, or any other device capable of storing data. The RAM234may be a dynamic random-access memory (DRAM), synchronous DRAM (SDRAM), a static memory, such as static random-access memory (SRAM), and the like.

The system memory230may include one or more registers236to store a cryptographic key and intermediate values during the decryption operations (e.g., p, q, αp, βp, rp, γp, etc.). In some implementations, registers236may be implemented as part of RAM234. In some implementations, some or all of registers236may be implemented separately from RAM234. Some or all of registers236may be implemented as part of the hardware registers of the processor220. In some implementations, the processor220and the system memory230may be implemented as a single field-programmable gate array (FPGA).

The computer device202may include a fast prime number generation104module to assist in key generation and may further include an inverse-free decryption120module for optimization of use of processor220and system memory230resources during message decryption, in accordance with implementations of the present disclosure. The fast prime number generation104and the inverse-free decryption120may be implemented in software, hardware (e.g., as part of the processor220), firmware, or in any combination thereof. In some implementations, the fast prime number generation104and the inverse-free decryption120may access the contents of registers236to retrieve and store data used and generated during respective operations.

FIG.3depicts a flow diagram of an illustrative example of method300of optimization of decryption operations by avoiding computations of inverse values, in accordance with one or more aspects of the present disclosure. Method300and/or each of its individual functions, routines, subroutines, or operations may be performed by one or more processing units of the computing system implementing the method. In certain implementations, method300may be performed by a single processing thread. Alternatively, method300may be performed by two or more processing threads, each thread executing one or more individual functions, routines, subroutines, or operations of the method. In an illustrative example, the processing threads implementing method300may be synchronized (e.g., using semaphores, critical sections, and/or other thread synchronization mechanisms). Alternatively, the processing threads implementing method300may be executed asynchronously with respect to each other. Various operations of method300may be performed in a different order compared with the order shown inFIG.3. Some blocks may be performed concurrently with other blocks. Some blocks may be optional. Some or all of the block of method300may be performed by inverse-free decryption120module.

Method300may be implemented by processor220(or an arithmetic logic unit, an FPGA, and the like, or any processing logic, hardware or software or a combination thereof) performing a cryptographic operation, which may be based on a private key that includes a first prime number (q) and a second prime number (p). In some implementations, the private key may include three or more prime numbers. At least some operations of method300may be modular arithmetic operations, e.g., mod q, mod p, mod pq operations, and the like. Some or all such modular multiplications may be performed using Montgomery reduction.

Method300may involve receiving a number c corresponding to an encrypted message (ciphertext) from sending device110. At block310, method300may involve obtaining, by a processing device, a first intermediate value (e.g., αp) based on the number c corresponding to an encrypted message and a first number related to the first prime number. In some implementations, obtaining the first intermediate value (e.g., αp) may include multiplying the number c corresponding to the encrypted message by a first power of a first number related to the first prime number q, e.g., c·qe−n. In some implementations, obtaining the first intermediate value (e.g., αp) may include exponentiating, to the first power, a product of the number corresponding to the encrypted message c and the first number related to the first prime number, e.g. computing (c·q)e−1.

In some implementations, the first number related to the first prime number may be the first prime number q itself. In some implementations (as indicated by an optional block312), the first number related to the first prime number may be a number derived from the first prime number q. For example, the first number related to the first prime number may be obtained using multiplication of the first prime number q by a random number r: q·r. The first intermediate value αpmay be obtained by multiplying the number c corresponding to the encrypted message by a first power of the first number related to the first prime number. For example, the first intermediate value αpmay be one of cqe−1, cqe−2, c(q·r)e−1, c(q·r)e−2, c(q·r)e−n, and so on, wherein the first power (e.g., e−n) may be determined in view of an encryption exponent e for the cryptographic operation.

At block320, method300may continue with the processing device obtaining a second intermediate value (e.g., βp) by computing a second power of a third intermediate value. In some implementations, the third intermediate value may be determined in view of the first prime number q, e.g., the third intermediate value may be αpq, αpq2, αpqn, etc. The second power (e.g., dp−1, dp−2, dp−s, etc.) may be determined in view of a first decryption exponent dp. Accordingly, the second intermediate value may be βp=(αpq)dp−2, (αpq2)dp−1(αpqn)dp−2, etc. The second power may be chosen in conjunction with the first power. In some implementations, the first power is the encryption exponent reduced (decremented) by one, e−1, and the second power is the first decryption exponent reduced by two, dp−2. In some implementations, the first power is the encryption exponent reduced by two, e −2, and the second power is the first decryption exponent reduced by one, dp−1. In some implementations, the second power is equal to a decremented difference of the first prime number and the first decryption exponent (e.g., p−1−dp). In such implementations, the third intermediate value may include a product of the first prime number and the first number related to the first prime number e.g., αp·q. Accordingly, the second intermediate value may be (αp·q)p−1−dp.

In some implementations, the third intermediate value may be determined (optional block322) in further view of the random number r, e.g., as αp(q·r), αp(q·r)2, αp(q·r)n, etc. Accordingly, the second intermediate value may be βp=(αpq·r)dp−2, (αp(q·r)2)dp−1, (αp(q·r)n)dp−s, etc.

At block330, method300may continue with the processing device determining a decrypted message using the first intermediate value (e.g., αp) and the second intermediate value (e.g., βp). More specifically, in some implementations, at block332, the processing device may determine a first combined value (e.g., γp) by multiplying the second intermediate value (e.g., βp) by the first intermediate value (e.g., αp), e.g., γp=αpβp, or by a third power (e.g., power 2, s, etc.) of the first intermediate value, e.g., γp=αp2βp, αpsβp, etc. At block334, the processing device may multiply the first combined value (e.g., γp) by the first prime number q. In some implementations, the processing device may multiply the first combined value (e.g., γp) by a fourth (e.g., ns−1) power of the first prime number q, for example: γp·qns−1.

In some implementations, blocks310-334may be repeated (e.g., in parallel or sequentially) for a second prime number p with the operations differing from the operations described above in conjunction with blocks310-334by the replacement q↔p. More specifically, in conjunction with another instance of block310, a fourth intermediate value (e.g., αq) may be obtained by multiplying the number (e.g., c) corresponding to the encrypted message by the first power of a second number related to the second prime number. The second number related to the second prime number may be the second prime number p itself or the second prime number may be a number derived from the second prime number p. In some implementations, the second number related to the second prime number may be obtained using multiplication of the second prime number p by a random number r: p·r. (The random number may be the same as or different than the random number used for blinding the first prime number.) The fourth intermediate value may be obtained by multiplying the number c corresponding to the encrypted message by the first power of the second number related to the second prime number. For example, the fourth intermediate value may be one of cpe−1, cpe−2, c(p·r)e−1, c(p·r)e−2,c(p·r)e−n, and so on.

In conjunction with another instance of block320, a fifth intermediate value (e.g., βq) may be computed as a fifth power of a sixth intermediate value. In some implementations, the sixth intermediate value may be determined in view of the second prime number p. For example, the sixth intermediate value may be αqp, αqp2, αqpn, etc. The fifth power (e.g., dq−1, dq−2, dq−s, etc.) may be determined in view of a second decryption exponent dq. Accordingly, the fifth intermediate value may be βq=(αqp)dq−2, (αqp2)dq−1, (αqpn)dq−s, etc. The fifth power may be chosen in conjunction with the first power. In some implementations, the first power is the encryption exponent reduced by one e−1 and the fifth power is the second decryption exponent reduced by two, dq−2. In some implementations, the first power is the encryption exponent reduced by two, e−2, and the fifth power is the second decryption exponent reduced by one, dq−1. The sixth intermediate value may be determined in further view of the random number r, e.g., as αq(p·r), αq(p·r)2, αq(p·r)n, etc. Accordingly, the fifth intermediate value may be βq=(αqp·r)dq−2, (αq(p·r)2)dq−1, (αq_l (p·r)n)dq−s, etc.

In conjunction with another instance of block330, method300may continue with the processing device determining a decrypted message using the fourth intermediate value (e.g., αq) and the fifth intermediate value (e.g., (βq). More specifically, the processing device may determine a second combined value (e.g., γq) by multiplying the fifth intermediate value (e.g., βq) by the fourth intermediate value (e.g., αq), e.g., γq=αqβq, or by the third power (e.g., power 2, s, etc.) of the fourth intermediate value, e.g., γq=αq2βq, αq2βqetc. In conjunction with another instance of block334, the processing device may multiply the second combined value (e.g., γq) by the second prime number p. In some implementations, the processing device may multiply the second combined value (e.g., γq) by the forth (e.g., ns−1) power of the second prime number p, e.g., γq·pns−1.

At block336, method300may continue with multiplying a number based on the first combined value by the random number. The number based on the first combined value may additionally be based on the second combined value, e.g., q·γp+p·γq, and upon multiplication (modulo pq) determine the decrypted message m=r·(q·γp+p·γq) or m=rns−1·(q·γp+p·γq) In some implementations, the first combined value and the second combined value can be first multiplied by the random number and then added together, e.g., m=rns−1·(qns−1·γp)+rns−1·(pns−1γq). In particular, multiplication followed by addition may be performed when different random numbers are used for blinding: m=r1ns−1·(qns−1·γp)+r2ns−1·(pns−1·γq).

Prime numbers (e.g., p and q) used in cryptographic applications (e.g., employing the Rivest-Shamir-Adleman key exchange, the Diffie-Hellman key exchange, the Digital Signature algorithms, elliptic curve applications, and the like) may be generated based on any known methods, such as Atkin-Bernstein sieve, sieve of Eratosthenes, Joye-Paillier method, or the like. Candidate prime numbers can be tested for primality using any known tests, such as the Pocklington primality test, the Baillie-Pomerance-Selfridge-Wagstaff primality test, the Miller-Rabin primality test, or the like. Existing methods of generating primes, however, suffer from a number of shortcomings. For example, generating random numbers and testing for primality provides a rather low yield of prime numbers, as it may take about 700 tries on average to identify one 1024-bit prime number. Algorithms that deterministically search for prime numbers based on failed attempts may be capable of finding prime numbers faster, but may be vulnerable to power analysis attacks, such as simple power analysis (SPA) attacks, differential power analysis (DPA) attacks, and so on. A side-channel attacker intercepting hardware emissions may be capable of acquiring additional information with each iteration of the generating algorithm until the attacker becomes capable of ascertaining what candidate numbers are being tested, leading to a potential exposure of the eventual identified prime numbers.

Disclosed herein are fast and efficient methods of generating prime numbers that have enhanced resistance to power analysis attacks. Disclosed implementations are described in reference toFIG.4that depicts schematically an example sequence of operations during efficient generation of prime numbers and use of the generated prime numbers in cryptographic application. Disclosed implementations may involve employing polynomial functions for generation of candidate prime numbers. In some implementations, the polynomial functions may be operating on input numbers classified by their residue (e.g., quadratic residue) properties. A quadratic residue Y modulo a number P is a number that is congruent to (different by a multiple of P from) a square of some number Z: Y=Z2mod P. Conversely, a quadratic nonresidue (QNR) Y modulo P is a number that is not congruent, Y≠X2mod P to a square of any number X. Accordingly, selecting a number −u such that −u≠X2mod P (QNR modulo P) for any number X enables to construct the quadratic polynomial X2+u whose value for any number X is not divisible by P (since by construction X2+u≠0 mod P).

For a set of numbers {Pi}, selecting a number u (block410) such that −u≠X2mod Pifor any number X and for all numbers Pjof the set ensures that the polynomial X2+u is not divisible by any number Piof the set {Pi}. Based on this property, in some implementations, the set of numbers {Pi} may be chosen to include some (or all) prime numbers up to a target number (e.g., the first 50 prime numbers, the first 100 prime numbers, and so on): {Pi}=3, 5, 7, 11, 13, 17, 19, 23 . . . In some implementations, the set of numbers {Pi} may be different from the first m prime numbers, as some prime numbers (e.g., 2, in this example) may be excluded while some additional (e.g., larger prime) numbers may be included, and so on. Therefore, selecting an arbitrary number X modulo M=ΠjPjensures that the number F(X)=X2+u is not divisible by any of Pi. This increases the likelihood that F(X)=X2+u is a prime number, compared with a random selection of potential candidates. The use of one or more such polynomials, therefore, speeds up successful prime number generation. Other polynomials may be used for generation of candidate numbers (herein also, “candidates”). For example, since by construction, for all X it holds that −u≠X−2mod Pi, the polynomial G(X)=u·X2+1 is likewise not divisible by any of Pi. Therefore, the polynomial function G(X) can be used in place of the function F(X) (or together with the function F(X), as explained in more detail below). Compared with the function F(X), the polynomial function G(X) includes one additional multiplication, which in many instances may be an acceptable increase of the involved computational time. Other polynomials can be used as well, e.g., polynomials that have no roots modulo any Piof the set {Pi}, e.g., a general quadratic polynomial G(X)=s·X2+t·X+u provided that s·X2+t·X+u≠0 mod Pifor any X, which upon multiplication by 4s and rearrangement in the form (2s·X+t)2−t2+4s·u≠0 mod Pi, requires that the number t2−4s·u is QNR for all Pi.

Various algorithms may be used to identify numbers −u that are QNR for a set of {Pi} numbers. Approximately a half of all numbers are QNR modulo each Pi, with another half being QR. Various tests can be used to determine whether a number uiis a QR or QNR modulo Pi, such as randomly choosing uiwithin interval [2,Pi−1], calculating ui(Pi−1)/2mod Pi, using quadratic reciprocity, and so on. Once a value for uihas been determined modulo each prime or prime-power Pi, a value of u may be calculated using Chinese Remainder Theorem. Various QNR −u can be precomputed and stored, e.g., in a QNR list in a read-only memory of the processing device that generates prime numbers. A number −u may be selected (e.g., randomly) from the stored QNR list and used to form one of the polynomials F(x), G(x), H(x), and the like. At block420, a number X may then be selected (e.g., randomly, in some implementations), and at block430a candidate number Z=F(X) mod M=(X2+u) mod M may be generated where M may be a product of the set {Pi}: M=ΠiPi. One of primality tests may then be applied (block435) to the candidate Z. In case the candidate Z fails a primality test, another number X may be selected (e.g., also randomly) and the process repeated until a successful prime number Z is obtained.

The number M may serve as the upper number for the candidates (and, therefore, generated primes) and may be selected based on a target size of the desired key. The numbers X used as input into the polynomial function(s) may be selected uniformly from a range [0,Xmax−1], which may be the same or different (e.g., smaller or larger) than the range [0,M−1]. The numbers X may be selected uniformly from the range of X, e.g., with equal likelihood to be selected within different sub-ranges of X. Because QR/QNR are not distributed uniformly, the candidate outputs Z may be distributed with a degree of non-uniformity within the range [0,M−1]. In some implementations, to ensure the uniformity of candidate outputs Z, additional instances of polynomials may be used.

In some implementations, at block420, a set of numbers (e.g., random numbers) {Xj} may be generated (e.g., uniformly within the range of X) instead of a single value X. The candidate number may be generated (at block430) using a product of n instances (the n-product) of the polynomials:

Z=∏j=1n⁢(Xj2+u)⁢mod⁢⁢M,⁢orZ=∏j=1n⁢(u·Xj2+1)⁢mod⁢⁢M.
With increasing n, the degree of uniformity of the candidate outputs Z increases. For a product of n=5 polynomials, the degree of uniformity is characterized by losses of approximately 0.055 bits of entropy for each generated prime number, or approximately 0.11 bits of for each pair of cryptographic primes p and q. With the further increase of the number of polynomial instances n, additional incremental improvements in uniformity may be achieved, but in many cryptographic applications it may be sufficient (for adequate protection against side-channel attacks) to implements n=5 or n=6 instances of polynomial functions. For increased uniformity (and protection), any higher number n>6 may be used. The enhanced uniformity of outputs may be weighed against increased amount of computations associated with additional multiplications and operations used to generate additional Xj. In some implementations, any other polynomials G(x), H(x), and the like, may be used in the product of the polynomials. In some implementations, all polynomial instances j may involve the same polynomial function. In some implementations, some polynomial instances, e.g., j=1, 2, 3, may involve a first kind of a polynomial (e.g., F(x)) whereas other polynomial instances, e.g., j=4, 5, 6, may involve a second kind of a polynomial (e.g., G(x)).

Operations that are performed to generate a candidate number (for a given number of polynomial instances n) include 2n−1 multiplications and n additions when polynomials F(x) are used, or 3n−1 multiplications and n additions when polynomials G(x) are used. When a computed candidate number Z is an even number, an odd number may be added before the primality testing is performed, for example, M, or any other predetermined number. In some implementations, the n-product may be modified to output an odd number, e.g., using a modulo 2M arithmetic operation:

Z=∏j=1n⁢(2·(Xj2+u)+M)⁢mod⁢⁢2⁢M,⁢orZ=∏j=1n⁢(2·(Xj2·u+1)+M)⁢mod⁢⁢2⁢M.
Other variations of these expressions may be used to ensure that the candidate Z is a number that is both odd and 2 mod 3 (a number 1 less than a multiple of 3), which may be useful when the public exponent e=3. Similarly, it may be ensured that the candidate Z is 3 mod 4 (a number 1 less than a multiple of 4), or that Z is k mod n, e.g.,

Z=∏i=1n⁢(n·(Xi2+n)+(k·M-1⁢mod⁢⁢N)⁢M)⁢⁢mod⁢⁢nM.
As should be recognized by a person skilled in this technology, numerous other similar polynomial product-based expressions can be used to generate prime number candidates that satisfy various additional target conditions, by adjusting the form of the polynomials or the modular operations.

When a computed candidate number Z is determined not to be a prime number, a different set of input numbers {Xi} may be selected and another n-product of polynomials may be computed, as indicated by the NO-loop inFIG.4. Alternatively, in some implementations, one or more additional numbers Xn+1, Xn+2. . . may be generated and the new candidate number Z* obtained according to
Z*=Z·(Xn30 12+u)·(Xn+22u) . . . modM.
Primality testing may be performed using any available test, such as the Pocklington test, the BailliePSW test, the MillerRabin test, or the like.

In some implementations, depending on the desired size of the prime numbers, a lower bound L may be set for the target range of Z. In some implementations, the lower bound may be a soft bound, with the candidate numbers that are below (but not significantly below) the lower bound deemed acceptable. Similarly, in some implementations, the candidate numbers that are above (but not significantly above) the lower bound may still be excluded. In one illustrative example, after the candidate number Z is determined, a modified candidate number ZLmay be computed as follows:
ZL=L+(Z−LmodM),
ensuring that ZL∈[L,M+L−1]. In some implementations, L may be comparable to M (e.g., by an order of magnitude). In some implementations, L can be a multiple of M, pushing the interval [L,M+L−1] to values that are outside (and do not overlap with) the interval [0,M−1]. In some implementations, a larger range can be obtained by taking L to be a random multiple of M: L=R·M where a random number R may be taken within a predefined interval corresponding to a desired (target) range of prime numbers. In some implementations, the random number R can be selected once for a particular instance of the prime number being generated and reused for all attempts to obtain this prime number (with other random numbers R selected when additional prime numbers are sought). In some implementations, the random number R can be resampled for each attempt (e.g., each application of the n-product) to obtain the prime number.

In some implementations, modular operations may be performed using Montgomery multiplication that replaces division by the modulus (e.g., M) with a Montgomery reduction operation, which amounts to adding an appropriately chosen multiple of M until the result is a multiple of an auxiliary Montgomery modulus and thus amenable to a simple transformation (e.g., cancellation the low bits of the result).

In some implementations, generation of the set of numbers {Xj} may be performed using one or more pseudorandom functions (PRF), e.g., a function which generates outputs deterministically (so that the same inputs generate the same inputs), while the outputs appear similar to random numbers (block422). A PRF may use a seed number Seed (block424), an identifier j (e.g., enumerator) of the number Xjbeing generated and a hint Hint (block426) that may change (deterministically or randomly) between different attempts (applications of the n-product) in generating the prime number:
Xj=PRF (Seed,j,Hint).
In some implementations, Seed may be a longer number (e.g., a 128-bit number, a 256-bit number, and the like), whereas Hint may be a shorter number (e.g., a 16-bit number, a 32-bit number, and the like). The inputs Seed and Hint may be stored as a secret information and may be protected, during execution of PRF( ) using various methods of blinding, masking, or other types of cryptographic protection.

In some implementations, Seed may be generated randomly, for each prime number generating session, for each particular time period, every time the processing device is powered on, and so on. Seed may be generated from a hardware key, such as a PUF (physical unclonable function) key that is based on manufacturing characteristics of a hardware device. Upon a successful prime number identification using the methods disclosed above, as depicted by dashed arrows inFIG.4, at block450, the processing device may store Seed and Hint (and, optionally, if one or more additional numbers Xn+1, Xn+2. . . were employedthe total number jmax of the numbers Xused in the n-product) whereas the actual generated prime number (p and/or q) may not be stored (e.g., for additional protection of secret information). Respectively, when a ciphertext c is received (block460), the processing device may access stored Seed, Hint (and, optionally, imax) and generate the set {Xj} using PRF( ). Based on the generated set {Xj}, the processing device can recover, applying the n-product to the set {Xj} (or jmax−product, if jmax>n) to recover the prime number (block470) and decrypt the encrypted message (block480). A similar process may be used to reproduce other prime numbers of the cryptographic key, such as q (and/or any additional prime numbers as may be used by the decryption algorithm). For example, to reproduce multiple prime numbers, e.g., p and q, a single Seed and multiple hints may be stored, e.g., Hint1, Hint2. . . In some implementations, a single Seed and a single hint, e.g., Hint1, may be stored whereas other hints Hint2. . . may be deterministically determined based on Hint1. In some implementations, as depicted by solid arrows inFIG.4, the generated prime numbers may be stored directly (block440) and used for decryption of a received ciphertext (block480).

FIG.5depicts a flow diagram of an illustrative example of method500of generating and using prime numbers in cryptographic applications, in accordance with one or more aspects of the present disclosure. Method500, as well as method600disclosed below, and/or each of their individual functions, routines, subroutines, or operations may be performed by one or more processing units of the computing system implementing the methods, e.g., the processor220. In certain implementations, each of methods500and600may be performed by a single processing thread. Alternatively, each of methods500and600may be performed by two or more processing threads, each thread executing one or more individual functions, routines, subroutines, or operations of the method. In an illustrative example, the processing threads implementing each of methods500and600may be synchronized (e.g., using semaphores, critical sections, and/or other thread synchronization mechanisms). Alternatively, the processing threads implementing each of methods500and600may be executed asynchronously with respect to each other. Various operations of each of methods500and600may be performed in a different order compared to the order shown inFIGS.5and6. Some blocks may be performed concurrently with other blocks. Some blocks may be optional. Some or all of the blocks of each of methods500and600may be performed by fast prime number generation104module.

Method500may be implemented by processor220(or an arithmetic logic unit, an FPGA, and the like, or any processing logic, hardware or software or a combination thereof) performing a cryptographic operation, which may be set up to use a private key comprising two or more prime numbers, e.g., p and q. Method500may involve receiving an encrypted message c (ciphertext) from sending device110. Prime numbers may be generated when the cryptographic application is set up and/or at regular time intervals, when the previous key has become compromised as a result of a power-analysis attack, a security breach, and so on. In some implementations, the private key may include three or more prime numbers.

The processing device implementing method500may initiate generation of a new set of prime numbers as part of a new cryptographic key. At block510, the processing device may determine one or more polynomial functions that have no roots modulo each of a predefined set of prime numbers {Pi}, which may be a set of the lowest prime numbers up to a certain target prime number (e.g., the first N prime numbers excluding number 2). The processing device may select one or more parameter values (e.g., −u, −u1, −u2. . . ) that are quadratic non-residues modulo each of the predefined set of prime numbers and use the selected parameter values to construct the one or more polynomial functions, e.g., X2+u. In some implementations, the one or more polynomial functions can be quadratic functions, e.g., G(X)=s·X2+t·X+u, whose discriminant s·X2+t·X+u≠0 is a quadratic nonresidue modulo each of the predefined set of prime numbers.

At block520, method500may continue with selecting one or more input numbers {xj}. In some implementations, the input numbers may be selected randomly within a predetermined interval. In some implementations, the input numbers may be selected using a respective (different for each j) output of a pseudorandom function. The respective j-th output of the pseudorandom function may determined in view of a seed number Seed and a respective hint value Hintj. The seed number may be common to all instances j of selection of the input numbers Xjwhereas the hint numbers may be different for different j. In some implementations, both the hint number and the seed number change with every j when a new number Xjis being selected.

At block530, method500may continue with the processing device generating a candidate number Z by applying one or more instances of the one or more polynomial functions to the one or more input numbers. The candidate number Z may be generated by determining a product of multiple instances of the polynomial function, e.g., Z=(X12+u)·(X22+u) . . . . In some implementations, all instances j involve the same polynomial function F(Xj,u) whereas in other implementations, some of the instances j may involve a different polynomial function G(Xj,u) that is based on the same parameter value −u, or the same polynomial function F(Xj,u1), F(Xj, u2) . . . that is based on different values −u1, −u2. . . , or different polynomial functions G(Xju2) . . . that are based on different values −u1, −u2. . . , and so on. In some implementations, the product of the instances of the polynomial function is determined modulo a modulus number. The modulus number may be divisible by each of the predefined set of prime numbers {Pi}, e.g., the modulus number may be a product of the predefined set of prime numbers, ΠiPi(but may also include additional factors). The number of instances jmaxof polynomial function(s) may be arbitrary, e.g., in some implementations, the number of instances may be four, five, or more. In some implementations, the product of each of the one or more instances of the polynomial function(s) may be determined using Montgomery multiplication techniques.

At block540, method500may continue with the processing device determining, using any known methods, that the candidate number Z is a prime number. Responsive to such a determination, the processing device may store, at block550, the seed number Seed and the one or more hint values Hint, which resulted in generation of a successful candidate number Z. In some implementations, the determined prime numbers, e.g., p and q, may be used to generate the product p·q that is published (or transmitted) as part of the public key, whereas the values p and q may not be stored.

In some instances, the successful candidate number Z may not be the first candidate number generated using the set of input numbers {Xj}. For example, the set of initial input numbers {xj} may first be used to generate an initial (unsuccessful) candidate number using initial instances of the polynomial function(s) as described above, e.g., by multiplying the product of each of the one or more initial instances of the polynomial function(s). Accordingly, once it is determined that the initial candidate number is not a prime number, the product of the initial instances of the polynomial function(s) may be multiplied by one or more additional instances of the polynomial function (as applied to one or more additional input numbers Xj).

At block560, method500may continue with the processing device using the determined prime number to decrypt an input into the cryptographic operation. For example, the processing device may receive the (ciphertext) input c and decrypt c to obtain message m. The decryption operation may be performed using the previously determined prime number(s), e.g., p and q, by computing (recovering) the determined prime number(s) using the stored seed number Seed and the one or more hint values Hintj. In some implementations, computing the determined prime number(s) may be performed as described below in relation toFIG.6.

FIG.6depicts a flow diagram of an illustrative example of method600of efficient storing and using generated prime numbers in cryptographic applications, in accordance with one or more aspects of the present disclosure. Some of the blocks of method600may be performed by fast prime number generation104module and some of the blocks of method600may be performed by inverse-free decryption120module ofFIGS.1-2. Method600may be implemented by processor220(or an arithmetic logic unit, an FPGA, and the like, or any processing logic, hardware or software or a combination thereof) performing a cryptographic operation based on a previously determined private key that uses two or more prime numbers, e.g., p and q. Method600may include obtaining, at block610, an encrypted message c (ciphertext), e.g. from sending device110.

At block620, method600may continue with the processing device generating a first prime number, e.g., p, and a second prime number, e.g., q, using a seed number Seed, one or more hint numbers Hint, and one or more instances of a polynomial function. Each of the one or more instances of the polynomial function may include at least one parameter value, e.g., −u, that is a quadratic non-residues modulo each of a predefined set of prime numbers {Pi}. At block630, the processing device may determine, using the first prime number p and the second prime number q, a first decryption exponent, e.g., dp. The first decryption exponent may be a base decryption exponent d modulo a decremented first prime number, dp=d mod(p−1). At block640, the processing device may determine, using the first prime number p and the second prime number q, a second decryption exponent, e.g., dq. The second decryption exponent may be the base decryption exponent d modulo a decremented second prime number, dq=d mod(q−1). In some implementations, the first dpand second dqdecryption exponents may be computed by first determining the base exponent d: e·d=1 mod λ(p,q), using the public exponent e. In some implementations, the first dpand second dqdecryption exponents may be computed using Arazi's lemma and Hensel's lemma directly from p and q, bypassing the step of determining the base exponent d.

At block650, the processing device performing method600may determine a decrypted message m, using exponentiation, to a first power derived from the first decryption exponent dp, of a first number associated with the encrypted message. For example, the first number, q·αp, q2·αp, etc., associated with the encrypted message (with αp=cp·qe−1, αp=cp·qe−2, etc.) may be exponentiated to the to the first power, e.g., dp−1, dp−2, etc., as described in more detail above in conjunction withFIG.3. Additionally, determining the decrypted message m may involve exponentiation, to a second power (e.g., dq−1, dq−2, etc.) derived from the second decryption exponent dq, of a second number associated with the encrypted message. For example, the second number, p·αq, p2·αq, etc., associated with the encrypted message (with αq=cq·pe−1, αq=cq··pe−2,etc.) may be exponentiated to the second power, e. g., dq−1, dq−2, etc. Some or all operations (e.g., blinding operations that use random numbers) described in conjunction withFIG.3may also be performed as part of block650.

FIG.7depicts a block diagram of an example computer system700operating in accordance with one or more aspects of the present disclosure. In various illustrative examples, computer system700may represent the computer device202, illustrated inFIG.2.

Example computer system700may be connected to other computer systems in a LAN, an intranet, an extranet, and/or the Internet. Computer system700may operate in the capacity of a server in a client-server network environment. Computer system700may be a personal computer (PC), a set-top box (STB), a server, a network router, switch or bridge, or any device capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that device. Further, while only a single example computer system is illustrated, the term “computer” shall also be taken to include any collection of computers that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methods discussed herein.

Example computer system700may include a processing device702(also referred to as a processor or CPU), which may include processing logic727, a main memory704(e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM), etc.), a static memory706(e.g., flash memory, static random access memory (SRAM), etc.), and a secondary memory (e.g., a data storage device718), which may communicate with each other via a bus730.

Processing device702represents one or more general-purpose processing devices such as a microprocessor, central processing unit, or the like. More particularly, processing device702may be a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, processor implementing other instruction sets, or processors implementing a combination of instruction sets. Processing device702may also be one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. In accordance with one or more aspects of the present disclosure, processing device702may be configured to execute instructions implementing method300of optimization of decryption operations by avoiding computations of inverse values, method500of generating and using prime numbers in cryptographic applications, and method600of efficient storing and using generated prime numbers in cryptographic applications.

Example computer system700may further comprise a network interface device708, which may be communicatively coupled to a network720. Example computer system700may further comprise a video display710(e.g., a liquid crystal display (LCD), a touch screen, or a cathode ray tube (CRT)), an alphanumeric input device712(e.g., a keyboard), a cursor control device714(e.g., a mouse), and an acoustic signal generation device716(e.g., a speaker).

Data storage device718may include a computer-readable storage medium (or, more specifically, a non-transitory computer-readable storage medium)728on which is stored one or more sets of executable instructions722. In accordance with one or more aspects of the present disclosure, executable instructions722may comprise executable instructions implementing method400of protecting cryptographic operations by intermediate randomization.

Executable instructions722may also reside, completely or at least partially, within main memory704and/or within processing device702during execution thereof by example computer system700, main memory704and processing device702also constituting computer-readable storage media. Executable instructions722may further be transmitted or received over a network via network interface device708.

While the computer-readable storage medium728is shown inFIG.7as a single medium, the term “computer-readable storage medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of operating instructions. The term “computer-readable storage medium” shall also be taken to include any medium that is capable of storing or encoding a set of instructions for execution by the machine that cause the machine to perform any one or more of the methods described herein. The term “computer-readable storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories, and optical and magnetic media.

Some portions of the detailed descriptions above are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “identifying,” “determining,” “storing,” “adjusting,” “causing,” “returning,” “comparing,” “creating,” “stopping,” “loading,” “copying,” “throwing,” “replacing,” “performing,” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

Examples of the present disclosure also relate to an apparatus for performing the methods described herein. This apparatus may be specially constructed for the required purposes, or it may be a general purpose computer system selectively programmed by a computer program stored in the computer system. Such a computer program may be stored in a computer readable storage medium, such as, but not limited to, any type of disk including optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic disk storage media, optical storage media, flash memory devices, other type of machine-accessible storage media, or any type of media suitable for storing electronic instructions, each coupled to a computer system bus.

The methods and displays presented herein are not inherently related to any particular computer or other apparatus. Various general purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct a more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear as set forth in the description below. In addition, the scope of the present disclosure is not limited to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the present disclosure.

It is to be understood that the above description is intended to be illustrative, and not restrictive. Many other implementation examples will be apparent to those of skill in the art upon reading and understanding the above description. Although the present disclosure describes specific examples, it will be recognized that the systems and methods of the present disclosure are not limited to the examples described herein, but may be practiced with modifications within the scope of the appended claims. Accordingly, the specification and drawings are to be regarded in an illustrative sense rather than a restrictive sense. The scope of the present disclosure should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.