Şifreleme algoritması GOST 28147-89. Basit değiştirme yöntemi. - WASM.RU'yu arşivle

“Hayattayken ölme, şu dünyaya bir bak.
Buradaki pek çok kişinin ölü bir ruhu var - içlerinde ölüler.
Ama öyle olmadıklarını bilmeden yürür ve gülerler,
Ölüm saatini aceleye getirme,” dedi bana.

Aria, "Orada Yüksek"

2.1 Feistel ağları.
2.2 Blok şifre GOST 28147-89

3.1 Anahtar bilgi
3.2 Kripto dönüşümünün ana adımı

3.3 Temel döngüler:“ 32-Z” , “ 32-R” .

4.1 Kripto dönüşümünün ana adımının uygulanması
4.2 Algoritmanın hızını artırmak
5. Anahtar bilgi gereksinimleri
6. kullanılmış literatür listesi
7. Teşekkürler.

Tanıtım.

Bu belge, GOST 28147-89 şifreleme algoritmasını en basit, ancak yine de teknik olarak yetkin bir dille değiştirmek için bir yöntemi açıklama girişimidir. İlk altı noktayı okuduktan sonra, okuyucu bunu nasıl yaptığım hakkında fikrini verecektir.

Çalışmamın daha fazla fayda sağlaması için kullanılmış literatür listesinde belirtilen yazarların eserleri ile kendinizi donatmanızı tavsiye ederim. Ayrıca, bir hesap makinesinin işlemi hesaplamak için bir işlevi olması önerilir. XOR dan beri makaleyi okumak, okuyucunun bu şifreleme algoritmasını incelemeyi amaçladığını varsayar. Referans olarak da uygun olsa da, bu makaleyi tam olarak bir eğitim makalesi olarak yazdım.

Blok şifreler hakkında ön bilgiler.

Algoritmaya bakmaya başlamadan önce, bu tür şifrelerin yaratılış tarihine aşina olmamız gerekir. Algoritma, mimarisinde bilginin sınırlı sayıda bloğa bölündüğü blok şifreleri kategorisine aittir, sonuncusu doğal olarak tamamlanmayabilir. Şifreleme işlemi, şifreyi oluşturan tam bloklar üzerinde gerçekleşir. Son blok, eksikse, bir şeyle desteklenir (aşağıda tamamlamanın nüansları hakkında söyleyeceğim) ve tam bloklarla aynı şekilde şifrelenir. Bir şifre ile, kullanıcının şifreleme için gönderdiği belirli bir miktarda veri üzerinde hareket eden şifreleme işlevinin sonucunu kastediyorum. Başka bir deyişle, bir şifre, şifrelemenin nihai sonucudur.

Blok şifrelerin gelişiminin tarihi, IBM'in bilgisayar iletişim kanalları aracılığıyla veri iletirken bilgileri koruma ihtiyacını fark ederek, elektronik ağlarda bilgilerin korunmasına yönelik kendi araştırma programını başlattığı 70'lerin başlangıcı ile ilişkilidir. kriptografi dahil.

Simetrik anahtar kullanım şemasına sahip şifreleme sistemlerini araştırmaya başlayan IBM'den bir grup araştırmacı - geliştiriciler, Dr. Horst Feistel.

2.1 Feistel ağları

Feistel tarafından klasik literatürde önerilen yeni şifreleme yönteminin mimarisine "Feistel Mimarisi" denir, ancak şu anda Rus ve yabancı literatürde daha yerleşik bir terim kullanılmaktadır - "Feistel'in ağı" veya Feistel'in Ağı. Daha sonra, "Lucifer" şifresi bu mimari üzerine inşa edildi - bu daha sonra yayınlandı ve genel olarak kriptografiye yeni bir ilgi dalgasına neden oldu.

"Feistel ağı" mimarisi fikri şu şekildedir: bilgi giriş akışı, n'nin çift sayı olduğu n bitlik bloklara bölünür. Her blok iki parçaya bölünür - L ve R, daha sonra bu parçalar, j-inci aşamanın sonucunun önceki j-1 aşamasının sonucuyla belirlendiği yinelemeli bir blok şifresine beslenir! Bu bir örnekle gösterilebilir:

Pirinç. 1

Burada, A işlevi, blok şifrelemenin ana eylemidir. Bir XOR işlemi gibi basit bir eylem olabilir veya bir dizi basit eylemin bir dizisi olarak daha karmaşık bir forma sahip olabilir - modulo ekleme, sola kaydırma, eleman değiştirme vb., birlikte ele alındığında, bu basit eylemler oluşur. sözde - kripto dönüşümünün ana adımı.

Unutulmamalıdır ki, fonksiyonun çalışmasının kilit unsurları, anahtar unsurların temini ve XOR işlemidir ve bu işlemlerin çalışmasının ne kadar iyi düşünüldüğüne bakılırsa, bir bütün olarak şifrenin kriptografik gücünden bahseder.

Feistel ağları fikrinin nihayet netleşmesi için, gösterilen en basit durumu düşünün. pilav. 1, burada A işlevinde - “mod 2” (“xor”) işlemleri olacak, ancak bu en basit bir durumda, daha ciddi bir durumda, örneğin, ulusal öneme sahip bilgileri gizlemek, A işlevi daha karmaşık olabilir (gördüğüm kadarıyla, A işlevi gerçekten çok karmaşıktır):

İlk veri:

L = 1110b, R = 0101, K = 1111b

bir şifre al

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Eylemlerimizi açıklayalım:

1. Bu işlem ek mod 2'dir 4. Pratikte, böyle bir işlem, iki sayı eklememiz ve 5. basamağa aktarımı görmezden gelmemiz gereken basit toplama işlemine indirgenir. Bir sayının ikili gösteriminin basamaklarının üstüne üsler koyarsak, beşinci basamağın üzerinde dört üs olacağından, işlemimizin eylemlerini gösteren aşağıdaki şekle bir göz atalım:

Pirinç. 2

Burada üsleri ok ile gösterdim gördüğünüz gibi sonuç 10100 olmalıydı fakat mod 2 4 işlemi sırasında transfer yok sayıldığı için 0100 alıyoruz.

2. Literatürdeki bu işlem mod 2 olarak adlandırılır, Assembly dilinde komut ile gerçekleştirilir. XOR... Ancak daha doğru adı mod 2 1'dir. Bu benzersiz işlem olmadan, hızlı, kolay uygulanabilir bir şifreleme algoritması oluşturmak ve aynı zamanda kriptografik olarak hala oldukça güçlü olması pek mümkün değildir. Bu operasyonun benzersizliği, kendisinin tam tersi olması gerçeğinde yatmaktadır! Örneğin, A sayısı B sayısı ile XORlanırsa, sonuç olarak B elde ederiz, gelecekte A'nın önceki değerini elde etmek için B ve C sayılarını birbirleri arasında reXOR yapmak yeterlidir!

Bu işlemde 1110 ve 0100 sayılarıyla 1010 elde ettik, 1110'u geri almak için 0100 ve 1010 sayılarını yeniden XOR yapmak yeterli! Bu işlemle ilgili daha fazla ayrıntı, siteye ekli makalede bulunabilir. www.wasm.ru, « için temel bir rehberCRC_ hata algılama algoritmaları» yazar kim Ross N Williams... Bu işte bir nokta var - “ 5. Tireleme olmadan ikili aritmetik". Bu yazıda operasyon anlatılmaktadır. xor! Haykırıyorum çünkü bu yazıda bu işlem o kadar planlanmış ki okuyucu sadece bu işlemin nasıl çalıştığını anlamakla kalmıyor, hatta başlatıyor. gör, duy ve hisset!

3. Bu işlem, şifre çözme sırasında şifrelemeden ilk değerlerin alınabilmesi için gereklidir.

2.2 Blok şifre GOST 28147-89

GOST 28147 - 89 şifreleme algoritması, seçilen bilgi bloğunun iki bölümünün eşit boyutta olduğu dengeli Feistel ağlarının mimarisine göre çalışan blok şifreleri kategorisine aittir. Algoritma, KGB'nin sekizinci bölümünün derinliklerinde geliştirildi, şimdi FAPSI'ye dönüştürüldü ve 1989'da SSCB altında Rusya Federasyonu'nun şifreleme standardı olarak kabul edildi.

Algoritmanın bu yönteminin çalışması için bilgiyi 64 bitlik bloklara bölmek gerekir. Şifreleme sistemine aşağıdaki anahtar bilgileri oluşturun veya girin: anahtar ve ikame tablosu. Şifreleme için anahtar ve ikame tablosunun seçimi çok ciddiye alınmalıdır, çünkü bu, bilgilerinizin güvenliğinin temelidir. Anahtara hangi gereksinimlerin getirildiği ve ikame tablosu hakkında "Anahtar bilgileri için gereksinimler" maddesine bakın.

Yöntemi düşünürken buna odaklanmayacağız, çünkü Bu yazı, yukarıda da belirttiğim gibi, okuyucuya bu şifreleme algoritmasının basit bir şekilde değiştirilmesi yöntemiyle verilerin nasıl şifreleneceğini öğretmek amacıyla yazılmıştır, ancak bu konuya yazının sonunda mutlaka değineceğiz.

Teorik minimum.

3.1 Anahtar bilgiler

Yukarıda söylediğim gibi, aşağıdakiler veri şifrelemede aktif olarak yer almaktadır:

3.1.1. Anahtar, her biri 32 bit olan sekiz öğeden oluşan bir dizidir. Aşağıda, K sembolü ile göstereceğiz ve içerdiği elemanlar k1, k2, k3, k4, k5, k6, k7, k8'dir.

3.1.2 İkame tablosu - bundan sonra sekiz satır ve on altı sütundan oluşan bir matris - Hij. i satırı ve j sütununun kesişimindeki her eleman 4 bit kaplar.

3.2 Kripto dönüşümünün temel adımı

Şifreleme sürecindeki ana adım, kripto dönüşümünün ana adımıdır. Bu, belirli bir algoritmaya göre verileri şifrelemek için yapılan bir eylemden başka bir şey değildir, yalnızca geliştiriciler çok hantal bir isim sunmuştur.

Şifrelemeye başlamadan önce blok, her biri 32 bit olan iki parça L ve R'ye bölünür. Anahtar eleman seçilir ve ancak o zaman bloğun bu iki parçası, anahtar eleman, ikame tablosu ana adım fonksiyonuna beslenir, ana adımın sonucu, aşağıda tartışılacak olan temel döngünün bir yinelemesidir. sonraki paragraf. Ana adım aşağıdakilerden oluşur:

1. R bloğunun ilave kısmı, anahtar eleman K mod 2 32 ile toplanır. Yukarıda benzer bir işlemi tanımladım, burada aynı şey sadece üs "4" değil, "32" - bu işlemin sonucu gelecekte Smod olarak gösterilecektir.
2. Daha önce elde edilen Smod sonucunu dört bitlik s7, s6, s5, s4, s3, s2, s1, s0 öğelerine bölün ve değiştirme işlevine besleyin. Değiştirme aşağıdaki gibidir: Smod - si öğesi seçilir, en baştan en düşük öğeyle başlarız ve değiştirme tablosundaki değerle i ile değiştiririz - s öğesinin değeriyle gösterilen satır ve sütun ben. s i +1 elemanına geçiyoruz ve aynı şekilde ilerliyoruz ve son elemanın Smod değerini değiştirene kadar devam ediyoruz - bu işlemin sonucu Ssimple olarak gösterilecektir.
3. Bu işlemde Ssimple değerini döngüsel olarak 11 bit sola kaydırıyoruz ve Srol elde ediyoruz.
4. L bloğunun ikinci bölümünü seçiyoruz ve Srol ile mod 2'yi ekliyoruz, sonuç olarak Sxor'umuz var.
5. Bu aşamada, L bloğunun parçası, R parçasının değerine eşit olur ve sırayla R parçası, Sxor'un sonucu ile başlatılır ve bu noktada ana adımın işlevi tamamlanır!

3.3 Temel döngüler: "32-З", "32-Р".

Bilgiyi şifrelemek için 64 bitlik bloklara bölmek gerekir, tabii ki son blok 64 bitten küçük olabilir. Bu gerçek, bu "kolay değiştirme" yönteminin Aşil topuğudur. 64 bit'e eklenmesi, şifre kodunun şifreleme gücünü ve bu hassas yere, bilgi dizisinde varsa, ancak mevcut olmayabilir (örneğin, 512 baytlık bir dosya) şifreleme gücünü artırmak için çok önemli bir görev olduğundan! ), Kişi büyük bir sorumlulukla davranmalıdır!

Bilgileri bloklara böldükten sonra anahtarı öğelere ayırmalısınız:

K = k1, k2, k3, k4, k5, k6, k7, k8

Şifrelemenin kendisi, sözde temel döngülerin kullanımından oluşur. Bu da, kripto dönüşümünün n'inci temel adımlarını içerir.

Temel döngüler etiketlenmiştir, nasıl yazılır: n - m. Burada n, temel döngüdeki kripto dönüşümünün temel adımlarının sayısıdır ve m, temel döngünün "türü"dür, yani. ne hakkında konuşuyoruz, "Z" şifrelemesi veya "R" veri şifrelemesi hakkında.

Temel şifreleme döngüsü 32-З, kripto dönüşümünün 32 temel adımından oluşur. Bir N bloğu ve K anahtarının bir öğesi, adımın eylemlerini uygulayan işleve beslenir ve ilk adım k1 ile gerçekleşir ve ikincisi k2 öğesiyle elde edilen sonucun üzerinde, vb. aşağıdaki şemaya göre:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

32-P için şifre çözme işlemi benzer şekilde gerçekleşir, ancak anahtar öğeler ters sırada verilmiştir:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Uygulama.

4.1 Kripto dönüşümünün ana adımının uygulanması

Bilginin nasıl şifreleneceği teorisini öğrendikten sonra, pratikte şifrelemenin nasıl gerçekleştiğini görmenin zamanı geldi.

İlk veri:

N = 0102030405060708h bilgi bloğunu alın, burada L ve R parçaları eşittir:

L = 01020304h, R = 05060708h, anahtarı alalım:

