MiniM. Saving time.


| About | Download | Tools | Knowledge Base | How to Buy |

MiniM Overview

Getting Started

Download

Documentation

Tools

Cache Tools

GT.M Tools

Knowledge Base

FAQ

Contacts

Copyrights

MiniM Additional Tools | Jun 18, 2012

Генератор псевдослучайных чисел A4RNG

A4rng - это потоковый генератор псевдослучайных чисел с переменным и многократно добавляемым ключем. Используется P-блок размером в 256 байт, сами элементы представляют собой перестановку чисел от 0 до 255, перестановка является функцией ключа или строки инициализации (зависит в т.ч. от дополнительного вектора IV). Базовая функция очень похожа на аналогичную используемую в алгоритме RC4 (1987 Ron Rivest RSA) но со значительной доработкой, перестановка выполняется еще в "глубину" по таблице P и несколько раз с использованием дополнительного смещения O (для ускорения лавинообразности). A4rng может находится в 256! состояниях , что достаточно для большинства приложений на много лет. Для устранения проблемы (RC4 - подобных алгоритмов )корреляции ключа и выходного потока, генератор пропускает первые A4RNG_DROP_N байт, прежде чем начнет отдавать значения.

Оглавление

  1. Иниализация генератора
  2. Прочитать N байт
  3. Добавит вектор(строку) в "мешанину"
  4. Пример использования всех функций zdll
  5. Дополнительно: C-API
  6. Структура ключа хранения
  7. Внутренний API (ядро)
  8. Базовый Rng-API
  9. Дополнительно Hash-API
  10. Дополнительно Crypto-API
  11. Служебные для ключа
  12. Утилиты
1. Иниализация генератора

В качестве параметров передается:

Номер параметраОписание
1парольная фраза, длина ограничена только размером переменной MINIM_STR_MAX c-коде, длина как DWORD (32 бита)
2сколько раз крутить блок перестановок , по умолчанию блок вращается A4RNG_ROTATE_R раз (768)
3Сколько вращать байт, обслуживает A4RNG_ROTATE_Y раз по умолчанию (17)

Возвращается: значение/структура в которой хранится состояние генератора.

Пример вызова:

 s %Z4=$zdll("call","ZA4rng.dll","init","ключ",1024,17)
 s %Z3=$zdll("call","ZA4rng.dll","init","ключ")

2. Прочитать N байт

Прочитать N байт, если без параметров, то вертаем 1 байт.

Номер параметраОписание
1обязательнвый параметр, это имя переменной, где хранится состояние генератора, $NAME(%Z4VARLOCAL)
2длина генерируемой последовательности в байтах, не более MINIM_STR_MAX (лишнее обрезается)

Возвращает: строку байтов длиной 2го параметра или 1 байт если параметр не указан.

Пример:

 s b99=$zdll("call","ZA4rng.dll","rng",$na(%Z4),99)
 w !,$l(b99)

3. Добавит вектор(строку) в "мешанину"

Добавляем в существующее состояние генератора дополнительную последовательность IV (как строка). Обязательный параметр ето имя переменной, где хранится состояние генератора. Возвращает 0

Пример:

 i $zdll("call","ZA4rng.dll","vector",$na(%Z4),"смещаемгенератор")

4. Пример использования всех функций zdll

za4rng
 w $zdll("load","ZA4rng.dll")
 ;
 ;иниализация генератора, в %Z4 храним состояние генератора
 s (%Z0,%Z4)=$zdll("call","ZA4rng.dll","init","testkey")
 ;
 ;прочитать N байт, если без параметров, то вертаем 1 байт
 s ret=$zdll("call","ZA4rng.dll","rng",$na(%Z4),99)
 w !,$l(ret)
 ;
 ;проверка, что переменная %Z4 модифицирована
 i %Z0=%Z4 w !,"rng:problem modify %Z4"
 ;
 ;добавит IV вектор в ключ
 i $zdll("call","ZA4rng.dll","vector",$na(%Z4),"addingvector")
 ;
 ;шифровать или дешифровать строку, в данном случе шифровать, т.к. что
 ;бы дешифровать придется привести генератор в тоже состояние, что и до
 ;вызова,т.е. можно сохранить переменную %Z4
 s %Z2=%Z4
 ;
 ;строка для шифрования
 s text="plain"
 ;получили зашифрованую строку
 s code=$zdll("call","ZA4rng.dll","ecode",$na(%Z4),text)
 ;
 ;здесь уже дешифруем используя предыдущее состояние генератора из %Z2,
 ;в %Z4 уже другое состояне, после преобразования %Z2==%Z4!
 s plain=$zdll("call","ZA4rng.dll","ecode",$na(%Z2),code)
 ;
 w !,plain,"==",text
 ;
 ;пример хеширования строки/строк
 w !,"hash:",$zdll("call","ZA4rng.dll","hash","ключдляхеша",plain)
 ;
 w $zdll("unload","ZA4rng.dll")
 q
 ;

