RSA şifrelerini hackliyoruz (RSA bankalar, web ssl ve daha bir çok alanda kullanılmaktadır)

[ayhanarican]

RSA, güvenliği tam sayıları çarpanlarına ayrımanın algoritmik zorluğuna dayanan bir tür Açık anahtarlı şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman 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.

https://tr.wikipedia.org/wiki/RSA_Algoritması

Yukarıdaki vikipedi linkinde anlatılan RSA algoritması ile ilgili C# kullanarak örnek bir kod hazırladım. Bu örnek kodda secret değişkeninde tuttuğumuz 16777215 değerini hazırladığımız RSA sınıfındaki methodlarla önce şifreliyoruz sonra bu şifrelenmiş veriyi özel anahtarı kullanarak çözüyoruz. Bu sistemde her 4 byte ta en fazla 3 byte saklayabiliyoruz. 16777215 değerinden büyük sayıları sağlıklı şekilde şifreleme konusunda garanti veremiyorum.

Kullandığım değişkenlerin isimlerini vikipedi örnek algoritmasına göre seçtim.

Algoritma Fermat teoremini kullanmaktadır.

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. Ancak videoda arkadaş şifreli verinin public key ile çözülebileceğini bilerek veya bilmeyerek söylüyor. Bu yazımda arkadaşı doğrulasamda RSA şifrelemenin amacı public key ile bu şifrenin çözülemeyeceğini garanti etmek için hazırlanmıştır. Karşılıklı yapılan şifreli bir dialogta şifreleme karşı tarafın ürettiği key ile yapıldığından kişi kendine gelen şifreli metni kendi private key ini kullanarak çözer. SSL buna en güzel örnektir.

Bu konu ile ilgili aklınıza takılan bir soru veya bir düşünce varsa paylaşabilirsiniz. Ayrıca RSA sınıfını kendi hazırladığı kod ile çalıştırabilen Türkiye'de bu konu ile ilgili yazılmış bir kod görmedim. Bu bakımdan paylaşımın önemli olduğunu düşünüyorum. Eğer böyle bir paylaşım daha önce gördüyseniz lütfen benimle paylaşın.

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

namespace RSATest
{
    class Program
    {
        static void Main(string[] args)
        {
            uint secret = uint.MaxValue / 256; // 16777215 max verilebilecek değer.

            Console.WriteLine(); Console.WriteLine();
            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);

            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();
            Console.WriteLine("secret value is {0}", RSAHacking.GetSecretValue(encrypted, publicKey));


            // 10 adet private key üretiliyor
            // RSA da private key üretmek çok zaman alan bir işlemdir.
            Console.WriteLine();
            Console.WriteLine("Generating 10 keys...");
            for (int i = 0; i < 10; i++)
                Console.WriteLine(Key.Generate());

            Console.WriteLine();
            Console.WriteLine("Press [Enter] to finish.");
            Console.ReadLine();
        }
    }

    public class RSAHacking
    {
 
        // Dikkat edin public key den gizli değeri buluyoruz. PrivateKey değil.
        public static uint GetSecretValue(uint encrypted, PublicKey key)
        {
            var privateKey = HackKey(key);

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

            return RSA.Decryption(encrypted, privateKey);
        }

        // Get private key from public key
        public static Key HackKey(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(sqrtn + 1).ToList();
            var count = primes.Count;
            ulong p = 0, q = 0;
            // n değeri çarpanlarına ayrılıyor.
            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.e;
            ulong d = 0;

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

            return new Key { e = key.e, n = key.n, p = p, q = q, d = d };
        }
    }

    // RSA sample
    public class RSA
    {
        public static uint Encryption(uint value, PublicKey key)
        {
            //Şifrelemek için  value ^ key.e mod ken.n değerini hesaplar.
            return (uint)BigInteger.ModPow(value, key.e, key.n);
        }

        public static uint Decryption(uint encrypted, Key key)
        {
            // Şifreyi çözmek için encrypted ^ key.d mod ken.n değerini hesaplar.
            return (uint)BigInteger.ModPow(encrypted, 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 e { get; set; }
        public ulong n { get; set; }

        public override string ToString()
        {
            return string.Format("PublicKey {{ e = {0}, n = {1} }}", e, 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;

        private static List<ulong> primes;

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

        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.

            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 { e = e, n = p * q, p = p, q = q, d = d }; // Private Key oluşturuluyor.
        }

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

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

        public override string ToString()
        {
            return string.Format("PrivateKey {{ e = {0}, n = {1}, p={2}, q={3}, d={4} }}", e, 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; } }
    }
}