Cryptography Reference
In-Depth Information
13.3.1.2 Reversing the Final Powering
The remaining problem is the reversal of the final powering: given the result
R
=
e
we want to recover
S
, the value that was computed by the algorithm before
the final powering (i.e., before line 9) so that
R
(
P
,
Q
)
S
q
3
1
. It is clear that given
R
,
the value of
S
is only determined up to a non-zero factor in
−
=
F
q
3
. Indeed, for non-
∈ F
q
3
we have
c
q
3
−
1
zero
c
=
1. Furthermore, given one solution
S
∈ F
q
6
to
X
q
3
−
1
∈ F
q
3
.
Given the description above it should be clear that the attacker does not need to
reverse the powering of a full product of factors, but rather a single factor with a
fairly special form. That is, given
−
R
=
0, all others are of the form
c
·
S
for non-zero
c
R
2
R
1
=
e
m
±
d
+
1
(
P
,
Q
)
g
q
3
−
1
R
=
=
(
m
±
d
+
1
)
e
m
±
d
(
P
,
Q
)
the attacker aims to recover
g
(
m
±
d
+
1
)
, which will, in turn, allow recovery of the
correct
x
P
and
y
P
. This requires
1. a method to compute one valid root of
R
g
q
3
1
for some factor
g
, and
2. a method to derive the correct value of
g
from among all possible solutions.
The first problem can be solved very efficiently as follows: multiply the equation
X
q
3
−
=
−
1
−
R
=
0by
X
to obtain
X
q
3
−
R
·
X
=
0
,
and note that the operator
X
q
3
−
R
·
X
is a linear operator on the two-dimensional
=
F
q
3
2
vector space
F
q
6
/
F
q
3
. Since
F
q
6
[
σ
]
/(σ
−
1
)
, we can write
X
=
x
0
+
σ
x
1
and
R
=
r
0
+
σ
r
1
, with
x
0
,
x
1
,
r
0
,
r
1
∈ F
q
3
. Using this representation, we see that
the above equation is equivalent to
1
x
0
x
1
−
r
0
r
1
M
·
X
=
=
0
.
r
1
1
+
r
0
The kernel of the matrix
M
is a one-dimensional vector space over
F
q
3
and thus
provides all the solutions to
X
q
3
−
1
0.
To choose the correct root from among all
q
3
−
R
=
1 possibilities, one can use the
specific form of the factors in the computed product. Each factor
g
is of the form
−
2
g
=
g
0
+
g
1
ρ
−
ρ
+
g
2
σ,
g
q
3
−
1
, one first obtains
g
with
g
0
,
g
1
,
g
2
∈ F
q
. To recover
g
from
R
=
=
c
·
g
∈ F
q
3
using the root finding approach above, and then computes
c
−
1
and thus
g
itself. Again this boils down to a simple linear system of equations: by
multiplying
g
for some
c
F
q
3
, we can assume
g
with an appropriate factor in
is of the form
