Archive for Czerwiec, 2009

Zabawa w szyfrowanie – RSA

W ramach zaliczenia laboratorium jednego z przedmiotów szkolnych miałem za zadanie napisać niewielki programik szyfrujący. Wybrałem szyfr RSA – jak podaje wikipedia jego nazwa jest akronimem utworzonym z pierwszych liter nazwisk jego twórców – Rivest, Shamir, Adleman. Szyfrowanie i odszyfrowanie tekstu z wykorzystaniem RSA nie jest procesem zbyt skomplikowanym – wymaga jednak operowania dość dużymi liczbami pierwszymi co zmusiło mnie do rezygnacji ze standardowego typu int w C# który miał za mały zakres. W bezdennych zasobach internetowych znalazłem strukturę którą wykorzystałem w swojej implementacji -> BigInt.

Etapy szyfrowania umożliwiające zakodowanie i odkodowanie tekstu:

  1. Wylosuj dwie duże liczby pierwsze p i q
  2. Oblicz n = p * q
  3. Oblicz phi = (p – 1) * (q – 1)
  4. Oblicz e -> Para (e, n) tworzy klucz publiczny wykorzystywany do szyfrowania
  5. Oblicz d -> Para (d, n) tworzy klucz prywatny wykorzystywany do odszyfrowania
  6. Szyfrowanie znaku:
    • Zamiana znaku na kod Ascii
    • Oznaczmy c jako zaszyfrowany znak c = asciiNume mod n
  7. Odszyfrowanie znaku:
    • Aby otrzymać na powrót zaszyfrowany znak: t = cd mod n

Zamiana znaku na kod Ascii i na odwrót:

          char ch = "A";
          int asciiNum = (int)ch;
          ch = (char)asciiNum;

Nie chcę jednak zagłębiać się maksymalnie w poszczególne etapy szyfrowania i odszyfrowania, a skupię się na samym specyficznym sposobie zapisu zaszyfrowanych znaków który sobie wymyśliłem i zakodziłem. ;)

Przykład 1:

Powiedzmy, że mam wyraz „Ola”, który zaszyfrowałem i chcę zapisać do pliku następnie odczytać i odszyfrować. Liczby powstałe w procesie szyfracji: 186220802, 16730814, 137205435. I tutaj pojawia się pytanie w jaki sposób mogę zapisać liczby tak aby osoba otwierająca plik nie domyśliła się, że poszczególne liczby reprezentują znaki? Jednym ze sposobów jest na przykład oddzielanie liczba przecinkami, kropkami lub innymi znakami interpunkcyjnymi. Mnie to jednak nie zadowalało wpadłem więc na pomysł, aby ustalić na stałe znaki „specjalne”, które zostaną zakodowane i „dodane” do powstałych liczb.

Przykład 2:

Ustalam, że moim znakiem specjalnym będzie przecinek następnie szyfruje jego kod i otrzymuję na przykład liczbę: 164916224.
Dodaje do każdej z wyżej powstałych liczb znak specjalny i do pliku wędruję taki oto ciąg liczb 18622080216491622416730814164916224137205435 :)

Jest jednak problem w sytuacji gdy ciąg znaków wygląda tak „O,l,a,,,”, a znakiem specjalnym jest przecinek. Odczytanie z pliku zaszyfrowanego ciągu z użyciem jako znak specjalny przecinka znacząco utrudnia odszyfrowanie – mamy długi ciąg liczb chcemy go podzielić po przecinku, ale tak naprawdę nie wiemy ile razy przecinek mógł wystąpić w danym wyrażeniu. By mieć możliwość swobodnego podziału tego typu ciągu liczb i odzyskać poszczególne liczby, aby je odkodować następnie odczytać oryginalny tekst źródłowy ustaliłem znaki specjalne spoza kodów Ascii. – Są to losowa przeze mnie wybrane trzy dziwne „krzaczki” które mi pięknie oddzielają poszczególne zakodowane znaki.

Klasę realizującą szyfrowanie i odszyfrowanie na podstawie obliczonych kluczy nazwałem Rsa. Jako, że spróbuję zmierzyć się z implementacją innych sposobów szyfrowania utworzyłem interfejs który w moim programie będzie reprezentował klasy szyfrujące i deszyfrujące.

