Biraz hack yapalım. (RSA şifrelerini hack liyoruz)

[John Ahmet]

RSA, güvenliği tam sayıları çarpanlarına ayrımanın algoritmik zorluğuna dayanan bir tür

Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.

yöntemidir. 1978’de

Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.

,

Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.

ve

Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.

tarafından bulunmuştur. Bir RSA kullanıcısı iki büyük asal sayının çarpımını üretir ve seçtiği diğer bir değerle birlikte ortak anahtar olarak ilan eder. Seçilen asal çarpanları ise saklar. Ortak anahtarı kullanan biri herhangi bir mesajı şifreleyebilir, ancak şu anki yöntemlerle eğer ortak anahtar yeterince büyükse sadece asal çarpanları bilen kişi bu mesajı çözebilir. RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problemdir.

Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.

İsteyen arkadaşlar forumdaki RSA Kriptolama - Mühendis Beyinler yazısını da okuyabilir. Kullandığım değişkenlerin isimlerini vikipedi örnek algoritmasına göre seçtim.

Yukarıdaki vikipedi linkinde anlatılan RSA algoritması ile ilgili C# ile örnek bir kod hazırladım. Bu örnek kodda secret değişkeninde tuttuğumuz 12345 değerini hazırladığımız RSA sınıfındaki methodlarla önce şifreliyoruz sonra bu şifrelenmiş veriyi özel anahtarı kullanarak çözüyoruz.

İsteyen arkadaşlar forumdaki RSA Kriptolama - Mühendis Beyinler yazısını da okuyabilir. Kullandığım değişkenlerin isimlerini vikipedi örnek algoritmasına göre seçtim.

Daha sonra RSAHacking sınıfındaki GetSecretValue methodu ile özel anahtar kullanmadan genel anahtarı kullanarak hack liyoruz.

Elbette gerçek hayatta anahtarlar oluşturulurken bu kadar küçük sayılar seçilmiyor. Bir RSA şifresinin genel anahtarla çözülmesine örnek olması bakımından kodu çok basit tutmaya çalıştım. Umarım bu konuya merak duyan arkadaşlara faydalı olabilmişimdir.

Örnek kodu aşağıda paylaşıyorum. Örnek kodda (x ^ y ) mod z değerlerini hesaplamak için BigInteger sınıfı kulanılmıştır. Çalıştırmada sorun yaşayan arkadaşlar Solution Explorer da References yazısına sağ tıkladıktan sonra Add Reference ' e tıklayıp açılan penceredeki listede System.Numerics başlığının solundaki işaret kutusunu işaretleyip tamama tıkladıktan sonra sorun yaşamadan çalıştırabilirler.

