Kriptolojinin matematiksel temelleri

Bunlarada Bakarsınız

S.A. DORICHENKO, V.V. YAŞÇENKO

25

ÇALIŞMALAR

ŞİFRELER HAKKINDA

Modern kriptografi hakkında popüler

MOSKOVA “TEİS” 1994

 

Seri "Kriptolojinin Matematiksel Temelleri"

Sanatçı A.Yu.Sharapanova

Dorichenko S.A., Yashchenko V.V. Şifreler üzerine 25 çalışma. — M.: TEİS, 1994. —69 s.

Kitap yeni bir dizi "Kriptolojinin Matematiksel Temelleri" açar. Moskova Devlet Üniversitesi Kriptografinin Matematiksel Problemleri Laboratuvarı çalışanları tarafından kriptografiye popüler bir giriş olarak yazılmıştır.

Kitap, Rusça'da ilk kez, kriptografinin temel kavramlarını katı ama erişilebilir bir biçimde açıklıyor. Kriptografinin matematiksel aparatından gerekli bilgiler verilir. Ayrıca, modern kriptografinin en son fikirleri sunulmaktadır.

Tarihten ve polisiye literatürden iyi bilinen şifreler örnek olarak incelenmiştir.

Kitap aynı zamanda kriptografinin temel kavramları için popüler bir referans olarak da kullanılabilir.

Geniş bir okuyucu yelpazesi için.

 

İÇERİK

Önsöz         5

Giriiş. Bu kitabı nasıl okumalı         6

Bölüm 1. Temel kavramlar         8

1. Ne zaman ve neden korunmalı?

bilgi         8

2. Kriptografiden farkı nedir?

steganografi                         10

3. Ana şeyi nasıl hayal edebilirsiniz?

kriptografi nesnesi         12

4. Sanat olarak kriptografi.

biraz tarih         14

5. 18 nedir        
6. Şifreye saldırı. Şifre gücü         20
7. Kriptografi ve kriptoloji         22
8. Neden birçok farklı şifre makinesine ihtiyaç duyulur         23

9. Kriptografinin seviyeye bağımlılığı

teknoloji         24

Bölüm 2. Matematiksel Temeller         25

1. Herhangi bir bilgi getirmek

ikili         25'e

2. Rastgelelik ve düzenlilik

ikili dizilerde         27

3. Algoritma nedir ve karmaşıklığı         31

2.4♦ Değiştirme ve permütasyon şifreleri        

5. Kesinlikle güçlü bir şifre mümkün mü?        

6. Dayanıklılık teorik ve pratik        

7. Anahtara saldırmak her zaman gerekli midir?        

8. Kriptografi, kombinatoryal algoritmalar

ve bilgi işlem        

Bölüm 3 Yeni Yol Tarifi        

1. tek yönlü işlev nedir        

2. Tek yönlü bir işlev ne verir?

kriptografi için        

3. Modern kriptografide sayılar ve alanlar        

4. Sayı çarpanlarına ayırma problemleri ve

ayrık logaritma        

5. RSA şifreleme sistemi        

6. Ortak anahtar dağıtımı        

7. Elektronik imza                        

8. kriptografik protokol nedir        

Çözüm                

Kriptografi hakkında başka ne okuyabilirsiniz?        

Başvuru. Kriptografide olimpiyatların seçilmiş görevleri        

Önsöz

Sevgili okuyucu! "Kriptolojinin Matematiksel Temelleri" adlı yeni serinin ilk kitabı karşınızda. Dizi, bilgi güvenliği, şifreleme ve şifre çözme, dijital imza, bilgisayar güvenliği vb. ile ilgili sorunların ve sorunların popüler bir sunumu olarak tasarlandı.

Günümüzde, belirli çıkarların (devlet, ticari, kişisel vb.) Sağlanması için bu tür görevlerin çoğu kez çözülmesi gerekmektedir. Bunları çözmenin en güvenilir yolu, yasadışı kullanıcılardan korumak için bilgileri dönüştürme (şifreleme) yöntemleri bilimi olan kriptografidir. Kriptografi, temel bilimlerin ve her şeyden önce matematiğin en son başarılarına dayanmaktadır.

“25 Studies on Ciphers” kitabı, modern kriptografinin matematiksel problemleri hakkında bir fikir veriyor. Kriptografinin tüm temel kavramlarını tanıtır ve örneklerle açıklar. Kesin ama halka açık bir biçimde, gerekli matematiksel tanımlar verilir ve kriptografiye ilişkin birçok fikir, bunların temelinde açıklanır. Örnek olarak, tarih ve macera literatüründen yaygın olarak bilinen şifreler kullanılır.

Kitap, kriptografi hakkında Rusça literatürde şu anda var olan bir boşluğu dolduruyor. Geniş bir okuyucu kitlesinin ilgisini çekebilir. Kesinliği ve özlülüğü nedeniyle, kriptografinin temel kavramları için popüler bir referans olarak eğitim amaçlı olarak da kullanılabilir.

N.N. Andreyev

Kriptografi Akademisi Başkanı

Rusya Federasyonu

астоящая книга является популярным изложением

 Giriş
BU KİTABI NASIL OKUYUN

modern kriptografinin temel kavramları ve fikirleri ve daha ince - kriptografinin matematiksel sorunları. Yeni bir dizi “Kriptolojinin Matematiksel Problemleri” açar.

Yazarlar, küçük bir ciltle mümkün olduğunca çok bilgi vermek için kitap için etüt veya eskiz türünü seçtiler. Aynı soruların tam bir sistematik açıklaması yüzlerce sayfa gerektirir. Meraklı okuyucular, yurtdışında yayınlanan ders kitaplarına ve kitabın sonunda listesi verilen Rusça yayınlara yönlendirilir.

Kitabın amaçlarından biri, kriptografinin matematiksel problemlerine giriş yapmaktır. Bu nedenle, ikinci ve özellikle üçüncü bölümler, matematiksel düşünmeye meyilli bir okuyucu için tasarlanmıştır. Ancak kitabı anlamak derin bir matematik bilgisi gerektirmez.

Ana terim ve kavramlar metinde ilk kullanıldıkları yerde italik olarak vurgulanmıştır. Bazen bu kavramın resmi bir tanımı "metnin içine küçük puntolarla girer".

Bazı etütler, etüt başlığına konulan bir sorunun cevabıdır. Bu nedenle, şu şekilde yapılandırılırlar: önce soruya kısa ve resmi bir cevap verilir, ardından daha ayrıntılı yorumlar ve örnekler verilir. Böyle bir etüdü okuduktan sonra başa dönmekte ve yeni bilgilerle etüdün ana sorusunun cevabını tekrar okumakta fayda var.

Bazı okuyucular sadece okumak değil, anlamak, her çalışma hakkında daha derin düşünmek isteyeceklerdir. Onlar için bazı etütler, kontrol sorularını ve görevleri içeren bir "Kendin için düşün" bölümü ile desteklenir . Ek olarak, Ek, Olimpiyatların kriptografideki en ilginç sorunlarını listeler.

Kitabı okurken bazı bölümleri anlamakta güçlük çekiyorsanız üzülmeyin: büyük olasılıkla bu parça büyük bir bilime açılan bir "pencere" dir.

Şu anda teorik kriptografi, matematiğin birçok bölümünün kavramlarını ve sonuçlarını kullanır: cebir, sayılar teorisi, algoritmalar ve hesaplamaların karmaşıklık teorisi, kodlama teorisi vb. Bu nedenle, modern bir kriptograf için her şeyden önce iyi bir matematiksel hazırlık önemlidir.

Mesleği olarak kriptografiyi seçmeye karar veren okul çocukları için üç üniversiteden birini öneriyoruz:

• Rusya Federasyonu Federal Şebeke Şirketi Güvenlik Akademisi Kriptografi, İletişim ve Bilişim Enstitüsü (ICSI);

• Mekanik ve Matematik Fakültesi, Lomonosov Moskova Devlet Üniversitesi M.V. Lomonosov (Moskova Devlet Üniversitesi);

• Rusya Devlet Beşeri Bilimler Üniversitesi (RSUH) Bilgi Güvenliği Fakültesi.

Yazarlar, bu kitabın yazılmasının her aşamasında tartışmaya katılan Moskova Devlet Üniversitesi Kriptografinin Matematiksel Problemleri Laboratuvarı personeline teşekkür etmek isterler.

SA Dorichenko

VV Yaschenko

Bölüm 1

ANAHTAR KAVRAMLAR
1.1• Bilgiler ne zaman ve neden korunmalı?

Ne zaman? Bilgilerin, meşru kullanıcının zararına çevirebilecek yabancıların eline geçeceği korkusunun olduğu durumlarda.

Ne için? Bilgilerin açıklanmasından kaynaklanabilecek olası zararları önlemek için.

Bilgi, çeşitli verilerin iletilmesi, işlenmesi ve saklanması süreçlerini inceleyen bilimsel alanların temel kavramıdır. Bilgi kavramının özü genellikle ölçülerle açıklanır         . Resmi bir tanım verilmemiştir,

■'bildiğim kadarıyla bilgi kavramı f J D•־ ifade eder. '•?         madde ile aynı temel kavramlar.

-         •'•'İnsanlar uzun zamandır bilginin

gerçek bir hazinedir ve bu nedenle hem korunması hem de üretilmesi için genellikle çok çaba harcanmıştır. Genel olarak konuşursak, mutlaka bir tür “casusluk” vakasıyla bağlantılı değildir. Korunması gereken bilgiler, çeşitli yaşam koşullarında ortaya çıkar. Genellikle bu gibi durumlarda bilginin sır içerdiği veya korunan, özel, gizli, gizli olduğu söylenir . Bu türden en tipik, sık karşılaşılan durumlar için özel konseptler bile getirilmiştir:

• devlet sırrı;

• bir askeri sır;

• meslek sırrı;

• yasal gizlilik;

• tıbbi sır vb.

bu tür bilgilerin aşağıdaki özelliklerini göz önünde bulundurarak korunan bilgilerden bahsedeceğiz :

• bu bilgilere sahip olma hakkına sahip belirli bir yasal kullanıcı çevresi vardır ;

• bu bilgileri kendi çıkarlarına ve meşru kullanıcıların zararına çevirmek için elde etmeye çalışan yasa dışı kullanıcılar var .

tehdidi - bilgilerin ifşası tehdidini dikkate almakla sınırlıyoruz . Korunan bilgilere yönelik yasa dışı kullanıcılardan gelen başka tehditler de vardır: ikame, taklit vb. İlgili okuyucunun, bilgilerin ikamesi ve taklidi ile ilgili sorunlar hakkında benzer şekilde düşünmesini öneririz.

Artık hayat, insanlar arasında, genellikle çok uzak mesafelerde yoğun bir bilgi alışverişi olacak şekilde düzenlenmiştir. Bunu yapmak için, dünya çeşitli teknik iletişim araçlarıyla karışmıştı : telgraf, telefon, radyo, televizyon vb. Bu durumda, yasa dışı bir kullanıcı, kamuya açık bir teknik iletişim kanalından bilgi almaya çalışabilir . Bundan korkan meşru kullanıcılar, bilgilerini korumak için ek adımlar atmalıdır. Bu tür güvenlik önlemlerinin geliştirilmesinde kriptografi ve steganografi yer alır .

Kriptografi , yasadışı kullanıcılardan korumak için bilgileri dönüştürme (şifreleme) yöntemleri bilimidir.

Steganografi, iletilen bir mesajın gerçeğini gizlemek için bir dizi araç ve yöntemdir.

Şifre , bilgileri yasadışı kullanıcılardan korumak için dönüştürmenin bir yoludur.

Bu çalışmayı sonlandırırken, bir başka önemli sorunun daha olduğunu vurguluyoruz: Bilginin fiyatı, onu koruma maliyetleri ve onu elde etme maliyetleri arasındaki oran sorunu. Bu konunun ayrıntılı bir tartışması bu kitabın kapsamı dışındadır, ancak meraklı okuyucu burada ortaya çıkan çeşitli durumlar üzerinde kendi kendine kafa yorabilir. Sadece teknolojinin mevcut gelişme düzeyiyle, iletişim araçlarının kendisinin yanı sıra onlardan bilgi alma araçlarının ve bilgileri koruma araçlarının geliştirilmesinin çok yüksek maliyetler gerektirdiğini not ediyoruz.

Kendin için düşün:

1. Çalışmada bahsedilen gizem türlerine örnekler veriniz.

2. Örnekleriniz için meşru kullanıcıları, yasa dışı kullanıcıları ve korunan bilgilerin ifşa edilmesinden kaynaklanabilecek olası zararları açıklayın.

2. Kriptografiden farkı nedir?

Steganografi iletişim gerçeğini gizler

iletişim, kriptografi ise mesajın (şifreli biçimde!) yasa dışı bir kullanıcı tarafından erişilebilir olduğunu düşünür, ancak bu mesajdan korunan bilgileri çıkaramaz.

eski zamanlarda kaybolmuştur . Örneğin,

yazılı bir mesajı gizlemenin böyle bir yöntemi bilinmektedir: Bir kölenin başı tıraş edilir, saç derisine bir mesaj yazılır ve saçlar tekrar çıktıktan sonra köle muhatabına gönderilir.

современный метод

Dedektiflik çalışmalarından, sıradan, korumasız bir mektubun satırları arasında çeşitli gizli yazma yöntemleri iyi bilinmektedir: sütten karmaşık kimyasal reaktiflere ve sonraki işlemlere.

Ayrıca dedektiflerden bilinen "mikro noktalar" vardır: mesaj kaydı!-

Modern teknolojinin yardımıyla çok küçük bir ortamda gönderilir - örneğin bir pulun altında veya önceden belirlenmiş başka bir yerde normal bir mektupla gönderilen bir "mikrodot".

Gizli yazmanın tipik bir steganografik tekniği - akrostiş - şiir uzmanları tarafından iyi bilinir. Bir akrostiş, örneğin her satırın ilk harflerinin gizli bir mesaj oluşturduğu şiirsel bir metnin böyle bir organizasyonudur.

yaygın kullanımı nedeniyle , korunan bilgileri bir bilgisayarda depolanan büyük miktarda bilginin içine “gizlemek” için pek çok incelikli yöntem bilinmektedir.

Verilen az sayıda örnekten bile, steganografi kullanıldığında, kriptografiden farklı olarak, korunan bilginin dönüştürülmediği, ancak iletildiği gerçeğinin gizlendiği görülebilir.

Подумайте сами:

1. Bir bilgisayarda saklanan bilgileri korumak için bir tür steganografik yöntem geliştirin.

Kriptografinin ana amacı nasıl temsil edilebilir?

Şöyle hayal edilebilir:

Burada A ve B, uzak meşru kullanıcılar ve korunan bilgilerdir; halka açık bir iletişim kanalı üzerinden bilgi alışverişi yapmak istiyorlar. P , bir iletişim kanalı üzerinden iletilen mesajları yakalayabilen ve onlardan kendisini ilgilendiren bilgileri çıkarmaya çalışan yasa dışı bir kullanıcıdır (düşman) .

, kriptografik bilgi koruma yöntemlerinin uygulandığı tipik bir durumun modeli olarak da düşünülebilir .