K = ' 28 gibi zw37 q839 7342ui23 8e2t wqm2 ewp1 '(bunlar ASCII - kodlardır, onaltılık gösterimi görüntülemek için, bu dosyayı Total Commander'da tuşuna basarak görüntüleme modunda açabilirsiniz. F3"Ve sonra anahtar" 3 "). Bu anahtarda, elemanların değerleri şöyle olacaktır:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = "ui23", k6 = "8e2t", k7 = "wqm2", k8 = "ewp1"

Ayrıca aşağıdaki ikame tablosunu da alın:

Pirinç. 3

Burada satırlar 0'dan 7'ye, sütunlar 0'dan F'ye kadar numaralandırılmıştır.

Bir uyarı:İkame tablosuna sahip anahtar dahil tüm bilgiler, algoritmayı dikkate almak için örnek olarak alınmıştır!

"İlk verileri" kullanarak, kripto dönüşümünün ana adımının eyleminin sonucunu elde etmek gerekir.

1. R = 05060708h bölümünü ve k1 = 'as28' anahtar öğesini seçin, onaltılık biçimde anahtar öğe şöyle görünecektir: 61733238h. Şimdi toplama işlemi mod 2 32'yi yapıyoruz:

Pirinç. 4

Şekilde gördüğünüz gibi kırmızı ile işaretlenmiş ve üslü 33 bitlik bir transferimiz olmadı. 32 ". Ve eğer başka R değerlerine ve anahtar öğeye sahip olsaydık, bu pekala olabilirdi ve o zaman onu görmezden gelirdik ve sadece sarı ile işaretlenmiş bitleri kullanırdık.

Bu işlemi assembler komutu ile gerçekleştiriyorum Ekle:

; eax = R, ebx = 'as28'

Bu işlemin sonucu Smod = 66793940h

2. Şimdi en karmaşık işlem, ancak yakından bakarsanız, artık ilk bakışta göründüğü kadar korkunç değil. Smod'u aşağıdaki gibi hayal edelim:

Pirinç. 5

Şekilde Smod öğelerini görselleştirmeye çalıştım ama yine de açıklayayım:

s0 = 0, s1 = 4, s2 = 9, vb.

Şimdi, en düşük s0 elemanından başlayarak değiştirmeyi yapıyoruz. Paragrafı hatırlamak " 3.2 Kripto dönüşümünün temel adımı»I - satır, s ben - sütun, sıfır satırındaki ve sıfır sütundaki değeri arayın:

Şekil 6

Yani Smod'un şu anki değeri 6679394 değil 0 ve 6679394 5 H.

S1'i değiştirmeye devam ediyoruz, yani. dört. İlk satırı ve dördüncü sütunu kullanma (s1 = 4!). Resme bakıyoruz:

Pirinç. 7

Şimdi zaten 667939 değil Smod'un değeri 4 5 saat, 667939 2 5 saat Şimdi değiştirme algoritmasının okuyucu için açık olduğunu varsayıyorum ve Ssimple'ın nihai sonucunun aşağıdaki değere sahip olacağını söyleyebilirim - 11e10325h.

Genişletilmiş tablodan bahsettikten sonra bir sonraki paragrafta bunun montajcı komutları şeklinde uygulanmasının en kolay olduğundan bahsedeceğim.

1. Ortaya çıkan Ssimple değerini 11 bit sola kaydırmalıyız.

Pirinç. sekiz

Gördüğünüz gibi, bu eylem oldukça basittir ve montaj dilinin bir komutuyla uygulanır - rol ve bu Srol işleminin sonucu 0819288Fh'dir.

4. Şimdi bilgi bloğumuzun L kısmı Srol değeri ile XORlanacak. w2k sp4'ten bir hesap makinesi alıyorum ve Sxor = 091b2b8bh alıyorum.

5. Bu eylem sondur ve biz basitçe L parçasının değerini R'yi atadık, temizledik ve L bölümünü Sxor değeriyle başlattık.

Son sonuç:

L = 091b2b8bh, R = 01020304h

4.2 Algoritmanın hızını artırma

Şimdi algoritmayı hız için optimize etmekten bahsedelim. Bir projeyi uygulama sürecinde, kayıtlarla çalışan bir programın bellekten çok daha hızlı çalıştığını hesaba katmak gerekir ve burada bu yargı da çok önemlidir, çünkü bir bilgi bloğu üzerinden 32 şifreleme eylemi!

Programımda şifreleme algoritmasını uyguladığımda aşağıdakileri yaptım:

1. Blok L'nin eax kaydına ve R'den edx'e seçilen kısmı.

2. Genişletilmiş anahtarın adresi ile başlatılan esi kaydında, daha fazlası aşağıdadır.

3. ebx kaydında, genişletilmiş ikame tablosunun adresinin değeri atanır, aşağıda daha fazlası

4. Öğe 1, 2, 3'ün bilgileri, duruma bağlı olarak 32 - З veya 32 - Р temel döngüsünün işlevine aktarıldı.

Paragraftaki kilit unsurların akış şemasına bakarsanız " Temel döngüler: "32-З", "32-Р"", O zaman 32 - 3 temel döngüsü için anahtarımız aşağıdaki gibi temsil edilebilir:

K32-Z =

"As28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"As28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"Ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28"

Onlar. başlangıçta k1, k2, k3, k4, k5, k6, k7, k8 vardır - ‘ olarak28','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2T ','wqm2 ','ewp1' bu dizi üç kez tekrarlanır. Sonra elemanlar ters sırada gider, yani: k8, k7, k6, k5, k4, k3, k2, k1 - "Ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28".

Dizideki elemanları 32 - Z'de beslenmeleri gereken sıraya göre önceden düzenledim. Böylece anahtar teslim bazında gereken hafızayı arttırdım ama gerek duymadığım bazı düşünme süreçlerinden kendimi kurtardım ve hızı arttırdım. algoritmanın, bellek erişim süresini azaltarak! Burada sadece 32 - З için anahtarı tanımladım, 32 - Р döngüsü için aynısını yaptım, ancak paragrafta da tanımladığım farklı bir tedarik elemanı şeması kullandım " Temel döngüler: “32-Z”, “32-P».

Şimdi yukarıda söz verdiğim gibi değiştirme fonksiyonunun uygulamasını açıklamanın zamanı geldi. Daha önce tarif edemedim, çünkü bu, yeni bir kavramın - genişletilmiş bir ikame tablosunun - tanıtılmasını gerektirir. Sana ne olduğunu açıklayamam. Bunun yerine, size göstereceğim ve siz kendiniz formüle edeceksiniz, bu nedir - genişletilmiş bir ikame tablosu mu?

Dolayısıyla, genişletilmiş bir ikame tablosunun ne olduğunu anlamak için bir ikame tablosuna ihtiyacımız var, örneğin, Şekil 1'de gösterileni alacağım. 3.

Örneğin, 66793940h numarasını değiştirmemiz gerekiyordu. Bunu şu şekilde sunacağım:

Pirinç. dokuz

Şimdi s1, s0, elemanlarını alırsak, yani. en az anlamlı bayt, değiştirme işlevinin sonucu 25 saat olacaktır! Paragrafta alıntıladığım Andrey Vinokurov'un makalesini okuduktan sonra " kullanılmış literatür listesi", Aslında, iki satır alırsanız, bir dizi alabileceğinizi ve montajcı komutunu kullanarak yedek öğeleri hızlı bir şekilde bulmanızı sağladığını görüyorsunuz. xlat. Başka bir şekilde daha hızlı mümkün olduğunu söylüyorlar, ancak Andrey Vinokurov, GOST'un uygulanması için hızlı algoritmaları araştırmak için yaklaşık dört yıl harcadı! Zaten bir tane varken tekerleği yeniden icat etmen gerektiğini düşünmüyorum.

Yani, dizi hakkında:

İlk iki satırı sıfır alalım ve ilkini 256 baytlık bir dizi oluşturalım. Şimdi, 00h'yi dönüştürmek gerekirse, sonucun 75h olacağına dair bir tuhaflık gözlemliyoruz (Şekil 3'e göre) - bu değeri 00h ofsetindeki diziye koyarız. 79h ikame fonksiyonunun sonucu olan 01h değerini alıyoruz, onu 01 ofsetindeki diziye koyuyoruz ve böylece 0FFh'ye kadar devam ediyoruz, bu bize 0FCh'yi verecek ve 0FFh ofsetinde diziye koyacağız. Böylece ilk satır grubu için genişletilmiş bir ikame tablosu elde ettik: ilk ve sıfır. Ama yine de üç grup var: ikinci sayfa 2, sayfa 3, üçüncü sayfa 4, sayfa 5, dördüncü sayfa 6, sayfa 7. Bu üç grupla ilkiyle aynı şekilde ilgileniyoruz. Sonuç, genişletilmiş bir ikame tablosudur!

Artık değiştirme işlemini gerçekleştirecek bir algoritma uygulayabiliriz. Bunu yapmak için Andrei Vinokurov'un sayfasında yayınladığı kaynak kodlarını alıyoruz, bkz. " bibliyografya».

lea ebx, extension_table_simple

mov eax, [değiştirilecek numarayı girin]

ebx, 100h ekle; sonraki iki düğüme atla

alt ebx, 300h; böylece gelecekte ebx tabloya işaret eder

Şimdi bir özellik daha, önceki eylemlerle sadece değiştirmekle kalmadık, aynı zamanda sayıyı 8 bit sola kaydırdık! Sayıyı 3 bit daha sola kaydırmamız gerekiyor:

ve operasyon rolü eax, 11'in sonucunu alıyoruz!

Optimizasyon üzerine daha fazla bir şey ekleyemem, vurgulayabileceğim tek şey yukarıda söylediklerim - kayıtları bellek erişiminden daha sık kullanın. Sanırım bu sözler sadece yeni başlayanlar için, deneyimli ve benim sözlerim olmadan mükemmel bir şekilde anlıyor.

Anahtar bilgiler için gereksinimler.

Andrey Vinokurov'un makalesinde belirtildiği gibi, anahtar iki kritere göre seçilir:

Bitlerin eşit olası dağılımı için 1 ve 0 değerleri arasındaki kriter. Genellikle, bitlerin eşit olası dağılımı için kriter Pearson kriteridir ("ki-kare").

Bu, prensipte herhangi bir sayının yapabileceği bir anahtar anlamına gelir. Yani, anahtarın bir sonraki biti oluşturulduğunda, bunun bir veya sıfır tarafından başlatılma olasılığı 50/50'dir!

Lütfen anahtarın her biri 32 bit olan sekiz öğeden oluştuğunu unutmayın, bu nedenle anahtarda yalnızca 32 * 8 = 256 bit vardır ve olası anahtar sayısı 2 256'dır! Bu seni etkilemiyor mu?

Seri kriteri.

Paragrafta verdiğim anahtarımıza bakarsak " 4.1 Kripto dönüşümünün ana adımının uygulanması», O zaman aşağıdaki gösterimin geçerli olduğunu fark edeceksiniz:

Pirinç. on

Bir cümlede, k 1 değeri, k 2'de veya anahtarın başka hiçbir öğesinde tekrarlanmamalıdır.

Yani, şifreleme algoritmasını göz önünde bulundurarak seçtiğimiz anahtar, yukarıdaki iki kriteri tam olarak karşılamaktadır.

Şimdi ikame tablosunun seçimi hakkında:

Şimdi doğru ikame tablosunun nasıl seçileceğinden bahsedelim. Değiştirme tablolarının seçimi için temel gereksinim, her biri 4 bit boyutunda olan öğelerin “tekrarlanamazlığı” olgusudur. Yukarıda gördüğünüz gibi, ikame tablosunun her satırı 0h, 1h, 2h, 3h,…, 0fh değerlerinden oluşur. Bu nedenle temel gereksinim, her satırın 0h, 1h, 2h, ..., 0fh değerlerini ve bu tür her bir değeri bir kopyada içermesidir. Örneğin, sıra:

1 2 3 4 5 6 7 8 9 A B C D E F

Bu gereksinime tamamen uygundur, ancak yine de! Dize gibi bir dizinin seçilmesi önerilmez. Çünkü böyle bir dizgeye dayanan bir fonksiyonun girişine bir değer beslerseniz, çıktıda aynı değeri alırsınız! Bana inanmıyor musun? Ardından, bir ikame tablosu olarak 332DA43Fh sayısını ve bu tür sekiz satırı alın. Değiştirme işlemini gerçekleştirin ve sizi temin ederim, çıktı 332DA43Fh sayısı olacaktır! Yani, işlemin girişine gönderdiğiniz ile aynı! Ve bu şifrelemede iyi bir formun işareti değil, değil mi?

Bu bir gereklilikti, bir sonraki kriter şunu söylüyor - çıkış bloğunun her biti, giriş bloğunun her bir bitinden istatistiksel olarak bağımsız olmalıdır!

Nasıl daha basit görünüyor? Ve örneğin, yukarıdaki sayıdan s0 = 0Fh, 01111b öğesini nasıl seçtik. Şimdi ilk biti bir veya sıfırla değiştirme olasılığımız 0,5! İkinci, üçüncü ve dördüncü bitleri, her bir biti ayrı ayrı birler veya sıfırlarla değiştirme olasılığı da 0, 5'tir. s1 = 0Eh seçerken, sıfır bit olmamız olasılığı ve bu "0". , sıfır veya bir çok eşittir - 0,5 ile değiştirilecektir! Böylece, bu kritere göre, s0, s1 elemanlarının sıfır bitlerinin yer değiştirmesi arasında bir düzenlilik yoktur! Evet, birleri değiştirebilirsin, ama sıfırları da değiştirebilirsin.

Tabloyu bu kritere göre değerlendirmek için, aşağıdaki formülle hesaplanan bir korelasyon katsayıları tablosu oluşturabilirsiniz:

p = 1 ise, çıkıştaki j bitinin değeri, girişteki herhangi bir bit kombinasyonu için girişteki i bitinin değerine eşittir;

p = -1 ise, o zaman çıkıştaki j bitinin değeri her zaman giriş biti i'nin tersidir;

p = 0 ise, j çıkış biti eşit olasılıkla, giriş biti i'nin herhangi bir sabit değeri için 0 ve 1 değerlerini alır.

Bir satırlık örnek verelim:

Bunu "bileşenlere" ayıralım:

Yukarıdaki formüle göre bir katsayı hesaplayalım. Bunun nasıl yapıldığını anlamayı kolaylaştırmak için daha ayrıntılı olarak açıklayacağım:

Girişte 0. sayının (0) 0. bitini, çıkışta (1) 0. sayının 0. bitini alıyoruz 0 XOR 1 = 1 işlemini yapıyoruz.

Girişte 1. sayının (1) 0. bitini ve çıkışta (1) 1. sayının 0. bitini alıyoruz 1 XOR 1 = 0 işlemini yapıyoruz.

Girişte 2. sayının (0) 0. bitini ve çıkışta (0) 2. sayının 0. bitini alıyoruz 0 XOR 0 = 0 işlemini yapıyoruz.

Girişte 3. sayının (1) 0. bitini ve çıkışta (1) 3. sayının 0. bitini alıyoruz 1 XOR 1 = 0 işlemini yapıyoruz.

