6 results on '"Karatsuba algorithm"'
Search Results
2. Security and efficiency trade-offs for elliptic curve Diffie–Hellman at the 128-bit and 224-bit security levels
- Author
-
Kaushik Nath and Palash Sarkar
- Subjects
Computer Networks and Communications ,business.industry ,Computer science ,Elliptic curve Diffie–Hellman ,Edwards curve ,Montgomery curve ,Karatsuba algorithm ,Cryptography ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,020202 computer hardware & architecture ,Elliptic curve ,Twisted Edwards curve ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Curve25519 ,Arithmetic ,business ,Software - Abstract
Within the transport layer security (TLS) protocol version 1.3, RFC 7748 specifies elliptic curves targeted at the 128-bit and the 224-bit security levels. For the 128-bit security level, the Montgomery curve Curve25519 and its birationally equivalent twisted Edwards curve Ed25519 are specified; for the 224-bit security level, the Montgomery curve Curve448, the Edwards curve Edwards448 (which is isogenous to Curve448) and another Edwards curve which is birationally equivalent to Curve448 are specified. Our first contribution is to provide the presently best known 64-bit assembly implementations of Diffie–Hellman shared secret computation using Curve25519. The main contribution of this work is to propose new pairs of Montgomery–Edwards curves at the 128-bit and the 224-bit security levels. The new curves are nice in the sense that they have very small curve coefficients and base points. Compared to the curves in RFC 7748, the new curves lose two bits of security. The gain is improved efficiency. For Intel processors, we have made different types of implementations of the Diffie–Hellman shared secret computation using the new curves. The new curve at the 128-bit level is faster than Curve25519 for all types of implementations that we considered, while the new curve at the 224-bit level is faster than Curve448 using 64-bit sequential implementation using schoolbook multiplication, but is slower than Curve448 for vectorized implementation using Karatsuba multiplication. Overall, the new curves provide good alternatives to Curve25519 and Curve448.
- Published
- 2021
3. Parallel modular multiplication using 512-bit advanced vector instructions
- Author
-
Clifton R. Haider, Benjamin Buhrow, and Barry K. Gilbert
- Subjects
Modular exponentiation ,Xeon ,Modular arithmetic ,Computer Networks and Communications ,Computer science ,Karatsuba algorithm ,Multiplication ,Parallel computing ,512-bit ,Throughput (business) ,Software ,Xeon Phi - Abstract
Applications such as public-key cryptography are critically reliant on the speed of modular multiplication for their performance. This paper introduces a new block-based variant of Montgomery multiplication, the Block Product Scanning (BPS) method, which is particularly efficient using new 512-bit advanced vector instructions (AVX-512) on modern Intel processor families. Our parallel-multiplication approach also allows for squaring and sub-quadratic Karatsuba enhancements. We demonstrate $$1.9\,\times $$ 1.9 × improvement in decryption throughput in comparison with OpenSSL and $$1.5\,\times $$ 1.5 × improvement in modular exponentiation throughput compared to GMP-6.1.2 on an Intel Xeon CPU. In addition, we show $$1.4\,\times $$ 1.4 × improvement in decryption throughput in comparison with state-of-the-art vector implementations on many-core Knights Landing Xeon Phi hardware. Finally, we show how interleaving Chinese remainder theorem-based RSA calculations within our parallel BPS technique halves decryption latency while providing protection against fault-injection attacks.
- Published
- 2021
4. A new class of irreducible pentanomials for polynomial-based multipliers in binary fields
- Author
-
Gustavo Banegas, Ricardo Felipe Custódio, Daniel Panario, Coding Theory and Cryptology, and Discrete Mathematics
- Subjects
FOS: Computer and information sciences ,Irreducible pentanomials ,Polynomial ,Computer Science - Cryptography and Security ,Computer Networks and Communications ,Modulo ,Polynomial multiplication ,Karatsuba algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Irreducible pentanomials Polynomial multiplication Modular reduction Finite fields ,Binary fields ,Modular reduction ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Number Theory (math.NT) ,Computer communication networks ,Mathematics ,Discrete mathematics ,Mathematics - Number Theory ,020202 computer hardware & architecture ,Finite field ,010201 computation theory & mathematics ,Finite fields ,Multiplier (economics) ,Cryptography and Security (cs.CR) ,Software - Abstract
We introduce a new class of irreducible pentanomials over $${\mathbb F}_{2}$$ of the form $$f(x) = x^{2b+c} + x^{b+c} + x^b + x^c + 1$$ . Let $$m=2b+c$$ and use f to define the finite field extension of degree m. We give the exact number of operations required for computing the reduction modulo f. We also provide a multiplier based on Karatsuba algorithm in $$\mathbb {F}_2[x]$$ combined with our reduction process. We give the total cost of the multiplier and found that the bit-parallel multiplier defined by this new class of polynomials has improved XOR and AND complexity. Our multiplier has comparable time delay when compared to other multipliers based on Karatsuba algorithm.
- Published
- 2019
5. Some new results on binary polynomial multiplication
- Author
-
M. Anwar Hasan and Murat Cenk
- Subjects
Multiplication algorithm ,Finite field ,Computer Networks and Communications ,Binary operation ,Polynomial arithmetic ,Karatsuba algorithm ,Multiplication ,Arithmetic ,Scalar multiplication ,Bernstein polynomial ,Software ,Mathematics - Abstract
This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein’s 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein’s 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein’s algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.
- Published
- 2015
6. Multiprecision multiplication on AVR revisited
- Author
-
Michael Hutter and Peter Schwabe
- Subjects
Computer Networks and Communications ,business.industry ,Computer science ,Quadratic complexity ,Karatsuba algorithm ,Cryptography ,Microcontroller ,Software ,Multiplication ,Digital Security ,Arithmetic ,business ,Computer communication networks - Abstract
This paper presents new speed records for multiprecision multiplication on the AVR ATmega family of 8-bit microcontrollers. For example, our software takes only 1,969 cycles for the multiplication of two 160-bit integers; this is more than 15 % faster than that demonstrated in previous work. For 256-bit inputs, our software is not only the first to break through the 6,000-cycle barrier; with only 4,771 cycles it also breaks through the 5,000-cycle barrier and is more than 21 % faster than previous work. We achieve these speed records by carefully optimizing the Karatsuba multiplication technique for AVR ATmega. One might expect that subquadratic-complexity Karatsuba multiplication is only faster than algorithms with quadratic complexity for large inputs. This paper shows that it is in fact faster than fully unrolled product-scanning multiplication already for surprisingly small inputs, starting at 48 bits. Our results thus make Karatsuba multiplication the method of choice for high-performance implementations of elliptic-curve cryptography on AVR ATmega microcontrollers.
- Published
- 2015
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.