Tarihsel olarak bazı tamamen askeri kelimelerin (düşman, şifreye saldırı vb.) kriptografide sabitlendiğine dikkat edilmelidir.Karşılık gelen kriptografik kavramların anlamını en doğru şekilde bunlar yansıtır. Aynı zamanda, bir kod kavramına dayanan yaygın olarak bilinen askeri terminoloji (deniz kodları, Genelkurmay kodları, kod defterleri, kod atamaları vb.) Teorik kriptografiyi çoktan terk ediyor. Gerçek şu ki, son on yılda bir kodlama teorisi oluşturuldu - bilgiyi iletişim kanallarındaki rastgele bozulmalardan korumak için yöntemler geliştiren ve inceleyen yeni bir büyük bilimsel yön. Ve daha önce kodlama ve şifreleme terimleri bir anlamda eşanlamlı olarak kullanılıyorsa, şimdi bu kabul edilemez. Bu nedenle, örneğin, çok yaygın bir ifade olan "kodlama - bir tür şifreleme" yanlış olur.

Kriptografi, bir rakibin ele geçirilen mesajlardan onu çıkarmasına izin vermeyecek bilgileri dönüştürme yöntemleriyle ilgilenir. Bu durumda, iletişim kanalı üzerinden iletilen artık korunan bilginin kendisi değil, bir şifre yardımıyla dönüştürülmesinin sonucudur ve düşman için

şifreyi açmak gibi zor bir görev vardır.

Bir şifreyi açmak (kırmak), kullanılan şifreyi bilmeden şifrelenmiş bir mesajdan (şifreli metin ) korunan bilgileri (düz metin) elde etme işlemidir .

Şifreleme (şifreleme), korunan bilgilere, yani bir şifre uygulama işlemidir . korunan bilgilerin, şifrede bulunan belirli kuralları kullanarak şifreli bir mesaja dönüştürülmesi.

Şifre çözme, şifrelemenin ters işlemidir, yani. şifrelenmiş bir mesajı, şifrede bulunan belirli kuralları kullanarak korumalı bilgiye dönüştürmek.

Bununla birlikte, saldırgan, şifreyi ele geçirip kırmanın yanı sıra, korunan bilgileri başka birçok yoldan da elde etmeye çalışabilir.

Bu yöntemlerin en bilineni gizlidir, yani düşman bir şekilde yasal kullanıcılardan birini işbirliği yapmaya ikna eder ve bu ajanın yardımıyla korunan bilgilere erişim kazanır. Böyle bir durumda, kriptografi güçsüzdür.

Saldırgan, iletim sürecinde korunan bilgileri almaya değil, yok etmeye veya değiştirmeye çalışabilir. Bu, müdahale ve şifreyi kırmadan farklı olarak, bilgiye yönelik tamamen farklı bir tehdit türüdür. Bu tür tehditlere karşı korunmak için kendilerine özgü yöntemler geliştirilmektedir. Korunan bilgilere yönelik birçok tehdit arasında, kriptografi yalnızca birkaç tanesine karşı duruyor. Bu nedenle, bilgileri diğer tehditlerden korumak için kriptografiyi önlemlerle birleştirmek doğaldır.

Bu çalışmanın sonucunda, çoğu zaman korunan bilgi alışverişinin yalnızca iki abone arasında değil - meşru kullanıcılar arasında değil, aboneler ağında gerçekleştiğini ve ardından yeni sorunların ortaya çıktığını not ediyoruz. Ağlar, birimlerden binlerce aboneye kadar farklı boyutlarda olabilir. Bununla birlikte, kriptografinin temel kavramları ve fikirleri, kriptografinin açıklanan ana nesnesi örneği ile anlaşılabilir.

4. яи
5. Sanat olarak kriptografi.
   biraz tarih

Uzun bir süre boyunca kriptografi, yalnız eksantriklerin çoğuydu. Bunların arasında yetenekli bilim adamları, diplomatlar, din adamları vardı. Kriptografinin kara büyü olarak bile kabul edildiği durumlar vardır. Bir sanat olarak kriptografinin bu gelişim dönemi, çok eski zamanlardan, ilk şifreleme makinelerinin ortaya çıktığı 20. yüzyılın başına kadar sürdü. Kriptografi ile çözülen problemlerin matematiksel doğasının anlaşılması, seçkin Amerikalı bilim adamı C. Shannon'ın çalışmalarından sonra ancak 20. yüzyılın ortalarında geldi.

Kriptografi tarihi, çok sayıda diplomatik ve askeri sırla ilişkilendirilir ve bu nedenle bir efsaneler sisi içinde örtülür. Kriptografi tarihiyle ilgili en eksiksiz kitap binden fazla sayfa içerir. 1967'de New York'ta yayınlandı ve henüz Rusçaya çevrilmedi ^[1]). Rusya'da kriptografinin tarihi üzerine temel bir çalışma yakın zamanda Rusça olarak yayınlandı 1b

Pek çok tanınmış tarihi şahsiyet, kriptografi tarihine damgasını vurdu. İşte en çarpıcı örneklerden bazıları.

Şifrelerin askeri işlerde kullanılmasına ilişkin ilk bilgiler, Spartalı komutan Lysander'ın adıyla ilişkilendirilir (şifre ״Scital, MÖ 5. yüzyıl). Sezar, yazışmalarında tarihe Sezar şifresi olarak geçen bir şifre kullandı.” Antik Yunanistan'da, daha sonra Politius Meydanı olarak bilinen bir şifre türü icat edildi. Masonların Kardeşliği, başlangıcından bu yana (VIII.Yüzyıl) bütün bir özel şifreler sistemi geliştirdi ve kullandı. Kriptografi üzerine ilk kitaplardan biri Almanya'da yaşayan başrahip I. Tritelius (1462-1516) tarafından yazılmıştır. 1566'da ünlü tamirci ve matematikçi D. Cardano, icat ettiği şifreleme sistemini (Cardano kafesi) açıklayan bir makale yayınladı. 16. yüzyıl Fransa'sı, kripto sürahiler tarihinde Kral IV. Henry ve Richelieu'nun şifrelerini bıraktı. T. A. Soboleva'nın söz konusu kitabında, yazarı Büyük Peter olan 1700 tarihli “dijital alfabe” de dahil olmak üzere birçok Rus şifresi ayrıntılı olarak anlatılmaktadır.

Şifrelerin özellikleri ve uygulamaları hakkında bazı bilgiler kurmaca, özellikle macera, polisiye ve askeri edebiyatta da bulunabilir. En basit şifrelerden biri olan ikame şifresinin özelliklerinin ayrıntılı bir açıklaması ve açma yöntemleri iki iyi bilinen hikayede yer almaktadır: E. Poe'nun “Altın Böceği” ve A'nın “Dans Eden Adamlar”. . Conan doyle.

ABD'de yayınlanan popüler bilim dergisi “Cryptology”de kriptografi ile ilgili birçok ilginç bilgi yayınlanmaktadır. Kapsamlı bibliyografik liste (111

T.A. Sobolev. Rusya tarihinde gizli yazı. (18. - 20. yüzyılın başlarında Rusya Kriptografik Hizmetinin Tarihi). M., 1994.

Diffie ve Hellman tarafından yazılan çok faydalı ve önemli bir makale 1 ), Rusçaya çevrilmiş ve halka açıktır (bu makalenin yazarlarının kriptografiye devrim niteliğindeki katkısı Bölümde tartışılacaktır). 3).

Üç örneğe daha ayrıntılı bakalım.

Şifre "Scital". Bu şifre, Sparta ve Persler arasında Atina'ya karşı yapılan savaştan beri biliniyor. Spartalı komutan Lysander, Perslerin olası bir ihanet olduğundan şüpheleniyordu, ancak onların gizli planlarını bilmiyordu. Pers kampındaki temsilcisi, Lysander'ın Perslerin önüne geçmesine ve onları yenmesine izin veren şifreli bir mesaj gönderdi. Şifreli mesaj, Perslerden gelen resmi habercinin kemerine şu şekilde yazılmıştır: ajan, kemeri bir scital (belirli çapta ahşap bir silindir) etrafına sardı ve scital boyunca kemerin üzerine bir mesaj yazdı; sonra kemeri çözdü ve harflerin kemer boyunca düzensiz bir şekilde yazıldığı ortaya çıktı. Habercinin, güzel kemerindeki desenin aslında şifreli bilgiler içerdiğinden haberi yoktu. Lysander aynı çapta bir tırpan aldı, kemerini dikkatlice etrafına doladı ve tırpan boyunca ajanından gelen mesajı okudu.

Örneğin, eğer bir kalem ile

altı yüz, daha sonra CRYPTOGRAPHY düz metni bir şifreli metne dönüştürülebilir

Kalemin çapından daha fazlasına bağlı olduğu için şifreli metin farklı olabilir. Deney!

Защищенность и имитостойкость. Вве-

W. Diffie, M. E. Cehennem adamı.

kriptografiye giriş. TIIER, cilt 67, N 3, 1979.

Bu şifrede, açık metnin şifreli metne dönüştürülmesinin, açık metnin harflerinin belirli bir permütasyonundan oluştuğuna dikkat edin. Bu nedenle, ״Scital şifresinin ait olduğu şifreler sınıfına permütasyon şifreleri denir. Çalışma 2.4, bu tür şifrelerin matematiksel açıklamasına ayrılmıştır.

Sezar'ın şifresi. Bu şifre, açık metnin aşağıdaki dönüşümünü gerçekleştirir: açık metnin her harfi, alfabede kendisinden sonra daire şeklinde yazıldığı kabul edilen üçüncü harfle değiştirilir, yani. ״я” harfinden sonra ״а” harfi gelir. Bu nedenle Sezar şifresinin ait olduğu şifreler sınıfına ikame şifreler denir. Çalışma 2.4, bu tür şifrelerin matematiksel açıklamasına ayrılmıştır.

Örneğin, bu şifreleme yöntemiyle KRİPTOGRAFİ düz metni şifreli metne dönüştürülür.

NULTHSEOUGCHLV.

Sezar'ın mektubu üçüncü harfle değiştirdiğini unutmayın, ancak beşinci ve diğerlerini değiştirebilirsiniz. Önemli olan şifreli mesajın gönderildiği kişinin bu shift değerini bilmesidir.

Vigenere şifresi. Bu şifre en uygun şekilde değişken kaydırmalı bir Sezar şifresi olarak düşünülür. Düz metnin bir sonraki harfinin ne kadar kaydırılacağını bilmek için, kaydırmaların nasıl ezberleneceği konusunda önceden anlaşırlar. Vigener'in kendisi , her harfi alfabedeki sayısına göre değişimin büyüklüğünü gösteren bir anahtar kelimeyi ezberlemeyi önerdi . Anahtar kelime, düz metindeki tüm harfleri değiştirmek için gerektiği kadar tekrarlanır. Örneğin, VAZA anahtar kelimesi, aşağıdaki düz metin harf kaydırma dizisi anlamına gelir

3191319131913191...

Örneğin, bu şifreleme yöntemiyle KRİPTOGRAFİ düz metni şifreli metne dönüştürülür.

NSSRPLSGHSA.

Bir anahtar kelime fikrinin daha da geliştirilmesi, yani düz bir metni < bazı kitapları kullanarak dönüştürmenin bir yolunu ezberleme fikri, çeşitli sözde kitap şifrelerinin ortaya çıkmasına neden oldu. Polisiye ve macera edebiyatı sevenler tarafından iyi bilinirler.

Kendin için düşün:

1. Caesar ve Vigenère şifreleriyle deneyler yapın.

2. ״Scytal” şifresini açmanın bir yolunu bulmaya çalışın (: sitalin çapını bilmek).

6. anahtar nedir

anahtar , belirli bir mesajı şifrelemek için kullanılan bir şifrenin değiştirilebilir bir öğesi olarak anlaşılır .

çalışmada açıklanan antik şifre ״Scital”

1.4, anahtar sitalin çapıdır. Aynı zamanda, bir şifre oluşturma ilkesini değiştirmeden, farklı mesajları şifrelemek için farklı çaplarda scitals kullanmak mümkündür.

Sezar şifresi gibi şifrelerde anahtar, şifreli metin harflerinin düz metin harflerine göre kayma miktarıdır.

Anahtar neden gereklidir? Önceki sunumdan, iyi bir şifre icat etmenin zahmetli bir iş olduğu açıktır. Bu nedenle, iyi bir şifrenin “ömrünü” artırmak ve onu mümkün olduğu kadar çok mesajı şifrelemek için kullanmak arzu edilir. Ancak bu durumda, düşmanın şifreyi zaten tahmin etmesi (açması) ve korunan bilgileri okuması tehlikesi vardır. Şifrenin değiştirilebilir bir anahtarı varsa, anahtarı değiştirerek, düşman tarafından geliştirilen yöntemlerin artık bir etkisinin olmamasını sağlamak mümkündür. Bu ilke, özellikle büyük iletişim ağlarında pahalı şifreleme makineleri (şifreleme makineleri) kullanıldığında yararlı ve önemlidir .

Açıklanan hususlar, korunan bilgilerin güvenliğinin öncelikle anahtar tarafından belirlenmeye başlamasına neden oldu. Şifrenin kendisi, şifre makinesi veya şifreleme ilkesi, düşman tarafından biliniyor ve ön çalışma için uygun kabul edilmeye başlandı. Ancak şifrelerde kullanılan bilgi dönüşümleri büyük ölçüde anahtara bağlı olmaya başladı. Ve düşman için yeni bir görev ortaya çıktı - anahtarı belirlemek, ardından bu anahtarda şifrelenmiş mesajları okumak kolay. Meşru kullanıcılar, şifreli mesajları değiş tokuş etmeden önce, düşmandan gizlice anahtar alışverişi yapmalı veya iletişim kanalının her iki ucunda da aynı anahtarı ayarlamalıdır.

Kriptografinin ana nesnesinin resmi açıklamasına geri dönelim (etüd 1.3). Şimdi önemli bir değişiklik yapmak gerekiyor - anahtar değişimi için düşmanın erişemeyeceği gizli bir iletişim kanalı eklemek için:

mesaj tuşları

Büyük bir şifreli mesaj alışverişi için bu tür iletişim ağlarının pratik inşası daha da pahalı bir girişim haline geldi.

Kendiniz için düşünün: 1. Vigenère şifresindeki anahtar nedir?

7. Şifreye saldırı. Şifre Gücü

Bir şifreye yapılan saldırı , şifreyi açma girişimidir.

bu şifre.

Bir şifrenin gücü, bir şifrenin kendisine yönelik her türlü saldırıya karşı koyma yeteneği olarak anlaşılır.