Bu dizide art arda XOR işlemleri yaparak sıfır olmayan tüm değerleri sayarız, 6 değerini alırız. Dolayısıyla P 00 = 1- (6/2 4-1) = 0.25. Böylece, çıktıdaki bit 0'ın değerinin, 16'nın 4'ünde girişteki bit 0'ın değerine eşit olduğu ortaya çıktı;

Son oran tablosu:

Korelasyon katsayıları tablosundan görülebileceği gibi, girişteki bit 3, çıkıştaki bit 0'a göre 16'nın 14'ünde ters çevrilir, bu %87,5'tir.Bu artık normal şifreleme sistemleri için kabul edilemez. Bir değişiklik için başka bir örnek verelim:

Katsayı tablosu aşağıdaki gibi olacaktır (yeniden hesaplamanın tembel olmadığı)

Bu tabloda işler daha da kötü - grubun 1. ve 2. bitleri değişmeden kalıyor! Kriptanalyst nereye dönebilir Tüm bu gereksinimler göz önüne alındığında, basit bir arama ("kafa kafa"), belirtilen teoriye karşılık gelen permütasyon tabloları bulundu (bugün - 1276 kombinasyon) İşte bunlardan bazıları:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Kullanılmış literatür listesi.

1. Andrey Vinokurov'un makalesi:

Şifreleme algoritması GOST 28147-89, kullanımı ve uygulanması

Intel x86 platformunun bilgisayarları için.

Şifreleme algoritmasının uygulanması için kaynak kodları da vardır.

1. Horst Feistel'in makalesi:

Kriptografi ve Bilgisayar Güvenliği.

(bir önceki makale ile aynı adreste bulunabilir)

1. Ross N. Williams:

CRC Hata Tespit Algoritmaları için Temel Kılavuz

sitede yayınlandı www.wasm.ru.

Teşekkürler.

www.wasm.ru forumunun tüm ziyaretçilerine şükranlarımı sunmak istiyorum. Ancak şu anda SteelRat olarak bilinen ChS'e, muhtemelen asla anlayamayacağım şeyleri anlamama ve ayrıca paragrafı yazmama yardım ettiği için özellikle teşekkür etmek istiyorum: “ Anahtar bilgi gereksinimleri”, Bu paragrafın ana kısmı onun tarafından yazılmıştır. KSTU çalışanına da derinden müteşekkirim. BİR. Tupolev Anikin Igor Vyacheslavovich ve onun olduğu gerçeği için Chris Kaspersky'den ve talimatları için Volodya / wasm.ru'dan bahsetmemek günah olurdu. Oh, ve ondan alıyorum. Ayrıca Sega-Zero / Callipso'yu not etmek istiyorum, ancak bu aklıma matematiksel bir orman getirdi.

Belki de size söylemek istediklerimin hepsi bu.

Bu makaleyle ilgili herhangi bir eleştiri veya soru ya da sadece tavsiye için minnettar olurum. İletişim bilgilerim: [e-posta korumalı], ICQ - 337310594.

Saygılarımla, Evil's Interrupt.

Not: Bu yazı ile kimseyi geçmeye çalışmadım. GOST çalışmasını kolaylaştırmak amacıyla yazılmıştır ve zorluk yaşıyorsanız, bu benim bundan suçlu olduğum anlamına gelmez. Makul olun ve sabırlı olun, sizin için en iyisi!

“Hayattayken ölme, şu dünyaya bir bak.
Buradaki birçok insanın ölü bir ruhu var - içlerinde ölüler.
Ama öyle olmadıklarını bilmeden yürür ve gülerler,
Ölüm saatini aceleye getirme,” dedi bana.

Aria, "Orada Yüksek"

1. Tanıtım

1. Blok şifreler hakkında ön bilgiler

2.1 Feistel ağları.
2.2 Blok şifre GOST 28147-89

1. teorik minimum

3.1 Anahtar bilgi
3.2 Kripto dönüşümünün ana adımı

3.3 Temel döngüler:“ 32-Z” , “ 32-R” .

1. Uygulama

4.1 Kripto dönüşümünün ana adımının uygulanması
4.2 Algoritmanın hızını artırmak
5.
6. kullanılmış literatür listesi
7. Teşekkürler.

Tanıtım.

Bu belge, GOST 28147-89 şifreleme algoritmasını en basit, ancak yine de teknik olarak yetkin bir dille basitçe değiştirme yöntemini açıklama girişimidir. İlk altı noktayı okuduktan sonra okuyucu, bunu ne kadar iyi yaptığım konusunda fikrini bildirecektir.

Çalışmamın daha fazla fayda sağlaması için kullanılmış literatür listesinde belirtilen yazarların eserleri ile kendinizi donatmanızı tavsiye ederim. Bir hesap makinesinin işlemi hesaplamak için bir işlevi olması da önerilir. XOR dan beri makaleyi okumak, okuyucunun bu şifreleme algoritmasını incelemeyi amaçladığını varsayar. Referans olarak da uygun olsa da, bu makaleyi tam olarak bir eğitim makalesi olarak yazdım.

Blok şifreler hakkında ön bilgiler.

Algoritmaya bakmaya başlamadan önce, bu tür şifrelerin yaratılış tarihine aşina olmamız gerekir. Algoritma, mimarisinde bilginin sınırlı sayıda bloğa bölündüğü blok şifreleri kategorisine aittir, sonuncusu doğal olarak tamamlanmayabilir. Şifreleme işlemi, şifreyi oluşturan tam bloklar üzerinde gerçekleşir. Son blok, eksikse, bir şeyle desteklenir (aşağıda tamamlamanın nüansları hakkında söyleyeceğim) ve tam bloklarla aynı şekilde şifrelenir. Bir şifre ile, kullanıcının şifreleme için gönderdiği belirli bir miktarda veri üzerinde hareket eden şifreleme işlevinin sonucunu kastediyorum. Başka bir deyişle, bir şifre, şifrelemenin nihai sonucudur.

Blok şifrelerin gelişiminin tarihi, IBM'in bilgisayar iletişim kanalları aracılığıyla veri iletirken bilgileri koruma ihtiyacını fark ederek, elektronik ağlarda bilgilerin korunmasına yönelik kendi araştırma programını başlattığı 70'lerin başlangıcı ile ilişkilidir. kriptografi dahil.

Simetrik anahtar kullanım şemasına sahip şifreleme sistemlerini araştırmaya başlayan IBM'den bir grup araştırmacı - geliştiriciler, Dr. Horst Feistel.

2.1 Feistel ağları

Klasik literatürde Feistel tarafından önerilen yeni şifreleme yönteminin mimarisine “Feistel Mimarisi” adı verildi, ancak şu anda Rus ve yabancı literatürde daha yerleşik bir terim kullanılıyor - “Feistel'in ağı” veya Feistel'in Ağı. Daha sonra, "Lucifer" şifresi bu mimari üzerine inşa edildi - bu daha sonra yayınlandı ve genel olarak kriptografiye yeni bir ilgi dalgasına neden oldu.

"Feistel ağı" mimarisi fikri şu şekildedir: giriş bilgi akışı, n'nin çift sayı olduğu n bitlik bloklara bölünür. Her blok iki parçaya bölünür - L ve R, daha sonra bu parçalar, j-inci aşamanın sonucunun önceki j-1 aşamasının sonucuyla belirlendiği yinelemeli bir blok şifresine beslenir! Bu bir örnekle gösterilebilir:

Pirinç. 1

Burada, A işlevi, blok şifrelemenin ana eylemidir. Bir XOR işlemi gibi basit bir eylem olabilir veya bir dizi basit eylemin bir dizisi olarak daha karmaşık bir forma sahip olabilir - modulo ekleme, sola kaydırma, eleman değiştirme vb., birlikte ele alındığında, bu basit eylemler oluşur. sözde - kripto dönüşümünün ana adımı.

Unutulmamalıdır ki, fonksiyonun çalışmasının kilit unsurları, anahtar unsurların temini ve XOR işlemidir ve bu işlemlerin çalışmasının ne kadar iyi düşünüldüğüne bakılırsa, bir bütün olarak şifrenin kriptografik gücünden bahseder.

Feistel ağları fikrinin nihayet netleşmesi için, gösterilen en basit durumu düşünün. pilav. 1, burada A işlevinde - “mod 2” (“xor”) işlemleri olacak, ancak bu en basit bir durumda, daha ciddi bir durumda, örneğin, devlet açısından önemli bilgileri gizlemek, A işlevi daha karmaşık olabilir (gördüğüm kadarıyla, A işlevi gerçekten çok karmaşıktır):

İlk veri:

L = 1110b, R = 0101, K = 1111b

bir şifre al

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Eylemlerimizi açıklayalım:

1. Bu işlem mod 2 4 ilavesidir. Pratikte, böyle bir işlem, iki sayı eklememiz ve 5. basamağa aktarımı görmezden gelmemiz gereken basit toplama işlemine indirgenir. Bir sayının ikili gösteriminin basamaklarının üstüne üsler koyarsak, beşinci basamağın üstünde dört üs olacağından, işlemimizin eylemlerini gösteren aşağıdaki şekle bir göz atalım:

Pirinç. 2

Burada üsleri ok ile gösterdim gördüğünüz gibi sonuç 10100 olmalıydı fakat mod 2 4 işlemi sırasında transfer yok sayıldığı için 0100 alıyoruz.

1. Literatürde bu işlem mod 2 olarak adlandırılır, Assembly dilinde komut ile gerçekleştirilir. XOR... Ancak daha doğru adı mod 2 1'dir. Bu benzersiz işlem olmadan, hızlı, kolay uygulanabilir bir şifreleme algoritması oluşturmak ve aynı zamanda kriptografik olarak hala oldukça güçlü olması pek mümkün değildir. Bu operasyonun benzersizliği, kendisinin tam tersi olması gerçeğinde yatmaktadır! Örneğin, A sayısı B sayısı ile XORlanırsa, sonuç olarak B elde ederiz, gelecekte A'nın önceki değerini elde etmek için B ve C sayılarını aralarında yeniden XOR yapmak yeterlidir!

Bu işlemde 1110 ve 0100 sayılarına sahip 1010 elde ettik, 1110'u geri almak için 0100 ve 1010 sayıları arasında reXOR yapmak yeterli! Bu işlemle ilgili daha fazla ayrıntı, siteye ekli makalede bulunabilir. www.wasm.ru, « için temel bir rehberCRC_ hata algılama algoritmaları» yazar kim Ross N Williams... Bu işte bir nokta var - “ 5. Tireleme olmadan ikili aritmetik". Bu yazıda operasyon anlatılmaktadır. xor! Haykırıyorum çünkü bu yazıda bu işlem o kadar planlanmış ki okuyucu sadece bu işlemin nasıl çalıştığını anlamakla kalmıyor, hatta başlatıyor. gör, duy ve hisset!

1. Bu eylem, şifre çözme sırasında şifreden ilk değerlerin alınabilmesi için gereklidir.

2.2 Blok şifre GOST 28147-89

GOST 28147 - 89 şifreleme algoritması, seçilen bilgi bloğunun iki bölümünün eşit boyutta olduğu dengeli Feistel ağlarının mimarisine göre çalışan blok şifreleri kategorisine aittir. Algoritma, KGB'nin sekizinci bölümünün derinliklerinde geliştirildi, şimdi FAPSI'ye dönüştürüldü ve 1989'da SSCB altında Rusya Federasyonu'nun şifreleme standardı olarak kabul edildi.

Algoritmanın bu yönteminin çalışması için bilgiyi 64 bitlik bloklara bölmek gerekir. Şifreleme sistemine aşağıdaki anahtar bilgileri oluşturun veya girin: anahtar ve ikame tablosu. Şifreleme için anahtar ve ikame tablosunun seçimi çok ciddiye alınmalıdır, çünkü bu, bilgilerinizin güvenliğinin temelidir. Anahtara hangi gereksinimlerin getirildiği ve ikame tablosu hakkında "Anahtar bilgileri için gereksinimler" maddesine bakın.

Yöntemi düşünürken buna odaklanmayacağız, çünkü bu yazı yukarıda da belirttiğim gibi bu şifreleme algoritmasının basit bir şekilde değiştirilmesi yöntemiyle okuyucuya verilerin nasıl şifreleneceğini öğretmek amacı ile yazılmıştır ancak bu konuya yazının sonunda mutlaka değineceğiz.

Teorik minimum.

3.1 Anahtar bilgiler

Yukarıda söylediğim gibi, aşağıdakiler veri şifrelemede aktif olarak yer almaktadır:

3.1.1. Anahtar, her biri 32 bit olan sekiz öğeden oluşan bir dizidir. Aşağıda, K sembolü ile göstereceğiz ve içerdiği elemanlar k1, k2, k3, k4, k5, k6, k7, k8'dir.

3.1.2 İkame tablosu - bundan sonra sekiz satır ve on altı sütundan oluşan bir matris - Hij. i satırı ve j sütununun kesişimindeki her eleman 4 bit kaplar.

Şifreleme sürecindeki ana adım, kripto dönüşümünün ana adımıdır. Bu, belirli bir algoritmaya göre verileri şifrelemek için yapılan bir eylemden başka bir şey değildir, yalnızca geliştiriciler adı çok hantal hale getirdi :).

Şifrelemeye başlamadan önce blok, her biri 32 bit olan iki parça L ve R'ye bölünür. Anahtar eleman seçilir ve ancak o zaman bloğun bu iki parçası, anahtar eleman, ikame tablosu ana adım fonksiyonuna beslenir, ana adımın sonucu, aşağıda tartışılacak olan temel döngünün bir yinelemesidir. sonraki paragraf. Ana adım aşağıdakilerden oluşur:

1. R bloğunun ilave kısmı, anahtar eleman K mod 2 32 ile toplanır. Yukarıda benzer bir işlemi tanımladım, burada aynı şey sadece üs "4" değil, "32" - bu işlemin sonucu gelecekte Smod olarak gösterilecektir.
2. Daha önce elde edilen Smod sonucunu dört bitlik s7, s6, s5, s4, s3, s2, s1, s0 öğelerine bölün ve değiştirme işlevine besleyin. Değiştirme aşağıdaki gibidir: Smod - si öğesi seçilir, en baştan en düşük öğeyle başlarız ve değiştirme tablosundaki değerle i ile değiştiririz - s öğesinin değeriyle gösterilen satır ve sütun ben. si +1 elemanına geçiyoruz ve aynı şekilde ilerliyoruz ve son elemanın Smod değerini değiştirene kadar devam ediyoruz - bu işlemin sonucu Ssimple olarak gösterilecektir.
3. Bu işlemde Ssimple değerini döngüsel olarak 11 bit sola kaydırıyoruz ve Srol elde ediyoruz.
4. L bloğunun ikinci bölümünü seçiyoruz ve Srol ile mod 2'yi ekliyoruz, sonuç olarak Sxor'umuz var.
5. Bu aşamada, L bloğunun parçası, R parçasının değerine eşit olur ve sırayla R parçası, Sxor'un sonucu ile başlatılır ve bu noktada ana adımın işlevi tamamlanır!

