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

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

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

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

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

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

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

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

Исходное число, например 129, делим на 2#k8SjZc9Dxk7, если получается больше единицы, то первый бит — 1, иначе 0. Далее Из исходного числа 129 вычитаем 2#k8SjZc9Dxk7*бит и получаем 129-128*1=1. Далее получаем следующий бит — 1 делим на 2#k8SjZc9Dxk6, получаем число меньшее единицы, т.е. текущий бит будет равен нулю. Теперь повторем вычитание текущего множителя 2#k8SjZc9Dxk6 — 1-2#k8SjZc9Dxk6*0=1. Таким образо дроходим до множителя 2#k8SjZc9Dxk0 — 1/2#k8SjZc9Dxk0=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#k8SjZc9Dxk7)%2=1, следующий ЦЕЛ(129/2#k8SjZc9Dxk6)%2=0 и так далее до младшего бита ЦЕЛ(129/2#k8SjZc9Dxk0)%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;
КонецФункции

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

40 Comments

AlexO 13.03.2013 at 17:34

Антон, вы поразрядно сравниваете числа. По позиции, мантиссе числа.

А не биты.

Reply ↓
Антон Ширяев 13.03.2013 at 17:40

(1)

Чем по сути отличается поразрядное сравнение числа от сравнения битов из которых состоит это число?

Reply ↓
AlexO 13.03.2013 at 17:44

(2) Антон Ширяев,

Вы сравниваете мантиссу чисел, по позиции-разрядности.

А такое работает только там, где байтам поставлено в соответствии какое-либо число (любой системы счисления) — например, с кодировками такое прокатывает, где только числа в качестве кода. А вот реальный двоичный код, где нужно настоящее ПОБИТОВОЕ сравнение — данным методом уже никакого результат не получим.

Reply ↓
Антон Ширяев 13.03.2013 at 17:57

(3) Проблема в том, что нет возможности в 1С8 прочитать двоичный файл побайтово. Можно прочитать только его весь в ДвоичныеДанные. Дальше эти ДвоичныеДанные можно закодировать в BASE64 и уже постепенно раскодируя из BASE64 в числа делать с ними что угодно. Писать обратно опять через то же место 🙂

Reply ↓
andrewks 13.03.2013 at 18:00

(4) Антон Ширяев, а почему бы не попробовать читать как unicode? (вот только вопрос, что считается, когда в конце останется один байт, а не два — надо проверять)

Reply ↓
andrewks 13.03.2013 at 18:03

а если абстрагироваться от кросс-платформенности, то можно привлечь SAPI.spFileStream, например

Reply ↓
Антон Ширяев 13.03.2013 at 18:15

(5) andrewks,

В обработке как раз идет разбор Unicode-строки на байты и последующее хэширование строки. Кириллица в Unicode занимает от двух байт для основных букв и более (например буква ё).

Если читать бинарные файлы как Unicode думаю ничего хорошего не выйдет, т.к. 100% попадется символ не используемый в Unicode.

Обработку писал давно — больше года назад, нашел время опубликовать только сейчас. В статье не указал как разобрать Unicode-строку на байты, возможно дополню позже.

Reply ↓
andrewks 13.03.2013 at 20:48

(7) Антон Ширяев,

Кириллица в Unicode занимает от двух байт для основных букв и более (например буква ё)

Вы путаете с UTF-8. Unicode-символ в виде UTF-16LE занимает стабильно 2 байта (хоть английские, хоть русские буквы)

Reply ↓
andrewks 13.03.2013 at 20:53

т.к. 100% попадется символ не используемый в Unicode.

вот этого не понял вообще. двухбайтный юникод идёт от 0000 до FFFF. что значит «символ не используемый в Unicode»?

Reply ↓
Поручик 14.03.2013 at 01:04

Я тоже вброшу. символ не используемый в Unicode. Символ EOF или имеется в виду, что размер файла не будет кратен 2?

Reply ↓
aet 14.03.2013 at 05:00

Мне тоже нравятся всякие математические штуки на 1С ненужные в реальных системах учета, поэтому плюс.

Reply ↓
yuraos 14.03.2013 at 06:28

(11)

Математические штучки, олимпиадные задачки.

Это все хорошо с познавательной точки зрения.

—

Только вот беда…