Şifre gücü kavramı, kriptografinin merkezinde yer alır. Niteliksel olarak anlamak oldukça kolay olsa da, her bir özel şifre için kesin olarak kanıtlanabilir güvenlik tahminleri elde etmek çözülmemiş bir sorundur. Bu, böyle bir sorunu çözmek için gerekli matematiksel sonuçların hala olmamasıyla açıklanmaktadır. (Bu konunun tartışmasına etüt 2.6'da döneceğiz.)

şifreye saldıran kriptanalistlerin niteliklerine bağlıdır . İkinci prosedüre bazen dayanıklılık testi denir .

Bir şifrenin gücünü test etmek için önemli bir hazırlık adımı, bir rakibin şifreye saldırabileceği çeşitli olası olasılıkları düşünmektir. Düşman tarafından bu tür fırsatların ortaya çıkması genellikle kriptografiye bağlı değildir, bu bir tür dış ipucudur ve şifrenin gücünü önemli ölçüde etkiler. Bu nedenle, şifre gücü tahminleri her zaman, bu tahminlerin altında elde edildiği düşman hakkındaki varsayımları içerir.

Her şeyden önce, Etude 1.5'te belirtildiği gibi, genellikle düşmanın şifreyi kendisinin bildiği ve önceden inceleme fırsatına sahip olduğu varsayılır. Saldırgan ayrıca düz metinlerin (korumalı bilgiler) bazı özelliklerini de bilir; örneğin, mesajların genel konusu, stilleri, bazı standartları, formatları vb.

Daha spesifik olanlardan, düşmanın yeteneklerine ilişkin üç örnek daha:

• düşman tüm şifrelenmiş mesajları yakalayabilir, ancak karşılık gelen düz metinleri yoktur;

• düşman tüm şifrelenmiş mesajları yakalayabilir ve karşılık gelen düz metinleri çıkarabilir;

• saldırgan şifreye erişebilir (ancak anahtarlara erişemez!) ve bu nedenle herhangi bir bilgiyi şifreleyebilir ve şifresini çözebilir.

Kendi başınıza birkaç düşman seçeneği daha bulmanızı öneririz. Örneğin, düz metinde sözde "olası kelime" nin kullanılmasını önerelim : Düşman, herhangi bir nedenle düz metinde belirli bir kelimenin geçtiğini bilir. Bazen bu tür bilgiler şifreyi kırma sürecini kolaylaştırır.

Yüzyıllar boyunca, uzmanlar arasında şifrelerin güvenliği ve kesinlikle güvenli bir şifre oluşturma olasılığı hakkındaki tartışmalar sona ermedi. İşte bu konuda iki karakteristik ifade.

İngiliz matematikçi Charles Babbage (19. yüzyıl): "Her insan, şifreleri kırma tekniğine aşina olmasa bile, kesinlikle güvenli bir şifre icat edebileceğine inanır ve bu kişi ne kadar zeki ve eğitimliyse, o kadar kesindir. bu kanaat. Ben de bu güveni yıllarca paylaştım.”

״Sibernetiğin Babası” Norbert Wiener (XX yüzyıl): ״Herhangi bir şifre açılabilir, eğer acil bir ihtiyaç varsa ve elde edilmesi gereken bilgi harcanan paraya, emeğe ve zamana değerse...”

Claude Shannon'ın çalışmasından bahsettikten sonra bu konuya etüt 2.5'te döneceğiz.

8. Kriptografi ve kriptoloji

Kriptoloji iki daldan oluşan bir bilimdir: kriptografi ve kriptanaliz.

Kriptografi, yasadışı kullanıcılardan korumak için bilgilerin nasıl dönüştürüldüğü (şifrelendiği) bilimidir.

Kriptanaliz, şifreleri kırma yöntemleri ve araçları hakkındaki bilimdir (ve uygulama pratiğidir).

Son zamanlarda ״cryptography kelimesinin yanı sıra ״cryptology kelimesine de sıklıkla rastlanmakta ancak aralarındaki ilişki her zaman doğru anlaşılamamaktadır. Bu bilimsel disiplinlerin artık son oluşumu gerçekleşmekte, konu ve görevleri belirlenmektedir.

Kriptografi ve kriptanaliz arasındaki ilişki açıktır: kriptografi korumadır, yani. şifrelerin geliştirilmesi ve kriptanaliz bir saldırıdır, yani. şifre saldırısı Bununla birlikte, bu iki disiplin birbiriyle ilişkilidir ve kriptanaliz yöntemlerine hakim olmayan iyi bir kriptograf yoktur. Gerçek şu ki, geliştirilen şifrenin güvenliği ancak şifreye çeşitli saldırılar düzenleyerek, kendinizi zihinsel olarak düşmanın konumuna getirerek kanıtlanabilir (bkz. Etütler 1.6, 2.6).

9. Neden birçok farklı şifre makinesine ihtiyaç duyulur?

Tek, uygun olmadığı için

bilgi şifreleme yönteminin tüm durumları için. Bir kriptografik sistemin seçimi, bilginin özelliklerine, değerine ve sahiplerinin bilgilerini koruma yeteneğine bağlıdır.

Her şeyden önce, çok çeşitli korunan bilgi türlerinin altını çiziyoruz: belgesel, telefon, televizyon, bilgisayar vb. Her bilgi türünün kendine özgü özellikleri vardır ve bu özellikler, bilgi şifreleme yöntemlerinin seçimini büyük ölçüde etkiler. Şifrelenmiş bilgilerin hacimleri ve gerekli iletim hızı büyük önem taşımaktadır. Şifre tipinin seçimi, parametreleri ve gücü önemli ölçüde korunan sırların veya sırların doğasına bağlıdır. Bazı sırlar (örneğin, devlet, askeri vb.) Onlarca yıl saklanmalıdır ve bazıları (örneğin, takas olanlar) birkaç saat içinde ifşa edilebilir. Bu bilgilerin korunduğu düşmanın yeteneklerini de hesaba katmak gerekir. Bir yalnızlığa, hatta bir suçlu çetesine direnmek bir şeydir ve güçlü bir devlet yapısı başka bir şeydir.

Bu kadar çeşitli gereksinimler nedeniyle, yüzlerce türde şifreleme makinesi ve cihazında uygulanan çeşitli şifrelerin geliştirilmesi gerekmektedir. Aynı zamanda, kriptografik olarak en gelişmiş ülkelerde standart şifreler vardır: örneğin ABD'de DES ve Rusya'da SKZD.

10. Kriptografinin
    teknoloji düzeyine bağımlılığı

sonuçları, modern iletişim ağlarına yerleşik şifreleme cihazları şeklinde gerçekleştirilir. Bu nedenle, kriptograflar, şu anda elde edilen teknoloji ve teknoloji düzeyi ile araç seçimlerinde sınırlıdır. Bu bağımlılık , kriptografide kullanılan matematiksel aparatın seçimine de yansır .

Temel olarak farklı üç tanesini ayırt etmek şartlı olarak mümkündür.

До 40-х годов XX

kriptografinin matematiksel aparatının geliştirilmesindeki aşama.

yüzyılda yalnızca elektromekanik şifre makineleri vardı, bu nedenle matematiksel dönüşümlerin aralığı sınırlıydı: esas olarak kombinatoryal analiz yöntemleri ve olasılık teorisi kullanıldı.

Elektronik teknolojisinin ve hatta bilgisayarların ortaya çıkışından sonra, kriptografinin matematiksel aygıtı da çok değişti. Bilgi teorisi, cebir ve sonlu otomata teorisinin uygulamalı fikirleri ve yöntemleri geliştirilmiştir.

Diffie ve Hellman'ın (70'ler) çalışmaları, matematiğin yeni alanlarının hızlı gelişimi için bir itici güç oldu: tek yönlü fonksiyonlar teorisi, sıfır bilgi ispatları. Artık bu alanlardaki ilerleme, kriptografinin pratik olanaklarını belirlemektedir.

Bölüm 2 MATEMATİKSEL
TEMELLER

Yüzyılımızın ortalarında ortaya çıkan Amerikalı matematikçi Claude Shannon'ın çalışmalarının kriptografinin gelişmesinde büyük etkisi oldu. Bu çalışmalarda bilgi teorisinin temelleri atılmış, bilgi ile ilgili bilimin birçok alanında araştırmalar için matematiksel bir aygıt geliştirilmiştir. Bu bölümde, kriptografi alanında hangi başarılı çalışmanın imkansız olduğunu bilmeden, size temel matematiksel kavram ve fikirleri kısaca tanıtacağız.

1. Herhangi bir bilgi getirmek

ikiliye

Matematiksel teoremleri kanıtlamak için uğraştığımız nesneleri açıkça tanımlamak gerekir. Bir metni şifrelerken öncelikle içinde hangi karakterlerin bulunabileceğini bilmek veya daha basit bir ifadeyle alfabeyi bilmek gerekir . Ama pek çok alfabe var. Aktarılan bilgiler ayrıca basit sayı dizilerinden, örneğin banka hesap numaralarından ve bunlara yapılan ödemelerden oluşabilir. Bu nedenle, bazı genelleştirilmiş alfabelerle çalışmak doğaldır - o zaman aynı teoremin, örneğin Rusça ve İngilizce metinler için ayrı ayrı kanıtlanması gerekmeyecektir.

Teorik kriptografide, belirli bir uzunluktaki tüm ikili sözcüklerden oluşan evrensel bir alfabe ile çalışmak alışılmış bir durumdur. n uzunluğunda ikili bir sözcük, n tane sıfır ve birden oluşan bir kümedir. Karşılık gelen alfabe 2n karakterden oluşur . Böyle bir alfabenin seçimi birçok hususla açıklanmaktadır.

Bilgisayarları kullanırken, bilgileri sıfırlar ve birler dizileri şeklinde temsil etmek uygundur. Bu, özellikle kullanılan teknik araçlardan kaynaklanmaktadır: bilgisayar, iki durumdan birinde olabilen öğeler kullanır. Biri 0״”, diğeri 1״” ile gösterilir.

Öte yandan, herhangi bir alfabedeki kelimeler kolayca ikili kelimelere çevrilebilir. Diyelim ki Rusça metinlerle uğraşıyoruz ve ״е” ve ״ё” ile ״и” ve ״й” harflerinin farklı olmamasına izin verin ve kelimeler arasındaki boşluk ayrı bir harf olarak kabul edilir (sembol: _). O zaman alfabemiz otuz iki karakterden oluşuyor. Şimdi ikili sayı sisteminin eski bir teknik uygulaması olan telgraf kodunu ele alalım. Ayrıca 32 karakterden oluşur — 5 uzunluğunda ikili sözcükler. 5 aşağıdaki gibi:

-->00000, A->00001, B->00010, B- >00011,

G->00100, q -> 00,101, ... , u - 11110,         11111.

Metindeki her harfi karşılık gelen ikili kelimeyle değiştirerek, bilgimizin ikili biçimini alırız - bir dizi sıfır ve bir (veya dedikleri gibi, bitler). Aynısını başka herhangi bir alfabe ile yapabilirsiniz.

Uygulamada, bir kişi tarafından girilen metinsel bilgilerin otomatik olarak ikili bilgilere dönüştürülmesine izin veren özel cihazlar oluşturulur.

Üstelik şu anda hemen hemen her bilgi - konuşma, televizyon sinyalleri, müzik vb. - ikili biçimde saklanabilir ve gönderilebilir. Bu tür bilgilerle çalışmak için özel cihazlar kullanılır:

örneğin, ADC ve DAC (analogdan dijitale ve dijitalden analoğa dönüştürücüler), müziğin dijital olarak kaydedilmesi ve çalınması için cihazlar.

Bu nedenle ikili sözcükler ve ikili diziler, kriptografik araştırmalarda tipik nesnelerdir.

Kendin için düşün:

1. n doğal sayısının , - 0 veya 1'de n = 2 k + ak-!2 k ~ 1 + ...+a ! -i, ..., şeklinde benzersiz bir şekilde temsil edildiğini kanıtlayın .

2. Rastgelelik ve düzenlilik

ikili dizilerde

. .-.iptstgtar dizisi okul yıllarından beri bilinmektedir. Bununla birlikte, orada incelenen diziler deterministikti - çeşitli öğelerinden benzersiz bir şekilde yeniden oluşturulmuşlardı .

Böylece, aritmetik ve geometrik ilerlemeler, ardışık terimlerinden herhangi ikisi tarafından geri yüklenir. Polinomun tamsayı noktalarındaki değerleri de deterministik bir dizi oluşturur: terimlerinden herhangi biri tarafından belirlenir , burada n , verilen polinomun derecesidir (kanıtlayın!).

Ancak rastgele denilen başka diziler de var . Onlara göre, deterministik olanların aksine, genel olarak konuşursak, öncekileri bilerek dizinin bir sonraki üyesini belirlemek imkansızdır. Bir ikili rasgele dizi elde etmenin en basit yolunu açıklayalım.

"Doğru" yazı tura atalım. Nasıl düştüğüne bağlı olarak, dizinin bir sonraki üyesini 0 (tura) veya 1'e (yazı) eşitliyoruz. Deneyimin gösterdiği gibi, bir dahaki sefere madeni paranın nasıl düşeceğini tahmin etmek genellikle imkansızdır. Ancak, yeterince uzun bir yazı tura atarsanız , yaklaşık yarısında tura gelir ve yaklaşık yarısında yazı gelir. Bir madeni paranın , her birinin tura (0) veya yazı (1) atma olasılığının 1/2'si ile aynı olasılıkla rastgele düştüğü söylenir .