3.3 Temel döngüler: "32-З", "32-Р".

Bilgiyi şifrelemek için 64 bitlik bloklara bölmek gerekir, tabii ki son blok 64 bitten küçük olabilir. Bu gerçek, bu "kolay değiştirme" yönteminin Aşil topuğudur. 64 bit'e eklenmesi, şifreleme programının kriptografik gücünü artırmak için çok önemli bir görev olduğundan ve bu hassas yere, eğer bilgi dizisinde varsa, ancak mevcut olmayabilir (örneğin, 512 baytlık bir dosya! ), Kişi büyük bir sorumlulukla davranmalıdır!

Bilgileri bloklara böldükten sonra anahtarı öğelere ayırmalısınız:

K = k1, k2, k3, k4, k5, k6, k7, k8

Şifrelemenin kendisi, sözde temel döngülerin kullanımından oluşur. Bu da, kripto dönüşümünün n'inci temel adımlarını içerir.

Temel döngüler etiketlenir, nasıl yazılır: n - m. Burada n, temel döngüdeki kripto dönüşümünün temel adımlarının sayısıdır ve m, temel döngünün "türü"dür, yani. ne hakkında, "Z" şifrelemesi veya "R" veri şifrelemesi hakkında.

Temel şifreleme döngüsü 32-З, kripto dönüşümünün 32 temel adımından oluşur. N bloğu ve K anahtarının bir öğesi, adımın eylemlerini uygulayan işleve beslenir ve ilk adım k1 ile gerçekleşir ve ikincisi k2 öğesiyle elde edilen sonucun üzerinde, vb. aşağıdaki şemaya göre:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

32-P için şifre çözme işlemi benzer şekilde gerçekleşir, ancak anahtar öğeler ters sırada verilmiştir:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Uygulama.

Bilginin nasıl şifreleneceği teorisini öğrendikten sonra, şifrelemenin pratikte nasıl çalıştığını görmenin zamanı gelmişti.

İlk veri:

N = 0102030405060708h bilgi bloğunu alın, burada L ve R parçaları eşittir:

L = 01020304h, R = 05060708h, anahtarı alalım:

K = ' 28 gibi zw37 q839 7342ui23 8e2t wqm2 ewp1 '(bunlar ASCII - kodlardır, onaltılık gösterimi görüntülemek için, bu dosyayı Total Commander'da görünüm modunda tuşuna basarak açabilirsiniz. F3"Ve sonra anahtar" 3 "). Bu anahtarda, elemanların değerleri şöyle olacaktır:

k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'

k5 = "ui23", k6 = "8e2t", k7 = "wqm2", k8 = "ewp1"

Ayrıca aşağıdaki ikame tablosunu da alın:

Pirinç. 3

Burada satırlar 0'dan 7'ye, sütunlar 0'dan F'ye kadar numaralandırılmıştır.

Bir uyarı:İkame tablosuna sahip anahtar dahil tüm bilgiler, algoritmayı dikkate almak için örnek olarak alınmıştır!

"İlk verileri" kullanarak, kripto dönüşümünün ana adımının eyleminin sonucunu elde etmek gerekir.

1. R = 05060708h bölümünü ve k1 = 'as28' anahtar öğesini seçiyoruz, onaltılık biçimde anahtar öğe şöyle görünecektir: 61733238h. Şimdi toplama işlemi mod 2 32'yi yapıyoruz:

Pirinç. 4

Şekilde gördüğünüz gibi kırmızı ile işaretlenmiş ve üslü 33 bitlik bir transferimiz olmadı. 32 ". Ve eğer R ve anahtar eleman için başka değerlerimiz olsaydı, bu pekala olabilirdi ve o zaman onu görmezden gelirdik ve sadece sarı ile işaretlenmiş bitleri kullanırdık.

Bu işlemi assembler komutu ile gerçekleştiriyorum Ekle:

; eax = R, ebx = 'as28'

Bu işlemin sonucu Smod = 66793940h

1. Şimdi en karmaşık operasyon, ancak yakından bakarsanız, artık ilk bakışta göründüğü kadar korkunç değil. Smod'u aşağıdaki gibi hayal edelim:

ŞEKİL KAYDEDİLMEDİ

Pirinç. 5

Şekilde Smod öğelerini görselleştirmeye çalıştım ama yine de açıklayayım:

s0 = 0, s1 = 4, s2 = 9, vb.

Şimdi, en düşük s0 elemanından başlayarak değiştirmeyi yapıyoruz. Paragrafı hatırlamak " 3.2 Kripto dönüşümünün temel adımı»I - satır, s ben - sütun, sıfır satırındaki ve sıfır sütundaki değeri arayın:

Şekil 6

Yani Smod'un şu anki değeri 6679394 değil 0 ve 6679394 5 H.

S1'i değiştirmeye devam ediyoruz, yani. dört. İlk satırı ve dördüncü sütunu kullanma (s1 = 4!). Resme bakıyoruz:

Pirinç. 7

Şimdi zaten 667939 değil Smod'un değeri 4 5 saat, 667939 2 5 saat Şimdi değiştirme algoritmasının okuyucu için açık olduğunu varsayıyorum ve Ssimple'ın nihai sonucundan sonra şu değere sahip olacağını söyleyebilirim - 11e10325h.

Genişletilmiş tablodan bahsettikten sonra, bir sonraki paragrafta bunun montajcı komutları şeklinde uygulanmasının en kolay olduğundan bahsedeceğim.

1. Ortaya çıkan Ssimple değerini 11 bit sola kaydırmalıyız.

Pirinç. sekiz

Gördüğünüz gibi, bu eylem oldukça basittir ve montaj dilinin bir komutuyla uygulanır - rol ve bu Srol işleminin sonucu 0819288Fh'dir.

1. Şimdi, Srol değeriyle XOR'lanacak bilgi bloğumuzun L kısmı olarak kalıyor. w2k sp4'ten bir hesap makinesi alıyorum ve Sxor = 091b2b8bh alıyorum.
2. Bu eylem sondur ve biz sadece L parçasının değeri olan R'yi atadık, temizledik ve L parçasını Sxor değeriyle başlattık.

Son sonuç:

L = 091b2b8bh, R = 01020304h

4.2 Algoritmanın hızını artırma

Şimdi algoritmayı hız için optimize etmekten bahsedelim. Bir projeyi uygulama sürecinde, kayıtlarla çalışan bir programın bellekten çok daha hızlı çalıştığını hesaba katmak gerekir ve burada bu yargı da çok önemlidir, çünkü bir bilgi bloğu üzerinden 32 şifreleme eylemi!

Programımda şifreleme algoritmasını uyguladığımda aşağıdakileri yaptım:

1. L bloğunun seçilen kısmı eax kaydına ve R'den edx'e.
2. Esi kaydında, genişletilmiş anahtarın adresi ile başlatıldı, daha fazlası aşağıda.
3. ebx kaydında, genişletilmiş ikame tablosunun adresinin değeri atanır, aşağıda daha fazlası
4. 1, 2, 3 öğelerinin bilgileri, duruma bağlı olarak 32 - З veya 32 - Р temel döngüsünün işlevine aktarıldı.

Paragraftaki kilit unsurların akış şemasına bakarsanız " Temel döngüler: "32-З", "32-Р"", O zaman 32 - 3 temel döngüsü için anahtarımız aşağıdaki gibi temsil edilebilir:

K32-Z =

"As28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"As28", "zw37", "q839", "7342", "ui23", "8e2t", "wqm2", "ewp1",

"Ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28"

Onlar. başlangıçtan itibaren k1, k2, k3, k4, k5, k6, k7, k8 vardır - ‘ olarak28','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2T ','wqm2 ','ewp1' bu dizi üç kez tekrarlanır. Sonra elemanlar ters sırada gider, yani: k8, k7, k6, k5, k4, k3, k2, k1 - "Ewp1", "wqm2", "8e2t", "ui23", "7342", "q839", "zw37", "as28".

Dizideki elemanları 32 - Z'de beslenmeleri gereken sıraya göre önceden düzenledim. Böylece anahtar teslim olarak gereken hafızayı arttırdım ama gerek duymadığım bazı düşünme süreçlerinden kendimi kurtardım ve hızımı arttırdım. algoritmanın, bellek erişim süresini azaltarak! Burada sadece 32 - З için anahtarı tanımladım, 32 - Р döngüsü için aynısını yaptım, ancak paragrafta da tanımladığım farklı bir tedarik elemanı şeması kullandım " Temel döngüler: “32-Z”, “32-P».

Şimdi yukarıda söz verdiğim gibi değiştirme fonksiyonunun uygulamasını açıklamanın zamanı geldi. Daha önce tarif edemedim, çünkü bu, yeni bir kavramın - genişletilmiş bir ikame tablosunun - tanıtılmasını gerektirir. Sana ne olduğunu açıklayamam. Bunun yerine, size göstereceğim ve siz kendiniz formüle edeceksiniz, bu nedir - genişletilmiş bir ikame tablosu mu?

Dolayısıyla, genişletilmiş bir ikame tablosunun ne olduğunu anlamak için bir ikame tablosuna ihtiyacımız var, örneğin, Şekil 1'de gösterileni alacağım. 3.

Örneğin, 66793940h numarasını değiştirmemiz gerekiyordu. Bunu şu şekilde sunacağım:

ŞEKİL KAYDEDİLMEDİ

Pirinç. dokuz

Şimdi s1, s0, elemanlarını alırsak, yani. en az anlamlı bayt, değiştirme işlevinin sonucu 25 saat olacaktır! Paragrafta alıntıladığım Andrey Vinokurov'un makalesini okuduktan sonra " kullanılmış literatür listesi", Aslında, iki satır alırsanız, bir dizi alabileceğinizi ve montajcı komutunu kullanarak yedek öğeleri hızlı bir şekilde bulmanızı sağladığını görüyorsunuz. xlat. Başka bir yolla daha hızlı yapılabileceğini söylüyorlar, ancak Andrey Vinokurov GOST'un uygulanması için hızlı algoritmaları araştırmak için yaklaşık dört yıl harcadı! Zaten bir tane varken tekerleği yeniden icat etmen gerektiğini düşünmüyorum.

Yani, dizi hakkında:

İlk iki satırı sıfır alalım ve ilkini 256 baytlık bir dizi oluşturalım. Şimdi, eğer 00h'yi dönüştürmek gerekirse, sonucun 75h olacağına dair bir tuhaflık gözlemliyoruz (Şekil 3'e göre) - bu değeri 00h ofsetindeki diziye koyarız. 79h ikame fonksiyonunun sonucu olan 01h değerini alıyoruz, onu 01 ofsetindeki diziye koyuyoruz ve böylece 0FFh'ye kadar devam ediyoruz, bu bize 0FCh'yi verecek ve 0FFh ofsetinde diziye koyacağız. Böylece ilk satır grubu için genişletilmiş bir ikame tablosu elde ettik: ilk ve sıfır. Ama yine de üç grup var: ikinci sayfa 2, sayfa 3, üçüncü sayfa 4, sayfa 5, dördüncü sayfa 6, sayfa 7. Bu üç grupla ilkiyle aynı şekilde ilgileniyoruz. Sonuç, genişletilmiş bir ikame tablosudur!

Artık değiştirme işlemini gerçekleştirecek bir algoritma uygulayabiliriz. Bunu yapmak için Andrei Vinokurov'un sayfasında yayınladığı kaynak kodlarını alıyoruz, bkz. " bibliyografya».

lea ebx, extension_table_simple

mov eax, [değiştirilecek numarayı girin]

ebx, 100h ekle; sonraki iki düğüme atla

alt ebx, 300h; böylece gelecekte ebx tabloya işaret eder

Şimdi bir özellik daha, önceki eylemlerle sadece değiştirmekle kalmadık, aynı zamanda sayıyı 8 bit sola kaydırdık! Sayıyı 3 bit daha sola kaydırmamız gerekiyor:

ve operasyon rolü eax, 11'in sonucunu alıyoruz!

Optimizasyon üzerine daha fazla bir şey ekleyemem, vurgulayabileceğim tek şey yukarıda söylediklerim - kayıtları bellek erişiminden daha sık kullanın. Sanırım bu sözler sadece yeni başlayanlar için, deneyimli olanlar ve benim sözlerim olmadan bunu mükemmel bir şekilde anlıyor :).

Anahtar bilgiler için gereksinimler.

Andrey Vinokurov'un makalesinde belirtildiği gibi, anahtar iki kritere göre seçilir:

- 1 ve 0 değerleri arasında bitlerin eşit olası dağılımı için bir kriter. Genellikle, bitlerin eşit olası dağılımı için kriter Pearson kriteridir ("ki-kare").

Bu, prensipte herhangi bir sayının yapabileceği bir anahtar anlamına gelir. Yani, anahtarın bir sonraki biti oluşturulduğunda, bunun bir veya sıfır tarafından başlatılma olasılığı 50/50'dir!

Lütfen anahtarın her biri 32 bit olan sekiz öğeden oluştuğunu unutmayın, bu nedenle anahtarda yalnızca 32 * 8 = 256 bit vardır ve olası anahtar sayısı 2 256'dır! Bu seni etkilemiyor mu? 🙂

- seri kriteri.

Paragrafta verdiğim anahtarımıza bakarsak " 4.1 Kripto dönüşümünün ana adımının uygulanması», O zaman aşağıdaki gösterimin geçerli olduğunu fark edeceksiniz:

Pirinç. on

Bir cümlede, k 1 değeri, k 2'de veya anahtarın başka hiçbir öğesinde tekrarlanmamalıdır.

Yani, şifreleme algoritmasını göz önünde bulundurarak seçtiğimiz anahtar, yukarıdaki iki kriteri tam olarak karşılamaktadır.

Şimdi ikame tablosunun seçimi hakkında:

Şimdi doğru ikame tablosunun nasıl seçileceğinden bahsedelim. Değiştirme tablolarının seçimi için temel gereksinim, her biri 4 bit boyutunda olan öğelerin “tekrarlanamazlığı” olgusudur. Yukarıda gördüğünüz gibi, ikame tablosunun her satırı 0h, 1h, 2h, 3h,…, 0fh değerlerinden oluşur. Bu nedenle temel gereksinim, her satırın 0h, 1h, 2h, ..., 0fh değerlerini ve bu tür her bir değeri bir kopyada içermesidir. Örneğin, sıra:

1 2 3 4 5 6 7 8 9 A B C D E F

Bu gereksinime tamamen uygundur, ancak yine de! Dize gibi bir dizinin seçilmesi önerilmez. Çünkü böyle bir dizgeye dayanan bir fonksiyonun girişine bir değer beslerseniz, çıktıda aynı değeri alırsınız! Bana inanmıyor musun? Ardından, bir ikame tablosu olarak 332DA43Fh sayısını ve bu tür sekiz satırı alın. Değiştirme işlemini gerçekleştirin ve sizi temin ederim, çıktı 332DA43Fh sayısı olacaktır! Yani, işlemin girişine gönderdiğiniz ile aynı! Ve bu şifrelemede iyi bir formun işareti değil, değil mi? 🙂

Bu bir gereklilikti, sonraki kriter şunu söylüyor - çıkış bloğunun her biti, giriş bloğunun her bir bitinden istatistiksel olarak bağımsız olmalıdır!

Nasıl daha basit görünüyor? Ve örneğin, yukarıdaki sayıdan s0 = 0Fh, 01111b öğesini nasıl seçtik. Şimdi ilk biti bir veya sıfırla değiştirme olasılığımız 0,5! İkinci, üçüncü ve dördüncü bitleri, her bir biti ayrı ayrı birler veya sıfırlarla değiştirme olasılığı da 0, 5'tir. s1 = 0Eh seçerken, sıfır bit olma olasılığımız ve bu "0". , sıfır veya bir çok eşittir - 0,5 ile değiştirilecektir! Böylece, bu kritere göre, s0, s1 elemanlarının sıfır bitlerinin yer değiştirmesi arasında bir düzenlilik yoktur! Evet, birleri değiştirebilirsin, ama sıfırları da değiştirebilirsin. 🙂

Tabloyu bu kritere göre değerlendirmek için, aşağıdaki formülle hesaplanan bir korelasyon katsayıları tablosu oluşturabilirsiniz:

- p = 1 ise, çıkıştaki j bitinin değeri, girişteki herhangi bir bit kombinasyonu için girişteki i bitinin değerine eşittir;

- p = -1 ise, o zaman çıkıştaki j bitinin değeri her zaman giriş biti i'nin tersidir;

- p = 0 ise, eşit olasılıkla çıkış biti j, giriş biti i'nin herhangi bir sabit değeri için 0 ve 1 değerlerini alır.

Bir satırlık örnek verelim:

NS	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Bunu "bileşenlere" ayıralım:

Yukarıdaki formüle göre bir katsayı hesaplayalım. Bunun nasıl yapıldığını anlamayı kolaylaştırmak için daha ayrıntılı olarak açıklayacağım:

- girişte 0. sayının (0) 0. bitini ve çıkışta (1) 0. sayının 0. bitini alıyoruz 0 XOR 1 = 1 işlemini yapıyoruz.

- girişte 1. sayının (1) 0. bitini ve çıkışta (1) 1. sayının 0. bitini alıyoruz 1 XOR 1 = 0 işlemini yapıyoruz.

- girişte 2. sayının (0) 0. bitini ve çıkışta (0) 2. sayının 0. bitini alıyoruz 0 XOR 0 = 0 işlemini yapıyoruz.

- girişte 3. sayının (1) 0. bitini ve çıktıda (1) 3. sayının 0. bitini alıyoruz 1 XOR 1 = 0 işlemini yapıyoruz.

Bu dizide art arda XOR işlemleri yaparak sıfır olmayan tüm değerleri sayarız, 6 değerini alırız. Dolayısıyla P 00 = 1- (6/2 4-1) = 0.25. Böylece, 16'nın 4'ünde çıkıştaki bit 0'ın değerinin girişteki bit 0'ın değerine eşit olduğu ortaya çıktı;

Son oran tablosu:

Katsayı tablosu aşağıdaki gibi olacaktır (yeniden hesaplamanın tembel olmadığı)

	giriş
Çıktı		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Bu tabloda işler daha da kötü - grubun 1. ve 2. bitleri değişmeden kalıyor! Kriptanalist nereye dönecektir 🙂 Tüm bu gereksinimleri dikkate alarak, basit bir arama ("kafa kafa") belirtilen teoriye karşılık gelen permütasyon tablolarını buldu (bugün - 1276 kombinasyon) İşte bunlardan bazıları:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Kullanılmış literatür listesi.

1. Andrey Vinokurov'un makalesi:

Şifreleme algoritması GOST 28147-89, kullanımı ve uygulanması

Intel x86 platformunun bilgisayarları için.

(http://www.enlight.ru/crypto/frame.htm adresinde bulunabilir).

Şifreleme algoritmasının uygulanması için kaynak kodları da vardır.

1. Horst Feistel'in makalesi:

Kriptografi ve Bilgisayar Güvenliği.

(bir önceki makale ile aynı adreste bulunabilir)

1. Ross N. Williams:

CRC Hata Tespit Algoritmaları için Temel Kılavuz

sitede yayınlandı www.wasm.ru.

Teşekkürler.

www.wasm.ru forumuna gelen tüm ziyaretçilere şükranlarımı sunmak istiyorum. Ancak şu anda SteelRat olarak bilinen ChS'e, muhtemelen asla anlayamayacağım şeyleri anlamama ve ayrıca paragrafı yazmama yardım ettiği için özellikle teşekkür etmek istiyorum: “ Anahtar bilgi gereksinimleri”, Bu paragrafın ana kısmı onun tarafından yazılmıştır. KSTU çalışanına da derinden müteşekkirim. BİR. Tupolev Anikin Igor Vyacheslavovich ve onun olduğu gerçeği için Chris Kaspersky'den ve talimatları için Volodya / wasm.ru'dan bahsetmemek günah olurdu. Oh, ve ondan alıyorum :). Ayrıca Sega-Zero / Callipso'yu not etmek istiyorum, ancak bu aklıma matematiksel bir orman getirdi.

Belki de size söylemek istediklerimin hepsi bu.

Bu makaleyle ilgili herhangi bir eleştiri veya soru ya da sadece tavsiye için minnettar olurum. İletişim bilgilerim: [e-posta korumalı], ICQ - 337310594.

Saygılarımla, Evil's Interrupt.

Not: Bu yazı ile kimseyi geçmeye çalışmadım. GOST çalışmasını kolaylaştırmak amacıyla yazılmıştır ve zorluk yaşıyorsanız, bu benim bundan suçlu olduğum anlamına gelmez. Makul olun ve sabırlı olun, sizin için en iyisi!

Bu algoritma, Rusya Federasyonu devlet kuruluşlarında ve bir dizi ticari kuruluşta bir şifreleme algoritması olarak kullanılması zorunludur.

Algoritma açıklaması

Algoritma diyagramı Şekil 2'de gösterilmektedir. 3.1. Gördüğünüz gibi, bu algoritmanın şeması oldukça basittir, bu da yazılım veya donanım uygulamasını açık bir şekilde basitleştirir.

GOST 28147-89 algoritması, bilgileri 32 bitlik iki alt bloğa (N1 ve N2) bölünmüş 64 bitlik bloklarda şifreler. N1 alt bloğu belirli bir şekilde işlenir ve ardından değeri eklenir.

alt blok değeri N2 ile (ekleme modulo 2 yapılır), daha sonra alt bloklar değiştirilir. Böyle bir dönüşüm, belirli sayıda tur için gerçekleştirilir: algoritmanın çalışma moduna bağlı olarak (aşağıda açıklanmıştır) 16 veya 32. Her turda aşağıdaki işlemler gerçekleştirilir:

1. Anahtar yerleşimi. Alt bloğun / VI'nın içeriği, Kx anahtarının bir kısmı ile modulo 2 32'ye eklenir.

GOST 28147-89 algoritmasının şifreleme anahtarı 256 bit boyutuna sahiptir ve Kx 32 bit parçasıdır, yani 256 bit şifreleme anahtarı 32 bit alt anahtarların bir birleşimi olarak temsil edilir (Şekil 3.2). :

SH ATI, AG2, YU, AG4, K5, KB, K7.

Şifreleme işleminde, algoritmanın çalışma şekline ve tur sayısına bağlı olarak bu alt anahtarlardan biri kullanılır.

Pirinç. 3.1. Algoritma şeması GOST 28147-

Pirinç. 3.2. Algoritma şifreleme anahtarı GOST 28147-89

2. Tablo değiştirme. Anahtar yerleştirildikten sonra, alt blok / VI, alt bloğun bu kısmı için değiştirme tablosuna göre her birinin değeri ayrı ayrı değiştirilen 4 bitlik 8 parçaya bölünür. Değiştirme kutuları (S-kutuları) genellikle modern şifreleme algoritmalarında kullanılır, bu nedenle onları daha ayrıntılı olarak ele almaya değer.

Tablo değiştirme şu şekilde kullanılır: sayısal gösterimi çıkış değerinin sayısını belirleyen girişe belirli bir boyutta (bu durumda 4 bit) bir veri bloğu beslenir. Örneğin, aşağıdaki biçimde bir S kutumuz var:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Girişe 4 bitlik bir blok "0100" yani 4 değeri gelsin. Tabloya göre çıkış değeri 15 yani 15 olacaktır. "1111" (0, 4 ile değiştirilir, 1, 11 ile değiştirilir, 2 değeri değişmez vb.).

Gördüğünüz gibi, algoritma şeması çok basittir, bu da en büyük veri şifreleme yükünün değiştirme tablolarına düştüğü anlamına gelir. Ne yazık ki, algoritma, kullanıldığında algoritmanın kriptanalitik yöntemlerle ifşa edilebileceği “zayıf” ikame tabloları olma özelliğine sahiptir. Zayıf olanlar, örneğin, çıktının girdiye eşit olduğu bir tabloyu içerir:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. 11 bit bit düzeyinde döngüsel sola kaydırma.

Algoritma çalışma modları

GOST 28147-89 algoritmasının 4 çalışma modu vardır:

□ basit değiştirme modu;

□ gama modu;

Geri bildirimli P gama modu;

□ simülatörlerin üretim modu.

Bu modlar genel kabul görmüş olanlardan biraz farklıdır (Bölüm 1.4'te açıklanmıştır), bu nedenle onları daha ayrıntılı olarak ele almaya değer.

Bu modların farklı amaçları vardır, ancak yukarıda açıklanan aynı şifreleme dönüşümünü kullanırlar.

Kolay değiştirme modu

Basit değiştirme modunda, her 64 bitlik bilgi bloğunu şifrelemek için yukarıda açıklanan 32 tur basitçe gerçekleştirilir. 32 bitlik alt anahtarlar aşağıdaki sırayla kullanılır:

□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI, vb. - 1 ila 24. turlarda;

□ K1, Kb, K5, K4, KZ, K2, K \, KO — 25'ten 32'ye kadar olan turlarda.

Basit değiştirme modundaki şifre çözme işlemi tamamen aynı şekilde, ancak biraz farklı bir alt anahtar dizisi ile gerçekleştirilir:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - 1'den 8'e kadar turlarda;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb, vb. - 9'dan 32'ye kadar olan turlarda.

Standart ECB moduna benzer şekilde, blokların ayrı şifrelenmesi nedeniyle, basit değiştirme modunun verilerin kendisini şifrelemesi kesinlikle önerilmez; yalnızca çok anahtarlı şemalarda diğer şifreleme anahtarlarını şifrelemek için kullanılmalıdır.

Gama modu

Gama modunda (Şekil 3.3), her düz metin bloğu, 64-bit şifreli gama bloğu ile modülo 2'ye bit bazında eklenir. Bir şifrenin gaması, yukarıda açıklanan dönüşümler kullanılarak oluşturulan özel bir dizidir:

1. N1 ve N2 kayıtlarında ilk doldurmaları yazılır - "senkro patlama" adı verilen 64 bitlik bir değer (aslında senkronizasyon patlaması CBC, CFB ve OFB modlarındaki başlatma vektörünün bir analogudur).

2. Kayıtların / VI ve N2 içeriğinin şifrelenmesi (bu durumda - senkronizasyon mesajları) basit değiştirme modunda gerçekleştirilir.

3. N1'in içeriği, CI = 2 24 + 2 16 + 2 8 + 4 sabiti ile modulo (2 32 - 1) eklenir, toplamanın sonucu / VI kaydına yazılır.

4. N2'nin içeriği modülo 2'ye C2 = 2 24 + 2 16 + 2 8 +1 sabiti ile eklenir, toplamanın sonucu N2 kaydına yazılır.

5. / VI ve N2 kayıtlarının içeriği 64-bit şifreli gama bloğu olarak çıkar (yani, bu durumda / VI ve N2 ilk gama bloğunu oluşturur).

6. Bir sonraki gama bloğu gerekiyorsa (yani şifrelemeye veya şifre çözmeye devam etmeniz gerekiyorsa), 2. adıma dönersiniz.

Şifre çözme için gama benzer şekilde üretilir, ardından XOR işlemi tekrar şifreli metin ve gama bitlerine uygulanır.

Aynı şifre gamını oluşturmak için, kriptogramın şifresini çözen kullanıcının, bilgiyi şifrelemek için kullanılanla aynı anahtara ve aynı senkro-mesaj değerine sahip olması gerekir. Aksi takdirde, orijinal metni şifreli olandan almak mümkün olmayacaktır.

GOST 28147-89 algoritmasının çoğu uygulamasında, senkronizasyon mesajı gizli bir unsur değildir, ancak senkronizasyon mesajı şifreleme anahtarı kadar gizli olabilir. Bu durumda, algoritma anahtarının (256 bit) etkin uzunluğunun, ek bir anahtar öğe olarak kabul edilebilecek olan senkronizasyon mesajının 64 bit'i tarafından artırıldığını varsayabiliriz.

Geri bildirimli gama modu

Geri beslemeli gama modunda, 2. bloktan başlayarak / VI ve L / 2 kayıtlarının doldurulması olarak, önceki gama bloğu değil, önceki düz metin bloğunun şifrelenmesinin sonucu kullanılır (Şekil 3.4). . Bu moddaki ilk blok, bir öncekine tamamen benzer şekilde oluşturulur.

Pirinç. 3.4. Geri besleme gama modunda şifreli gama üretimi

Bir simülatörün üretim şekli

Önek, mesajların bütünlüğünü doğrulamak için bir şifreleme anahtarı kullanılarak hesaplanan kriptografik bir sağlama toplamıdır. Bunu hesaplamak için GOST 28147-89 algoritmasının özel bir modu vardır.

Bir simülatörün oluşturulması şu şekilde gerçekleştirilir:

1. Ön ekin hesaplandığı ilk 64 bitlik bilgi bloğu, N1 ve N2 kayıtlarına yazılır ve 32'den ilk 16 turun gerçekleştirildiği azaltılmış basit değiştirme modunda şifrelenir.

2. Elde edilen sonuç, sonucu N1 ve N2'de saklayarak bir sonraki bilgi bloğu ile modulo 2'yi toplar.

3. M ve N2, indirgenmiş basit değiştirme modunda tekrar şifrelenir ve bu, son bilgi bloğuna kadar devam eder.

Taklitçi, N1 ve N2 kayıtlarının veya bunun bir parçasının 64 bitlik sonuç içeriğidir. En yaygın olarak kullanılan 32 bit önek, yani kayıt içeriğinin yarısı kullanılır. Bu yeterlidir, çünkü herhangi bir sağlama toplamı gibi, simülatör de öncelikle bilgilerin yanlışlıkla bozulmasına karşı koruma sağlamak için tasarlanmıştır. Kasıtlı veri değişikliklerine karşı koruma sağlamak için diğer şifreleme yöntemleri kullanılır - her şeyden önce elektronik bir dijital imza (bkz. bölüm 1.1).

Taklitçi şu şekilde kullanılır:

1. Herhangi bir bilgiyi şifrelerken, şifreli metin ile birlikte bir düz metin öneki hesaplanır ve gönderilir.

2. Şifre çözme işleminden sonra önek tekrar hesaplanır ve gönderilen ile karşılaştırılır.

3. Hesaplanan ve gönderilen önekler eşleşmiyorsa - iletim sırasında şifreli metin bozuldu veya şifre çözme sırasında yanlış anahtarlar kullanıldı.

Önek, özellikle çok anahtarlı şemalar kullanılırken anahtar bilgilerinin doğru şifresinin çözüldüğünü doğrulamak için kullanışlıdır.

Taklitçi, CBC modunda hesaplanan MAC mesaj doğrulama kodunun bir benzeridir; fark, ön ekin hesaplanmasında senkronizasyon mesajının kullanılmaması, MAC hesaplamasında başlatma vektörünün kullanılmasıdır.

Algoritmanın kriptografik gücü

1994 yılında GOST 28147-89 algoritmasının açıklaması İngilizce'ye çevrildi ve yayınlandı; bundan sonra yabancı uzmanlar tarafından yapılan analizin sonuçları ortaya çıkmaya başladı; bununla birlikte, önemli bir süre boyunca, olası hiçbir saldırı bulunmadı.

□ büyük anahtar uzunluğu - 256 bit; gizli senkronizasyon mesajı ile birlikte etkin anahtar uzunluğu 320 bite çıkarılmıştır;

□ 32 tur dönüşüm; 8 turdan sonra, girdi verilerinin dağılmasının tam etkisi elde edilir: düz metin bloğunun bir bitindeki bir değişiklik, şifreli metin bloğunun tüm bitlerini etkiler ve bunun tersi, yani çoklu bir güvenlik payı vardır.

GOST 28147-89 algoritmasının kriptanalizinin sonuçlarını düşünün.

Değiştirme tablolarının analizi

Standartta ikame tabloları verilmediği için bazı çalışmalar (örneğin c) "yetkin bir kuruluşun" hem "iyi" hem de "kötü" ikame tabloları üretebileceğini öne sürmektedir. Ancak ünlü uzman Bruce Schneier, bu tür varsayımları "söylentiler" olarak adlandırıyor. Algoritmanın kriptografik gücünün büyük ölçüde kullanılan değiştirme tablolarının özelliklerine bağlı olduğu açıktır; buna göre, kullanımı algoritmaya yönelik saldırıyı basitleştirebilecek zayıf değiştirme tabloları (yukarıdaki örneğe bakın) vardır. Bununla birlikte, farklı ikame tabloları kullanma olasılığı, lehine DES şifreleme standardının geçmişinden iki gerçeğin alıntılanabileceği çok değerli bir fikir gibi görünmektedir (ayrıntılar için bkz. bölüm 3.15):

□ DES algoritmasının hem doğrusal hem de diferansiyel kriptoanalizini kullanan saldırılar, değiştirme tablolarının belirli özelliklerini kullanır; diğer tabloları kullanırken kriptanalizin baştan başlaması gerekecektir;

□ daha sağlam ikame tabloları kullanarak DES'yi doğrusal ve diferansiyel kriptanalize karşı güçlendirmeye yönelik girişimlerde bulunulmuştur; gerçekten daha sağlam olan bu tür tablolar, örneğin, s 5 DES algoritmasında önerilmiştir; ancak, ne yazık ki, DES'i s 5 DES ile değiştirmek imkansızdı, çünkü değiştirme tabloları sırasıyla standartta katı bir şekilde tanımlandığından, algoritmanın uygulanması muhtemelen tabloları başkalarına değiştirme yeteneğini desteklemez.

Bazı çalışmalarda (örneğin, ve) yanlışlıkla GOST 28147-89 algoritmasının gizli ikame tablolarının anahtarın bir parçası olabileceği ve etkili uzunluğunu artırabileceği (algoritmanın çok fazla olduğu için önemsiz olduğu) sonucuna varılmıştır. büyük 256 bit anahtar). Ancak çalışma, gizli ikame tablolarının pratikte uygulanabilecek aşağıdaki saldırı kullanılarak hesaplanabileceğini kanıtladı:

1. Sıfır tuşu ayarlanır ve “sıfır vektör” araması yapılır, yani z = / (0) değerleri, burada / () algoritma turunun işlevidir. Bu aşama yaklaşık 2 şifreleme işlemi gerektirir.

2. Sıfır vektörü kullanılarak, 2 11 işlemden fazla olmayan ikame tablolarının değerleri hesaplanır.

Algoritma modifikasyonları ve analizleri

GOST 28147-89 algoritmasının modifikasyonlarının kriptanalizi yapılan çalışma:

□ orijinal algoritmaya göre alt anahtarların kullanım sırasının değiştirildiği, yani 25 ila 32. turlarda alt anahtarların doğrudan sırayla kullanıldığı GOST-H algoritması, yani algoritmanın önceki turları;

□ Anahtarlama için modulo 32 eklemesi yerine XOR kullanan 20 aşamalı GOST® algoritması.

Analiz sonuçlarına dayanarak, GOST-H ve GOST ©'nin orijinal GOST 28147-89 algoritmasından daha zayıf olduğu sonucuna varıldı, çünkü her ikisi de zayıf anahtar sınıflarına sahip. GOST © kriptanalizi bölümünde, çalışmanın, 2000 yılında iyi bilinen bir çalışma tarafından yayınlanan GOST 28147-89 algoritmasının kriptanalizine ayrılmış bölümü kelimesi kelimesine tekrarladığı belirtilmelidir (orijinal referans olmadan) . Bu, eserin yazarlarının profesyonelliği ve sonuçlarının geri kalanı hakkında şüphe uyandırır.

Çalışmada algoritmanın çok ilginç bir modifikasyonu önerilmiştir: S \… Ss tabloları farklı olmalıdır; algoritmanın her turunda, belirli bir yasaya göre yeniden düzenlenmeleri gerekir. Bu permütasyon, şifreleme anahtarına bağlı olabilir veya gizli olabilir (yani, orijinal 256 bitlik anahtardan daha büyük şifreleme anahtarının bir parçası olabilir). Yazarlarına göre bu seçeneklerin her ikisi de algoritmanın doğrusal ve diferansiyel kriptanalize karşı direncini önemli ölçüde artırıyor.

Ve şifreleme anahtarına dayalı ikame tablolarını hesaplamak için olası yöntemlerden birini analiz eden çalışmada, ikame tablolarıyla ilgili bir değişiklik daha verilmiştir. Çalışmanın yazarları, böyle bir bağımlılığın algoritmayı zayıflattığı, çünkü zayıf anahtarların varlığına ve algoritmanın bazı potansiyel güvenlik açıklarına yol açtığı sonucuna varmışlardır.

Tam kapsamlı algoritma analizi

Tam kapsamlı GOST 28147-89'da herhangi bir değişiklik yapılmadan saldırılar var. Algoritmayı analiz eden ilk açık makalelerden biri, iyi bilinen bir makale, bir dizi iyi bilinen şifreleme algoritmasının anahtar genişletme prosedürünün zayıflıklarından yararlanan saldırılara ayrılmıştır. Özellikle, tam kapsamlı GOST 28147-89 algoritması, bağlantılı anahtarlar üzerinde diferansiyel kriptanaliz kullanılarak kırılabilir, ancak yalnızca zayıf ikame tabloları kullanılırsa. Algoritmanın 24 turlu varyantı (ilk 8 turdan yoksun), herhangi bir ikame tablosu için aynı şekilde açılır, ancak güçlü ikame tabloları (örneğin, c'de gösterilen) böyle bir saldırıyı tamamen pratik hale getirir.

