Форум программистов, компьютерный форум, киберфорум
Криптография
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
Задачи выполнил, ушёл
26 / 28 / 7
Регистрация: 16.10.2015
Сообщений: 345
1

Расчёт хеш-суммы большого файла в параллельном режиме для проверки целостности

12.01.2016, 20:36. Просмотров 1173. Ответов 3
Метки нет (Все метки)

Метод для расчёта хеш-суммы большого файла в параллельном режиме для проверки целостности.

Не будем выдерживать строгий стиль текста).


- "А разве была какая-то проблема?".

Все уже знают, что тактовая частота процессоров остановилась очень давно и больше расти не собирается (плохо, но жить можно).
Дальнейшее увеличение производительности за многоядерностью, таково текущее приоритетное направление (да и хорошо).
Далее, вполне известно, что есть алгоритмы, которые нельзя распараллелить, и один из этих алгоритмов - криптографическая хеш-функция. Таким образом, поскольку криптографическую хеш-функцию нельзя распараллелить на ядра, то скорость её выполнения упёрлась в тактовую частоту процессора.

- "Я бы на цифры посмотрел...".

Пример:
Допустим у нас есть файл размером 1 Тбайт.
Допустим у нас есть хеш-функция, оптимизированная и написанная на C++, но скорость нашей хеш-функции явно заставляет Вас усомниться в том, что даже сам Бог создавал вселенную на C++. Пусть её скорость будет 1 Гбайт/сек.
Получается, мы рассчитаем хеш-сумму для файла размером 1 Тбайт за 1 Тбайт / 1 Гбайт = 1024 секунды ~= 17 минут.
Ждать 17 минут, чтобы получить хеш-сумму файла, неужели ничего нельзя сделать!? В светлом будущем задержки должны быть очень небольшими.

- "Катастрофа, что выхода походу совсем нет?".

Итак, прежде чем ошибочно признать, что выхода нет, надо понять вот что:
С какой целью мы вообще рассчитываем хеш-сумму файла? Для того, чтобы проверить целостность файла. Значит, наша цель всё-таки не рассчитать хеш-функцию, а всё-таки проверить целостность файла с помощью хеш-функции. Но это уже получается совсем другое дело.
Значит нам надо как-то использовать хеш-функцию для проверки целостности файла, но это однако совершенно не значит, что нужно прямо в лоб рассчитывать хеш-сумму для файла.

- "Ну и что же ты предлагаешь? Не томи!".

Допустим, у нашего процессора 1024 ядра, это даже реальнее, чем поднять частоту процессора в 1000 раз.
Итак, каждое ядро вычисляет хеш-функцию со скоростью 1 Гбайт/сек, так мы условились выше.
Получается, задействовав все ядра процессора (нечего им прохлаждаться под кулером), мы сможем прогнать через хеш-функцию суммарно 1 Тбайт данных за 1 сек.
И ещё, допустим, что скорость чтения данных с нашего суперсовременного SSD как раз 1 Тбайт/сек (это я могу как-то представить, чтение данных всё-таки можно распараллелить).

- "Гм... Ближе к сути дела!".

Итак, сама идея следующая:
Разделяем файл размером в 1 Тбайт на 1024 части, по 1 Гбайту каждая.
Каждую часть параллельно на каждом из 1024 ядер пропускаем через хеш-функцию (скорость расчёта хеша 1 Гбайт/сек на каждом ядре).
Через 1 секунду мы получим 1024 хеш-суммы от каждой части файла.
Теперь просто нужно рассчитать общую хеш-сумму от всех 1024 хеш-сумм вместе взятых (правильный порядок хеш-сумм должен быть соблюдён, первая хеш-сумма должна относиться к первой части файла, вторая к второй и т. д.).

Параллельный расчёт всех 1024 частей файла займёт 1 секунду.
Затем нужно рассчитать итоговый хеш, но поскольку 1024 хеша * 512 бит (выходное значение хеша) = 64 Кбайта, то даже одно ядро рассчитает итоговую хеш-сумму за доли миллисекунды.

Итого, мы получили (для проверки целостности) хеш-сумму 1 Тбайтного файла с использованием 1024 ядер процессора за 1 секунду вместо 17 минут.
Вот это я понимаю светлое будущее.

- "А ещё проще можно? Чтоб прям сама суть видна была.".

Делим файл на части, от каждой части параллельно получаем хеш, потом от всех хешей вместе взятых рассчитываем итоговый хеш. Всё.

- "Насколько безопасно?".