sırasıyla р ve q (р / q) ile düştüğü durumlar (״a bozuk para") vardır . р 4־ q = 1 olduğuna dikkat edin ! 'יל'־         O fırlatılarak elde edilen rastgele bir ikili dizide

״ madeni para eğrisi , p, sıfırın oluşma sıklığı olarak kabul edilebilir, cehennem - birinin görünme sıklığı.

Limitleri inceleyenler için şunu açıklığa kavuşturalım: sıfırların sayısını S 0 (k) ile ve dizimizin k ilk üyesi arasındaki birlerin sayısını S! (k) ile gösterirsek, o zaman Ііт         ііт =д .

Güvenlik Sorusu. p = q = 1/2 ve karşılık gelen dizinin ilk yüz terimi 1'e eşit olacak şekilde rastgele bir yazı tura atalım (kuyruklar art arda 100 kez atılır). Bu dizinin 101. üyesinin tekrar 1 olma olasılığı nedir?

Bu sorunun doğru cevabı: 1/2. q = 1/2 olduğundan ve dizimizin rasgeleliği, önceki üyeleri ne olursa olsun , ardışık her üyesinin q olasılıkla 1'e eşit olduğu anlamına gelir.

Genellikle, pratikte ele alınması gereken diziler, genel olarak konuşursak, kesinlikle rastgele (rastgele olmayan) değildir. Rastgele ve rastgele olmayan ikili dizilerin incelenmesi kriptografi için önemlidir. Örneğin, şifreli mesajlardaki örüntüleri belirlemek, bir şifreyi kırmada çok faydalıdır (bkz. Etüt 2.7). Alıştırma 2.5'te ayrıca tamamen güvenli bir şifre oluşturmak için tamamen rasgele bir anahtar üretebilmeniz gerektiğini öğreneceksiniz.

Rastgele ve rasgele olmayan diziler arasında ayrım yapmanın yanı sıra rasgele olmayan dizilerdeki düzenlilikleri belirleme sorunları, matematiğin çeşitli alanlarında birçok çalışmanın konusudur. Örneğin, matematiksel istatistiğin ana dallarından biri , özellikle gözlemlenen dizilerin doğası ve özellikleri hakkındaki hipotezleri ayırt etmek için yöntemlerin geliştirildiği istatistiksel hipotezlerin test edilmesidir . Başka bir örnek, modern teorik kriptografide aktif olarak incelenen varsayımsal bir nesnedir - sözde rastgele bir üreteç. Bu nesneyi incelerken, algoritmaların ve hesaplamaların karmaşıklık teorisinin çok sayıda sonucu kullanılır. Gayri resmi olarak konuşursak, sözde rasgele bir üreteç, rasgeleden ayırt edilmesi zor ve kalıpları çıkarmanın zor olduğu bu tür diziler üretir. Gerekli kavramların katı tanımları kitabımızın kapsamı dışındadır.

Ruh olarak yakın, ancak daha basit ve özellikle programcılar için iyi bilinen, rastgele sayı üreteci gibi bir nesnedir . Bu , sözde rasgele diziler üreten bir cihaz veya programdır . Bazı durumlarda sözde rastgele dizilerin rastgele olanlardan ayırt edilemeyeceği kabul edilir ve farklı durumlar ve görevler için uygun sensörler seçilir. Üretilen dizilerin rasgeleliği konusunda ne kadar katı gereksinimler uygulanırsa, karşılık gelen rasgele sayı üreteci o kadar karmaşık olur. Birçok şifre makinesi, üretilen dizilerin kalitesi için çok yüksek gereksinimleri karşılayan rasgele sayı üreteçleri olarak düşünülebilir.

doğrusal eşleme yöntemi olarak adlandırılan en basit sensörlerden birini açıklayalım . Belirli bir ilk ao sayısı için, aşağıdaki tekrarlayan yasaya göre sonsuz bir doğal sayılar dizisi {al:} üretir :

ak = d + al-1 ־ l (modJV).

Burada sensör parametreleri d,l,N bazı tamsayılardır. Genel olarak a = b (modiV) yazmak , a - b'nin jV sayısı ile bölünebilir olduğu anlamına gelir; bu durumda d + al-1 ־ I'in N'ye bölümünden kalan al olarak alınır.

{al} dizisinin tüm üyeleri, N - 1'i geçmeyen negatif olmayan tam sayılar olduğundan, aralarında iki özdeş sayı vardır, örneğin a< ve a^«. O halde, kolayca görülebileceği gibi, k > i için al = al + t, yani dizi, periyot uzunluğu t olan periyodiktir . Tabii ki, periyodiklik, rastgelelik hakkındaki fikirlerimizle tam olarak uyuşmuyor, ancak bu tür sensör parametrelerini, periyodun yeterince büyük olması ve dizinin birçok rastgelelik belirtisine sahip olması için seçmenin mümkün olduğu ortaya çıktı.

Hemen hemen her açıdan "iyi bir rastgele dizi" olmadığına dikkat edilmelidir: bir rastgele dizinin ne kadar "iyi" olduğu amacına bağlıdır.

Подумайте сами:

1. Aşağıdaki iddiayı kanıtlayın: k eğri bir madeni para fırlattığında I kere tura gelme olasılığı eşittir

І ben Іс - 1

S         •

2. d, І ve N gibi sayıları düşünün , öyle ki N çok küçük olmasın ve lineer uyumlu yöntemle elde edilen dizinin periyodunun uzunluğu N'ye yakın olsun.

3. Kendi rasgele sayı üretecinizi bulun.

3. Algoritma nedir ve karmaşıklığı

bir algoritma, belirli bir sonuca götüren, açıkça tanımlanmış bir eylemler dizisi olarak anlaşılabilir .

algoritma kavramı çok uzun süre sezgisel bir kavram olarak kaldı. Sadece 1930'larda, önde gelen matematikçiler D. Hilbert, A. Church, S. Kleene, E. Post ve A. Turing'in çalışmalarında, yinelemeli fonksiyon kavramına ve algoritmik bir işlemin açıklamasına dayanmaktadır . Böylece, daha sonra bilgisayar teknolojisinin gelişimi için teorik temel haline gelen matematikte yeni bir yön olan algoritma teorisi oluşturuldu. Şu anda, algoritma teorisi hızla gelişiyor, kavramlarının çoğu netleştiriliyor ve geliştiriliyor (kanıtlanabilirlik ve çözülebilirlik, verimlilik , vb.).

Hayatta sürekli olarak matematiksel olmayan algoritmalarla karşılaşıyoruz (örneğin, pancar çorbası yapmak için bir tarif veya okulda sınav yapmak için talimatlar bu şekilde kabul edilebilir). Bir matematiksel algoritmanın en basit örneği, iki sayının en büyük ortak bölenini bulmak için kullanılabilen iyi bilinen Öklid algoritmasıdır. Ve programlama gibi bir aktivite, algoritmalarla sürekli bir çalışmadır.

просы, на которые можно ответить ״да” или ״нет”. Одним из!

Matematikte çok önemli bir kavram (sezgisel olarak açık, ancak biçimlendirilmesi çok kolay değil) bir algoritmanın karmaşıklığıdır. Basit bir örnek verelim. Doğal bir sayı olduğu bilinen ve 1000'i geçmeyen tasarlanan sayıyı tahmin etmek istensin.

tahmin yolları (algoritmalar) aşağıdaki gibi olabilir: 1'den 1000'e kadar tüm sayılar, istenen sayı bulunana kadar sırayla sıralanır. En kötü durumda, bu 999 soru gerektirecektir. Ancak 10 soruda sayının tahmin edilmesini sağlayan başka bir algoritma önerilebilir: önce tahmin edilen sayının 500'den büyük olup olmadığı, öyleyse 750'den büyük olup olmadığı vb. Her adımda, olası adayların sayısı yarı yarıya azalır. Burada; Algoritmanın karmaşıklığı, soru sayısı olarak kabul edilebilir. Sonra] ilk algoritma, ikincisinden 100 kat daha karmaşıktır”.

Algoritma bir dizi hesaplama gerçekleştiriyorsa, algoritmanın karmaşıklığı gerçekleştirilen işlem sayısı olarak kabul edilebilir. Ayrıca, bir algoritmada yalnızca çarpma ve toplama meydana geliyorsa , bu işlem çok daha fazla zaman gerektirdiğinden, karmaşıklık genellikle yalnızca çarpma sayısı olarak anlaşılır. Uygulamada, algoritma vb. Tarafından gerçekleştirilen işlemlerin maliyetini de hesaba katmak gerekir.

toplu problemleri çözmek için algoritmalar dikkate alınır . Toplu bir görevi, sonsuz sayıda bireysel görev olarak düşünmek uygundur. Bireysel bir problem, belirli bir boyutla karakterize edilir , yani. Bu sorunu açıklamak için gereken girdi verisi miktarı. Bireysel bir problemin boyutu bir doğal sayı n ise, o zaman kütle problemini çözmek için algoritmanın karmaşıklığı n'nin bir fonksiyonu olur , iki örnek verelim.

uzunluğundaki tüm ikili anahtarların basit bir şekilde sıralanması için bir algoritma düşünelim . Bu tür 2 anahtar olduğu açıktır ve bu nedenle bu algoritmada 1'in 2 n adımı vardır, yani karmaşıklığı 2 n'dir . ן Bu en basit örnektir. üstel bir algoritmanın (karmaşıklığı, n ile üs tarafından ifade edilir .) Çoğu üstel algoritma, kapsamlı aramanın yalnızca varyantlarıdır.

Şimdi iki n basamaklı sayıyı bir sütunla çarpmak için algoritmayı düşünün. Tek basamaklı sayıların n 2 çarpımından oluşur , yani. bu tür çarpmaların sayısıyla ölçülen karmaşıklığı n2'ye eşittir . Bu, bir polinom algoritmasının en basit örneğidir (karmaşıklığı, bir polinom tarafından n cinsinden ifade edilir ).

Aynı matematik problemini çözmek için farklı algoritmaların önerilebileceği oldukça açıktır. Bu nedenle, bir sorunun karmaşıklığı, onu çözmek için algoritmaların minimum karmaşıklığı olarak anlaşılır. Şimdi Etude 1.6'ya dönersek, yeni terimlerle bir şifrenin gücünün onu kırma görevinin zorluğu olduğunu söyleyebiliriz.

Matematikte, henüz polinom algoritmasının oluşturulmadığı birçok problem vardır. Bunlar, örneğin gezgin satıcı problemini içerir: bir yol ağıyla birbirine bağlı n şehir vardır ve her yol için seyahatin maliyeti belirtilir; tüm şehirlerden geçen bir rota belirtmek gerekir, böylece seyahat maliyeti

bu rota çok azdı.

Kendin için düşün:

1. Sütun çarpımından daha az tek basamaklı çarpma gerektiren iki n basamaklı sayıyı çarpmak için bir algoritma önerebilir misiniz ?

4. ve permütasyon şifreleri

Claude Shannon, "Gizli İletişimin Matematiksel Teorisi" adlı çalışmasında, şifrelerin geliştirilmesinde kendisinden önce biriken deneyimi özetledi. Karmaşık şifrelerde bile ikame şifrelerin, permütasyon şifrelerin veya bunların kombinasyonlarının tipik bileşenler olarak ayırt edilebileceği ortaya çıktı. Bu şifreler temel gibi kabul edilebilir.

Yerine koyma şifresi en basit, en popüler şifredir. Tipik örnekler, A. Conan Doyle tarafından yazılan "Büyük Peter ve dans eden adamların" basamaklı alfabesi olan Sezar şifresidir. Adından da anlaşılacağı gibi, ikame şifresi, harflerin veya diğer harflerin ikamesinin dönüşümünü gerçekleştirir.

bu metnin şifreli metnin benzer "bölümlerine" bölünmesi. Alfabeleri artırarak, yani. "parçaları" harf olarak bildirerek, herhangi bir ikame şifresi, harflerin yerine geçen bir şifreye indirgenebilir. Artık ikame şifresinin matematiksel bir tanımını yapmak kolaydır.

X ve Y , sırasıyla aynı sayıda

karakterden oluşan iki düz metin ve şifreli metin alfabesi olsun . Ayrıca q : X -> Y, X'in Y'ye bire bir eşlenmesi olsun. Bu , X alfabesindeki her x harfinin, Y alfabesinin benzersiz bir şekilde tanımlanmış bir y harfiyle ilişkili olduğu anlamına gelir ; bu, sembolle gösteririz. g(x) ve farklı harfler farklı harflerle ilişkilendirilir. Daha sonra ikame şifresi şu şekilde hareket eder: X]X2-..x n düz metni , q(x\)d(x2)...d(x n ) şifreli metnine dönüştürülür . Yerine koyma şifresini kırma sorusuna Etude 2.8'de geri döneceğiz.

ח

и

Permütasyon şifresi, adından da anlaşılacağı gibi, düz metindeki harflerin permütasyon dönüşümünü gerçekleştirir. Bir permütasyon şifresinin tipik ve en eski örneği ״Scital şifresidir. Genellikle düz metin eşit uzunlukta parçalara bölünür ve her bölüm bağımsız olarak şifrelenir (yani harfler yeniden düzenlenir). Örneğin, segmentlerin uzunluğu n'ye eşit olsun ve <7, {1,2,...,n) kümesinin kendi içine bire bir eşlenmesi olsun. Daha sonra permütasyon şifresi şu şekilde çalışır: x\...x n düz metninin bir bölümü, x a ^) ... x a ^ n y şifreli metnin bir bölümüne dönüştürülür.

q ve < 7 eşlemelerinin uygun şekilde ezberlenmesi sorunudur . Bazı eşlemeleri ezberlemenin kolay olduğu açıktır: örneğin, "küçük" boyutlardaki eşlemeler, bazı nesneler tarafından gerçekleştirilen eşlemeler (scital ״Scytal" şifresinde scital, vb.). Ekran "büyük" boyuttaysa, ezberleme işlemi çok daha karmaşık hale gelir. Örneğin, bigram şifreleri yaygın olarak bilinmektedir. Bigramlar (harf çiftleri) bunlara dönüştürüldü. Bigram sayısı 1000'i geçtiği için pratikte bigram şifreleri özel kitaplar gibi görünür.

g ve a eşlemelerinin ezberlenmesini kolaylaştırmak için çeşitli ustaca yöntemler icat edildi. Doğru, bunun "cezası" kullanılan eşlemelerin basitleştirilmesi ve dolayısıyla şifrelerin gücünün azalmasıydı.

a eşlemesini hatırlamanın popüler bir yolu, yani. permütasyon şifresi aşağıdaki gibidir. Örneğin, n = 20 olsun. 4x5 boyutunda dikdörtgen bir tablo alıyoruz, içine "satırlar halinde" düz metni giriyoruz ve "sütunlar halinde" şifreli metni okuyoruz. Girmenin ve okumanın daha zor yolları da mümkündür.

Kendin için düşün:

1. Sezar şifresi için q haritasını yazın .

2. Açıklanan permütasyon şifresi için 4x5'lik bir dikdörtgen olan <m eşlemesini yazın.

5. Kesinlikle güçlü bir şifre mümkün mü?

Evet ve bu tür tek şifre! düz metnin tam kutu ile "birleştiği" bir tür sözde tek kullanımlık bant ־? aynı uzunlukta anahtar.         BEN

sonuç K. Shannon'ın yardımıyla kanıtlandı.

schyu, kendisi tarafından şifrelerin incelenmesi için teorik bilgi yöntemini geliştirdi. Burada bunun üzerinde ayrıntılı olarak durmayacağız, ancak ilgili okuyucunun K. Shannon'ın çalışmasını incelemesini tavsiye ediyoruz, bu eser bibliyografya-1'de listelenmiştir.

Tamamen güvenli bir şifrenin yapısının özelliklerini ve pratik kullanım olanaklarını tartışalım. Kesinlikle güvenli bir şifrenin uygulanmasının tipik, tipik ve en basit örneği, n-bitlik düz metnin bit düzeyinde eklenmesini gerçekleştiren Vernam şifresidir ve

n bitlik anahtar:

Ui = xt®ki ve — 1,..., n.

Burada W1,...,a:n açık metindir, fc!,...,fc n anahtardır, y\1-1yn şifreli metindir; semboller aşağıdaki kurallara göre eklenir: 0f0 = 0, 0f1 = 1f0 = 1, 1f1=0. Okuyucunun Burnham şifresinin neden kesinlikle güvenli olduğunu düşünmesini tavsiye ediyoruz. ( İpucu. Yalnızca j/1,...,j/ n biliniyorsa ve k\,...,kn bilinmiyorsa ve tamamen rasgeleyse (daha kesinlikle, eşit derecede olası), o zaman x!,. .., x n keyfi olabilir, bu durumda şifreleme denklemlerinin açık metin hakkında herhangi bir bilgi vermediği de söylenir.)

Şimdi, tek kullanımlık bir bant için aşağıdaki gereksinimlerin her birinin mutlak dayanıklılık için gerekli olduğunu vurguluyoruz:

1. anahtarın tam rastgeleliği (denklenebilirliği) (bu, özellikle, anahtarın herhangi bir deterministik cihaz kullanılarak üretilemeyeceği anlamına gelir);

2. anahtar uzunluğu ve düz metin uzunluğunun eşitliği;

3. anahtarın tek kullanımı.

Bu koşullardan en az biri ihlal edilirse, şifre kesinlikle güvenli olmaktan çıkar ve onu kırmak için temel olasılıklar ortaya çıkar (uygulanması zor olsa da).

Ancak, kesinlikle güvenli bir şifreyi çok pahalı ve kullanışsız kılan tam da bu koşullar olduğu ortaya çıktı. Böyle bir şifreyi kullanmadan önce, tüm abonelere yeterli miktarda rasgele anahtar sağlamalı ve bunların yeniden kullanılma olasılığını dışlamalıyız. Ve bunu yapmak alışılmadık derecede zor ve pahalıdır. D. Kahn'ın belirttiği gibi: “Anahtar oluşturma, kaydetme, dağıtma ve iptal etme sorunu, askeri iletişim kanalları aracılığıyla mesaj iletme konusunda deneyimi olmayan biri için çok karmaşık görünmeyebilir, ancak savaş zamanında iletilen mesajların hacmi, profesyonel işaretçilerin bile kafasını karıştırır. Günde yüz binlerce kelime şifrelenebilir. Milyonlarca anahtar işaretin yaratılması, büyük finansal maliyetler gerektirecek ve büyük bir zaman yatırımıyla ilişkilendirilecektir. Her metnin kendine ait, biricik anahtarı olması gerektiğinden, ideal bir sistemin uygulanması, en az iletilen tüm askeri bilgi hacmine eşit sayıda karakterin iletilmesini gerektirir.”         ן

Bu nedenlerden dolayı, kesinlikle güçlü şifreler yalnızca az miktarda iletilen bilgi içeren iletişim ağlarında kullanılır, genellikle bunlar özellikle önemli durum bilgilerinin iletilmesi için ağlardır.         '

6. Dayanıklılık teorik ve pratik і

BEN

Artık, meşru kullanıcıların bilgilerini korumak için çoğu zaman kesinlikle güçlü olmayan şifreler kullanmaya zorlandıklarını zaten anlıyoruz. Bu tür şifreler, en azından teoride kırılabilir. Soru! sadece rakibin uygun algoritmaları geliştirmek ve uygulamak için yeterli güce, araçlara ve zamana sahip olup olmadığı] ile ilgilidir.Bu fikir genellikle şu şekilde ifade edilir: sınırsız kaynaklara sahip bir düşman, kesinlikle güvenli olmayan herhangi bir şifreyi kırabilir.

