Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770
Форумы портала PHP.SU :: Версия для печати :: Немного RSA
Форумы портала PHP.SU » » Хранилище функций на JavaScript » Немного RSA

Страниц (1): [1]
 

1. UserID - 08 Апреля, 2007 - 11:32:59 - перейти к сообщению
Записки сумашедшего Улыбка

Наткнулся я тут однажды на одну ссылку: http://passcracking[dot]ru

И что-то мне грустно стало. Ну вот кому не понравился этот алгоритм, не знаю. Теперь придёться ломать голову...

Кое-что из истории:
Цитата:
RSA (Rivest-Shamir-Adelman) является наиболее известным алгоритмом с открытым ключом. Может использоваться как для шифрования, так и для создания подписи. Считается, что алгоритм надежен при использовании достаточно длинных ключей (значение 512 бит считается недостаточным, 768 бит - умеренно надежным, 1024 бит - хорошим). Безопасность RSA основана на проблеме факторизации больших целых чисел. Существенные продвижения в способах факторизации больших чисел могут сделать метод RSA уязвимым. В настоящее время, 512-битные ключи считаются слабозащищенными, 1024-битные ключи вероятно подходят для большинства практических целей, 2048-битные ключи будут безопасны для использования в течении десятилетий.


Видимо ещё не так всё плохо... посмотрим что из себя представляет сам md5:
Цитата:
MD5 (Message Digest Algorithm 5) представляет собой алгоритм хэширования, разработанный компанией RSA Data Security, Inc. Он может использоваться для хэширования строки байт произвольной длины в 128-битное значение. MD5 широко используется и считается достаточно надежным.

Функция хэширования H представляет собой отображение, на вход которого подаётся сообщение M произвольной длины, а на выходе получается значение h конечной длины, где h = H(M).
В общем случае хэш-значение h гораздо меньше исходного сообщения M. Так для MD5 h=128 бит. Хэш-функция должна обладать следующими свойствами:
1. По достаточно большому сообщению M хэш-функция должна быстро вычислить h значение, которое должно зависеть от каждого бита сообщения M.
2. Необратимость: по h значению невозможно восстановить исходный текст M
3. Вычислительно очень трудно (почти невозможно) найти два сообщения M и M1, которые дают два одинаковых h-значения.
Хэш-значение является контрольной суммой исходного сообщения M и называется MDC (Manipulation Detection Code - код обнаружения изменений) или MIC (Message Integrity Check - проверка целостности сообщения). Если хэш-функция использует для своей работы ключ (пароль), то получаемое значение называется MAC (Message Authentication Code - код аутентичности сообщения).Подробное официальное описание MD5 даётся в RFC 1321.


По RFC примерный алгоритм шифрования состоит из последовательностей:

Шаг 1: выравнивание потока.
Входной поток выравнивается так, что бы его длина стала конгруэнтной (сравнимой) с 448 по модулю 512. Выравнивание происходит следующим образом: к потоку добавляется один бит '1', а затем биты '0' до тех пор, пока длина потока не будет сравнима с 448 по модулю 512. Выравнивание происходит всегда, даже если длина потока была уже сравнима с 448 по модулю 512. Таким образом к потоку добавляется минимум 1 бит, максимум - 512.

Шаг 2: добавление длины.
64 битное представление длины входного потока (длины потока до выравниваия) добавляется к результату предидущего шага. Если длина потока превосходит 2^64, то добавляются младшие 64 бит. Эти биты добавляются как 2 32-битных слова, младшее слово добавляется первым. Таким образом на этом шаге длина потока становится кратной 512 битам или 16 32-битным словам. Далее будем рассматривать входной поток как массив M[0 ... N-1] слов длиной N.

Шаг 3: инициализация MD буфера.
Буфер из 4 слов {A, B, C, D} используется для вычисления хэш функции, который инициализируется в следующие значения:

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476


Шаг 4: обработка потока блоками по 16 слов.
Определим четыре вспомогательные функции, каждая из которых принимает три параметра размеров в слово и производит результат - слово.

F(x, y, z) = (x & y) | (~x & z)
G(x, y, z) = (x & z) | (y & ~z)
H(x, y, z) = x ^ y ^ z
I(x, y, z) = y ^ (x | ~z)

