Transcript This is first slide - International Association for

Implementing Cryptographic
Pairings on Smartcards
Mike Scott
Whats a Pairing?
• Denoted e(P,Q), P and Q points on curve
over extension field GF(qk), k is the
embedding degree.
• P of order r.
• k smallest integer such that r|(qk-1)
• Useful range of k between 2 and 36
• Pairing evaluates as element of order r in
GF(qk)
• Pairing algorithm does not need
knowledge of r
What’s a Pairing?
• MOV condition – Don’t use these curves!
• Pairing-based Crypto – We need these
curves!
• Bilinearity: e(aP,bQ) = e(P,Q)ab = e(bP,aQ)
• A Pairing is a flexible crypto primitive –
with more structure than most
• Famously pairings enable Identity Based
Encryption (IBE)
Pairing-friendly Elliptic curves
• Right now we have choice between
supersingular curves, any characteristic,
and …
• Non-supersingular curves of prime
characteristic.
• Group size r at least 160 bits.
• Index calculus “difficulty” at least 1024
bits, so k.lg(q) at least 1024, where q is
the field size and k is the embedding
degree.
Pairing-friendly Elliptic curves
• We will use 3 different pairing friendly
curves. In all cases the group size is at
least 160 bits.
– GF(2m) supersingular curve, m=379 and k=4
– GF(p) non-supersingular curve, lg(p)=512 and
k=2 (generated using Cocks-Pinch method)
– GF(p) non-supersingular curve, lg(p)=256 and
k=4 (generated from a pairing-friendly family –
see Freeman-Scott-Teske (to appear))
SmartMIPS Architecture
• 32-bit RISC MIPS-based processor.
• No crypto-coprocessor – but instruction
set enhancements (Groβschadl & Savas).
• Fast clock speed (up to 36MHz), fast
enough to do standard crypto < 0.5
second.
• Triple register ACX|HI|LO
SmartMIPS Architecture
• MADDU instruction – multiplies two 32-bit
integers and adds to triple register
• MADDP instruction – multiplies two 32-bit
binary polynomials and xors to triple
register
• 5 stage pipeline
• 2k Instruction cache (2-way associative)
• 256k Flash memory
• 16k RAM
SmartMIPS Architecture
• Finally a processor with GF(2m) support!
• But MIPS architecture like to loop unroll…
• … but small instruction cache means that
we cannot unroll to the max 
• CPU Time =
#Instructions X CPI
-----------------------------------
Clock Speed
SmartMIPS Architecture
• Faster clock speeds implies cache misses
are more costly, which implies greater CPI
which implies greater CPU Time 
• So very important to use tight loops and
avoid cache misses where possible.
• Minimizing instruction count is not going to
be optimal!
Pairing algorithms
• Chance to show-case state of the art
algorithms.
• For GF(2m) curve, the ηT pairing is optimal.
• For GF(p) k=2 Cocks-Pinch curve, BKLS
algorithm for the Tate pairing.
• For GF(p) k=4 FST curve, Ate pairing is
best.
• Considered in the context of IBE, the first
parameter to the pairing is fixed, so we will
use precomputation.
Pairing algorithms
• All these algorithms need to efficiently
handle extension field arithmetic
• Base field GF(q), extension field GF(qk)
Implementation
• Uses MIRACL library
• Uses stack only allocation, for everything.
All of the 16k RAM is available for the
stack.
• Groβschadl & Savas-like assembly
language coding for the inner loops.
• Use the MADDP instruction for assembly
language GF(2m) squaring.
Implementation
• In a pairing-based protocol we are also
interested in variable-point multiplication
over the base field GF(q)…
• (Fixed point multiplication as required in
IBE will be very fast using precomputation)
• Also interested in pairing exponentiation.
Results – Instructions (%cache misses)
Pairing
Point Mult.
Field Exp.
RSA decrypt
E[GF(2239)]
ηT k=4
3705344
(10.9%)
2589569
(9.6%)
151117
(11.4%)
E[(GF(p)]
Tate k=2
7753341
(7.3%)
7418768
(6.1%)
1364124
(7.2%)
4372772
(3.4%)
E[(GF(p)]
Ate k=4
8156645
(15.8%)
2663217
(17.5%)
1614016
(15.7%)
Results – Clocks/CPI/Time 9 MHz
Pairing
Point Mult.
Field Exp.
RSA decrypt
E[GF(2239)]
ηT k=4
4311454/
1.16/0.48
3118344/
1.20/0.35
1924596/
1.24/0.21
E[(GF(p)]
Tate k=2
9104450/
1.17/1.01
8529176/
1.15/0.95
1593313/
1.17/0.18
4740271/
1.08/0.53
E[(GF(p)]
Ate k=4
10860479/
1.33/1.21
3739596/
1.40/0.42
2122221/
1.31/0.24
Results – Clocks/CPI/Time 36 MHz
Pairing
Point Mult.
Field Exp.
RSA decrypt
E[GF(2239)]
ηT k=4
4891054/
1.32/0.14
3677188/
1.42/0.10
2326675/
1.50/0.06
E[(GF(p)]
Tate k=2
10467010
1.35/0.29
9570210/
1.29/0.27
1814285/
1.33/0.05
5072415/
1.16/0.14
E[(GF(p)]
Ate k=4
13621597/
1.67/0.38
4847055/
1.82/0.13
2630846/
1.63/0.07
Results – Timings 3GHz Pentium IV
Pairing
E[GF(2239)] E[(GF(p)]
ηT k=4
Tate k=2
3.88
2.97
E[(GF(p)]
Ate k=4
3.16
Point Mult.
1.82
3.08
1.17
Field Exp.
1.14
0.54
0.62
RSA decrypt
1.92
Pairing Delegation
• Idea – delegate pairing calculation to the
terminal
• Exchange the cost of the pairing for 1
point multiplications and 3 extension field
exponentiations.
• May be beneficial….
Questions ??
Thank you!
[email protected]