Meşru bir kullanıcı bu durumda kendisi için bir şifre seçerek nasıl hareket etmelidir? Elbette en iyi şey, hiçbir rakibin seçilen şifreyi örneğin 10 yıl içinde kıramayacağını kanıtlamak ve böylece teorik bir güvenlik tahmini elde etmektir. Ne yazık ki, matematiksel teori henüz gerekli teoremleri vermiyor - problemlerin karmaşıklığı için çözülmemiş alt sınırlar problemine atıfta bulunuyorlar.

Bu nedenle, kullanıcıya kalan tek yol, pratik direnç değerleri elde etmektir. Bu yol aşağıdaki adımlardan oluşur:

• bilgileri hangi düşmandan koruyacağımızı anlamak ve açıkça ifade etmek; düşmanın şifre sistemi hakkında tam olarak ne bildiğini veya öğrenebileceğini, onu açmak için hangi güçleri ve araçları kullanabileceğini anlamak gerekir;

• zihinsel olarak kendinizi düşmanın yerine koyun ve şifreye onun konumlarından saldırmaya çalışın, yani. şifreyi kırmak için çeşitli algoritmalar geliştirmek; aynı zamanda, düşmanın kuvvetlerinin, araçlarının ve yeteneklerinin mümkün olan en üst düzeyde modellenmesini sağlamak gerekir;

• Şifrenin güvenliğinin pratik olarak değerlendirilmesi için geliştirilen algoritmaların en iyileri kullanılmalıdır.

Burada örnek olarak bir şifreyi kırmanın en basit iki yönteminden bahsetmekte fayda var: anahtarı rastgele tahmin etmek (küçük bir olasılıkla çalışır, ancak küçük bir karmaşıklığa sahiptir) ve doğru olanı bulana kadar tüm anahtarları arka arkaya numaralandırmak (o her zaman çalışır, ancak çok yüksek bir karmaşıklığa sahiptir).

7. Нет, для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.

8. Anahtara saldırmak her zaman gerekli midir?

Bu fikir, en uygun şekilde, kırma yöntemlerinin uzun süredir geliştirildiği bir ikame şifresi örneğiyle gösterilmektedir.

q ikamesi ile tanımlandığını hatırlayın (bkz. Etüt 2.4). Böyle bir şifre, düz metni aşağıdaki kurala göre şifreli metne dönüştürür: her x harfinin yerine d(x) harfi gelir. Şifre kırma, aşağıdaki iki düzenliliğe dayanmaktadır:

1. herhangi bir doğal dilin anlamlı metinlerinde, farklı frekanslarda farklı harfler oluşur ve ikame eylemi q ״ bu düzenliliği şifreli metne aktarır;

2. , mesajdaki bazı harfler bilinmese bile mesajın anlamını yüksek olasılıkla tahmin etmeyi mümkün kılan sözde fazlalığa sahiptir.

Örnek olarak Rus alfabesindeki harflerin göreli sıklıklarını verelim.

N	Mektup	İlişki, sıklık	N	Mektup	İlişki, sıklık	N	Mektup	İlişki, sıklık
1	A	0,062	12	ben	0,035	23	C	0,004
2	B	0,014	13	M	0,026	24	H	0,012
3	V	0,038	14	N	0,053	25	w	0,006
4	G	0,013	15	Ö	0,090	26	SCH	0,003
5	D	0,025	16	P	0,023	27	S	0,016
6	o	0,072	17	R	0,040	28	b, b	0,014
7	Ve	0,007	18	İle	0,045	29	uh	0,003
8	3	0,016	19	T	0,053	otuz	Yu	0,006
9	Ve	0,062	20	-de	0,021	31	BEN	0,018
10	inci	0,010	21	F	0,002	32	-	0,175
onbir	İle	0,028	22	X	0,009

Bu tür tablolar, basit ikame şifresini aşağıdaki şekilde kırmak için kullanılır. Şifreli metindeki harf frekanslarının bir tablosunu derleyin. Değiştirme sırasında en sık kullanılan harflerin en sık kullanılanlara aktarıldığını varsayıyoruz. Çeşitli seçenekleri sırayla sıralayarak, ya Rus dilinin yasalarıyla çelişmeye ya da mesajın okunabilir parçalarını almaya çalışıyoruz. Ayrıca, mümkünse okunabilir parçaları ya anlama göre ya da Rus dilinin yasalarına göre genişletiyoruz.

Tek bir örneğin ayrıntılı analizi bile çok yer kaplayabilir. Meraklı okuyucuların, bazı ikame şifreleri için bunu kendi başlarına yapmalarını öneririz. Üç örneğin ayrıntılı açıklamasını da okuyabilirsiniz:

• E. Po'nun "Altın Böcek" öyküsünde;

• A. Conan Doyle'un "Dans Eden Adamlar" öyküsünde;

• M.N. Arshinova ve L.E. Sadovsky "Kodlar ve Matematik".

9. Kriptografi, kombinatoryal algoritmalar

ve bilgi işlem

şifrelerin pratik güvenliğine ilişkin tahminler bilimin hangi alanlarındaki ilerlemeye bağlıdır? Önceki sunumdan dikkatli okuyucunun kendisi bu soruyu cevaplayacaktır: her şeyden önce, bu, algoritmaların ve hesaplamaların karmaşıklığının yanı sıra bilgisayar teknolojisinde algoritmaların uygulanmasının karmaşıklığının teorisidir. Son yıllarda, bu alanlar hızla gelişti ve özellikle şifrelerin pratik güvenliğine ilişkin tahminleri etkileyen ilginç sonuçlar elde edildi . Pek çok yararlı sonuç, algoritmaları hızlandırmak ve bu nedenle programcıların toplu pratiğine hızla girmek için “hileler” niteliğindedir. Bu, özellikle hızlı veri arama ve sıralama gibi iyi bilinen tipik problemlerden doğan kombinatoryal algoritmalar alanı için geçerlidir . D. Knuth'un üç ciltlik popüler kitabı The Art of Computer Programming'de bu konuların sistematik ve ayrıntılı bir sunumu yer almaktadır.

Kombinatoryal algoritmalar alanının, Rubik Küpü gibi iyi bilinen bulmaca oyunlarına yönelik algoritmaları da içerdiğini not ediyoruz.

Kural olarak şifreleri kırmak için algoritmalar kullanılır

anahtar aramayı (veya şifrenin diğer öğelerini) ve verilerin aranmasını, karşılaştırılmasını ve reddedilmesini azaltmak için çok sayıda farklı teknik kullanın. Bu nedenle, şifre güvenliği tahminleri, kombinatoryal algoritmalar teorisinden çeşitli tahminler içerir.

Kendin için düşün:

1. Sayılar arasındaki en küçük öğenin {z! xn ], n - 1'den az karşılaştırmada bulunamaz .

2. x p ] sayılarının düzenlenmesi için bir algoritma önerin

karşılaştırılabilirden daha azını kullanarak artan düzende        

kavramlar (yani, her sayıyı sırayla karşılaştırmak için önemsiz algoritmadan daha verimli).

3. Rafta n cilt derlenmiş eser var. İki cildi yanlış sırada gören sahibi, onları değiştirir. Bu tür permütasyonlardan en geç n 2 sonra hacimlerin sırayla düzenleneceğini kanıtlayın.

4. Mareşal bahçesinde birkaç tren var. Birkaç vagondan oluşan bir trenin iki trene ayrılmasına veya sadece bir vagonu varsa bir trenin kaldırılmasına izin verilir. Bu eylemleri keyfi bir sırayla gerçekleştirerek er ya da geç tüm arabaları kaldıracağımızı kanıtlayın.

5. n doğal sayıları tasarlandı ve bilgisayara girildi . Bir adımda bilgisayara herhangi bir n başka doğal sayının girmesine izin verilir b!,...,b p . Bilgisayar daha sonra a!b! 4-... 4־ a p b p ve sonucu ekranda görüntüler. Bu sonucun amaçlanan sayılar hakkında bazı bilgiler içerdiği açıktır. Verilen sayıları tahmin etmek için gereken minimum adım sayısı nedir?

Bölüm 3 YENİ
YÖNLENDİRMELER

1983 yılında M.N. Arshinova ve L.E. Sadovsky (״Kvant kütüphanesi) şöyle yazdı: "Gizli yazmanın pek çok yöntemi var ve büyük olasılıkla burası, esasen yeni bir şey icat etmeye artık gerek olmayan alandır." Ancak bu, kriptografiyle ilgili bir başka büyük yanılgıydı. 1976'da, genç Amerikalı matematikçiler W. Diffie ve M. E. Hellman'ın, yalnızca kriptografiyi önemli ölçüde değiştirmekle kalmayan, aynı zamanda matematikte yeni eğilimlerin ortaya çıkmasına ve hızla gelişmesine yol açan “Kriptografide Yeni Trendler” adlı çalışması yayınlandı. Bu bölümde, yeni kriptografinin temel kavramlarını açıklayacağız.”

1. tek yönlü işlev nedir

Tek taraflı bir işlev , iki özelliği olan F-.X- >Y olarak adlandırılır :

a ) F(x)         değerlerini hesaplamak için bir polinom algoritması vardır ;

b )         F fonksiyonunu tersine çevirmek için polinom algoritması yoktur , yani F(x)=y denkleminin x'e göre çözümü .

Tek yönlü fonksiyonun, hesaplanmasının ve tersine çevrilmesinin karmaşıklığı üzerindeki kısıtlamalar nedeniyle okuldan bilinen fonksiyonlardan önemli ölçüde farklı olduğuna dikkat edin. Matematikteki bu yeni kavram, 1975 yılında Diffie ve Hellman tarafından tanıtıldı. Ancak son 19 yılda, tek yönlü bir fonksiyonun tek bir örneğini oluşturmak mümkün olmamıştır. Bununla birlikte, şimdiye kadar varsayımsal olan bu matematiksel nesnenin özelliklerinin aktif bir şekilde incelenmesi, daha fazla çalışılan diğer nesnelerle bağlantısını kurmayı mümkün kıldı. Aynı zamanda, tek yönlü bir fonksiyonun varlığı probleminin, iyi bilinen ilgisiz problemlerden birine eşdeğer olduğunu kanıtlamak mümkün oldu: "P ve NP karmaşıklık sınıfları çakışıyor mu?" P ve NP sınıflarının kesin bir tanımı bu kitabın kapsamının çok ötesindedir. Hazırlıklı okuyucular için, M. Gary ve D. Johnson'ın “Bilgisayarlar ve zorlu problemler” adlı temel monografisini öneriyoruz.

P sınıfı polinom karmaşıklığına sahip problemlerden oluşur. Daha kesin olarak, P sınıfı, deterministik bir Turing makinesinde polinom zamanında tanınabilen diller sınıfıdır . Böyle bir Turing makinesi varsayımsal bir tahmin etme yeteneği ile desteklenirse, daha güçlü bir model elde edilir - deterministik olmayan, mayınlı bir Turing makinesi. NP sınıfı, deterministik olmayan bir Turing makinesinde polinom zamanında tanınabilen bir dil sınıfıdır. P ve NP sınıflarının çakışma sorunu, iki hesaplama modelinin yetenekleri arasındaki korelasyon sorunudur: deterministik ve deterministik olmayan bir Turing makinesi.

, bir sır ile tek yönlü işlev kavramıdır . Bazen tuzak işlevi, sürgülü kapı işlevi (İngilizce adı: one-wajttrap-door işlevi) terimleri de kullanılır .

Gizli bir K'ye sahip tek yönlü bir işlev, K parametresine bağlı olarak ve üç özelliği olan bir Bk:X->Y işlevidir:

a ) herhangi bir         K için , Fk(x) değerlerini hesaplamak için bir polinom algoritması vardır ;

b )         bilinmeyen K için, polinom ters çevirme algoritması F K yoktur ;

c )         bilinen K için , bir polinom ters çevirme algoritması Fk vardır .

Sırrı olan tek yönlü işlevlerin varlığı hakkında, daha önce tek yönlü işlevler hakkında söylenenlerin aynısı söylenebilir. Pratik amaçlar için, kripto-

трудной математической задаче.

приводятся в этюдах 3.5, 3.6, 3.7. Стоит отметить, что

Sürahi, tek yönlü olabilecek çeşitli işlevlerle inşa edilmiştir. Bu, onlar için b) özelliğinin henüz kesin olarak kanıtlanmadığı anlamına gelir, ancak ters çevirme probleminin uzun süredir çalışılan bir probleme eşdeğer olduğu bilinmektedir.Tek yönlü fonksiyon başlığı için bazı adaylar için bu tür fonksiyonların örnekleri bulunmuştur . polinom ters çözüm algoritmaları için ve böylece bu fonksiyonların tek yönlü olmadığını kanıtladı.

2. Kriptografi için tek yönlü bir işlev sağlayan nedir?
   

Kriptografide tek yönlü bir işlevin kullanılması şunları sağlar:

1. sadece açık iletişim kanallarını kullanarak şifreli mesaj alışverişini organize edin, örn. ön anahtar değişimi için gizli iletişim kanallarını reddetme;

2. şifreyi açma problemine zor bir matematik problemini dahil etmek ve böylece şifre güvenliğinin geçerliliğini artırmak;

3. (dijital imza vb.) dışındaki yeni kriptografik sorunları çözebilir .

Spesifik örnekleri ele almadan önce, Diffie ve Hellman fikrini genel bir şekilde gözden geçirelim.

ile tek yönlü Fk işlevini seçmelidir. İlgili tüm taraflara şifreleme algoritması olarak Fk işlevinin açıklamasını iletir (örneğin yayınlar) . Ama aynı zamanda K sırrının anlamını kimseye söylemez ve bunu bir sır olarak saklar. Şimdi B kullanıcısı A korumalı bilgisini x € X göndermek isterse , o zaman Fk(%)' yi hesaplar ve bunu açık bir kanal üzerinden A'ya gönderir. A, gizli K'si için Fk'yi nasıl tersine çevireceğini bildiğinden, x'i alınan Fk'den hesaplar . (x). Başka hiç kimse K'yi bilmez ve bu nedenle, bir sır içeren tek yönlü bir fonksiyonun b) özelliği nedeniyle, korunan bilgi x'i bilinen bir şifreli mesajdan Fk(x) polinom zamanında hesaplayamayacaktır .

Böylece, korunan bilgilerin iletilmesi için bir sistem oluşturulmuş ve iki yeni özellik yerine getirilmiştir:

1. mesajların iletimi, gizli bir iletişim kanalı üzerinden bir ön anahtar değişimi gerektirmez;

2. şifrenin gücü, tek yönlü bir işlevi bir sır ile tersine çevirmek gibi zor bir matematik problemini çözmenin karmaşıklığına bağlıdır.

