Trapdoor işlevi - Trapdoor function

Tuzak kapısı işlevi fikri. Bir tuzak kapısı işlevi f tuzak kapısı ile t bir algoritma tarafından oluşturulabilir Gen. f verimli bir şekilde hesaplanabilir, yani olasılıksal olarak polinom zamanı. Ancak, tersinin hesaplanması f tuzak kapısı olmadığı sürece genellikle zordur t verilmiş.^[1]

Bir trapdoor fonksiyonu bir işlevi tek yönde hesaplaması kolay, ancak ters yönde hesaplaması zordur ( ters ) özel bilgi olmadan, "tuzak kapısı" olarak adlandırılır. Trapdoor fonksiyonları yaygın olarak kullanılmaktadır. kriptografi.

Matematiksel terimlerle, eğer f bir tuzak kapısı işlevidir, bu durumda bazı gizli bilgiler vardır t, öyle verilen f(x) ve thesaplaması kolaydır x. Bir düşünün asma kilit ve anahtarı. Kilit mekanizmasının içerisine kelepçeyi iterek, asma kilidi anahtarı kullanmadan açıktan kapalıya değiştirmek çok önemlidir. Ancak asma kilidin kolayca açılması anahtarın kullanılmasını gerektirir. Burada anahtar, tuzak kapısı ve asma kilit, tuzak kapısı işlevidir.

Basit bir matematiksel tuzak kapı örneği "6895601 iki asal sayının çarpımıdır. Bu sayılar nedir?" Tipik bir çözüm, cevabı bulana kadar 6895601'i birkaç asal sayıya bölmeyi denemektir. Ancak, 1931'in sayılardan biri olduğu söylenirse, cevabı herhangi bir hesap makinesine "6895601 ÷ 1931" girerek bulabilirsiniz. Bu örnek sağlam bir tuzak kapısı işlevi değildir - modern bilgisayarlar bir saniye içinde olası tüm yanıtları tahmin edebilir - ancak bu örnek sorun şu şekilde iyileştirilebilir: çok daha büyük iki astarın ürününü kullanarak.

Trapdoor fonksiyonları, kriptografi 1970'lerin ortalarında asimetrik (veya açık anahtar) şifreleme teknikleri Diffie, Cehennem adamı, ve Merkle. Aslında, Diffie ve Hellman (1976) terimi icat etti. Birkaç işlev sınıfı önerilmişti ve kısa süre sonra tuzak kapısı işlevlerinin bulunmasının başlangıçta düşünüldüğünden daha zor olduğu ortaya çıktı. Örneğin, erken bir öneri, şuna dayalı şemaları kullanmaktı. alt küme toplamı sorunu. Bu oldukça hızlı bir şekilde uygunsuz olduğu ortaya çıktı.

2004 itibariyle^{[Güncelleme]}en iyi bilinen tuzak kapısı işlevi (aile) adayları, RSA ve Rabin fonksiyon aileleri. Her ikisi de üs alma modülü olarak yazılmıştır ve bileşik bir sayıdır ve her ikisi de şu problemle ilgilidir: asal çarpanlara ayırma.

Sertliği ile ilgili fonksiyonlar ayrık logaritma problemi (modulo a asal veya bir eliptik eğri ) değil Ayrık logaritmaların verimli hesaplanmasını sağlayan grup hakkında bilinen hiçbir "tuzak kapısı" bilgisi olmadığından, tuzak kapısı işlevleri olarak bilinir.

Kriptografide bir tuzak kapısı, yukarıda bahsedilen çok özel bir anlama sahiptir ve arka kapı (bunlar sıklıkla birbirinin yerine kullanılır, bu da yanlıştır). Arka kapı, bir kriptografik algoritmaya (örneğin bir anahtar çifti oluşturma algoritması, dijital imzalama algoritması, vb.) Veya işletim sistemine eklenen, örneğin bir veya daha fazla yetkisiz tarafın güvenliklerini atlamasına veya alt üst etmesine izin veren kasıtlı bir mekanizmadır. sistem bir şekilde.

Tanım

Bir trapdoor fonksiyonu bir koleksiyon tek yönlü işlevler { f_k : D_k → R_k } (k ∈ K), içinde tümü K, D_k, R_k ikili dizelerin alt kümeleridir {0, 1}^*, aşağıdaki koşulları yerine getirir:

Olasılıklı bir polinom zamanı (PPT) vardır örnekleme algoritma Gen s.t. Gen (1ⁿ) = (k, t_k) ile k ∈ K ∩ {0, 1}ⁿ ve t_k ∈ {0, 1}^* tatmin | t_k | < p (n), içinde p bir polinomdur. Her biri t_k denir tuzak kapısı karşılık gelen k. Her bir tuzak kapısı verimli bir şekilde örneklenebilir.
Verilen girdi k, ayrıca çıktı veren bir PPT algoritması vardır. x ∈ D_k. Yani her biri D_k verimli bir şekilde örneklenebilir.
Herhangi k ∈ K, doğru hesaplayan bir PPT algoritması vardır. f_k.
Herhangi k ∈ K, bir PPT algoritması var Bir öyledir herhangi x ∈ D_k, İzin Vermek y = Bir ( k, f_k(x), t_k ) ve sonra bizde f_k(y) = f_k(x). Yani, tuzak kapısı verildiğinde, tersine çevrilmesi kolaydır.
Herhangi k ∈ K, kapaksız t_k, herhangi bir PPT algoritması için, doğru şekilde tersine çevirme olasılığı f_k (yani verilen f_k(x), bir ön resim bulun x ' öyle ki f_k(x ' ) = f_k(x)) ihmal edilebilir.^[2]^[3]^[4]

Yukarıdaki koleksiyondaki her işlev tek yönlü bir permütasyon ise, koleksiyona ayrıca trapdoor permütasyonu.^[5]

Örnekler

Aşağıdaki iki örnekte, büyük bir bileşik sayıyı çarpanlara ayırmanın her zaman zor olduğunu varsayıyoruz (bkz. Tamsayı çarpanlara ayırma ).

RSA Varsayımı

Bu örnekte, tersine sahip olmak e modulo φ (n), Euler'in totient işlevi nın-nin n, tuzak kapısı:

{ displaystyle f (x) = x ^ {e} mod n}

Çarpanlara ayırma biliniyorsa, φ (n) hesaplanabilir, yani tersi $d$ nın-nin $e$ hesaplanabilir $d$ = e⁻¹ mod φ (n) ve sonra verilir y = f(x) bulabiliriz x = y^d mod n = x^ed mod n = x mod n. Sertliği RSA varsayımından kaynaklanmaktadır.^[6]

Rabin'in İkinci Dereceden Kalıntı Varsayımı

İzin Vermek n büyük bir bileşik sayı olacak şekilde n = pq, nerede p ve q öyle büyük asallardır p ≡ 3 mod 4, q ≡ 3 mod 4 ve düşmana karşı gizli tutuldu. Sorun hesaplamaktır z verilen a öyle ki a ≡ z² mod n. Tuzak kapısı çarpanlara ayrılmıştır n. Trapdoor ile çözümler z olarak verilebilir cx + dy, cx - dy, - cx + dy, - cx - dy, nerede a ≡ x² mod p, a ≡ y² mod q, c ≡ 1 mod p, c ≡ 0 mod q, d ≡ 0 mod p, d ≡ 1 mod q. Görmek Çin kalıntı teoremi daha fazla ayrıntı için. Asalların verildiğine dikkat edin p ve q, bulabiliriz x ≡ a^(p+1)/4 mod p ve y ≡ a^(q+1)/4 mod q. İşte koşullar p ≡ 3 mod 4 ve q ≡ 3 mod 4 çözümlerin x ve y iyi tanımlanabilir.^[7]

Ayrıca bakınız

Tek yönlü işlev

Notlar

^ Ostrovsky, s. 6-9
^ Pass's Notes, def. 56.1
^ Goldwasser'in ders notları, def. 2.16
^ Ostrovsky, s. 6-10, def. 11
^ Pass'ın notları, def 56.1; Dodis'in def 7, ders 1.
^ Goldwasser'in ders notları, 2.3.2; Lindell'in notları, s. 17, Örn. 1.
^ Goldwasser'in ders notları, 2.3.4

Referanslar

Diffie, W.; Hellman, M. (1976), "Kriptografide yeni yönler" (PDF), Bilgi Teorisi Üzerine IEEE İşlemleri, 22 (6): 644–654, CiteSeerX 10.1.1.37.9720, doi:10.1109 / TIT.1976.1055638
Geç, Rafael, Kriptografi Kursu (PDF), alındı 27 Kasım 2015
Goldwasser, Shafi, Kriptografi Üzerine Ders Notları (PDF), alındı 25 Kasım 2015
Ostrovsky, Rafail, Kriptografinin Temelleri (PDF), alındı 27 Kasım 2015
Dodis, Yevgeniy, Kriptografiye Giriş Ders Notları (Güz 2008), alındı 17 Aralık 2015
Lindell, Yehuda, Kriptografinin Temelleri (PDF), alındı 17 Aralık 2015

[1] Ostrovsky, s. 6-9

[2] Pass's Notes, def. 56.1

[3] Goldwasser'in ders notları, def. 2.16

[4] Ostrovsky, s. 6-10, def. 11

[5] Pass'ın notları, def 56.1; Dodis'in def 7, ders 1.

[6] Goldwasser'in ders notları, 2.3.2; Lindell'in notları, s. 17, Örn. 1.

[7] Goldwasser'in ders notları, 2.3.4

[1]

[2]

[3]

[4]

[5]

[6]

[7]