Расчет SHA-1 хеша средствами 1С. Битовые операции в 1С или урок двоичной математики

13.03.13

Разработка - Математика и алгоритмы

Расчет хеша SHA-1 без использования каких-либо внешних компонет - возможно ли это в 1Cv8? Оказывается вполне возможно!

Скачать файлы

Наименование Файл Версия Размер
Калькулятор SHA-1 хеша от строки
.epf 10,11Kb
155
.epf 10,11Kb 155 Скачать

Я думаю если провести опрос, то многие программисты ответят, что в 1С нет штатных средств для работы с отдельными битами, нет операторов XOR, OR, AND над числами.

Расчет хеша SHA-1 без использования каких-либо внешних компонет - возможно ли это в 1Cv8? Оказывается вполне возможно!

В прикрепленном файле содержится готовая обработка, которая возвращает SHA-1 хеш от указанной строки.

Для понимания как это реализовано на 1с вспомним двоичную систему счисления. В принципе, если представить целое десятичное число в двоичной системе счисления, то как раз получим последовательность бит. Например число 128 в двоичной счисления будет иметь вид 10000000 для 8-битного представления или 00000000000000000000000010000000 для 32-битного, а 129 соответственно 10000001 или 00000000000000000000000010000001.

Т.е. число в десятичной системе = ΣBi·2i, где Bi - бит из двоичного числа, а отсчет битов начинается с нуля. Т.е. для числа 10000001 получаем 128·1+64·0+32·0+16·0+8·0+4·0+2·0+1·1=129

 Для обратного перевода можно пользоваться несколькими способами:

1) Для получения битов начиная со старшего, заканчивая младшим:

Исходное число, например 129, делим на 2^7, если получается больше единицы, то первый бит - 1, иначе 0. Далее Из исходного числа 129 вычитаем 2^7*бит и получаем 129-128*1=1. Далее получаем следующий бит - 1 делим на 2^6, получаем число меньшее единицы, т.е. текущий бит будет равен нулю. Теперь повторем вычитание текущего множителя 2^6 - 1-2^6*0=1. Таким образо дроходим до множителя 2^0 - 1/2^0=1 - т.е. последний бит равен 1.

Число = 129;
Битность = 8;
Биты = "";
Для
й = 1 По Битность Цикл
   
Множитель = pow(2, Битность - й);
   
Бит = Цел(Число / Множитель);
   
Число = Число - Множитель * Бит;
   
Биты = Биты + Бит;
КонецЦикла;
Сообщить(Биты);

2) Для получения битов начиная с младшего до страшего:

Исходное число, например 129, делим оператором % на 2, получаем остаток от деления 1 - это крайний левый бит. Теперь делим нацело 129/2, получаем 64. Далее 64 опять делим оператором % на 2 - получаем следующий бит - 0. Продолжаем так вычислять пока не получим нужные 8 бит.

Число = 129;
Битность = 8;
Биты = "";
Для
й = 1 По Битность Цикл
   
Бит = Число % 2;
   
Число = Цел(Число / 2);
   
Биты = Строка(Бит) + Биты;
КонецЦикла;
Сообщить(Биты);

3) В вышеописаных способах мы изменяем входное число, например 129, но можно вычислять биты не изменяя его. Например старший бит это ЦЕЛ(129/2^7)%2=1, следующий ЦЕЛ(129/2^6)%2=0 и так далее до младшего бита ЦЕЛ(129/2^0)%2=1

Число = 129;
Битность = 32;
Биты = "";
Для
й = 1 По Битность Цикл
   
Бит = Цел(Число / pow(2, Битность - й)) % 2;
   
Биты = Биты + Строка(Бит);
КонецЦикла;
Сообщить(Биты);

Привожу код готовых функций XOR, LR, RR, AND, OR при помощи которых можно вычислить практически любой распространенный хэш

Функция _XOR(Знач A, Знач B, L = 8)
   
R = 0;
    Для
I = 1 по L Цикл
       
M = POW(2, L - I);
       
R = R + M * ?((A < M) = (B < M), 0, 1);
       
A = ?(A < M, A, A - M);
       
B = ?(B < M, B, B - M);
    КонецЦикла;
    Возврат
R;
КонецФункции
 
Функция _LR(Знач A, S, L = 8)
    Возврат
Цел(A / POW(2, L - S)) + POW(2, S) * (A % POW(2, L - S));
КонецФункции