Açıklanan sistem, açık anahtar şifreleme sistemi olarak adlandırılır, çünkü şifreleme algoritması Fk genel veya açıktır. Son zamanlarda, bu tür şifreleme sistemlerine asimetrik de denir , çünkü algoritmalarında asimetri vardır: şifreleme ve şifre çözme algoritmaları farklıdır. Bu tür sistemlerin aksine, geleneksel şifrelere simetrik denir: bunlarda şifreleme ve şifre çözme anahtarı aynıdır ve bu nedenle gizli tutulmalıdır. Asimetrik sistemler için şifreleme algoritması iyi bilinir, ancak şifre çözme algoritmasını polinom zamanında ondan kurtarmak imkansızdır.

, polinom zamanında taklit edilemeyen mesajları dijital olarak imzalamak için kullanılması önerildi .

A kullanıcısının x mesajını imzalamasına izin verin . K sırrını bilen , y'yi Fk (y) = x olacak şekilde bulur ve y'yi B kullanıcısına dijital imzası olarak gönderir. B kullanıcısı, A'nın x mesajını imzaladığının kanıtı olarak y'yi tutar . Bu kanıt çürütülemez, çünkü başka hiç kimse, sır içeren tek yönlü bir fonksiyonun b) özelliği nedeniyle, bilinen x = F K (y) mesajına göre polinom zamanında y dijital imzasını oluşturamaz .

Daha sonra, benzer bir akıl yürütme temelinde, bir dizi sözde kriptografik protokol önerildi. Bu protokoller, uzak kullanıcılar arasındaki birçok yeni etkileşim sorununu çeşitli tehditler altında teknik iletişim kanalları aracılığıyla çözmeyi mümkün kıldı (daha fazla ayrıntı için, etüt 3.8'e bakın).

3. Modern kriptografide sayılar ve alanlar

Matematik yaptığınızda, sürekli kullanırsınız

gerçek sayıların bariz özellikleri, farkına bile varmadan , örneğin: sayıların toplamı terimlerin sırasına bağlı değildir.

F gerçek sayıları kümesinde toplama ve çarpma işlemlerinin ana özelliklerini gösterelim.

1. . Her üç element için a, b, c Є F a + (b 4- c) =

= (bir 4־4 (6 ־ sn.

2. . F kümesinin bir 0 elemanı vardır öyle ki her biri için

o € jF g 4״4 0 = 0 ״ o = ct.

3. . Her bir € F elemanı için böyle bir eleman vardır.

х Є F, bu а4־х = х4־а = 0 (böyle bir eleman verilenin tersi olarak adlandırılır).

4. . Her iki eleman için a, b Є F a + b = b + a.

5. . Her üç öğe için a, b, c € F a • (b • c) = (a • b) • c.

6. . F kümesinin 1 (0'a eşit olmayan) bir elemanı vardır, öyle ki

her a€fe*l = l־e = a için.

7. . Her eleman için a Є F, a / 0 gibi bir eleman vardır.

a• x = x•a = 1 olacak şekilde x Є F yazın (böyle bir elemana verilenin tersi denir).

8. . Her iki eleman için a,b EF a • b = b • a.

9. . Her üç element için a, b, c € F a*(b+c) = a׳b+a-c.

Özellikler 1) - 4) toplama işleminin özellikleridir, özellikler 5) - 8) çarpma işleminin özellikleridir ve özellik 9) bu iki işlem arasında bir bağlantı kurar.

Matematikte, üzerinde aynı özelliklere sahip işlem çiftleri olan başka birçok küme olduğu ortaya çıktı. Bu tür kümeler için özel bir ad bile vardır: alan.

Bir alan, her biri F'den herhangi bir öğe çiftini F'den benzersiz bir şekilde belirlenmiş üçüncü bir öğeyle ilişkilendiren iki eşlemeye (״işlemler") sahip bir F kümesidir ve bu eşlemeler (geleneksel olarak ״+" ve ״•" ile gösterilir) yukarıda verilen dokuz aksiyom (özellikler).

kriptografi için özellikle önemlidir . Bu alanlardan birini oluşturalım.

P bir asal sayı olsun . Toplama ve çarpma işlemleri ile {0,1,2,...,p - 1} sayı kümesini ele alalım p modulo (iki sayının toplamı, normal toplamın p ile bölümünden kalandır , çarpım normal çarpımın p ile bölümünden kalan ). 1) - 4) özelliklerinin karşılanıp karşılanmadığını kontrol etmek kolaydır: 1) ve 4) özellikleri için bu açıktır, özellik 2)'deki 0 öğesi normal sıfırdır, özellik 3'teki a öğesinin karşısındadır - bu eleman p - a. Özellikler 5), 6), 8) ve 9) aynı kolaylıkla doğrulanabilir. Özellik 7) kanıtlanmalıdır. Sizi kendiniz kanıtlamaya davet ediyoruz, sadece fikri açıklayacağız: her biri için £ {0,1, ..., p - 1}, öyle ki x ve y'yi bulmanız gerekir ax \u003d 1 + pp, yani. ax - py = 1 ve bu tür x ve y her zaman Öklid'in algoritması kullanılarak bulunabilir.

Sonlu bir alan çok ilginç bir matematiksel nesnedir. Örneğin, sonlu bir alandaki öğelerin sayısının yalnızca bir asal sayının kuvveti olabileceği ve bunun tersinin, herhangi bir p asal sayısı ve herhangi bir doğal sayı n için var olduğu ve belirli bir anlamda benzersiz olduğu ortaya çıktı. pn elemanlarının alanı . Hatta bunun için özel bir notasyon getirilmiştir: GF(p n ).

elemanları alanının ne anlamda benzersiz olduğunu daha ayrıntılı olarak açıklayalım . Matematikte, çalışılan özellikleri çakışan birçok nesne arasında ayrım yapmamak gelenekseldir. Örneğin toplama ve çarpma yapmak için toplama ve çarpma tablosunu elmalar için ayrı, sandalyeler için ayrı ayrı öğrenmek hiç de gerekli değildir. Sayıların nasıl ekleneceğini bilmek yeterlidir. Bu durumdaki sayı, ne olursa olsun, genelleştirilmiş bir ürünün birim sayısı olarak temsil edilebilir. Alan teorisinde, herhangi bir x!,x 2 6F için koşullar s ( x1+x 2 )=s(tf1) karşılanır +s(x2), z(x1x2)=z(x 1 )z(x2)> Aslında bu, tüm elemanları bire bir ilişkilendirebileceğiniz anlamına gelir. elemanları olan bir alan diğerinin böylece bu alanlardaki çarpma ve toplama tabloları aynı olacaktır". Örneğin, bir eşbiçimlilik altında sıfırın sıfıra ve birin bire gittiğini kanıtlamak kolaydır.

Kriptografide alanların kullanımının canlı bir örneği, RSA şifreleme sistemini açıklayan Etude 3.5'te bulunabilir. Bunu tam olarak anlamak için çözmenizi (veya sayı teorisi üzerine herhangi bir kitabı okumanızı, örneğin I.M. Vinogradov'un “Fundamentals of Number Theory” kitabını veya O. Ore'nin “Invitation to Number Theory” kitabını) okumanızı öneririz. aşağıdaki problemler.

Kendin için düşün:

1. Euler işlevi (</?(n) gösterimi), n'den küçük ve n'ye nispeten asal olan negatif olmayan tamsayıların sayısıdır . farklı asal sayılardır ve a!,...,"* doğal sayılardır. Kanıtla

¥>(n) = n • (1 --J-) •• (1 -

R1         Rk

2. (Fermat'nın Küçük Teoremi). P bir asal sayı olsun ve p, p'ye göre asal bir sayı olsun . kanıtla o zaman

bir P-i _ 1 (modp).

3. (Euler teoremi). a ve n görece asal sayılar olsun . kanıtla o zaman

a^(”) = 1 (modn).

4. Sayı çarpanlarına ayırma sorunları

ve ayrık logaritma

ilkokulda herkes problem çözer

sayıların asal çarpanlara ayrıştırılması. Bu, basitçe verilen sayıyı ardışık asal sayılara bölerek yapılır. Sayı büyükse, bu algoritma uzun süre çalışacaktır (bilgisayarda bile). Sayı çok büyükse (diyelim ki .200 karakter uzunluğunda), en modern bilgisayar yıllarca çalışma gerektirebilir. Ve garip

bir şekilde, şimdiye kadar matematikçiler çok daha hızlı çalışan başka bir algoritma bulamadılar. Böyle bir algoritma oluşturma problemi, sayıları çarpanlarına ayırma problemi olarak adlandırılır. Öte yandan, belirli bir sayının asal olup olmadığını yüksek olasılıkla belirlemeyi mümkün kılan hızlı algoritmalar vardır (ancak bu algoritmalar, bir sayının asal çarpanlara herhangi bir ayrıştırmasını bulamaz).

Sayı çarpanlarına ayırma probleminin kriptografik uygulamaları ve özellikle bankacılık dijital imza sistemleri kullanıcılarının ilgisi, sayıların çarpanlarına ayırma ile ilgili araştırmaların keskin bir şekilde artmasına neden olmuştur. Son yıllarda, sayı teorisi ve cebirsel geometrinin incelikli yöntemlerinin uygulanması yoluyla birkaç verimli çarpanlara ayırma algoritması geliştirilmiştir. Bu algoritmaların en iyisi henüz polinom değildir, ancak üstel de değildir, sözde alt üstel algoritmalar sınıfına aittir (kesin olarak, karmaşıklığı n'deki herhangi bir polinomu aşar, ancak herhangi bir Є > 0 için 2 n'den azdır ) .

Bu alandaki en son başarılar arasında, Haziran 1990'da 155 bitlik bir sayıyı üç asal sayıya ayrıştıran Lenstra ve Monassi'nin başarısından bahsedebiliriz. Bunu yapmak için, 1000 birleşik bilgisayar ve bilgisayar sürelerinin altı haftasını kullandılar. Hesaplamalar, İngiliz matematikçi J. Pollard'ın algoritması kullanılarak yapıldı. Lenstra ve Monassi, şu anda (1991 ) 155 basamağa kadar olan yeni tamsayı sınıflarını bir yıl içinde 200 milyon $ maliyetle ayrıştırmanın mümkün olduğuna inanıyor.

Diğer bir büyük sorun da sonlu alanlarda ayrık logaritmadır. Örneğin, bize sonlu bir F alanından a ve b elemanları verilsin ve bir doğal x için a = bx olduğu biliniyor . Ayrık logaritmanın görevi bu x'i belirlemektir . Elbette, belirtilen eşitliğin sağlanıp sağlanmadığını kontrol ederek tüm doğal sayıları sırayla gözden geçirebilirsiniz, ancak bu üstel bir algoritma olacaktır. Şimdiye kadar, matematikçiler tarafından geliştirilen en iyi ayrık logaritma algoritması alt üsteldir.

Şu anda, açıklanan bu zor matematiksel problemler çok sayıda kriptografik uygulamaya sahiptir (bkz. Etüt 3.5, 3.6, 3.7).

5. RSA şifreleme sistemi

Bölüm 3.2 , Diffie ve Hellman'ın gizli bir . Doğru, uygulamaya uygun işlevler sunmadılar.

Ancak, 1977'nin başında, Amerikalı uzmanlar

bilgisayar biliminde R. Rivest, A. Shamir ve L. Adleman böyle bir işlev buldular. Bu işleve dayalı sistem çok pratik hale geldi ve yazarların soyadlarının İngilizce ilk harflerinden sonra “RSA sistemi” adı altında yaygın olarak kullanıldı.

RSA sistemini açıklayalım. Bunu yaparken ayrıntılı açıklamalar olmaksızın etüt 3.2 ve 3.3'ün notasyonunu ve sonuçlarını kullanacağız. n = pq olsun , burada p ve q büyük asal sayılardır ve e, 9'a eş asal olan bir sayıdır?(n). Denklemden d sayısını bulun

d • e = l(mod9?(n)).

p, qn d sayıları gizli kabul edilecek ve sırrı K - {p, q, d} ile göstereceğiz. n ve e sayıları halka açık olarak kabul edilecektir. Açık mesajlar X ve şifreli mesajlar Y'nin kümeleri şuna eşit kabul edilecektir:

X = Y = {1,2,...,n-1}.

Fk : X -> Y işlevi eşitlikle tanımlanır

Fk(x) = a: e (modn).

Sırlı tek yönlü bir fonksiyonun a) özelliği, Fk için bariz bir şekilde geçerlidir. c) özelliğini kontrol edelim. Bunu yapmak için, bilinen К ile Fk fonksiyonunun nasıl ters çevrileceğini • Рк־(x) = y denklemini çözerek x = y d (modn) olacak şekilde gösteriyoruz . Bu gerçeğin ayrıntılı kanıtını okuyucuya bırakıyoruz, sadece gerekli hesaplamaları yorumsuz sunuyoruz:

d • e = 9?(n) • m + 1

(x e ) <i (modn) = a:^ n ^ TO+1 (modn) = (x^ n ^ ) m • a: (modn) = = (1) m • x(modn) = x.

Fk fonksiyonu için b) özelliği kesin olarak kanıtlanmamıştır. Şimdiye kadar, Fk'yi tersine çevirmek için n'yi çarpanlarına ayırmanın gerekli olduğu genel olarak kabul edildi ve Etüt 3.4'te belirtildiği gibi, tamsayıları çarpanlara ayırma problemi zor matematik problemlerinden biridir.

Fk fonksiyonu, sır içeren tek yönlü bir fonksiyon başlığına aday olarak kabul edilebilir . RSA sistemi, etüt 3.2'de açıklandığı gibi bu işlev kullanılarak oluşturulmuştur.

29 Nisan 1994 tarihli Izvestia gazetesinde "17 yılda çözülen çok gizli şifre" başlığı altında şu mesaj çıktı: 1977'de matematikçiler Ronald Rivest, Adi Shamir ve Leonard Adleman birkaç kelimeden oluşan bir cümleyi bir kombinasyon kullanarak şifrelediklerinde. 129 sayının çözülmesinin trilyonlarca yıl alacağını savundular. Ancak dünyanın en karmaşık şifresi ״RSA-129”un anahtarı 17 yılda bulundu... Bu kadar kısa bir sürede şifrenin çözülmesi, benzer uzun dijital kodları benzer uzun dijital kodlar kullanan devlet kurumları ve girişimciler için büyük önem taşıyor. bilgisayar veritabanlarındaki gizli bilgilerin korunması..." Bu mesaj bilimsel yayınlarla doğrulanmamakla birlikte, sadece 1977'de kullanılan 129 haneli sayıyı çarpanlarına ayırmayı başardığımızdan bahsettiğimiz açıktır. Ancak gerçek RSA sistemlerinde uzun süredir daha uzun sayılar kullanılmaktadır.

Kendiniz için düşünün: 1. M. Gardner'ın "From Penrose Tilings to Strong Ciphers" kitabının 241-243. sayfalarındaki RSA sistemi örneklerini inceleyin.

6. роме принципа построения криптосистемы с от-
7. Ortak anahtar dağıtımı

özel anahtar, Diffie ve Hellman aynı çalışmada başka bir yeni fikir buldular: açık anahtar dağıtımı. Böyle bir organizasyonun mümkün olup olmadığını merak ettiler.

1 ) Bu, RSA sistemini ifade eder. Aşağıdaki görevleri çözmek için A ve B abonelerinin açık iletişim kanalları aracılığıyla etkileşimi için hangi prosedür:

1. Başlangıçta A ve B'nin herhangi bir ortak gizli bilgisi yoktur, ancak prosedür sonunda A ve B'nin böyle bir paylaşılan gizli bilgisi (ortak anahtar), yani. üretilmiş;

2. Tüm iletimleri yakalayan ve A ve B'nin almak istediğini bilen bir düşman, yine de A ve B'nin oluşturulmuş ortak anahtarını kurtaramaz.

Diffie ve Hellman, işlevi kullanarak bu sorunları çözmeyi önerdi.

F(x) = "®(modp),

burada p büyük bir asal sayıdır, x gelişigüzel bir doğal sayıdır ve GF(p) alanının ilkel bir elemanıdır .

'nin bir a öğesinin ilkel olduğu söylenir , öyle ki alanın her öğesi, sıfır hariç, a'nın bir kuvveti olarak temsil edilebilir. İlkel bir öğenin her zaman var olduğu, kolay olmasa da kanıtlanabilir.

"® (modp) işlevinin tersine çevrilmesinin, yani. ayrık logaritma zor bir matematik problemidir (bkz. Etüt 3.4).

Prosedürün kendisi veya dedikleri gibi, paylaşılan bir anahtar oluşturma protokolü aşağıdaki gibi açıklanmaktadır.

p ve a sayıları halka açık kabul edilir.

A ve B aboneleri , birbirlerinden bağımsız olarak rastgele bir doğal sayı seçerler — diyelim ki xa 11 X B. Bu öğeleri gizli tutarlar. Sonra her biri yeni bir eleman hesaplar:

y a = a Xx (modp), uv = a* B (modp).

Daha sonra bu öğeleri bir iletişim kanalı üzerinden değiş tokuş ederler. Şimdi, y'yi alan ve gizli öğesi Xa'yı bilen A abonesi , yeni bir öğe hesaplar.

y^(modp) = (bir Xv y l (modp).

Abone B aynısını yapar:

2/d in (tos/p) = (bir XA ) Xv (modp).

Alanın özelliklerinden, bu şekilde, A ve B'nin XlXv'ye eşit, alanın ortak bir öğesine sahip olduğu sonucu çıkar . Bu eleman, A ve B'nin ortak anahtarı olarak bildirilir.

a XA , a Xv bildiği, w ve xv bilmediği ve bir XXv bilmek istediği görülebilir . Şu anda, ayrık logaritmadan daha verimli rakip algoritma yoktur ve bu zor bir matematik problemidir. (Rakip için ortak anahtarı, ayrık logaritma algoritmasını kullanarak ve karmaşıklığıyla ilgili sorunları hesaba katmadan kendi başınıza bulmanızı öneririz.)

8. дея цифровой подписи (иногда ее еще называют
9. Elektronik imza

elektronik imza) Diffie ve Hell-

5 - 6893

Maine. Fikrin özü, gizli Fk ile tek yönlü bir işlev kullanmaktır (bkz. Etüt 3.2). Şu anda, bu fikir çok sayıda veri aktarım sisteminde, özellikle bankacılık sistemlerinde uygulanmıştır. Dijital imza ile imzalanan bir mesaj bir çift (x, y) olarak düşünülebilir , burada x bir mesajdır (örnekte bir banka ile ödeme talimatı vb.), F K : X -> Y birdir Etkileşen abonelerin bildiği yol fonksiyonu, y , Pk(y) = x denkleminin çözümüdür . Fk fonksiyonunun tanımından (bkz. Etüt 3.2), dijital imzanın aşağıdaki avantajları açıktır:

1. x mesajını imzala , yani Fr־ (! /) = x denklemini çöz , sadece abone - bu gizli K'nin sahibi; yani sahte imza yapılamaz;

2. Genel anahtarı bilen herhangi bir abone, imzanın gerçekliğini doğrulayabilir, yani. Fk işlevinin kendisi ;

3. ihtilaf durumunda, imzanın geri çevrilemezliği nedeniyle reddedilmesi mümkün değildir;

4. imzalı mesajlar (w, y} herhangi bir iletişim kanalından zarar görme korkusu olmadan gönderilebilir.

Dijital imza sistemlerinin yaygın olarak kullanılmasına yol açan bu avantajlardır. Dijital imza kullanımının pratikte nasıl göründüğünü en basit örnekle açıklayalım: Bir bankanın müşterilerinin ödeme emirleriyle yaptığı işi. Bu ağın tüm aboneleri tek yönlü Fk işlevini bilir, her müşterinin kendi bilinmeyen K sırrı vardır . Müşteri, gizli K ile Fk işlevini kullanarak x ödeme emrini imzalar ve imzalanan ödeme talimatını bankaya gönderir. Müşteriden bir mesaj alan 

ve genel anahtarı bilen banka, müşterinin imzasının gerçekliğini doğrular ve ancak o zaman ödeme emrini yerine getirir. Dijital imzanın yukarıda belirtilen avantajları nedeniyle hem banka hem de müşteri menfaatlerinin etkilenmeyeceğinden emindir.

Подумайте сами:

Elektronik ödeme sistemlerinin, e-posta ve diğer veri iletim sistemlerinin yaygın gelişimi, çok çeşitli dijital imzaları gerektirmiştir. Bu, şu anda teorik kriptografinin büyük bir bölümünü oluşturan dijital imza protokolleri teorisinin gelişmesine yol açtı. Bu teori çerçevesinde, bir dijital imza sistemine yönelik çeşitli düşman saldırıları, bir rakibin elde edebileceği çeşitli başarı türleri, dijital imza şemalarının çeşitli güç türleri sistemleştirilir. Bir anlamda, iki varsayımsal nesnenin varlığının denkliğini kanıtlamak da mümkündü: tek yönlü bir işlev ve güvenli bir dijital imza şeması.

1. Etüt 3.2'deki genel şemayı kullanarak, RSA dijital imza şemasını tanımlayın.

10. kriptografik protokol nedir

J спехи,

Bir kriptografik protokol, abonelerin (rakiplerin değil!) Hedeflerine ulaşmasının bir sonucu olarak, abonelerin etkileşimi için böyle bir prosedür olarak anlaşılır, ancak düşman bunu başaramaz.

dijital devrelerin tasarımında elde edilen

imzalar ve genel anahtar dağıtımı, bu fikirlerin uzak aboneler arasındaki diğer etkileşim sorunlarına da uygulanmasına izin verdi. Böylece yeni ve büyük bir teorik kriptografi dalı ortaya çıktı: kriptografik protokoller . Şu anda, hala yerleşik tanımlar ve genel kabul görmüş terminoloji yoktur, ancak okuyucuya bu yeni ilginç alan hakkında gayri resmi bir fikir vermenin gerekli olduğunu düşünüyoruz.

Kriptografik protokoller teorisinin çalışmanın amacı, açık iletişim kanalları aracılığıyla etkileşime giren uzak abonelerdir. Abonelerin etkileşiminin amacı, bazı sorunları çözmektir. Bir de kendi hedeflerinin peşinden koşan bir düşman var. Aynı zamanda, düşman farklı görevlerde farklı yeteneklere sahip olabilir: örneğin, diğer aboneler adına abonelerle etkileşime girebilir veya aboneler arasındaki bilgi alışverişine müdahale edebilir, vb. Düşman, abonelerden biri veya bir anlaşma yapmış birkaç abone bile olabilir.

Genel anahtar dağıtımı ve dijital imza için daha önce çalışılan protokollerin örneklerini kullanarak tanıtılan kavramları bağımsız olarak düşünmek faydalıdır.

Uzak aboneler tarafından çözülen görevlere birkaç örnek daha verelim. (Okuyucunun kendi zevkine göre daha fazla örnek bulması teşvik edilir).

1. Birbirine güvenmeyen iki abone etkileşime giriyor. Sözleşme imzalamak istiyorlar. Bu, aşağıdaki durumu önleyecek şekilde yapılmalıdır: abonelerden biri diğerinin imzasını aldı, ancak kendisi imzalamadı.

sözleşme imzalama protokolü denir .

2. Birbirine güvenmeyen iki abone etkileşime giriyor. Madeni parayla kura çekmek istiyorlar. Bu, yazı tura atan kullanıcı, bu sonucu tahmin eden kullanıcıdan bir tahmin aldıktan sonra, yazı tura atmanın sonucunu değiştiremeyecek şekilde yapılmalıdır.

yazı tura atma protokolü denir .

Telefona yazı tura atmak için en basit protokollerden birini açıklayalım (sözde Blume-Micali şeması). Bunu uygulamak için, A ve B abonelerinin aşağıdaki koşulları karşılayan /:X-4Y tek yönlü bir işlevi olmalıdır:

1. X, aynı sayıda çift ve tek sayıları içeren sonlu bir tamsayılar kümesidir;

2. herhangi bir sayı х!,х 2 €Х bir görüntüye sahip /(х!)=/(х 2 ) bir pariteye sahiptir;

3. /(x) görüntüsü verildiğinde, bilinmeyen x argümanının paritesini hesaplamak zordur.

Bir yazı tura atma rolü, x € X öğesinin rastgele ve eşitlenebilir bir seçimiyle oynanır ve tura ve yazıların rolü, sırasıyla x'in düzgünlüğü ve tuhaflığı tarafından oynanır. A yazı tura atan kişi ve B tahmin eden kişi olsun . Protokol aşağıdaki adımlardan oluşur:

1. A, x'i seçer (yazı tura atar), x'i şifreler, yani y=/(x)'i hesaplar ve y'yi abone B'ye gönderir ;

2. B , y'yi alır, x'in paritesini tahmin etmeye çalışır ve tahminini abone A'ya gönderir ;

3. A, B'den bir tahmin alır ve B'ye seçilen x sayısını göndererek doğru tahmin edip etmediğini söyler;

4. B, /(x) değerini hesaplayarak ve ikinci adımda elde edilen y değeriyle karşılaştırarak A'nın hile yapıp yapmadığını kontrol eder .

Okuyucunun / işlevinin özelliklerinden dolayı yazı-tura protokolü için gerekli gereksinimlerin karşılanıp karşılanmadığını kendisinin kontrol etmesi önerilir.

3. İki abone A ve B etkileşim içindedir (tipik örnek: A bir banka müşterisidir, B bir bankadır). Abone A, abone B'ye kendisinin A olduğunu ve rakip olmadığını kanıtlamak istiyor.

abone tanımlama protokolü denir .

4. Bir merkezden emir alan birkaç uzak abone etkileşim halindedir. Merkez dahil bazı aboneler rakip olabilir. Aboneler için avantajlı olan birleşik bir eylem stratejisi geliştirmek gereklidir.

Bu soruna genellikle Bizans generallerinin sorunu denir ve çözüm protokolüne Bizans anlaşmasının protokolü denir.

Bu sorunun adını borçlu olduğu bir örneği açıklayalım. Bizans. Büyük savaştan önceki gece. Bizans ordusu , her biri kendi generaline bağlı n lejyondan oluşur. Ayrıca ordunun generalleri yöneten bir başkomutanı vardır. Ancak imparatorluk düşüşte ve başkomutan da dahil olmak üzere generallerin üçte biri hain olabilir. Gece boyunca, generallerin her biri başkomutandan sabahki eylemlerle ilgili bir emir alır ve emir için iki seçenek mümkündür: saldırı veya geri çekilme. Tüm dürüst generaller saldırırsa kazanırlar. Hepsi geri çekilirse, orduları kurtarmayı başarırlar). Ama bir kısmı saldırır ve bir kısmı geri çekilirse, o zaman yenilirler. Başkomutan hain çıkarsa farklı generallere farklı emirler verebilir, dolayısıyla başkomutanın emirlerine zımnen uyulmamalıdır. Her general diğerlerinden bağımsız hareket ederse, sonuçlar felaket olabilir.” Açıkçası, generallerin bir anlaşmaya varmak için birbirleriyle (alınan emirlerle ilgili) bilgi alışverişinde bulunmaları gerekiyor.

Çeşitli protokollerin ve bunların inşası için yöntemlerin anlaşılması 1985-1986'ya öncülük etti. iki verimli matematiksel modelin ortaya çıkmasına - etkileşimli kanıt sistemi ve sıfır bilgi kanıtı Bu yeni nesnelerin matematiksel çalışmaları, kriptografik protokollerin geliştirilmesinde çok yararlı olan birkaç ifadeyi kanıtlamamıza izin verdi.

Etkileşimli bir ispat sistemi (Р, V, S), iki abone arasındaki etkileşim protokolü olarak anlaşılır : Р (kanıtlama) ve V (doğrulama). Abone P, V'ye S ifadesinin doğru olduğunu kanıtlamak istiyor . Aynı zamanda, abone V bağımsız olarak, P'nin yardımı olmadan S ifadesini kanıtlayamaz (bu nedenle V'ye doğrulayıcı denir). P abonesi, S önermesinin yanlış olmasına rağmen doğru olduğunu V'ye kanıtlamak isteyen bir hasım da olabilir . Protokol, P ve V arasında birçok mesajlaşma turundan oluşabilir ve iki koşulu karşılamalıdır:

1. tamlık - eğer S gerçekten doğruysa, o zaman P abonesi neredeyse kesinlikle V abonesini bunu kabul etmeye ikna edecektir;

2. doğruluk - eğer S yanlışsa, P abonesinin V abonesini S'nin doğru olduğuna ikna etmesi olası değildir.

Burada, olasılık kavramını kullanan kesin matematiksel formülasyonları "neredeyse kesinlikle" ve "zorla" sözcükleriyle değiştirdik.

Sistemin tanımında (P, V, S) V'nin düşman olmasına izin verilmediğini vurguluyoruz. Peki ya V'nin, P'den S ifadesi hakkında bazı yeni yararlı bilgiler "öğrenmek" isteyen bir hasım olduğu ortaya çıkarsa? bu durumda P, protokolün (P, V, S) işleyişi sonucunda bunun olmasını elbette istemeyebilir . Böyle bir sorunu çözen bir protokole (P, V, S) sıfır bilgi kanıtı denir ve 1. ve 2. koşullara ek olarak aşağıdaki koşulu da karşılaması gerekir:

3. sıfır bilgi (veya güvenlik) - protokolün (P, V, S) çalışmasının bir sonucu olarak, abone V S ifadesi hakkındaki bilgisini artırmayacak veya başka bir deyişle herhangi bir bilgi çıkaramayacaktır. S'nin neden doğru olduğu hakkında .

En şaşırtıcı şey, 1991'de geniş bir matematik problemi sınıfı için (sözde dahil)

tam problemler) sıfır bilgi kanıtlarının varlığını kanıtladı. Ancak, bu yalnızca tek yönlü bir fonksiyonun var olduğu varsayımı altında kanıtlanmıştır.

İşte sıfır bilgi kanıtları teorisinin pratik bir uygulaması - "akıllı kartlar" (kopyalanamaz kimlik kartları, kredi kartları, vb.). Sıfır bilgi kanıtı protokolü (P, V, S) olduğunu iddia eden bir protokolde P abonesinin eylemlerini uygulayan yerleşik bir mikroişlemciye sahiptirler . Burada abone P , kartın sahibidir ve abone V, örneğin bir bankadaki veya gizli bir kurumun kontrol noktasındaki bir bilgisayardır. Böyle bir durumda kimlik belgelerinin ve kredi kartlarının taklit edilemezliğinin sağlanmasının neden mümkün olduğunu bir düşünün.

ы прочли первую книгу по криптографии.

Çözüm

Kriptografi tarihi, onunla ilgili olaylar ve efsaneler hakkında daha fazla bilgi edinmek istiyorsanız , D. Kahn ve T.A.'nın kitaplarını bulup okumanızı öneririz. Soboleva'nın yanı sıra ״Cryptology dergisinin tüm sayıları.

