advanced code snippet search

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#
 
Expand | Embed | Plain Text 
  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.