The Carry Leakage on the Randomized Exponent
14
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
14
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
The Carry Leakage on the Randomized Exponent Countermeasure Pierre-Alain Fouque 1 , Denis Real 2;3 , Frederi Valette 2 , and Mhamed Drissi 3 1 E ole normale superieure/CNRS/INRIA, 75 Paris, Fran e Pierre-Alain.Fouqueens.fr 2 CELAR, 35 Bruz, Fran e fDenis.Real;Frederi .Valettegdga.defense.gouv.fr 3 INSA-IETR, 20 avenue des oesmes, 35043 Rennes, Fran e fDenis.Real;Mhamed.Drissiginsa-rennes.fr Abstra t. In this paper, we des ribe a new atta k against a lassi al dierential power analysis resistant ountermeasure in publi key implementations. This ountermeasure has been suggested by Coron sin e 1999 and is known as the exponent randomization. Here, we show that even though the binary exponentiation, or the s alar produ t on ellip- ti urves implementation, does not leak information on the se ret key, the omputation of the randomized se ret exponent, or s alar, an leak useful information for an atta ker. Su h part of the algorithm an be not well-prote ted sin e its goal is to avoid atta k during the exponentiation. Consequently, our atta k an be mounted against any kind of exponentiation, even very resistant as soon as the exponent randomization ounter- measure is used.
- prote ted
- bit
- against spa
- has been
- against very
- ted sin
- exponent randomization
- dpa atta
The
Carry
Leak
age
y
er
on
the
the
Randomized
tro
Exp
double-and-add
onen
t
t
m
Coun
er
termeasure
k
Pierre-Alain
and
F
ouque
simple
1
implemen
,
implemen
Denis
R
of
Coron
eal
bit
2
in
;
of
3
v
,
applications
F
of
r
and
a
ed
so
eric
t.
V
use
alette
b
2
h
,
onen
and
ts
Mhamed
of
Drissi
termeasure
3
termeasure,
1
ted.
Ecole
ed
normale
Ho
sup
tire
based
erieure/CNRS/INRIA,
hannel
75
w
P
most
aris,
lev
F
against
rance
o
Pierre-Alain.Fouque@ens.fr
the
2
Elliptic
CELAR,
wide
35
to
Bruz,
er
F
a
rance
the
f
op
k
g
is
that
.def
ev
ense.
e
gouv
tial
.fr
[13])
3
and
INSA-IETR,
randomizing
20
scalar
a
order
v
)
en
or
ue
oin
des
e.
prop
esmes,
1999.
35043
onen
Rennes,
same
F
v
rance
f
This
Denis.Real;Mhamed.Drissi
een
g
ouque
Doubling
sa-r
in
ennes
is
.fr
k
or
In
1
this
Side
pap
ks
er,
p
w
e
da
describ
b
e
require
a
of
new
h
k
ks.
against
the
a
algorithms
ultiply
dieren
analog
tial
e,
p
since
o
There
w
er
v
analysis
o
resistan
(SP
t
that
p
termeasure
ultiply
in
op
public
all
k
of
ey
are
implemen
dep
tations.
This
ery
termeasure
implemen
has
Ho
b
een
suggested
k
b
using
y
o
Coron
(DP
since
hniques
1999
in
and
p
is
kno
wn
or
as
y
the
of
exp
the
onent
(
r
the
andomization
mo
.
the
Here,
base
w
in
e
Elliptic
sho
h
w
b
that
b
ev
℄
en
this
though
the
will
binary
e
exp
DP
onen
that
tiation,
the
or
y
the
e
scalar
W
pro
ell-kno
has
on
ellip-
y
V
using
es
ttac
implemen
ev
tation,
h
do
adv
es
en
not
leak
ey
information
RSA
on
ECC
the
In
k
ey
,
the
are
ery
of
o
the
erful
randomized
ks
to
exp
y
onen
em
t,
edded
or
that
scalar,
high
el
leak
useful
use
information
termeasures
for
an
kind
k
Tw
er.
of
most
h
studied
part
are
of
square-and-m
the
algorithm
algorithm
its
on
b
Curv
e
the
not
algorithm,
w
its
ell-protected
usage.
since
exists
its
goal
termeasure
is
a
to
oid
a
p
v
w
oid
analysis
A)
k
k,
during
alw
the
ys
exp
erforms
onen
m
tiation.
or
Consequen
add
tly
eration
,
that
our
the
erations
k
the
tation
b
not
e
ey
moun
enden
ted
This
against
termeasure
an
v
y
kind
in
of
so
exp
most
onen
tations
tiation,
it.
ev
w
en
er,
v
h
ery
tations
resistan
b
t
as
ed
so
y
on
dieren
as
p
the
w
exp
analysis
onen
A
t
randomization
as
ter-
[14]
measure
a
is
opular
used.
termeasure
W
in
e
the
target
exp
an
t
`
-bit
b
adder
a
whic
ultiple
h
the
adds
of
`
elemen
-bit
'
w
N
ords
in
of
the
RSA
dulus
exp
of
onen
order
t
the
and
p
of
t
a
the
random
of
v
Curv
alue.
W
e
has
sho
een
w
osed
that
y
if
in
the
since
With
leaks
during
the
the
exp
addition,
t
then
nev
w
b
e
the
and
almost
A
learn
ks
the
high
er
order
bits
b
of
bit
b
h
moun
w
Related
ord
ork.
of
w
the
wn
termeasure
exp
b
onen
rst
t.
k
Finally
b
,
F
and
h
alette
information
[11]
the
b
A
e
k.
then
w
used
er,
to
v
the
er
ersary
the
assumedto
b
e
side
and
a
able
other
to
v
send
for
man
of
y
for
times
w
the
)
same
base
message
k
and
the
that
er
no
of
randomization
to
of
ot
the
k
message
is
x
p
with
erformed
v
b
not
efore
en
the
tiation
exp
onen
Then
tiation.
step
Here,
our
onen
the
k
is
a
in
v
missing
oids
t
these
whole
t
of
w
d
o
and
dra
the
wbac
eration
ks
random
since
[17]
the
part
in
k
do
w
es
uses
not
need
the
the
w
kno
e
wledge
the
of
k
the
that
message.
other
In
eys
[10],
alue
F
are
ouque
et
et
Ho
al.
ust
sho
since
w
birthda
that
requiremen
if
ot
Coron's
um
In
termeasure
that
is
used
with
some
no
windo
is
wing
itself
exp
onen
an
tiation
onen
algorithms
d
and
random
a
one,
small
of
public
um
k
the
ey
P
e
al.
,
then
on
a
simple
since
SP
and
A
Finally
follo
w
ery
ed
exp
b
t
y
age
a
from
v
sho
ery
t,
in
er
h
k
the
-bit
go
v
er
er
the
the
is
y
k
b
ey
required
d
and
k
'
ering
(
the
N
the
)
addition
in
y
the
in
same
mo
time.
ev
In
bits
[10],
b
the
n
implemen
metho
tation
on
is
parado
not
and
protected
are
against
square
SP
fourth
A
the
er
ks
Our
since
pap
the
sho
exp
SP
A
e
v
k
and
do
k
es
e
not
The
w
elt
ork
on
target
the
the
windo
j
wing
algorithms.
(
In
this
mo
w
the
ork,
x
the
j
authors
.
ha
of
v
alue
e
and
to
targeted
solv
the
e
a
random
problem
er,
similar
ultiple
of
of
that
oin
whic
Seifert
h
Brier
w
℄
e
also
try
on
to
the
solv
public
e
Here,
here,
is
namely
asiv
,
e
hange
v
e
ering
the
this
v
d
since
in
against
RSA,
or
kno
v
wing
tiation
some
exp
since
onse
hannel
from
bits
and
of
exp
d
W
.
that
Indeed,
exp
side
scalar,
are
hannel
`
then
hnique
the
allo
and
ws
F
to
ouque
order
et
h
al.
ord
to
with
learn
d
some
k
whole
ey
,
bits
um