Функция
_RR(Знач A, S, L = 8)
    Возврат
Цел(A / POW(2, S)) + POW(2, S) * (A % POW(2, S));
КонецФункции

Функция
_AND(Знач A, Знач B, L = 8)
   
R = 0;
    Для
I = 1 по L Цикл
       
M = POW(2, L - I);
       
R = R + M * ?((A >= M) AND (B >= M), 1, 0);
       
A = ?(A < M, A, A - M);
       
B = ?(B < M, B, B - M);
    КонецЦикла;
    Возврат
R;
КонецФункции

Функция
_OR(Знач A, Знач B, L = 8)
   
R = 0;
    Для
I = 1 по L Цикл
       
M = POW(2, L - I);
       
R = R + M * ?((A >= M) OR(B >= M), 1, 0);
       
A = ?(A < M, A, A - M);
       
B = ?(B < M, B, B - M);
    КонецЦикла;
    Возврат
R;
КонецФункции

Так же в обработку встроен простой замер производительности, который показывает, что циклы в одну строку показывают заметный прирост только при включенном сеансе отладки :)

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1714    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4316    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7343    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7817    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4414    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8793    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7713    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. AlexO 135 13.03.13 17:34 Сейчас в теме
Антон, вы поразрядно сравниваете числа. По позиции, мантиссе числа.
А не биты.
2. Антон Ширяев 527 13.03.13 17:40 Сейчас в теме
(1)
Чем по сути отличается поразрядное сравнение числа от сравнения битов из которых состоит это число?
3. AlexO 135 13.03.13 17:44 Сейчас в теме
(2) Антон Ширяев,
Вы сравниваете мантиссу чисел, по позиции-разрядности.
А такое работает только там, где байтам поставлено в соответствии какое-либо число (любой системы счисления) - например, с кодировками такое прокатывает, где только числа в качестве кода. А вот реальный двоичный код, где нужно настоящее ПОБИТОВОЕ сравнение - данным методом уже никакого результат не получим.
4. Антон Ширяев 527 13.03.13 17:57 Сейчас в теме
(3) Проблема в том, что нет возможности в 1С8 прочитать двоичный файл побайтово. Можно прочитать только его весь в ДвоичныеДанные. Дальше эти ДвоичныеДанные можно закодировать в BASE64 и уже постепенно раскодируя из BASE64 в числа делать с ними что угодно. Писать обратно опять через то же место :)
5. andrewks 1367 13.03.13 18:00 Сейчас в теме
(4) Антон Ширяев, а почему бы не попробовать читать как unicode? (вот только вопрос, что считается, когда в конце останется один байт, а не два - надо проверять)
7. Антон Ширяев 527 13.03.13 18:15 Сейчас в теме
(5) andrewks,
В обработке как раз идет разбор Unicode-строки на байты и последующее хэширование строки. Кириллица в Unicode занимает от двух байт для основных букв и более (например буква ё).
Если читать бинарные файлы как Unicode думаю ничего хорошего не выйдет, т.к. 100% попадется символ не используемый в Unicode.
Обработку писал давно - больше года назад, нашел время опубликовать только сейчас. В статье не указал как разобрать Unicode-строку на байты, возможно дополню позже.
8. andrewks 1367 13.03.13 20:48 Сейчас в теме
(7) Антон Ширяев,
Кириллица в Unicode занимает от двух байт для основных букв и более (например буква ё)

Вы путаете с UTF-8. Unicode-символ в виде UTF-16LE занимает стабильно 2 байта (хоть английские, хоть русские буквы)
13. Антон Ширяев 527 14.03.13 09:08 Сейчас в теме
(8) andrewks,
Вы путаете с UTF-8. Unicode-символ в виде UTF-16LE занимает стабильно 2 байта (хоть английские, хоть русские буквы)


Для начала заглянем в Википедию.
UTF-8 и UTF-16LE это способы представления Юникода.
Посмотрим пример где используются хеши SHA-1 в 1C - на память приходит пока только хеши паролей пользователей.
Кодируется как раз представление пароля в UTF-8.

Сейчас посмотрел - в списке доступных кодировок в 1С есть UTF-16. Попробую поиграться и отпишусь о результатах.

