Conversion algorithms and implementations for koblitz curve cryptography

Billy Bob Brumley, Kimmo U. Jarvinen

    Research output: Contribution to journalArticleScientificpeer-review

    19 Citations (Scopus)


    In this paper, we discuss conversions between integers and \tau-adic expansions and we provide efficient algorithms and hardware architectures for these conversions. The results have significance in elliptic curve cryptography using Koblitz curves, a family of elliptic curves offering faster computation than general elliptic curves. However, in order to enable these faster computations, scalars need to be reduced and represented using a special base-τ expansion. Hence, efficient conversion algorithms and implementations are necessary. Existing conversion algorithms require several complicated operations, such as multiprecision multiplications and computations with large rationals, resulting in slow and large implementations in hardware and microcontrollers with limited instruction sets. Our algorithms are designed to utilize only simple operations, such as additions and shifts, which are easily implementable on practically all platforms. We demonstrate the practicability of the new algorithms by implementing them on Altera Stratix ∥ FPGAs. The implementations considerably improve both computation speed and required area compared to the existing solutions.

    Original languageEnglish
    Article number5255226
    Pages (from-to)81-92
    Number of pages12
    JournalIEEE Transactions on Computers
    Issue number1
    Publication statusPublished - 4 Jan 2010
    Publication typeA1 Journal article-refereed


    • Elliptic curve cryptography
    • Field-programmable gate arrays
    • Koblitz curves
    • Public-key cryptosystems

    Publication forum classification

    • Publication forum level 2

    ASJC Scopus subject areas

    • Software
    • Theoretical Computer Science
    • Hardware and Architecture
    • Computational Theory and Mathematics


    Dive into the research topics of 'Conversion algorithms and implementations for koblitz curve cryptography'. Together they form a unique fingerprint.

    Cite this