5. Дополнительно: C-API

Важно! Все генераторы псч должны инициализироватся перед использованием, чем интересней строка иницализации (и/или восстановление сохраненого состояния) тем лучше последовательность (хоть тесты и показывают, что генерится почти равномерное распределение значений). не забывайте почаще добавлять IV при длительных генерациях.

6. Структура ключа хранения

struct A4RNG_T
{
  BYTE P[A4RNG_P_SIZE]; // таблица перестановок, 0-255 (аналогично RC4)
  BYTE S,N,O; 	        // индексы в таблице S-случаный,N-последовательный,
                        // накапливамое смещение O для увеличения 
                        // лавинообразности 
  WORD R,Y;   	        // сколько раз крутануть блок 
                        // (при заполнении вектора) и байт
};

7. Внутренний API (ядро)

A4RNG_EXPORT BYTE __A4rng_F(A4RNG_T *e, BYTE o);

Базовая функция F преобразования байта. Байт о подмешивается в поток на выходе байт после преобразования. Алгоритм работает так: выполняется перестановка чисел от 0 до 255, применяются 3 счетчика, N,S,O , N-последовательно обегает все значения таблицы перестановок, S - выбирает псевдослучайное значение для обмена в таблице, O- "ускоритель" лавинообразности перестановки, таблица используется несколько раз в "глубину", прежде чем получить результат.

A4RNG_EXPORT BYTE __A4rng_B(A4RNG_T *e, WORD n);

Получаем следующий байт. N-сколько раз крутануть байт в таблице перестановок (функция F) прежде, чем его отдать в работу.

A4RNG_EXPORT WORD __A4rng_W(A4RNG_T *e, WORD n);

Получаем 16-бит (сдвоенный байт).

A4RNG_EXPORT BYTE __A4rng_A(A4RNG_T *e, BYTE b, WORD n);

Добавить байт в мешанину, покрутить N-раз. Фактически дополнительная инициализация блока перестановок.

Данные функции _F,_B,_A,_W являются ядром генератора A4rng.

8. Базовый Rng-API

A4RNG_EXPORT BYTE A4rng_B(A4RNG_T *e);

Получить сл.байт prng

A4RNG_EXPORT int  A4rng_S(A4RNG_T *e, BYTE *o, DWORD z);

Получить блок байтов длиной z

A4RNG_EXPORT int  A4rng_V(A4RNG_T *e, BYTE *v, DWORD z);

Добавить вектор в мешанину.

A4RNG_EXPORT void 
A4rng_I(A4RNG_T *e, BYTE *k, DWORD z, WORD r, WORD y);

Первоначальная инициалализация, параметры:

  • e - структура ключа,
  • k - ключ,
  • z - длина ключа,
  • r - сколько крутить блок >0
  • y - сколько крутить байт >0

9. Дополнительно Hash-API

На базе предыдущего функционала, пример организации функции хеширования

Структура:

typedef struct _A4RNG_HASH_T
{
  QWORD   L;            	  // сколько всего пропихнули символов..
  BYTE    H[A4RNG_HASH_SIZE];  // здесь накапливается текущий хеш
  A4RNG_T E;            	 // нам в помощь при формировании потока.
} A4RNG_HASH_T;
A4RNG_EXPORT void __A4rng_H(A4RNG_HASH_T *e, BYTE b);

Базовая мешалка хеша.

A4RNG_EXPORT void A4rng_HI(A4RNG_HASH_T *e, BYTE *s, DWORD z);

Инициализация хеша,подмешиваем s - первоначальный ключ/вектор длиной z.