Yerli bilim adamları A.G. Rostovtsev ve E.B. Makhovenko 2001 yılında çalışmalarında, şifreli metne karşılık gelen bilinen bir düz metinden nesnel bir işlev oluşturarak temelde yeni bir kriptanaliz yöntemi önerdiler (yazarlara göre, doğrusal ve diferansiyel kriptanalizden çok daha etkilidir). ve istenen anahtar değeri bulma ve gerçek anahtar değere karşılık gelen ekstremumunu bulma. Ayrıca, GOST 28147-89 algoritmasının, yalnızca 4 seçilmiş düz metin ve oldukça düşük karmaşıklığa sahip ilgili şifreli metinler kullanılarak algoritmanın açılmasına izin veren geniş bir zayıf anahtar sınıfı buldular. Çalışmada algoritmanın kriptoanalizine devam edilmektedir.

2004 yılında, Kore'den bir grup uzman, bağlantılı anahtarlar üzerinde diferansiyel kriptanaliz kullanarak, %91,7 olasılıkla 12 bit gizli anahtarın elde edilmesinin mümkün olduğu bir saldırı önerdi. Saldırı, 2 35 seçilmiş düz metin ve 2 36 şifreleme işlemi gerektirir. Gördüğünüz gibi, bu saldırı, algoritmaya gerçek bir saldırı için pratik olarak işe yaramaz.

GOST 28147-89 algoritması ve "Magma" şifresi (GOST R 34.12-2015)

Algoritmanın genel şeması. GOST 28147-89 tarafından açıklanan algoritma “Bilgi işleme sistemleri. Kriptografik koruma. Kriptografik Dönüşüm Algoritması ", simetrik şifreleme için yerel bir standarttır (1 Ocak 2016'dan önce) ve devlet bilgi sistemlerinde ve bazı durumlarda ticari sistemlerde kullanılan sertifikalı kriptografik bilgi koruma araçlarında uygulanması zorunludur. Rusya Federasyonu'nun devlet sırrını oluşturan bilgilerin ve gizliliğinin yürürlükteki mevzuata göre sağlanması gereken bilgilerin korunması için bilgilerin kriptografik olarak korunması araçlarının belgelendirilmesi gerekmektedir. Ayrıca Rusya Federasyonu'nda, bankacılık bilgi sistemlerinin korunması için GOST 28147-89 algoritmasının kullanılması önerilir.

GOST 28147-89 algoritması (Şekil 2.21), Feistel şemasına dayanır ve bilgileri 32 bitlik iki alt bloğa bölünmüş 64 bitlik bloklarda şifreler (I ve R). alt blok R, yuvarlak dönüşüm fonksiyonu tarafından işlenir, ardından değeri Lj alt bloğunun değerine eklenir, ardından alt bloklar değiştirilir. Algoritma, şifreleme moduna (taklit ekleme veya diğer şifreleme modlarının hesaplanması) bağlı olarak 16 veya 32 tura sahiptir.

Pirinç. 2.21.

Algoritmanın her turunda aşağıdaki dönüşümler gerçekleştirilir.

