Posted By

ozkriff on 11/07/09


Tagged


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

khouser


rsa


 / Published in: C#
 

  1. using System;
  2. using Emil.GMP; //from Emil.GMP.dll (class BigInt)
  3. using System.Collections.Generic; //for LIST
  4. using System.Text;
  5.  
  6.  
  7. class RSA
  8. {
  9. static void Main(string[] args)
  10. {
  11. Random rnd = new Random();
  12.  
  13. /// 1. Генерируется случайные простые числа p и q
  14. /// 2. Вычисляется их произведение n = pq
  15. /// 3. Вычисляется значение функции Эйлера от числа n.
  16. /// 4. Выбирается целое число e, взаимно простое со значением функции fi
  17. /// часто выбирают равным 17, 257 или 65537 — простым числам,
  18. /// двоичное представление которых содержит лишь две единицы:
  19. /// 17 = 0x11, 257 = 0x101, 65537 = 0x10001 (простые числа Ферма). */
  20. /// 5. Вычисляется число d мультипликативное обратное к числу e по модулю fi
  21. ///
  22. /// Пара P = (e,n) публикуется в качестве открытого ключа RSA
  23. /// Пара S = (d,n) играет роль секретного ключа RSA
  24. /* 1 */ BigInt p = new BigInt(61); Console.WriteLine("p = " + p);
  25. BigInt q = new BigInt(53); Console.WriteLine("q = " + q);
  26. /* 2 */ BigInt n = p * q; Console.WriteLine("n = " + n);
  27. /* 3 */ BigInt fi = (p-1)*(q-1); Console.WriteLine("fi = " + fi);
  28. /* 4 */ string[] pre_e = {"17", "257", "65537",
  29. "18446744073709551617",
  30. "340282366920938463463374607431768211457"};
  31. int i = rnd.Next(0, pre_e.GetLength(0));
  32. BigInt e = new BigInt(pre_e[i]);Console.WriteLine("e = " + e);
  33. /* 5 */ BigInt d = e.InvertMod(fi); Console.WriteLine("d = " + d);
  34.  
  35.  
  36.  
  37. /// ПРОВЕРКА:
  38. string text = "котлеты подешевели?";
  39. Console.WriteLine("Оригинальный текст: \'" + text + "\'");
  40.  
  41. List<BigInt> original = new List<BigInt>();
  42. List<BigInt> encripted = new List<BigInt>();
  43. List<BigInt> decripted = new List<BigInt>();
  44.  
  45. foreach(char c in text)
  46. original.Add(new BigInt((int)c));
  47.  
  48. Console.WriteLine("Оригинальные цифры:");
  49. foreach(BigInt bi in original)
  50. Console.Write(bi + " ");
  51. Console.WriteLine();
  52.  
  53. Console.WriteLine("Шифр:");
  54. for (int ii = 0; ii < original.Count; ii++)
  55. {
  56. encripted.Add(original[ii].PowerMod(e, n));
  57. Console.Write(encripted[ii] + " ");
  58. }
  59. Console.WriteLine();
  60.  
  61. Console.WriteLine("Расшифровка:");
  62. for (int ii = 0; ii < original.Count; ii++)
  63. {
  64. decripted.Add(encripted[ii].PowerMod(d, n));
  65. Console.Write(decripted[ii] + " ");
  66. }
  67. Console.WriteLine();
  68.  
  69. StringBuilder decripted_text = new StringBuilder();
  70. foreach(BigInt x in decripted)
  71. decripted_text.Append((char)x);
  72. Console.WriteLine("Расшифрованный текст: \'" + decripted_text + "\'");
  73.  
  74.  
  75. } // static void Main(string[] args)
  76. } // class RSA
  77.  
  78. // csc /nologo /r:Emil.GMP.dll RSA.cs && RSA.exe
  79. // C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727
  80.  
  81. /**
  82. C:\downloads\RSA\CS>csc /nologo /r:Emil.GMP.dll RSA.cs && RSA.exe
  83. p = 61
  84. q = 53
  85. n = 3233
  86. fi = 3120
  87. e = 65537
  88. d = 2753
  89. Оригинальный текст: 'котлеты подешевели?'
  90. Оригинальные цифры:
  91. 1082 1086 1090 1083 1077 1090 1099 32 1087 1086 1076 1077 1096 1077 1074 1077 1083 1080 63
  92. Шифр:
  93. 2611 1625 2839 1666 1862 2839 2380 1992 3039 1625 187 1862 3067 1862 2814 1862 1666 1804 3216
  94. Расшифровка:
  95. 1082 1086 1090 1083 1077 1090 1099 32 1087 1086 1076 1077 1096 1077 1074 1077 1083 1080 63
  96. Расшифрованный текст: 'котлеты подешевели?'
  97. */

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: ozkriff on November 9, 2009

блин. замени fi на n в шифровке и расшифровке!

Posted By: ulitiy on December 16, 2010

rsa это не блочный шифр, вы не можете вот так взять и разбить сообщение на куски и зашифровать каждый кусок в отдельности. Таким образом вы ослабляете криптостойкость алгоритма. Информация в данном алгоритме представляет собой одно большое число, которое нужно возводить в степень по модулю.

Второе - в похожей либе(BigInteger) есть методы генерации простых чисел - их и надо использовать. 61 и 53 не годятся для целей шифрования.

Третье - небольшие числа, например 257 - тоже удар по криптостойкости алгоритма. А так же существует теорема о том, что не все числа ферма являются простыми, поэтому вы не можете вот так просто брать рандом от тех чисел, которые вы привели. Лучше берите статично 65537 - будет куда лучше.

В остальном - замечательно что оно работает. Я у себя пока не добился, но я все-таки пытаюсь сделать правильно (см. пункт 1).

Posted By: ulitiy on December 16, 2010
    string encode(string hextext,BigInteger e, BigInteger n)
    {
        BigInteger m = new BigInteger(hextext, 16);
        BigInteger P=m.modPow(e, n);
        return P.ToHexString();
    }

    void genkeys(int bits,out BigInteger e, out BigInteger d, out BigInteger n)
    {
        Random rand=new Random();
        //случайные простые числа
        BigInteger p = BigInteger.genPseudoPrime(bits, 5, rand);
        BigInteger q = BigInteger.genPseudoPrime(bits, 5, rand);
        //их модуль
        n = p * q;
        //функция эйлера от n
        BigInteger phi = (p - 1)*(q - 1);
        //открытая экспонента
        e = 65537;
        //мультипликативно обратное по модулю phi
        d = e.modInverse(phi);
    }

У меня получилось вот так. Работает. Здесь используется либа biginteger.cs, 16-ричная строка, но я думаю не составит труда сначала конвертнуть в байт-сиквенс, а потом конвертнуть обратно. Обратите внимание - информация не делится на байты, здесь - информация воспринимается как огромное целое число. Шифрование открытой экспонентой и модулем, дешифрование - секретной и модулем.

You need to login to post a comment.