Действительно все что я писал выше я подразумевал, что Юникод закодирован UTF-8.
35. premierex 204 17.02.16 08:35 Сейчас в теме
(7) Антон Ширяев, Ildarovich вот в этой публикации "предлагает ограничиться только символами, имеющимися в таблице windows-1251". И даже приводит функцию преобразования. Вполне рабочий вариант.
А идея реализации бинарных операций очень даже неплохая. Только про инверсию забыли, незаслуженно, имхо.
40. MuI_I_Ika 1109 27.08.19 15:08 Сейчас в теме
Очень большая просьба к автору разжевать как работает данный цикл. Уже всю голову сломал. Комментариев в описании не хватает.

// Разбираем исходную строку в массив из 16 слов W (1 слово - 32-битное число)
	// Переводим UNICODE номер символа в UTF-8 представление (1 символ может занимать от 1 до 6 байт)
	Для I=1 По СтрДлина(S) Цикл
		
		C=КодСимвола(S,I);
		
		Если C<128 Тогда
			// Если код символа меньше 128, то на выходе получаем один байт N
			N=C;
			G=0;
		Иначе
			// Вычмсляем количество дополнительных байт G для преобразования символов с кодом больше 127
			G=Цел((Log©/Log(2)-6)/5)+1;
			// Вычисляем старшие биты D для первого байта
			D=128;
			Для J=1 По G Цикл
				D=D+pow(2,7-J);
			КонецЦикла;
			M=pow(64,G);
			// Получаем значение первого байта
			N=Цел(C/M)+D;
			// Отрезаем старшие биты от исходного кода символа
			C=C%M;
		КонецЕсли;
		
		Для J=0 По G Цикл
			
			// Записываем байт N в нужное положение слова R
			R=R+pow(256,3-L%4)*N;
			L=L+1;
			Если L%4=0 Тогда
				// Длина сообщения кратна 4 - записываем времееное слово R в массив стов W и обнуляем R
				W[Цел((L-1)%64/4)]=R;
				R=0;
				Если L%64=0 Тогда
					// Длина сообщения достигла 512 бит - выполняем раунд SHA-1
					_SHA1_ROUND(W,H);
				КонецЕсли;
			КонецЕсли;
			Если J=G Тогда
				// Это последня итерация, дальше рассчитывать не нужно
				Прервать;
			КонецЕсли;
			M=pow(64,G-J-1);
			// Получаем значение дополнительного байта
			N=Цел(C/M)+128;
			// Отрезаем старшие биты от текущего кода символа
			C=C%M;
			
		КонецЦикла;
		
	КонецЦикла;
Показать
21. andrewks 1367 14.03.13 14:31 Сейчас в теме
возможно, выгоднее тогда будет заюзать ЧтениеТекста с кодировкой ANSI и посимвольным чтением Прочитать(1)
однако ж здесь тоже таится засада - в 8-ке 1с перекодирует строки в 2-х байтовый Unicode
28. Антон Ширяев 527 18.03.13 10:26 Сейчас в теме
Попробовал прочитать заранее подготовленный файл со всеми двухбайтовыми символами

Текст = Новый ЧтениеТекста("c:\1.bin", КодировкаТекста.UTF16);
Для й = 0 По 65535 Цикл
С = Текст.Прочитать(1);
Если Кодсимвола(С) <> й Тогда
Сообщить("Кодсимвола = " + Кодсимвола(С) + " Й = " + й);
КонецЕсли;
КонецЦикла;
Текст.Закрыть();

Вместо символов "00 D8" - "FF DF", кроме символов "FF DB" и "00 DC" читается символ "FD FF".

Т.е. никак не получается прочитать бинарный файл через ЧтениеТекста...
29. AlexO 135 18.03.13 10:43 Сейчас в теме
(28) Антон Ширяев,
Т.е. никак не получается прочитать бинарный файл через ЧтениеТекста

Так это ЧТЕНИЕ ТЕКСТА :)
А не бинарника. 1С не осилила реализовать "ПрочитатьБинарныйФайлПобайтово".
Да и текст читает эта ЧтениеТекста - сплошной мрак и тормоза. Лучше и быстрее на порядок для чтения текста - использовать FileSystemObject.
6. andrewks 1367 13.03.13 18:03 Сейчас в теме
а если абстрагироваться от кросс-платформенности, то можно привлечь SAPI.spFileStream, например
9. andrewks 1367 13.03.13 20:53 Сейчас в теме
т.к. 100% попадется символ не используемый в Unicode.