Напомним, что & - побитовое И, | - побитовое ИЛИ, ^ - побитовое исключающее ИЛИ, ~ - побитовое отрицание. Функция F для каждого бита дает следующий результат: если X, то Y, иначе Z.
На этом шаге также используется таблица T[1..64], которая построена с помощью функции синуса:
T[1] = int(4294967296 * abs(sin(i))), где int() - целая часть. Например:
T[1] = int(4294967296 * abs(sin(i))) = int(3614090360,282...) = 3614090360.

Шаг 5: вывод MD5.
Результат вычисления (хэш) представлен четырьмя 32 битными словами -A, B, C, D (младшим записывается A, старшим - D). 128-битный MD5 хэш готов!
2. -SCHATTEN- - 08 Апреля, 2007 - 12:38:16 - перейти к сообщению
Действительно обидно . Я бы посмотрел на код =(

3. valenok - 08 Апреля, 2007 - 14:46:53 - перейти к сообщению
..
начинаем разработку самодельных алгоритмов..
4. UserID - 08 Апреля, 2007 - 20:04:20 - перейти к сообщению
valenok

Хорошая идея Улыбка Математики есть на форуме?
5. kamikadze - 08 Апреля, 2007 - 20:54:15 - перейти к сообщению
Я математик, но в яве не шарю (да и математику подзабыл уже немного) !
6. -SCHATTEN- - 08 Апреля, 2007 - 21:08:20 - перейти к сообщению
По сути каждый прогер - это спяший математик.
Так давайте будить себя.
7. kamikadze - 08 Апреля, 2007 - 21:09:21 - перейти к сообщению
Давайте! Знание в какой области надо?
8. Jakeryf - 08 Апреля, 2007 - 21:22:24 - перейти к сообщению
Наслаждайтесь
PHP:
скопировать код в буфер обмена
  1.  
  2. <script>
  3. function sha1Hash(msg)
  4. {
  5.     // constants
  6.     var K = [0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6];
  7.     // PREPROCESSING
  8.     msg += String.fromCharCode(0x80); // add trailing '1' bit to string
  9.     // convert string msg into 512-bit/16-integer blocks arrays of ints
  10.     var l = Math.ceil(msg.length/4) + 2;  // long enough to contain msg plus 2-word length
  11.     var N = Math.ceil(l/16);              // in N 16-int blocks
  12.     var M = new Array(N);
  13.     for (var i=0; i<N; i++) {
  14.         M[i] = new Array(16);
  15.         for (var j=0; j<16; j++) {  // encode 4 chars per integer, big-endian encoding
  16.             M[i][j] = (msg.charCodeAt(i*64+j*4)<<24) | (msg.charCodeAt(i*64+j*4+1)<<16) |
  17.                       (msg.charCodeAt(i*64+j*4+2)<<8) | (msg.charCodeAt(i*64+j*4+3));
  18.         }
  19.     }
  20.     // add length (in bits) into final pair of 32-bit integers (big-endian)
  21.  
  22.     M[N-1][14] = ((msg.length-1) >>> 30) * 8;
  23.  
  24.  
  25.     M[N-1][15] = ((msg.length-1)*8) & 0xffffffff;
  26.  
  27.     // set initial hash value
  28.  
  29.     var H0 = 0x67452301;
  30.     var H1 = 0xefcdab89;
  31.     var H2 = 0x98badcfe;
  32.     var H3 = 0x10325476;
  33.     var H4 = 0xc3d2e1f0;
  34.  
  35.     // HASH COMPUTATION
  36.  
  37.     var W = new Array(80); var a, b, c, d, e;
  38.     for (var i=0; i<N; i++) {
  39.  
  40.         // 1 - prepare message schedule 'W'
  41.         for (var t=0;  t<16; t++) W[t] = M[i][t];
  42.  
  43.         for (var t=16; t<80; t++) W[t] = ROTL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);
  44.         // 2 - initialise five working variables a, b, c, d, e with previous hash value
  45.         a = H0; b = H1; c = H2; d = H3; e = H4;
  46.         // 3 - main loop
  47.         for (var t=0; t<80; t++) {
  48.             var s = Math.floor(t/20); // seq for blocks of 'f' functions and 'K' constants
  49.             var T = (ROTL(a,5) + f(s,b,c,d) + e + K[s] + W[t]) & 0xffffffff;
  50.             e = d;
  51.             d = c;
  52.             c = ROTL(b, 30);
  53.             b = a;
  54.             a = T;
  55.         }
  56.         // 4 - compute the new intermediate hash value
  57.         H0 = (H0+a) & 0xffffffff;  // note 'addition modulo 2^32'
  58.         H1 = (H1+b) & 0xffffffff;
  59.         H2 = (H2+c) & 0xffffffff;
  60.         H3 = (H3+d) & 0xffffffff;
  61.         H4 = (H4+e) & 0xffffffff;
  62.     }
  63.     return H0.toHexStr() + H1.toHexStr() + H2.toHexStr() + H3.toHexStr() + H4.toHexStr();
  64. }
  65.  
  66. //
  67. // function 'f'
  68. //
  69.  
  70.  
  71. function f(s, x, y, z)
  72. {
  73.     switch (s) {
  74.     case 0: return (x & y) ^ (~x & z);
  75.     case 1: return x ^ y ^ z;
  76.     case 2: return (x & y) ^ (x & z) ^ (y & z);
  77.     case 3: return x ^ y ^ z;
  78.     }
  79. }
  80. //
  81. // rotate left (circular left shift) value x by n positions
  82. //
  83.  
  84.  
  85. function ROTL(x, n)
  86. {
  87.     return (x<<n) | (x>>>(32-n));
  88. }
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95. Number.prototype.toHexStr = function()
  96. {
  97.     var s="", v;
  98.     for (var i=7; i>=0; i--) { v = (this>>>(i*4)) & 0xf; s += v.toString(16); }
  99.     return s;
  100. }
  101. </script>
  102.  
  103. <form name="f" action="none!">
  104.   <table>
  105.     <tr>
  106.       <td> </td>
  107.       <td colspan="2">Введите сообщение для получения SHA-1 хэш:</td>
  108.     </tr>
  109.     <tr>
  110.       <td>    </td>
  111.       <td>Сообщение:</td>
  112.       <td><input type="text" name="message" size="48" value="abc"></td>
  113.     </tr>
  114.     <tr>
  115.       <td> </td>
  116.       <td colspan="2"><input name="button" type="button"
  117.         onClick='f.hash.value = sha1Hash(f.message.value)' value="Генерировать"></td>
  118.     </tr>
  119.     <tr>
  120.       <td> </td>
  121.       <td>Хэш:</td>
  122.       <td><input type="text" name="hash" size="48" readonly></td>
  123.     </tr>
  124.     <tr valign="bottom">
  125.       <td> </td>
  126.       <td style="font-size: smaller"><i>хэш для ‘abc’ должен быть: </i></td>
  127.       <td style="font-size: smaller"><i>a9993e364706816aba3e25717850c26c9cd0d89d</i></td>
  128.     </tr>
  129.   </table>
  130. </form>
  131.  