1. Anahtar yerleşimi. alt blok içeriği Ri yuvarlak anahtarlı modulo 2 32 eklendi K.Kj yuvarlak anahtar olarak kullanılan orijinal anahtarın 32-bit kısmıdır. GOST 28147-89 ns algoritması bir anahtar genişletme prosedürü kullanır, orijinal 256-bit şifreleme anahtarı, sekiz 32-bit alt anahtarın birleştirilmesi (birleştirilmesi) olarak temsil edilir (Şekil 2.22): K 0, K (, K t K, KA, K 5, K 6, K 7.

Şifreleme işlemi bu alt anahtarlardan birini kullanır İLE

1. turdan 24. tura kadar - doğrudan sırayla:

25. turdan 32. tura - ters sırada:

Pirinç. 2.22. GOST 28147-89 algoritmasının şifreleme anahtarının yapısı

2. Tablo değiştirme. Anahtar uygulandıktan sonra alt blok Ri sekiz parçaya bölünmüş, ancak her birinin değeri, değiştirme tablosuna (S-kutusu) göre ayrı ayrı değiştirilen 4 bit'tir. Toplam sekiz S-kutusu kullanılır - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. GOST 28147-89 algoritmasının her S bloğu, 0'dan 15'e kadar numaralandırılmış ^ öğelerine sahip bir vektördür (tek boyutlu dizi). S bloğunun değerleri 4 bitlik sayılardır; 0'dan 15'e kadar tam sayılar

S-box tablosundan, sıra numarası ikame girişine gelen değerle çakışan bir eleman alınır.

Örnek 2.6.

Aşağıdaki formun bir S bloğu olsun:

Bu S-box'ın girişine 0100 2 = 4 değeri verilsin.S-box'ın çıkışı ikame tablosunun 4. elemanı olacaktır yani. 15 = 1111 2 (eleman numaralandırması sıfırdan başlar).

ikame kişiler, örneğin DES şifresinde yapıldığı gibi standart tarafından tanımlanmaz. İkame tablolarının değiştirilebilir değerleri, algoritmanın kriptanalizini önemli ölçüde karmaşıklaştırır. Aynı zamanda, algoritmanın sağlamlığı, önemli ölçüde doğru seçimlerine bağlıdır.

Ne yazık ki, GOST 28147-89 algoritması, algoritmanın kriptanalitik yöntemlerle kolayca ortaya çıkarılabileceği kullanıldığında “zayıf” ikame tablolarına sahiptir. "Zayıf" arasında, örneğin, girdinin çıktıya eşit olduğu önemsiz bir ikame tablosu bulunur (Tablo 2.16).

Tablo 2.16

Zayıf bir S kutusu örneği

Değiştirme tablolarının belirli değerlerinin gizli tutulması gerektiğine ve uzun vadeli bir anahtar unsur olduğuna inanılmaktadır, yani. bireysel anahtarlardan çok daha uzun bir süre için geçerlidir. Ancak, değiştirme tablolarının gizli değerleri anahtarın parçası değildir ve etkin uzunluğunu artıramaz.

Gerçekten de, gizli ikame tabloları, pratikte uygulanabilecek aşağıdaki saldırı kullanılarak hesaplanabilir:

• bir sıfır anahtarı ayarlanır ve bir "sıfır vektör" araması yapılır, yani. anlam z = F ( 0) nerede F - algoritmanın yuvarlak dönüşüm fonksiyonu. Bu, yaklaşık 2 32 test şifreleme işlemi gerektirir;
• sıfır vektörü kullanılarak, 2 11 işlemden fazla olmayan ikame tablolarının değerleri hesaplanır.

Ancak, ikame tablolarının gizliliği ihlal edilse bile, şifrenin gücü son derece yüksek kalır ve izin verilen sınırın altına düşmez.

Aynı kriptografik koruma sistemi içindeki tüm şifreleme düğümleri için ikame tablolarının ortak olduğu da varsayılmaktadır.

S-kutularının yapısının iyileştirilmesi, simetrik blok şifreleme alanında en yoğun araştırılan problemlerden biridir. Temel olarak, S-kutularının girişlerinde yapılan herhangi bir değişikliğin rastgele görünüşe göre çıktıyı değiştiriyor. Bir yandan, S-kutuları ne kadar büyük olursa, algoritma doğrusal ve diferansiyel kriptanaliz yöntemlerine o kadar dirençli olur. Öte yandan, büyük bir yedek masa tasarlamak daha zordur.

Modern algoritmalarda, S kutuları genellikle aşağıdakileri içeren bir vektördür (tek boyutlu dizi). 2 "t- bit öğeleri. Blok girişi, değeri S bloğunun çıkışı olarak işlev gören öğenin numarasını tanımlar.

S-kutularının tasarımı için bir takım kriterler öne sürülmüştür. İkame tablosu şunları sağlamalıdır:

• katı çığ kriteri;
• bit bağımsızlık kriteri;
• giriş değerlerinden doğrusal olmayan gereksinim.

Son şartı yerine getirmek için doğrusal bir kombinasyon belirtilmesi önerildi. ben bit ( ben = 1, ..., T) ikame tablosu değerleri bükülmüş fonksiyonlar(İng, kıvrılmış - bu durumda sapma - doğrusal fonksiyonlardan). Bükülmüş fonksiyonlar, en yüksek doğrusal olmama sınıfı ve katı çığ kriterine uygunluk ile karakterize edilen özel bir Boole fonksiyonları sınıfını oluşturur.

Bazı çalışmalarda, S-kutuları için, bir giriş biti değiştiğinde, en azından S-kutusunun çıkış bitleri değiştiğinde, y sıralı garantili çığ etkisinin uygulanmasının kontrol edilmesi önerilmektedir. 2'den 5'e kadar y mertebesinde garantili çığ etkisi özelliği, herhangi bir şifreleme algoritması için S-kutularının yeterince iyi difüzyon özelliklerini sağlar.

Yeterince büyük değiştirme masaları tasarlarken aşağıdaki yaklaşımlar kullanılabilir:

• rastgele seçim (küçük S kutuları için zayıf ikame tablolarının oluşturulmasına yol açabilir);
• rastgele seçim ve ardından çeşitli kriterlere uygunluğun kontrol edilmesi ve zayıf S-kutularının reddedilmesi;
• manuel seçim (büyük S blokları için çok zahmetli);
• matematiksel yaklaşım, örneğin, bükülmüş fonksiyonları kullanarak oluşturma (bu yaklaşım CAST algoritmasında kullanılır).

GOST 28147-89 algoritmasının bireysel S bloklarını tasarlamak için aşağıdaki prosedür önerilebilir:

• her S-kutusu dört mantıksal işlevle tanımlanabilir, işlevlerin her biri dört mantıksal argümana sahip olmalıdır;
• bu işlevlerin yeterince karmaşık olması gerekir. Bu karmaşıklık gerekliliği resmi olarak ifade edilemez, ancak gerekli bir koşul olarak, temel mantıksal işlemler kullanılarak minimum biçimde (yani, mümkün olan minimum ifade uzunluğu ile) yazılan karşılık gelen mantıksal işlevlerin aşağıdakinden daha kısa olmaması istenebilir. belirli bir gerekli değer;
• Bireysel fonksiyonlar, farklı ikame tablolarında kullanılsa bile, birbirinden yeterince farklı olmalıdır.

2011 yılında, GOST 28147-89'un (2256'dan 2225'e) direncini biraz azaltan yeni bir “ortada yansımalı toplantı” saldırısı önerildi. 2012 itibariyle algoritmanın kriptanalizinin en iyi sonucu, gücünü 2.192'ye düşürür ve nispeten büyük bir şifreli metin boyutu ve önceden oluşturulmuş bir veri hacmi gerektirir. Önerilen saldırılara rağmen, GOST 28147-89, bilgisayar teknolojisinin mevcut gelişme düzeyinde pratik olarak sabit kalmaktadır.

"Magma" kodu (GOST R 34.12-2015). GOST 28147-89 standardı Rusya'da 25 yılı aşkın bir süredir yürürlüktedir. Bu süre zarfında, düşük kaynaklı cihazlarda olanlar da dahil olmak üzere yazılım ve donanım uygulamalarının yeterli dayanıklılığını ve iyi verimliliğini göstermiştir. Direnç tahminlerini azaltan kriptanalitik saldırılar önerilmiş olsa da (en iyisi 2,192'dir), bunlar uygulanabilir olmaktan uzaktır. Bu nedenle, yeni geliştirilen simetrik şifreleme standardına GOST 28147-89 algoritmasının dahil edilmesine karar verildi.

2015 mağazasında iki yeni ulusal şifreleme standardı kabul edildi: GOST R 34.12-2015 “Bilgi teknolojisi. Kriptografik bilgi koruması. Blok şifreleri "ve GOST R 34.13-2015" Bilgi teknolojisi. Kriptografik bilgi koruması. 1 Ocak 2016'da yürürlüğe giren "blok şifrelerinin çalışma modları".

GOST R 34.12-2015 standardı, blok uzunluğu 128 ve 64 bit olan iki blok şifresinin bir tanımını içerir. Sabit doğrusal olmayan ikame bloklarına sahip GOST 28147-89 şifresi, yeni GOST R 34.12-2015'e "Magma" adı verilen 64 bitlik bir şifre olarak dahil edilmiştir.

Standartta sabitlenen yedek bloklar aşağıdadır:

Standartta verilen S-kutuları seti, kriptoalgoritmanın diferansiyel ve lineer kriptanalize direncini belirleyen en iyi özellikleri sağlar.

"Bilginin kriptografik korunması" (TC 26) standardizasyon teknik komitesine göre, doğrusal olmayan ikame bloklarının sabitlenmesi GOST 28147-89 algoritmasını daha birleşik hale getirecek ve "zayıf" doğrusal olmayan ikame bloklarının kullanımının ortadan kaldırılmasına yardımcı olacaktır. Ek olarak, şifrenin tüm uzun vadeli parametrelerinin standartta sabitlenmesi, kabul edilen uluslararası uygulamayı karşılamaktadır. Yeni standart GOST R 34.12-2015, terminolojik ve kavramsal olarak uluslararası ISO / IEC 10116 “Bilgi teknolojisi standartları ile bağlantılıdır. Güvenlik Yöntemleri. "-bit blok şifreleri" için çalışma modları (ISO / IEC 10116: 2006 Bilgi teknolojisi - Güvenlik teknikleri - n-bit blok şifresi için çalışma modları) ve ISO / IEC 18033 serisi "Bilgi teknolojisi. Güvenliği sağlama yöntemleri ve araçları. Şifreleme algoritmaları ": ISO / IEC 18033-1: 2005" Bölüm 1. Genel "(ISO / IEC 18033-1: 2005 Bilgi teknolojisi - Güvenlik teknikleri - Şifreleme algoritmaları - Bölüm 1: Genel) ve ISO/IEC 18033-3: 2010 "Bölüm 3. Blok şifreleri" (ISO / IEC 18033-3: 2010 (Bilgi teknolojisi - Güvenlik teknikleri - Şifreleme algoritmaları - Bölüm 3: Blok şifreleri)).

GOST P 34.12-2015 standardı ayrıca 128 bitlik blok boyutuna sahip yeni bir blok şifresi ("Çekirge") içerir. Bu şifrenin bugün bilinen tüm blok şifreleme saldırılarına karşı sağlam olması bekleniyor.

Blok şifrelerin çalışma modları (basit değiştirme, gama, çıktı geri bildirimli gama, şifreli metin geri bildirimli gama, etkileşimli basit değiştirme ve bir taklit ekleme oluşturma) ayrı bir GOST R 34.13-2015 standardına dahil edilmiştir; kabul edilen uluslararası uygulama Bu modlar hem Magma şifresi hem de yeni Grasshopper şifresi için geçerlidir.

• 11 bit bit düzeyinde dairesel sola kaydırma gerçekleştirilir. Şifre çözme aynı şemaya göre, ancak farklı bir anahtar kullanım planı ile gerçekleştirilir: 1. ila 8. şifre çözme turuna - doğrudan sırada: 9. ila 32. şifre çözme turuna - ters sırada: GOST 28147-89'daki DES şifresi aşağıdaki avantajlara sahiptir: önemli ölçüde daha uzun bir anahtar (DES şifresi için 56 bit'e karşı 256 bit), şu anda anahtar kümesinin kaba kuvvetle numaralandırılmasının imkansız göründüğü bir saldırı; Algoritmanın uygulanmasını basitleştiren ve hesaplamaların hızını artıran anahtarı kullanmak için basit bir program. S-bloklarının tasarımı GOST 28147-89. GOST 28147-89 algoritmasının şemasının çok basit olduğu açıktır. Bu, en büyük şifreleme yükünün ikame tablolarına düştüğü anlamına gelir. Sekme değerleri
• Panasepko S.P. Şifreleme algoritmaları: özel bir referans kitabı. SPb.: BHV-Peter-burg, 2009.
• Kara O. Ürün Şifrelerine Yansıma Saldırıları. URL: http://eprint.iacr.org/2007/043.pdf
• Rus şifreleme standardı: güç azaltıldı. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Onu gömmek için acele etmeyin."

Cebirsel kriptanalizin kurucusu, ünlü araştırmacı Nicolas Courtois, yakın gelecekte uluslararası bir standart haline gelecek olan GOST blok şifresinin aslında kırıldığını ve gelecekte fikirlerini geliştirecek birçok yayın beklediğini iddia ediyor. Bu algoritmanın kararsızlığı hakkında.

