Guest
Новичок
|
    
Задача такова данна хеш функция х
х( вводим значения{0,1}длинной 2к выводит значения{0,1}длинной к)
-----------------
А > 2
нужно создать фунцию б (в которую вводятся значения {0,1}длинной Ак выводит значения{0,1}длинной к)
при создании используя данную функцию х
А потом доказать что новая функция будет "колижин фри" то есть два разных вводимых значения не дадут два одинаковых ответа (Это свойство хеш функции то есть это свойство функции х)
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 29 янв. 2005 21:20 | IP
|
|
Guest
Новичок
|
2. Propri´et´es de fonctions
Une fonction f : A ! B s’appelle
• `a sens unique s’il est dicile de trouver, pour un y 2 f(A) donn´e, un ´el´ement x de A tel que
f(x) = y,
• `a collisions diciles s’il est dicile de trouver x, x0 2 A, x 6= x0, tel que f(x) = f(x0).
(Notez que le terme “`a collisions diciles” est utilis´e pour une seule fonction ici, ce qui n’est
pas formel.)
(a) Soit f : {0, 1}k ! {0, 1}k une fonction `a sens unique. Construisez, `a partir de f, une fonction
de hachage g : {0, 1}2k ! {0, 1}k qui est ´egalement `a sens unique. Est-ce que votre fonction
g est `a collisions diciles?
(b) Soit h : {0, 1}2k ! {0, 1}k une fonction de hachage `a collisions diciles, et soit n > 2 un
entier. Construisez une fonction de hachage `a collisions diciles h0 : {0, 1}nk ! {0, 1}k.
Prouvez que h0 est `a collisions diciles si h a cette propri´et´e.
может я не понятно перевёл то вот версия на буржуйском языке А я уже ответил а на Б торможу.
Ответ А черновик
New function will be :
G(2n)= F(n) act F(n) (act might be For example xor)
Since F(n) is function a cence unique function G(n) which is constructuded from 2 functions will have to be a sence unique. To prove it we can say that it F(n) is function a sence unique any action between 2 functions a snce unique will be a sence unique if we will prove that this is not the case we will prove that F9n) is not a sence unique but f(n ) is function a sence unique by defenition.
The function that we created is not a collisions defficiles. Since we use operator XOR.
And the value of 2n will be constracted by chaining of two different values of the length n. n1 and n2. Since the operation XOR between n1 and n2 will give the similar resalt as operation between n2 and n1. And n1-n2 and n2-n1 are different values we esaly found this collusion
So we conclude that the new function that we have created is not a difficult collusion.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 29 янв. 2005 21:34 | IP
|
|
|
Форум
Свойство Хэш функции
