1-) Giriş

Herkese selamlar! Bugün eski bir şifreleme yöntemi olan ve adını Knapsack probleminden alan Knapsack şifrelemesini anlatacağım. Benim için araştırması keyifli olacak gibi görünüyor. O zaman ne duruyoruz? Başlayalım!

2-) İşin matematik olmayan kısmını anlat bize, nedir bu?

Kne yapsack şifresi, başta da söylediğim gibi adını Kne yapsack probleminden almıştır. Bu tür, ilk genel açık anahtarlı kriptografi algoritmasıdır. Yani şifreleme (encryption) ve deşifreleme (decryption) iki farklı anahtara ihtiyaç duyar, şifreleme süreci için açık anahtar kullanılır. Deşifrelemek için ise özel anahtar kullanılır. Bu şifreleme türü, 1978 yılında Ralph Merkle ve Mertin Hellman tarafından bulundu. Bu şifreleme türü ilk genel açık anahtarlı kriptografi algoritması olsa da, 1984 yılında Adi Shamir'in yaptığı bir saldırı sonucunda bu algoritmanın kırılabileceği ve güvenilir olmadığı anlaşıldı. Yine de bence, bu algoritma ilk genel açık anahtarlı bir kriptografi algoritması olduğu için şifreleme ve şifre çözme biliminin kronolojisinde önemli bir yer edindi ve anlaşılması gereken bir algoritma. Meraklısına: sırt çantası problemi (Knapsack problem)

3-) İşin matematik kısmı nedir? Algoritmasını anlat bize!

Pekala, fikrimce eğer lise düzeyi, hatta ortaokul düzeyi matematik bilmiyorsanız zorlanacağınız kısma. Bunu aşağılamak için söylemiyorum. Bu kısım ironik bir şekilde hem zor, hem de kolay. Ben anlamak için yaklaşık birkaç saatimi gömmüştüm. Fakat anladıktan sonra epey kolaylaşıyor çünkü gerektirdiği matematik bilgisi ortaokul düzeyi. Önemli olan mantığını kavramak. Burada hayal satmayacağım. Bu yazıyı Kne yapsack Şifreleme türü ile ilgili Türkçe bir kaynak bulamadığımdan ötürü yazıyorum ancak siz hangi yazıyı okursanız okuyun eğer mantığını kavramazsanız ezber yapmış olursunuz bu da işe yaramaz. Bu yüzden matematiğin canı cehenneme! Şaka şaka. Matematik olmasa kriptografi olmazdı fakat öncelikle mantığını anlatayım önce.

4-) İşin mantığı nedir?

Tamam, şimdi öncelikle mod almayı biliyor musunuz? Basit bir şey. Bir sayının bir sayıya bölümünden kalan moddur. Örneğin,
3 mod 2 = 1
Eğer ilk sayı ikinci sayıdan küçükse sonuç direkt ilk sayı. Örneğin,
2 mod 3 = 2
Güzel. Birbirine asal olma durumunu biliyor musunuz? İki sayının ortak böleni olmama durumu. Pratik bilgi: İki sayıda asalsa iki sayı birbirine de asaldır.
Daha sonrasında bir bilgiye daha geçeceğiz. Modüler çarpımsal ters. Bunu açıklamak yerine örneğini vereceğim.
X * y = Z (mod 3)
X = 2, y = 7
2 * 7 = (mod 3)
Bu durumda Z = 2'dir.
İfadenin sözel açıklaması: "2 ve 7'nin çarpımının mod 3'e bölümü...'dır.
Şimdi mantığına geçebiliriz. Ben sırasıyla yapılması gerekenleri yazacağım.

Genel anahtarı türetmek için;

