Information Technology Reference
In-Depth Information
other situations where Condition 2 can be reduced to Condition 1 which could
be solved easily (because Condition 1 is dependent on one variable).
Since the Condition 1 is easier to solve, now we shall study the S-boxes
X
d
using Condition 1 to find some situations when they are not APN. Since
X
d
is
APN iff
X
2
d
is APN, we consider
d
is an odd positive number. We can write
every odd positive integer
d
of the form
+2
q
−
2
1) + 2
q
−
1
(2
a
0
1) + 2
a
0
+
b
0
(2
a
1
i
=0
(
a
i
+
b
i
)
(2
a
q
−
1
i
=0
(
a
i
+
b
i
)
(2
a
q
−
−
−
1) +
···
−
1)
where
a
i
,
0
i<q
are the length of
i
th contiguous 1's and
0's in the binary representation of
d
. For example, (77)
10
= (1001101)
2
where
a
0
=1
,b
0
=1
,a
1
=2
,b
1
=2
,a
2
=1and
q
=2.
≤
i
≤
q
and
b
i
,
0
≤
Theorem 5.
Let
d
be of the form
d
=(2
a
0
1) + 2
a
0
+
b
0
(2
a
1
−
−
1) +
···
+
2
q
−
2
1) + 2
q
−
1
i
=0
(
a
i
+
b
i
)
(2
a
q
−
1
−
i
=0
(
a
i
+
b
i
)
(2
a
q
−
1)
.Denote
l
0
=
d
,
+2
q
−
1
l
1
=2
a
0
+
b
0
(2
a
1
1) + 2
a
0
+
b
0
+
a
1
+
b
1
(2
a
2
i
=0
(
a
i
+
b
i
)
(2
a
q
−
−
−
1) +
···
1)
,
+2
q
−
1
1
(
a
i
+
b
i
)
(2
a
q
−
l
j
=2
a
j
−
1
+
b
j
−
1
(2
a
j
−
1)+2
a
j
−
1
+
b
j
−
1
+
a
j
+
b
j
(2
a
j
+1
−
1)+
···
1)
i
=
j
−
(2
a
j
−
1
(that is,
l
j
=
l
j−
1
>>
(
a
j−
2
+
b
j−
2
)
−
−
1)
,where“
t>>n
”isbitwise
right shift of integer
t
by
n
places) for
1
<j
≤
q
.If
-
gcd
(
l
i
+1
−
1
,
2
m
−
=1
or,
gcd
(
a
i
,m
)
≤
i<q
,
1)
=1
for
0
-
and
gcd
(
a
q
−
1
,m
)
=1
.
then
F
(
X
)=
X
d
is not APN.
j
j<q
. Similar to
l
j
,denote
k
j
as
k
0
=2
a
0
Proof.
Denote
s
j
=
(
a
i
+
b
i
)
,
0
≤
−
1
i
=0
and
k
j
=
k
j−
1
+2
s
j
−
1
(2
a
j
−
j<q
.Nowweopen(1+
x
)
d
using Lucas'
1)
,
0
≤
theorem.
(1 +
x
)
d
=
i
:
i⊆d
x
i
=
i
:
i⊆k
0
x
i
+
i
:
i⊆k
0
x
i
2
s
q
−
1
x
i
2
s
0
+
x
i
x
i
···
+
0=
i⊆
2
a
1
0=
i⊆
2
a
q
−
1
−
1
i
:
i⊆k
q
−
1
2
a
0
x
i
2
a
1
−
1
x
i
2
a
q
−
1
−
1
x
i
+
i
:
i
x
i
2
s
0
+
x
i
2
s
q
−
1
=
···
+
i
=0
⊆
k
0
i
=1
i
:
i
⊆
k
q
−
1
=
i
i
=1
2
a
0
2
a
1
2
a
q
−
1
−
1
−
1
(
x
2
s
q
−
1
)
i
(
x
2
s
0
)
i
+
x
i
+(1+
x
)
k
0
+(1+
x
)
k
q
−
1
=1+
···
i
=1
i
=1
i
=1
2
a
0
2
a
1
2
a
q
−
1
−
1
−
1
−
1
(
x
2
s
0
)
i
+
(
x
2
s
q
−
2
)
i
x
i
+(1+
x
)
k
0
+(1+
x
)
k
q
−
2
=1+
···
i
=1
i
=1
i
=1
2
a
q
−
2
(
x
2
s
q
−
1
)
i
+(1+
x
)
k
q
−
1
(
x
2
s
q
−
1
)
2
a
q
−
1
+(1 +
x
)
k
q
−
1
i
=1
