Design of High Speed Long Calculation
Units for Public-Key Cryptography
Jean-Pierre Seifert
Infineon Technologies Corporation
Security & Chip Card ICs
Technical Innovation
D-81669 Munich
Germany

Security & Chip Card ICs

Motivation - Why to think about new long integer arithmetic units
for smart card ICs?
Î First generation long integer units were designed to support RSA
Î Longer RSA parameters desired
Î RSA is loosing its dominant role
Î Increasing interest in public key schemes based on elliptic curvesÎ New attacks unknown when the current units were designedrequirements

Î Support of RSA up to 2048 Bits
Î Support of elliptic curves over finite fields up to 256 Bits
Î Immunity against recent attacks
Î Flexibility and scalability of the design
Security & Chip Card ICs

What are the arithmetic requirements due to RSA?

RSA
Crucial cryptographic operation:
a,b, N → ab mod N
Reduction to more elementary operations

modular squarings , modular multiplications
c → c2 mod N;
c,a → c×a mod N
Registers:
small number of very long registers(4 x 2048 Bits)

Security & Chip Card ICs

What are the arithmetic requirements due to elliptic curves?
Elliptic curve E: y2 = x3 + ax + b over GF(p) or E: y2 = x3 + ax + b over GF(2k)Crucial cryptographic operation:k, P → k×P,
where k is a secret integer, P = (xP, yP) is a point on E.

Reduction to elementary operations on elliptic curve
point doublings / additions of different points
Q → 2×Q
Q,P → Q + P

Reduction to elementary modular arithmetic
a lot of modular additions, modular subtractions, modular multiplications, andat least one modular inversion
Registers:
large number of rather short registers (8 x 256 Bits)
random access to operands necessary
Security & Chip Card ICs

What is “modular arithmetic“ and how to do it?
Given:

a positive integer N, the modulus,integers a and b with 0 ≤ a, b < N

Modular addition:

Find the integer c with 0 ≤ c < N such that c ≡ a+b mod N

Modular multiplication:

Find the integer c with 0 ≤ c < N such that c ≡ a×b mod N

Standard techniques for modular multiplication:••

Multiply a and b and divide the result by N.
Interleave steps necessary for multiplication with steps for modular reduction

The methods for modular arithmetic depend strongly on the chosen representation ofintegers:
Basis B = {Bm-1,...,B0}
integer a⇔vector (am-1, ...,a0) of coordinates aj with respect to Bj

Security & Chip Card ICs

Some design approaches
Î The chinese remainder approachÎÎÎBasis B = {Bm-1, ...,B0} consists of coprime integers
additions, multiplications mod Bm-1 ,..., mod B0 in parallel
modular reduction difficult

Î The full-parallel-multiplier-approachÎ Basis B = {Bm-1, ...,B0} consists of powers of a fixed radix BÎ widely a software approachÎ The serial-parallel-multiplier approachÎ Basis B = {Bm-1, ...,B0} consists of powers of a fixed radix B

Security & Chip Card ICs

Algorithmic description of interleaved modular multiplication
Given : Basis B = {Bm-1, ...,B0} with Bj = Bj , for some radix B = 2k anda = (am-1, ..., a0), b = (bm-1, ..., b0), c = (cm-1, ..., c0)
Input: Operands a, b of length m, radix B, modulus N
Output: c = a·b mod N1)
2)
3)
4)

c ← 0;for i ← m - 1 downto 0 doc ← c·B + ai ·bc ← c mod N

interleaved reduction

Basic design options for a modular multiplication device
The full-parallel-multiplier approach:large radix B = 2k(i.e. k = 16)

The serial-parallel-multiplier approach:small radix B = 2k(i.e. k = 1,..,3)

core component: k-bit parallel-multipliercore component:• calculates products ai ·b in blocks of length k• reduced number of loop iterations• small number of products ai ·b• addition of intermediate results in one step

fast parallel adder

Security & Chip Card ICs

The serial-parallel-multiplier approach

MethodÎ

multiplication is broken down to shifts and additions

Îmodular reduction interleaved with steps for multiplication

Basic constituentsÎfast parallel adderÎalgorithm for modular reduction

Security & Chip Card ICs

The problem of fast parallel addition
Given :

Basis B = {Bm-1, ...,B0} with Bj = Bj , for some fixed radix B, set of digits Z.
Integers a = (am-1, ..., a0) and b = (bm-1, ..., b0) , ai, bi ∈ Z.

Problem:Design a device that determines s = (sm, ..., s0) , where s = a + b
Area:
as small as possibleTime:
as short as possible
Scalability:
as good as possible

Non-redundant set Z of digits:

Redundant set Z of digits:

Z = {0,1,....,B -1}
representation of integer is unique#(Z) > B
representation of integer is not uniqueÎ Carry-ripple-adderÎ Carry-look-ahead-adderÎ Carry-completition-adderÎ Carry-save-adderÎ Delayed-carry-adderÎ RSD-adders
Security & Chip Card ICs

Comparision of parallel adders (i)Basis B = {Bm-1, ...,B0} with Bj = Bj , for radix B=2, set of digits: Z = {0,1}Î Carry-ripple-adder
Area:
O(m)
Time:
O(m)
Scalability:
goodm full-adder-cells

Î Carry-look-ahead-adderArea:O(m⋅log m)Time:O(log m)Scalability:
difficultÎ Carry-completition-adderArea:O(m⋅log m)Time:O(log m)Scalability:
difficult
Security & Chip Card ICs

The carry-ripple-adder
Given :

Basis B = {Bm-1, ...,B0} with Bj = Bj , for the radix B = 2, set ofdigits Z = {0,1}Integers a = (am-1, ..., a0) and b = (bm-1, ..., b0), ai, bi ∈ Z.
s = (sm, ..., s0) , where s = a + b