A4RNG_EXPORT void A4rng_HU(A4RNG_HASH_T *e, BYTE *s, DWORD z);

Обновление хеша, s-строка, z- длина строки.

A4RNG_EXPORT int  A4rng_HF(A4RNG_HASH_T *e, BYTE *s);

Закончили/финиш работу и получили результат в массив s. Длина массива должна быть не мешьше чем размер хеша A4RNG_HASH_SIZE. Возвращает тек. размер хеша.

A4RNG_EXPORT int  
A4rng_HFile  (char *f, BYTE *pwd, DWORD pwd_z, BYTE *outh);
A4RNG_EXPORT int  
A4rng_HS(BYTE *str, DWORD str_z, BYTE *pwd, DWORD pwd_z, BYTE *outh);

Сервисные функции: хеш файла и хеш строки.

10. Дополнительно Crypto-API

A4RNG_EXPORT BYTE A4rng_E(A4RNG_T *e, BYTE b);
A4RNG_EXPORT void A4rng_ES(A4RNG_T *e, BYTE *b, DWORD z);
A4RNG_EXPORT int  A4rng_EFile(char *from, char *to, BYTE *pwd, DWORD pwd_z);

Пример функционала: симметричное де/шифрование байта, строки и файла, т.к. используется XOR для шифрования, то повторное использование тех же значений ключа/e позволяет расшифровать. Пример в приложении.

11. Служебные для ключа

A4RNG_EXPORT int A4rng_VS(A4RNG_T *e, char *to);

Сохранить состояние ключа во внешнем файле.

A4RNG_EXPORT int A4rng_VL(A4RNG_T *e, char *from);

Восстановить состояние ключа из файла.

12. Утилиты

Bin24bmp - Конвертируем любой файл в bmp картинку размерностью 24 бита, цветную, для просмотра результата в графическом вьюере, самый простой визуальный тест на "крипторафическую" стойкость (не должно быть регулярных скоплений и т.п. регулярных форм), остальные тесты стойкости проверяем через diehard и др..известные статистические программы.

Testbit - формирует статистику использования битов. При правильной работе генератора, распределение должно быть максимально приближено к равномерному во всех таблицах.
БитКол-воОтносительные зн.
0 (1 бит)204806460.500016
1204793540.499984
0 (2 бита)51205640.250028
151186610.249935
251208570.250042
351199180.249996
0 (3-бита …)17072890.125046
117068760.125015
217054110.124908
317049170.124872
417069120.125018
517066490.124999
617088140.125157
717064650.124985

Testbitlen - проверяет максимальные последовательности одинаковых бит.
Длина в битах(повтор бита)Кол-во "0"относительноКол-во "1"Относительно
110239912030.1249991023977752 0.124997
25119946940.0624995119898070.062499
3 2560115960.0312512559826340.031248
4 1279908790.0156241280194290.015627
5640041120.007813640030150.007813
6320012530.003906320032600.003907
7 159938590.001952160007180.001953
8 79966760.00097680044000.000977
9 40002110.00048840006970.000488
10 19988390.00024419997610.000244
11 9986980.00012210009860.000122
125005230.0000615000120.000061
132506490.0000312501120.000031
141247170.0000151252500.000015
15626980.000008626170.000008
16309310.000004311800.000004
17156550.000002155410.000002
1877600.00000178570.000001
1939050.00000039050.000000
2020170.00000019580.000000
219740.0000009680.000000
224500.0000004820.000000
232550.0000002260.000000
241220.0000001270.000000
25840.000000640.000000
26310.000000410.000000
27130.000000100.000000
2890.00000070.000000
2950.00000030.000000
3020.00000010.000000
3100.00000020.000000
3310.00000000.000000

Diehard - классическая утилита построения данных для анализа.

Downloads

Source code, a4rng.zip (ZIP, 40 Kb)
Update, A4rng.20120703-2000.zip (ZIP, 78 Kb)
ZDLL for MiniM 32 bit (ZIP, 33 kB)
ZDLL for MiniM 64 bit (ZIP, 38 kB)

Александр Чудновский
azbuka@rbcmail.ru

To add module send text description and zip archive to mail: support@minimdb.com


Copyright (C) 2017 Eugene Karataev
Emails: Info Tech Support