d0LpHiNs™
AzraiLin GözYa$LaRı
- Katılım
- 10 Eyl 2005
- Mesajlar
- 1,457
- Reaction score
- 0
- Puanları
- 0
- Yaş
- 35
KNAPSACK
Knapsack Algoritması R. C. Merkle, M. E. Hellman tarafından 1978 de bulunmuştur. Bulunuşu NP tipi bir probleme dayanır. NP tipi problem çözümü olmayan problem demektir. Buna karşın lineer bir sistem olan ve KNAPSACK algoritmasının temelini oluşturan Super increasing vector dediğimiz yapıdan kaynaklanan bir zayıflık sayesinde bu metod bazı insanlar tarafından kırılabilmiştir.
2. Algoritma
2.1. Super Increasing Vector
Super Increasing Vector tek bir şarta bağlı bir sayı dizisidir. Bu şart; her elemanın kendisinden önce gelen elemanların toplamından büyük olmasıdır. Aşağıda bir super increasing vector görüosunuz.
A= [1, 3, 5, 10, 21, 46, 127, ....]
Burada dizinin 5. elemanı, yani 21 kendisinden önce gelen dört elemanın toplamlarından büyüktür. Bu şart dizinin bütün elemanları için geçerlidir.
2.2 Mod sayısı (m)
Dizinin son elemanından büyük olan bir sayıdır. Dolayısıyla her zeki türk gencinin farkedeceği gibi; bu sayı dizideki bütün elemanlardan büyüktür.
2.3. Anahtar (t)
Bir asal sayı
2.4. Şifreleme
Elimizdeki A vektörü deşifre işleminde kullanılacaktır. Bu A vektöründen elde edeceğimiz B vektörü ise şifreleme için kullanılır. B vektörü şu işlemle oluşturulur;
B(i)=A(i) x t mod m
t=3 ve m=191 alalım ve B vektörünü oluşturalım;
A= [ 1 3 5 10 21 41 83 170 ]
x x x x x x x x
3 3 3 3 3 3 3 3
mod
191
B= [ 3 9 15 30 63 123 58 128 ]
Oluşturulan bu B vektörü artık şifreleme için kullanılabilir. KNAPSACK te her harfi bir binary sayıyla ifade etmeliyiz. Örneğin;
a = 0001
b = 0010
c = 0011
.
.
.
gibi. Mesela “ba” kelimesini şifrelemek istersek. Bunu aşağıdaki gibi kodlayabiliriz;
010001
Bu kodlamadan sonra her 1 veya 0 B vektörü üzerine konur.
0 0 1 0 0 0 0 1
B= [ 3 9 15 30 63 123 58 128 ]
Birlere karşı gelen sayılar toplanır ve bu toplam karşıya yollanır.
15+128=143
2.5. Deşifreleme
Karşı taraf deşifreleme yapmak için A vektörünü bilmelidir. Her iki taraf da B ve A vektörlerini bulma işlemini işin en başında bir kereye mahsus olarak hesaplar. A vektöründen B yi hesaplamayı göstermiştim zaten. B den A yı hesaplamak için t sayısının inversi (tersi) bulunur. Bir sayının belli bir moddaki tersini bulmayı totient function yoluyla hesaplamayı RSA – 1. Kısımda anlattım. t_invers bulunduktan sonra şu işlemle A vektörü hesaplanır;
A(i)=B(i) x t_invers mod m
Daha sonra karşı tarafın yolladığı toplam (bu örnekte 143 idi) ın da tersi alınır. İşlem yapılırsa bunun 175 olduğu görülecektir.
Toplam_invers=toplam x t_invers mod m
1. A vektörünü taramaya sondan başla
2. toplam >= A(i)
2.1. ise toplam=toplam-a(i)
2.2. a(i) nin üstüne 1 koy
3. toplam < A(i) ise 0 koy
4. Elde edilen 1 ve 0 lar sana kelimeyi verir.
Örnek üzerinde işlem yaparsak;
A= [ 1 3 5 10 21 41 83 170 ]
Adım i A(i) toplam >= A(i) toplam_yeni ÜsteGelen
1 8 170 evet 175-170=5 1
2 7 83 hayır 5 0
3 6 41 hayır 5 0
4 5 21 hayır 5 0
5 4 10 hayır 5 0
6 3 5 evet 5-5=0 1
7 2 3 hayır 0 0
8 1 1 hayır 0 0
Oluşan sayı dizimiz; 00100001
Başlangıçtaki sayı dizisini elde ettik. Bunun karşılığı “ba” dır.
Knapsack Algoritması R. C. Merkle, M. E. Hellman tarafından 1978 de bulunmuştur. Bulunuşu NP tipi bir probleme dayanır. NP tipi problem çözümü olmayan problem demektir. Buna karşın lineer bir sistem olan ve KNAPSACK algoritmasının temelini oluşturan Super increasing vector dediğimiz yapıdan kaynaklanan bir zayıflık sayesinde bu metod bazı insanlar tarafından kırılabilmiştir.
2. Algoritma
2.1. Super Increasing Vector
Super Increasing Vector tek bir şarta bağlı bir sayı dizisidir. Bu şart; her elemanın kendisinden önce gelen elemanların toplamından büyük olmasıdır. Aşağıda bir super increasing vector görüosunuz.
A= [1, 3, 5, 10, 21, 46, 127, ....]
Burada dizinin 5. elemanı, yani 21 kendisinden önce gelen dört elemanın toplamlarından büyüktür. Bu şart dizinin bütün elemanları için geçerlidir.
2.2 Mod sayısı (m)
Dizinin son elemanından büyük olan bir sayıdır. Dolayısıyla her zeki türk gencinin farkedeceği gibi; bu sayı dizideki bütün elemanlardan büyüktür.
2.3. Anahtar (t)
Bir asal sayı
2.4. Şifreleme
Elimizdeki A vektörü deşifre işleminde kullanılacaktır. Bu A vektöründen elde edeceğimiz B vektörü ise şifreleme için kullanılır. B vektörü şu işlemle oluşturulur;
B(i)=A(i) x t mod m
t=3 ve m=191 alalım ve B vektörünü oluşturalım;
A= [ 1 3 5 10 21 41 83 170 ]
x x x x x x x x
3 3 3 3 3 3 3 3
mod
191
B= [ 3 9 15 30 63 123 58 128 ]
Oluşturulan bu B vektörü artık şifreleme için kullanılabilir. KNAPSACK te her harfi bir binary sayıyla ifade etmeliyiz. Örneğin;
a = 0001
b = 0010
c = 0011
.
.
.
gibi. Mesela “ba” kelimesini şifrelemek istersek. Bunu aşağıdaki gibi kodlayabiliriz;
010001
Bu kodlamadan sonra her 1 veya 0 B vektörü üzerine konur.
0 0 1 0 0 0 0 1
B= [ 3 9 15 30 63 123 58 128 ]
Birlere karşı gelen sayılar toplanır ve bu toplam karşıya yollanır.
15+128=143
2.5. Deşifreleme
Karşı taraf deşifreleme yapmak için A vektörünü bilmelidir. Her iki taraf da B ve A vektörlerini bulma işlemini işin en başında bir kereye mahsus olarak hesaplar. A vektöründen B yi hesaplamayı göstermiştim zaten. B den A yı hesaplamak için t sayısının inversi (tersi) bulunur. Bir sayının belli bir moddaki tersini bulmayı totient function yoluyla hesaplamayı RSA – 1. Kısımda anlattım. t_invers bulunduktan sonra şu işlemle A vektörü hesaplanır;
A(i)=B(i) x t_invers mod m
Daha sonra karşı tarafın yolladığı toplam (bu örnekte 143 idi) ın da tersi alınır. İşlem yapılırsa bunun 175 olduğu görülecektir.
Toplam_invers=toplam x t_invers mod m
1. A vektörünü taramaya sondan başla
2. toplam >= A(i)
2.1. ise toplam=toplam-a(i)
2.2. a(i) nin üstüne 1 koy
3. toplam < A(i) ise 0 koy
4. Elde edilen 1 ve 0 lar sana kelimeyi verir.
Örnek üzerinde işlem yaparsak;
A= [ 1 3 5 10 21 41 83 170 ]
Adım i A(i) toplam >= A(i) toplam_yeni ÜsteGelen
1 8 170 evet 175-170=5 1
2 7 83 hayır 5 0
3 6 41 hayır 5 0
4 5 21 hayır 5 0
5 4 10 hayır 5 0
6 3 5 evet 5-5=0 1
7 2 3 hayır 0 0
8 1 1 hayır 0 0
Oluşan sayı dizimiz; 00100001
Başlangıçtaki sayı dizisini elde ettik. Bunun karşılığı “ba” dır.