вот этого не понял вообще. двухбайтный юникод идёт от 0000 до FFFF. что значит "символ не используемый в Unicode"?
10. Поручик 4670 14.03.13 01:04 Сейчас в теме
Я тоже вброшу. символ не используемый в Unicode. Символ EOF или имеется в виду, что размер файла не будет кратен 2?
11. aet 54 14.03.13 05:00 Сейчас в теме
Мне тоже нравятся всякие математические штуки на 1С ненужные в реальных системах учета, поэтому плюс.
12. yuraos 991 14.03.13 06:28 Сейчас в теме
(11)
Математические штучки, олимпиадные задачки.
Это все хорошо с познавательной точки зрения.
---
Только вот беда...
Для практического применения реализация алгоритмов в коде 1С
не самый лутший вариант с точки зрения производительности.
---
ВК эти же алгоритмы выполняют более эффективнее.
Можно сравнить хотя бы на примере
задачи выгрузки результата запроса ADO
Можно сделать все в коде 1С,
но средствами ВК получается на порядок эффективней
14. Aleksey.Bochkov 3659 14.03.13 09:48 Сейчас в теме
(0) а в 8.3 для вычисления хэша уже сделали полноценные методы встроенного языка
15. AlexO 135 14.03.13 10:00 Сейчас в теме
(14) Aleksey.Bochkov,
а в 8.3

а в 9.0 обещают, что кодить не надо будет совсем :)
27. yuraos 991 14.03.13 17:26 Сейчас в теме
(15)
ага, вся платформа будет "управляемой", конфигуратор - тоже.
в нем останутся одни "ТЫЧИ".
НАЖМИ НА "ТЫЧУ" - И ПОЛУЧИШЬ РЕЗУЛЬТАТ!!!
;)))
16. Антон Ширяев 527 14.03.13 10:11 Сейчас в теме
Итак, попробовал записать в файл все символы средствами 1с

Текст = Новый ЗаписьТекста("c:\t2.txt", КодировкаТекста.UTF16);
Для й = 0 По 65535 Цикл
Текст.Записать(Символ(й));
КонецЦикла;
Текст.Закрыть();

Получил следующие проблемы
1) В начало файла пишется лишний символ - заголовок "FF FE"
2) Вместо символа "0A 00" пишется 2 символа "0A 00 OD 00"
3) Вместо символов "00 D8" - "FF DF", кроме символов "FF DB" и "00 DC" пишется символ "FD FF"

Т.е. через ЗаписьТекста() бинарные файлы писать не получится. Поэкспериментирую еще с чтением.
17. AlexO 135 14.03.13 10:18 Сейчас в теме
(16) Антон Ширяев,
1) В начало файла пишется лишний символ - заголовок "FF FE"

это "стандарт" у 1С (один из многих "стандартов 1С", за соблюдение которых тут ратуют тру-1сники): в любой, даже пустой текстовик - писать перевод каретки в начале. За кой - тайна за семью печатями.
18. Антон Ширяев 527 14.03.13 10:51 Сейчас в теме
(17)
Снова смотрим Википедию :)
1С тут ни при чем, "FF FE" - это заголовок обозначающий что файл закодирован UTF-16LE. Для UTF-8 пишется "EF BB BF"
19. AlexO 135 14.03.13 11:53 Сейчас в теме
(18) Антон Ширяев,
Да, похоже, насчет первых символов - это от кодировок..
а на кой тогда? все равно путаница с кодировками...
24. AlexO 135 14.03.13 15:09 Сейчас в теме
(18) Антон Ширяев,
так ведь эти символы вообще практического никакого влияния и значения не оказывают..
только под ногами "мешаются".
Видимо, 1С - как всегда! - запользовало при разработке платформы некую сторонне-бесплатную (когда 1С что-либо лицензировало у третьих фирм? ну, собственно, и качество отсюда, сама-то ни в дугу, ни в красную армию разработать что-либо...) примочку, которая "на автомате" пихает "лишние" символы в файл.
25. andrewks 1367 14.03.13 16:37 Сейчас в теме
(24) не сказать, чтобы они лишние, просто неплохо было бы предоставить возможность управлять выводом маркеров, чего сделано ими не было
20. andrewks 1367 14.03.13 14:25 Сейчас в теме
(16) Антон Ширяев, да, с BOM в 1С засада - нельзя управлять записью маркера, она его пишет всегда. вот только речь-то была не про запись, а про чтение :-)
однако, видимо, траблы с перекодировкой некоторых служебных символов всё равно будут
22. andrewks 1367 14.03.13 14:33 Сейчас в теме
видимо, извращаться через разбор BASE64 единственный гарантированный способ, если религией запрещены ВК
23. AlexO 135 14.03.13 15:02 Сейчас в теме
Самое интересное - что сама 1С юзает вовсю двоичную запись в платформе, но программистам - ни-ни.
(22) andrewks,
видимо, извращаться