1-) Özel anahtar olmak üzere bir süper artımlı dizi oluştur.
2-) N ve M olmak üzere iki tane sayı seç. M sayısı, süper artımlı dizideki sayıların toplamından büyük olmalı. N sayısı ile M sayısı birbirine asal olmalı.
3-) Burada bir formül kullanıyoruz açık anahtara erişmek için: süper artımlı dizi elemanı * N mod(m), yani süper artımlı dizinin her bir elemanını N ile çarpıp M'ye modunu alıyoruz.
4-) İşte açık anahtarımız. Şimdi asıl şifreleme işlemine geçelim. Sonrasında örneklere geçeceğim.
Plain texti (Herkesçe okunabilir metni) şifrelemek için;
1-) Kullanıcı düz metni alır. Bu düz metni 6'lı parçalara ayırır.
2-) Ayırdığı parçayı genel anahtarın elemanlarıyla sırasıyla çarpar. Çarptıktan sonra hepsini toplar.
3-) Eğer 6'lı 3 parça oluştuysa, her bir blokta bunu yaptıktan bulduğu sonuçları virgülle birleştirir. Bu kadar!

Deşifreleme işlemi için;

1-) Alıcı şifreli metni alır. Ardından bunu 6'lı bloklara ayırır.
2-) Kullanıcı çarpımsal tersi bulmak için şu formülü uygular: n * x = 1 (mod m)Bu sayede N'nin M'ye çarpımsal tersi bulunur.
3-) Bulunduktan sonra şifreli metnin her bir bloğunu bulduğumuz sayıyla çarpıp mod M'ini alırız.
4-) Şifreli metnimizin ilk bloğuna yaptığımız işlem sonucunda bulduğumuz sayıyı özel anahtarımızda (süper artımlı dizimizde) iki sayının toplamının sonucu olacak şekilde bulmaya çalışırız. Bulduğumuz iki sayının konumlarına 1, diğerlerine 0 koyarız. Aynısını diğer bloklara da yaparız ve bunun sonucunda plain texti yani şifresiz metini bulmuş oluruz. Tebrikler!

5-) Örnekler

Biliyorum, anlamadınız. Çok normal. Açıkçası 15 20 dakika nasıl yazacağımı düşündüm zaten. Anlaması zor, anladıktan sonra yapması kolay bir konu. Örneklere geçince anlayacaksınız. Ben işin mantığı kısmında bahsettiğim kavramların açıklamasını kısa tuttum fakat şunu bilin. Eğer bu yöntemi iyi bir şekilde öğrenmek istiyorsanız o konuları iyi bilmelisiniz. Ayrıca genel olarak kriptografide modüler matematik çok kullanılıyor.

Şifreleme işlemi için örnekler oluşturalım.

Örnek 1:

 süper artımlı dizi = [1, 2, 4, 8, 16, 32]