Programlamaya meraklıysanız ve bazı kriptografik algoritmaları kendiniz uygulamak istiyorsanız, o zaman öncelikle D. Knuth'un etüt 2.8'de bahsedilen kitabına hakim olmanızda fayda var. Ardından, bilgisayar bilgi güvenliği konusunda programcılar için birçok kitaptan birine dönebilirsiniz.

Kriptografların matematiksel konularıyla ilgileniyorsanız, öncelikle etK> da 2.1, 2.2, 2.3, 3.3, 3.4 ve 3.8'de bahsedilen matematiğin bu bölümlerini araştırmanız gerekir. Bu alanda sistematik eğitim, girişte listelenen üniversitelerin herhangi birinde alınabilir.

Kriptografi hakkında başka ne okuyabilirsiniz?

1. T.A. Sobolev. Rusya tarihinde gizli yazı • (XVIII - XX yüzyılın başlarında Rusya'nın kriptografik hizmetinin tarihi) • M., 1994.

2. K. Shannon. Bilgi teorisi ve sibernetik üzerine çalışır. M., İL, 1963.

3. W. Diffie, ME Cehennem adamı. Güvenlik ve taklit direnci. Kriptografiye giriş. TIER, cilt 67, N 3, 1979.

4. G. Frolov. Kriptografinin sırları. M., 1992.

5. Bay Gardner. Penrose Mozaiklerinden Güvenli Şifrelere. M., Mir, 1993.

6. BİR. Lebedev. “Genel anahtar” ile kriptografi ve pratik uygulama olasılığı. “Bilgilerin korunması”, sayı 2, 1992.

BAŞVURU

Kriptografide olimpiyatların seçilmiş görevleri

Kriptografi, İletişim ve Bilişim Enstitüsü (ICSI), Rusya Federasyonu Federal Karşı İstihbarat Servisi Akademisi'nin bir parçasıdır. ICSI'nin iki fakültesi vardır: bilişim ve özel mühendislik. Enstitü, bilgi güvenliği, kriptografi, özel iletişim ve bilgisayar güvenliği alanlarında yüksek nitelikli uzmanlar yetiştirmektedir.

ICSI'de okul çocukları için bir akşam fizik ve matematik okulu vardır. Enstitü 1991'den beri kriptografi ve matematik yarışmaları düzenliyor ve bu yarışmaların seçilmiş sorunları bu ekte yayınlanıyor.

Görevler

1. "Kafes" adı verilen şifrenin anahtarı, n x n (n çifttir) ölçülerinde kare kareli bir kağıttan yapılmış bir şablondur. Hücrelerin bir kısmı, şifrelenecek metnin harfleri aynı boyutta boş bir kağıt üzerinde ortaya çıkan deliklere girilebilecek şekilde kesilir. Şablonun bir tarafı işaretlenmiştir. Ek olarak, şablonun önemli bir özelliği olmalıdır: boş bir kağıda dört olası şekilde uygulandığında (işaretli taraf yukarı, sağ, aşağı, sol), kesikleri karenin tüm alanını tamamen kaplar ve her biri hücre tam olarak bir kez kesmenin altındadır.

Uzunluğa sahip olan mesajın harfleri n2 , belirtilen dört pozisyonun her birinde şablonun kesiklerine sırayla sığar. Şablonu çıkardıktan sonra, bir kağıt parçası üzerinde şifreli bir mesaj belirir.

Rastgele bir çift sayı n için farklı anahtarların sayısını bulun.

2. Olimpiyatlara şifreli bir telgraf gönderildi

TsDOZIFKDTSYU.

Alfabedeki harfin iki haneli seri numarasına polinom değerinin eklendiği bir şifre kullanıldığını biliyorsanız şifreli mesajı okuyun (01'den 33'e kadar)

f(x) \u003d x 6 + Zx 5 4־ x 4 + x 3 4- 4x 2 44 ־x 45 ־,

X = X1'de veya X = X2'de (rastgele sırada) hesaplanır, burada

2 4־ Зх 41 ־ üçlüsünün kökleri ve ardından elde edilen sayı, ona karşılık gelen harfle değiştirildi.

3. Bir firma otomatik bir şifre denetleyici önerdi. Parola, {a, 6, c) alfabesindeki boş olmayan sıralı herhangi bir harf grubu olabilir. Bu tür kümeleri büyük Latin harfleriyle göstereceğiz. Cihaz içine girilen P setini Q = y>(P) setine işler. <p eşlemesi gizli tutulur, ancak her P harf grubu için tanımlanmadığı ve aşağıdaki özelliklere sahip olduğu bilinmektedir. Herhangi bir harf grubu için R

1) <p(aP) = P; 2) <p(bP) = ^(P)a^(P);

<p(cP) kümesi, <p(P) kümesinden harflerin ters sırada yazılmasıyla elde edilir.

<p(P) = P ise cihaz sunulan şifreyi doğru olarak tanır. Örneğin, <p(bab) = <p(ab)a<p(ab) = bab olduğundan, üç harfli bab kümesi bir şifredir. . Üçten fazla harf içeren bir şifre seçin.

4. Bir tüccar, dijital bilgiyi iletmek için, iletimi kontrol etmek için, iletilen rakamlar satırını beşe böler ve her iki beşten sonra, bu beşlerin gösterdiği sayıların toplamından son iki haneyi atar. Daha sonra şifreleme işlemi, bir aritmetik ilerlemenin üyelerini şifrelenmiş basamaklara ekleyerek, ardından basamak toplamlarını 10'a bölmekten kalanlarla değiştirerek gerçekleştirilir. Şifreli mesajı okuyun:

42346140531 3.

5. Dijital bir metin için, her basamağın polinomun değerinin bölümünden kalanla değiştirildiği bir şifre modeli düşünün.

f(x) = b(x 3 4- 7x 2 4־ Zx 4־ a)

10 sayısı ile, burada a,6 sabit doğal sayılardır. Hangi a ve b değerlerinin kesin kod çözmenin mümkün olduğunu öğrenin.

6. Şirket, pazara bir şifreli kilit sundu. Ayar yaparken, kilidin sahibi klavyede bulunan 26 Latin harfinin her birini rastgele bir doğal sayıyla eşleştirir (yalnızca kilidin sahibi tarafından bilinir). İkili olarak farklı harflerden rastgele bir kombinasyon seçtikten sonra, yazılan harflerin sayısal değerleri toplanır ve toplam 26'ya bölünebilirse kilit açılır. Harflerin herhangi bir sayısal değeri için bir kombinasyon olduğunu kanıtlayın bu kilidi açar.

7. Rus 30 harfli Q alfabesinin harflerinin aşağıdaki tabloya göre numaralandırıldığı bir şifreyi ele alıyoruz:

ABVGDEZHZIKLMNOPR STU FKhTSCHSHSHCH YE YUYA 1234567 89 1011 1213141516171819 20 2122 2324 25 26 27 28 29 30

m = t\t2 ..L p mesajını şifrelemek için , P alfabesinin harflerinden oluşan bir k = 7172 * * •7p (anahtar) dizisi seçilir. bu toplamın kalanını 30'a böler.

Bilindiği gibi iki mesaj t! ve T2'nin aynı anahtarla (k) şifrelendiğini ve her birinin ״ships״ kelimesini içerdiğini. 71 ve t 2'yi şu kriptogramların metinlerine göre geri yükleyin:

A! \u003d UPTTSARG SHALZHE VTSCHYRVUU a 2 \u003d YUPYATVNSCHMSDT L ZhGPS G HSTTS

8. Yakalanan ״şifreleme

RBNPTSITSRREZOH

Şifre hakkında bilinenler şunlardır:

• önceki görevin şifresi kullanılır;

• anahtar olarak, keyfi bir harf dizisi kullanılır: A, B, C.

Şifreli mesajı okuyun.

9. A = {a!, 02,..., an n ) alfabesindeki n farklı harften oluşan basit ikame şifresi , şifreli metnin her harfinin aynı alfabeden bir harfle değiştirilmesinden oluşur ve farklı harfler, farklı olanlar Basit ikame şifre anahtarı, A alfabesindeki her bir harfin hangi harfle değiştirileceğini gösteren bir tablodur. ACİL kelimesi, anahtar kullanılarak basit bir ikame ile şifrelenmişse:

ABC G DEZHZ IKLMNOPRSTUFHTSCHSHSHCHYEYYUYA CHAYEYBLSCHCHFUBDTZVRMLKAI OJEGN N, sonra VZDABD kelimesini alırsınız. Alınan kelimeyi tekrar aynı anahtar ile şifreleyerek yeni bir kelime YUSHYCHYAYY elde ederiz. Belirtilen şifreleme işlemi süresiz olarak devam ettirilirse kaç farklı kelime elde edilebilir?

10. A noktasında, Rus dilinin harflerinin alfabesinde basit bir ikame şifresi ve kelimeler arasında bir boşluk karakteri (_) ile şifrelenen mesaj, 12 karakterlik bölümler halinde B noktasına iletilir. Bir sonraki segmenti iletirken, ikinciden başlayarak önce onun numaralarının artan sırasına göre çift yerlerde olan tüm karakterleri iletilir ve ardından tek yerlerde olan tüm karakterler de sayılarının artan sırasına göre iletilir. birinciden. B noktasında, alınan şifreli mesaj, aynı alfabedeki başka bir basit ikame şifresi kullanılarak ek olarak şifrelenir ve ardından, A noktasında olduğu gibi, C noktasına iletilir. C noktasında yakalanan segmentler kullanılarak

orijinal mesajı geri yükle

SO_GZHTP NBL ZHO RS TKD KS PHE U B . E PF PU B_ YuO B SP _ EO KZHUUL ZHL SMTSHB EK GOSHP Y UL kl_ik ntl zhg,

iletilen segmentlerden birinde CRYPTOGRAPHY kelimesinin şifreli olduğunu bilmek.

11. С n'nin n n sayısının son basamağı olduğu С1, С2, Сз,..., С׳ n ,... dizisi verildi . Bu dizinin periyodik olduğunu ve periyodunun 20 olduğunu gösteriniz.

12. Rus dilinin harflerinden ve kelimeler arasındaki boşluk karakterinden (_) oluşan alfabenin karakterlerini tabloya göre sayı çiftleriyle değiştireceğiz:

AB VG D E GZ ICL MNOPR ST U FHTSCHSHSHCH YE YUYA. 0102 03 04 05 06 07 08 09 10 11 12 13 14 15 16 1718 19 20 21 22 23 24 25 26 27 28 29 30 31

Bu alfabe ile yazılmış m uzunluğundaki bir mesajı şifrelemek için önce alfabetik metni T = ¢1, /2, • • • > *2m> dijitale çeviriyoruz ve ardından K = С׳ n +1 segmentini seçerek, С ׳ n +2> •. •, Problem 11'deki dizinin C n + 2m'si, T metninin rakamlarını K segmentinin rakamlarıyla sıralı bitsel toplama yapalım ve karşılık gelen toplamın (en az anlamlı rakam) birim basamağı alınır şifreli metnin bir sonraki karakteri olarak.

Şifrelenmiş mesajı okuyun:

2 3 3 9 8,6 7 2 1 6,4 5 8 1 6,0 6 7 0 6.1.7 W 1 5,5 8 8.

DİKKAT!

Şu anda, BAŞVURU SAHİBİNİN benzersiz PRATİK ANSİKLOPEDİSİ, Birinci Örnek Matbaa'da sınırlı sayıda basılmaktadır.

VV Tkachuk. Matematik - başvuru sahibine. Cilt I ve II. - M.: TEİS, 1994. - 499 + 553 sayfa.

İlk kez yayınlanan kitap, herhangi bir karmaşıklık seviyesindeki giriş sınavlarına hazırlanmak için temel matematik alanında en eksiksiz özel derstir. Ülkenin önde gelen üniversiteleri tarafından çok çeşitli kriterlerde başarıyla test edilmiş benzersiz kendi kendine çalışma algoritmaları sunulmaktadır.

Sınavlar sırasında davranış psikolojisi hakkında özel tavsiyeler verilir. Önyargı testi ve temyizde davranış gibi daha önce tabu olan konular ilk kez ustalıkla işleniyor. Moskova Devlet Üniversitesi'nin tüm fakülteleri için giriş sınavı seçeneklerine ayrı bir bölüm ayrılmıştır. M.V. Kullanılan değerlendirme kriterleri ile son 23 yıldır Lomonosov. Cevaplarla birlikte sözlü sınav biletlerinin tam sürümleri sunulmaktadır. Temel matematiğin temel kavramlarının ve gerçeklerinin ayrı bir bölümde verilen sistematik listesi, kitap üzerindeki çalışmayı büyük ölçüde kolaylaştırır.

İki ciltlik kitap, okul matematik dersini bağımsız, son derece etkili ve kısa sürede tekrarlamanıza olanak tanır. Kitap, ülkenin uzak bölgelerinden başvuranlar için özellikle değerlidir. Ayrıca öğretmenler, matematik öğretmenleri, çevrelerin ve seçmeli derslerin liderleri, hazırlık kurslarının öğretmenleri için de yararlıdır.

Kitabın yazarı, hem ders verme hem de Moskova Devlet Üniversitesi seçim komitesinde çalışma konusunda engin deneyime sahiptir.

Kitabı satın almak için lütfen Staraya Ploshchad reklam ajansıyla iletişime geçin:

127016, Moskova, posta kutusu 2, tel. 939-45-27, faks 488-75-38.

Yazarlar hakkında bilgi

Dorichenko Sergey Aleksandroviç — Moskova Devlet Üniversitesi laboratuvarının kriptografinin matematiksel problemleriyle ilgili çalışanı, milletvekili. Moskova Şehir Matematik Olimpiyatı Organizasyon Komitesi Başkanı.

Yashchenko Valery Vladimirovich - Fiziksel ve Matematiksel Bilimler Adayı, Moskova Devlet Üniversitesi Kriptografinin Matematiksel Problemleri Laboratuvarı'nın Önde Gelen Araştırmacısı

MSU laboratuvarı

kriptografinin matematiksel problemlerinde

Laboratuvar, teorik kriptografinin temel problemlerinin geliştirilmesi ile ilgilenmektedir.

Bilimsel araştırmanın ana yönleri:

• bilinenlerin incelenmesi ve yeni tek yönlü fonksiyonların oluşturulması,

• kriptografide kodlama teorisi yöntemleri,

• kriptografide karmaşıklık teorisi sorunları,

• kriptolojide ortaya çıkan ayrık matematik, cebir ve sayı teorisi problemlerinin gelişimi.

Laboratuvar, bilgi güvenliği algoritmalarının (bankacılık ve benzeri ağlar için dijital imza ve değişim protokolleri, konuşma bilgilerini kodlama algoritmaları, vb.) geliştirilmesi ve gerekçelendirilmesine ilişkin uygulamalı araştırmalara katılır.

Laboratuvar, kriptografik bilgi koruma önlemlerinin güvenliği konusunda danışmanlık hizmetleri sunabilir.

Laboratuvarın başkanı, Rusya Federasyonu Kriptografi Akademisi Akademisyeni, Fizik ve Matematik Bilimleri Doktoru V.M. Sidelnikov.

---

[1]) David Kahn. kod kırıcılar. Gizli Yazının hikayesi. New York, Macmillan, 1967.

Not: Bazen Büyük Dosyaları tarayıcı açmayabilir...İndirerek okumaya Çalışınız.

Benzer Yazılar