AYRIK LOGARİTMA PROBLEMİ Semiha TURP T.C. BURSA ULUDAĞ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ AYRIK LOGARİTMA PROBLEMİ Semiha TURP https://orcid.org/0000-0002-9851-2009 Doç. Dr. Betül GEZER YÜKSEK LİSANS TEZİ MATEMATİK ANABİLİM DALI BURSA – 2019 Her Hakkı Saklıdır ÖZET Yüksek Lisans Tezi AYRIK LOGARİTMA PROBLEMİ Semiha TURP Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı Danışman: Doç. Dr. Betül GEZER Bu çalışmada ayrık logaritma problemi ve bu problemin çözümleri ele alınmış ve eliptik eğri ayrık logaritma problemini daha kolay bir ayrık logaritma problemine dönüştüren algoritmalar verilmiştir. Birinci bölümünde cebir ve sayılar teorisi ile ilgili temel kavramlar verildikten sonra kriptoloji ile ilgili temel kavramlar üzerinde durulmuştur. İkinci bölümde ayrık logaritma problemi ve bu problemin çözümünde kullanılan çeşitli algoritmalar ele alınmıştır. İlk olarak Diffie ve Hellman anahtar değişimi algoritması ele alınmış ve El-Gamal açık anahtar kriptosistemleri üzerinde durulmuştur. Daha sonra problemin çözümü için çeşitli algoritmalar verilmiştir. Üçüncü bölümde eliptik eğriler ve eliptik eğri ayrık logaritma problemi ele alınmıştır. Bu bölümde ise eliptik eğri ayrık logaritma problemini bir ayrık logaritma problemine dönüştüren algoritmalar verilmiştir. Dördüncü bölümde ise bir eliptik eğrinin bölüm polinomları kavramı kullanılarak benzer algoritmalar verilmiştir. Anahtar Kelimeler: Açık anahtar kriptolojisi, ayrık logaritma problemi, eliptik eğriler. 2019, vii + 85 sayfa. i ABSTRACT MSc Thesis THE DISCRETE LOGARITHM PROBLEM Semiha TURP Bursa Uludağ University Graduate School of Natural and Applied Sciences Department of Mathematics Supervisor: Doç. Dr. Betül GEZER In this work, the discrete logarithm problem and solutions of this problem are disscused and the algorithms are given to reduce the elliptic curve discrete algorithm problem to an easier discrete logartihm problem. In the first chapter, some fundamental concepts on the theory of algebra and number theory and cryptography are given. In the second chapter, the discrete logarithm problem and the algorithms that used for the solutions of this problem are disscused. Firstly, Diffie and Hellman key exchange algorithm is considered and the El-Gamal public key cryptosystem is discussed. Then some algorithms are given for solving the discrete logarithm problem. In the third chapter, elliptic curves and elliptic curve discrte logarithm problem are considered. In this chapter, some algorithms are given to reduce the elliptic curve discrete algorithm problem to a discrete logartihm problem. In the fourth chapter, similar algorithms are given by using the division polynomials of an elliptic curve. Key words: The public key cryptology, the discrete logarithm problem, elliptic curves. 2019, vii + 85 pages. ii İÇİNDEKİLER Sayfa ÖZET ........................................................................................................................... i ABSTRACT ................................................................................................................ ii TEŞEKKÜR ................................................................................................................ iii İÇİNDEKİLER ............................................................................................................ iv ŞEKİLLER DİZİNİ ..................................................................................................... v SİMGELER ve KISALTMALAR DİZİNİ ................................................................. vi ÇİZELGELER DİZİNİ ................................................................................................ vii 1. GİRİŞ ....................................................................................................................... 1 1.1. Cebir ve Sayılar Teorisi ile İlgili Temel Kavramlar ............................................. 1 1.2. Hızlı Kuvvet Algoritması ..................................................................................... 4 1.3. Simetrik ve Asimetrik Şifreler .............................................................................. 7 2. KURAMSAL TEMELLER VE KAYNAK ARAŞTIRMASI ................................ 18 2.1. Ayrık Logaritma Problemi ................................................................................... 18 2.2. Diffie-Hellman Anahtar Değişimi ........................................................................ 23 2.3. ElGamal Açık Anahtar Kriptosistemi .................................................................. 26 2.4. Ayrık Logaritma Problemi İçin Bir Çarpışma Algoritması ................................. 30 2.5. Pollard’ın  Algoritması ...................................................................................... 33 2.6. Pohlig-Hellman Algoritması ................................................................................ 37 2.7. Fp deki Ayrık Logaritma Problemini Hesaplamak İçin İndeks Hesabı Yöntemi ........... 43 3. MATERYAL VE YÖNTEM .................................................................................. 48 3.1. Eliptik Eğriler ...................................................................................................... 48 3.2. Bir Eliptik Eğrinim Bölüm Polinomları ............................................................... 51 3.3. Eliptik Eğri Üzerinde Bölenler ............................................................................. 53 3.4. Sonlu Cisimler Üzerinde Tanımlı Eliptik Eğriler ................................................ 54 3.5. Eliptik Eğri Ayrık Logaritma Problemi ............................................................... 56 3.6. İkiye Katlama ve Toplama Algoritması ............................................................... 58 3.7. EEALP Ne Kadar Zordur? ................................................................................... 62 3.8. Eliptik Eğri Kriptolojisi ....................................................................................... 63 3.9. Eliptik ElGamal Açık Anahtar Kriptosistemi ...................................................... 67 3.10. Weil Eşleştirmesi ............................................................................................... 69 3.11. Gömme Derecesi ve MOV Algoritması ............................................................ 73 4. BULGULAR VE TARTIŞMA ............................................................................... 77 4.1. Eliptik Eğrilerle Eşleşen Diziler ve Eliptik Eğri Ayrık Logaritma Problemi ...... 77 5. SONUÇ .................................................................................................................... 82 KAYNAKLAR ............................................................................................................ 83 ÖZGEÇMİŞ ................................................................................................................. 85 iv SİMGELER ve KISALTMALAR DİZİNİ Simgeler Açıklama K anahtarların uzayı der(D) bir D böleninin derecesi sum(D) bir D böleninin toplamı O bir eliptik eğri üzerindeki sonsuzdaki nokta E[m] bir E eliptik eğrisinin m-büküm alt grubu em bir eliptik eğri üzerindeki Weil eşleştirmesi E(F) bir F cismi üzerinde tanımlı E eliptik eğrisi üzerindeki noktalar grubu µm birimin m. ilkel köklerinin grubu O(g(x)) büyük-O gösterimi M düz metin mesajlarının uzayı div(f) f fonksiyonunun böleni tp Frobenius endomorfizminin izi logg(h) g tabanına göre h elemanının ayrık logaritması Zm m modülüne göre kalan sınıflarının kümesi Fp p bir asal sayı olmak üzere p elemanlı sonlu cisim F kp p bir asal sayı olmak üzere pk elemanlı sonlu cisim logP(Q) Q noktasının P noktasına göre eliptik ayrık logaritması C şifreli metinlerin uzayı e veya ek şifreleme fonksiyonu d veya dk şifre çözme fonksiyonu Z, Q, R, C tamsayılar, rasyonel sayılar, gerçel ve karmaşık sayılar kümeleri π(X) 2 ve X arasındaki asal sayıların sayısı ψ(X, B) 2 ve X arasındaki B-düzgün tamsayıların sayısı Kısaltmalar Açıklama ALP Ayrık logaritma problemi DHP Diffie-Hellman problemi EEALP Eliptik eğri ayrık logaritma problemi MOV Menezes, Okamoto, Vanstone RSA Rivest, Shamir ve Adleman SEA Schoof, Elkies, Atkin v ŞEKİLLER DİZİNİ Sayfa Şekil 2.1. Pollard’ın  algoritmasındaki x0 ın yörüngesi ............................................ 33 vi ÇİZELGELER DİZİNİ Sayfa Çizelge 1.1…………………………………................................................................ 5 vii 1. GİRİŞ Bu bölümde ayrık logaritma problemi teorisinde kullanılacak temel kavramlar ve teoremler ele alınacaktır. 1.1. Cebir ve Sayılar Teorisi ile İlgili Temel Kavramlar Bu kısımda kriptolojide kullanılan cebir ve sayılar teorisi ile ilgili bazı temel kavram ve teoremler ele alınacaktır. İlk olarak kriptolojide sonlu cisimlerin kullanılması durumunda karşılaşılan temel kavramlar ele alınacak, daha sonra modül kavramı üzerinde durulacaktır. Aşağıda sayılar teorisinin en temel teoremlerinden biri verilmektedir. 1.1.1. Fermat’nın Küçük Teoremi. p bir asal sayı ve a herhangi bir tamsayı olmak üzere p ‒ 1 1 (mod p), p | aa ≡  0 (mod p), p | a dir (Fraleigh 2003). 1.1.2. Uyarı. Kısım 1.2 ele alınacak olan hızlı kuvvet alma algoritması ve Teorem 1.1.1, herhangi bir a  Fp sayısının p modülüne göre tersinin hesaplanmasında oldukça kolaylık sağlar. Gerçektende, Fermat’nın Küçük Teoremi gereği, ap ‒ 2 sayısı a sayısının çarpımı p modülüne göre 1’e denk olduğundan a‒1 ≡ ap ‒ 2 (mod p) dir.   1 Fermat’nın Küçük Teoremi’ne göre, p | a ise ap ‒ 1 ≡ 1 (mod p) dir. Bununla birlikte, herhangi bir a tamsayısının p modülüne göre 1’e denk olan daha küçük kuvvetleri bulunabilir. ak ≡ 1 (mod p) olacak şekilde en küçük k ≥ 1 tamsayısına a sayısının p modülüne göre mertebesi denir. 1.1.3. Önerme. p bir asal sayı, a bir tamsayı ve p | a olmak üzere an ≡ 1 (mod p) olsun. Bu durumda a sayısının p modülüne göre mertebesi n sayısını böler. Özel olarak a sayısının mertebesi p ‒ 1 sayısını böler (Fraleigh 2003). Cebir ve sayılar teorisinden de hatırlanacağı gibi, Fp bir sonlu cisim ise F *p   = Fp\{0} grubu bir devirli gruptur. Aşağıda bu devirli grubun üretecine özel bir isim verilecektir.   1.1.4. Tanım. F * p devirli grubunu üreten g  F * p elemanlarına Fp sonlu cisminin ilkel kökleri denir. Tanıma dikkat edilirse g  F *p bir ilkel kök ise g elemanının mertebesi p ‒ 1 dir ve F * p = {1, g, g2, g3, …, gp‒ 2} dir. Bilindiği üzere her bir abelyen G grubuna Z üzerinde bir “vektör uzayı” olarak bakılabilir. Vektör uzayı tanımındaki F cisminin yerine bir R halkasının alınması halinde elde edilen cebirsel yapıya “R halkası üzerinde bir vektör uzayı” denir veya bu ifade yerine “R halkası üzerinde bir modül” ifadesi kullanılır. Buradan anlaşıldığı gibi modül kavramı vektör uzayı kavramının bir genellemesidir. Vektör uzayı ile ilgili kavramların birçoğu modüller için de geçerlidir. Bu nedenle modüller de cebir ve matematiğin birçok dalında kullanılan önemli cebirsel yapılarından birisidir.   2 1.1.5.Tanım. R bir halka, (M, +) bir değişmeli grup ve  : R × M → M olmak üzere, her r, s  R ve her α, β  M için M1. rα  M, M2. r(α + β) = rα + rβ, M3. (r + s)α = rα + sα, M4. (rs)α = r(sα) koşulları gerçekleniyorsa (R M, +, ) cebirsel yapısına bir sol R- modül denir ve kısaca R M ile gösterilir. Eğer R birimli halka ve her α  M için 1α = α ise R M modülüne bir birimli sol R-modül denir. 1.1.6. Tanım. M ve N, R-modül olmak üzere T: M → N dönüşümü her m, n  M ve her r  R için T(m + n) = T(m) + T(n), T(rm) = rT(m) koşullarını gerçekliyorsa T dönüşümüne bir R-modül homomorfizmi veya kısaca R- homomorfizmi denir. 1.1.7. Uyarı 1. M ve N birer vektör uzayı, yani R bir cisim ise R-modül homomorfizmine R-lineer dönüşüm denir. 2. Bundan başka her m, n  M ve her r, s  R için, T(rm + sn) = r T(m) + s T(n) koşulu gerçekleniyorsa T dönüşümü bir R-modül homomorfizmidir. 1.1.8. Tanım. M bir R-modül ve S  M olsun. ri  R ve mi  S olmak üzere   3 r1m1 + … + rkmk biçimindeki tüm lineer birleşimlerin ailesi S kümesini bulunduran en küçük alt modüldür. Bu modüle S  M kümesi ile üretilen alt modül denir ve bu küme ile gösterilir. Eğer = M ise M R-modülüne S kümesi ile üretilmiş modül veya S kümesine M R- modülünün üreteç kümesi denir. Eğer M R-modülünün üreteç kümesi sonlu bir küme ise M R-modülüne sonlu üreteçli modül denir. 1.1.9. Tanım. S kümesi M R-modülünün bir üreteç kümesi ve üstelik S kümesi lineer bağımsız ise S kümesine M R-modülünün bir bazı ve bir bazı olan M R-modülüne de serbest modül denir. 1.2. Hızlı Kuvvet Algoritması RSA ve Diffie-Hellman gibi bazı şifreleme sistemlerinde bir g sayısının modülo N ye göre çok büyük kuvvetlerinin hesaplanması gerekmektedir. Burada N, yüzlerce basamağı olan bir sayı olabilir. A herhangi bir sayı olmak üzere, gA değerini hesaplamanın bir yolu bulunan her sayıyı g sayısı ile tekrar çarpmaktır. Böylece g1  g (mod N), g2  g‧g1 (mod N), g3  g‧g2 (mod N), g4  g‧g3 (mod N), … dir. Buna göre, gA ≡ gA (mod N) dir, ancak A çok büyük bir sayı, örneğin, A ≈ 21000 ise bu yöntemle hesapla yapmak dünyanın yaşından daha fazla zaman alır. Bu nedenle gA (mod N) değerini hesaplamak için kullanışlı ve daha hızlı bir yol kullanmak gerekir. Aşağıda ele alınacak hızlı kuvvet algoritmasına göre, N modülüne göre gA sayısını, arka arkaya kare alma ve çarpma işlemleri kullanarak hesaplamak için A sayısının ikili açılımı kullanır. Bu algoritmayı vermeden önce aşağıdaki örneği inceleyelim.   4 1.2.1. Örnek. 3218 (mod 1000) değerini hesaplamak için 218 sayısı 2 nin kuvvetlerinin bir toplamı olarak 218 = 2 + 23 + 24 + 26 + 27 biçiminde yazılabilir. Böylece 3218 sayısı 218 223242627 2 23 24 26 73 = 3 = 3 ‧ 3 ‧ 3 ‧ 3 ‧3 2 2 3 4 olarak yazılabilir. Dikkat edilirse 32, 3 2 , 3 2 , 3 2 , … dizisindeki değerlerin her biri bir önceki değerin karesi olduğundan bu dizideki her bir terimi hesaplamak oldukça kolaydır. Üstelik bu değerler modülo 1000’e göre hesaplanacağından üç basamaktan daha fazla depolama alanına ihtiyaç yoktur. Aşağıdaki tabloda modülo 1000 e göre 3 7 7 sayısının 32 kadar olan kuvvetleri hesaplanmıştır. 3 2 = 3218 sayısının büyük bir kuvveti olduğu halde her bir değer bir önceki değerin karesi olduğundan bu tabloyu oluşturmak için sadece yedi tane çarpma işlemi yapılmıştır. Çizelge 1.1. 1000 modülüne göre 3 sayısının kuvvetleri (Hoffstein ve ark. 2008) i 0 1 2 3 4 5 6 7 i 32 (mod 1000) 3 9 81 561 721 841 281 961 Yukarıdaki çizelgedeki değerlerden ihtiyaç duyulanlar kullanarak 3 4 6 3218 ≡ 32 ‧ 3 2 ‧ 3 2 ‧ 3 2 ‧3 2 7 ≡ 9 ‧ 561 ‧ 721 ‧ 281 ‧ 961 (mod 1000) ≡ 489 (mod 1000) olarak bulunur. Dikkat edilirse 9‧561‧721‧281‧961 çarpma işlemi yapılırken her çarpma işleminden sonra 1000 modülüne göre indirgeme yapılarak büyük sayıların oluşumu engellenmiş ve 3218 (mod 1000) değeri hesaplanırken sadece 11 tane çarpma işlemi yapılmıştır.   5 Bu yöntem Hızlı Kuvvet Algoritması veya Kare ve Çarpım Algoritması olarak adlandırılır. 1.2.2. Algoritma. 1. Ar = 1 olduğunu varsayalım ve A0, A1, A2, …, Ar  {0, 1} olmak üzere A sayısının A = A + A ‧ 2 + A ‧ 22 + A ‧ 23 + … + A ‧ 2r0 1 2 3 r ikili açılımını hesapla. 2. 0 ≤ i ≤ r için ardışık kare alma işlemi yaparak g 2i (mod N) değerlerini, yani a0 ≡ g(mod N), a1 ≡ a 2 ≡ g2 0 (mod N) , 2 a 2 22 ≡ a 1 ≡ g (mod N),  r a 2r ≡ a r1 ≡ g 2 (mod N) değerlerini hesapla. 3. gA = g A0A 2 r 12A22 Ar 2 = g A0 (g 2 ) A1 ‧(g 22 ) A2 ‧(g 23 ) A r 3 …(g 2 )Ar ≡ a A0 0 ‧ a A1 1 ‧ a A2 2 ‧ a A3 3 … a Ar r (mod N) eşitlik ve denkliği kullanarak gA(modN) değerini hesapla. Dikkat edilirse a0, a1, …, ar değerleri 2. adımda hesaplanmışlardır, doğal olarak A0, …, Ar  {0, 1} olduğundan bu çarpımda sadece kuvvetleri 1 olan ai değerleri dikkate alındığından fazladan en çok r tane daha çarpma işlemi söz konusudur. Dolayısıyla gA(modN) değerini hesaplamak için en çok 2r tane çarpma işlemi gerekir. A ≥ 2r olduğundan gA(modN) değerini hesaplamak için en çok 2log2(A) çarpma işlemi yapıldığı görülür. Eğer A sayısı çok büyük bir sayı, örneğin, A ≈ 21000 ise bir bilgisayarın yaklaşık 2000 çarpma işlemi yaparak 2A(modN) değerini hesaplaması oldukça kolaydır.   6 1.3. Simetrik ve Asimetrik Şifreler Bir A kişisinin bir B kişisine gizli bir mesaj göndermek istediğini varsayalım. A kişisi m düz metin mesajını şifreleyerek bir c şifreli metnine çevirmek için gizli bir k anahtarı kullanır. B kişisi c şifreli metnini aldıktan sonra bu metni deşifre etmek ve m düz metin mesajını yeniden oluşturmak için k gizli anahtarını kullanır. Eğer bu yöntem düzgün çalışıyorsa A ve B kişileri k gizli anahtarına sahiptirler. Üstelik bu sistem güvenli ise A ve B kişileri dışında başka bir C kişisinin k gizli anahtarını bilmemesi, tahmin edememesi ve k gizli anahtarını bilmeden c şifreli metninden m düz metnini elde edememesi gerekir. Bu kısımda “kriptosistem” kavramı soyut matematiksel terimlerle ifade edilecektir. Böylece değişik sistemler arasındaki benzerlikler ve farklılıklar vurgulanırken aynı zamanda bir şifreleme sisteminin çeşitli saldırılara karşı güvenliği incelenecektir. Simetrik Şifreler Simetrik şifreleme yönteminde A ve B kişilerinin gizli k anahtarını paylaşmaları gerekir. Çünkü bu gizli anahtarı kullanarak mesajları hem şifreleyip hem de şifrelerini çözebilirler. Böylece A ve B kişileri eşit (veya simetrik) bilgi ve yeteneklere sahip olurlar. Bu nedenle bu tür şifrelere simetrik şifreler adı verilir. Matematiksel olarak, bir simetrik şifre olası anahtarların bulunduğu K uzayından bir k anahtarı seçerek olası mesajların bulunduğu M uzayından seçilen bir düz m mesaj metnini şifreler. Dolayısıyla düz m metninin k anahtarı ile olası şifrelenmiş mesajların bulunduğu C uzayından bir c şifreli mesajı elde edilmiş olur. Böylece K × M, k anahtarı ve m düz metninden oluşan (k, m) çiftlerinin ve C, şifreli metinlerin kümesi olmak üzere simetrik şifreleme işlemi   7 e : K × M → C biçiminde bir fonksiyon olarak düşünülebilir. Benzer şekilde şifreli metni çözme fonksiyonu da d : K × C → M biçiminde tanımlanır. Dolayısıyla c şifreli metnini çözerek m düz metni elde edilmek istendiğinden bu durum matematiksel olarak her k  K, her m  M için d(k, e(k, m)) = m biçiminde ifade edilir. Genellikle bu işlemler, k bir alt indis olarak alınarak her bir k anahtarı ve her m  M için dk(ek(m)) = m olacak biçimde ek : M → C ve dk : C → M fonksiyonları ile ifade edilir. Dikkat edilirse her k anahtarı için dk fonksiyonu ek fonksiyonunun tersidir, ek(m) = ek(m) ise m = dk(ek(m)) = dk(ek(m)) = m olduğundan ek bir birebir fonksiyondur. A ve B kişilerinin C kişisinin de kullanılan şifreleme yöntemini bildiğini varsaymaları A ve B kişileri için en güvenli yoldur. Matematiksel olarak, C kişisinin de e ve d fonksiyonlarını bildiği fakat A ve B kişilerinin kullandığı k özel anahtarını bilmediği anlamına gelir. Örneğin, A ve B kişileri basit bir yer değiştirme şifreleme tekniği kullanıyorlarsa C kişisinin de bu gerçeğin farkında olduğunu varsaymaları gerekir. Dolayısıyla bir şifreleme sisteminin güvenliği, kullanılan şifreleme algoritmasının gizliliğinden daha çok kullanılan anahtarın gizliliğine bağlıdır. Bu anlayış modern kriptolojide Kerckoff Prensibi olarak isimlendirilir. Eğer (K, M, C, e, d) işleyen, güvenilir bir şifre ise bu şifre aşağıdaki özelliklere sahip olmalıdır:   8 1. Her k  K anahtarı ve her m  M düz metni için ek(m) şifreli metnini hesaplamak kolay olmalıdır. 2. Her k  K anahtarı ve her c  C şifreli metni için dk(c) düz metnini hesaplamak kolay olmalıdır. 3. k  K anahtarı kullanılarak şifrelenmiş olan bir veya daha fazla c1, c2, …, cn  C şifreli mesajları verildiğinde bunlara karşılık gelen dk(c1), dk(c2), …, dk(cn) düz metinlerinin k anahtar bilgisi olmadan hesaplanması çok zor olmalıdır. 4. Bir veya daha fazla (m1, c1), (m2, c2), …, (mn, cn) düz metin ve bunlara karşılık gelen şifreli metin çiftleri için bu listede bulunmayan herhangi bir c şifreli metnin k anahtarı bilinmeden çözülmesi zor olmalıdır. Bu bilinen bir düz metin saldırısına karşı güvenlik özelliğidir. 5. C kişisi tarafından seçilmiş olan düz metinlerin herhangi m1, m2, …, mn  M listesi için karşılık gelen ek(m1), ek(m2), …, ek(mn) şifreli metinleri bilinse bile k anahtarı bilinmeksizin herhangi bir c şifreli metnini çözümlemek çok zor olmalıdır. Bu seçilmiş bir düz metin saldırısına karşı güvenlik özelliğidir. 1.3.1.Örnek. Basit bir yer değiştirme şifreleme tekniği yukarıda belirtilen 4.özelliğe sahip değildir. Çünkü bir tek (m, c) düz metin/şifreli metin çifti bile şifreleme tekniğinin çoğunu ortaya çıkarır. Bu nedenle basit bir yer değiştirme şifreleme tekniği bilinen düz metin saldırılarına karşı oldukça savunmasız bir şifreleme tekniğidir. Kodlama Şemaları Bir şifreleme sisteminde anahtarları, düz metinleri, şifreli metinleri birer sayı olarak ifade etmek ve bu sayıları da ikilik sistemde yazmak uygundur. Örneğin, bir bit 0 veya 1 olmak üzere, 0 dan 255 e kadar verilen sayılar 8 bitlik dizgiler halinde a = 00000000, b = 00000001, c = 00000010, … , z = 00011001   9 biçiminde alfabetik harflerin gösterilmesi için kullanılabilir. Küçük harfleri büyük harflerden ayırmak için A = 00011011, B = 00011100, … olarak alınabilir. Böylece bu kodlama yöntemi 256 tane farklı sembolün ikilik sisteme çevrilmesine olanak tanır. Birçok bilgisayar verileri depolamak için yukarıdakine benzeyen ve adına ASCII kodlama denen bir kodlama sistemi kullanır. Bu kodlama sisteminin bir kısmı aşağıda görülmektedir. Örneğin, “Bed bug.” ifadesi boşluk ve noktalama dahil olmak üzere ASCII koduna göre B e d b u g . 66 101 100 32 98 117 103 46 01000010 01100101 01100100 00100000 01100010 01110101 01100111 00101110 biçiminde şifrelenir ve böylece bilgisayar tarafından 0100001001100101011001000010000001100010011101010110011100101110 biçimindeki bir bit dizgisi biçiminde görür. 1.3.2. Tanım. Bir veri türünü başka bir veri türüne dönüştürme yöntemine kodlama şeması denir. Örneğin, bir metni sayılara dönüştürmek bir kodlama şeması ile gerçeklenir. Kodlama şeması ile şifreleme şemalarının birbirlerinden farklı olmaları gerekir. Bir kodlama şemasının tamamen kamuya açık olduğu ve herkes tarafından aynı amaçlar için kullanıldığı varsayılır. Şifreleme şemaları ise gizli anahtara sahip olmayan herhangi birinden bilgi gizlemek için tasarlanırlar. Bu nedenle bir kodlama şeması bir şifreleme şemasında olduğu gibi bir kodlama fonksiyonu ve bu fonksiyonun tersi olan kodlamayı çözme (decoding) fonksiyonundan oluşur. Bununla birlikte bir kodlama şeması için her iki fonksiyon da kamuya açıktır ve hesaplaması hızlı ve kolaydır.   10 Bir kodlama şeması kullanılarak bir düz metin veya bir şifreli metin her bir blok sekiz bit olmak üzere sekizli bloklar halinde ifade edilebilir. Sekiz bitlik bir bloğa bir byte adı verilir, yani bir byte, 0 ile 255 arasında onluk sistemdeki bir sayı ile veya 00 ile FF arasında onaltılık sistemdeki ikililer ile ifade edilir. Bilgisayarlar genellikle bir zamanda bir seferde birden fazla byte işlem yapar. Örneğin, 64 bitlik bir işlemci bir zamanda her seferinde sekiz byte işlem yapar. Kodlanmış Blokların Simetrik Şifrelenmesi Daha önce de belirtildiği gibi bir kodlama şeması kullanılırken M düz metin mesajlarının uzayının sabit bir B uzunluğundaki dizgilerden, yani tam olarak B tane 0 ve 1 rakamlarından oluşan dizgilerden oluşur. Buradaki B sayısına şifrenin blok boyutu denir. Böylece genel bir düz metin mesajı, M uzayından seçilen mesaj bloklarının bir listesinden ibarettir ve şifreleme fonksiyonu, bu mesaj bloklarını her bloğu B bitlerin bir dizisi olan C uzayındaki bir şifreli metin blokları listesine dönüştürür. Eğer bu düz metin mesajı B bitten daha az bir blokla bitiyorsa bloğun sonu sıfırlarla biter. Orijinal düz metin mesajını M kümesinde bitlerin bloklarının bir dizisine dönüştüren bu kodlama işlemi kamuya açıktır. Şifreleme ve şifre çözme her seferinde bir blok için yapıldığından bu işlemi bir tek düz metin mesajı, yani bir tek m  M için çalışmak yeterlidir. Dolayısıyla bir mesajı bloklara bölmek oldukça kullanışlıdır. Bir mesaj keyfi uzunlukta olabildiğinden şifreleme işlemini bir tek sabit uzunlukta parça üzerinde yapmak kolaylık sağlar. m düz mesaj metin bloğu bir B bitlerin dizgisidir ve bu dizgi ikili formda bir sayı ile özdeşleştirilir. Diğer bir deyişle, M uzayı, 0 ≤ m < 2B özelliğindeki m tamsayılarının kümesi ile mB1 m ...m B1 B2 2 1 0 B22m1m0 ↔ mB1 2 mB2 2  ...m2 2  2  2 m1 m0  m sayısının B bitlerinin listesi 0 ve 2B ‒ 1 arasındaki tamsayılar biçiminde özdeşleştirilir. Burada m0, m1, …, mB‒ 1 sayılarının her biri 0 veya 1 dir.   11 Benzer şekilde, K anahtar uzayı ve C şifreli metin uzayı, belirli bir blok uzunluğundaki bit dizgilerinin tamsayı kümeleri ile özdeşleştirilir. Eğer anahtarlar, düz metin mesajları ve şifreli metin mesajları sırasıyla Bk, Bm ve Bc olarak gösterilirse K, M, C uzayları K = {k Z| 0 ≤ k < 2 Bk } M = {m Z| 0 ≤ m < 2 Bm } C = {c Z | 0 ≤ c < 2 Bc } biçiminde pozitif tamsayıların kümesi ile özdeşleştirilir. Böylece çok önemli bir soru ortaya çıkar: “A ve B kişileri K kümesini ne kadar büyük yapmalıdır?” veya denk olarak, “Bk anahtar bloğunu ne kadar büyük seçmelidir?” Eğer Bk çok küçükse, bir C kişisi A ve B kişilerinin gizli anahtarını bulana kadar 0 ile 2 Bk ‒ 1 arasındaki her sayıyı kontrol edebilir. Daha kesin olarak, C kişisinin d şifre çözme algoritmasını bildiği kabul edildiğinden C kişisi her bir k  K anahtarını alarak dk(c) yi hesaplamak için kullanır. C kişisinin geçerli ve geçersiz düz metin mesajları arasında ayrım yapabildiği varsayılırsa C kişisi bu işlemin sonucunda mesajı ele geçirir. C kişisi anahtar uzayında geniş kapsamlı bir arama yaptığından bu saldırı kaba kuvvet saldırısı olarak adlandırılır. Diğer yandan şimdiki teknoloji ile anahtar uzayının en az 280 elemana sahip olduğunda kapsamlı bir araştırmanın olanaksızdır. Böylece A ve B kişileri Bk değerini 80 sayısından büyük seçmelidirler. Simetrik Şifrelerin Örnekleri p büyük bir asal sayı, yani 2159 < p < 2160 olmak üzere A ve B kişilerinin K anahtar uzayını, M düz metin mesaj uzayını ve C şifreli metin mesaj uzayını Fp sonlu cismindeki birimlerin kümesini, yani K = M = C = {1, 2, … , p ‒ 1} = F * p olarak aldıklarını varsayalım.   12 A ve B kişileri rastgele bir k  K anahtarı seçerler, yani 1 ≤ k < p özelliğinde bir k tamsayısı seçerler ve ek(m) ≡ k ‧ m (mod p) (1.1) biçiminde tanımlana ek şifreleme fonksiyonunu kullanmaya karar verirler. Buna karşılık gelen dk şifre çözme fonksiyonu, k, p modülüne göre k sayısının tersi olmak üzere dk(c) ≡ k ‧ c (mod p) dir. Dikkat edilirse, p çok büyük bir asal sayı olduğu halde genişletilmiş Öklid Algoritması ile k sayısı, 2log2p adımdan daha az adımda hesaplanabilir. Böylece k değerinden k değerini elde etmek kriptolojide “kolay” sayılır. Seçilebilecek yaklaşık 2160 olasılık var olduğundan bir C kişisinin k gizli anahtarını tahmin etmesi zordur. Üstelik C kişisi c şifreli metnini bilse bile k gizli anahtarını ele geçirmesi zordur. Dikkat edilirse ek : M → C şifreleme fonksiyonu herhangi bir k anahtarının seçimi için örtendir. Dolayısıyla her c  C ve herhangi bir k  K için ek(m) = c olacak şekilde bir m  M vardır. Ayrıca verilen herhangi bir şifreli metin, uygun bir anahtarla şifrelenmesi şartıyla herhangi bir düz metni temsil edebilir. Matematiksel olarak, bu herhangi bir c  C şifreli metin ve herhangi bir m  M düz metin verildiğinde ek(m) = c olacak şekilde bir k anahtarının var olduğunu ifade eder. Özellikle bu k ≡ m‒1 ‧ c (mod p) (1.2) anahtarı için de geçerlidir. Bu, A ve B kişilerinin şifrelerinin daha önce bahsedilen 1., 2. ve 3. özelliklerine sahip olduğunu gösterir. Gerçekten de, k anahtarını bilen herkes şifreleme ve şifre çözme işlemlerini kolayca yapabilir. Ancak k değerini bilmiyorsa şifre çözmek zordur. Bununla birlikte, bir tek bir düz metin/şifreli metin çifti (m,c) bile bir C kişisinin (1.2) denkliğini kullanarak k özel anahtarını bulmasına olanak sağladığından bu şifre 4. özelliğe sahip değildir.   13 Ayrıca A ve B kişileri şifreleme fonksiyonlarını ek(m) = k ‧ m olarak tanımlarsa bu şifre, yine 1. ve 2. özelliği gerçeklerken 3. özelliği gerçeklemez. Eğer C kişisi tek bir c = k ‧ m şifreli metnini çözmeyi denerse bile bir büyük sayının çarpanlarına ayırma işlemi ile karşıya kalır. Bununla birlikte C kişisi c1, c2, …, cn gibi birkaç şifreli metin elde edebilirse obeb(c1, c2, … ,cn) = obeb (k ‧ m1, k ‧ m2 , … , k ‧ mn) = k ‧(m1, m2 ,…, mn) olarak yazılabilir. Dikkat edilirse en büyük ortak bölen bulma işlemi kolaydır. Yukarıdaki örneğe göre p modülüne göre indirgeme işleminin bölünebilirlik gibi özellikleri yok eden bir “karıştırma” etkisi vardır. Bununla birlikte (1.1) şifresi bilinen bir düz metin saldırısına karşı savunmasız olduğundan sadece p modülüne göre indirgeme işlemi yapmak yeterli değildir. Eğer C kişisi hem şifreli metin hem de buna karşılık gelen m düz metnini elde ederse k ≡ m‒1 ‧ c (mod p) değerini hesaplayarak anahtara kolayca ulaşabilir. Böylece tek bir düz metin/şifreli metin çifti bile anahtarı bulmak için yeterlidir. Dolayısıyla (1.2) şifreleme fonksiyonu da 4. özelliğe sahip değildir. Yukarıda ele alınmış olan “çarpma-p modülüne göre indirgeme” şifresinin değişik versiyonları vardır. Örneğin, ek(m) ≡ m + k (mod p) ve dk(c) ≡ c ‒ k (mod p) biçiminde verilen “toplama-p modülüne göre indirgeme” şifresi bunlardan birisidir. Bir başka versiyon, değiştirme şifresi ve çarpma şifresinin bileşimiyle oluşan afin şifredir. denir. Bir afin şifresi için bir k anahtarı k = (k1, k2) biçiminde iki tamsayıdan oluşur ve k1, p modülüne göre k1 değerinin tersi olmak üzere şifreleme ve şifreyi çözme fonksiyonları ek(m) = k1 ‧ m + k2 (mod p)   14 dk(c) = k1‧ (c ‒ k2) (mod p) (1.3) olarak tanımlanır. Afin şifresinin bir genellemesi m düz metni, c şifreli metni ve k anahtarının ikinci kısmı olan k2 değeri p modülüne göre n sayılarından oluşan sütun vektörleri ile değiştirilerek elde edilir. Bu şifreye Hill şifresi denir. Burada k anahtarının birinci kısmı olan k1 değeri girdileri p modülüne göre tamsayılar olan n  n tipinde bir matris olarak alınır. Bu durumda şifreleme ve şifre çözme fonksiyonları yine (1.3)’ te verildiği gibidir, ancak k1 ‧ m çarpımı bir matris ve bir vektörün çarpımıdır ve k1, p modülüne göre k1’in ters matrisidir. Afin ve Hill şifreleri de bilinen düz metin saldırılarına karşı savunmasızdır. Asimetrik Şifreler Daha önce görüldüğü gibi A ve B kişileri bir simetrik şifre kullanarak mesaj alışverişinde bulunmak isterlerse bir k gizli anahtarı belirlerler. Eğer A ve B kişileri gizli bir kanaldan haberleşirlerse bu şifreleme sistemi iyi olabilir. Ancak bir C kişisi bu kişilerin iletişiminden haberdar ise bu şartlar altında bir gizli anahtar alışverişi yapmak mümkün olabilir mi? Bu sorunun cevabı ilk bakışta hayır olarak düşünüldüğü halde Diffie ve Hellman (1976) bazı koşullar altında bunun mümkün olabileceğini belirtmişlerdir. Bu soruna etkili çözümler aramaya açık anahtar (veya asimetrik) kriptolojisi denir. A kişisinin üst tarafında dar bir yuvası bulunan bir kasası olduğunu ve bu kasayı kamuya açık bir yere koyduğunu varsayalım. Üstelik bu kasanın oldukça güvenilir olduğu herkes tarafından bilinsin. B kişisinin A kişisine bir mesaj yazdığını ve bunu kasanın üst tarafındaki yuvadan içeri attığını düşünelim. Bu durumda sadece kasanın anahtarına sahip olan kişi, yani sadece A kişisi bu mesajı alır ve okur. Bu senaryoda, A kişisinin açık anahtarı kasadır ve şifreleme algoritması mesajı yuvaya koymak, şifreyi çözme algoritması ise anahtarla kasayı açmaktır. Dikkat edilirse bu yöntem gerçek   15 dünyada kullanılmaktadır. Örneğin, bir bankanın bankamatiğinde kullanılan para yatırma yuvaları bu biçimdedir. Bu para yatırma yuvaları güvenli olmalı, bir kişinin yuvayı kullanarak başka insanların mevduatlarına ulaşması mümkün olmamalıdır. Yukarıda söz edilen “yuvalı kasa” kriptosistemi, kasa kamuya açık bir yerde bulunduğundan ve herkesin bu kasayı kullanarak A kişisine şifreli mesajlar gönderebildiğinden oldukça kullanışlıdır. Üstelik A kişisinin iletişime geçtiği her bir kişi için ayrı bir kasa oluşturması gerekmemektedir. Bundan başka A kişisinin kasayı açarak başka kişiler A kişisine mesaj göndermeden önce B kişisinin gönderdiği mesajı silmesi gerekmemektedir. Şimdi bunu matematiksel olarak açıklayalım. Daha önce olduğu gibi, anahtarların bulunduğu bir K uzayı, düz mesajların bulunduğu bir M uzayı ve şifreli mesajların bulunduğu bir C uzayı vardır. Bununla birlikte bir k  K anahtarı k = (köz, kaç) biçiminde adlarına sırasıyla özel anahtar (private key) ve açık anahtar (public key) denilen bir anahtar çiftinden oluşur. Her bir kaç açık anahtarı için ek : M → C aç biçiminde verilen bir şifreleme fonksiyonu ve her bir köz özel anahtarı için dk : C → M öz biçiminde verilen bir şifre çözme fonksiyonu vardır. Eğer k = (köz, kaç)  K ise her m  M için dk (e (m)) = m dir. öz kaç Bir asimetrik şifre güvenli ise bir C kişisi kaç açık anahtarını bilse bile dk şifre çözme öz fonksiyonunu hesaplayamaz. Bu durumda A kişisi bir B kişisine güvenli olmayan bir iletişim kanalından kaç anahtarını gönderebilir ve B kişisi, A kişisine (ek (m)) şifreli aç mesajını gönderir ve bir başka C kişisi bu mesajı çözemez. Bu şifreli mesajın şifresinin   16 kolayca çözümü köz anahtarını kullanmakla mümkündür ki bu anahtarı sadece A kişisi bilmektedir. ek fonksiyonunun tersini hesaplamak için A kişisinin kullandığı köz özel aç anahtarına, kestirme bilgisi (trapdoor information) denir. köz ve kaç anahtarlarının birbirinden farklı olması şifreyi asimetrik yapar.   17 02. KURAMSAL TEMELLER ve KAYNAK ARAŞTIRMASI Ayrık logaritma problemi, şifreleme, anahtar değişimi, dijital imazalar ve belli bir çıktıya sahip fonksiyonlar (hash fonksiyonları) gibi birçok kriptografik yapıda kullanılır. Ayrık logaritma problemine dayanan ilk açık anahtar kriptosistemi Diffie ve Hellman (1976) tarafından “New directions in cryptography” isimli makalede ele alınmıştır. Daha sonraki yıllarda Rivest, Shamir ve Adleman (1978) tarafından güvenilirliği büyük sayıların çarpanlamasına bağlı olan Rivest, Shamir, Adleman kriptosistemleri (RSA kriptosistemleri) ele alınmıştır. Bununla birlikte Diffie ve Hellman, güvenilirliği F *p grubundaki ayrık logaritma probleminin çözümüne dayanan bir anahtar değişim algoritması vermişlerdir. Daha sonra, ElGamal (1985) ayrık logaritma problemine dayanan bir açık anahtar kriptosistemi oluşturulmuştur. Koblitz (1987) ve Miller (1986), ayrık logaritma probleminin çözümünün daha zor olabileceğini düşünerek,  F * p grubu yerine Fp sonlu cismi üzerinde tanımlı eliptik eğri üzerindeki noktaların grubu olan E(Fp) grubunu almışlar ve bu düşünce ışığında eliptik eğri kriptolojisi ortaya çıkmıştır. Bu çalışmada özellikle açık anahtar kriptosistemleri ile ilgili olan ayrık logaritma problemi ele alınacaktır. 2.1. Ayrık Logaritma Problemi Bu kısımda ayrık logaritma problemi tanıtılacak ve bu problemin çözümü için geliştirilmiş çeşitli algoritmalar üzerinde durulacaktır. 2.1.1. Tanım. G bir grup, x, y  G olmak üzere y, x ile üretilen alt grubun bir elemanı olsun. xm = y   18 olacak biçimdeki m  1 tamsayısının bulunması problemine G grubu için ayrık logaritma problemi (ALP) denir. xm = y eşitliğini gerçekleyen en küçük m tamsayısına y elemanının x elemanına göre logaritması (indeksi) denir ve m = logx(y) veya m = indx(y) ile gösterilir. 2.1.2. Uyarı 1. Ayrık logaritma problemi bir G grubu için tanımlandığından bu problemin çözümü bazı gruplar için kolay bazı gruplar için zordur. Örneğin, ayrık logaritma probleminin (Fp, +) grubundaki çözümü oldukça kolaydır. Gerçekten de (Fp, +) grubu için ayrık logaritma problemi, x, y  Fp olmak üzere mx = y olacak biçimdeki m tamsayısının bulunmasıdır ve bu denklemin çözümü için x elemanının Fp cismindeki tersinin belirlenmesi gerekir. x  Fp nin tersinin belirlenmesi ise Euclid algoritması kullanılarak O(log p) zaman alır. Benzer biçimde (Z , +), (R*m , ), (C , ‧) grupları için de bu problem oldukça kolaydır. 2. Bununla birlikte, ALPnin çözümü (F *p , ) grubu için zordur: (F *p , ) grubu için ayrık logaritma problemi x, y  F *p olmak üzere xm = y olacak biçimdeki m tamsayısının belirlenmesidir. Daha sonra görüleceği gibi, O(p) mertebeli bir grupta ayrık logaritma problemi O( p ) adımda çözülebilir. Ancak ayrık logaritma problemini F *p grubunda çözmek için daha hızlı algoritmalar da bulunabilir. F * p grubunda ALPni çözmek için bilinen en iyi algoritma indeks hesabı yöntemidir ve bu algoritma ALPni c belli bir sabit olmak üzere exp(c3 (log p)(loglog p)2 ) zamanda çözer. Bu zaman üstel zamandan daha hızlı fakat polinom zamandan da daha yavaş olduğundan altüstel zaman olarak adlandırılır. 3. Yukarıda da görüldüğü gibi, ayrık logaritma probleminin çözümünde çeşitli algoritmalar kullanılır. Kullanım açısından, ayrık logaritma probleminin üstel bir   19 zamanda çözülebileceği bir G grubu alınır. Bu çalışmada ayrık logaritma problemi özellikle F *p sonlu grubu ve sonlu bir cisim üzerinde tanımlı bir eliptik eğrinin üzerindeki noktaların oluşturduğu E(Fp) grubu için ele alınacaktır. 4. Bir G grubu için verilmiş olan ayrık logaritma problemi, grubun bir sonlu grup olması durumunda aşağıdaki hali alır. 2.1.3. Tanım. g  Fp bir ilkel kök olmak üzere h, Fp cisminin sıfırdan farklı elemanı olsun. gm ≡ h (mod p) olacak biçimdeki m  1 tamsayısının bulunması problemine Fp sonlu cismi üzerinde ayrık logaritma problemi denir. Bu özellikteki m tamsayısına g tabanına göre h elemanının ayrık logaritması denir ve logg(h) ile gösterilir. 2.1.4. Uyarı 1. gm ≡ h (mod p) denkliğini gerçekleyen bir m çözümü var ise sonsuz tane çözüm bulunabilir. Buna göre m, bu denkliğin bir çözümü ise her k  Z için m + k (p  1) de bir çözümdür. Gerçektende, Fermat’nın Küçük Teoremi gereği, gp  1 ≡ 1 (mod p) olduğundan gm + k(p  1) = gm(gp  1)k ≡ h ‧ 1k ≡ h (mod p) dir, yani logg(h) sayısı p  1 modülüne göre tanımlanır. Üstelik logg : F  p  Zp  1 fonksiyonunun iyi tanımlı olduğu kolayca görülebilir. 2. Her a, b  F * p için logg(ab) = logg(a) + logg(b) yani   20 logg(ab) ≡ logg(a) + logg(b) (mod p  1) dir. O halde logg fonksiyonunda klasik logaritma fonksiyonunda olduğu gibi çarpma işlemi toplamaya dönüşür. 2.1.5. Örnek 1. p = 56509 ve g = 2 olmak üzere 2m  38679 (mod 56509) olacak biçimdeki m tamsayısını belirlemek için 2 elemanının 22, 23, 24, … (mod 56509) olacak biçimde tüm kuvvetleri belirlenebilir. Ancak bu yol oldukça zordur. Bununla birlikte bir bilgisayar kullanılarak m = 11235 olduğu görülebilir (J. Hoffstein ve ark. 2008). Aşağıda böyle bir m sayısının belirlenmesi için indeks hesabı yöntemi kullanılmıştır. Bu yöntem Kısım 2.7 de detaylı olarak ele alınacaktır. 2. p = 1217 ve g = 3 olmak üzere 3m ≡ 37 (mod 1217) olacak biçimdeki m sayısını belirlemek için küçük asal sayılardan oluşan adına çarpım tabanı denilen B = {2, 3, 5, 7, 11, 13} kümesini dikkate alalım. İlk olarak 3x ≡  B kümesindeki belli asal sayıların çarpımı (mod 1217) olacak biçiminde x sayılarını belirleyelim. Bu sayılardan bazıları; 31 ≡ 3 (mod 1217) 324 ≡ 22 ‧ 7 ‧ 13 (mod 1217) 325 ≡ 53 (mod 1217) 330 ≡ 2 ‧ 52 (mod 1217) 354 ≡ 5 ‧ 11 (mod 1217) 387 ≡ 13 (mod 1217)   21 biçimindedir. Diğer yandan 3(p1) / 2 ≡ 1 (mod p) olduğundan log3(1) = 608’dir. Dolayısıyla 1 ≡ log3(3) (mod 1216) 24 ≡ 608 + 2log3(2) + log3(7) + log3(13) (mod 1216) 25 ≡ 3log3(5) (mod 1216) 30 ≡ 608 + log3(2) + 2log3(5) (mod 1216) 54 ≡ 608 + log3(5) + log3(11) (mod 1216) 87 ≡ log3(13) (mod 1216) olarak yazılabilir. Birinci denklikten log3(3) ≡ 1 dir. Diğer yandan üçüncü denklikten log3(5) ≡ 819 (mod 1216) ve altıncı denklikten log3(13) ≡ 87 olduğu elde edilir. Böylece dördüncü denklikten log3(2) ≡ 30  608  2 ‧ 819 ≡ 216 (mod 1216) denkliği ve beşinci denklikten log3(11) ≡ 54  608  log3(5) ≡ 1059 (mod 1216) denkliği elde edilir. Son olarak ikinci denklikten log3(7) ≡ 24  608  2log3(2)  log3(13) ≡ 113 (mod 1216) denkliği elde edilir. Yukarıdaki denklikler dikkate alındığında çarpım tabanındaki tüm elemanların ayrık logaritmalarının belirlenmiş olduğu görülür. 3m ≡ 37 (mod 1216) olacak biçimdeki m sayısını bulmak için 3k ‧ 37 (mod p) değeri B kümesindeki asal sayıların çarpımı olarak yazılabileceği bir k değeri seçilir. Böylece k = 16 için 316 ‧ 37 ≡ 23‧ 7 ‧ 11 (mod 1217) olduğundan log3(37) ≡ 3log3(2) + log3(7) + log3(11)  16 ≡ 588 (mod 1216) denkliği elde edilir. O halde m = 588 dir (Washington 2003).   22 Burada B çarpım tabanı kümesinin büyüklüğünün seçimi önemlidir. Eğer B kümesi çok küçük alınırsa B kümesindeki asal sayıları kullanarak g nin kuvvetlerini bulmak zorlaşır. Eğer B kümesi çok büyük alınırsa bağlantıları bulmak kolay olduğu halde B kümesinin elemanlarının ayrık logaritmalarını belirlemek için lineer cebir kullanılır. Bu ise oldukça kullanışsızdır. 2.2. Diffie-Hellman Anahtar Değişimi Bu kısımda kriptogarfik anahtarların değişimi işleminde kullanılan ve ayrık logaritma problemine dayanan Diffie-Hellman anahtar değişimi ele alınacaktır. Diffie-Hellman anahtar değişimi sisteminde X ve Y kişileri simetrik bir şifreleme yöntemi kullanarak veri alışverişi yapmak için ortak bir anahtar belirlerler. Örneğin, X ve Y kişileri finansal verileri iletmek isteyen bankalar olabilir. Bu ortak anahtarın teslimi için bir kurye kullanmak güvenilir ve pratik değildir. Dahası X ve Y kişilerinin daha önce iletişime geçmediği ve bu nedenle aralarındaki tek iletişim kanalının kamuya açık olduğu varsayılabilir. Diffie ve Hellman gizli bir anahtar oluşturmak için aşağıdaki biçimde hareket edilebileceğini söylemişlerdir. Buna göre,  X ve Y kişileri büyük bir p asal sayısı ve p modülüne göre sıfırdan farklı bir g tamsayısı belirlerler. Daha sonra bu kişiler, p asal sayısını ve F * p grubundaki mertebesi büyük bir asal sayı olacak biçimde seçilen bir g değerini kamuya açık bir kanalda paylaşırlar. Örneğin, bu değerleri kendi internet sitelerinde yayınlayabilirler ve böylece bu değerlerden üçüncü bir Z kişisi de haberdar olur.  X kişisi gizli bir a tamsayısı seçer ve A ≡ ga (mod p) değerini hesaplar. Y kişisi de gizli bir b tamsayısı seçer ve B ≡ gb (mod p) değerini hesaplar.   23  X kişisi A değerini Y kişisine gönderir ve Y kişisi de B değerini X kişisine gönderir. X ve Y kişileri güvenli olmayan iletişim kanalı üzerinden bu değerleri gönderdiğinden Z kişisi de A ve B değerlerinden haberdardır.  X kişisi A ≡ Ba (mod p) değerini ve Y kişisi de B ≡ Ab (mod p) değerini hesaplar. A ve B değerleri aslında aynıdır. Gerçekten de, A ≡ Ba ≡ (gb)a ≡ gab ≡ (ga)b ≡ Ab ≡ B (mod p) dir. Böylece X ve Y kişileri Diffie-Hellman anahtar değişimi sistemi ile veri alışverişinde bulunurlar. 2.2.1. Örnek. X ve Y kişilerinin p = 953 asal sayısını ve g = 629  F 953 ilkel kökünü kullandıklarını varsayalım. X kişisi a = 381 gizli anahtarını seçer ve A = 196 ≡ 629381 (mod 953) değerini hesaplar. Benzer şekilde, Y kişisi b = 781 gizli anahtarını seçer ve B = 289 ≡ 629781 (mod 953) değerini hesaplar. X kişisi Y kişisine 196 sayısını ve Y kişisi de X kişisine 289 sayısını gönderir. Bu iletişim güvensiz bir kanal üzerinden yapıldığından halka açıktır ve A = 196 ile B = 289 değerleri gizli kalamaz. Burada sadece a = 381 ve b = 781 sayıları gizlidir. X ve Y kişileri A = 289381 ≡ 839 (mod 953) ve B = 196781 ≡ 839 (mod 953) değerlerini hesaplar. Buradaki ortak değer, yani 839 sayısı onların gizli değeridir. Eğer Z kişisinin bu anahtar değişimini gördüğü varsayılır ve Z kişisi 629a ≡ 196 (mod 953) ve 629b ≡ 289 (mod 953) denkliklerinin her ikisini de çözebilirse X ve Y kişilerinin gizli anahtarını ele geçirebilir. Z kişisinin X ve Y kişilerinin yardımı olmadan gizli anahtarı ele geçirebilmesinin tek yolu budur.   24 Örneğe dikkat edilirse, X ve Y kişilerinin hesapladığı A, B, A = B değerleri oldukça küçük, yani hesaplaması kolaydır. Ayrıca Z kişisinin bilgisayarının da 953 modülüne göre 629 sayısının mümkün olan tüm kuvvetlerini kontrol etmesi çok az zaman alır. Bu ise bu bilgi aktarımının güvenli olmadığını gösterir. Son bilgisayar teknolojileri göz önüne alınırsa, X ve Y kişilerinin güvenli bir şekilde bilgi aktarımı yapabilmeleri için p asal sayısını yaklaşık olarak 1000 bit ve asal mertebeli g elemanını yaklaşık p/2 olarak seçmelerinin uygun olduğu düşünülebilir. Z kişisi A ve B değerlerini bildiğinden ga ve gb değerlerini de bilmektedir. Ayrıca g ve p değerlerini de bildiğinden ayrık logaritma problemini çözebilir. Böylece a ve b değerlerini bulabilir. Bu şekilde X ve Y kişilerinin gizli değeri olan gab değerini hesaplayabilir. X ve Y kişileri, ancak güvenliği sağladıklarında Z kişisinin ayrık logaritma problemini çözmesi olanaksız hale gelir. Bu durumda X ve Y kişilerinin paylaştığı ortak değerin güvenliği, aşağıda tanımlanacak olan Diffie-Hellman problemine bağlıdır. 2.2.2. Tanım. p bir asal sayı ve g bir tamsayı olsun. ga (mod p) ve gb (mod p) bilinen değerlerinden gab (mod p) değerini hesaplama problemine Diffie-Hellman problemi (DHP) denir. Diffie-Hellman probleminin ayrık logaritma probleminden daha zor olmadığı açıktır. Eğer Z kişisi ayrık logaritma problemini çözebilirse, ele geçirilen A ≡ ga ve B ≡ gb değerlerinden X ve Y kişilerinin gizli anahtarları olan a ve b değerlerini hesaplayabilir. Doğal olarak, Z kişisi için a ve b değerlerini bulduktan sonra gab değerini hesaplamak kolay olacaktır.   25 2.3. ElGamal Açık Anahtar Kriptosistemi Açık anahtar kriptosistemleri ilk olarak Diffie-Hellman tarafından ele alındığı halde Taher ElGamal’ın 1985 yılında tanımladığı ElGamal açık anahtar kriptosistemi ile birlikte gelişmiştir. Bu sistem ayrık logaritma problemine dayalıdır ve Diffie-Hellman anahtar alışverişi ile ilgili bir asimetrik şifreleme algoritmasıdır. Bu kısımda F * p grubu için ayrık logaritma problemine dayalı olarak ElGamal açık anahtar kriptosistemi ele alınacaktır. Açık anahtar kriptosistemlerinin en önemlilerinden birisi olan ElGamal açık anahtar kriptosisteminde X kişisi bir açık anahtar ve bir algoritma yayınlar. Bu sistemde açık anahtar bir sayı, algoritma ise Y kişisinin X kişisinin açık anahtarını kullanarak kendi mesajını şifrelediği yöntemdir. X kişisinin kimseye açıklamadığı özel bir anahtarı vardır ve üstelik sadece X kişisi açık anahtarı kullanarak şifrelenmiş mesajların şifresini çözebilir. ElGamal açık anahtar kriptosistemini kullanmak için X kişisi F * p grubu için ayrık logaritma probleminin çözümünün zor olduğu bir büyük p asal sayısı ve bir büyük asal mertebeli g  F * p elemanını seçer. X kişisi p ve g değerlerini kendisi seçebilir veya p ve g değerleri güvenilir bir kaynak tarafından önceden seçilmiş de olabilir. X kişisi özel anahtar olarak gizli bir a sayısı seçer ve A ≡ ga (mod p) değerini hesaplar. ElGamal açık anahtar kriptosisteminde de Diffie-Hellman anahtar değişiminde olduğu gibi X kişisi özel anahtarı olan a sayısını gizli tutar ve açık anahtar olan A değerini yayınlar. Y kişisinin, X kişisinin açık anahtarı olan A değerini kullanarak bir m mesajını şifrelemek istediğini ve üstelik m mesajının 2 ile p arasında bir tamsayı olduğunu varsayalım. Y kişisi m mesajını şifrelemek için p modülüne göre rastgele bir k sayısı   26 seçer. Y kişisinin seçmiş olduğu k sayısı sadece ve sadece bir mesajı şifrelemek için kullanıldığından k sayısına bir geçici anahtar denir. Y kişisi, m mesajını, rastgele seçilen k geçici anahtarını ve X kişisinin açık anahtarı olan A değerlerini kullanarak c1 ≡ gk (mod p) ve c2 ≡ mAk (mod p) değerlerini hesaplar. Böylece Y kişisinin X kişisine göndermiş olduğu şifreli metin, yani m mesajının şifrelenmiş hali, (c1, c2) sayı çiftidir. X kişisinin Y kişisine göndermiş olduğu bu şifreli metni çözmesi için izlemesi gereken yol aşağıdaki şekildedir: X kişisi a özel anahtarını bildiğinden x ≡ c a1 (mod p) değerini ve böylece x1(mod p) değerini hesaplar. Daha sonra X kişisi x1 ile c2 yi çarpar ve x ≡ c a1 (mod p) olduğunu kullanarak x1 ‧ c ≡ (c a)12 1 ‧ c2 (mod p) denkliğini elde eder. Bu denklikte c1 ≡ gk, c2 ≡ mAk (mod p) olduğunu göz önüne alarak x1 ‧ c2 ≡ (gak)1 ‧ (mAk) (mod p) denkliğini elde eder. Daha sonra A ≡ ga (mod p) denkliğini kullanarak x1 ‧ c2 ≡ (gak)1 ‧ (m(ga)k) (mod p) denkliğini elde eder. Son olarak gak ‧ (gak)1 = 1 olduğundan bu son denklik x1 ‧ c2 ≡ m (mod p) halini alır. Böylece X kişisi, x1 ile c2 yi çarparak m mesajına ulaşmış olur.   27 X ve Y kişilerinden farklı bir Z kişisinin mesajın şifresini çözmek istediğini düşünelim. p ve g parametreleri ve açık anahtar olan A ≡ ga (mod p) değeri halka açık bir kanaldan yayınlandığından Z kişisi bu değerleri bilmektedir. Eğer Z kişisi ayrık logaritma problemini çözebilirse, a özel anahtarını bulur ve mesajın şifresini de çözer. Dolayısıyla bu mesajın şifresinin çözülmesi ayrık logaritma probleminin çözümüne bağlıdır. 2.3.1. Örnek. X kişisinin p = 521 asal sayısını ve g = 6 ilkel kökünü kullandığını varsayalım. X kişisi kendisine seçmiş olduğu a = 165 özel anahtarını kullanarak A ≡ ga ≡ 6165 ≡ 175 (mod 521) açık anahtarını hesaplar. Y kişisi X kişisine m = 407 mesajını göndermeye karar verir ve rasgele seçilmiş bir k = 112 anahtarını belirler. Y kişisi bilinen bu değerlerle birlikte c1 ≡ 6112 ≡ 59 (mod 521) ve c2 ≡ 407 ‧ 175112 ≡ 511 (mod 521) hesaplamalarını yapar. Böylece Y kişisi X kişisine göndermek istediği şifreli metni (c1, c2) = (59, 511) sayı çifti olarak belirlemiş olur. X kişisi Y kişisinin gönderdiği m mesajını çözmek için olan a = 165 özel anahtarını kullanarak x ≡ c a 1651 ≡ 59 ≡ 320 (mod 521) ve x1 ≡ 324 (mod 521) hesaplamalarını yapar. Böylece X kişisi c x12 ≡ 511 ‧ 324 ≡ 407 (mod 521) hesaplamasını yaparak gönderilmiş olan m mesajını çözmüş olur. 2.3.2. Uyarı 1. ElGamal kriptosisteminde m düz metin mesajı 2 ile p  1 arasında bir tamsayı iken şifrelenmiş metin mesajı 2 ile p  1 arasındaki c1 ve c2 tamsayılarından oluşur. Böylece genellikle, şifreli mesajı yazmak için düz mesajı yazmak için gerekli olan bit sayısının iki katı kadar bit gereklidir. Dolayısıyla ElGamal, 2 ye 1 mesaj sistemidir.   28 Modern kriptosistemlerinin amaçlarından birisi, kriptosistemlerin güvenirliğinin bağlı olduğu bir zor problem belirlemektir. Örneğin, ElGamal kriptosisteminin güvenirliği, Diffie-Hellman probleminin çözümünün zorluğuna bağlıdır. Böylece aşağıdaki önermede görüleceği gibi, ElGamal kriptosistemi ile elde edilen şifreleri çözebilen kişilerin Diffie-Hellman problemini de çözebileceği sonucu elde edilir. 2.3.3. Önerme. p bir asal sayı ve g  F * p olsun. Z kişisinin ElGamal açık anahtarlarını kullanarak şifrelenmiş keyfi ElGamal şifreli mesajlarını çözen bir sisteme (oracle) eriştiğini varsayalım. Bu durumda Z kişisi Diffie-Hellman problemini çözmek için bu sistemi kullanabilir (Hoffstein ve ark. 2008). İspat. Diffie-Hellman problemini çözmek için ElGamal oracle sistemini nasıl kullanabileceğini açıklayalım. Diffie-Hellman probleminde Z kişisinin A ≡ ga (mod p) ve B ≡ gb (mod p) değerlerini bildiği hatırlanırsa Z kişisinin gab (mod p) değerini hesaplaması gereklidir. Burada Z kişisinin gizli a ve b değerlerini bilmediği unutulmamalıdır. Z kişisinin bir ElGamal oracle sistemini kullandığını varsayalım. Z kişisi, bir p asal sayısını, bir g elemanını, belirli bir A açık anahtarını ve belirli bir (c1, c2) şifreli metnini sisteme gönderebilir. Bu sistem Z kişisine (c a1 )1 ‧ c2 (mod p) değerini geri döndürür. Eğer Z kişisi Diffie-Hellman problemini çözmek istiyor ise c1 = B = gb ve c2 = 1 olarak seçebilir. Bu seçimle birlikte, sistem Z kişisine (gab)1 (mod p) değerini verir, Z kişisi de bu değerin p modülüne göre tersini alarak ve gab (mod p) değerini hesaplamış ve böylece Diffie-Hellman problemini çözmüş olur.   29 Z kişisi keyfi bir c2 değeri seçer ve A açık anahtarı ile (B, c2) şifreli metnini oracle sistemine gönderirse sistem Z kişisine asıl ulaşmak istediği m düz metin mesajının m ≡ (c a)1 ‧ c ≡ (Ba)11 2 ‧ c2 ≡ (gab)1 ‧ c2 (mod p) denkliğini gerçeklediğini belirtir. m değerini bilen Z kişisi gab (mod p) değerini bulmak için m1 ‧ c ≡ gab2 (mod p) hesabını yapar. Böylece Z kişisi a ve b gizli değerlerini bilmeden, sistem yardımı ile gab (mod p) değerini hesaplamış olur. Bundan başka, Z kişisi ayrık logaritma problemini çözmediği halde, yalnızca Diffie-Hellman problemini çözmüş olur. Z kişisinin keyfi şifrelemeleri çözen bir oracle sistemine erişimi bir saldırıdır ve bu saldırı seçilmiş şifreli metin saldırısı olarak bilinir. O halde, bir Diffie-Hellman probleminin zor olması ElGamal sisteminin seçilmiş şifreli metin saldırılarına karşı güvenli olduğunu gösterir. 2.4. Ayrık Logaritma Problemi İçin Bir Çarpışma Algoritması Bu kısımda bir çarpışma veya ortada buluşma algoritması örneği olan bir ayrık logaritma algoritması tanımlanacaktır. Daniel Shanks tarafından ele alınmış olan bu algoritma yalnızca F * p grubunda değil, herhangi bir grupta da çalışmaktadır. 2.4.1. Önerme. G bir grup ve g  G elemanının mertebesi N olsun. Bu durumda gx = h ayrık logaritma problemi, her adım g elemanı ile çarpma işleminden oluşmak üzere O(N) adımda çözülür (Hoffstein ve ark. 2008).   30 İspat. x = 0, 1, … , N  1 için gx değerleri bulunur ve listelenir. Burada her ardışık değer g elemanının önceki değerle çarpılmasıyla elde edilir. gx = h eşitliğinin bir çözümü varsa h listede bulunur. 2.4.2. Uyarı. Eğer G = F * p olarak alınırsa, her bir gx (mod p) değerinin hesaplanması O((log p)k) bilgisayar işlemi gerektirir, burada k ve büyük-O sabitleri, bilgisayara ve çarpma işlemi için kullanılan algoritmaya bağlıdır. Böylece bilgisayar adımlarının tüm sayısı ya da çalışma süresi, N, g elemanının mertebesi olmak üzere O(N(log p)k) kadardır. Genel olarak, O((log p)k) çarpanı ihmal edilerek, O(N) zamanda çalışması tercih edilecektir. Aşağıda verilecek olan çarpışma algoritmasının amacı, iki liste yaparak bu iki listedeki ortak olan elemanı bulmaktır. Ayrıca bu algoritmanın çalışma süresi O( N ) adımdan biraz daha fazladır. 2.4.3. Önerme (Shanks’in Bebek Adımı-Dev Adımı Algoritması). G bir grup ve g  G mertebesi N  2 olan bir eleman olsun. Aşağıdaki algoritma gx = h ayrık logaritma problemini O( N log N) adımda çözer. 1. n = 1 +  N  al, böylece n > N dir. 2. e, g, g2, g3, … , gn elemanlarının listesini oluştur (buradaki g elemanı ile çarpma işlemleri bebek adımlarıdır). 3. u = gn olmak üzere h, h ‧ u, h ‧ u2, h ‧ u3, … , h ‧ un elemanlarının listesini oluştur (buradaki u elemanı ile çarpma işlemleri dev adımlardır). 4. (2) ve (3) adımlarındaki listeler arasında bir eşleme bul. Eğer gi = h ‧ uj ise h = g i + jn dir, aksi halde h, g nin bir kuvveti değildir (Hoffstein ve ark. 2008).   31 İspat. (2) ve (3) adımlarındaki iki listeyi oluşturmak için yaklaşık olarak 2n çarpma işlemi yapılmıştır. Şimdi bu listeler arasında bir eşleme olduğunu varsayalım. Standart sınıflandırma ve arama algoritmalarını kullanarak log(n) adımın bir küçük katında bir eşleme bulunabilir, dolayısıyla bu iki liste arasında eşleme bulmak O(n log n) adım alır. Böylece n  N olduğundan n log n  N log N = 1 N log N 2 dir. O halde algoritmanın çalışma süresi O(n log n) = O( N log N) olur. Şimdi (2) ve (3) adımlarında böyle bir eşlemenin her zaman var olduğunu görelim. Bunun için x, gx = h eşitliğinin bir çözümü olsun. Bu durumda 0  r < n olmak üzere x = nq + r olarak yazılabilir. 1  x < N ve n > N olduğundan q = x  r < N < n n n eşitsizliği elde edilir. O halde gx = h eşitliği 0  r  n ve 0  q  n olmak üzere gr = h ‧ uq olarak yeniden yazılabilir. Böylece gr, 2. adımdaki listede ve h ‧ uq, 3. adımdaki listededir. Bu ise iki liste arasında bir eşleme olduğunu gösterir. 2.4.4. Örnek. g = 9704, h = 13896 ve p = 17389 için Shanks’in bebek adımı-dev adımı yöntemini kullanarak F * da gxp = h ayrık logaritma problemini çözelim. 9704 sayısının F*17389 daki mertebesi 1242’dir. n = 1 +  1242 = 36 ve u = gn = 970436 = 2494 alınır. F*17389 da, k = 7 için gk = 97047 = 14567 ve l = 32 için h ‧ ul = 13896 ‧ 249432 = 14567 yani 97047 = 14567 = 13896 ‧ 249432 ortak değeri bulunur. F*17389 da, 2494 = 970436 olduğu kullanılırsa   32 13896 = 97047 ‧ 249432 = 97047 ‧ (970436)32 = 97041159 eşitliği elde edilir. Böylece F*17389 daki 9704x = 13896 probleminin çözümü x = 1159 olarak bulunur (Hoffstein ve ark. 2008). 2.5. Pollard’ın  Algoritması Shanks’in bebek adımı-dev adımı algoritması çok fazla depolama alanı gerektirir. Bu kısımda ele alınacak olan Pollard’ın  algoritması da bir çarpışma algoritmasıdır. Bu algoritmada daha az veri depolanır ve adım sayısı Shanks’in bebek adımı-dev adımı algoritması ile yaklaşık olarak aynıdır. Pollard’ın  algoritması, eliptik eğrilerle ayrık logaritma problemini çözmek için bilinen en iyi yöntemdir. Bu algoritma aşağıdaki çarpışma teoremine dayanmaktadır. 2.5.1. Teorem. S, N elemanlı bir sonlu küme ve f : S  S bir fonksiyon olsun. Başlangıç terimi x0  S olmak üzere x0, x1, … noktalarının bir dizisi xi = f(xi1) = f  f      f(x0) biçiminde tanımlansın. i  0 olmak üzere (xi) dizisinde xT  1 sadece bir kere görünecek şekilde en büyük tamsayı T ve xT + L = xT olacak şekilde en küçük tamsayı L olsun. xT+1  x x T+2T xL+T xT 1 xT+3  x3 xL+T1 x2  xT+4  x1  xL+T4 x Kuyruk uzunluğu = T Yörünge uzunluğu = L0  Şekil 2.1. Pollard’ın  algoritmasındaki x0 ın yörüngesi (Silverman 2009)   33 a) x2i = xi olacak şekilde bir 1  i  T + L indeksi vardır. b) f : S  S olmak üzere f fonksiyonunun iterasyonları (ardışık olarak uygulanması) S kümesinin elemanlarını karıştıracak kadar “yeterince rastgele” ise T + L nin beklenen değeri N / 2 dir (Silverman 2009). İspat. a) Şekle dikkat edilirse j  i için xj = xi  i  T ve j ≡ i (mod L) olduğu açıktır. Böylece, x2i = xi  i  T ve L i dir. Bu özellikteki ilk i, T ve T + L  1 arasındadır. b) S kümesinden rastgele seçilen k tane x0, x1, x2, … , xk   1 noktalarının birbirinden farklı olma olasılığı k1 Prob(x0, … , xk  1 birbirinden farklı) =Pr ob (her 0  j  i için xi  xjx0, …, xi 1 farklı) i1 k1 k1 =  N  i i   = N    1  i1   i1  N  dir. t nin küçük değerleri için 1  t  et olduğu gerçeği kullanılırsa son çarpımın yaklaşık değeri k 1 2 Prob(x0, x1, … , xk  1birbirinden farklı)   N  i     ek / 2N i1  N  olarak bulunur. Şimdi x0, x1, … , xk  1 in birbirinden farklı olduğunu varsayalım. xk noktasının önceki değerlerden biriyle eşleşme olasılığı, Prob(xk bir eşlemedir  x0, x1, … , xk  1birbirinden farklı) = k N dir. Bu iki olasılık hesabı göz önüne alınırsa Prob(xk birinci eşlemedir) = Prob(xk bir eşleme ve x0, x1, … , xk  1 birbirinden farklı) = Prob(xk bir eşleme ve x0, x1, … , xk  1 birbirinden farklı)  Prob(x0, x1, … , xk  1 birbirinden farklı)   34 k k 2 e / 2N N olduğu elde edilir. Böylece ilk eşlemeden önce beklenen adım sayısı 2 k ‧Prob(x ilk eşlemedir)  k  ‧ ek 2 / 2N k k1 k1 N 2   dir. Diğer yandan Φ(t) = t2 et / 2N olarak alınır, (k / n)  n(t) olduğu kullanılırsa k 1 0  k ‧Prob(x ilk eşlemedir)  N  t 2et 2 / 2 k = N / 2 k1 0 olarak bulunur. 2.5.2. Pollard’ın  Algoritması. G bir grup ve x, y  G olsun. xm = y eşitliğini gerçekleyen bir m tamsayısını bulmak için xi yj = xk yl olacak biçimde i, j, k, l tamsayılarını bulmak için Teorem 2.5.1’ i kullanalım. xi  k = yj  l olduğundan j  l sayısının x in mertebesi olan n sayısı ile aralarında asal olduğu varsayılırsa y, x in bir kuvveti olarak çözülebilir. f : G  G fonksiyonu, G grubundaki elemanları yeterince karıştırabilecek ve yörüngeleri kolay izlenebilecek biçimde tanımlanmalıdır. Pollard, G grubunu yaklaşık olarak eşit büyüklükte üç ayrık kümeden oluşacak biçimde parçalamıştır. Buna göre, G = A  B  C olmak üzere xz, z A f(z) =  2z , zB  yz, zC fonksiyonu kullanılarak işlemler yapılır.   35 f fonksiyonu tekrar tekrar başlangıç noktası z0 = 1 noktasına uygulandığında f nin i iterasyonu sonrasında bir zi noktası elde edilir. Böylece belli i, i tamsayıları için zi = f  f    f(1) = xi yi olarak yazılabilir. Burada i, i değerleri 0 = 0 = 0 olmak üzere z1, z2, … değerlerini hesaplayarak ve  i1, zi  A  i , zi  A  i + 1 =  2i , zi B ,   i + 1 = 2i , zi B    i , zi C i1, zi C iterasyon formüllerini kullanarak hesaplanır. Dikkat edilirse xn = 1 olduğundan i ve i değerleri n modülüne göredir. Benzer şekilde w0 = 1 ve wi + 1 = f(f(wi)) noktalarının dizisi hesaplanabilir. Böylece, wi = z2i = x i yi olduğu elde edilir. Burada i ve i değerleri, ilk olarak wi = z2i eşitliği ve daha sonra f(wi) = z2i + 1 fonksiyonunu kullanarak i ve i için verilen bağıntılar yardımıyla i – 1 ve  i – 1 değerlerinden hesaplanabilir. Bu işlemler, (z1, w1), (z2, w2), … sıralı ikililerinden x ve y koordinatları birbirine eşit olan bir çift bulana kadar devam ettirilir. Dikkat edilirse her bir (zi, wi) sıralı ikilisi yalnızca önceki (zi  1, wi  1) sıralı ikilisi ile elde edilebileceğinden depolanan veri azdır. A, B, C kümelerinin G grubunun elemanlarının karıştırılmasında yeterince iyi olduğu varsayılırsa bir önceki teorem gereği, O( N ) adımda zi = wi = z2i şeklinde bir eşleme bulunur. zi = wi olduğundan xi  i = yi i eşitliği elde edilir. n bir asal sayı olmak üzere (i  i, n) = 1 ise   36 m ≡ (i  i) (i   1i) (mod n) olarak bulunur. Bu ise xm = y eşitliğini çözer. Genel olarak, d = (i  i, n)  1 ise yd, x in bir kuvveti olarak ifade edilebilir, örneğin yd = xe olarak alınabilir. Bu durumda 0  u  d olmak üzere y, x(enu) / d elemanlarından birine eşittir. Dolayısıyla eğer d büyük bir sayı değilse, bu ayrık logaritma problemini çözer, eğer d büyükse Pollard’ın algoritması x ve y arasında bir ilişki bulana kadar çalışır. 2.5.3. Uyarı. Shanks’in ve Pollard’ın algoritmaları herhangi bir gruba uygulanabilir ve bu algoritmalar, n mertebeli devirli bir G grubundaki ayrık logaritma probleminin O( N ) adımda çözülebileceğini gösterir. G grubunun işlemlerini gerçekleştiren bir kara kutu olduğu düşünülürse gruptaki herhangi x1, x2 elemanları bu kutuya atıldığında x1x2 değerini hesaplar, ancak kara kutuda yapılan bu hesaplamanın nasıl olduğu bilinmez. Shoup (1997), kara kutu algoritması yardımıyla, G grubunda ayrık logaritma problemini çözen herhangi bir algoritmanın en az O( N ) adım sürdüğünü göstermiştir. Dolayısıyla eliptik eğri üzerindeki grup yapısı kullanılarak ayrık logaritma problemini çözmek için bilinen en iyi algoritmalar bile kara kutu algoritmasından daha iyi değildir. 2.6. Pohlig-Hellman Algoritması G bir grup ve g  G mertebesi N olan bir eleman olmak üzere G grubundaki gx = h eşitliğinin çözümü N modülüne göre belirlenebileceğinden N sayısının asal çarpanlaması oldukça önemlidir. Aşağıda verilecek olan Pohlig-Hellman algoritması N sayısının asal çarpanlarını kullanır. Bu algoritmayı vermeden önce aşağıdaki uyarıya ihtiyaç vardır. 2.6.1. Uyarı. G bir grup g, h  G ve q bir asal sayı olmak üzere g  G elemanının mertebesi qe olsun. G grubunda gx = h ALPni çözen bir algoritma olduğunu varsayalım.   37 Bu durumda ALP, O(S eq ) adımda çözülebilir. Eğer e, q dan çok daha küçük bir sayı ise ALP, S eq = e q adımda çözülür, eğer Shanks’in bebek adımı-dev adımı algoritması kullanılırsa S eq = qe/2 dir. 2.6.2. Teorem. G bir grup olmak üzere g  G elemanının mertebesi N olsun ve N sayısı asal sayıların kuvvetlerinin çarpımı biçiminde t N = qeii i1 olarak yazılsın. Bu durumda gx = h ayrık logaritma problemi t O(S  log N ) i1 q ei i adımda aşağıdaki gibi çözülebilir. 1) Her 1  i  t için N / qeig = g i ve h = hN / q ei i i i olsun. gi elemanının mertebesi qeii asal kuvveti olduğundan g yi = hi ayrık logaritma problemini çözmek için uyarıda geçen algoritmalardan biri kullanılır ve bu eşitliğin bir çözümü y = yi olarak alınır. 2) Çinlilerin kalan teoremi kullanılarak x ≡ y1 (mod qe11 ), x ≡ y (mod q e2 2 2 ), … , x ≡ yt (mod q et t ) denkliklerinin çözümü bulunur (Hoffstein ve ark. 2008). t İspat. (1) adımı O(S e ) zaman, (2) adımı ise Çinlilerin kalan teoremi kullanarak i i1 qi t O(log N) zaman alır. Dolayısıyla algoritmanın çalışma süresinin O(S e  log N ) q ii1 i olduğu açıktır.   38 Şimdi (1) ve (2) adımlarının gx = h ayrık logaritma probleminin bir çözümünü verdiğini görelim. x, (2) adımındaki denklik sisteminin bir çözümü olsun. O halde her i ve belli zi ler için x = y + qeii i zi olarak yazılabilir. Bu eşitlikten (g x )N / q ei ei ei ei i  (g yi qi zi )N / qi = (g N / qi ) yi g Nzi ei ei eşitliği elde edilir. Diğer yandan gN = 1 ve g = g N / qi , g yi i = hi ve son olarak h = h N / qi i olduğu hatırlanırsa (g x )N / q ei N / qey ii  g ii  h  h ii olduğu elde edilir. gN elemanı etkisiz eleman olduğundan g tabanında ayrık logaritma sadece N modülüne göre tanımlıdır. Böylece son eşitlikten g tabanında ayrık logaritma problemi N e x ≡ N e logg (h) (mod N) (2. 1) q ii q ii olarak yeniden yazılabilir. Dikkat edilirse Ne , … , N   e sayılarının ortak çarpanı q 1 q t1 t yoktur, yani bu sayılar aralarında asaldır. Dolayısıyla N e ‧ c1 + N ‧‧‧ + e ‧ ct = 1 (2. 2) q 11 q tt olacak şekilde c1, c2, … , ct tamsayıları vardır. (2. 1) denkliğinin her iki tarafı ci lerle çarpılır ve i = 1, 2, … , t üzerinden toplam alınırsa t N t N  e ci x ≡ i  e ci logg(h) (mod N) i i1 qi i1 qi denkliği elde edilir. Böylece (2. 2) eşitliği dikkate alınırsa x ≡ logg(h) (mod N) denkliği elde edilir.   39 2.6.3. Uyarı. Pohlig-Hellman algoritmasına göre, G grubunun mertebesi küçük asal sayıların kuvvetinin çarpımı biçiminde yazılabilirse G grubunda ayrık logaritma problemi güvenli değildir. Diğer bir ifade ile, g elemanının mertebesi küçük asal sayıların kuvvetinin bir çarpımı ise gx = h eşitliğini çözmek kolaydır. Bu durum özellikle p  1 sayısının çarpanlarının küçük asal sayıların kuvvetleri biçiminde yazılabilmesi halinde Fp deki ayrık logaritma problemi için geçerlidir. Bu halde p  1 çift olduğundan q bir asal sayı olmak üzere p = 2q + 1 ve q mertebeli bir g elemanı alınabilir. Bu algoritmanın çalışma süresi Önerme 2.4.3 gereği, O( q ) = O( p ) dir. Bununla birlikte daha sonraki kısımda görüleceği gibi indeks hesabı yönteminin çalışma süresi alt üsteldir. Dolayısıyla p = 2q + 1 olarak alınsa bile q asal sayısı oldukça büyük seçilmelidir. Aşağıdaki önermede, mertebesi asal sayıların kuvvetleri olan elemanlar için ayrık logaritma probleminin mertebesi asal elemanlar için ayrık logaritma problemine e1 indirgendiği görülecektir. Bu önerme g elemanının mertebesi qe ise g q elemanının mertebesinin q olduğunu kullanır. Teorem 2.6.2 deki notasyonlarla, aşağıda da görüleceği gibi, qe mertebeli elemanlar için çalışma süresi S eq den O(eSq) ya indirgenebilir. Önerme, G bir grup g, h  G ve q bir asal sayı, g  G elemanının mertebesi q olmak üzere G grubunda gx = h ALPni Sq adımda çözen bir algoritma olduğunu varsaymaktadır. Dolayısıyla Shanks’in bebek adımı-dev adımı algoritması kullanılırsa ALP, Sq = O( q ) adımda çözülebilir, ancak bu önerme g  G elemanının mertebesi qe ise ALP nin O(e q ) adımda çözülebildiğini ifade etmektedir. 2.6.4. Önerme. G bir grup, q bir asal sayı ve a  G elemanın mertebesi q olmak üzere G grubundaki ax = b ayrık logaritma problemini Sq adımda çözen bir algoritma olduğunu varsayalım. e  1 olmak üzere g  G elemanının mertebesi qe ise gx = h ayrık logaritma problemi O(eSq) adımda çözülebilir (Hoffstein ve ark. 2008). İspat. gx = h eşitliğindeki x kuvveti, 0  xi  q olmak üzere   40 x = x + x q + x q2 + ‧‧‧ + x qe  10 1 2 e  1 (2. 3) olacak şekilde yazılabilir ve x0, x1, x2, … değerleri belirlenebilir. gx = h eşitliğinin her iki tarafının qe1 inci kuvveti alınır ve (2. 3) eşitliği kullanılırsa e1 e1 hq  (g x )qe1  (g x0  x1q... xe1q ) ve bu eşitlik yeniden düzenlenir ve g q e =1 olduğu kullanılırsa qe1 x qe1 eh  g 0 (g q )x1... xe1q e2 e1  (g q )x0 e1 eşitliği elde edilir. g q , G grubunda q mertebeli bir eleman olduğundan qe1 x e1(g ) 0  hq eşitliği tabanı q mertebeli bir eleman olan bir ayrık logaritma problemidir. Varsayım gereği, bu ayrık logaritma problemi Sq adımda çözülebilir. Bu durumda G grubunda x qe1 qe1g 0  h olacak biçimde x0 üssü bilindiğinden benzer bir hesaplama yapılabilir. Buna göre gx = h eşitliğinin her iki tarafının qe2 inci kuvveti alınır ve gerekli düzenlemeler yapılırsa e2 e2 hq  (g x q )  (g x0  x1q... x q e1 qe2 x qe2 x qe1e1 ) = g 0 g 1 e1 eşitliği elde edilir. Dikkat edilirse x0 değeri belirlenmiştir ve g q elemanının G grubundaki mertebesi q dur. x1 değerini bulmak için qe1(g )x e2 1  (hg  x0 )q ayrık logaritma problemi çözülmelidir. Verilen algoritma tekrar uygulanırsa bu problem Sq adımda çözülebilir. Böylece O(2Sq) adımda, G grubunda e2 e2 (g x0  x1q )q  hq eşitliğini gerçekleyen x0 ve x1 değerleri belirlenmiş olur. Benzer şekilde   41 qe1 e3(g )x2  (hg  x0  x1q )q ayrık logaritma problemi çözülerek x2 değeri bulunur. Bu şekilde devam edilerek x0, … , xi  1 değerleri belirlendikten sonra G grubunda qe1 x  x  x q... x qi1 qei1(g ) i  (hg 0 1 i1 ) ayrık logaritma problemi çözülerek xi değeri bulunur. Bunların her biri tabanı q mertebeli olan bir ayrık logaritma problemidir ve varsayım gereği her bir problem Sq adımda çözülebilir. Dolayısıyla O(eSq) adımda gx = h eşitliğini gerçekleyen bir x = x0 + x1q + x2q2 + ‧‧‧ + x e  1e  1q kuvveti bulunur. Böylece ayrık logaritma problemi çözümü elde edilmiş olur. 2.6.5. Örnek. F* x11251 grubunda 5448 = 6909 ayrık logaritma problemini çözelim. Buna göre 11250 sayısı 54 ile bölündüğünden F11251 grubunda 5448 elemanının mertebesinin 54 dür. Bu ayrık logaritma probleminin çözümü için ilk olarak 3 3 (54485 )x0 = 69095 eşitliğini alalım. Dikkat edilirse bu eşitlik F*11251 grubunda 11089x0 = 11089 eşitliğine indirgenir ve böylece eşitliğin çözümü x0 = 1 dir. Böylece x bilinmeyen kuvvetinin ilk değeri x0 = 1 olarak bulunur. İkinci olarak 3 2 2 (54485 )x1 = (6909 5448x0 )5 = (6909 54481)5 eşitliğini alalım. Bu eşitlik F*11251 grubunda 11089x1 = 3742 eşitliğine indirgenir. Eğer q büyük bir sayı olsaydı bu ayrık logaritma problemini çözmek için Shanks’in bebek adımı-dev adımı gibi hızlı bir algoritma kullanılabilir, ancak bu durumda x1 sayısının 1 ve 4 arasındaki değerlerini denemek yeterlidir. Böylece x1 = 2 çözümü bulunur. Bulunan x1 değeriyle birlikte x = 11 = 1 + 2 ‧ 5 olduğu elde edilir.   42 Şimdi x2 değerini bulmak için 53(5448 )x2 = (6909 5448x0x15 )5 = (6909 544811)5 eşitliği F*11251 grubunda 11089x2 = 1 eşitliğine indirgenir ve dolayısıyla x2 = 0 olarak bulunur. Böylece x değeri değişmez, yani x = 1 + 2 ‧ 5 + 0 ‧ 52 = 11 dir. Son olarak 3 2 (54485 )x3 = (6909 5448x0x15x25 ) = 6909 544811 eşitliği F*11251 grubunda 11089x3 = 6320 eşitliğine indirgenir ve böylece x3 = 4 olduğu elde edilir. O halde x = 511 = 1 + 2 ‧ 5 + 4 ‧ 53 dir. Dikkat edilirse 5448511 ≡ 6909 (mod 11251) dur (Hoffstein ve ark. 2008). 2.7. Fp deki Ayrık Logaritma Problemini Hesaplamak İçin İndeks Hesabı Yöntemi İndeks hesabı yöntemi, açık anahtar kriptolojisinin bulunuşundan birkaç yıl önce ilk olarak 1968’de Western ve Miller’in (1968) çalışmasında ortaya çıkmıştır. Bu yöntem, Diffie-Hellman’nın (1976) makalesinin yayınlanmasından sonra 1970’li yıllarda birkaç kriptosistemci tarafından yeniden keşfedilmiştir. İndeks hesabı, Fp sonlu cismindeki ayrık logaritma probleminin çözümü için kullanılan bir yöntemdir. Aşağıda bu yöntemde kullanılacak olan bir tanım verilmiştir. 2.7.1. Tanım. n bir tamsayı olsun. Eğer n, bir B sayısından küçük ya da eşit olan asal sayıların çarpımı biçiminde yazılabiliyorsa n tamsayısına B-düzgün (B-smooth) sayı denir.   43 Örneğin, 18 sayısı 3-düzgün sayıdır. Gerçekten de, 18 = 2 ‧ 32 olduğundan 18 sayısı 2 ve 3 asal sayılarının kuvvetleri biçiminde yazılır. 2.7.2. İndeks Hesabı Yöntemi. p asal sayı ve g, h tamsayılar olmak üzere gx ≡ h (mod p) ayrık logaritma problemini çözmek için g yi p modülüne göre bir ilkel kök olarak alalım. Bu yöntemde gx ≡ h (mod p) ayrık logaritma problemini doğrudan çözmek yerine bir B düzgün sayısı seçilir ve l  B özelliğindeki her l asal sayısı için gx ≡ l (mod p) ayrık logaritma problemi çözülür. Diğer bir deyişle l  B özelliğindeki her l asal sayısı için logg(l) ayrık logaritması hesaplanır. Daha sonra k = 1, 2, … için h ‧ gk (mod p) değerleri hesaplanır, bu işleme h ‧ gk (mod p) değerleri B-düzgün sayı olacak şekilde bir k değeri bulana kadar devam edilir. Bu özellikteki k sayısı belli el ler için h ‧ gk ≡  l el (mod p) (2. 4) lB denkliği elde edilir. Bu denklik logg(h) ≡ k + el logg(l) (mod p  1) (2. 5) lB olarak yeniden yazılabilir, burada ayrık logaritmalar sadece p  1 modülüne göre tanımlıdır. l  B özelliğindeki her l asal sayısı için logg(l) değerinin hesaplandığı varsayıldığından (2. 5) denkliği logg(h) değerini verir. Şimdi küçük l asal sayıları için logg(l) değerinin nasıl bulunduğunu açıklayalım. 0  gi  p olmak üzere i nin rastgele seçimi için gi ≡ gi (mod p) denkliği hesaplanır.   44 gi, B-düzgün değilse bu gi değeri alınmaz ve elenir, eğer gi değeri B-düzgün ise gi g = lul (i)i lB olarak çarpanlarına ayrılabilir. Böylece i ≡ logg(gi) ≡ ul (i) ‧ logg(l) (mod p  1) (2. 6) lB denkliği elde edilir. Dikkat edilirse (2. 6) denkliğinde bilinmeyen değerler logg(l) ayrık logaritma değerleridir. B sayısından küçük veya B sayısına eşit olan asal sayıların eleman sayısı (B) ile gösterilirse, (2. 6) denkliğine benzer (B) sayısından daha fazla denklik bulunabilirse logg(l) değerlerini bulmak için lineer cebir kullanılabilir. 2.7.4. Örnek. p = 18443 olmak üzere indeks hesabı yöntemini kullanarak 37x ≡ 211 (mod 18443) ayrık logaritma problemini çözelim. g = 37 sayısı p = 18443 modülüne göre bir ilkel köktür. Eğer B = 5 olarak alınırsa asal sayıların oluşturduğu çarpım tabanı kümesi {2, 3, 5} tir. 18443 modülüne göre g = 37 sayısının rastgele kuvvetlerini alınır ve B-düzgün sayıları seçilirse g12708 ≡ 23 ‧ 34 ‧ 5 (mod 18443), g15400 ≡ 23 ‧ 33 ‧ 5 (mod 18443) g11311 ≡ 23 ‧ 52 (mod 18443), g2731 ≡ 23 ‧ 3 ‧ 54 (mod 18443) denklikleri elde edilir. Bu denklikler yardımıyla g tabanına göre 2, 3 ve 5’in ayrık logaritmaları için eşitlikler elde edilir. Örneğin, birinci denklikten 12708 = 3 ‧ logg(2) + 4 ‧ logg(3) + logg(5) eşitliği elde edilir. Eğer x2 = logg(2), x3 = logg(3), x5 = logg(5) denirse yukarıdaki dört denklikten 12708 = 3x2 + 4x3 + x5 15400 = 3x2 + 3x3 + x5 11311 = 3x2 + 2x5 2731 = 3x2 + x3 + 4x5 (2. 7)   45 lineer denklemleri elde edilir. Dikkat edilirse ayrık logaritmalar sadece p  1 modülüne göre tanımlı olduğundan Böylece (2. 7) deki formüller p  1 = 18442 = 2 ‧ 9221 modülüne göredir. 9221 sayısı bir asal sayı olduğundan (2. 7) deki lineer denklem sisteminin 2 ve 9221 modülüne göre çözülmesi gerekir. Bu lineer denklem sistemi Gauss yöntemiyle kolaylıkla çözülebilir. x2, x3, x5 bilinmeyenlerinin 2 modülüne ve 9221 modülüne göre çözümleri (x2, x3, x5) ≡ (1, 0, 1) (mod 2) (x2, x3, x5) ≡ (5733, 6529, 6277) (mod 9221) olduğundan (x2, x3, x5) ≡ (5733, 15750, 6277) (mod 18442) olduğu elde edilir. Daha sonra 375733 ≡ 2 (mod 18443), 3715750 ≡ 3 (mod 18443), 376277 ≡ 5 (mod 18443) değerleri hesaplanarak çözümler kontrol edilir. 37x ≡ 211 (mod 18443) ayrık logaritma probleminin çözümü bulunmak istendiğinden k sayısının rastgele değerleri için B-düzgün 211 ‧ 37k (mod 18443) değerini bulana kadar hesaplama yapılırsa 211 ‧ 379549 ≡ 25 ‧ 32 ‧ 52 (mod 18443) olduğu elde edilir. Yukarıda elde edilen 2, 3 ve 5’in ayrık logaritma değerleri kullanılarak logg(211) = 9549 + 5 logg(2) + 2 logg(3) + 2 logg(5) = 9549 + 5 ‧ 5733 + 2 ‧ 15750 + 2 ‧ 6277 ≡ 8500 (mod 18442) olduğu elde edilir. Son olarak 378500 ≡ 211 (mod 18443) olduğundan logg(211) = 8500 dür (Hoffstein ve ark. 2008). 2.7.5. Uyarı. İndeks hesabının çalışma süresi kabaca hesaplanabilir. B sayısından küçük asal sayılardan oluşan bir çarpım tabanı kullanılarak yaklaşık (B) tane B-düzgün gi (mod p) sayıları bulunmalıdır. Bunun için elek-tipi (sieve-type) gibi çeşitli yöntemler   46 kullanılabilir. Her durumda indeks hesabı, F p daki ayrık logaritma problemini çözmek için bir altüstel algoritmadır. Ancak daha sonra da görülebileceği gibi eliptik eğri gruplarındaki genel ayrık logaritma problemini çözmek için bilinen en iyi algoritmalar üstel algoritmalardır.   47 3. MATERYAL VE YÖNTEM Çalışmada eliptik eğri ayrık logaritma problemi daha kolay bir ayrık logaritma problemine dönüştürülmek istendiğinden eliptik eğriler kavramı oldukça önemlidir. Dolayısıyla bu bölümde eliptik eğriler ve eliptik eğriler ile ilgili temel kavramlar ele alınacak, eliptik eğrilerin ayrık logaritma probleminde nasıl kullanıldığını gösteren bazı temel teoremler incelenecektir. Daha sonra eliptik eğri ayrık logaritma problemi üzerinde durulacak ve bu problemin çözümü için bazı algoritmalar verilecektir. Eliptik eğriler, Fermat’nın son teoreminin ispatında A. Wiles tarafından kullanıldıktan sonra oldukça popüler olmuşlardır. Böylece eliptik eğriler teorisi, cebirin de önemli bir alanı haline gelmiştir. Son yıllarda eliptik eğriler kriptosistemciler tarafından şifreleme yöntemlerinde kullanılmaya başlanmıştır. Böylece bu şekilde oluşturulan şifrelerin kırılmasında son teknoloji bilgisayarların kullanılması halinde bile uzun zaman alması hedeflenmiştir. 3.1. Eliptik Eğriler Bu kısımda eliptik eğriler tanıtılacak ve bu eğrilerin temel özellikleri ele alınacaktır. Eliptik eğriler ile ilgili detaylı bilgi için (Silverman 2009) ve (Silverman ve Tate, 2015) kitapları incelenebilir. 3.1.1. Tanım. F karakteristiği 2 ve 3 ten farklı bir cisim, a, b  F ve 4a3 + 27b2  0 olmak üzere E : y2 = x3 + ax + b şeklindeki denklemin tüm çözümlerinin oluşturduğu (x, y) sıralı ikililerinin kümesine O noktası ile birlikte bir eliptik eğri denir. Bu denkleme E eliptik eğrisinin Weierstrass formu denir.   48 F bir cisim ve a1, a2, a3, a4, a6  F olmak üzere E: y2 + a1 x y + a3 y = x3 + a2 x2 + a4 x + a6 biçimindeki bir denkleme E eliptik eğrisinin uzun Weierstrass formu denir. Eğer E, F cismi üzerinde tanımlı bir eliptik eğri ise bu eğri üzerindeki noktaların kümesi E(F) ile gösterilir, yani E(F) = {(x, y) : x, y  F  F| y2 = x3 + ax + b}  {O} dir. E(F), E eliptik eğrisinin üzerinde tanımlanan özel bir toplama işlemine göre bir gruptur ve O noktası bu grubun etkisiz elemanıdır. O noktası sonsuzdaki nokta olarak adlandırılır ve bu noktanın x-eksenine dik olan tüm doğruların üzerinde olduğu varsayılır. Bir E eliptik eğrisi üzerindeki toplama işlemi ise şu şekilde tanımlanır: Bir E eliptik eğrisi üzerinde iki farklı P ve Q noktaları toplamak için bu noktalardan geçen l doğrusunu alalım. l doğrusu E eliptik eğrisini üçüncü bir R noktasında keser, R noktasının x-eksenine göre simetriği olan nokta P + Q = R noktası olarak tanımlanır. Eğer P noktası kendisiyle toplanmak istenirse bu noktadan geçen teğet doğru dikkate alınır. Eğer bir P = (x, y) noktasının x-eksenine göre simetriği olan P = (x, y) noktası ile toplanmak istenirse P ve P noktalarından geçen doğrusu x-eksenine diktir. Dolayısıyla P + P = O dur. Son olarak E eliptik eğrisi üzerinde bir P noktası ile O noktası toplanmak istenirse P noktası ile O noktasından geçen l doğrusu x-eksenine dik olduğundan P + O = P dir. E, y2 = x3 + ax + b Weierstrass denklemi ile verilen bir eliptik eğri olmak üzere P = (x, y)  E ise P = (x, y) dir. Bundan başka, P  E ve m  Z olmak üzere m > 0 ise mP =P...P m tan e   49 ve m < 0 ise mP = (–m)(–P) olarak alınır ve 0P = O olarak tanımlanır. 3.1.2. Teorem. E, F cismi üzerinde tanımlı bir eliptik eğri olmak üzere E(F) abelyen bir gruptur (Silverman 2009). Aşağıdaki teoremde E eliptik eğrisi üzerindeki toplama işlemi cebirsel olarak verilmiştir. 3.1.3. Teorem (Eliptik Eğriler için Toplama İşlemi Algoritması). Input: E : y2 = x3 + ax + b bir eliptik eğri ve E eğrisi üzerinde P1 ve P2 noktaları olsun. 1. Eğer P1 = O ise P1 + P2 = P2 dir. 2. P1  O ve P2 = O ise P1 + P2 = P1 dir. 3. P1, P2  O ise P1 = (x1, y1) ve P2 = (x2, y2) olarak al. 4. Eğer x1 = x2 ve y1 =  y2 ise P1 + P2 = O dur. 2 5. P1  P2 ve x1  x2 ise  = y2  y1 , P 3x1  a1 = P2 ve y1  0 ise  = olarak tanımla x2  x1 2y1 ve x3 = 2  x1  x2 ve y3 =  (x1  x3)  y1 olarak al. Bu durumda P1 + P2 = (x3, y3) tür (Hoffstein ve ark. 2008). Bir E eliptik eğrisi üzerindeki büküm noktaları kümesinin kriptolojide oldukça önemli uygulamaları vardır. 3.1.4. Tanım. E, bir eliptik eğri ve m  1 bir tamsayı olsun. E eliptik eğrisinin m mertebeli noktalarının kümesine E eliptik eğrisinin m-büküm altgrubu denir ve E[m] ile gösterilir, yani   50 E[m] = {P  E| mP = O} dir. Aşağıdaki teorem E[m] grubunun nasıl bir grup olduğunu belirtmektedir. 3.1.5. Teorem. E, F cismi üzerinde tanımlı bir eliptik eğri olmak üzere m  1 bir tamsayı olsun. Eğer K cisminin karakteristiği m sayısını bölmüyor veya 0 ise E[m]  Z/mZ  Z/mZ dir. Eğer K cisminin karakteristiği p > 0, p | m ve p | m olmak üzere m = prm ise E[m]  Z/mZ  Z/mZ veya E[m]  Z/mZ  Z/mZ dir (Washington 2003). 3.2. Bir Eliptik Eğrinin Bölüm Polinomları Şimdi bir eliptik eğrinin bölüm polinomları kavramını ele alalım. E, bir K cismi üzerinde tanımlı ve Weierstrass denklemi E: y2 + a1 x y + a3 y = x3 + a2 x2 + a4 x + a6 olan bir eliptik eğri olsun. E eliptik eğrisinin Fn bölüm polinomları F1 = 1 F2 = 2y + a1x + a3 F3 = 3x4 + b2x3 + 3b x24 + 3b6 x + b8 F4 = F2 (2x6 + b 52x + 5b 44x + 10b x36 + 10b8 x2 + (b2b8 ‒ b4b 26)x + (b4b8 ‒ b6 )) başlangıç terimlerini kullanarak m ≥ 2 için F 3 32m + 1 = Fm + 2Fm ‒ Fm ‒ 1Fm + 1 , ve m ≥ 3 için, F 2 2m F2 = Fm ‒ 1 Fm Fm + 2 ‒ F 3m ‒ 2 Fm Fm + 1   51 indirgeme bağıntıları ile elde edilir. Burada bi terimleri E eliptik eğrisinin Tate değerleridir (Silverman 2009, Chapter III.1). Bir eliptik eğrinin bölüm polinomları kavramı literatürde oldukça önemlidir. Bir eliptik eğrinin bölüm polinomları kavramı eliptik fonksiyonlar teorisi, eliptik bölünebilir diziler teorisi ile yakından ilgilidir. Bundan başka E, karakteristiği 2’den farklı bir F cismi üzerinde tanımlı bir eliptik eğri ve P  E(F) olmak üzere n  1 tamsayısı için P noktasının n katı nP,   nP =  Gn (P) , Hn (P) 2 3  (3.1)  Fn (P) Fn (P)  olarak yazılabilir. Bundan başka Gn ve Hn bölüm polinomları G0 = 1, G1 = x H0 = 1, H1 = y (3.2) başlangıç terimlerini kullanarak n ≥ 2 için G 2n = xFn ‒ Fn + 1Fn ‒ 1, Hn = (F 2F 2 2 ‒ 1 n ‒ 1 n + 2 ‒ Fn ‒ 2Fn + 1 ‒ F2Fn(a1Gn + a3Fn ))(2F2) (3.3) indirgeme bağıntıları ile elde edilirler. Bir eliptik eğrinin Fn bölüm polinomları aşağıdaki zincir kuralını gerçekler. 3.2.1. Lemma. E, bir F cismi üzerinde tanımlı bir eliptik eğri ve P  E(F) olmak üzere her m, n ≥ 1 tamsayıları için F n2mn = Fm o (Fn o m) dir (Mazur ve Tate 1991).   52 3.3. Eliptik Eğri Üzerinde Bölenler f bir rasyonel fonksiyon olmak üzere f fonksiyonunun sıfırları ve kutup yerleri katlılıkları da sayarak bir formal toplamla ifade edilebilir. Buna göre, f fonksiyonun birbirinden farklı sıfırları 1, …, r ve bu sıfırların katlılıkları sırasıyla d1, …, dr ve f fonksiyonun birbirinden farklı kutupları 1, …, s ve bu kutupların katlılıkları sırasıyla e1, …, es olmak üzere f fonksiyonunun böleni (divisor) div(f) ile gösterilir ve div(f) = d1(1) + … + dr(r) – e1(1) – … – es(s) formal toplamı olarak tanımlanır. E, y2 = x3 + ax + b denklemi ile verilen bir eliptik eğri ve f(x, y) iki değişkenli bir rasyonel fonksiyon olsun. P = (x, y)  E olmak üzere f(P) = f(x, y) olarak alınırsa f, E eliptik eğrisi üzerinde tanımlı bir rasyonel fonksiyon olarak düşünülebilir. O halde f fonksiyonunun payını ve paydasını sıfır yapan E eliptik eğrisinin noktaları vardır. Dolayısıyla f fonksiyonunun E eğrisi üzerinde sıfırları ve kutupları vardır. Üstelik sıfır ve kutup yerlerinin katlılıkları da belirtilebilir. Dolayısıyla f fonksiyonu div(f) böleni ile div(f) = nP (P) PE biçiminde eşleşir. Bu toplamdaki nP katsayıları tamsayılardır ve sadece sonlu sayıda nP terimi sıfırdan farklı olduğundan div(f) sonludur. Doğal olarak f fonksiyonunun sıfırları ve kutupları E cisminin tanımlı olduğu cisimden daha büyük bir cisimde bulunabilir. Daha genel olarak aşağıdaki tanım verilebilir. 3.3.1 Tanım. E bir eliptik eğri, P  E ve nP  Z olmak üzere D = nP (P) PE biçimindeki herhangi bir formal toplama E üzerinde bir bölen denir. Burada sadece sonlu sayıda P E için nP terimi sıfırdan farklı ve diğer tüm nP terimleri sıfırdır.   53 Bir D böleninin nP katsayılarının toplamına D nin derecesi denir ve der(D) ile gösterilir, yani der(D) = der (nP (P)) = nP PE PE dir. Bir D böleninin toplamı sum(D) ile gösterilir ve sum(D) = sum (nP (P)) = nPP PE PE dir. 3.3.2 Örnek 1. E, y2 = x3 + ax + b denklemi ile verilen bir eliptik eğri olmak üzere x3 + ax + b kübik polinomu x3 + ax + b = (x – 1)(x – 2)(x – 3) olarak çarpanlarına ayrılsın. Bu durumda P1 = (1, 0), P2 = (2, 0) ve P3 = (3, 0) noktaları birbirinden farklıdır ve 2P1 = 2P2 = 2P3 = O dur. y fonksiyonunun bu üç noktada sıfırı vardır ve div(y) = (P1) + (P2) + (P3) – 3(O) dur. 2. E bir eliptik eğri ve P  E[m] noktasının mertebesi m olsun. Bu durumda mP = O olduğundan E eliptik eğrisi üzerinde div(f) = m(P) – m(O) olacak biçimde bir f fonksiyonu vardır. Eğer m = 2 olarak alınırsa P = (, 0)  E[2] olduğundan f(x) = x –  fonksiyonu için div(x – ) = 2(P) – 2(O) dur.   54 3.4. Sonlu Cisimler Üzerinde Tanımlı Eliptik Eğriler Eliptik eğriler teorisinin kriptoloji uygulamalarında sonlu bir Fp cismi üzerinde tanımlı eliptik eğriler kullanılır. Eğer bir E eliptik eğrisi sonlu bir Fp cismi üzerinde tanımlı ise eliptik eğri üzerindeki noktaların x- ve y-koordinatları için sonlu çoklukta olasılık olduğundan E(Fp) noktalarının kümesinin sonlu bir küme olduğu açıktır. Bir başka ifade ile x-koordinatı için p olasılık varken her x için y2 = x3 + ax + b eşitliğinden y için en çok iki olasılık vardır. Böylece sonsuzdaki O noktası ile E(Fp) grubunun eleman sayısı en çok 2p + 1 olabilir. Ancak alınan bir noktanın x-koordinatının p modülüne göre bir ikinci dereceden kalan olabilme olasılığı yüzde elli olduğundan E(Fp) grubundaki noktaların sayısının yaklaşık olarak #E(Fp) 1   2  p + 1 = p + 1 2 dir. Hasse’nin aşağıdaki teoremi #E(Fp) değeri için bir üst sınır verilmektedir. Bu teoremin ortaya atılmasından yıllar sonra Weil ve Deligne tarafından teorem daha genel hale getirilmiştir. 3.4.1. Teorem (Hasse Teoremi). E, Fp cismi üzerinde tanımlı bir eliptik eğri olsun. O halde tp  2 p   olmak üzere #E(Fp) = p + 1  tp dir (Silverman 2009). 3.4.2. Tanım. Hasse Teoreminde geçen tp = p + 1  #E(Fp) değerine Fp cismi üzerinde tanımlı E eliptik eğrisi için Frobenius endomorfizminin izi denir.   55 3.4.3. Uyarı. Hasse teoremi #E(Fp) değeri için bir üst sınır verdiği halde bu değerin hesaplanması için bir yöntem belirtmez. Verilen bir x değeri için x3 + ax + b değerinin p modülüne göre bir kare olup olmadığını belirlemek O(p) süre alır ve bu kullanışlı değildir. Schoof (1985), #E(Fp) sayısını O((log p)6) sürede hesaplayan polinom zamanlı bir algoritma geliştirmiştir. Schoof’un algoritması daha sonra Elkies ve Atkin tarafından geliştirildiğinden bu algoritma SEA algoritması olarak bilinmektedir. 3.5. Eliptik Eğri Ayrık Logaritma Problemi Bu kısımda eliptik eğri ayrık logaritma problemi ele alınacaktır. Bunun için ilk olarak F p grubu için ayrık logaritma problemini hatırlayalım: A kişisi g ve h sayılarını yayınlar ve bu kişinin gizli sayısı x, h ≡ gx (mod p) denkliğinin çözümüdür. Eğer A kişisi g ve h sayılarını F p grubunun elemanları olarak düşünürse ayrık logaritma problemi, A kişisinin düşmanı olan B kişisinin h ≡ g  g (mod p)  x tan e olacak biçimde bir x değerini bulmasını zorunlu hale getirir. Diğer bir ifade ile B kişisi, h yi elde etmek için g nin kaç kere kendisi ile çarpıldığını bulmalıdır. Benzer şekilde, A kişisi E(Fp) grubunu kullanarak aynı işlemleri yapabilir. Bunun için A kişisi E(Fp) grubundan P ve Q noktalarını yayınlar ve Q = PP = nP n tan e olacak şekilde bir n tamsayısını gizli tutar. Böylece B kişisinin P noktasını kaç defa kendisiyle toplarsa Q noktasına ulaşacağını bulması gerekir. E eliptik eğrisi üzerindeki   56 noktaların toplama işlemi daha karışık olduğundan E(Fp) grubu için ayrık logaritma problemini çözmek oldukça zordur. 3.5.1. Tanım. E, Fp sonlu cismi üzerinde tanımlı bir eliptik eğri ve P, Q  E(Fp) olsun. Q = nP olacak şekildeki bir n tamsayısını bulma problemine eliptik eğri ayrık logaritma problemi (EEALP) denir. F p grubu için ayrık logaritma problemine benzer olarak bu n tamsayısı n = logP(Q) ile gösterilir ve n tamsayısına Q noktasının P noktasına göre eliptik ayrık logaritması denir. 3.5.2. Uyarı 1. Bu tanımda bazı durumlara dikkat edilmelidir. Örneğin P, Q  E(Fp) olmak üzere P noktasının bir katı olacak şekilde bir Q noktası olmayabilir. Bu durumda, logP(Q) değeri tanımlı değildir. Ancak, A kişisi herkese açık bir P noktası ve gizli bir n tamsayısı seçip Q = nP değerini hesaplayarak P ve Q noktalarını yayınlamaktadır, böylece logP(Q) değeri vardır ve bu değer A kişisinin gizli değeri olmalıdır. 2. Bundan başka, eğer Q = nP olacak biçimde bir n tamsayısı varsa bu özellikte birçok değer bulunabilir. Bunun görmek için ilk önce sP = O olacak şekilde bir pozitif s tamsayısının var olduğunu düşünelim. E(Fp) sonlu bir grup olduğundan P, 2P, 3P, … noktalarının tümü birbirinden farklı olamaz. Böylece kP = jP olacak şekilde k  j tamsayıları vardır ve s = k  j alabiliriz. Bu özellikteki en küçük s  1 tamsayısına P noktasının mertebesi denir. Böylece eğer, s, P noktasının mertebesi ve Q = n0P olacak şekilde herhangi bir n0 tamsayısı varsa Q = nP eşitliğinin çözümleri, i  Z olmak üzere n = n0 + is tamsayılarıdır. O halde logP(Q) değeri Z/sZ nin bir elemanıdır, yani s, P noktasının mertebesi olmak üzere logP(Q), s modülüne göre bir tamsayıdır. Genellikle logP(Q) = n0 olarak alınır. logP(Q) değeri Z/sZ nin bir elemanı olduğundan eliptik ayrık logaritması her Q1, Q2  E(Fp) için   57 logP(Q1 + Q2) = logP (Q1) + logP(Q2) (3. 4) dir. Böylece (3. 4) eşitliğinden E(Fp) grubu için EEALPnin, klasik logaritma özelliğine ve F  p için ayrık logaritma özelliğine benzediği görülmektedir. Bundan başka (3. 4) eşitliği kullanılarak logP fonksiyonunun E(Fp) grubundan Z/sZ grubuna bir grup homomorfizm olduğu kolayca görülebilir. 3.5.3. Örnek. F73 sonlu cismi üzerinde tanımlı E : y2 = x3 + 8x + 7 eliptik eğrisi dikkate alınırsa P = (32, 53), Q = (39, 17)  E(F73) için Q = 11P ve böylece logPQ = 11 dir. Benzer şekilde R = (35, 47), S = (58, 4)  E(F73) noktaları için R = 37P ve S = 28P olduğundan logP (R) = 37 ve logP (S) = 28 dir. Diğer yandan E(F73) = 82 olduğu halde P noktası için 41P = O, yani P noktasının mertebesi 82/2 = 41 dir. Dolayısıyla E(F73) grubundaki noktaların yarısı P noktasının bir katıdır. Örneğin, (20, 65)  E(F73) noktası P noktasının bir katına eşit değildir (Hoffstein ve ark. 2008). 3.6. İkiye Katlama ve Toplama Algoritması E(Fp) grubundaki P ve Q = nP noktalarından n değerini elde etmek, yani EEALPni çözmek zordur. Bununla birlikte Z  E(Fp) , n  nP fonksiyonunu kriptolojide kullanmak için bilinen n ve P değerlerinden nP değeri verimli bir biçimde elde edilmelidir. Eğer n sayısı büyük bir sayı ise P, 2P, 3P, … gibi değerleri hesaplayarak nP değerini bulmak zaman alacaktır. Dolayısıyla nP değerini hesaplamak için daha önce Diffie-Hellman anahtar değişimi, ElGamal ve RSA açık anahtar kriptosistemleri için an (mod N) kuvvetlerinin hesaplanması için uygulanan hızlı   58 kuvvet alma algoritmasına benzer bir yöntem kullanılabilir. Bunun için ilk olarak n sayısı n0, n1, n2, …, nr  {0, 1} olmak üzere n = n0 + n1 ‧ 2 + n2 ‧ 4 + n3 ‧ 8 + ‧‧‧ + n rr ‧ 2 şeklinde yazılır ve nr = 1 olduğu varsayılarak Q0 = P, Q1 = 2Q0 , Q2 = 2Q1, …, Qr = 2Qr  1 değerleri hesaplanır. Bu eşitliklerden görülebileceği gibi Qi = 2Qi  1 olduğundan Qi = 2iP olduğu elde edilir. Bu noktalar P noktasının 2 nin bir kuvvetinin katıdır ve bu noktaların hesaplanması en çok r tane ikiye katlama gerektirir. Son olarak nP noktası en çok r tane toplama işlemi ile nP = n0 Q0 + n1 Q1 + ‧‧‧ + nr Qr biçiminde hesaplanır. E(Fp) grubundaki iki noktanın toplama işlemi bir nokta işlemi olarak alınırsa nP değerini hesaplamak için E(Fp) grubunda en çok 2r tane nokta işlemi yapılmış olur. n  2r olduğundan nP değerini hesaplamak için 2log2(n) tane nokta işleminden daha fazla işleme gerek yoktur. Üstelik bu yöntemle n sayısının çok büyük değerleri için de nP değerini hesaplamak mümkün olur. Aşağıda bu yöntem için bir algoritma verilecektir. 3.6.1. Algoritma (İkiye Katlama ve Toplama Algoritması). Input. P  E(Fp) noktası ve n ≥ 1 tamsayısı. 1. Q = P ve R = O al. 2. n  0 iken 3. n ≡ 1 (mod 2) ise, R = R + Q al.   59 4. Q = 2Q ve n = n / 2 al. 5. n  0 ise 2. adıma git. 6. nP = R noktasına dön (Hoffstein ve ark. 2008). 3.6.2. Örnek. Yukarıda verilen İkiye Katlama ve Toplama algoritmasını kullanarak E : y2 = x3  21x + 23 eliptik eğrisi ve n = 187, p = 1531, P = (5, 434) için E(Fp) grubunda nP değerini hesaplanmak istenirse n sayısı ikinin kuvvetleri biçiminde n = 187 = 1 + 2 + 23 + 24 + 25 + 27 olarak yazılabilir. Böylece n sayısının yazılışından da anlaşılacağı gibi yedi ikiye katlama ve beş toplama işlemi yapıldığı görülür. Sonuç olarak 187P = (935, 866) olarak bulunur. 3.6.3. Uyarı. nP değerini hesaplamak için gereken süreyi daha da azaltmanın bir yöntemi n sayısını 2 nin kuvvetlerinin farkı ve toplamını kullanarak yazmaktır. Böylece nP değerini hesaplamak için daha az nokta kullanılır. Weierstrass formda verilen bir eliptik eğri üzerindeki herhangi bir nokta için (x, y) = (x,  y) olduğundan iki noktanın farkı, toplamları kadar kolay bulunur. F p grubunda bir a elemanı için a1 değerinin hesaplanması herhangi iki elemanın çarpımı işleminden daha fazla zaman aldığından E(Fp) grubunda yapılan yukarıdaki işlemler F p grubundan farklıdır. Yukarıdaki örnekte, 187 = 1 + 2 + 23 + 24 + 25 + 27 olarak yazıldığından 187P değerini hesaplamak için 7 ikiye katlama ve 5 toplama işlemi olmak üzere toplam 12 nokta işlemi yapılmıştır. Ancak n sayısı 187 =  1  22  26 + 28 şeklinde yazılırsa 187P =  P  22P  26P + 28P   60 yi hesaplamak için 8 ikiye katlama ve 3 toplama işlemi olmak üzere toplam 11 nokta işlemi yapılmış olur. Bir n sayısının 2’nin pozitif ve negatif kuvvetlerinin bir toplamı olarak yazılmasına n sayısının bir üçlü açılımı denir. Şimdi n sayısının büyük bir sayı olduğunu varsayalım ve k = log n + 1 olarak alalım. n sayısı 2k  1 biçiminde yazılabiliyorsa 2k  1 = 1 + 2 + 22 + ‧‧‧ + 2k  1 olduğundan n sayısının bir ikili açılımını kullanarak nP değerinin hesaplanması k tane ikiye katlama ve k tane toplama işlemi olmak üzere toplam 2k tane nokta işlemini gerektirir. Eğer n sayısının yazılışında üçlü açılım kullanılırsa Önerme 3.6.4’te görüleceği gibi nP değerini hesaplamak için k + 1 tane ikiye katlama ve 1 k tane 2 toplama işlemi olmak üzere toplam 3 k + 1 nokta işleminden daha fazla nokta işlemi 2 gerekmez. Şimdi genel duruma bakalım. Rastgele bir sayının ikili açılımındaki 0’ların ve 1’lerin sayısı yaklaşık olarak aynıdır. Dolayısıyla n sayısının ikili açılımı kullanarak nP değerini hesaplamak k tane ikiye katlama ve 1 k tane toplama işlemi olmak üzere 2 toplam 3 k adım gerekir. Eğer 2’nin kuvvetlerinin toplamları ve farkları alınırsa n 2 sayısının ikili açılımında terimlerin 2 ’ ü sıfır olduğundan nP değerini hesaplarken k + 1 3 tane ikiye katlama ve k tane toplama işlemi olmak üzere toplam 4 k + 1 adım gerekir. 3 3.6.4. Önerme. n bir pozitif tamsayı ve k = log n + 1, yani 2 k  n olsun. u0, u1, … , uk  {1, 0, 1} ve ui değerlerinin en çok 1 k tanesi sıfırdan farklı olmak üzere 2 n = u0 + u1 ‧ 2 + u2 ‧ 4 + u3 ‧ 8 + ‧‧‧ + u ‧ 2k k (3. 5)   61 olarak yazılabilir (Hoffstein ve ark. 2008). İspat. Önermenin ispatı aslında n sayısını istenen biçimde yazmak için kullanılan bir algoritmadır. n sayısı, n0, … , nk  1  {0, 1} olmak üzere n = n0 + n1 ‧ 2 + n2 ‧ 4 + n3 ‧ 8 + ‧‧‧ + n k  1k  1 ‧ 2 olarak ikili biçimde yazılabilir. Ardışık sıfırdan farklı ni katsayılarını bulmak istiyoruz. Belli bir t  2 için ns = ns + 1 = ‧‧‧ = ns + t  1 = 1 ve ns + t = 0 olduğunu varsayalım, diğer bir ifade ile n sayısının ikili açılımında 2s + 2s + 1 + ‧‧‧ + 2s + t  1 + 0 ‧ 2s + t (3. 6) ifadesinin olduğunu düşünelim. Bu ifade 2s + 2s + 1 + ‧‧‧ + 2s + t  1 + 0 ‧ 2s + t = 2s (1 + 2 + 4 + 2t  1) = 2s (2t  1) şeklinde yazılabildiğinden (3. 6) ifadesi  2s + 2s + t olarak yazılabilir. Bu işleme devam edilirse ardışık iki ui değeri sıfırdan farklı olmayacak şekilde n sayısının (3. 5) deki gibi bir yazılımı elde edilmiş olur. 3.7. EEALP Ne Kadar Zordur? Kısım 2.4. de ele alınan çarpışma algoritmaları herhangi bir gruba kolayca uygulanabilir. Dolayısıyla bir eliptik eğrinin üzerindeki noktaların grubu E(Fp) için böyle bir algoritma verilebilir. Q = nP eşitliğini çözmek için bir B kişisi 1 ve p asal sayısı arasında rastgele j1, j2, … ,jr ve k1, k2, … , kr tamsayıları seçer ve aşağıdaki gibi iki liste oluşturur. 1. Liste: j1P, j2P, j3P, … , jrP , 2. Liste: k1P + Q, k2P + Q, k3P + Q, … , krP + Q.   62 B kişisi iki liste arasında juP = kvP + Q eşlemesini bulursa Q = (ju  kv)P olduğundan çözümü elde eder. Bu çarpışma algoritması iki liste için fazla depolama alanı gerektirir. Bununla birlikte, Kısım 2.5. te ele alınan Pollard’ın  algoritması daha az depolama alanına sahiptir ve benzer bir çalışma süresiyle buradaki duruma uygulanabilir. Her halde E(Fp) grubu için EEALPni O( p ) adımda çözen algoritmalar vardır. F  p grubu için ayrık logaritma problemini çözmenin daha hızlı yollarının var olduğunu biliyoruz. Özellikle, daha önce ele alınan indeks hesabı yöntemi alt üstel çalışma süresine sahiptir, yani bu yöntemin çalışma süresi her ε  0 için O(pε) dir. Eliptik eğrilerin kriptolojide kullanılmasının temel nedeni, EEALP için indeks hesabı yöntemlerinin bulunmamasıdır. Gerçekten de EEALPni O( p ) adımdan daha az sürede çözmek için bilinen genel algoritmalar yoktur. EEALPni çözmek için bilinen en hızlı algoritmalar herhangi bir gruptaki ALPni için aynı derecede çalışan algoritmalardan daha iyi değildir. Böylece EEALP, ALPnden çok daha zordur. Bununla birlikte F  p grubu için ALPnin kolay çözülebildiği p asal sayıları vardır. Örneğin, p  1 sayısı küçük asal sayıların çarpımı şeklinde yazılabiliyorsa, Pohlig-Hellman algoritması F  p grubu için ALPni hızlı bir şekilde çözüme ulaştırır. 3.8. Eliptik Eğri Kriptolojisi Bu kısımda eliptik eğrilerin kriptolojiye nasıl uygulandığını ele alacağız. E(Fp) grubu için ayrık logaritma problemi ile anahtar değişimini güvenli bir şekilde sağlayan en basit uygulama Diffie-Hellman anahtar değişimi algoritmasıdır.   63 3.8.1. Eliptik Diffie-Hellman Anahtar Değişimi Bu kısımda daha önce Fp grubunda ele alınan Diffie-Hellman anahtar değişimi yöntemi, bir E eliptik eğrisi üzerindeki noktaların grubu E(Fp) üzerinde ele alınacaktır. Buna göre, A ve B kişileri bir E(Fp) grubu ve P  E(Fp) noktasını kullanırlar.  İlk olarak A kişisi gizli bir nA tamsayısı seçer ve B kişisi de gizli bir nB tamsayısı seçer.  İkinci olarak A kişisi QA = nAP değerini ve B kişisi de QB = nBP değerini hesaplar.  Sonraki adımda A kişisi QA değerini B kişisine, B kişisi de QB değerini A kişisine gönderir. Böylece A kişisi gizli nA değerini kullanarak nAQB yi ve B kişisi de nB değerini kullanarak nBQA yı hesaplar ve paylaştıkları gizli değerlerle birlikte nAQB = (nAnB)P = nB gizli değerine ulaşırlar. Bu gizli değeri A ve B kişileri simetrik şifreyle iletişim kurma k için anahtar olarak kullanabilirler. 3.8.2. Örnek. A ve B kişileri p = 3851 asal sayısı, E: y2 = x3 + 324x + 1287 eliptik eğrisi ve P = (920, 303)  E(F3851) noktası ile eliptik Diffie-Hellman anahtar değişimi yöntemini kullanmaya karar verirler. A kişisi nA = 1194 ve B kişisi nB = 1759 gizli değerlerini seçerler ve daha sonra A kişisi QA = 1194P = (2067, 2178)  E(F3851) değerini B kişisi QB = 1759P = (3684, 3125)  E(F3851) değerini hesaplar. A kişisi QA değerini B kişisine, B kişisi de QB değerini A kişisine gönderir. Sonuç olarak, A ve B kişileri nAQB = 1194(3684, 3125) = (3347, 1242) = nBQA = 1759(2067, 3178)  E(F3851)   64 hesaplamalarını yaparak (3347, 1242) gizli noktasını paylaşmış olurlar. Uyarı 3.8.4 te açıklanacağı gibi A ve B kişileri gizli değerin y koordinatını kullanmayıp sadece x = 3347 gizli değerini kullanırlar. Eğer bir C kişisi A ve B kişilerinin gizli değerini çözmek için nP = QA EEALPni çözebilirse nA değerini bildiğinden nAQB değerini hesaplayabilir (J. Hoffstein ve ark. 2008). 3.8.3. Tanım. E, Fp sonlu cismi üzerinde tanımlı bir eliptik eğri ve P  E(Fp) olsun. Bilinen n1P ve n2P değerlerinden n1n2P değerini hesaplama problemine eliptik eğri Diffie-Hellman problemi denir. 3.8.4. Uyarı 1. Eliptik Diffie-Hellman anahtar değişimi, A ve B kişilerinin bir eliptik eğri üzerinde nokta alışverişi yapmasını gerektirir. E(Fp) grubundaki bir Q noktası, xQ ve yQ Fp sonlu cisminin elemanları olmak üzere Q = (xQ, yQ) biçiminde olduğundan A kişisi B kişisine Fp de iki sayı göndermek zorundadır. Bununla birlikte, bu iki sayı arasında Fp cisminde y 2 = x 3Q Q + axQ + b biçiminde bir ilişki olduğundan bu iki sayı p modülüne göre iki keyfi sayı kadar bilgi vermez. Dikkat edilirse bir C kişisi a ve b değerlerini bilmektedir ve dolayısıyla C kişisi xQ nun doğru değerini tahmin edebilirse yQ için iki muhtemel değer olduğundan C kişisi için yQ değerini hesaplamak zor değildir. 2. Dolayısıyla A kişisinin QA noktasının iki koordinatını B kişisine göndermesine gerek yoktur. O halde A kişisi B kişisine sadece QA noktasının x-koordinatını gönderir. Böylece B kişisi de mümkün olan iki y koordinatından birini hesaplar ve kullanır. Eğer B kişisi doğru y değerini seçerse QA değerini kullanır. Eğer B kişisi yanlış y değerini seçerse QA değerini kullanmış olur. Her iki durumda da B kişisi   65  nBQA =  (nAnB)P değerlerinden birini hesaplar. Benzer şekilde A kişisi de (nAnB)P değerlerinden birini hesaplar. Böylece A ve B kişileri hangi y değerini kullandıklarına bakmaksızın x- koordinatı aynı olduğundan paylaşılan gizli değerleri olarak x-koordinatını kullanırlar. Şimdi eliptik Diffie-Hellman anahtar değişimine bir örnek verelim. Bunun için aşağıdaki uyarıya ihtiyaç vardır. 3.8.5. Uyarı. p, p ≡ 3 (mod 4) özelliğinde bir asal sayı ve a sayısı x2 ≡ a (mod p) denkliğinin bir çözümü olacak şekilde bir tamsayı olsun. O halde b ≡ a(p + 1)/4 (mod p) bir çözümdür, yani b2 ≡ a (mod p) denkliğini gerçekler. 3.8.6. Örnek. A ve B kişileri Örnek 3.8.2’deki p = 3851 asal sayısı, E: y2 = x3 + 324x + 1287 eliptik eğrisi ve P = (920, 303)  E(F3851) noktasını kullanarak birbirlerine daha az bit göndererek başka bir gizli değer alışverişi yapmaya karar verirler. A ve B kişileri yeni gizli değerlerini nA = 2489, nB = 2286 olarak seçerler ve A kişisi QA = nAP = 2489(920, 303) = (593, 719)  E(F3851) değerini, B kişisi de QB = nBP = 2286(920, 303) = (3681, 612)  E(F3851) değerini hesaplar. Bununla birlikte, noktanın iki koordinatını göndermek yerine A kişisi B kişisine sadece xA = 593 değerini ve B kişisi de A kişisine sadece xB = 3681 değerini gönderir. Böylece, A kişisi E eliptik eğrisinin denkleminde xB = 3681 değerini yazarsa, y 2B = x 3B + 324 x 3B + 1287 = 3681 + 324 ‧ 3681 + 1287 = 997 değerini bulur ve A kişisinin 3851 modülüne göre 997 sayısının bir karekökünü hesaplaması gerekir. Böylece A kişisi p ≡ 3 (mod 4) olduğundan yukarıdaki uyarıyı dikkate alarak   66 y = 997(3851 + 1)/4B = 997963 ≡ 612 (mod 3851) değerini hesaplar. Böylece B kişisinin kullandığı QB = (xB, yB) = (3681, 612) noktasını elde eder ve nAQB = 2489(3681, 612) = (509, 1108) değerini hesaplar. Benzer şekilde, B kişisi xA = 593 değerini E eliptik eğri denkleminde yerine yazar ve karekök alırsa, y 2A = x 3A + 324xA + 1287 = 5933 + 324 ‧ 593 + 1287 = 927 y = 927(3851 + 1)/4A = 927963 ≡ 3132 (mod 3851) olarak elde eder. B kişisi, A kişisinin QA noktasını kullanmayıp QA' = (593, 3132) noktasını kullanır ve n BQA' = 2286(593, 3132) = (509, 2743) değerini hesaplar. B kişisinin yaptığı bu hesaplamada E(Fp) deki noktanın negatifi kullandığı halde bu noktaların x-koordinatı aynı olduğundan A ve B kişilerinin paylaştığı gizli değer x = 509 dur (Hoffstein ve ark. 2008). 3.9. Eliptik ElGamal Açık Anahtar Kriptosistemi Bu kısımda daha önce Kısım 2.4. te ele alınan ElGamal açık anahtar kriptosistemine benzer bir kriptosistemin eliptik eğrilere uygulamasını ele alınacaktır. Eliptik ElGamal açık anahtar kriptosistemine göre, A ve B kişileri belli bir p asal sayısı, E eliptik eğrisi ve P  E(Fp) noktasını kullanır. A kişisi gizli bir nA değeri (özel anahtar) seçer ve E(Fp) grubunda QA = nAP değerini hesaplayıp QA değerini açık anahtarı olarak yayınlar. B kişisi bir M  E(Fp) noktasını düz metni olarak alır ve rastgele bir k tamsayısı seçip A kişisinin QA değerini kullanarak c1 = kP, c2 = M + k QA  E(Fp) değerlerini hesaplar. Daha sonra B kişisi (c1, c2) noktalarını A kişisine gönderir. Böylece A kişisi   67 c2  nAc1 = (M + kQA)  nA(kP) = M + k (nAP)  nA(kP) = M hesaplamasını yaparak M düz metnine ulaşır. 3.9.1. Uyarı 1. Eliptik ElGamal açık anahtar kriptosisteminde düz metin mesajlarını E(Fp) noktaları ile bağlamanın açık bir yolu yoktur. 2. Fp cismi kullanılırsa ElGamal 2’ye 1 mesaj kriptosistemi olduğu halde eliptik ElGamal 4’e 1 mesaj kriptosistemidir. Eliptik ElGamal kriptosisteminde 4’e karşılık 1 mesaj elde edilmesinin nedeni, M düz metninin E(Fp) de tek bir nokta olmasıdır. Hasse Teoremi’ne göre, E(Fp) de yaklaşık olarak p farklı nokta olması p farklı düz metin olabileceğini gösterir. Bununla birlikte, E(Fp) deki her nokta iki koordinattan oluştuğundan (c1, c2) şifreli metni p modülüne göre dört sayıdan oluşur. 3. Eliptik Diffie-Hellman anahtar değişiminde olduğu gibi c1 ve c2 nin sadece x- koordinatlarını karşı tarafa gönderilebilir. Ancak, A kişisinin c2  nAc1 değerini hesaplaması gerektiğinden A kişisinin c1 ve c2 değerlerinin hem x- hem de y- koordinatının doğru değerlerine ihtiyacı vardır. Ayrıca bir noktanın x-koordinatı ile işarete bağlı olarak y-koordinatı belirlenebilir. Bu nedenle B kişisi, A kişisine ekstra bit yollamış olur, örneğin, 0, 0  y 1 p Ekstra bit =  2 1, 1 p  y  p  2 dir. Böylece B kişisi sadece c1 ve c2 değerlerinin x-koordinatlarını ve ekstra iki bit göndermelidir.   68 3.10. Weil Eşleştirmesi Aşağıda eliptik eğri kriptolojisinde ve özellikle MOV algoritmasında kullanılan Weil eşleştirmesi kavramı ve özellikleri üzerinde durulacaktır. İlk olarak Weil eşleştirmesi tanımı ile başlayalım. 3.10.1. Tanım. E, bir F cismi üzerinde tanımlı bir eliptik eğri, m bir pozitif tamsayı ve F cisminin karakteristiği ile m aralarında asal olmak üzere P, Q  E[m] olsun. fP ve fQ, E eliptik eğrisi üzerinde bölenleri div(fP) = m[P]  m[O] ve div(fQ) = m[Q]  m[O] olan rasyonel fonksiyonlar olmak üzere S  E(F) eliptik eğrisi üzerinde ve S  {O, P,  Q, P  Q} özelliğinde herhangi bir nokta olsun. Bu durumda µm, birimin m. ilkel köklerinin grubu olmak üzere f (PS) em : E[m]  E[m]  µ , e (P, Q) = fP (Q S) Q m m fP (S) fQ (S) biçiminde verilen em eşleştirmesine P ve Q noktalarının Weil eşleştirmesi (Weil pairing) denir. Burada em(P, Q) değeri fP, fQ fonksiyonları ve S noktasının seçiminden bağımsızdır. 3.10.2. Uyarı 1. Her P, Q  E[m] için em Weil eşleştirmesinin em(P, Q)m = 1 eşitliğini gerçeklediği açıktır. Diğer bir ifade ile em(P, Q) birimin m. köküdür. 2. Hatırlanacağı gibi E[m] grubu Z/mZ  Z/mZ grubuna izomorftur. Dolayısıyla E[m], rankı 2 olan serbest Z/mZ-modüldür. O halde {P1, P2}, E[m] için bir baz olmak üzere determinant dönüşümü kullanılarak   69 det: E[m]  E[m]  Z/mZ, det(aP1 + bP2, cP1 + dP2) = ad  bc biçiminde bir alterne bilineer eşleştirme tanımlanabilir. ad  bc değerinin bazın seçiminden bağımsız olduğu açıktır. Üstelik Weil eşleştirmesi ile determinant eşleştirmesi birbirleri ile yakından ilgilidir. 3. E[m] üzerindeki determinant eşleştirmesi bir Galois değişmezi değildir. Diğer bir ifade ile P, Q  E[m] ve   G( K /K)  ise det((P), (Q)) değeri (det(P, Q)) olmak zorunda değildir. Aşağıdaki teoremde em Weil eşleştirmesinin E[m] üzerinde Galois değişmezliği özelliğini gerçeklediği görülecektir. Buna göre , birimin m. ilkel kökü olmak üzere  = em(P, Q) olarak alınırsa  = em(P, Q) = em((P), (Q)) = (em(P, Q)) = () dir. Aşağıdaki teoremde Weil eşleştirmesinin özellikleri belirtilmektedir. 3.10.3. Teorem. E, bir F cismi üzerinde tanımlı bir eliptik eğri, m bir pozitif tamsayı olmak üzere F cisminin karakteristiği m sayısını bölmesin. µm, birimin m. ilkel köklerinin grubu olsun. Bu durumda em : E[m]  E[m]  µm Weil eşleştirmesi aşağıdaki özellikleri gerçekler. i) em eşleştirmesi bilineerdir, yani her P, P1, P2, Q, Q1, Q2  E[m] için em(P1 + P2, Q) = em(P1, Q) em(P2, Q), em(P, Q1 + Q2) = em(P, Q1) em(P, Q2) dir. ii) em eşleştirmesi alternedir, yani her P  E[m] için em(P, P) = 1   70 dir. Özel olarak her P, Q  E[m] için em(P, Q) = em(Q, P)1 dir. iii) em eşleştirmesi dejenere değildir, yani her Q  E[m] için em(P, Q) = 1 ise Q = O dur. iv) em eşleştirmesi Galois değişmezidir, yani G(K /K), K cisminin K cismi üzerinde Galois grubu olmak üzere her   G(K /K) için em(P, Q) = (em(P, Q)) dir. v) em eşleştirmesi uyumludur, yani her P  E[mm'] ve Q  E[m] için emm' (P, Q) = em (m'P, Q) dur (Silverman 2009). 3.10.4. Örnek. Şimdi Weil eşleştirmesi tanımını kullanarak E : y2 = x3 + ax + b = (x  1)(x  2)(x  3) eliptik eğrisi için e2 değerini hesaplayalım. Dikkat edilirse yukarıdaki eşitliğin sol tarafında x2 li terim olmadığından 1 + 2 + 3 = 0 dır. Diğer yandan P1 = (1, 0), P2 = (2, 0) ve P3 = (3, 0) noktalarının mertebesi 2 olduğundan div(x  i) = 2[Pi]  2[O] dur. e2(P1, P2) değerini hesaplamak için E eliptik eğrisi üzerinde keyfi bir S = (x, y) noktası alalım. Eliptik eğriler üzerindeki toplama işlemi formülleri kullanılırsa P1  S noktasının x-koordinatı bulunabilir. Buna göre   71   2 2 x(P1  S) =   y    x  = y  (x  1) (x  1) x 1   1  (x  1) 2 dir. Eğer y2 = (x  1)(x  2)(x  3) olduğu dikkate alınırsa x(P S) = (x  1)(x  2 )(x   )  (x   ) 2 (x   23 1 1) (2 3)x23 1 1  (x   2 = 1) x 1 dır. Son olarak 1 + 2 + 3 = 0 olduğundan 2 x(P1  S) = 1x23  1 x  1 olarak bulunur. Benzer biçimde  x   2x(P + S) = 2 1 3 22 x  2 olarak elde edilir. Şimdi e2(P1, P2) değerini hesaplayalım. Bunun için fP = x  i rasyonel fonksiyonlarını i kullanalım ve P1 ve P2 noktalarının E[2] de sıfırdan ve birbirinden farklı noktalar olduğu varsayalım. O halde em eşleştirmesinin tanımından f (P  S) f (P S) e (P , P ) = P1 2 P2 12 1 2 fP (S) fP (S)1 2 = X (P2  S)  a1 X (P1  S)  a2 X (S)  a1 X (S)  a2  x   2  x   22 1 3 2  1 2 3 11 2                                   x 2 x 1   x 1 x 2 eşitliği elde edilir. Bu eşitlik yeniden düzenlenir ve 1 + 2 + 3 = 0 olduğu kullanılırsa   e (P , P ) = (2  1)x   2 2   2 1 2 1 2 =  1 (1  2 )x  2  21 2 olarak bulunur (Hoffstein ve ark. 2008).   72 3.11. Gömme Derecesi ve MOV Algoritması Weil eşleştirmesinin asal kuvvet mertebeli F k cisimlerinde çalışıldığı birçok p uygulaması vardır. Bu kısımda bu uygulamalardan biri olan MOV algoritmasından bahsedilecektir. Bu algoritma E(Fp) grubu üzerinde tanımlı olan EEALPni F pk   cismindeki ALPne indirgediğinden etkili bir algoritmadır. MOV algoritmasını daha iyi anlayabilmek için aşağıdaki tanıma ihtiyacımız vardır. 3.11.1. Tanım. E, Fp sonlu cismi üzerinde tanımlı bir eliptik eğri, m  1 bir tamsayı olmak üzere p | m olsun. E (F k ) [m]  Z/mZ  Z/mZ p olacak şekildeki en küçük k değerine E eliptik eğrisinin m ye göre gömme derecesi denir. Aşağıdaki önermede bir E eliptik eğrisinin gömme derecesinin nasıl belirlendiği görülmektedir. 3.11.2. Önerme. E, Fp sonlu cismi üzerinde tanımlı bir eliptik eğri ve l  p bir asal sayı olsun. E(Fp) grubunda l mertebeli bir nokta olduğunu varsayalım. Bu durumda, E eliptik eğrisinin l asal sayısına göre gömme derecesi aşağıdakilerden biridir: a) l < p + 1 ise E eliptik eğrisinin gömme derecesi 1’dir. b) p ≡ 1 (mod l) ise gömme derecesi l’dir. c) p  1 (mod l) ise gömme derecesi pk ≡ 1 (mod l) olacak şekildeki en küçük k  2 değeridir (Hoffstein ve ark. 2008).   73 E eliptik eğrisinin k gömme derecesi, E(Fp) üzerindeki EEALPni F k sonlu cismindeki p ALPne indirgediğinden oldukça önemlidir. Buna göre, E, Fp sonlu cismi üzerinde tanımlı bir eliptik eğri ve l > p + 1 bir büyük asal sayı olmak üzere P  E(Fp) noktasının mertebesi l olsun. E eliptik eğrisinin l ye göre gömme derecesi k olmak üzere F k sonlu cismi üzerinde ayrık logaritma probleminin nasıl çözüldüğünün bilindiğini p varsayalım ve Q  E(Fp), P noktasının bir katı olsun. Bu durumda aşağıda verilen Menezes, Okamoto ve Vanstone (1993) tarafından verilen MOV algoritması P ve Q noktaları için eliptik eğri ayrık logaritma problemini çözer. Burada E(Fp) grubunda l mertebeli bir P noktası olduğundan N = #E( F k ) denirse l | N dir. p 3.11.3. MOV Algoritması Input: l > p + 1 özelliğinde bir asal sayı, mertebesi l olan bir P  E(Fp) noktası, E eliptik eğrisinin l ye göre gömme derecesi k, P noktasının bir katı olan Q  E(Fp) noktası. 1) N = #E (F k ) noktalarının sayısını hesapla. p 2) T  E(Fp) olacak şekilde rastgele bir T  E (F k ) noktası seç. p 3) T ' = (N/l)T değerini hesapla. 4) Eğer T ' = O ise 2. adıma git. 5) T ', l mertebeli bir nokta ise 6. adıma git. 6)  = el(P, T ')  F *k ve  = el(Q, T ')  F * k Weil eşleştirmelerini hesapla. Eğer  = p p 1 ise 2. adıma dön.  7) F *k grubunda  ve  için ALPni çöz, yani  =  n olacak şekilde bir n kuvveti bul. p 8) O halde Q = nP dir ve böylece EEALP çözülmüş olur.   74 3.11.4. Uyarı 1. Yukarıda verilen MOV algoritması EEALPni çözer. Gerçektende, algoritmada kullanılan T ' noktası P noktasından bağımsız olduğundan {T ', P} kümesi rankı 2 olan serbest Z/lZ-modül E[l] için bir bazdır. Hatırlanacağı gibi Weil eşleştirmesi dejenere değildir, dolayısıyla el(P, T ') Weil eşleştirmesi F *k da bir birimin (aşikardan p farklı) l. köküdür. Bir başka değişle e (P, T ')rl = 1 olması için gerek ve yeter koşul l r olmasıdır. Eğer Q = jP olduğu varsayılır ve j sayısının l modülüne göre değeri bulunmak istenirse MOV algoritması el(Q, T ') = el(P, T ')n eşitliğini gerçekleyen bir n tamsayısını bulur. Weil eşleştirmesinin lineer olduğu kullanılarak el(P, T ')n = el(Q, T ') = el(jP, T ') = el(P, T ')j eşitlikleri elde edilir ve böylece el(P, T ')n j = 1 dir. Bu ise P ve Q noktaları için n ≡ j (mod l) değerinin EEALPni çözdüğünü gösterir. 2. MOV algoritmasının kullanışlı olup olmadığı k sayısına bağlıdır. Eğer k sayısı yeterince büyük, yani k  (ln p)2 ise MOV algoritmasını çözmek kolay değildir, yani bu algoritma kullanışlı değildir. Örneğin p  2160 olarak alınırsa k  4000 olmak üzere ALPni F k de çözmek gerekir. Fp cismi üzerinde tanımlı rastgele seçilen herhangi bir E p eliptik eğrisinin gömme derecesi (ln p)2 den daha büyük olabileceğinden MOV algoritması kullanışlı değildir. Ancak bu algoritmanın kullanışlı olduğu, yani gömme derecesi küçük olan eliptik eğriler vardır. Aşağıdaki tanımda bu eğriler isimlendirilmiştir. 3.11.5. Tanım. E, Fp cismi üzerinde tanımlı bir eliptik eğri olmak üzere E[p] = {O} ise E eliptik eğrisine bir süpersingüler eliptik eğri denir.   75 3.11.6. Uyarı. p  5 bir asal sayı olmak üzere Fp cismi üzerinde tanımlı E eliptik eğrisinin süpersingüler olması için gerek ve yeter koşul #E(Fp) = p + 1 olmasıdır. Bundan başka süpersingüler eğrilerin gömme dereceleri genellikle k = 2 veya k  6 dır. Örneğin E : y2 = x3 + x eğrisi, herhangi p ≡ 3 (mod 4) asal sayısı için süpersingülerdir ve üstelik bu eğrinin gömme derecesi herhangi l  p + 1 sayısı için 2’dir. Bu ise E(Fp) deki EEALPni çözmenin F *2 daki ALPni çözmekten daha zor olmadığını gösterir. p   76 4. BULGULAR VE TARTIŞMA Bu bölümde eliptik eğrilerle eşleşen diziler ve eliptik eğri ayrık logaritma problemi arasındaki ilişkiler ortaya konularak eliptik eğri ayrık logaritma problemini daha kolay bir ayrık logaritma problemine dönüştüren iki algoritma verilecektir. 4.1. Eliptik Eğrilerle Eşleşen Diziler ve Eliptik Eğri Ayrık Logaritma Problemi 3. Bölümde görüldüğü gibi, E, karakteristiği 2’den farklı bir F cismi üzerinde tanımlı bir eliptik eğri ve P  E(F) olmak üzere n  1 tamsayısı için P noktasının n katı nP,  nP =  Gn (P) , Hn (P)     Fn (P) 2 Fn (P) 3   olarak yazılabilir. Silverman (Silverman, 2005), Fq sonlu cismi üzerinde tanımlı E eliptik eğrisinin bölüm polinomlarının P  E(Fq) noktasında hesaplanan değerlerinin (Fn(P))n≥0 dizisinin periyodik olduğunu göstermiştir. Shipsey ve Swart (2008), (Fn(P))n≥0 dizisinin periyodiklik özelliklerini kullanarak EEALPni çözmek için alternatif bir algoritma vermişlerdir. Gezer ve Bizim (2019), Fq sonlu cismi üzerinde tanımlı E eliptik eğrisinin P  E(Fq) noktasından elde edilen bölüm polinomlarının değerlerinin (Gn(P))n≥0 ve (Hn(P))n≥0 dizilerinin periyodik olduğunu göstermişlerdir. Bu kısımda (Gn(P))n≥0 ve (Hn(P))n≥0 dizilerinin periyodiklik özelliklerini kullanarak EEALPni çözmek için Shipsey ve Swart’ın algoritmasına benzer algoritmalar verilecektir. Silverman (2005), (Fn(P))n≥0 dizisinin periyodik olduğunu ve bu dizinin aşağıdaki teoremde verilecek olan simetri özelliklerini gerçeklediğini ispatlamıştır. 4.1.1. Teorem. E, Fq sonlu cismi üzerinde tanımlı bir eliptik eğri, P  E(Fq) N ≥ 3 mertebeli bir nokta olmak üzere (Fn(P))n ≥0, E eliptik eğrisinin bölüm polinomlarının P   77 noktasında hesaplanan değerlerinin dizisi olsun. Bu durumda, P noktasına bağlı olarak aN = b2 ve her k, t ≥ 0 için F kt k 2 kN + t(P) = a b Ft(P) (4. 1) olacak biçimde a, b  F *q birimleri vardır (Silverman 2005). Gezer ve Bizim (2019), (Gn(P))n≥0 ve (Hn(P))n≥0 dizilerinin simetri özelliklerini gerçeklediğini göstermişlerdir. 4.1.2.Teorem. E, Fq sonlu cismi üzerinde tanımlı bir eliptik eğri, P  E(Fq) N ≥ 3 mertebeli bir nokta olmak üzere (Gn(P))n≥0 ve (Hn(P))n≥0, E eliptik eğrisinin bölüm polinomlarının P noktasında hesaplanan değerlerinin dizileri olsun. Bu durumda, P noktasına bağlı olarak aN = b2 ve her k, t ≥ 0 için 2 GkN + t(P) = a 2kt b 2k Gt(P) (4. 2) H (P) = a 3kt 2 kN + t b 3k Ht(P) (4. 3) olacak biçimde a, b  F *q birimleri vardır (Gezer ve Bizim 2019). 4.1.3. Algoritmalar Shipsey ve Swart (2008), |E(Fq)| = q ‒ 1 olduğunda Teorem 4.1.1’i kullanarak EEALPni çözmek için alternatif bir algoritma vermişlerdir. Bu kısımda (Gn(P))n ≥ 0 ve (Hn(P))n ≥ 0 dizilerinin simetri özellikleri kullanılarak E(F ) grubundaki bir EEALPni F * q q grubundaki kolay bir ALPne indirgeyen iki algoritma verilecektir. E, Fq sonlu cismi üzerinde tanımlı bir eliptik eğri, P, Q  E(Fq) olmak üzere Q = mP olsun. P  E(Fq) noktasının mertebesi N ≥ 3, E(Fq) grubunun mertebesi q ‒ 1 olmak   78 üzere N sayısı q ‒ 1 sayısının bir büyük asal çarpanı olsun. Bu durumda l bir küçük tamsayı olmak üzere q ‒ 1 = lN biçiminde yazılabilir. O halde Teorem 4.1.2. gereği, 2 2 2 Gmq(P) = G (P) = a 2lm b 2l mm + mlN Gm(P), G 2l (m1) 2 2l2 (m1)2 (m + 1)q(P) = G(m + 1) + (m + 1)lN (P) = a b Gm + 1(P) dir. Yukarıdaki eşitlikler yeniden düzenlenirse G (P)G (P) 2 2 (m1)q m = a 2l(2m + 1) b 2l (2m1) Gmq (P)Gm1(P) 2 = (a 2l b2l ) 2m + 1 (4. 4) 2 olduğu elde edilir. (3.2) ve (4. 2) gereği, (a2l b2l ) = Gq(P)/G1(P) = Gq(P)/x(P) olduğundan (4.4) eşitliği G (P) 2m1  G  q  = (m1)q (P)Gm (P)   (4. 5)  x(P)  Gmq (P)Gm1(P) biçiminde yeniden yazılabilir. Dikkat edilirse m sayısı bilinmediğinden eşitliğin sağ tarafındaki herhangi bir değer hesaplanamaz. Diğer yandan (3.1) eşitliğinden Gn(P) = x(nP)F (P)2 n olduğu elde edilir. Dolayısıyla Gm(P) = x(mP) Fm(P)2 = x(Q) F (P)2, m (4.6) Gm + 1(P) = x((m + 1)P) Fm + 1(P)2 = x(Q + P) Fm + 1(P)2, (4.7) Gmq(P) = x(mqP) Fmq(P)2 = x(qQ)F (P)2mq , (4.8) ve mP = Q ve (m + 1)P = P + Q olduğundan G (P) = x((m + 1)qP) F (P)2 (m + 1)q (m + 1)q = x(q(Q + P))F 2(m + 1)q(P) (4.9) dır. Diğer yandan Lemma 3.3.2 gereği, 2 2 Fmq(P) = F (P) qm Fq(mP) = Fm(P) q Fq(Q) (4.10) dir ve mP = Q ve (m + 1)P = P + Q olduğundan 2 2 F(m + 1)q(P) = Fm +1(P) q Fq((m + 1)P) = Fm + 1(P) q Fq(Q + P) (4.11)   79 olduğu elde edilir. Böylece (4. 10) ve (4. 11) eşitlikleri kullanılarak (4. 8) ve (4. 9) teki eşitlikler 2 Gmq(P) = x(q(Q)Fm(P) 2q F (Q)2q (4. 12) ve 2 G(m + 1)q(P) = x(q(Q + P)Fm + 1(P) 2q Fq(Q + P)2 (4. 13) olarak yeniden yazılabilir. Şimdi (4. 11), (4. 12) eşitlikleri ve daha sonra (4. 6) ve (4. 7) eşitlikleri (4. 5) eşitliğinde yazılırsa 2 Gq (P) 2m1   x(q(QP))Fm 1(P) 2q Fq (QP) 2 Gm (P)    = 2  x(P)   x(qQ )F (P) 2q F (Q )2 G (P) m q m1  2(q2 1) 2  F (P)     F (QP)  =  m1   x(q(QP)) x(Q)   q   Fm (P)     x(qQ )x(QP)    Fq (Q)  eşitliği elde edilir. Dolayısıyla F *q grubunun mertebesi q ‒ 1 olduğundan G (P) 2m1 2   q    =  x(q(QP)) x(Q)   Fq (QP)     x(P)    x(qQ )x(QP)   Fq (Q)  olarak bulunur. Böylece Gq(P) = x(qP) Fq(P)2 olduğundan son eşitlik 2 m 2 G  q (P)    =  x(q(QP)) x(Q)    Fq (QP)     x(P)     x(P)       x(qQ )x(QP)    F    q (Q)  Gq (P)  2    F (QP)  =  x(q(QP)) x(Q)x(P)   q    x(qQ )x(qP)x(QP)   Fq (Q) Fq (P)  olarak yeniden yazılabilir. Dikkat edilirse bu eşitliğin sağ tarafı hesaplanabilir. Böylece indeks hesabı yöntemi ile çözülebilecek bir αm = β ayrık logaritma problemi elde edilir.   80 Benzer biçimde (Hn(P))n ≥0 dizisinin periyodik özelliklerinden bir F * q ALP eşitliği elde edilebilir. Böylece Teorem 4.1.2 kullanılarak ve yukarıdakine benzer biçimde hareket edilerek 2 m  3  Hq (P)     =  y(q(QP)) y(P)y(Q)    Fq (PQ)   y(P)             y(qQ )y(qP)y(P Q)   Fq (P) Fq (Q)  F * q ALP eşitliği elde edilir. Böylece başka bir γ m =  ALP elde edilir. 4.1.4. Uyarı. G(1)(P) = x(P) olduğundan Teorem 4.1.2 gereği, G 2l 2l2q (P) = G 2 lN1(P) = a b x(P) = a2l b2l x(P) x(P) x(P) olarak bulunur. Şimdi aN = b2 olduğundan Teorem 4.1.2 gereği, Gq (P) 2= a2l (b2 )l = a2l 2 aNl = a2l (aNl)l = a2l (aq ‒ 1)l = a2l x(P) dir. Diğer yandan, F * da a2lN = a2(q ‒ 1)q = 1 olduğundan a 2 nin mertebesi N sayısını G (P) böler. N bir asal sayı olduğu için q nin mertebesi 1 ya da N olabilir. Eğer mertebe x(P) G (P) 1 ise saldırı başarısız olur. Ancak Shipsey ve Swart’ta olduğu gibi q = 1 olma x(P) H (P) olasılığı 1 dir. Benzer biçimde q = 1 olma olasılığı da 1 dır. N y(P) N Şimdi aşağıdaki konjektürü verebiliriz. 4. 1. 5. Konjektür. E, Fq sonlu cismi üzerinde tanımlı bir eliptik eğri ve P  E(Fq) noktasının mertebesi N olmak üzere E(Fq) grubunun mertebesi q ‒ 1 ise Gq (P) H (P) = 1 (ya da q = 1) x(P) y(P) olma olasılığı 1 dir (Gezer ve Turp 2019). N   81 5. SONUÇ Bu çalışmada ayrık logaritma problemi ve bu problemin çözümleri ele alınmıştır. Ayrık logaritma problemi birçok kriptografik yapıda kullanılmaktadır. Bu problemin çözümünün zorluk derecesi üzerinde çalışılan grubu bağlıdır. Örneğin, ayrık logaritma probleminin (Fp, +) grubundaki çözümü oldukça kolaydır. Bununla birlikte ALPnin çözümü (F *p , ) grubu için zordur. Buna göre O(p) mertebeli bir grupta ayrık logaritma problemi O( p ) adımda çözülebilir. F * p grubunda bu problemi çözmek için bilinen en iyi algoritma indeks hesabı yöntemidir ve bu yöntem ALPni c belli bir sabit olmak üzere exp(c3 (log p)(loglog p)2 ) zamanda çözer. Bu zaman altüstel zaman olarak bilinmektedir. Genel olarak ALPnin üstel bir zamanda çözülebileceği bir G grubu alınır. Bu çalışmada ayrık logaritma problemi özellikle F *p sonlu grubu ve sonlu bir cisim üzerinde tanımlı bir eliptik eğrinin üzerindeki noktaların oluşturduğu E(Fp) grubu için ele alınmıştır. Literatürde EEALPni daha kolay bir ALPne dönüştüren algoritmalar verilmektedir. Çalışmada eliptik eğriler ile eşleşen diziler ve eliptik eğri ayrık logaritma problemi arasındaki ilişkiler ortaya konulmuş ve EEALPni daha kolay bir ALPne dönüştüren iki algoritma verilmiştir. Daha sonra konu ile ilgili bir konjektür verilmiştir.   82 KAYNAKLAR Diffie, W., Hellman, M.E. 1976. New directions in cryptography, IEEE Trans. Information Theory, 22(6): 644-654. Elgamal, T. 1985. A public key cryptosystem and a signature scheme based on the discrete logarithms. IEEE Trans. Information Theory, 31(4): 469-472. Fraleigh, J. B. 2003. A first course in abstract algebra. Addison-Wesley, 513 pp. Gezer, B., Bizim, O. 2019. Sequences generated by elliptic curves. Acta Arithmetica, 188(3): 253-268. Gezer, B., Turp, S. 2019. The elliptic curve discrete logarithm problem and sequences associated to elliptic curves. Journal of Mathematical Cryptology adlı dergiye sunuldu. Hoffstein, J., Piper, J., Silverman, J. H. 2008. An introduction to mathematical cryptography. Springer, New York, USA, 523 pp. Koblitz, N. 1987. Elliptic curve cryptosystems. Math. Comp., 48(177): 203-209. Mazur, B., Tate, J. 1991. The p-adic sigma function. Duke Math. J., 62: 663-688. Menezes, A. J., Okamoto, T., Vanstone, S. A. 1993. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inform. Theory, 39(5):1639- 1646. Miller, V. S., 1986. Use of elliptic curves in cryptography: In advances in cryptology- Crypto’85 (Santa Barbara, CA), volume 218 of lecture notes in comput. sci., Ed., Williams, H. C., Berlin, Germany, pp: 417-426. Rivest, R. L., Shamir, A., Adleman. L. 1978. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21(2):120-126. Schoof, R., 1985. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp. 44(170): 483-494. Shipsey, R., Swart, C. 2008. Elliptic divisibility sequences and elliptic curve discrete logarithm problem, Cryptology ePrint Archieve. https://eprint.iacr.org/2008/444.pdf- (Erişim tarihi: 12.04.2019). Shoup, V. 2001. OAEP reconsidered. In advances in cryptology-Crypto 2001 (Santa Barbara, CA), volume 2139 of lecture notes in comput. sci., Ed., Williams, H. C., Berlin, Germany, pp: 239-259. Silverman, J. H. 2005. p-adic properties of division polynomials and elliptic divisibility sequences, Math. Ann., 332: 443-471, addendum 473-474.   83 Silverman, J. H. 2009. The arithmetic of elliptic curves. Springer, New York, USA, 513 pp. Silverman, J. H., Tate J. 1994. Rational points on elliptic curves, Springer, New York, USA, 267 pp. Washington, L. C. 2003. Elliptic curves: Number theory and cryptography. Chapman & Hall / CRC, Boca Raton, FL, 428 pp. Western, A. E., Miller, J. C. P. 1968. Tables of indices and primitive Roots: Royal Society Mathematical Tables, Vol. 9. Cambridge University Press, London, UK, 440 pp.   84 ÖZGEÇMİŞ   Adı Soyadı : Semiha TURP Doğum Yeri ve Tarihi : BURSA – 10.08.1993 Yabancı Dili : İngilizce Eğitim Durumu (Kurum ve Yıl) Lise : İMKB Gürsu Anadolu Lisesi -2011 Lisans : Uludağ Üniversitesi -2016 Yüksek Lisans : Uludağ Üniversitesi Fen Bilimleri Enstitüsü-2019 Çalıştığı Kurum/Kurumlar ve Yıl : İletişim (e-posta) : semihaturp@outlook.com Yayınları : The elliptic curve discrete logarithm problem and sequences associated to elliptic curves. Journal of Mathematical Cryptology adlı dergiye sunuldu.   85