Почему извращаться?! Обычная сериализация нетекствоого содержимого.
через разбор BASE64

Так кто-бы еще сохранил в BASE64, чтобы потом разбирать в 1С....
26. andrewks 1367 14.03.13 16:39 Сейчас в теме
а уж за то, что объект ДвоичныеДанные недоделан, и не позволяет практически ничего с ними делать - я готов был 1соцев укусить, когда писал свою обработку по шифрованию файлов отчётности для ФСРАР
30. LexSeIch 210 20.03.13 05:35 Сейчас в теме
Мир этому дому. Статья заинтересовала - взял на заметку. Автору спасибо.
31. NGPhoenix 8 03.06.14 22:08 Сейчас в теме
Проверил обработку на предмет совпадения пароля пользователя и заявленного хеша. Совпало!!! Значит обработка точно кодирует. Хочу на основе данной обработки попробывать обратный подход (брутфорс). Посмотрим, что получиться.
32. NGPhoenix 8 04.06.14 07:37 Сейчас в теме
Брутфорс SHA1 утомительное дело. Слишком долго. Даже трехзначный пароль за 5 часов полностью не перебрался. Но к работе обработки это дела не имеет.
33. andrushok_7 20.01.15 15:55 Сейчас в теме
Обработка неверно считает хэш по алгоритму SHA-1, проверил на многочисленных онлайн-генераторах
34. Brawler 453 04.02.16 10:56 Сейчас в теме
Скоро, скоро придет мир в этот дом, однако не на 100%
http://v8.1c.ru/o7/201602bin/index.htm
36. premierex 204 02.03.16 14:31 Сейчас в теме
(0) Раз автор публикации не желает обнародовать функцию инверсии числа, попытаюсь сделать это сам:
Функция _INV(Знач A, L = 32) Экспорт
    Возврат POW(2, L) - 1 - A;
КонецФункции 
37. ildarovich 7846 22.06.16 12:15 Сейчас в теме
Вот в этой статье: Простая и быстрая эмуляция операций с битовыми строками приведен другой способ реализации операций с битовыми строками в языке 1С. Он не требует использования циклов и поэтому гораздо быстрее. По оценкам, сделанным в той статье, если длина битовой строки равна 300 символов, то выигрыш достигает 15-ти раз.
Не знаю, подойдет ли метод из упомянутой статьи для решения этой задачи.
42. dctvghbdtn 03.10.21 12:52 Сейчас в теме
(37) А если в районе 32 или 64 бит, будет выигрыш? Ведь в основном оперируют такими разрядами.
43. ildarovich 7846 04.10.21 11:37 Сейчас в теме
(42) Это, скорее всего, пограничный случай. Нужно тестирование. Можно и другие приемы оптимизации быстродействия в этой задаче применить. Но есть ли в этом практическая необходимость?
44. dctvghbdtn 04.10.21 12:54 Сейчас в теме
(43) Всегда есть - стремление к лучшему. И люди забыли эру становления компьютеров, когда оптимизация на пару байтов, тактов процессора были очень важны, т.к. производительность компьютеров, вместимость носителей была очень мала. Поэтому тема всегда актуальна.
38. renmy 92 17.04.17 15:34 Сейчас в теме
Сдвиг вправо неправильно работает.
Мой вариант:
Функция _RR(Знач A, S)
    Возврат Цел(A / POW(2, S)) + ?(A<0,A % POW(2, S),0);
КонецФункции


И сдвиг вправо с замещением(>>>):
Функция _RRR(Знач A, S)
    Возврат Цел(A / POW(2, S)) * ?(A<0,-1,1);
КонецФункции
41. dctvghbdtn 29.07.21 22:22 Сейчас в теме
(38) А они будут работать с большими числами?
"В случае арифметического переполнения или невозможности вычислить результат происходит ошибка "Неправильное значение аргумента встроенной функции (Pow)".
39. Mails79 12 26.02.18 23:18 Сейчас в теме
Большое спасибо, для версий платформы ниже 8.3.11 просто незаменимо.
Оставьте свое сообщение