n = 3, m = 100
1 * 3 mod 100 = 3
2 * 3 mod 100 = 6
4 * 3 mod 100 = 12
8 * 3 mod 100 = 24
16 * 3 mod 100 = 48
32 * 3 mod 100 = 96
açık anahtar = [3, 6, 12, 24, 48, 96]
düz metin = 100100001001100000
6'lı bloklara ayrılmış hali:
100100, 001001, 100000
100100 [3, 6, 12, 24, 48, 96]
1 * 3 + 0 * 6 + 0 * 12 + 1 * 24 + 0 * 48 + 0 * 96 = 27
001001 [3, 6, 12, 24, 48, 96]
0 * 3 + 0 * 6 + 1 * 12 + 0 * 24 + 0 * 48 + 1 * 96 = 108
100000 [3, 6, 12, 24, 48, 96]
1 * 3 + 0 * 6 + 0 * 12 + 0 * 24 + 0 * 48 + 0 * 96 = 3
şifreli metin = 27 108 3
 (

Gördüğünüz üzere, şifrelemek aslında çok zor değil. Temel aritmetik ve az miktar modüler matematik bilgisi yeterli oluyor. Size burada bir tavsiyede bulunacağım. Özellikle kriptografi alanı için geçerli bu bence. Her zaman adım adım gidin ve planınız olsun, ben bir kriptograf değilim. Sadece bu konulara ilgi duyan birisiyim. Satır satır yazmamın nedeni bunlara bakıp analiz yapabilmeniz. Adım adım. Kendinizin anlayacağı şekilde bir akış şeması oluşturun. Mesela üstteki sarı kısma bakarak yaptım ben. Ayrıca eğer matematiğinizi geliştirmek istiyorsanız, özellikle temel aritmetik konularında hızlanmak ve sayısal yeteneğinizin artmasını istiyorsanız işlemleri aklınızdan yapın ve çeşitli taktikler geliştirin. Süreden tasarruf edin. Birisi bir işlemi 10 saniyede yapıyorsa 5 saniyesini kontrole ayıracaktır. Fakat siz, 5 saniye işleme 5 saniye kontrole ayırırsanız hem işlemden emin olursunuz hem de zamanla kontrol etme süreniz de kısalır.

Örnek 2:

 süper artımlı dizi veya özel anahtar = [2, 5, 8, 17, 33, 70]
n = 13, m = 140
2 * 13 mod 140 = 26
5 * 13 mod 140 = 65
8 * 13 mod 140 = 104
17 * 13 mod 140 = 81
33 * 13 mod 140 = 9
70 * 13 mod 140 = 70
açık anahtar = [26, 65, 104, 81, 9, 70]
düz metin = 110100.100110.001100
6'lı bloklara ayıralım.
110100, 100110, 001100
110100 [26, 65, 104, 81, 9, 70]
1 * 26 + 1 * 65 + 0 * 104 + 1 * 81 + 0 * 9 + 0 * 70 = 172
100110 [26, 65, 104, 81, 9, 70]
1 * 26 + 0 * 65 + 0 * 104 + 1 * 81 + 1 * 9 + 0 * 70 = 116
001100 [26, 65, 104, 81, 9, 70]
0 * 26 + 0 * 65 ' 1 * 104 + 1 * 81 + 0 * 9 + 0 * 70 = 185
şifreli metin = 172 116 185

Aynı şekilde, bu sefer modülüs seçimine dikkat ettim. Bu örnekleri inceleyin. Son bir örnek daha vereceğim ve işin kanımca komplike kısmına geçeceğim, deşifreleme kısmına.
Örnek 3:

 özel anahtar = [1, 3, 6, 14, 26, 54]
n = 7, m = 110
1 * 7 mod 110 = 7
3 * 7 mod 110 = 21
6 * 7 mod 110 = 42
14 * 7 mod 110 = 98
26 * 7 mod 110 = 72
54 * 7 mod 110 = 50
açık anahtar = [7, 21, 42, 98, 72, 48]
düz metin = 100100111000000010
6'lı bloklara ayıralım.
100100, 111000, 000010
100100 [7, 21, 42, 98, 72, 48] 
1 * 7 + 0 * 21 + 0 * 42 + 1 * 98 + 0 * 72 + 0 * 48 = 105
111000 [7, 21, 42, 98, 72, 48]
1 * 7 + 1 * 21 + 1 * 42 + 0 * 98 + 0 * 72 + 0 * 48 = 70
000010 [7, 21, 42, 98, 72, 48]
0 * 7 + 0 * 21 + 0 * 42 + 0 * 98 + 1 * 72 + 0 * 48 = 72
şifreli metin = 105 70 98

Örnekler çoğaltılabilir. Benim için epey keyifli bir uğraş. Bir yerden sonra oyuna dönüşüyor ve eğlenceli hale gelmeye başlıyor.
Deşifreleme işlemi için örnekler oluşturalım.
Şimdi işin biraz daha zor kısmına geçiyoruz. Deşifreleme işlemini anlamak benim için de zordu. Çünkü şifreleme işleminde birkaç aritmetik işlem yapıp kurtuluyordun fakat deşifreleme işlemi için bunu söyleyemiyoruz. Bu arada deşifreci, N ve M değerlerini bilmek zorundadır fakat bunları bulmanın yolunu ben bulamadım. Araştırdığımda da bulamadım, bu yüzden bunları önceden bilmemiz gerekir.

Örnek 1:

süper artımlı dizi = [1, 2, 4, 8, 16, 32]
n = 3, m = 100
şifreli metin = 27 108 3
3 * x mod 100 = 1
x = 67
67 * 27 mod 100 = 9, 9'u arayalım ve bulduk! 8 + 1 = 9. 8 ve 1'in olduğu yerlere 1 koyalım, kalan yerlere 0.
100100
67 * 108 mod 100 = 36, 36'yı arayalım ve bulduk! 32 + 4 = 36. 34 ve 4'ün olduğu yerlere 1 koyalım, kalan yerlere 0.
001001
67 * 3 mod 100 = 1, 1'i arayalım ve bulduk! 1'in olduğu yere 1 koyalım, kalan yerlere 0.
100000
İşte şifresiz metnimiz:
100100001001100000

Nasıl? Keyifli mi Keyiflidir. Anlaması zor, anladıktan sonra yapması kolay. Yaklaşık 4. saatime denk geliyorum bunu hazırlıyorken, ilk başta yaptığım bir hata yüzünden yarım saat sorunu düzeltmeye çalıştım. Epey yorucu olsa da keyifli. Bunları yaptıkça ve doğru sonucu buldukça keyifleneceksiniz. Daha fazlasını yapmaya şevkleneceksiniz. İlk başta her şey zordur. Mantığını kavradıktan sonra ortaokul matematiğinden fazla olmadığını anlıyoruz. Haydi devam edelim.
Örnek 2:

süper artımlı dizi = [2, 5, 8, 17, 33, 70]
n = 13, m = 140
şifreli metin = 172 116 185
13 * x mod 140 = 1.
x = 97
97 * 172 mod 140 = 24, 24'ü özel anahtarımızda arayalım ve bulduk! 2 + 5 + 17 = 24 Şimdi bu sayıların olduğu yere 1, kalanlara 0 koyalım.
110100
97 * 116 mod 140 = 52, 52'yi özel anahtarımızda arayalım ve bulduk! 2 + 17 + 33 = 52 Şimdi bu sayıların olduğu yere 1, kalanlara 0 koyalım.
100110
97 * 185 mod 140 = 25, 25'i özel anahtarımızda arayalım ve bulduk! 8 + 17 = 25 Şimdi bu sayıların olduğu yere 1, kalanlara 0 koyalım.
001100
İşte şifresiz metnimiz:
110100100110001100

Örnek 3:

özel anahtar = [1, 3, 6, 14, 26, 54]
n = 7, m = 110
şifreli metin = 105 70 98
7 * x mod 110 = 1
x = 63
63 * 105 mod 110 = 15, 15'i özel anahtarımızda arayalım ve bulduk! 1 + 14 = 15 Şimdi bu sayıların olduğu yere 1, kalanlara 0 koyalım.
100100
63 * 70 mod 110 = 10, 10'u özel anahtarımızda arayalım ve bulduk! 1 + 3 + 6 = 10 Şimdi bu sayıların olduğu yere 1, kalanlara 0 koyalım.
111000
63 * 72 mod 110 = 26, 26'yı özel anahtarımızda arayalım ve bulduk! Şimdi 26'nın olduğu yere 1, kalanlara 0 koyalım.
000010
İşte şifresiz metnimiz:
100100111000000010

6-) Sonsöz