Aşağıdakiler, uluslararası standardizasyonun ortasında alarmist bir saldırı olarak kabul edilebilecek bu çalışmadan kısa alıntılardır (yazar AES ile ilgili benzer abartılarla biliniyordu, ancak çalışması o zamanlar kriptanaliz üzerinde büyük bir teorik etkiye sahipti, ancak AES'in kendisine pratik bir saldırıya yol açmadı). Ancak, belki de bu, SHA-1 karma algoritmasında olduğu gibi, ulusal şifreleme standardının çöküşüyle ​​sona erebilecek olan "uçağın kuyruk dönüşüne dalması" aşamasının başlangıcı hakkında gerçek bir uyarıdır ve fiili MD5 karma algoritması.

GOST 28147-89 1989'da standardize edildi ve ilk kez gizli bilgilerin korunması için resmi standart haline geldi, ancak şifre belirtimi kapalı kaldı. 1994 yılında, standart sınıflandırıldı, yayınlandı ve İngilizce'ye çevrildi. AES ile benzer şekilde (ve DES'den farklı olarak), GOST'un sınıflandırılmış bilgileri Rus standardında belirtilen şekilde kısıtlama olmaksızın korumasına izin verilir. O. GOST, DES'in bir analogu değil, üç bağımsız anahtar veya AES-256 ile 3-DES'in rakibidir. Açıkçası GOST, en ciddi uygulamaların beklentisiyle oluşturulmuş, askeri kriterleri karşılayan oldukça ciddi bir şifredir. Rus bankaları tarafından kullanılan uygulamalara dayalı olarak en az iki GOST S kutusu seti tanımlanmıştır. Bu bankaların yüzlerce şubeyle gizli iletişim kurması ve milyarlarca doları dolandırıcılık amaçlı hırsızlıktan koruması gerekiyor.

GOST, 64 bit blok boyutu, 256 bit anahtar ve 32 tur ile basit bir Feistel yapısına sahip bir blok şifredir. Her turda modulo 2 ^ 32 anahtar ekleme, sekiz adet 4 bitlik S-kutu seti ve basit bir 11 bit döngüsel kaydırma bulunur. GOST'un bir özelliği, etkin anahtar malzemesini 610 bite çıkaran ikinci bir anahtar olarak temsil edilebilen S-bloklarını gizli olarak saklama yeteneğidir. Bir dizi S-kutusu 1994 yılında GOST-R 34.11-94 hash fonksiyonu spesifikasyonunun bir parçası olarak yayınlandı ve Schneier'in yazdığı gibi, Rusya Federasyonu Merkez Bankası tarafından kullanıldı. Ayrıca "id-GostR3411-94-CryptoProParamSet" kısmında RFC4357 standardında yer almaktadır. Schneier'in kitabının sonundaki (S-kutu sırasına göre) kaynak kodunda bir hata vardı. Yerli Rus kökenli en doğru referans uygulaması artık OpenSSL kitaplığında bulunabilir. Bir yerde gizli S kutuları kullanılıyorsa, yazılım uygulamalarından ve mikro devrelerden çıkarılabilirler, aslında ilgili çalışmalar yayınlandı.

GOST ciddi bir rakip

Çok büyük anahtar boyutuna ek olarak, GOST, AES ve diğer benzer şifreleme sistemlerine kıyasla önemli ölçüde daha düşük yürütme maliyetine sahiptir. Aslında, çok daha düşük beyan edilen güvenlik için dört kat daha fazla donanım mantık kapısı gerektiren AES'ten çok daha düşük maliyetlidir.

GOST'un bir İnternet standardı haline gelmesi şaşırtıcı değil, özellikle OpenSSL ve Crypto ++ gibi birçok kripto kütüphanesinde yer alıyor ve menşe ülkesi dışında daha popüler hale geliyor. 2010 yılında GOST, ISO standardizasyonu için dünya çapında bir şifreleme standardı olarak ilan edildi. Çok az sayıda algoritma uluslararası standart haline gelebilmiştir. ISO / IEC 18033-3: 2010, aşağıdaki algoritmaları açıklar: dört 64 bit şifre - TDEA, MISTY1, CAST-128, HIGHT - ve üç 128 bit şifre - AES, Camellia, SEED. GOST'un aynı ISO/IEC 18033-3 standardına eklenmesi önerilmektedir.

Endüstriyel standardizasyon tarihinde ilk kez, maliyet ve güvenlik seviyesi arasındaki optimallik açısından böylesine rekabetçi bir algoritma ile uğraşıyoruz. GOST, 20 yıllık kriptanaliz çabalarına sahiptir ve yakın zamana kadar askeri düzeyde güvenliği sorgulanmamıştır.

Yazarın yakın zamanda özel yazışmalardan öğrendiği gibi, çoğu ülke Singapur'daki ISO oylamasında GOST'a karşı çıktı, ancak bu oylamanın sonuçları hala ISO SC27 genel kurulu toplantısında değerlendirilecek, bu nedenle GOST o tarihte hala standardizasyon sürecinde. bu eserin yayınlanması.

GOST hakkında uzman görüşleri

GOST ile ilgili mevcut bilgi ve literatürdeki hiçbir şey, şifrenin güvensiz olabileceğine inanmak için temel oluşturmaz. Aksine, büyük anahtar boyutu ve çok sayıda tur, GOST'u ilk bakışta onlarca yıllık kullanım için uygun hale getirir.

Moore Yasasına aşina olan herkes, teorik olarak 256-bit anahtarların en az 200 yıl boyunca güvende kalacağını bilir. GOST, Schneier, Biryukov, Dankelman, Wagner gibi blok şifreleme analizi alanında bilinen kriptografi alanında önde gelen uzmanlar, birçok Avustralyalı, Japon ve Rus bilim adamı, ISO'dan kriptografi uzmanları ve tüm araştırmacılar tarafından kapsamlı bir şekilde incelenmiştir. güvende olabileceği veya olması gereken her şeyin böyle göründüğünü ifade etti. Görüş, GOST'un yapısının, örneğin DES'e kıyasla son derece zayıf olduğu konusunda geniş bir anlayışa ulaşmış olsa da, özellikle difüzyonun o kadar iyi olmadığı, ancak bunun nedeni her zaman bunun telafi edilmesi gerektiği gerçeğiydi. modül ilavesiyle sağlanan ek bir doğrusal olmama ve difüzyonun yanı sıra çok sayıda tur (32).

Biryukov ve Wagner şunları yazdı: "Çok sayıda tur (32) ve iyi çalışılmış Feistel yapısı, birbirini takip eden Shannon'ın permütasyonlarıyla birleştiğinde, GOST güvenliği için sağlam bir temel sağlıyor." Aynı çalışmada şunu okuyoruz: "önemli bir zaman ve çaba yatırımından sonra, açık literatürde standardın kriptanalizinde hiçbir ilerleme kaydedilmemiştir." Böylece, GOST'un birçok farklı rastgele anahtarla şifrelemede kullanıldığı gerçekçi bir senaryoda şifre çözmeye veya anahtar kurtarmaya izin verecek önemli saldırılar olmadı. Buna karşılık, GOST'ta zayıf anahtarlara yönelik saldırılar, ilişkili anahtarlara yönelik saldırılar, gizli S-kutularını kurtarmaya yönelik saldırılar hakkında bilinen birçok çalışma vardır. Crypto-2008'de, bu şifreye dayalı bir hash fonksiyonunun hacklenmesi sunuldu. Tüm saldırılarda, saldırganın normalde izin verilenden önemli ölçüde daha fazla serbestliği vardır. Rastgele seçilmiş anahtarları kullanan geleneksel şifreleme uygulamalarında, şimdiye kadar GOST'a ciddi bir kriptografik saldırı bulunmadı, bu 2010'da son ifadeyle ifade edildi: "kriptanalistlerin son 20 yıldaki önemli çabalarına rağmen, GOST henüz bulunamadı. cracked" (Axel Poschmann, San Ling ve Huaxiong Wang: 650 GE GOST Revisited için 256 Bit Standardized Crypto, In CHES 2010, LNCS 6225, s. 219-233, 2010).

Doğrusal ve diferansiyel analiz GOST

Schneier'in iyi bilinen kitabında şunları okuyoruz: "Diferansiyel ve doğrusal kriptanalize karşı, GOST muhtemelen DES'ten daha sağlamdır." GOST'un güvenliğinin ana değerlendirmesi 2000 yılında Gabidulin ve diğerleri tarafından yapılmıştır.Sonuçları çok etkileyicidir: 2 ^ 256 setlik bir güvenlik seviyesi ile, GOST'yi lineer kriptanalizden korumak için beş tur yeterlidir. Ayrıca, S-kutularını aynı olanlarla değiştirdikten ve tek doğrusal olmayan şifreleme işlemi - mod 2 ^ 32 eklendikten sonra bile - şifre, 32'den 6 turdan sonra hala doğrusal kriptanalize karşı dirençlidir. GOST diferansiyel kriptanalizi nispeten daha kolay görünüyor ve daha fazla dikkat çekiyor. 2 ^ 128 güvenlik seviyesi için, araştırmacılar (Vitaly V. Shorin, Vadim V. Jelezniakov ve Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Elsevier Preprint'e sunulan Preprint, 4 Nisan 2001) 7 turda yeterli dayanıklılığı varsaydılar. Onlara göre, GOST'u beşten fazla turda kırmak "son derece zor". Ayrıca, iki Japon araştırmacı, bir diferansiyel özelliği olan klasik bir doğrudan diferansiyel saldırının, çok sayıda turdan geçme olasılığının son derece düşük olduğunu göstermiştir. Sınırlı sayıda tur için (kendi başına tur başına 2-11,4'ten daha iyi geçme olasılığı olmayan) yeterince "iyi" bir yinelemeli diferansiyel karakteristik çalışma gerçeğine dayanarak, uygun anahtar kümesinin değeri yarıdan azdır. . Tam kapsamlı bir GOST için, tek bir özelliğe sahip böyle bir saldırı, yalnızca 2-62 mertebesindeki tuşların ihmal edilebilir bir kısmı ile çalışacaktır (ve bu küçük kısımda bile, 2-360'tan fazla geçme olasılığı olmayacaktır). ).

Daha karmaşık saldırılar, sıfır diferansiyeline sahip ayrı S-kutuları kullanmak ve diğer bitlerin sıfır olmayanlara sahip olması gibi, belirli kalıpları takip eden çoklu diferansiyelleri içerir. GOST'un zayıf yayılma özelliklerine dayanan ayrımcı saldırılardan bahsediyoruz. Bu saldırıların en iyisi 17 GOST turuna karşı çalışır, anahtara bağlıdır ve çıktının kendisinde rastgele verilerden son derece zayıf bir ayırıcıya sahiptir, böylece bir şekilde anahtar hakkında bilgi elde etmek için kullanılabilir.

Kayma ve saptırma saldırıları

Biryukov ve Wagner'e göre, son turlarda alt anahtarların ters sırasını içeren GOST yapısı, onu kayan saldırılara ("kayma saldırıları" olarak adlandırılan) dayanıklı hale getiriyor. Bununla birlikte, şifrede büyük bir kendi kendine benzerliğin varlığı nedeniyle, bu, belirli zayıf anahtarlar için sabit noktaların ve "yansıma" özelliklerinin ("yansıma saldırıları" olarak adlandırılan) kombinasyonlarına anahtar ters çevirme saldırılarına izin verir. Bu saldırının karmaşıklığı 2 ^ 192 ve 2 ^ 32 eşleşen düz metindir.

Son sonuçlar

FSE 2011 konferansında sunulan yeni saldırılar da yansımayı kullanır ve aslında GOST'u bozar.Bu saldırılar da bu makalenin yazarı tarafından bağımsız olarak keşfedilmiştir. Saldırı, 2 ^ 132 bayt bellek gerektirir; bu, aslında daha az bellek gereksinimi olan daha yavaş saldırılardan daha kötüdür.

Çeşitli yeni kendi kendine benzerlik saldırıları, tüm GOST anahtarlarına karşı çalışır ve daha önce olduğu gibi yalnızca zayıf anahtarlar için değil, tam kapsamlı bir GOST'yi 256 bit anahtarla kırmanıza olanak tanır. Tüm bu saldırılar, önemli ölçüde daha az bellek gerektirir ve önemli ölçüde daha hızlıdır.

Bu yeni saldırılar, "cebirsel karmaşıklık azaltma" olarak adlandırılan blok şifrelerinin kriptanalizine yönelik yeni bir genel paradigmanın örnekleri olarak görülebilir ve bu saldırıların bilinen sabit noktalara, kaymalara, dönüşlere ve döngülere sahip birçok özel saldırı vakasına genelleştirilmesiyle birlikte. Tüm bu saldırıların ailesi arasında, GOST'un herhangi bir yansıma olmadan ve hesaplamalar sırasında ortaya çıkan herhangi bir simetrik nokta olmadan kriptanalize izin verenlerin olması önemlidir. Bir örnek, bu çalışmaya yansımayan basit bir GOST hack saldırısıdır.

Azaltılmış Tur Şifrelerine Cebirsel Kriptanaliz ve Düşük Veri Karmaşıklığı Saldırıları

Blok ve akış şifrelerine yönelik cebirsel saldırılar, belirli bir şifreleme şemasının geometrisini ve yapısını izleyen büyük bir Boole cebirsel denklem sistemini çözme problemi olarak temsil edilebilir. Bu fikir Shannon'a kadar uzanır. Uygulamada, DES için (ilk olarak bu çalışmanın yazarı tarafından sunulmuştur) resmi bir kodlama yöntemi olarak sunulmuştur ve bilinen tek bir düz metinde 6 tur kırabilir. Denklem işleme, XL algoritmalarına, Gröbner tabanlarına, ElimLin yöntemine, SAT çözücülerine dayanmaktadır.

Pratikte, çok az sayıda blok şifreleme turuna karşı cebirsel saldırılar uygulandı, ancak zaten akış şifrelerinin kırılmasına yol açtı ve mikro ekipman için ultra hafif şifreleri kırmada da başarılar var. Bellek boyutu ve hesaplama maliyeti tahminlerindeki zorluklar nedeniyle, diğer saldırılarla birleştirilirler.

GOST nasıl hacklenir?

Tam kapsamlı bir GOST'a cebirsel bir saldırı bu yayında daha ayrıntılı olarak sunulmaktadır. Daha önceki bir çalışmada, yazar GOST'a yönelik 20 cebirsel saldırıyı zaten özetledi ve yakın gelecekte çok sayıda olmasını bekliyor. Bu çalışmada önerilen saldırı en iyisi değil, ancak GOST'u kırmak için özel bir metodoloji oluşturmak için sonraki gelişmeler için kolay (en azından kriptografların anlayışı için) bir yol açıyor.

Pratik sonuç hala mütevazı: 2 ^ 64 bilinen düz metin ve düz metin / şifreli metin çiftlerini depolamak için 2 ^ 64 bellek, GOST 2 ^ 8'i basit kaba kuvvetten daha hızlı kırmayı mümkün kılar. Ancak kriptanaliz açısından bu, "GOST kırıldı" demeyi tamamen adil kılar.

sonuçlar

GOST, gelecek 200 yıl boyunca askeri düzeyde güvenlik sağlamak üzere tasarlanmıştır. GOST'u inceleyen önde gelen uzmanların çoğu, "20 yılı aşkın önemli kriptanalitik çabalara rağmen, GOST henüz kırılmadı" konusunda hemfikir oldular. 2010 yılında GOST, küresel şifreleme standardı olarak ISO 18033'e yükseltildi.

Cebirsel kriptoanaliz hakkındaki fikirlerin temeli 60 yıl öncesine dayanmaktadır. Ancak sadece son 10 yılda birçok NP-tam problemin (kısmi) çözümü için etkili yazılım araçları geliştirildi. Bir dizi akış şifresi kırıldı. Bu yöntemle yalnızca bir blok şifre kırıldı - zayıf KeeLoq'un kendisi. Bu çalışmada, yazar önemli, gerçekten kullanılan bir GOST şifresini kırar. Standart bir durum şifresinin cebirsel kriptanaliz tarafından kırıldığının tarihte ilk kez olduğunu belirtiyor.

GOST'a yönelik basit bir "MITM" saldırısı FSE 2011 konferansında zaten sunuldu.Bu makalede tartışılan çalışmada, yalnızca GOST'a halihazırda kaç saldırının ortaya çıktığı gerçeğini göstermek için başka bir saldırı sunulmuştur, bunların çoğu daha hızlıdır ve cebirsel bir saldırı çok daha az bellek gerektirir ve rakibin şifreye farklı şekillerde saldırması için neredeyse tükenmez bir olasılık alanı açar. Ayrıca bu yazıda, hackleme için yansıma özelliğinin kullanılmasına gerek olmadığı gösterilmiştir.

Yazar, GOST'un ciddi kusurları olduğunun aşikar olduğunu ve şu anda ISO'nun gerektirdiği dayanıklılık seviyesini sağlamadığını iddia ediyor. GOST'a yönelik birçok saldırı, cebirsel karmaşıklığı azaltma paradigmasının onaylanmasının bir parçası olarak sunulmuştur.

Son olarak, araştırmacı, özellikle ISO standardizasyon sürecinde önemli olan, okuyucunun henüz erişemeyeceği, ancak araştırmacının bildiği bazı gerçekleri not eder. Bu saldırı, yalnızca kaba kuvvet kaba kuvvet saldırısından daha hızlı olan GOST'a yönelik bir "sertifika" saldırısı değildir. Aslında, GOST'u standart hale getirmek artık son derece tehlikeli ve sorumsuz olacaktır. Bunun nedeni, bazı saldırıların pratik olmasıdır. Pratikte, ister zayıf anahtarlar, isterse GOST'un özel gerçek uygulamalarından gelen anahtarlar olsun, bazı GOST anahtarlarının şifresi çözülebilir. Önceki çalışmada yazar, pratik saldırı olasılığı vakalarının ayrıntılı bir değerlendirmesini verir. Anlamlı bir şekilde, "tarihte ilk kez, askeri düzeydeki sırları korumak için tasarlanmış ve devlet sırlarını hükümetler, büyük bankalar ve diğer kuruluşlar için korumak için tasarlanmış ciddi bir standartlaştırılmış blok şifreleme, matematiksel bir saldırıyla ele geçirildi."