Giri¸s
G¨
osterim
Kriptografi’de Boole Fonksiyonları
Z¨
ulf¨
ukar Saygı
Department of Mathematics,
TOBB University of Economics and Technology,
Ankara, Turkey.
1S
¸ ubat 2015
Kriptografik Kriterler
Giri¸s
G¨
osterim
˙I¸cerik
1
Giri¸s
2
G¨osterim
3
Kriptografik Kriterler
Kriptografik Kriterler
Outline
1
Giri¸s
2
G¨osterim
3
Kriptografik Kriterler
Giri¸s
G¨
osterim
Kriptografik Kriterler
Motivasyon
Boole fonksiyonları bir¸cok simetrik ¸sifreleme sisteminin tasarımında
ve g¨
uvenlik seviyelerinde kilit rol oynarlar.
Giri¸s
G¨
osterim
Kriptografik Kriterler
Motivasyon
Boole fonksiyonları bir¸cok simetrik ¸sifreleme sisteminin tasarımında
ve g¨
uvenlik seviyelerinde kilit rol oynarlar.
Akan S¸ifreler (Stream Ciphers) (Kombinasyon u
¨rete¸sleri, Filtre
u
¨rete¸cleri,...)
Bir¸cok LFSR ¸cıktısının kombinasyonu alınabilir veya tek bir
LFSR nin i¸ceri˘
gi filtrelenip tek bit c¸ıktı verilir.
S¨
ozde rastgele (pseudo-random) diziler u
¨retilir ve Vernam
benzeri ¸sifreleme olarak kullanılır (Vernam: mesaj ile dizi mod
2 de toplanır).
Giri¸s
G¨
osterim
Kriptografik Kriterler
Motivasyon
Boole fonksiyonları bir¸cok simetrik ¸sifreleme sisteminin tasarımında
ve g¨
uvenlik seviyelerinde kilit rol oynarlar.
Akan S¸ifreler (Stream Ciphers) (Kombinasyon u
¨rete¸sleri, Filtre
u
¨rete¸cleri,...)
Bir¸cok LFSR ¸cıktısının kombinasyonu alınabilir veya tek bir
LFSR nin i¸ceri˘
gi filtrelenip tek bit c¸ıktı verilir.
S¨
ozde rastgele (pseudo-random) diziler u
¨retilir ve Vernam
benzeri ¸sifreleme olarak kullanılır (Vernam: mesaj ile dizi mod
2 de toplanır).
Blok S¸ifreler
S-kutuları lineer olmayan Boole fonksiyonları birle¸stirilerek
olu¸sturulurlar.
Giri¸s
Motivasyon
G¨
osterim
Kriptografik Kriterler
Giri¸s
Motivasyon
G¨
osterim
Kriptografik Kriterler
Giri¸s
Motivasyon
G¨
osterim
Kriptografik Kriterler
Giri¸s
G¨
osterim
Kriptografik Kriterler
Bazı G¨osterimler
F2 = {0, 1} ⇒ 2 elemanlı sonlu cisim.
F2n ⇒ 2n elemanlı sonlu cisim.
Fn2 ⇒ F2 u
¨zerinde n-boyutlu vekt¨
or uzayı.
BF (n) ⇒ Fn2 den F2 ye t¨
um Boole fonksiyonları k¨
umesi.
wH (f ) = w (f ) ⇒ f nin Hamming a˘
gırlı˘
gı,
w (f ) = |{x ∈ Fn2 : f (x) 6= 0}|.
d(f , g ) ⇒ f ile g arasındaki uzaklık,
d(f , g ) = |{x ∈ Fn2 : f (x) 6= g (x)}| = w (f + g ).
Giri¸s
G¨
osterim
Kriptografik Kriterler
Bir NOT
Kriptografide kullanılan Boole fonksiyonlarının de˘gi¸sken
sayıları genellikle k¨
u¸cu
¨k sayılardır.
˙Istenilen Kriptografik ¨
ozelliklere sahip Boole fonksiyonları
b¨
ut¨
un fonksiyonları tarayarak bulmak ¸cok kolay de˘gildir!
n
|BF (n)| = 22 oldu˘
gundan n ≥ 6 i¸cin sayılar ¸cok b¨
uy¨
ur.
n
|BF (n)|
≈
4
216
6 · 104
5
232
4 · 109
6
264
1019
7
2128
1038
8
2256
1077
Outline
1
Giri¸s
2
G¨osterim
3
Kriptografik Kriterler
Giri¸s
G¨
osterim
Kriptografik Kriterler
Cebirsel Normal From (Algebraic Normal Form - ANF)
F2 u
¨zerinde n-de˘gi¸skenli polinom g¨
osterimi
!
f (x) =
X
I ∈P(N)
aI
Y
xi
i∈I
P(N): N = {1, 2, . . . , n} nin kuvvet k¨
umesi.
N = {1, 2, 3} ⇒ P(N) =
{∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
f (x) =
a0 +a1 x1 +a2 x2 +a3 x3 +a12 x1 x2 +a13 x1 x3 +a23 x2 x3 +a123 x1 x2 x3
Giri¸s
G¨
osterim
Kriptografik Kriterler
Cebirsel Normal From (Algebraic Normal Form - ANF)
Bu g¨osterim F2 [x1 , . . . , xn ]/ x12 + x1 , . . . , xn2 + xn u
¨zerinde
tanımlıdır.
ANF tek t¨
url¨
ud¨
ur.
Divide-and-conquer tipi ”‘Butterfly”’ (Kelebek) algoritması ile
hızlı bi¸cimde ANF hesaplanabilir.
Do˘
gruluk tablosundan ANF
ANF den Do˘
gruluk Tablosu
ANF nin derecesi deg (f ) = max{|I | : aI 6= 0} olarak
tanımlanır (|I |: I nın b¨
uy¨
ukl¨
u˘
gu
¨).
deg (f ) = 1 olan f fonksiyonlarına afin fonksiyonlar denir
(a0 = 0 ise afin fonksiyona lineer fonksiyon denir).
Giri¸s
G¨
osterim
Kriptografik Kriterler
ANF ¨orne˘gi
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
Giri¸s
G¨
osterim
Kriptografik Kriterler
ANF ¨orne˘gi
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
⇒ f = (1 + x1 )(1 + x2 )x3 + x1 (1 + x2 )x3 + x1 x2 x3 = x1 x2 x3 + x2 x3 + x3
|
{z
} |
{z
} | {z }
Giri¸s
G¨
osterim
Kriptografik Kriterler
ANF ¨orne˘gi
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
⇒ f = (1 + x1 )(1 + x2 )x3 + x1 (1 + x2 )x3 + x1 x2 x3 = x1 x2 x3 + x2 x3 + x3
|
{z
} |
{z
} | {z }
deg (f ) = 3
Not: f Boole fonksiyonunun cebirsel derecesi ancak ve ancak wH (f ) tek
ise n dir.
Giri¸s
G¨
osterim
Kriptografik Kriterler
Butterfly Algoritması ile ANF
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
1.
0
0+1=1
0
0+0=0
0
0+1=1
0
0+1=1
Giri¸s
G¨
osterim
Kriptografik Kriterler
Butterfly Algoritması ile ANF
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
1.
0
0+1=1
0
0+0=0
0
0+1=1
0
0+1=1
2.
0
1
0+0=0
0+1=1
0
1
0+0=0
1+1=0
Giri¸s
G¨
osterim
Kriptografik Kriterler
Butterfly Algoritması ile ANF
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
1.
0
0+1=1
0
0+0=0
0
0+1=1
0
0+1=1
2.
0
1
0+0=0
0+1=1
0
1
0+0=0
1+1=0
3.
0
1
0
1
0+0=0
1+1=0
0+0=0
1+0=1
Giri¸s
G¨
osterim
Kriptografik Kriterler
Butterfly Algoritması ile ANF
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f (x1 , x2 , x3 )
0
1
0
0
0
1
0
1
1.
0
0+1=1
0
0+0=0
0
0+1=1
0
0+1=1
2.
0
1
0+0=0
0+1=1
0
1
0+0=0
1+1=0
⇒ f = x1 x2 x3 + x2 x3 + x3
Karma¸sıklık (Complexity) n · 2n XOR operasyonu.
3.
0
1
0
1
0+0=0
1+1=0
0+0=0
1+0=1
Outline
1
Giri¸s
2
G¨osterim
3
Kriptografik Kriterler
Giri¸s
G¨
osterim
Tasarım Kriterleri
Se¸cilen kriptografik sisteme g¨
ore ¨
ozellikler de˘
gi¸sir...
Dengeli (Balanced)
C
¸ ıktı ile girdi arasında istatistiksel ba˘
gımlılık olmamalı
C
¸ ıktı d¨
uzg¨
un da˘
gılmalı
Kriptografik Kriterler
Giri¸s
G¨
osterim
Tasarım Kriterleri
Se¸cilen kriptografik sisteme g¨
ore ¨
ozellikler de˘
gi¸sir...
Dengeli (Balanced)
C
¸ ıktı ile girdi arasında istatistiksel ba˘
gımlılık olmamalı
C
¸ ıktı d¨
uzg¨
un da˘
gılmalı
Cebirsel derece y¨
uksek olmalı
Akan ¸sifrelerde Berlekamp-Massey ata˘
gı.
Blok ¸sifrelerde diferansiyel atak.
Kriptografik Kriterler
Giri¸s
G¨
osterim
Kriptografik Kriterler
Tasarım Kriterleri
Se¸cilen kriptografik sisteme g¨
ore ¨
ozellikler de˘
gi¸sir...
Dengeli (Balanced)
C
¸ ıktı ile girdi arasında istatistiksel ba˘
gımlılık olmamalı
C
¸ ıktı d¨
uzg¨
un da˘
gılmalı
Cebirsel derece y¨
uksek olmalı
Akan ¸sifrelerde Berlekamp-Massey ata˘
gı.
Blok ¸sifrelerde diferansiyel atak.
m. dereceden korelasyon-immune
girdinin m-biti sabit tutuldu˘
gunda ¸cıktının istatisti˘gi da˘gılımı
de˘
gi¸smemeli.
m-resilient:= m. dereceden korelasyon-immune + dengeli
m yeterince k¨
uc¸u
¨k ise Siegenthaler ata˘
gı (Akan S¸ifreler i¸cin
korelasyon ata˘
gı) ve geli¸smi¸s versiyonları (Hızlı Korelasyon
Atakları)
m ≤ n − 1 − deg (f )
Giri¸s
G¨
osterim
Kriptografik Kriterler
Tasarım Kriterleri
f nin c¸ıktısı ile lineer fonksiyonların korelasyonu d¨
u¸su
¨k olmalı.
Nonlinearity (N(f)): f ile t¨
um afin fonksiyonlar arasındaki
minimum Hamming uzaklık. X
n
Walsh d¨
on¨
u¸su
¨m¨
u: Wf (ω) =
(−1)f (x)+Tr1 (ωx) .
x∈F2n
⇒ N(f ) = 2n−1 − 12 maxω∈F2n |Wf (ω)|.
N(f ) ≤ 2n−1 − 2n/2−1 . E¸sitli˘
ge ula¸san fonksiyonlara bent
(b¨
uk¨
uk) fonksiyonlar denir.
Giri¸s
G¨
osterim
Kriptografik Kriterler
Tasarım Kriterleri
Yayılma (Propagation) Kriteri (PC )
Keskin ¸cı˘
g Kriterinin (Strict Avalanche Criterion - SAC)
genellemesi.
Boole fonksiyonun ¸sifre sistemine kattı˘
gı yayılma seviyesini
ol¸cer.
¨
Blok S
¸ ifre sistemleri ile alakalıdır.
f nin PC (l) olması wH (a) ≤ l olan ∀a i¸cin
Da f (x) = f (x) + f (x + a) nın dengeli olmasıdır.
SAC ≡ PC (1)
Bent fonksiyonlar PC (n) dir.
Giri¸s
G¨
osterim
Tasarım Kriterleri
Cebirsel immunity (AI (f ))
fg = 0 yapan g fonksiyonuna f nin annihilator ’ı denir.
AI (f ): f veya f + 1 fonksiyonlarının sıfırdan farklı
annihilatorlarının minimum derecesidir.
AI (f ) ≤ deg (f ) ve AI (f ) ≤ n2
Pratik uygulamalarda AI (f ) ≥ 7 olmalıdır.
Dolayısıyla n ≥ 13 ve n ≈ 20 olmalı.
Aksi halde cebirsel atak yapmak m¨
umk¨
un olabilir!
Kriptografik Kriterler
Giri¸s
G¨
osterim
Kriptografik Kriterler
Polinom g¨osterimi
Not: Fn2 ∼
= F2n .
F2n den F2n ye her fonksiyon (Vect¨
orel Boole Fonksiyon)
f (x) =
n −1
2X
ci x i
ci , x ∈ F2n
i=0
¸seklinde tek t¨
url¨
u g¨
osterime sahiptir.
n
f Boole fonksiyondur ⇔ (f (x))2 = f (x) mod x 2 + x, yani,
c0 , c2n −1 ∈ F2 ve c2j = (cj )2 (2j mod 2n − 1).
Giri¸s
G¨
osterim
Trace g¨osterimi
F2n den F2 ye Trace fonksiyonu: :
n−1
2
Tr (x) = x + x 2 + x 2 + · · · + x 2
T¨
um Boole fonksiyonlar a¸sa˘
gıdaki gibi g¨
osterilebilir:
!
n −1
2X
Tr
ci x i
ci , x ∈ F2n ,
i=0
fakat g¨osterim tek t¨
url¨
u de˘
gil!
Kriptografik Kriterler
Giri¸s
G¨
osterim
Kriptografik Kriterler
Monomial Bent Fonksiyonlar
Definition
Monomial f fonlsiyon: f (x) = Tr (ax s ), ∀x ∈ F2n .
f nin bent olması i¸cin a¸sa˘
gıdakiler sa˘
glanmalı:
gcd(s, 2n − 1) 6= 1.
either gcd(s, 2n/2 + 1) = 1 or gcd(s, 2n/2 − 1) = 1.
Definition
s > 0 i¸cin Tr1n (ax s ) bent olacak ¸sekilde bir ∃a ∈ F∗2n varsa s ye
bent kuvveti denir.
Giri¸s
G¨
osterim
Kriptografik Kriterler
Bent Kuvvetler
Table : Bilinen t¨
um bent kuvvetler, s
s
+1
n/2
r · (2 − 1)
22i − 2i + 1
(2n/4 + 1)2
2n/3 + 2n/6 + 1
2i
Kısıt
¸cift, 1 ≤ i ≤ n2
gcd(r , 2n/2 + 1) = 1
gcd(n, i) = 1
n = 4r , r tek
n = 0 mod 6
n
gcd(n,i)
Giri¸s
G¨
osterim
Kriptografik Kriterler
Referanslar
[1]
C. Carlet ”Boolean Functions for Cryptography and Error Correcting Codes”,
Chapter of the monography “Boolean Models and Methods in Mathematics,
Computer Science, and Engineering” published by Cambridge University Press,
Yves Crama and Peter L. Hammer (eds.), pp. 257-397, 2010.
[2]
C. Carlet, ”Vectorial Boolean Functions for Cryptography”. Idem, pp. 398-469,
2010.
[3]
Henk C. A. Van Tilborg, Sushil Jajodia (editors) ”Encyclopedia of Cryptography
and Security”, 2nd Edition - Springer 2011.
Download

Boole Fonksiyonları (Boolean Functions)