.PH ""
.nr Pt 1
.EQ
delim $$
define ref % "" sup %
define gcd % roman "gcd" %
define mod % roman "mod" %
.EN
.ds HP 10 10 10 10 10 10 10
.ds HF 3 3 3 3 3 3 3
.am DE
.ls 2
.sp
..
.ce 99
.S 12
\f3Fast Cryptanalysis of the Matsumoto-Imai Public Key Scheme\f1
.S 10
.sp
\f2P. Delsarte\f1
.sp .5
Philips Research Laboratory,
Avenue Van Becelaere, 2
B-1170 Brussels, Belgium
.sp
\f2Y. Desmedt\f1
.sp .5
Katholieke Universiteit Leuven,
Laboratorium ESAT, Kardinaal Mercierlaan, 94
B-3030 Heverlee, Belgium
.sp
\f2A. Odlyzko\f1
.sp .5
AT&T Bell Laboratories
Murray Hill, New Jersey 07974, U.S.A.
.sp
\f2P. Piret\f1
.sp .5
Philips Research Laboratory,
Avenue Van Becelaere, 2
B-1170 Brussels, Belgium
.sp 2
\f2ABSTRACT\f1
.ce 0
.sp 2
.ls 2
.P
The Matsumoto-Imai public key scheme was
developed to provide very fast signatures.
It is based on substitution polynomials
over $GF(2 sup m )$.
This paper shows in two ways that the Matsumoto-Imai
public key scheme is very easy to break.
In the faster of the two attacks the
time to cryptanalyze the scheme is about
proportional to the binary length of
the public key.
This shows that Matsumoto and Imai greatly
overestimated the security of their scheme.
.bp
.ls 1
.ce 99
.S 12
\f3Fast Cryptanalysis of the Matsumoto-Imai Public Key Scheme\f1
.S 10
.sp
\f2P. Delsarte\f1
.sp .5
Philips Research Laboratory,
Avenue Van Becelaere, 2
B-1170 Brussels, Belgium
.sp
\f2Y. Desmedt\f1
.sp .5
Katholieke Universiteit Leuven,
Laboratorium ESAT, Kardinaal Mercierlaan, 94
B-3030 Heverlee, Belgium
.sp
\f2A. Odlyzko\f1
.sp .5
AT&T Bell Laboratories
Murray Hill, New Jersey 07974, U.S.A.
.sp
\f2P. Piret\f1
.sp .5
Philips Research Laboratory,
Avenue Van Becelaere, 2
B-1170 Brussels, Belgium
.ce 0
.ls 2
.sp 2
.H 1 "INTRODUCTION"
Several attempts have been made to use
the fields $GF(2 sup m$) [1] in
cryptography.
The motivation is that these fields allow
very fast computation and are very easy
to implement in hardware [2].
However, many such attempts
.nr P 1
.PH "''- \\\\nP -''"
quickly yielded to cryptanalytic attacks.
For example, an extension of the RSA scheme
to the fields $GF(2 sup m )$ [3] was
immediately broken [4,10].
The security of the fields $GF(2 sup m )$
in public key distribution systems [5] was
also overestimated [6].
Cryptanalysis is possible there if the
dimension $m$ of the field $GF(2 sup m )$
is less than 1000 [6].
.P
The Matsumoto-Imai public key scheme [7]
also uses the fields $GF(2 sup m )$.
It allows generation of signatures much
faster than the RSA scheme.
Moreover the scheme is very easy
to implement.
However, in this paper we give two
efficient algorithms to cryptanalyze the
Matsumoto-Imai public key scheme.
.P
First the details of the Matsumoto-Imai
scheme are presented, based on our
interpretation of [7].
Then an overview of the first and second
cryptanalytic attack are given.
Both attacks use the public knowledge of
the construction algorithm for public
keys, and find secret parameters used
in the construction of the public key.
These algorithms are then presented in detail.
.H 1 "THE MATSUMOTO-IMAI PUBLIC KEY SCHEME"
The Matsumoto-Imai [7]
enciphering is defined over $GF(2 sup m )$,
the message space.
The public key is a substitution
polynomial [1]: $E(X)~=~SIGMA from i=0 to {2 sup m -2} ~ e sub i X sup i$.
For a message $Y$, which belongs to $GF(2 sup m )$,
the ciphertext is $E(Y)$.
In order to have a "short" public key
and to be able to encipher rapidly,
most of the $e sub i$ must be zero.
To that end, $E(X)$ is constructed as
$E(X)~==~a(b+X sup alpha ) sup beta$ modulo
$(X sup {2 sup m} + X)$, where
the Hamming weight [2] of $beta$ is $r$.
One can then easily prove that only
$2 sup r$ coefficients $e sub i$ will be
non-zero.
If $r$ is small (e.g., 14, as suggested in [7]), the public
key is not too long.
$E(X)$ in expanded form is made public,
while $a,^b,^ alpha$, and $beta$ are kept
secret in order to be able to decipher fast.
In order to specify $E(X)$, the field $GF(2 sup m )$
has to be made public also, and $r$ can be deduced
from the number of non-zero coefficients.
Therefore we have:
.P
.I
Remark:\0One can consider that $m$ and $r$
are given, so these values do not have to
be deduced.
.R
.H 1 "MAIN PRINCIPLES FOR THE CRYPTANALYSIS OF THE MATSUMOTO-IMAI PUBLIC KEY SCHEME"
In order to allow a unique deciphering, the system designer has to chose
$gcd ( alpha ,^ 2 sup m - 1)~=~ gcd ( beta ,^ 2 sup m -1)~=~1$,
and so from now on we will assume these conditions hold.
The following theorems help to explain
the cryptanalysis.
.P
.I
Theorem\ 1:\0If the public key is
constructed as mentioned above and $beta$
is written as
.DS 2
.EQ (1)
beta~=~sum from j=1 to r~2 sup {u sub j} ,~~~~with~~
0 ~<=~ u sub j < m ,
.EN
.DE
then the exponents of $X$ with non-zero
coefficients can be expressed as
.DS 2
.EQ (2)
alpha~sum from j=1 to r~z sub j 2 sup {u sub j}~
( mod ~2 sup m -1)^,~~~~with~~z sub j ~=~ 0~~roman or~1 ^ ,
.EN
.DE
and their corresponding coefficients as
.DS 2
.EQ (3)
ab sup k~~with~~k~==~sum from j=1 to r~
(1-z sub j ) 2 sup {u sub j}~~~( mod ~2 sup m -1) ^ .
.EN
.DE
.R
.P
\f2Proof\f1:\0Using the construction
algorithm for public keys and (1),
we have $E(X)~=$\p
.br
$a ~prod from j=1 to r$
$(b + X sup alpha ) sup {2 sup {u sub j}}$.
Since the characteristic of $GF(2 sup m )$
is 2, $E(X) ~=~ a~prod from j=1 to r$
$(b sup {2 sup {u sub j}} ~+~ X sup {alpha 2 sup {u sub j}} )$,
and using $X sup {2 sup m} ~==~ X$
modulo $X sup {2 sup m} ~+~ X$ we obtain
(2) and (3).
$blot$
.P
.I
Corollary\ 1:\0At least $m$ different
$(a,^b,^ alpha ,^ beta )$ determine the
same enciphering key.
.R
.P
\f2Proof\f1:\0Choose $alpha prime ~==~ 2 sup h alpha$
and $beta prime ~==~ 2 sup m-h beta$
(modulo $2 sup m - 1$) and
use the proof of Theorem\ 1.
$blot$
.P
It is sufficient to find any one of
these equivalent $(a,^ b,^ alpha ,^ beta )$
in order to break the scheme.
To simplify the description, all these
equivalent keys will be called the
secret key.
We will sometimes suppose in the paper
that $u sub 1 ~=~ 0$, which
by Corollary\ 1 entails no loss of
generality.
.P
.I
Corollary\ 2:\0If
$u sub 1 ~=~ 0$
then $b~=~$(coefficient of $X$ to the
power 0)/(coefficient of $X$ to the power
$alpha$) and $a~=~$(coefficient of $X$ to
the power 0)/$b sup beta$.
.R
.P
\f2Proof\f1:\0Can be verified easily
using Theorem\ 1.
$blot$
.P
.I
Theorem\ 2:\0If $gcd ( alpha ,^ 2 sup m -1)~=~1$
and $gcd ( beta ,^ 2 sup m -1)~=~1$,
then the list of exponents of $X$ in $E(X)$
with nonzero coefficients contains
a unique subset of size $r$ of the form
$"{" 2 sup {v sub 1} ^alpha sub 1~,~~
2 sup {v sub 2} ^alpha sub 1 ,"...", 2 sup {v sub r} ^alpha sub 1 "}"$
( modulo $2 sup m -1$).
Taking Corollary\ 1 into account one
has $alpha ~=~ alpha sub 1$ and
$beta ~=~ SIGMA 2 sup {v sub j}$.
.R
.P
\f2Proof\f1:\0In view of Theorem\ 1 this subset
is actually present in the list of exponents.
Let now $gamma$ be any other element of
the list, say
$gamma ~==~(2 sup {p sub 1} ~+~ 2 sup {p sub 2} ~+~
"..." ~+~2 sup {p sub s}) alpha$
(modulo $2 sup m -1$), where
$"{" p sub 1 ,^ p sub 2 ,^ "...",^ p sub s "}"$ is a subset
of $"{" u sub 1 ,^ u sub 2 , "...", u sub r "}"$
with $s ~>=~ 2$.
We shall prove that the list contains
fewer than $r$ elements of the form
$2 sup k gamma$ (modulo $2 sup m -1$).
First it is clear there cannot be more than
$r$ such elements, because for each $i$, each
sum $p sub i + k$ (modulo $m$)
must coincide with one of the integers
$u sub 1 ,^ u sub 2 , "...", u sub r$.
If there were exactly $r$ elements, then
one would necessarily have $p sub 1 + k sub j ~==~ u sub {pi (j)}$
and $p sub 2 + k sub j ~==~ u sub {sigma (j)}$ (modulo $m$),
for $j~=~1,2, "...", r$,
where $pi$ and $sigma$ are two permutations on
$"{" 1,^2, "...",^r "}"$.
Taking the binary exponential of these
identities and adding the results
together (for $j~=~1 ,^ 2 , "..." ,^ r$) one
readily obtains
$beta (2 sup {p sub 2 ~-~ p sub 1} ~-~ 1) ~==~ 0$
(modulo $2 sup m -1$), which is impossible
since $gcd ( beta ,^ 2 sup m -1)~=~1$ and
$p sub 2 ~!=~ p sub 1$.
$blot$
.P
If one finds an $alpha sub 1$ which satisfies
the above property, then $alpha$ will be
chosen equal to $alpha sub 1$.
The calculation of $beta$ is then trivial;
it is in fact obtained at the same time as
$alpha$.
Once $alpha$ and $beta$ have been found,
$a$ and $b$ are calculated using Corollary\ 2.
As a consequence of Theorem\ 2 and the
remark at the beginning of this section,
one does not need to check that the obtained
$alpha$ is correct!
Two algorithms will now be presented which
find $alpha$ and $beta$.
The first algorithm uses the calculation of
the inverse of elements modulo $2 sup m -1$.
The second one is based on shift operations
and sorting algorithms.
.H 1 "CRYPTANALYSIS USING INVERSE CALCULATION"
.H 2 "The Principles Of The Algorithm"
Exponents of $X$ with non-zero coefficients
will be written as $i sub k$, with $1 ~<=~ k ~<=~ 2 sup r$.
For each $k , ~1 <= k <= 2 sup r$, we test whether $alpha = i sub k$.
If $gcd (i sub k ,^ 2 sup m -1 )$ is not equal
to one, a wrong choice for $alpha$ was made.
If $gcd (i sub k ,^ 2 sup m -1)~=~1$ then
several techniques can be used to find $beta$.
In one of them the cryptanalyst first calculates
.DS 2
.EQ (4)
f sub l ~==~ i sub l i sub k "" sup -1~
( mod ~2 sup m -1 )^,~~1 ~<=~ scrL ~<=~ 2 sup r ^ .
.EN
.DE
In view of Theorem\ 2,
if $r$ values of $f sub l$ are powers of 2,
then $i sub k$ is
$alpha$, and $beta$ is the sum of these $r$
values of $f sub l$.
If no such $r$ values are found, continue
the exhaustive search.
Because $r$ is small this exhaustive search
is fast.
.H 2 "Speed Evaluation Of The Algorithm"
The number of elementary steps (such
as additions and shifts) used in the above
cryptanalytic algorithm will be
analyzed.
First the complexity of each step will be obtained; next
this value will be multiplied by the number of
times each step is executed.
.P
The calculation of the $gcd (i sub k ,^ 2 sup m -1)$
and the calculation of $i sub k "" sup -1$,
if it exists, can be done at once.
This requires $O (m)$ steps [8]
(subtractions or shifts).
This means in total $O (m2 sup r )$ steps
during the exhaustive search for $alpha$.
The calculation of (4) requires in practice
$O (m sup 2 )$ [8] elementary steps
(additions and small multiplications).
For larger values of $m$ better algorithms
(e.g., using the FFT) can be used [8].
This means for the exhaustive search
that (4) is executed in worst case in
$O ( m sup 2 2 sup 2r )$
steps, while on average it takes
$O ( m sup 2 2 sup 2r / r )$ steps.
The calculation of $beta$ requires for
each trial $O ( log sub 2~m)$ steps.
We conclude that the cryptanalysis
requires $O (m sup 2 2 sup 2r /r)$
steps on average, and $O(m sup 2 2 sup 2r )$ in the worst case.
The next algorithm has an improved speed
performance.
.H 1 "CRYPTANALYSIS USING SHIFT OPERATIONS"
.H 2 "The Principles Of The Algorithm"
In the second method of attack we partition the exponents of
$X$ with nonzero coefficients into sets $S sub p$.
Two different exponents $i sub k$ and $i sub l$
of $X$, with non-zero coefficients, will
belong to the same set $S sub p$ if and
only if for some $s$, $i sub k ~==~ 2 sup s i sub l$
(mod $2 sup m -1$).
In other words, $i sub k$ and $i sub l$
belong to the same set $S sub p$ if one
can obtain $i sub k$ from $i sub l$ by
a suitable rotation of its binary
representation.
The cryptanalysis consists of determining
all different sets $S sub p$ for all exponents of $X$
with non-zero coefficients.
Using Theorem\ 2 exactly one $S sub p$,
which we call $S sub r$, will contain
$r$ elements.
Using Corollary\ 2, any element of
$S sub r$ can be chosen as $alpha$.
Identifying the required rotation
operations for going from $alpha$
to obtain the other elements of
$S sub r$, we obtain $beta$.
We now describe how the above ideas
can be carried out.
The speed of the algorithm will be discussed later.
.P
First we define a unique representative
for each set $S sub p$.
A value $v sub p$ is the representative
of the set $S sub p$ if it is the smallest
of the $m$ values obtained by rotating
$0,^1,^2, "...",^ m-1$ times an element of the
set $S sub p$.
Note that $v sub p$ can be viewed as the
value of a function $v(i)$ defined over
the set $"{" 0 ,^ 1, "..." ,^ 2 sup m -2 "}"$
and satisfying $v(i sub 1 ) ~=~ v (i sub 2 )$
if and only if $i sub 1 ~==~ 2 sup s i sub 2$
(mod $2 sup m -1$), for a certain $s$.
This function $v(i)$ will now be used
to find $alpha$.
We calculate $v(i sub k )$ for all
$2 sup r$ exponents $i sub k$ of $X$
with non-zero coefficients.
The $v(i sub k )$ and $i sub k$
together are written in lists
A and B of $2 sup r$ elements, in which
each element contains $m$ bits.
There is a unique element $w$ that appears
$r$ times in list A, and then $alpha$
can be chosen as any of the corresponding
elements in list B.
This search for $w$ and $alpha$ can easily
be performed by sorting [9, pp.\ 2]
the list A while simultaneously permuting
the list B in the same way.
.H 2 "Speed Evaluation Of The Algorithm"
The calculation of $v(i)$ requires $m$ steps.
Doing this for all the exponents of $X$
that appear in $E(X)$ takes
$m2 sup r$ steps.
The sorting of list A, together with the
permutation of list B, requires
$O (r2 sup r )$ steps in practice
[9, pp.\ 181-198, p.\ 381].
.P
In total this algorithm requires $O (m2 sup r )$ steps even in the worst case!
.H 1 "CONCLUSIONS"
The Matsumoto-Imai public key scheme
seems attractive from speed considerations,
\f2but is totally insecure\f1!
Matsumoto and Imai estimated the cryptanalysis
of their scheme would require about $10 sup 20$
steps if $m~=~127$ and $r~=~14$.
However using our cryptanalytic attack using
inverse calculation, on the same example,
one needs only about $3 star 10 sup 11$
steps, which is performable even on a small
computer.
If one step requires 10\ $mu^ sec$
on a small computer, then the attack
requires 36 days.
If one step asks 100\ $eta^ sec$ on a fast
computer, the attack can be performed
in only 8 hours.
Using the cryptanalysis based on shift
operations, one needs only $2 star 10 sup 6$
steps.
Using the same small and fast computer, this
requires 20\ sec and 0.2\ sec, respectively.
On a fast computer, the cryptanalytic attack suggested by
Matsumoto and Imai would require $3 times 10 sup 5$ years.
.P
.I
Remark:\0The second cryptanalytic attack
requires about as many steps as the binary
length of the public key!
.R
.P
One could increase the security of the
Matsumoto-Imai scheme by increasing
$m$ and $r$.
However, even disregarding the fact
that this might entail impractically
large storage requirements, this would
not produce an acceptable system.
Evaluation of the publicly known
function
$E(X)$ takes at least $2 sup r$
multiplications in $GF( 2 sup m )$,
and each such multiplication might be
expected to take about $m$ operation
such as the shifts we utilize in our
second attack.
.I
Hence the time needed to cryptanalyze
the Matsumoto-Imai system is essentially
the same as the time needed to use it once!
.R
.bp
.ce
\f3REFERENCES\f1
.AL
.LI
R.\ Carmichael,
.ul
Introduction to the Theory of Groups of Finite Order,
Dover, New\ York, 1956.
.LI
E.\ R. Berlekamp,
.ul
Algebraic Coding Theory,
McGraw-Hill, 1968.
.LI
D.\ W. Kravitz and I.\ S. Reed,
Extension of RSA Crypto-Structure: A Galois Approach,
.ul
Electronics Letters,
vol.\ 18, no\ 6, pp.\ 255-256, 18th March\ 1982.
.LI
P.\ Delsarte and P.\ Piret,
Comment: Extension of RSA Crypto-Structure: A Galois Approach,
.ul
Electronics Letters,
vol.\ 18, no.\ 13, pp.\ 582-583, 24th June\ 1982.
.LI
K.\ Yiu and K.\ Peterson,
A Single-Chip VLSI Implementation of the Discrete Exponential
Public Key Distribution System,
.ul
Proc. Globecom '82 IEEE Global Telecommunications Conference,
vol.\ 1, pp.\ 173-179, Miami, USA, 1982.
.LI
D.\ Coppersmith,
Fast Evaluation of Logarithms in Fields of Characteristic Two,
.ul
Research Report,
RC 10187 IBM Yorktown Heights.
.ul
IEEE Trans. Inform. Theory,
to appear.
.LI
T.\ Matsumoto and H.\ Imai,
A Class of Asymmetric Crypto-Systems based on Polynomials over Finite
Rings,
.ul
IEEE Intern. Symp. Inform. Theory, St.
Jovite, Quebec, Canada, September\ 26-30, 1983,
Abstracts of Papers, pp.\ 131-132.
.LI
D.\ E. Knuth,
.I
The Art of Computer Programming,
Vol.\ 2, Seminumerical Algorithms,
.R
Addison-Wesley, Reading, Massachusetts, 1981.
.LI
D.\ E. Knuth,
.I
The Art of Computer Programming,
Vol.\ 3, Sorting and Searching,
.R
Addison-Wesley, Reading, Massachusetts 1975.
.LI
J.\ Gait,
Short Cycling in the Kravitz-Reed
Public Key Encryption System,
.ul
Electronics Letters,
vol.\ 18, no.\ 16, pp.\ 706-707, 5th August\ 1982.
.LE