Evet, bu kadardı. Biraz daha ileri düzeyleri var elbette. Örneğin çarpımsal tersleri bulmak için genişletilmiş öklid algoritması denilen bir algoritma var. Ancak buna girmedim çünkü anlaşılmasının basit olmasını istedim. Örneğin bunun daha da ileri seviyesi, ASCII kullanarak harfleri ikili sayı sistemine çevirip belirli bir yazıyı bu yöntemle şifrelemek. Bunu yaparsanız bunda çok iyi gelişirsiniz bu arada. Tavsiye ederim ancak yorucu. Zaten eğer gidip NSA'in kripto bölümünde (Dan Brown'dan esintiler ) çalışmak istemiyorsanız bunlarda ustalaşmaya gerek yok ki artık bu yöntem epey eskide kaldı. Zaten halktan birinin çok basitçe bunu çözebiliyor olması bunun zayıf bir şifre olduğunu gösteriyor. Fakat bu ilk genel açık anahtarlı algoritma olduğundan anlamak bence önemli. Ayrıca bunları yapmak keyifli ve beynin Prefrontal Korteks, Parietal Lob, Temporal Lob ve Hipokampüs bölümlerini çalıştırıyor. Çok da uzatmaya gerek yok, isterseniz siz de yorumlara bir örnek yazabilirsiniz. Bunu yazmak yaklaşık 5 6 saat sürdü ve iki güne yaydım, normalde bugün sabah saatlerinde yayınlanacaktı ancak bir talihsizlik oldu. Her neyse, benim için epey keyifliydi. Umarım sizin için de keyifli olmuştur.

7-) Kaynakça

geeksforgeeks.com
chatgpt.com