CPC

Тема в разделе "Оффтоп", создана пользователем aidoqa, 5 ноя 2011.

  1. aidoqa
    Оффлайн

    aidoqa Активный пользователь

    Сообщения:
    1.115
    Симпатии:
    313
    Здравствуйте) кто может мне подсказать хорошие ресурсы где можно найти ответы данные вопросы?
    1.Генератор псевдослучайных чисел?
    2.Методы хэширования?
    3.Организация защиты данных в сетях?
     
  2. shestale
    Оффлайн

    shestale Ассоциация VN/VIP Преподаватель

    Сообщения:
    8.056
    Симпатии:
    4.488
    Последнее редактирование: 5 ноя 2011
  3. aidoqa
    Оффлайн

    aidoqa Активный пользователь

    Сообщения:
    1.115
    Симпатии:
    313
    впервую очередь в нем и смотрел) просто думал может кто раньше этим занимался по советывал бы)

    Добавлено через 1 час 20 минут 48 секунд
    где по искать материал?

    Добавлено через 33 минуты 22 секунды
    мне хотя бы третий пункт подскажите что искать именно надо?
     
  4. SNS-amigo
    Оффлайн

    SNS-amigo SNS System Watch Freelance reporter

    Сообщения:
    5.220
    Симпатии:
    8.894
    Последнее редактирование: 5 ноя 2011
    1 человеку нравится это.
  5. aidoqa
    Оффлайн

    aidoqa Активный пользователь

    Сообщения:
    1.115
    Симпатии:
    313
    мне для учебы) большое спасибо)))

    Добавлено через 28 минут 46 секунд
    кстати оцените работы
    Хеширование
    Ключи и хеш-функция
    Хеш-функции
    Другие методы хеширования
    Разрешение коллизий
    Класс HashTable
    Реализация класса HashTableIterator









































    Хеширование

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

    В идеале нам хотелось бы выбирать данные за время O(1). В этом случае число необходимых сравнений не зависит от количества элементов данных. Выборка элемента осуществляется за время O(1) при использовании в качестве индекса в массиве некоторого ключа. Например, блюда из меню в закусочной в целях упрощения бухгалтерского учета обозначаются номерами. Какой-нибудь деликатес типа «бастурма, маринованная в водке» в базе данных обозначается просто №2. Владельцу закусочной остается лишь сопоставить ключ 2 с записью в списке (рисунок 25).


    Рисунок 25.

    Мы знаем и другие примеры. Файл клиентов пункта проката видеокассет содержит семизначные номера телефонов. Номер телефона используется в качестве ключа для доступа к конкретной записи файла клиентов.


    Рисунок 26.

    Ключи не обязательно должны быть числовыми. Например, формируемая компилятором таблица символов (symbol table) содержит все используемые в программе идентификаторы вместе с сопутствующей каждому из них информацией. Ключом для доступа к конкретной записи является сам идентификатор.
    Ключи и хеш-функция

    В общем случае ключи не настолько просты, как в примере с закусочной. Несмотря на то, что они обеспечивают доступ к данным, ключи, как правило, не являются непосредственными индексами в массиве записей. Например, телефонный номер может идентифицировать клиента, но вряд ли пункт проката хранит десятимиллионный массив.

    В большинстве приложений ключ обеспечивает косвенную ссылку на данные. Ключ отображается во множество целых чисел посредством хеш-функции (hash function). Полученное в результате значение затем используется для доступа к данным. Давайте исследуем эту идею. Предположим, есть множество записей с целочисленными ключами. Хеш-функция HF отображает ключ в целочисленный индекс из диапазона 0...n-1. С хеш-функцией связана так называемая хеш-таблица (hash table), ячейки которой пронумерованы от 0 до n-1 и хранят сами данные или ссылки на данные.


    Рисунок 27.

    Предположим, Key – положительное целое, а HF(Key) – значение младшей цифры числа Key. Тогда диапазон индексов равен 0-9. Например, если Key = 49, HF(Key) = HF(49) = 9. Эта хеш-функция в качестве возвращаемого значение использует остаток от деления на 10.// Хеш-функция, возвращающая младшую цифру ключа
    int HF(int key)
    {
    return key % 10;
    }


    Часто отображение, осуществляемое хеш-функцией, является отображением «многие к одному» и приводит к коллизиям (collisions). Например, выше мы видим HF(49) = HF(29) = 9. При возникновении коллизии два или более ключа ассоциируются с одной и той же ячейкой хеш-таблицы. Поскольку два ключа не могут занимать одну и ту же ячейку в таблице, мы должны разработать стратегию разрешения коллизий.

    Схемы разрешения коллизий обсуждаются после знакомства с некоторыми типами хеш-функций.


    Рисунок 28.
    Хеш-функции

    Хеш-функция должна отображать ключ в целое число из диапазона 0...n-1. При этом количество коллизий должно быть ограниченным, а вычисление самой хеш-функции – очень быстрым. Некоторые методы удовлетворяют этим требованиям.

    Наиболее часто используется метод деления (division method), требующий двух шагов. Сперва ключ должен быть преобразован в целое число, а затем полученное значение вписывается в диапазон 0...n-1 с помощью оператора получения остатка. На практике метод деления используется в большинстве приложений, работающих с хешированием.

    Предположим, что ключ – пятизначное число. Хеш-функция извлекает две младшие цифры. Например, если это число равно 56389, то HF(56389) = 89. Две младшие цифры являются остатком от деления на 100.int HF(int key)
    {
    return key % 100; // метод деления на 100
    }


    Эффективность хеш-функции зависит от того, обеспечивает ли она равномерное распределение ключей в диапазоне 0...n-1. Если две последние цифры соответствуют году рождения, то будет слишком много коллизий при идентификации подростков, играющих в юношеской бейсбольной лиге.

    Другой пример – ключ-символьная строка С++. Хеш-функция отображает эту строку в целое число посредством суммирования первого и последнего символов и последующего вычисления остатка от деления на 101 (размер таблицы).// хеш-функция для символьной строки.
    // Возвращает значение в диапазоне от 0 до 100
    int HF(char *key)
    {
    int len = strlen(key), hashf = 0;

    // если длина ключа равна 0 или 1, возвратить key[0].
    // иначе сложить первый и последний символ
    if (len <= 1)
    hashf = key[0];
    else
    hashf = key[0] + key[len-1];

    return hashf % 101;
    }


    Эта хеш-функция приводит к коллизии при одинаковых первом и последнем символах строки. Например, строки «start» и «slant» будут отображаться в индекс 29. Так же ведет себя хеш-функция, суммирующая все символы строки.int HF(char *key)
    {
    int hashf = 0;

    // просуммировать все символы строки и разделить на 101
    while (*key)
    hashf += *key++;

    return hashf % 101;
    }


    Строки «bad» и «dab» преобразуются в один и тот же индекс. Лучшие результаты дает хеш-функция, производящая перемешивание битов в символах.

    В общем случае при больших n индексы имеют больший разброс. Кроме того, математическая теория утверждает, что распределение будет более равномерным, если n – простое число.
    Другие методы хеширования

    Метод середины квадрата (midsquare technique) предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа.// возвратить средние 10 бит произведения key*key
    int HF(int key);
    {
    key *= key; // возвести ключ в квадрат
    key >>= 11; // отбросить 11 младших бит
    return key % 1024 // возвратить 10 младших бит
    }


    При мультипликативном методе (multiplicative method) используется случайное действительное число f в диапазоне от 0<f<1. Дробная часть произведения f * key лежит в диапазоне от 0 до 1. Если это произведение умножить на n (размер хеш-таблицы), то целая часть полученного произведения даст значение хеш-функции в диапазоне 0...n-1.// хеш-функция, использующая мультипликативный метод;
    // возвращает значение в диапазоне 0...700
    int HF(int key);
    {
    static RandomNumber rnd;
    float f;

    // умножить ключ на случайное число из диапазона 0...1
    f = key * rnd.fRandom();
    // взять дробную часть
    f = f - int(f);
    // возвратить число в диапазоне 0...n-1
    return 701*f;
    }

    Разрешение коллизий

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

    Эта методика предполагает, что каждая ячейка таблицы помечена как незанятая. Поэтому при добавлении нового ключа всегда можно определить, занята ли данная ячейка таблицы или нет. Если да, алгоритм осуществляет перебор по кругу, пока не встретится «открытый адрес» (свободное место). Отсюда и название метода. Если размер таблицы велик относительно числа хранимых там ключей, метод работает хорошо, поскольку хеш-функция будет равномерно распределять ключи по всему диапазону и число коллизий будет минимальным. По мере того как коэффициент заполнения таблицы приближается к 1, эффективность процесса заметно падает.

    Проиллюстрируем линейный перебор на примере семи записей.

    Предположим, что данные имеют тип DataRecord и хранятся в 11-элементной таблице.struct DataRecord
    {
    int key;
    int data;
    };


    В качестве хеш-функции HF используется остаток от деления на 11, принимающий значения в диапазоне 0-10.HF(item) = item.key % 11


    В таблице хранятся следующие данные. Каждый элемент помечен числом проб, необходимых для его размещения в таблице.Список: {54,1}, {77,3}, {94,5}, {89,7}, {14,8}, {45,2}, {76,9}


    Хеширование первых пяти ключей дает пять различных индексов, по которым эти ключи запоминаются в таблице. Например, HF({54,1}) = 10, и этот элемент попадает в Table[10]. Первая коллизия возникает между ключами 89 и 45, так как оба они отображаются в индекс 1.

    Элемент данных {89,7} идет первым в списке и занимает позицию Table[1]. При попытке записать {45,2} оказывается, что место Table[1] уже занято. Тогда начинается последовательный перебор ячеек таблицы с целью нахождения свободного места. В данном случае это Table[2]. На ключе 76 эффективность алгоритма сильно падает. Этот ключ хешируется в индекс 10 – место, уже занятое. В процессе перебора осуществляется просмотр еще пяти ячеек, прежде чем будет найдено свободное место в Table[4]. Общее число проб для размещения в таблице всех элементов списка равно 13, т.е. в среднем 1,9 проб на элемент.
    Метод цепочек

    При другом подходе к хешированию таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Эта стратегия разрешения коллизий называется методом цепочек (chaining with separate lists).

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


    Рисунок 29.

    Проиллюстрируем метод цепочек на семи записях типа DataRecord и хеш-функции HF.Список: {54,1}, {77,3}, {94,5}, {89,7}, {14,8}, {45,2}, {76,9}
    HF(item) = item.key % 11


    Каждый новый элемент данных вставляется в хвост соответствующего связанного списка. На рисунке 30 каждое значение данных сопровождается (в скобках) числом проб, требуемых для запоминания этого значения в таблице.


    Рисунок 30.

    Заметьте, что если считать пробой вставку нового узла, то их общее число при вставке семи элементов равно 9, т.е. в среднем 1,3 пробы на элемент данных.

    В общем случае метод цепочек быстрее открытой адресации, так как просматривает только те ключи, которые попадают в один и тот же табличный адрес. Кроме того, открытая адресация предполагает наличие таблицы фиксированного размера, в то время как в методе цепочек элементы таблицы создаются динамически, а длина списка ограничена лишь количеством памяти. Основным недостатком метода цепочек являются дополнительные затраты памяти на поля указателей. В общем случае динамическая структура метода цепочек более предпочтительна для хеширования.
    Класс HashTable

    В этом разделе определяется общий класс HashTable, осуществляющий хеширование методом цепочек. Этот класс образуется от базового абстрактного класса List и обеспечивает механизм хранения с очень эффективными методами доступа. Допускаются данные любого типа с тем лишь ограничением, что для этого типа данных должен быть определен оператор «==». Чтобы сравнить ключевые поля двух элементов данных, прикладная программа должна перегрузить оператор «==».

    Мы также рассмотрим класс HashTableIterator, облегчающий обработку данных в хеш-таблице. Объект типа HashTableIterator находит важное применение при сортировке и доступе к данным.

    Но сначала приведем листинги классов Array и LinkedList, используемых в классе HashTable. Особо пояснять мы их не будем, поскольку их обсуждение не входит в задачи этой статьи.
    Класс Array

    Объявлениеenum ErrorType
    {invalidArraySize, memoryAllocationError, indexOutOfRange};

    char *errorMsg[] =
    {
    "Неверный размер массива", "Ошибка при выделении памяти",
    "Неверный индекс: "
    };

    template <class T>
    class Array
    {
    private:
    // Динамически занимаемый массив.
    T* alist;
    // Размер массива.
    int size;

    // Обработчик ошибок.
    void Error(ErrorType error,int badIndex=0) const;

    public:
    // Конструкторы и деструктор.
    Array(int sz = 50);
    Array(const Array<T>& A);
    ~Array(void);

    // Оператор присвоения
    Array<T>& operator= (const Array<T>& rhs);
    // Оператор индексации
    T& operator[](int i);
    // Оператор приведения к void
    operator T* (void) const;

    int ListSize(void) const; // считать размер
    void Resize(int sz); // изменить размер
    };


    Реализация // печатает сообщение, соответствующее ошибке
    template <class T>
    void Array<T>::Error(ErrorType error, int badIndex) const
    {
    cerr << errorMsg
    ;
    if (error == indexOutOfRange)
    cerr << badIndex;
    cerr << endl;
    exit(1);
    }

    // конструктор
    template <class T>
    Array<T>::Array(int sz)
    {
    // проверка правильности заданного размера
    if (sz <= 0)
    Error(invalidArraySize);
    // запоминаем размер и выделяем память под массив
    size = sz;
    alist = new T[size];
    // проверяем, что система выделила запрошенную память
    if (alist == NULL)
    Error(memoryAllocationError);
    }

    // деструктор
    template <class T>
    Array<T>::~Array(void)
    {
    delete [] alist;
    }

    // конструктор копирования
    template <class T>
    Array<T>::Array(const Array<T>& X)
    {
    // присвоить размер объекта X текущему объекту
    int n = X.size;

    size = n;

    // выделить память под массив и проверить, что она выделена
    alist = new T[n]; // allocate dynamic array
    if (alist == NULL)
    Error(memoryAllocationError);

    // скопировать элементы массива из Х
    T* srcptr = X.alist; // начальный адрес X.alist
    T* destptr = alist; // начальный адрес alist
    // копируем элементы массива
    while (n--)
    *destptr++ = *srcptr++;
    }

    // оператор присвоения. Присвоить rhs текущему объекту
    template <class T>
    Array<T>& Array<T>::operator= (const Array<T>& rhs)
    {
    // запоминаем размер rhs
    int n = rhs.size;

    // если размеры не совпадают, перезанимаем память
    if (size != n)
    {
    delete [] alist; // освобождаем ранее занятую память
    alist = new T[n]; // занимаем память под новый массив
    if (alist == NULL)
    Error(memoryAllocationError);
    size = n;
    }

    // Копируем элементы массива из rhs в текущий объект
    T* destptr = alist;
    T* srcptr = rhs.alist;
    while (n--)
    *destptr++ = *srcptr++;

    // возвращаем ссылку на текущий объект
    return *this;
    }

    // оператор индексирования
    template <class T>
    T& Array<T>::operator[] (int n)
    {
    // проверяем границы массива
    if (n < 0 || n > size-1)
    Error(indexOutOfRange,n);
    // возвращаем ссылку на запрошенный элемент массива
    return alist[n];
    }

    // оператор приведения указателя
    template <class T>
    Array<T>::operator T* (void) const
    {
    // возвращаем значение скрытого поля alist
    return alist;
    }

    template <class T>
    int Array<T>::ListSize(void) const
    {
    return size;
    }

    // оператор изменения размеров массива
    template <class T>
    void Array<T>::Resize(int sz)
    {
    // Проверяем заданный размер
    if (sz <= 0)
    Error(invalidArraySize);
    // ничего не делать, если размер не изменился
    if (sz == size)
    return;
    // занимаем память
    T* newlist = new T[sz];
    if (newlist == NULL)
    Error(memoryAllocationError);

    // Рассчитываем количество элементов,
    // копируемых из старого массива в новый.
    // Запоминаем в n значение sz (обрезаем массив), если sz <= size
    // иначе запоминаем size
    int n = (sz <= size) ? sz : size;

    // копируем n элементов из старого массива в новый
    T* srcptr = alist; // начальный адрес старого массива
    T* destptr = newlist; // начальный адрес нового массива
    // Копируем элементы массива.
    while (n--)
    *destptr++ = *srcptr++;

    // Уничтожаем старый массив.
    delete[] alist;

    // Изменяем значение alist так, чтобы оно указывало на новый массив
    alist = newlist;
    // Запоминаем новый размер массива.
    size = sz;
    }

    Класс LinkedList

    Класс LinkedList использует класс Node для хранения элементов списка.template <class T>
    class Node
    {
    private:
    Node<T> *next; // указатель на следующий элемент

    public:
    T data;

    // конструктор
    Node (const T& item, Node<T>* ptrnext = NULL);

    // Методы модификации списка
    void InsertAfter(Node<T> *p);
    Node<T> *DeleteAfter(void);

    // возвращает адрес следующего элемента
    Node<T> *NextNode(void) const;
    };

    // Конструктор. Инициализирует data и next.
    template <class T>
    Node<T>::Node(const T& item, Node<T>* ptrnext) : data(item), next(ptrnext) {}

    // Возвращает значение next
    template <class T>
    Node<T> *Node<T>::NextNode(void) const
    {
    return next;
    }

    // Вставит ветку после текущей
    // p - элемент, подключаемый к текущему элементу
    template <class T>
    void Node<T>::InsertAfter(Node<T> *p)
    {
    p->next = next;
    next = p;
    }

    // Отсоединяет элемент, подключенный к текущему и возвращает
    // адрес отключенного элемента.
    template <class T>
    Node<T> *Node<T>::DeleteAfter(void)
    {
    Node<T> *tempPtr = next; // запоминаем отключаемый элемент

    // Если подключенного элемента нет, возвращаем NULL.
    if (next == NULL)
    return NULL;

    // Восстанавливает целостность цепочки.
    next = tempPtr->next;

    // возвращаем указатель на отключенный элемент.
    return tempPtr;
    }


    Объявление// Предобъявление класса SeqListIterator
    template <class T>
    class SeqListIterator;

    template <class T>
    class LinkedList
    {
    private:
    // указатели для доступа к началу и концу списка
    Node<T> *front, *rear;

    // используются для получения, вставки и удаления данных
    Node<T> *prevPtr, *currPtr;

    // число элементов списка
    int size;

    // позиция в списке. Используется методом Reset
    int position;
    // скрытые методы создания и уничтожения элементов
    Node<T> *GetNode(const T& item,Node<T> *ptrNext=NULL);
    void FreeNode(Node<T> *p);

    // копирует список L в текущий список
    void CopyList(const LinkedList<T>& L);

    public:
    // конструкторы
    LinkedList(void);
    LinkedList(const LinkedList<T>& L);

    // деструктор
    ~LinkedList(void);

    // оператор присвоения
    LinkedList<T>& operator= (const LinkedList<T>& L);

    // методы проверки состояния списка
    int ListSize(void) const;
    int ListEmpty(void) const;

    // Методы прохождения
    void Reset(int pos = 0);
    void Next(void);
    int EndOfList(void) const;
    int CurrentPosition(void) const;

    // Методы вставки
    void InsertFront(const T& item);
    void InsertRear(const T& item);
    void InsertAt(const T& item);
    void InsertAfter(const T& item);

    // Методы удаления
    T DeleteFront(void);
    void DeleteAt(void);

    // Получение/изменение данных
    T& Data(void);

    // Метод очистки списка
    void ClearList(void);

    // Класс SeqListIterator нуждается в доступе к этому классу
    friend class SeqListIterator<T>;
    };


    Реализацияtemplate <class T>
    Node<T> *LinkedList<T>::GetNode(const T& item, Node<T>* ptrNext)
    {
    Node<T> *p;

    p = new Node<T>(item,ptrNext);
    if (p == NULL)
    {
    cout << "Ошибка при выделении памяти!\n";
    exit(1);
    }
    return p;
    }

    template <class T>
    void LinkedList<T>::FreeNode(Node<T> *p)
    {
    delete p;
    }

    // копируем L в текущий список, который считаем пустым
    template <class T>
    void LinkedList<T>::CopyList(const LinkedList<T>& L)
    {
    // Используем p для пробегания по списку L
    Node<T> *p = L.front;
    int pos;

    // Перебираем элементы в списке L и вставляем каждый элемент
    // в конец текущего списка.
    while (p != NULL)
    {
    InsertRear(p->data);
    p = p->NextNode();
    }

    // Если список пуст, заканчиваем работу.
    if (position == -1)
    return;

    // Перезагрузка prevPtr и currPtr в новом списке
    prevPtr = NULL;
    currPtr = front;
    for (pos = 0; pos != position; pos++)
    {
    prevPtr = currPtr;
    currPtr = currPtr->NextNode();
    }
    }

    // Создает новый список. Устанавливает указатели в NULL, размер в 0,
    // и позицию в списке -1
    template <class T>
    LinkedList<T>::LinkedList(void): front(NULL), rear(NULL),
    prevPtr(NULL),currPtr(NULL), size(0), position(-1)
    {}

    template <class T>
    LinkedList<T>::LinkedList(const LinkedList<T>& L)
    {
    front = rear = NULL;
    prevPtr = currPtr = NULL;
    size = 0;
    position = -1;
    CopyList(L);
    }

    template <class T>
    void LinkedList<T>::ClearList(void)
    {
    Node<T> *currPosition, *nextPosition;

    currPosition = front;
    while(currPosition != NULL)
    {
    // Получаем адрес следующего элемента и удаляем текущий.
    nextPosition = currPosition->NextNode();
    FreeNode(currPosition);
    currPosition = nextPosition; // Переходим к следующему элементу.
    }
    front = rear = NULL;
    prevPtr = currPtr = NULL;
    size = 0;
    position = -1;
    }

    template <class T>
    LinkedList<T>::~LinkedList(void)
    {
    ClearList();
    }

    template <class T>
    LinkedList<T>& LinkedList<T>::operator=
    (const LinkedList<T>& L)
    {
    if (this == &L) // Нельзя копировать себя в себя же.
    return *this;

    ClearList();
    CopyList(L);
    return *this;
    }

    template <class T>
    int LinkedList<T>::ListSize(void) const
    {
    return size;
    }

    template <class T>
    int LinkedList<T>::ListEmpty(void) const
    {
    return size == 0;
    }

    // Передвигает prevPtr и currPtr вперед на одну позицию
    template <class T>
    void LinkedList<T>::Next(void)
    {
    // если перебирать нечего, заканчиваем
    if (currPtr != NULL)
    {
    // Передвигаем указатели вперед на одну позицию.
    prevPtr = currPtr;
    currPtr = currPtr->NextNode();
    position++;
    }
    }

    // Возвращает TRUE если достигнут конец списка.
    template <class T>
    int LinkedList<T>::EndOfList(void) const
    {
    return currPtr == NULL;
    }

    // Возвращает позицию текущего элемента
    template <class T>
    int LinkedList<T>::CurrentPosition(void) const
    {
    return position;
    }

    // Сбросить текущую позицию в pos
    template <class T>
    void LinkedList<T>::Reset(int pos)
    {
    int startPos;

    // Если список пуст, заканчиваем
    if (front == NULL)
    return;

    // В случае неверной позиции завершаем выполнение.
    if (pos < 0 || pos > size-1)
    {
    cerr << "Reset: Неверная позиция: " << pos
    << endl;
    return;
    }

    if(pos == 0)
    {
    // Сбрасываем механизм прохождения в начальное положение
    prevPtr = NULL;
    currPtr = front;
    position = 0;
    }
    else
    {
    // Устанавливаем механизм прохождения в pos.

    currPtr = front->NextNode();
    prevPtr = front;
    startPos = 1;
    // Пробегаем по списку до достижения pos
    for(position=startPos; position != pos; position++)
    {
    prevPtr = currPtr;
    currPtr = currPtr->NextNode();
    }
    }
    }

    // Возвращаем ссылку на элемент данных.
    template <class T>
    T& LinkedList<T>::Data(void)
    {
    // Ошибка если список пуст или прохождение завершено.
    if (size == 0 || currPtr == NULL)
    {
    cerr << "Data: неверная ссылка!" << endl;
    exit(1);
    }
    return currPtr->data;
    }

    // Вставить элемент в начало списка.
    template <class T>
    void LinkedList<T>::InsertFront(const T& item)
    {
    // Вызвать Reset если список не пуст.
    if (front != NULL)
    Reset();
    InsertAt(item);
    }

    // Вставить элемент в конец списка.
    template <class T>
    void LinkedList<T>::InsertRear(const T& item)
    {
    Node<T> *newNode;

    prevPtr = rear;
    newNode = GetNode(item); // создать новый элемент
    if (rear == NULL) // Если список пуст, вставить в начало
    front = rear = newNode;
    else
    {
    rear->InsertAfter(newNode);
    rear = newNode;
    }
    currPtr = rear;
    position = size;
    size++;
    }

    // Вставить элемент в текущую позицию в списке.
    template <class T>
    void LinkedList<T>::InsertAt(const T& item)
    {
    Node<T> *newNode;

    // Два случая: вставка в начало или в середину списка.
    if (prevPtr == NULL)
    {
    // Вставка элемента в начало списка. Также позволяет
    // поместить элемент в пустой список.
    newNode = GetNode(item,front);
    front = newNode;
    }
    else
    {
    // Вставка элемента внутрь списка. Помещает элемент после prevPtr
    newNode = GetNode(item);
    prevPtr->InsertAfter(newNode);
    }

    // Если prevPtr == rear, мы вставляем в пустой список
    // или в конец непустого списка; обновить rear и position
    if (prevPtr == rear)
    {
    rear = newNode;
    position = size;
    }

    // Обновить currPtr
    currPtr = newNode;
    size++; // увеличиваем размер списка
    }

    // Вставляет элемент за текущей позицией.
    template <class T>
    void LinkedList<T>::InsertAfter(const T& item)
    {
    Node<T> *p;

    p = GetNode(item);
    if (front == NULL) // вставляем в пустой список
    {
    front = currPtr = rear = p;
    position = 0;
    }
    else
    {
    // Вставляем в конец списка.
    if (currPtr == NULL)
    currPtr = prevPtr;
    currPtr->InsertAfter(p);
    if (currPtr == rear)
    {
    rear = p;
    position = size;
    }
    else
    position++;
    prevPtr = currPtr;
    currPtr = p;
    }
    size++; // увеличиваем размер списка
    }

    // Удаляет первый элемент списка.
    template <class T>
    T LinkedList<T>::DeleteFront(void)
    {
    T item;

    Reset();
    if (front == NULL)
    {
    cerr << "Ошибка - удаление в пустом списке!" << endl;
    exit(1);
    }
    item = currPtr->data;
    DeleteAt();
    return item;
    }

    // Удаляет текущий элемент
    template <class T>
    void LinkedList<T>::DeleteAt(void)
    {
    Node<T> *p;

    // Ошибка если список пуст или прохождение завершено.
    if (currPtr == NULL)
    {
    cerr << "Ошибка удаления - отсутствует текущий элемент!" << endl;
    exit(1);
    }

    // Если удаление производится в начале или внутри списка
    if (prevPtr == NULL)
    {
    // Сохраняем указатель на первый элемент и отключаем его. Если это
    // последний элемент, front становится равным NULL
    p = front;
    front = front->NextNode();
    }
    else
    p = prevPtr->DeleteAfter();

    // если удален последний элемент, новым последним элементом становится
    // prevPtr и позиция уменьшается на 1; иначе, позиция остается той же.
    // Если p - последний элемент, rear = NULL и position = -1
    if (p == rear)
    {
    rear = prevPtr;
    position--;
    }

    // Переключить currPtr на следующий за удаляемым элемент. Если p - последний
    // элемент в списке, currPtr принимает значение NULL.
    currPtr = p->NextNode();

    // Освободить память, занимаемую элементом, и уменьшить размер списка.
    FreeNode(p);
    size--;
    }

    Класс List

    Объявлениеtemplate <class T>
    class List
    {
    protected:
    // Число элементов списка. Изменяется производными классами.
    int size;
    public:
    // Конструктор
    List(void);

    // Делаем деструктор виртуальным, чтобы производные классы
    // могли использовать динамически занимаемую память.
    virtual ~List(void);

    // Методы доступа к списку
    virtual int ListSize(void) const;
    virtual int ListEmpty(void) const;
    virtual int Find (T& item) = 0;

    // Методы изменения списка
    virtual void Insert(const T& item) = 0;
    virtual void Delete(const T& item) = 0;
    virtual void ClearList(void) = 0;
    };

    // Конструктор устанавливает размер в 0
    template <class T>
    List<T>::List(void): size(0)
    {}

    // Виртуальный деструктор ничего не делает
    template <class T>
    List<T>::~List(void)
    {}

    // Возвращает размер списка
    template <class T>
    int List<T>::ListSize(void) const
    {
    return size;
    }

    // Проверка на отсутствие элементов
    template <class T>
    int List<T>::ListEmpty(void) const
    {
    return size == 0;
    }

    Спецификация класса HashTable

    Объявление#include "array.h"
    #include "list.h"
    #include "link.h"
    #include "iterator.h"

    template <class T>
    class HashTableIterator;

    template <class T>
    class HashTable: public List<T>
    {
    protected:
    // число блоков; представляет размер таблицы
    int numBuckets;

    // хеш-таблица есть массив связанных списков
    Array< LinkedList<T> > buckets;

    // хеш-функция
    unsigned long (*hf)(T key);
    // адрес элемента данных, к которому обращались последний раз
    T *current;

    public:
    // конструктор с параметрами, включающими
    // размер таблицы и хеш-функцию
    HashTable(int nbuckets, unsigned long hashf(T key));

    // методы обработки списков
    virtual void Insert(const T& key);
    virtual int Find(T& key);
    virtual void Delete(const T& key);
    virtual void ClearList(void);
    void Update(const T& key);

    // дружественный итератор, имеющий доступ к
    // данным-членам
    friend class HashTableIterator<T>
    }


    Описание

    Объект типа HashTable есть список элементов типа T. В нем реализованы все методы, которые требует абстрактный базовый класс List. Прикладная программа должна задать размер таблицы и хеш-функцию, преобразующую элемент типа T в длинное целое без знака. Описание параметра функции с помощью типа, заданного в шаблоне, позволяет использовать данный класс для хеширования данных любого типа.

    Методы Insert, Find, Delete и ClearList являются базовыми методами обработки списков. Отдельный метод Update служит для обновления элемента, уже имеющегося в таблице.

    Методы ListSize и ListEmpty реализованы в базовом классе. Элемент данных current всегда указывает на последнее доступное значение данных. Он используется методом Update и производными классами, которые должны возвращать ссылки.

    Пример

    Предположим, что NameRecord есть запись, содержащая поле наименования и поле счетчика.struct NameRecord
    {
    String name;
    int count;
    };

    // 101-элементная таблица, содержащая данные типа NameRecord
    // и имеющая хеш-функцию hash
    HashTable<NameRecord> HF(101,hash);
    // вставить запись {"Betsy",1} в таблицу
    NameRecord rec;
    rec.name = "Betsy";
    rec.count = 1;
    HF.Insert(rec);
    cout << HF.ListSize(); // распечатать размер таблицы

    // Найти значение данных, соответствующее ключу "Betsy",
    // увеличить поле счетчика на 1 и обновить запись.
    rec.name = "Betsy";
    if (HF.Find(rec) // найти "Betsy"
    {
    rec.cout += 1; // обновить поле данных
    HF.Update(rec); // обновить запись в таблице
    }
    else
    cerr << "Ошибка: \"Ключ Betsy должен быть в таблице.\"\n;


    Класс HashTableIterator образован из абстрактного класса Iterator и содержит методы для просмотра данных в таблице.
    Спецификация класса HashTableIterator

    Объявлениеtemplate <class T>
    class HashTableIterator: public Iterator<T>
    {
    private:
    // указатель таблицы, подлежащей обходу
    HashTable<T> *HashTable;

    // индекс текущего просматриваемого блока и указатель на связанный список
    int currentBucket;
    LinkedList<T> *currBucketPtr;

    // рабочая функция для реализации метода Next
    void SearchNextNode(int cb);

    public:
    // конструктор
    HashTableIterator (HashTable<T>& ht);

    // базовые методы итератора
    virtual void Next(void);
    virtual void Reset(void);
    virtual T& Data(void);

    // подключение к итератору другой хэш-таблицы
    void SetList(HashTable<T>& lst);
    };


    Описание

    Метод Next выполняет обход таблицы список (блок) за списком, проходя узлы каждого списка. Значения данных, выдаваемые итератором, никак не упорядочены. Для обнаружения очередного списка, подлежащего обходу, метод Next использует функцию SearchNextNode.

    Пример// объявить итератор для объекта HF типа HashTable
    HashTableIterator<NameRecord> hiter(HF);

    // сканировать все элементы базы данных
    for (hiter.Reset(); !hiter.EndOfList; hiter.Next())
    {
    rec = hiter.Data();
    cout << rec.name << ": " << rec.count << endl;
    }

    Реализация класса HashTable

    Данный класс образован от абстрактного класса List, предоставляющего методы ListSize и ListEmpty. Мы обсудим элементы данных класса HashTable и операции, реализующие виртуальные функции Insert, Find, Delete и ClearList. Ключевым элементом класса является объект buckets типа Array, который определяет массив связанных списков, образующих хеш-таблицу. В поле hf помещается указатель на хеш-функцию, а numBuckets является размером таблицы. Указатель current идентифицирует последний элемент данных, к которому осуществлялся доступ тем или иным методом класса. Его значение задается методами Find и Insert и используется методом Update для обновления данных в таблице.
    Методы обработки списков

    Метод Insert вычисляет значение хеш-функции и ищет объект типа LinkedList, чтобы проверить, есть ли уже такой элемент данных в таблице или нет. Если есть, то Insert обновляет этот элемент данных, устанавливает на него указатель current и возвращает управление. Если такого элемента в таблице нет, Insert добавляет его в хвост списка, устанавливает на него указатель current и увеличивает размер списка.template <class T>
    void HashTable<T>::Insert(const T& key)
    {
    // hashval - индекс блока (связанного списка)
    int hashval = int(hf(key) % numBuckets);

    // lst -- псевдоним для buckets[hashval]. Помогает обойтись без индексов
    LinkedList<T>& lst = buckets[hashval];

    for (lst.Reset(); !lst.EndOfList(); lst.Next())
    // если ключ найден, обновить данные и выйти
    if (lst.Data() == key)
    {
    lst.Data() = key;
    current = &lst.Data();
    return;
    }
    // данные, соответствующие этому ключу, не найдены.
    // вставить элемент в список
    lst.InsertRear(key);
    current = &lst.Data();
    size++;
    }


    Метод Find применяет хеш-функцию и просматривает указанный в результате список на предмет совпадения с входным параметром. Если совпадение обнаружено, метод копирует данные в key, устанавливает указатель current на соответствующий узел и возвращает True. В противном случае метод возвращает False.template <class T>
    int HashTable<T>::Find(T& key)
    {
    // вычислить значение хеш-функции и установить lst
    // на начало соответствующего связанного списка
    int hashval = int(hf(key) % NumBuckets);
    LinkedList<T>& lst = buckets[hashval];

    // просмотреть узлы связанного списка в поисках key
    for (lst.Reset(); !lst.EndOfList(); lst.Next())
    if (lst.Data() == key)
    {
    // если ключ совпал, получить данные, установить current и выйти
    key = lst.Data();
    current = &lst.Data();
    return 1; // вернуть TRUE
    }
    return 0; // иначе вернуть FALSE
    }


    Метод Delete просматривает указанный список и удаляет узел, если совпадение произошло.
    Реализация класса HashTableIterator

    Этот класс должен просматривать данные, разбросанные по хеш-таблице. Поэтому он более интересен и более сложен с точки зрения реализации, чем класс HashTable. Обход элементов таблицы начинается с поиска непустого блока в массиве списков. Обнаружив непустой блок, мы просматриваем все узлы этого списка, а затем продолжаем процесс, взяв другой непустой блок. Итератор заканчивает обход, когда просмотрен последний непустой блок. Итератор должен быть привязан к списку. В данном случае переменной hashTable присваивается адрес конкретного экземпляра класса HashTable. Поскольку класс HashTableIterator является дружественным по отношению к HashTable, он имеет доступ ко всем скрытым данным-членам последнего, включая массив buckets и его размер numBuckets.

    Переменная currentBucket является индексом связанного списка, который просматривается в данный момент, а currBucketPtr – указателем этого списка. Обход каждого блока осуществляется итератором, встроенным в класс LinkedList. На рисунке 31 показано, как итератор обходит таблицу с четырьмя элементами.


    Рисунок 31.

    Метод SearchNextNode вызывается для обнаружения очередного списка, подлежащего обходу. Просматриваются все блоки, начиная с cb, пока не встретится непустой список. Переменной currentBucket присваивается индекс этого списка, а переменной currBucketPtr – его адрес. Если непустых списков нет, происходит возврат с currentBucket = -1.// начиная с cb, искать следующий непустой список для просмотра
    template <class t>
    void HashTableIterator<T>::SearchNextNode(int cb)
    {
    currentBucket = -1;

    // если индекс cb больше размера таблицы, прекратить поиск
    if (cb > hashTable->numBuckets)
    return;

    // иначе искать, начиная с текущего списка до конца таблицы,
    // непустой блок и обновить скрытые элементы данных
    for (int i=cb; i<hashTable->numBuckets; i++)
    if (!hashTable->buckets.ListEmpty())
    {
    // перед тем как вернуться, установить currentBucket равным i
    // и в currBucketPtr поместить адрес нового непустого списка
    currBucketPtr = &hashTable->buckets;
    currBucketPtr ->Reset();
    currentBucket = i;
    return;
    }
    }


    Конструктор инициализирует базовый класс Iterator и присваивает скрытому указателю hashTable адрес хэш-таблицы. Непустой список обнаруживается с помощью вызова SearchNextNode с нулевым параметром.// конструктор. инициализирует базовый класс и класс HashTable
    // SearchNextNode идентифицирует первый непустой блок в таблице
    template <class T>
    HashTableIterator<T>::HashTableIterator(HashTable<T>& hf):
    Iterator<T>(hf), HashTable(&hf)
    {
    SearchNextNode(0);
    }


    С помощью метода Next осуществляется продвижение вперед по текущему списку на один элемент. По достижении конца списка функция SearchNextNode настраивает итератор на следующий непустой блок.// перейти к следующему элементу данных в таблице
    template <class T>
    void HashTableIterator<T>::Next(void)
    {
    // продвинуться к следующему узлу текущего списка
    currBucketPtr->Next();

    // по достижении конца списка вызвать SearchNextNode
    // для поиска следующего непустого блока в таблице
    if (currBucketPtr->EndOfList())
    SearchNextNode(++currentBucket);

    // установить флаг iterationComplete, если непустых списков
    // больше нет
    iterationComplete = currentBucket == -1;
    }
    http://www.rsdn.ru/article/alg/bintree/hash.xml

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

    Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).

    Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL (англ.): «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».Содержание [убрать]
    1 Источники случайных чисел
    2 Детерминированные ГПСЧ
    3 ГПСЧ с источником энтропии или ГСЧ
    3.1 Пример простейшего ГСЧ с источником энтропии
    3.2 Примеры ГСЧ и источников энтропии
    4 ГПСЧ в криптографии
    4.1 Примеры криптостойких ГПСЧ
    4.1.1 Циклическое шифрование
    4.1.2 ANSI X9.17
    5 Аппаратные ГПСЧ
    6 См. также
    7 Примечания
    8 Литература
    9 Ссылки

    [править]
    Источники случайных чисел

    Источники настоящих случайных чисел найти трудно. Физические шумы, такие как детекторы событий ионизирующей радиации, дробовой шум в резисторе или космическое излучение могут быть такими источниками. Однако применяются такие устройства в приложениях сетевой безопасности редко. Сложности также вызывают грубые атаки на подобные устройства. Альтернативным решением является создание некоторого набора из большого количества случайных чисел и опубликование его в некотором словаре. Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Хотя данные наборы действительно обеспечивают статистическую случайность, они не достаточно случайны, так как противник может получить копию словаря.

    Криптографические приложения используют для генерации случайных чисел особенные алгоритмы. Эти алгоритмы заранее определены и, следовательно, генерируют последовательность чисел, которая теоретически не может быть статистически случайной. В то же время, если выбрать хороший алгоритм, полученная численная последовательность будет проходить большинство тестов на случайность. Такие числа называют псевдослучайными числами.
    [править]
    Детерминированные ГПСЧ

    Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений».

    Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается — начинает повторять одну и ту же последовательность чисел. Длина циклов ГПСЧ зависит от самого генератора и составляет около 2n/2, где n — размер внутреннего состояния в битах, хотя линейные конгруэнтные и LFSR-генераторы обладают максимальными циклами порядка 2n. Если порождаемая ГПСЧ последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений.

    Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:
    Слишком короткий период/периоды.
    Последовательные значения не являются независимыми.
    Некоторые биты «менее случайны», чем другие.
    Неравномерное одномерное распределение.
    Обратимость.

    В частности, алгоритм RANDU, десятилетиями использовавшийся на мейнфреймах, оказался очень плохим[1][2], что вызвало сомнения в достоверности результатов многих исследований, использовавших этот алгоритм.

    Наиболее распространены линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, регистр сдвига с линейной обратной связью, Generalized feedback shift register.

    Из современных ГПСЧ широкое распространение также получил «вихрь Мерсенна», предложенный в 1997 году Мацумото и Нисимурой. Его достоинствами являются колоссальный период (219937−1), равномерное распределение в 623 измерениях (линейный конгруэнтный метод даёт более или менее равномерное распределение максимум в 5 измерениях), быстрая генерация случайных чисел (в 2-3 раза быстрее, чем стандартные ГПСЧ, использующие линейный конгруэнтный метод). Однако, существуют алгоритмы, распознающие последовательность, порождаемую вихрем Мерсенна, как неслучайную.
    [править]
    ГПСЧ с источником энтропии или ГСЧ

    Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать совершенно непредсказуемые или попросту абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG). Так как такие генераторы чаще всего применяются для генерации уникальных симметричных и асимметричных ключей для шифрования, они чаще всего строятся из комбинации криптостойкого ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ).

    Почти все крупные производители микрочипов поставляют аппаратные ГСЧ с различными источниками энтропии, используя различные методы для их очистки от неизбежной предсказуемости. Однако на данный момент скорость сбора случайных чисел всеми существующими микрочипами (несколько тысяч бит в секунду) не соответствует быстродействию современных процессоров.

    В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии являлся наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах), которые таким образом остаются уязвимыми. Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т. п.), как, например, в PGP и Yarrow[3], или взаимодействия между потоками, как, например, в Java secure random.
    [править]
    Пример простейшего ГСЧ с источником энтропии

    Если в качестве источника энтропии использовать текущее время, то для получения натурального числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N+1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.





















    Примеры ГСЧ и источников энтропии
    Источник энтропии ГПСЧ Достоинства Недостатки
    /dev/random в UNIX/Linux Счётчик тактов процессора, однако собирается только во время аппаратных прерываний LFSR, с хешированием выхода через SHA-1 Есть во всех Unix, надёжный источник энтропии Очень долго «нагревается», может надолго «застревать», либо работает как ГПСЧ (/dev/urandom)
    Yarrow от Брюса Шнайера[3] Традиционные методы AES-256 и SHA-1 маленького внутреннего состояния Гибкий криптостойкий дизайн Медленный
    Microsoft CryptoAPI Текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера MD5-хеш внутреннего состояния размером в 128 бит Встроен в Windows, не «застревает» Сильно зависит от используемого криптопровайдера (CSP).
    Java SecureRandom Взаимодействие между потоками SHA-1-хеш внутреннего состояния (1024 бит) Большое внутреннее состояние Медленный сбор энтропии
    Chaos от Ruptor[4] Счётчик тактов процессора, собирается непрерывно Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора Пока самый быстрый из всех, большое внутреннее состояние, не «застревает» Оригинальная разработка, свойства приведены только по утверждению автора
    RRAND от Ruptor[5] Счётчик тактов процессора Зашифровывание внутреннего состояния поточным шифром EnRUPT в authenticated encryption режиме (aeRUPT) Очень быстр, внутреннее состояние произвольного размера по выбору, не «застревает» Оригинальная разработка, свойства приведены только по утверждению автора. Шифр EnRUPT не является криптостойким.
    ГПСЧ в криптографии
    Основная статья: Криптографически стойкий генератор псевдослучайных чисел

    Разновидностью ГПСЧ являются ГПСБ (PRBG) — генераторы псевдо-случайных бит, а также различных поточных шифров. ГПСЧ, как и поточные шифры, состоят из внутреннего состояния (обычно размером от 16 бит до нескольких мегабайт), функции инициализации внутреннего состояния ключом или зерном (англ. seed), функции обновления внутреннего состояния и функции вывода. ГПСЧ подразделяются на простые арифметические, сломанные криптографические и криптостойкие. Их общее предназначение — генерация последовательностей чисел, которые невозможно отличить от случайных вычислительными методами.

    Хотя многие криптостойкие ГПСЧ или поточные шифры предлагают гораздо более «случайные» числа, такие генераторы гораздо медленнее обычных арифметических и могут быть непригодны во всякого рода исследованиях, требующих, чтобы процессор был свободен для более полезных вычислений.

    В военных целях и в полевых условиях применяются только засекреченные синхронные криптостойкие ГПСЧ (поточные шифры), блочные шифры не используются. Примерами известных криптостойких ГПСЧ являются RC4, ISAAC, SEAL, Snow, совсем медленный теоретический алгоритм Блюма, Блюма и Шуба, а также счётчики с криптографическими хеш-функциями или криптостойкими блочными шифрами вместо функции вывода.
    [править]
    Примеры криптостойких ГПСЧ
    [править]
    Циклическое шифрование

    В данном случае используется способ генерации ключа сессии из мастер-ключа. Счетчик с периодом N используется в качестве входа в шифрующее устройство. Например, в случае использования 56-битного ключа DES может использоваться счетчик с периодом 256. После каждого созданного ключа значение счетчика повышается на 1. Таким образом, псевдослучайная последовательность, полученная по данной схеме, имеет полный период: каждое выходное значение Х0, Х1,…XN-1 основано на разных значениях счетчика, поэтому Х0 ≠ X1 ≠ XN-1. Так как мастер-ключ является секретным, легко показать, что любой секретный ключ не зависит от знания одного или более предыдущих секретных ключей.
    [править]
    ANSI X9.17

    ГПСЧ из стандарта ANSI X9.17 используется во многих приложениях финансовой безопасности и PGP. В основе этого ГПСЧ лежит тройной DES. Генератор ANSI X9.17 состоит из следующих частей:
    Вход: генератором управляют два псевдослучайных входа. Один является 64-битным представлением текущих даты и времени, которые меняются каждый раз при создании числа. Другой является 64-битным исходным значением. Оно инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел.
    Ключи: генератор использует три модуля тройного DES. Все три используют одну и ту же пару 56-битных ключей, которая держится в секрете и применяется только при генерации псевдослучайного числа.
    Выход: выход состоит из 64-битного псевдослучайного числа и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа.
    DTi — значение даты и времени на начало i-ой стадии генерации.
    Vi — начальное значение для i-ой стадии генерации.
    Ri — псевдослучайное число, созданное на i-ой стадии генерации.
    K1, K2 — ключи, используемые на каждой стадии.

    Тогда:
    Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] Vi ]
    Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

    Схема включает использование 112-битного ключа и трех EDE-шифрований. На вход даются два псевдослучайных значения: значение даты и времени и начальное значение текущей итерации, на выходе получаются начальное значение для следующей итерации и очередное псевдослучайное значение. Даже если псевдослучайное число Ri будет скомпрометировано, вычислить Vi+1 из Ri не является возможным за разумное время, и, следовательно, следующее псевдослучайное значение Ri+1, так как для получения Vi+1 дополнительно выполняются три операции EDE.
    [править]
    Аппаратные ГПСЧ
    Основная статья: Аппаратный генератор случайных чисел

    Кроме устаревших, хорошо известных LFSR-генераторов, широко применявшихся в качестве аппаратных ГПСЧ в XX веке, к сожалению, очень мало известно о современных аппаратных ГПСЧ (поточных шифрах), так как большинство из них разработано для военных целей и держатся в секрете. Почти все существующие коммерческие аппаратные ГПСЧ запатентованы и также держатся в секрете. Аппаратные ГПСЧ ограничены строгими требованиями к расходуемой памяти (чаще всего использование памяти запрещено), быстродействию (1-2 такта) и площади (несколько сотен FPGA- или ASIC-ячеек). Из-за таких строгих требований к аппаратным ГПСЧ очень трудно создать криптостойкий генератор, поэтому до сих пор все известные аппаратные ГПСЧ были взломаны. Примерами таких генераторов являются Toyocrypt и LILI-128, которые оба являются LFSR-генераторами, и оба были взломаны с помощью алгебраических атак.

    Из-за недостатка хороших аппаратных ГПСЧ производители вынуждены применять имеющиеся под рукой гораздо более медленные, но широко известные блочные шифры (DES, AES) и хеш-функции (SHA-1) в поточных режимах.
    Литература
    Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming — 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6 (рус.) ISBN 0-201-89684-2 (англ.).
    http://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел

    вот насчет Организация защиты данных в сетях что конкретно сюда писать не понял(( кстати можно дополнять информацией и литературой)
     
  6. SNS-amigo
    Оффлайн

    SNS-amigo SNS System Watch Freelance reporter

    Сообщения:
    5.220
    Симпатии:
    8.894
    Как, я не знаю о требованиях, предъявляемых в вашем УЗ. Сам-то я уже давно отучился. :)

    Но простой копипаст вряд ли будет приветствоваться преподами. Нужно понимать, о чём это и писать своими словами. Раз вы этому учитесь, то вам и флаг в руки.

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

    "Организация защиты данных в сетях" или "Организация защиты информации в сетях ЭВМ", это примерно одно и тоже в рамках учебного материала, т.к. это скорее всего вопрос общего плана. Раз написано "в сетях", то скорее всего имеется ввиду не сам Интернет, а локальные и виртуальные частные сети. Не указано точно, оно и хорошо — свобода творчества.

    Попробуйте объединить данные из этих двух статей:

    http://www.osp.ru/os/1995/03/178615/
    http://elmech.mpei.ac.ru/books/edu/NIT/nit-part-1.html

    Одна старее, другая новее. Если добавить малость эволюции, то от этого статья только выиграет. Да и лучше и быстрее запомните текст. Может каким-то образом сумеете интегрировать в материал сведения из справки нашего продукта. :victory: Но больше того, что сказано на сайте или в справке, я помочь не смогу (работаю каждый день). А небольшое вкрапление в рамках абзаца будет только плюсом.
     
    Последнее редактирование: 6 ноя 2011
    2 пользователям это понравилось.
  7. aidoqa
    Оффлайн

    aidoqa Активный пользователь

    Сообщения:
    1.115
    Симпатии:
    313
    это вы в точку))) мне просто отчет надо сделать) а дальше я сам буду разбираться)


    Спасибо большое) ваш сценарий супер!!!!выручили)
     
    Последнее редактирование: 6 ноя 2011
    1 человеку нравится это.

Поделиться этой страницей