A system performs big number multiplication during a cryptographic process. This can occur, for example, when a controller in a storage system encrypts data for storage in its memory or decrypts data read from its memory. To perform the multiplication of these big input numbers quickly, the system uses a modified Toom-Cook algorithm comprising a plurality of levels of coefficient vectors for each of the input numbers. This involves performing a sample extraction process, a point multiplication process, and an interpolation (synthesis) process.

A method includes receiving a first element of a Galois Field of order q.sup.m, where q is a prime number and m is a positive integer. The first element is raised to a predetermined power so as to form a second element z, wherein the predetermined power is a function of q.sup.m and an integer p, where p is a prime number which divides q.sup.m−1. The second element z is raised to a p.sup.th power to form a third element. If the third element equals the first element, the second element multiplied by a p.sup.th root of unity raised to a respective power selected from a set of integers between 0 and p−1 is output as at least one root of the first element.

A processing acceleration system including at least one gate array that performs finite field arithmetic and at least one controller that sends information to the gate array(s) upon a determination that sending the information, performing the finite field arithmetic by the gate array(s), and sending results of the finite field arithmetic to at least one destination is more efficient than general-purpose computing processor(s) performing the finite field arithmetic and sending the results to the at least one destination. The gate array(s) may include field programmable gate array(s), and the destination(s) may include the general-purpose computing processor(s) or storage devices. The finite field arithmetic may include galois field arithmetic such as modular arithmetic, for example as may be used with respect to erasure coding for storage device(s).

A method (500) of generating a cryptographic checksum for a message M(x) is provided. The method comprises pseudo-randomly selecting (502) at least two irreducible polynomials p.sub.i(x). Each irreducible polynomial p.sub.i(x) is selected based on a first cryptographic key from the set of irreducible polynomials of degree n.sub.i over a Galois Field. The method further comprises calculating (503) a generator polynomial p(x) of degree n=formula (I) as a product of the N irreducible polynomials formula (II), and calculating (505) the cryptographic checksum as a first function g of a division of a second function of M(x), ƒ(M(x)), modulo p(x), i.e., g(ƒ(M(x)) mod p(x)). By replacing a standard checksum, such as a Cyclic Redundancy Check (CRC), with a cryptographic checksum, an efficient message authentication is provided. The proposed cryptographic checksum may be used for providing integrity assurance on the message, i.e., for detecting random and intentional message changes, with a known level of security. Further, a corresponding computer program, a corresponding computer program product, and a checksum generator for generating a cryptographic checksum, are provided.

[00001]$\begin{array}{cc}{\Sigma }_{i=1}^N.Math.n_i& \left(I\right)\\ p_i\left(x\right),p\left(x\right)={\Pi }_{i=1}^N.Math.p_i\left(x\right),& \left(\mathrm{II}\right)\end{array}$

Galois-field reduction circuitry for reducing a Galois-field expansion value, using an irreducible polynomial, includes a plurality of memories, each for storing a respective value derived from the irreducible polynomial and a respective combination of expansion bit values, wherein expansion bits of the expansion value address the plurality of memories to output one or more of the respective values. The Galois-field reduction circuitry also includes exclusive-OR circuitry for combining output of the plurality of memories with in-field bits of said expansion value. There are also a method of operating such Galois-field reduction circuitry to reduce a Galois-field expansion value, a programmable integrated circuit device incorporating the circuitry, a method of performing a Galois-field multiplication operation on such a programmable integrated circuit device, and a method of configuring a programmable integrated circuit device to perform such a Galois-field multiplication operation.

An electronic calculating device (100) for performing arithmetic in a commutative ring (Z.sub.n; Z.sub.n [x]/f(x)) is presented. The calculating device comprising a storage (110) arranged to store an increment table (T) defined for an increment ring element (1; u.sup.t), the increment table mapping an input ring element (k=u.sup.k1−u.sup.k2) to an output integer-list (T((k.sub.1 k.sub.2))=(I1, I2)) encoding an output ring element (I=u.sup.I1−u.sup.I2), such that the output ring element equals the increment ring element ring-added to the input ring element (I=k−1). Using the increment table, a ring addition unit (130) adds a first addition-input integer-list ((a.sub.1, a.sub.2)) encoding a first addition-input ring element and a second addition-input integer list ((b1, b2)) encoding a second addition-input ring element. The device may comprise a ring multiplication unit (140) also using the increment table.

An integrated circuit is provided with a modular multiplication circuit. The modular multiplication circuit includes an input multiplier for computing the product of two input signals, truncated multipliers for computing another product based on a modulus value and the product, and a subtraction circuit for computing a difference between the two products. An error correction circuit uses the difference to look up an estimated quotient value and to subtract out an integer multiple of the modulus value from the difference in a single step, wherein the integer multiple is equal to the estimated quotient value. A final adjustment stage is used to remove any remaining residual estimation error.

Disclosed herein is an apparatus for calculating a cryptographic component R.sup.2 mod n for a cryptographic function, where n is a modulo number and R is a constant greater than n. The apparatus comprises an arithmetic logic unit configured to iteratively perform Montgomery multiplication of a first operand with a second operand to produce an intermediate result, wherein the first operand and the second operand are set to the intermediate result after each iteration, responsive to a termination condition being met, determine an adjustment parameter indicative of a difference between the intermediate result and the cryptographic component, and perform Montgomery multiplication of the intermediate result with the adjustment parameter, to calculate the cryptographic component for the cryptographic function.

Embodiments are directed to aggregate GHASH-based message authentication code (MAC) over multiple cachelines with incremental updates. An embodiment of a system includes a controller comprising circuitry, the controller to generate an error correction code for a memory line, the memory line comprising a plurality of first data blocks, generate a metadata block corresponding to the memory line, the metadata block comprising the error correction code for the memory line and at least one metadata bit, generate an aggregate GHASH corresponding to a region of memory comprising a cacheline set comprising at least the memory line, encode the first data blocks and the metadata block, encrypt the aggregate GHASH as an aggregate message authentication code (AMAC), provide the encoded first data blocks and the encoded metadata block for storage on a memory module comprising the memory line, and provide the AMAC for storage on a device separate from the memory module.

Efficient polynomial multiplication for Accelerated Fully Homomorphic Encryption (FHE). An efficient method for large integer and polynomial multiplication in a ring using negacyclic convolution and discrete Galois transform with arbitrary primes is described. The method is adapted to work with arbitrary primes that support Gaussian arithmetic. Dealing with non-Gaussian primes gives rise to another problem of how to find primitive roots of unity and of (i). An efficient solution to find those roots of interest is provided.