Interfejs ICipher:

public interface ICipher
{
    StringCollection Encrypt(StringCollection sc);
    StringCollection Encrypt(string path);
    StringCollection Decrypt(StringCollection sc);
    StringCollection Decrypt(string path);
    void SaveToFile(string savePath);
}

Klasa Rsa:

/// <summary>
/// Klasa szyfrujaca RSA
/// </summary>
public class Rsa : ICipher
{
   #region Fields & Properties
   private BigInt _n;
   private BigInt _e;
   private BigInt _d;

   /// <summary>
   /// Tablica znakow specjalnych
   /// </summary>
   private readonly char[] _chars = { 'ฒ', 'ฑ', 'ฐ' };
   private StringCollection _scTemp;

   /// <summary>
   /// Zwraca tablice zawierajaca klucz prywatny i publiczny
   /// Indexy: 0 = n, 1 = e, 2 = d
   /// </summary>
   public BigInt[] Keys
   {
        get
        {
            return new BigInt[]
            {
                 _n,
                 _e,
                 _d
             };
         }
   }
   #endregion

   /// <summary>
   /// Konstruktor przyjmujacy wartosci umozliwiajace szyfrowanie
   /// </summary>
   /// <param name="n">n</param>
   /// <param name="e">e</param>
   /// <param name="d">d</param>
   public Rsa(BigInt n, BigInt e, BigInt d)
   {
            _n = n;
            _e = e;
            _d = d;
   }

    /// <summary>
    /// Konstruktor tworzacy obiekt Rsa tylko do odszyfrowywania danych
    /// Przyjmuje pare tworzaca klucz prywatny
   /// </summary>
   /// <param name="n">n</param>
   /// <param name="d">d</param>
   public Rsa(BigInt n, BigInt d)
   {
         _n = n;
         _d = d;
   }

   #region ICipher Members
   /// <summary>
   /// Szyfruje podana kolekcje stringow
   /// </summary>
   /// <param name="sc">Kolekcja stringow</param>
   /// <returns>Kolekcja zaszyfrowanych stringow</returns>
   public StringCollection Encrypt(StringCollection sc)
   {
       StringCollection cipheredText = new StringCollection();
       _scTemp = null;

       foreach (string s in sc)
       {
            //Zamiana stringa na tablice znakow
            char[] charArray = s.ToCharArray();

            int index = 0;
            string str = string.Empty;

            //Pobranie zakodowanych znakow specjalnych
            BigInt[] biArray = GetCipheredSpecialChar();

            foreach (char ch in charArray)
            {
                //Wylosowanie znaku specjalnego wykorzystanego do szyfracji
                index = Randomizer.UniqueInstance.Next(0, biArray.Count());

                //Szyfrowanie
                BigInt c = BigInt.Parse(ch.GetNumberOfChar().ToString());
                c = c.FastModuloPower(_e, _n);

                //Znak + znak specjalny
                str += c.ToString() + biArray[index].ToString();
            }

            cipheredText.Add(str);
       }
       _scTemp = cipheredText;

       return cipheredText;
   }

   /// <summary>
   /// Szyfruje wskazana zawartosc pliku
   /// </summary>
   /// <param name="path">Sciezka do pliku</param>
   /// <returns>Kolekcja zaszyfrowana</returns>
   public StringCollection Encrypt(string path)
   {
        StringCollection sc = null;
        _scTemp = null;

        try
        {
            string[] stringArray = File.ReadAllLines(path, Encoding.Default);
            sc = new StringCollection();
            sc.AddRange(stringArray);
            sc = Encrypt(sc);
        }
        catch (IOException)
        {
            throw;
        }
        catch (Exception)
        {
            throw;
        }

        return sc;
   }

