Tampere University of Technology

TUTCRIS Research Portal

Bit-sliced binary normal basis multiplication

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Original languageEnglish
Title of host publicationProceedings - 20th IEEE Symposium on Computer Arithmetic, ARITH-20
Number of pages8
Publication statusPublished - 2011
Publication typeA4 Article in a conference publication
Event20th IEEE Symposium on Computer Arithmetic, ARITH-20 - Tubingen, Germany
Duration: 25 Jul 201127 Jul 2011


Conference20th IEEE Symposium on Computer Arithmetic, ARITH-20


The performance of many cryptographic primitives is reliant on efficient algorithms and implementation techniques for arithmetic in binary fields. While dedicated hardware support for said arithmetic is an emerging trend, the study of software-only implementation techniques remains important for legacy or non-equipped processors. One such technique is that of software-based bit-slicing. In the context of binary fields, this is an interesting option since there is extensive previous work on bit-oriented designs for arithmetic in hardware, such designs are intuitively well suited to bit-slicing in software. In this paper we harness previous work, using it to investigate bit-sliced, software-only implementation arithmetic for binary fields, over a range of practical field sizes and using a normal basis representation. We apply our results to demonstrate significant performance improvements for a stream cipher, and over the frequently employed Ning-Yin approach to normal basis implementation in software.


  • Algorithm design, analysis, Computations in finite fields, Computer arithmetic, Data encryption