Для практического применения реализация алгоритмов в коде 1С

не самый лутший вариант с точки зрения производительности.

—

ВК эти же алгоритмы выполняют более эффективнее.

Можно сравнить хотя бы на примере

задачи выгрузки результата запроса ADO

Можно сделать все в коде 1С,

но средствами ВК получается на порядок эффективней

Reply ↓
Антон Ширяев 14.03.2013 at 09:08

(8) andrewks,

Вы путаете с UTF-8. Unicode-символ в виде UTF-16LE занимает стабильно 2 байта (хоть английские, хоть русские буквы)

Для начала заглянем в Википедию.

UTF-8 и UTF-16LE это способы представления Юникода.

Посмотрим пример где используются хеши SHA-1 в 1C — на память приходит пока только хеши паролей пользователей.

Кодируется как раз представление пароля в UTF-8.

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

Действительно все что я писал выше я подразумевал, что Юникод закодирован UTF-8.

Reply ↓
Aleksey.Bochkov 14.03.2013 at 09:48

(0) а в 8.3 для вычисления хэша уже сделали полноценные методы встроенного языка

Reply ↓
AlexO 14.03.2013 at 10:00

(14) Aleksey.Bochkov,

а в 8.3

а в 9.0 обещают, что кодить не надо будет совсем 🙂

Reply ↓
Антон Ширяев 14.03.2013 at 10:11

Итак, попробовал записать в файл все символы средствами 1с

Текст = Новый ЗаписьТекста(«c: 2.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»

Т.е. через ЗаписьТекста() бинарные файлы писать не получится. Поэкспериментирую еще с чтением.

Reply ↓
AlexO 14.03.2013 at 10:18

(16) Антон Ширяев,

1) В начало файла пишется лишний символ — заголовок «FF FE»

это «стандарт» у 1С (один из многих «стандартов 1С», за соблюдение которых тут ратуют тру-1сники): в любой, даже пустой текстовик — писать перевод каретки в начале. За кой — тайна за семью печатями.

Reply ↓
Антон Ширяев 14.03.2013 at 10:51

(17)

Снова смотрим Википедию 🙂

1С тут ни при чем, «FF FE» — это заголовок обозначающий что файл закодирован UTF-16LE. Для UTF-8 пишется «EF BB BF»

Reply ↓
AlexO 14.03.2013 at 11:53

(18) Антон Ширяев,

Да, похоже, насчет первых символов — это от кодировок..

а на кой тогда? все равно путаница с кодировками…

Reply ↓
andrewks 14.03.2013 at 14:25

(16) Антон Ширяев, да, с BOM в 1С засада — нельзя управлять записью маркера, она его пишет всегда. вот только речь-то была не про запись, а про чтение 🙂

однако, видимо, траблы с перекодировкой некоторых служебных символов всё равно будут

Reply ↓
andrewks 14.03.2013 at 14:31

возможно, выгоднее тогда будет заюзать ЧтениеТекста с кодировкой ANSI и посимвольным чтением Прочитать(1)

однако ж здесь тоже таится засада — в 8-ке 1с перекодирует строки в 2-х байтовый Unicode

Reply ↓
andrewks 14.03.2013 at 14:33

видимо, извращаться через разбор BASE64 единственный гарантированный способ, если религией запрещены ВК

Reply ↓
AlexO 14.03.2013 at 15:02

Самое интересное — что сама 1С юзает вовсю двоичную запись в платформе, но программистам — ни-ни.

(22) andrewks,

видимо, извращаться

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

через разбор BASE64

Так кто-бы еще сохранил в BASE64, чтобы потом разбирать в 1С….

Reply ↓
AlexO 14.03.2013 at 15:09

(18) Антон Ширяев,

так ведь эти символы вообще практического никакого влияния и значения не оказывают..

только под ногами «мешаются».

Видимо, 1С — как всегда! — запользовало при разработке платформы некую сторонне-бесплатную (когда 1С что-либо лицензировало у третьих фирм? ну, собственно, и качество отсюда, сама-то ни в дугу, ни в красную армию разработать что-либо…) примочку, которая «на автомате» пихает «лишние» символы в файл.

Reply ↓
andrewks 14.03.2013 at 16:37

(24) не сказать, чтобы они лишние, просто неплохо было бы предоставить возможность управлять выводом маркеров, чего сделано ими не было