Безопасно, любое изменение в файле изменит итоговый хеш и это очевидно, поскольку метод простой и надёжный. Даже если некоторые части файла совпадают, значит будут совпадать их хеши, но это никак не влияет на безопасность. Железобетонный метод.



Хотел бы выслушать мнение форумчан по этому методу, хотел бы услышать аргументированную критику и предложения. Спасибо.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.01.2016, 20:36
Ответы с готовыми решениями:

Расчет хеш-суммы файла
Общий смысл такой: проходишь посимвольно по всему содержимому документа, формируешь строку или...

Проверка целостности ехе-файла сравнением с хеш-суммой
есть ли нормальный способ убедиться, что файл не повреждён и не изменён? , что-то вроде контрольной...

Разобрать код Петрова для проверки "четности" хеш-суммы MD5
Скинули мне ссылку на публикацию Петрова (уж какого именно не знаю), под названием "В поисках...

Утилита проверки целостности файла
Прошу вашей помощи , так как уже обрыскал все что только можно . Нужно написать программу (утилиту)...

3
Ушел с форума
Эксперт С++
16299 / 7366 / 1183
Регистрация: 02.05.2013
Сообщений: 11,637
Записей в блоге: 1
12.01.2016, 20:43 2
Здесь есть очень узкое место - параллельное чтение с диска. В конечном счете
все упрется в него. Кроме этого, файл размером 1 ТБ не получится загрузить в
память и распределить между ядрами, так что какие-то ядра будут считать, а
другие ждать, пока до них дойдет очередь.

Так что идея хорошая, но она упирается в другие технические ограничения.
1
Задачи выполнил, ушёл
26 / 28 / 7
Регистрация: 16.10.2015
Сообщений: 345
12.01.2016, 20:48  [ТС] 3
Здесь есть очень узкое место - параллельное чтение с диска. В конечном счете
все упрется в него. Кроме этого, файл размером 1 ТБ не получится загрузить в
память и распределить между ядрами, так что какие-то ядра будут считать, а
другие ждать, пока до них дойдет очередь.

Так что идея хорошая, но она упирается в другие технические ограничения.
Да, к сожалению это самое узкое место, хотя есть и другие, но даже если будет в разы быстрее 17 минут, я думаю это стоит того).
Кстати, я имел в виду не диск, а именно SSD, с диска читать во много потоков не получиться.
0
Ушел с форума
Эксперт С++
16299 / 7366 / 1183
Регистрация: 02.05.2013
Сообщений: 11,637
Записей в блоге: 1
12.01.2016, 21:23 4
Цитата Сообщение от noname664 Посмотреть сообщение
даже если будет в разы быстрее 17 минут, я думаю это стоит того
Согласен. Хотя, как мне кажется, здесь сработает что-нибудь в духе закона Мура.
Я имею в виду, что к тому времени, когда мы будем иметь под тысячу ядер на
обычном десктопном PC и сможем читать по 1 ТБ за секунду, объемы данных
тоже пропорционально увеличатся и объемы дисков будут измеряться в петабайтах,
экзабайтах и т.п. И мы все равно будем ждать те самые 17 минут

Человек будущего будет очень мало работать, потому что за него все будут делать роботы.
У человека будущего будут очень маленькие ручки, потому что он будет редко что-то
ими делать. У человека будущего будут очень маленькие ножки, потому что вместо ходьбы
он будет путешествовать во времени и пространстве с помощью всевозможных аппаратов.
У человека будущего будет очень маленький живот, потому что он будет питаться
только высокоэнергетическими таблетками. У человека будущего будет большая
голова, потому что он будет много думать. Думать, где достать эти таблетки.


А вообще, идея с параллельными хэшами такая же живая, как и любая другая
идея распараллеливания в эпоху многоядерности. Возможно, в ближайшее время
появятся новые функции хэширования, которые можно будет юзать параллельно.
А может, такие давно есть, просто я про них не знаю...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2016, 21:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Расчет хеш-суммы
Ребят, помогите мне модифицировать метод. Нашел его здесь...

Вытащить хеш пароля из базы для проверки
Есть таблица 'users': id, email, password. Есть логин форма email, password. $email = $_POST;...

Генерация MD5 хеш суммы файла
Сколько не пробовал, неправильно генерируется хеш! :( Ведь файл это набор символов. Потому я...

Расчет значений резисторов в параллельном АЦП
Имеется схема АЦП параллельного кодирования. Как расчетать в ней значения резисторов и как...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.