   /// <summary>
   /// Deszyfracja z kolekcji stringow
   /// </summary>
   /// <param name="sc">Kolekcja stringow</param>
   /// <returns>Zwraca rozszyfrowany text</returns>
   public StringCollection Decrypt(StringCollection sc)
   {
        _scTemp = null;
        //Konwersja zakodowanych znakow specjalnych
        //i wrzucenie wszytkich do tablicy string
        string[] cipheredSpecialCharArray = GetCipheredSpecialChar().ToList()
                     .ConvertAll<string>((BigInt bi) =>
                {
                    return bi.ToString();
                }).ToArray();

        StringCollection decodedTextCollection = new StringCollection();

        foreach (string s in sc)
        {
             //Podział zakodowanych znakow metoda Split wedlug znakow specjalnych
             List<string> cStringArray = s.Split(cipheredSpecialCharArray, StringSplitOptions.RemoveEmptyEntries).ToList();

             string decodedText = string.Empty;
             //Iteracja po tablicy zawierajacej poszczegolne znaki w postaci zakodwanych liczb
             foreach (string str in cStringArray)
             {
                 BigInt de = BigInt.Parse(str).FastModuloPower(_d, _n);
                 char c = de.GetCharFromNumber();
                 decodedText += c;
             }
             //Dodanie do kolekcji utworzonej linii textu
             decodedTextCollection.Add(decodedText);
        }

        _scTemp = decodedTextCollection;

        return decodedTextCollection;
   }

   /// <summary>
   /// Deszyfruje text odczytany z pliku
   /// </summary>
   /// <param name="path">Sciezka do pliku</param>
   /// <returns>Zwraca rozszyfrowany text</returns>
   public StringCollection Decrypt(string path)
   {
        _scTemp = null;

        StringCollection sc = null;
        try
        {
             string[] stringArray = File.ReadAllLines(path, Encoding.Default);
             sc = new StringCollection();
             sc.AddRange(stringArray);
             sc = Decrypt(sc);
        }
        catch (IOException)
        {
              throw;
        }
        catch (Exception)
        {
              throw;
        }

        return sc;
   }

   /// <summary>
   /// Metoda realizujaca zapis do pliku
   /// </summary>
   /// <param name="savePath">Sciezka do zapisu</param>
   /// <param name="sc">Kolekcja do zapisu</param>
   public void SaveToFile(string savePath)
   {
         if (!String.IsNullOrEmpty(savePath) && _scTemp != null)
         {
              StreamWriter writer = null;
              try
              {
                  foreach (string s in _scTemp)
                  {
                      if (writer == null)
                      {
                          writer = new StreamWriter(savePath, false, Encoding.UTF8);
                      }

                      writer.WriteLine(s);
                 }
             }
             catch (IOException)
             {
                   throw;
             }
             catch (Exception)
             {
                  throw;
             }
             finally
             {
                  if (writer != null)
                  {
                       writer.Close();
                  }
             }
        }
   }
    #endregion

    #region Help Methods

    /// <summary>
    /// Metoda umozliwiajaca zapis kluczy do pliku
    /// </summary>
    /// <param name="savePath">Sciezka do zapisu</param>
    public void SaveKeysToFile(string savePath)
    {
         StreamWriter writer = null;
         try
         {
             writer = new StreamWriter(savePath, false, Encoding.UTF8);
             writer.WriteLine("Klucz publiczny:");
             writer.WriteLine("KP: (" + _e.ToString() + "; "
                           + _n.ToString() + ")");
             writer.WriteLine("Klucz prywatny:");
             writer.WriteLine("KPr: ( d=" + _d.ToString() + "; n="
                           + _n.ToString() + ")");
         }
         catch (IOException)
         {
              throw;
         }
         catch (Exception)
         {
              throw;
         }
         finally
         {
                if (writer != null)
                {
                    writer.Close();
                }
         }
    }

    /// <summary>
    /// Metoda pomocnicza szyfrujaca kody znakow specjalnych
    /// </summary>
    /// <returns>Tablica kodow znakow specjalnych</returns>
    private BigInt[] GetCipheredSpecialChar()
    {
         BigInt[] biArray = new BigInt[_chars.Length];
         for (int i = 0; i < _chars.Length; i++)
         {
             biArray[i] = BigInt.Parse(_chars[i].GetNumberOfChar()
                                 .ToString()).FastModuloPower(_e, _n);
         }

         return biArray;
    }
    #endregion
}