Начну с конца.

К классу Number добавляется метод toHexStr, так как toString(16) возвращает строку со знаком числа.


Функция ROTL() осуществляет циклический сдвиг влево, >>> - сдвиг влево без сохранения знака числа.


Функция f() делает 4 различные логические операции со своими параметрами, ^ - исключающее ИЛИ.


Функция sha1Hash() преобразует исходную строку в двумерный массив из целых чисел M[i][j].
N - первая размерность массива. Вторая размерность - 16. Используется
big-endian - кодировка многобайтных чисел (В "big-endian" кодировке, наиболее значимый байт хранится по наименьшему адресу.
В "little-endian" наоборот. Например, число 1025 может хранится как 4-х байтовое целое:
00000000 00000000 00000100 00000001


Инициализируются 5 составляющих будущего хэша - H0, H1, H2, H3, H4. В цикле по N происходит "перетряска" этих переменных.
Для параметризации используются значения очередного блока из 16 чисел (срез исходной строки). В результате такой
"магии" получается почти уникальное значение хэша.
9. -SCHATTEN- - 08 Апреля, 2007 - 21:28:21 - перейти к сообщению
Jakeryf
:love:
10. AterCattus - 29 Января, 2008 - 23:24:18 - перейти к сообщению
SHA-1 сломали на 2 года раньше, чем Jakeryf выложил тут код )
Лучше уж SHA-256 использовать. Он вроде пока только перебором...

 

Powered by ExBB FM 1.0 RC1