Reply ↓
andrewks 14.03.2013 at 16:39

а уж за то, что объект ДвоичныеДанные недоделан, и не позволяет практически ничего с ними делать — я готов был 1соцев укусить, когда писал свою обработку по шифрованию файлов отчётности для ФСРАР

Reply ↓
yuraos 14.03.2013 at 17:26

(15)

ага, вся платформа будет «управляемой», конфигуратор — тоже.

в нем останутся одни «ТЫЧИ».

НАЖМИ НА «ТЫЧУ» — И ПОЛУЧИШЬ РЕЗУЛЬТАТ!!!

;)))

Reply ↓
Антон Ширяев 18.03.2013 at 10:26

Попробовал прочитать заранее подготовленный файл со всеми двухбайтовыми символами

Текст = Новый ЧтениеТекста(«c:1.bin», КодировкаТекста.UTF16);

Для й = 0 По 65535 Цикл

С = Текст.Прочитать(1);

Если Кодсимвола(С) <> й Тогда

Сообщить(«Кодсимвола = » + Кодсимвола(С) + » Й = » + й);

КонецЕсли;

КонецЦикла;

Текст.Закрыть();

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

Т.е. никак не получается прочитать бинарный файл через ЧтениеТекста…

Reply ↓
AlexO 18.03.2013 at 10:43

(28) Антон Ширяев,

Т.е. никак не получается прочитать бинарный файл через ЧтениеТекста

Так это ЧТЕНИЕ ТЕКСТА 🙂

А не бинарника. 1С не осилила реализовать «ПрочитатьБинарныйФайлПобайтово».

Да и текст читает эта ЧтениеТекста — сплошной мрак и тормоза. Лучше и быстрее на порядок для чтения текста — использовать FileSystemObject.

Reply ↓
LexSeIch 20.03.2013 at 05:35

Мир этому дому. Статья заинтересовала — взял на заметку. Автору спасибо.

Reply ↓
NGPhoenix 03.06.2014 at 22:08

Проверил обработку на предмет совпадения пароля пользователя и заявленного хеша. Совпало!!! Значит обработка точно кодирует. Хочу на основе данной обработки попробывать обратный подход (брутфорс). Посмотрим, что получиться.

Reply ↓
NGPhoenix 04.06.2014 at 07:37

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

Reply ↓
andrushok_7 20.01.2015 at 15:55

Обработка неверно считает хэш по алгоритму SHA-1, проверил на многочисленных онлайн-генераторах

Reply ↓
Brawler 04.02.2016 at 10:56

Скоро, скоро придет мир в этот дом, однако не на 100%

http://v8.1c.ru/o7/201602bin/index.htm

Reply ↓
premierex 17.02.2016 at 08:35

(7) Антон Ширяев, Ildarovich вот в этой публикации «предлагает ограничиться только символами, имеющимися в таблице windows-1251». И даже приводит функцию преобразования. Вполне рабочий вариант.

А идея реализации бинарных операций очень даже неплохая. Только про инверсию забыли, незаслуженно, имхо.

Reply ↓
premierex 02.03.2016 at 14:31
(0) Раз автор публикации не желает обнародовать функцию инверсии числа, попытаюсь сделать это сам:
```
Функция _INV(Знач A, L = 32) Экспорт
Возврат POW(2, L) — 1 — A;
КонецФункции
```
Reply ↓
ildarovich 22.06.2016 at 12:15

Вот в этой статье: Простая и быстрая эмуляция операций с битовыми строками приведен другой способ реализации операций с битовыми строками в языке 1С. Он не требует использования циклов и поэтому гораздо быстрее. По оценкам, сделанным в той статье, если длина битовой строки равна 300 символов, то выигрыш достигает 15-ти раз.

Не знаю, подойдет ли метод из упомянутой статьи для решения этой задачи.

Reply ↓

renmy 17.04.2017 at 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);
КонецФункции

Reply ↓

Mails79 26.02.2018 at 23:18

Большое спасибо, для версий платформы ниже 8.3.11 просто незаменимо.

Reply ↓

MuI_I_Ika 27.08.2019 at 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;

КонецЦикла;

КонецЦикла;

Показать

Reply ↓

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

Related Posts

40 Comments

Leave a Comment Отменить ответ