RSA çok büyük tam sayılarla işlem yapmanın zorluğuna dayanan bir tekniktir. Yani, RSA algoritmasını kullanan kişi 2 büyük asal sayı seçer ve bunları saklar. Bu iki asal sayının çarpımı elde edip, random seçtiği başka bir değer ile birlikte ortak anahtar olarak belirler. Ortak anahtarı kullanan başka bir kullanıcı şifreleme yapabilir bu durumda bu mesajın şifresinin çözülüp anlamlı hale getirilebilmesi için ortak anahtar yeterince büyük olduğundan bu büyük sayının ortak çarpanlarının bilinmesi gerekir. Yani aslında RSA çarpanlara ayırma ile birebir ilişkilidir ki bu algoritma açık anahtarlı şifrelemeyi kullanır. Açık anahtarlı şifrelemede (asimetrik şifreleme) açık anahtarla şifreleme ve gizli anahtarla deşifreleme yapılmasını kolayca gerçekleştirilirken; yalnızca açık anahtarı (iki sayının çarpımını ) bilerek gizli anahtarın bulunmasını zor kılar (büyük olan bu sayının çarpanlarının bilinmesi gerekir). RSA 3 basamakta gerçekleştirilir. Bunlar: anahtar üretimi (2 büyük asal sayının çarpımı ve random seçilmiş bir sayı ile ortak anahtar üretilmesi), şifreleme (Oluşan ortak anahtarı kullanan başka bir kullanıcı şifreleme yapabilir) ve şifre çözmedir (Şifrenin çözülmesi için ortak anahtarın çarpanlarının bilinmesi gerekir). Özet olarak; tamamen random olarak ve birbirine yakın iki asal sayı seçilir. Bu sayılar tutulur. Mod n olacak şekilde ; n=p*q ve m(=(p-1)*(q-1) çarpımları hesaplanır. 1<e<m arasında bir e tamsayısı seçilir. Öyle ki e ve m’nin en büyük ortak böleni 1 olsun. Genel üs olarak kullandığımız e ve m sayıları kullanılarak gizli üs d hesaplanır (1<d<m) (Örneğin ed ≡ 1(mod m)). Genel anahtar (n,e) ve özel anahtar (n,d)’dir. p,q ve m değerleri de gizli tutulmalıdır.

Bu video da konuyu anlamak açısından faydalı olabilir.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace RSATest
{
    class Program
    {
        static void Main(string[] args)
        {
            ulong secret = 12345;

            Console.WriteLine("secret value is {0}", secret);
            Console.WriteLine();

            var privateKey = Key.Generate();
            var publicKey  = Key.GetPublicKey(privateKey);

            Console.WriteLine(privateKey);
            Console.WriteLine(publicKey);
            Console.WriteLine();

            var encrypted = RSA.Encryption(secret, publicKey);
            var decrypted = RSA.Decryption(encrypted, privateKey); // Normal şartlarda mesajı yalnızca private key i bilen kişi çözebilir.

            Console.WriteLine("encrypted value is {0}", encrypted);
            Console.WriteLine("decrypted value is {0}", decrypted);
            Console.WriteLine();


            Console.WriteLine(); Console.WriteLine();

             Console.WriteLine("Hacking please wait...");

            Console.WriteLine("secret value is {0}", RSAHacking.GetSecretValue(encrypted, publicKey));

            Console.ReadLine();
        }
    }

    public class RSAHacking
    {

        // Dikkat edin public key den gizli değeri buluyoruz. PrivateKey değil.
        public static ulong GetSecretValue(ulong encrypted, PublicKey key)
        {
            var n = key.n;

            ulong sqrtn = (ulong)Math.Floor(Math.Sqrt((double)n));
            Console.WriteLine("n value is {0}", n);
            Console.WriteLine("sqrt(n) = {0}", sqrtn);
            var primes = new Primes(Key.MAX_PRIME).Where(prime => prime <= sqrtn).ToList();
            var count = primes.Count;
            ulong p = 0, q = 0;
            // Burada n sayıyını asal çarpanlarına ayırıyoruz.
            for (int i = count - 1; i >= 0; i--)
                if (n % primes[i] == 0)
                {
                    p = primes[i];
                    q = n / primes[i];
                    break;
                }

            Console.WriteLine("p and q found. {0} and {1}", p, q);
   
            var totient = (p - 1) * (q - 1);

            Console.WriteLine("totient value is {0}", totient);

            var e = key.Value;
            ulong d = 0;

            while ((d * e) % totient != 1)
                d++;
            Console.WriteLine("d value is {0}", d);

            return (ulong)BigInteger.ModPow(encrypted, d, key.n);
        }
    }

    // RSA sample
    public class RSA
    {
        public static ulong Encryption(ulong value, PublicKey key)
        {
            return (ulong)BigInteger.ModPow(value, key.Value, key.n);
        }

        public static ulong Decryption(ulong decrypted, Key key)
        {
            return (ulong)BigInteger.ModPow(decrypted, key.d, key.n);
        }

        public static Key GenerateKey()
        {
            return Key.Generate();
        }

        public static PublicKey GetPublicKey(Key key)
        {
            return Key.GetPublicKey(key);
        }
    }

    public class PublicKey
    {
        public ulong Value { get; set; }
        public ulong n { get; set; }

        public override string ToString()
        {
            return string.Format("PublicKey {{ Value = {0}, n = {1} }}", Value, n);
        }
    }

    // PrivateKey
    public class Key: PublicKey
    {
        public ulong p { get; set; }
        public ulong q { get; set; }
        public ulong d { get; set; }

        public const ulong MAX_PRIME = 1000000;
        private const int RANDOM_MIN = 1024;
        private const int RANDOM_MAX = 2048;
        private const int RANDOM_DIFF = 127;

        public static Key Generate()
        {
            int pi = 0, qi = 0;

            pi = new Random().Next(RANDOM_MIN, RANDOM_MAX); // RANDOM_MIN ve RANDOM_MAX aralığında rastgele bir sayı seçiyoruz.

            qi = new Random().Next(pi - RANDOM_DIFF, pi + RANDOM_DIFF); // seçtiğimiz sayıya yakın rastgele bir sayı daha seçiyoruz.

            var primes = new Primes(MAX_PRIME).ToList(); // MAX_PRIME değerinden küçük asalları liste olarak hazırlıyoruz.

            ulong p = primes[pi]; // (pi + 1). asal sayı
            ulong q = primes[qi]; // (qi + 1). asal sayı

            var totient = getTotient(p, q); // (p - 1) * (q - 1)

            // e sayımızı seçiyoruz. (1 < e < totient) olmalı
            var selectedPrimes = primes.Where(prime => prime < totient).ToList(); // totient değerinden küçük asallar seçiliyor
            var ei = new Random().Next(0, selectedPrimes.Count()); // Seçeceğimiz asalın indisi olacak bir rastgele sayı belirliyoruz.
            ulong e = selectedPrimes[ei];
   
            ulong d = 0;
            while ((ulong)(d * e) % totient != 1) // (d * e) mod totient = 1 olmalı
                d++;

            return new RSATest.Key { Value = e, n = p * q, p = p, q = q, d = d }; // Private Key oluşturuluyor.
        }

        public static PublicKey GetPublicKey(Key key)
        {
            return new PublicKey { Value = key.Value, n = key.n };
        }

        private static ulong getTotient(ulong p, ulong q)
        {
            return (p - 1) * (q - 1);
        }

        public override string ToString()
        {
            return string.Format("PrivateKey {{ Value = {0}, n = {1}, p={2}, q={3}, d={4} }}", Value, n, p, q, d);
        }
    }

    /***********************************************************************************
     * Asal sayıları bir dizi şeklinde getirir. (limit değerinden küçük olanları)      *
     * Getting primes by enumerable. Developed by Ayhan ARICAN email: [email protected] *
     * ********************************************************************************/
    public class Primes : IEnumerable<ulong>
    {
        private ulong limit;
        private ulong count;
        private bool[] numbers;
        private DateTime startTime;
        private TimeSpan calculatationDuration;

        public Primes(ulong limit)
        {
            this.count = 0;
            this.limit = limit;
            this.numbers = new bool[limit];
            startTime = DateTime.Now;
            findPrimes(); // limit değerinden küçük bütün asallar bu method ile bulunuyor.
            calculatationDuration = DateTime.Now - startTime; // süre hesaplanıyor
        }

        private void findPrimes()
        {
            // Şu an numbers dizisinin tüm elemanları false değerindedir.
            // limitten küçük bütün tek sayılar true yapılıyor (1 hariç çünkü artık asal olarak kabul edilmiyor).
            for (ulong i = 3; i < limit; i += 2) numbers[i] = true;
            // 2 çift olan yegane asal sayıdır (özel durum).
            if (limit > 2) numbers[2] = true;
            // 3 ten itibaren bütün tek sayılar dolaşılıyor.
            for (ulong j = 3; j * j <= limit; j += 2)
            {
                if (numbers[j])//is true
                    // Tek sayıların tek katları asal olmadığından değerler false yapılıyor.
                    for (ulong p = 3; (p * j) < limit; p += 2)
                        numbers[p * j] = false;
            }
        }

        public IEnumerator<ulong> GetEnumerator()
        {
            for (ulong i = 2; i == 2; i++)
                if (numbers[i])
                    yield return i;
            for (ulong i = 3; i < limit; i += 2)
                if (numbers[i])
                    yield return i;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }


        public ulong Count
        {
            get
            {
                if (count == 0)
                {
                    if (limit > 2) count++;
                    for (ulong i = 3; i < limit; i += 2)
                        if (numbers[i]) count++;

                    return count;
                }
                else return count;
            }
        }

        public bool[] Numbers { get { return numbers; } }
        public TimeSpan CalculationDuration { get { return calculatationDuration; } }
    }
}

Örnek kodun tamamını bu linkten download edebilirsiniz.

Linki görmek için izniniz yoktur Giriş yap veya kayıt ol.

 

[arasosman]

Teşekkürler