Addition rule: si = ai ⊕ bi ⊕ ci, where c0 = 0ci+1 = ai×bi v ai×ci v bi×cism = cm
Properties:
Area:
Time:
Scalability:

O(m),
O(m)
good

Evaluation: completely inadequate for cryptographic applications

Security & Chip Card ICs

Comparision of parallel adders (II)Basis B = {Bm-1, ...,B0} with Bj = Bj , for radix B=2, set of digits: Z = {0,1}ÎÎÎ

Carry-Save-adder
Area:
O(m)
Time:
Scalability: goodm full-adder-cells
O(1)Delayed-carry-adder
Area:
O(m)
Time:
Scalability: goodm full-adder-cells + m half-adder-cells
O(1)RSD-adders
Area:
Time:
Scalability:

O(m)
O(1)
goodSecurity & Chip Card ICs

The carry-save-adder or (3,2)-counter or 3-operand-adder
Given : Basis B = {Bm-1, ...,B0} with Bj = Bj , for radix B = 2.
set of digits Z first operand:
second operandsum:

Input:

Z = {0,1}pair of binary digits from Z
pair of binary digits from Z

a = (am-1, ..., a0),b = (bm-1, ..., b0), c=(cm-1, ..., c0)

Output: s = (sm-1, ..., s0) and c‘ =(c‘m-1, ..., c‘0) such thats + c‘ = a + b + c
Addition rules.

Properties:

si = ai ⊕ bi ⊕ cic‘i+1 = ai× bi v ai× ci v bi × ci

Area: O(m) , scales easily
Time: O(1)The carry-save-adder is a straightforward derivate of the carry-ripple-adder.
Security & Chip Card ICs

The panic-adder or a fast-average-case adder
Idea: On average, the longest carry chain when adding two m-bit
numbers is of lengthlog2 m.
Thus:— Divide m bits into blocks of length b, i.e., m/b blocks.
— Choose b large enough such that there is on average no carry
between consecutive blocks.
— Realize the blocks of length b as carry-look-ahead-adders.
— A block gets into panic, if an incoming carry would travel through it.
Clue: No time needed for carry propagation on average, but only somelittle extra time in the unlikely case that a block gets into panic.
Security & Chip Card ICs

Probability that a block gets into panic

probability for panic in block of length b=(1/2)b

probability for no panic in l blocks of length b=( 1 - (1/2)b )lprobability for panic in at least 1 out of l blocks=1 - ( 1 - (1/2)b )lSecurity & Chip Card ICs

The panic adder
Given :

Basis B = {Bm-1, ...,B0} with Bj = Bj , for the radix B = 2, set ofdigits Z = {0,1}Integers a = (am-1, ..., a0) and b = (bm-1, ..., b0), ai, bi ∈ Zs = (sm, ..., s0), where s = a + b

Addition rule:as described before
Properties:
Area:
Time:
Scalability:

O(m),
O(1)
very goodEvaluation: Extraordinarily suited for cryptographic applications asoperands are long, thus resulting in a good average time.
Security & Chip Card ICs

Methods for interleaved modular reduction
Problem:

Given the modulus N and integers a and b with 0 ≤ a, b < N.
Find a + b mod N.

Methods to solve the problem:ÎComparision of sizes and subtractionc←a+b
if c ≥ N then c ← c - N
Problem: The comparision “ is c ≥ N ? “ can be difficultÎOmura reduction
For a fixed power 2s > N the integer 2s - N is stored
This replaces comparision of sizes by overflow detectionÎMontgomery reduction
avoids completely operations based on estimates of sizes
Replaces operations with N by operations with the radix B
Drawback: conversion to special represention of integers isnecessary
Security & Chip Card ICs

Comparision of some serial-parallel-designs
The ZDN-Unit
Concept due to H. Sedlak (1988)
Characteristics:- use of Booth´s algorithm to reduce the number of partial products- special modular reduction based on an easy comparison with (2/3)·N- execution of multiplication and reduction simultaneously- use of a special three-operand-adder via carry-save-adder and panic adderTime for one modular multiplication:~ (1/2.8)·m clock cycles in practice= (1/3)·m clock cycles in theory

The Brickell-design
Characteristics:- based on a delayed-carry-adder- modular reduction similar to Omura‘s approach
Time for one modular multiplication:m + 7 clock cycles

Security & Chip Card ICs

Comparision of some serial-parallel-designs(II)

Radix-2 and radix-4 RSD-units
N. Takagi and S. Yajima (1992)
Characteristics:
based on RSD-representation of integers
modular reduction similar to Omura‘s approach
Time for one modular multiplication:m clock cycles
m/2 clock cycles

radix B = 2
radix B = 4

Radix-8 RSD-unit
extrapolation based on Takagi -Yajima-design
Characteristics:
based on RSD-representation to radix B = 8
modular reduction similar to Omura‘s approach
Time for one modular multiplication:

m/3 clock cycles

Security & Chip Card ICs

Comparision of some serial-parallel-designs(III)

Comparing area and time for modular multiplication for some serialparallel units:
total areatime for modularmultiplication•••ZDN-unit Brickell RSD-21
1.821
2.8
2.8

RSD-4
31.4

RSD-8
<50.9

Data for the ZDN-unit are normalized to 1
Area for Brickell, RSD-2 and RSD-4 extrapolated to modern chiptechnology
Area estimate for RSD-8 based on a preliminary synthesis withautomatic design tool

Security & Chip Card ICs

ConclusionÎ

We described various design approaches for long integer arithmeticunitsÎThe serial-parallel-multiplier seems to be the adequate approachÎ

Under all serial-parallel designs under consideration the ZDN-unit
offers the best ratio between area consumption are performance

Security & Chip Card ICs