Использование библиотеки математических функций для больших чисел применительно к криптографии
FLINT/C
Лабораторная работа № 1
Использование библиотеки математических функций для больших чисел применительно к криптографии
“FLINT\C”.
Цель работы
- Ознакомиться с основами использования библиотеки “FLINT\C”.
- Научиться создавать Win32-консольные приложения с основами использования библиотеки “FLINT\C”.
Изучить функции для выполнения основных операции с большими числами (ввода-вывода, арифметические и поразрядные операции)
В ходе выполнения данной лабораторной работы необходимо создать консольное Win32-приложение, которое реализует некоторые математические вычисления
Методические указания к работе
FLINT\C(Functions for Large Integers in Number Theory and Criptography) является свободно распространяемой библиотекой функций и классов для реализации различных математических операций и алгоритмов с использованием больших чисел. Она включает в себя следующие группы функций:
· основные арифметические операции с большими числами
· функции модульной арифметики
· функции битовых операций
· теоретико-числовые функции
· функции генерации больших псевдослучайных чисел
И другие.
Подключение библиотеки
Для подключения “FLINT\C” в программы С\С++ достаточно подключить к проекту модуль flint.h - #include ”z:\xxxx\flint.h ”,а исходный код этого модуля flint.с необходимо включить в состав разрабатываемого проекта.
Создание проекта в Borland C++
· Создать новый проект – Project->Open Project (например Lab1.prj)
· Влючить в состав проекта библиотеку flinta.lib
Project->Open Project->Add item…
· Влючить в состав проекта файл flinta.h
Project->Open Project->Add item…
· Включить в состав проекта основной файл программы (например Lab1.cpp ) Project->Open Project->Add item
· Проверить состав проекта Windows-> Project
· Выполнить компиляцию проекта Compile->Make
· Выполнить программу Compile->Run
1. Представление больших чисел в “FLINT\C”
В основе “FLINT\C” лежит обработка многоразрядных натуральных чисел, длина которых намного превосходит допустимый размер стандартных типов данных.Эти числа представлены в виде вектора стандартного типа данных unsigned short int.Эти числа могут представляться числом длиной до 4094 бита(1024 десятичных разряда) и описываются специальным типом данных
CLINT.
2. Семантика интерфейса
Представление FLINT/C-функций начинается с заголовка, который содержит синтаксическое и семантическое описание интерфейса функции. Такие заголовки функций обычно выглядят следующим образом
Функция Краткое описание функции
Синтаксис: int f_l (CLINT a_l, CLINT b_l, CLINT c_l);
Вход: a_l, b_l (операнды)
Выход:c_l (результат)
Возврат:0, если все в порядке
предупреждение или сообщение об ошибке в противном случае
Здесь нужно различать между собой значения выхода и возврата.
В то время как выход относится к значениям, которые функция хранит в переданных аргументах, под возвратом подразумеваются значения, которые функция возвращает посредством команды return.
За исключением нескольких случаев,значение возврата содержит сведения о состоянии или сообщения об ошибке.
Другие параметры, не связанные с выходом, функция не изменяет.
Обращения вида f_l(a_j, b_j, a_j), где a_j и b_j - аргументы и в конце вычислении прежнее значение a+j затирается результатом, вполне допустимы, так как результат записывается в возвращаемую nepеменную только после завершения операции.
Если обнаруживается переполнение или потеря значимости, арж метическая функция возвращает соответствующий код ошибки
Код ошибки Интерпретация
E_CLINT_BOR Недопустимое основание в str2clint_l()
E_CL1NT_DBZ Деление на нуль
E_CLINT_MAL Ошибка при распределении ресурсов памяти
E_CLINT_MOD Четные модули в умножении по Монтгомери
E_CLINT_NOR Регистр недоступен
E_CLINT_NPT Пустой указатель в качестве аргумента
E_CLINT_OFL Переполнение
Дополнительные операции с CLlNT-объектами
Копирование CLINT
Синтаксис:void cpy_l (CLINT des, CLINT src);
Вход: src (присваиваемое значение)
Выход: des (объект назначения)
Перестановка значений двух CLlNT-объектов
Синтаксис: void fswap_l (CLINT a, CLINT b);
Вход: a, b (переставляемые значения)
Выход: a, b
Основные арифметические операции с большими числами типа CLINT
Функции сложения
Сложение
Синтаксис: int add_l (CLINT a, CLINT b, CLINT с);
Вход: a, b (слагаемые)
Выход: с (сумма)
Возврат: E_CLINT_OK, если все в порядке
E_CLINT_OFL в случае переполнения
Инкремент (увеличение CLINT-обьекта на 1)
Синтаксис: int inc_l (CLINT a);
Вход: а (слагаемое)
Выход: a (сумма)
Возврат: E_CLINT_OK, если все в порядке
E_CLINT_OFL в случае переполнения
Функции вычитания
Вычитание
Синтаксис int sub_l (CLINT a, CLINT b, CLINT с);
Вход: a (уменьшаемое),b (вычитаемое)
Выход: с (разность)
Возврат: E_CLINT_OK, если все в порядке
E_CLINT_UFL в случае потери значащих разрядов
Декремент (уменьшение CLINT-обьекта на 1)
Синтаксис: int dec_l (CLINT a);
Вход: а (уменьшаемое )
Выход: a (разность сумма)
Возврат: E_CLINT_OK, если все в порядке
E_CLINT_UFL в случае потри значащих разрядов
Функции умножения
Умножение
Синтаксис: int mul_l (CLINT a, CUNT b, CLINT c);
Вход: a, b (сомножители)
Выход: c(произведение)
Возврат: E_CLINT_OK, если все в порядке
E_CLlNT_OFL в случае переполнения
Возведение в квадрат
Синтаксис: inl sqr_l (CLINT a, CLINT c);
Вход: a (операнд)
Выход: c (квадрат)
Возврат: E_CLINT_OK, если все в порядке
E_CLINT_OFL в случае переполнения
Функции деления
Деление
Синтаксис: inl div_l (CLINT a, CLINT b, CLINT q, CLINT tem);
Вход: a (делимое), b (делитель)
Выход: q (частное), tem (остаток)
Возврат: E_CLINT_OK, если все в порядке
E_CLINT_DBZ в случае деления на 0
Функции модульного деления
Модульное деление( вычет по модулю )
Синтаксис: int mod_l (CLINT a, CLINT b, CLINT r);
Вход: a (делимое), b (делитель или модуль)
Выход: r (остаток)
Возврат: E_CLINT_OK, если все в порядке E_CLINT_D8Z в случае деления на 0
Модульное деление на степень двойки (вычет по модулю 2k)
Синтаксис: int mod2_l (CLINT a, ULONG b, CLINT r);
Вход: a (делимое),b (показатель степени делителя или модуля)
Выход: r (остаток)
Модульное деление переменной типа CLINT на переменную типа USHORT( вычет по модулю )
Синтаксис: USHORT umod_l (CLINT a, USHORT b);
Вход: a (делимое), b (делитель или модуль)
Возврат: неотрицательный остаток, если все в порядке 0xFFFF в случае деления на 0
Пример использования основных арифметических операций
#pragma hdrstop
#include <FLINT.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define ClintToStr xclint2str_l // Переопределение функции xclint2str_l
int main(int argc, char* argv[])
{
CLINT a,b,c; // Обьявление объектов CLINT
// Инициализаация объектов CLINT строкой 16-х цифр
char *sa =new char;sa="104576356756674567845764567456757645778467837638";
str2clint_l (a,sa,10);//Инициализация строкой
char *sb =new char;sb="1814595567567567567567635673567567567567876867897";
str2clint_l (b,sb,10);//Инициализация строкой
printf("a=%s\n",ClintToStr(a,10,1));
printf("b=%s\n",ClintToStr(b,10,1));
//Сложение
int Err= add_l (a,b,c);
printf("Err= %d c=a+b= %s\n",Err,ClintToStr(c,10,1));
// Инкремент
Err= inc_l ( a);
printf("Err= %d a=a+1= %s\n",Err,ClintToStr(a,10,1));
// Смешанное сложение переменных типа CLINT и USHORT
USHORT US=1956; printf("US= %d\n",US);
Err= uadd_l ( a,US, c);
printf("Err= %d a+US= %s\n",Err,ClintToStr(c,10,1));
//Вычитание
Err= sub_l (b,a,c);
printf("Err= %d c=b-a= %s\n",Err,ClintToStr(c,10,1));
// Денкремент
Err= dec_l ( c);
printf("Err= %d c=c-1= %s\n",Err,ClintToStr(c,10,1));
//Вычитание числа типа USHORT из числа типа CLINT
Err= usub_l ( c, US, a);
printf("Err= %d a=c-US= %s\n",Err,ClintToStr(a,10,1));
//Yмножение
Err= mul_l ( a, b, c);
printf("Err= %d c=a*b= %s\n",Err,ClintToStr(c,10,1));
// Возведение в квадрат числа a
Err= sqr_l ( a, c);
printf("Err= %d b=sql(a)= %s\n",Err,ClintToStr(b,10,1));
// Умножение CLINT- объекта на число типа USHORT
Err=umul_l (a, US, c);
printf("Err= %d c=a*US= %s\n",Err,ClintToStr(c,10,1));
//Деление
CLINT q, tem;
Err= div_l (b, a, q, tem );
printf("Err= %d q=b/a= %s\n",Err,ClintToStr(q,10,1));
printf(" tem= %s\n",ClintToStr(tem,10,1));
// Модульное деление ( вычет по модулю )
mod_l (b, a, tem);
printf(" Err= %d tem=b mod a= %s\n",Err,ClintToStr(tem,10,1));
// Модульное деление на степень двойки (вычет по модулю 2k)
Err= mod2_l ( a, 5, q);
printf(" Err= %d q=a mod (2*2*2*2*2) = %s\n",Err,ClintToStr(q,10,1));
//Модульное деление переменной типа CLINT на переменную типа USHORT
//( вычет по модулю )
US=pow(2,5) ;
USHORT F= umod_l (a, US);
printf(" F=a mod (2*2*2*2*2) = %d\n",F);
getch();
return 0; }
Рисунок Основные арифметические операции
Задание
| № п.п | Инициализация | Преобразование переменных , дополнительные операции | Арифметические операции | Поразрядные операции |
| Строкой 16-х цифр | Перестановка значений двух CLlNT-объектов | Сложение,деление ,модульное деление на степень двойки | Сдвиг влево на один бит | |
| Числом типа ULONG | Копирование CLINT | Смешанное сложение, возведение в квадрат, умножение | Сдвиг вправо на один бит | |
| Вектором байт | Перестановка значений двух CLlNT-объектов | Инкремент, модульное деление на степень двойки, вычитание числа типа USHORT из числа типа CLINT | Поразрядное “И” | |
| Строкой 2-х цифр | Преобр. CLINT-объекта в строку символов | Вычитание,деление, модульное деление переменной типа CLINT на переменную типа USHORT | Поразрядное “ИЛИ” | |
| Строкой 8-х цифр | Перестановка значений двух CLlNT-объектов | Смешанное сложение переменных типа CLINT и USHORT, умножение, декремент | Поразрядное “исключающее ИЛИ” | |
| Строкой 10-х цифр | Преобр. CLINT-объекта в строку символов | Вычитание числа типа USHORT из числа типа CLINT, деление переменной типа CLINT на переменную типа USHORT, вычитание | Проверка и задание значения бита | |
| Строкой 2-х цифр | Перестановка значений двух CLlNT-объектов | Сложение, умножение, модульное деление | Проверка и обнуление значения бита | |
| Числом типа ULONG | Копирование CLINT | Инкремент,деление, возведение в квадрат | Сдвиг влево на один бит | |
| Строкой 8-х цифр | Копирование CLINT | Умножение CLINT- объекта на число типа USHORT, возведение в квадрат, модульное деление переменной типа CLINT на переменную типа USHORT | Сдвиг вправо на один бит | |
| Строкой 16-х цифр | Перестановка значений двух CLlNT-объектов | Сложение, деление, модульное деление,деление переменной типа CLINT на переменную типа USHORT | Поразрядное “И” | |
| Вектором байт | Копирование CLINT | возведение в квадрат, модульное деление на степень двойки | Поразрядное “ИЛИ” | |
| Строкой 2-х цифр | Число значащих двоичных разрядов CLINT-объекта | Умножение, декремент,модульное деление | Проверка двоичного разряда | |
| Строкой 10-х цифр | Копирование CLINT | Смешанное сложение переменных типа CLINT и USHORT, умножение CLINT- объекта на число типа USHORT, модульное деление на степень двойки | Поразрядное “И” | |
| Строкой 16-х цифр | Преобр. CLINT-объекта в строку символов | Вычитание, умножение, модульное деление | Проверка и задание значения бита | |
| Числом типа ULONG | Перестановка значений двух CLlNT-объектов | Инкремент, деление, декремент | Поразрядное “ИЛИ” | |
| Строкой 8-х цифр | Копирование CLINT | Сложение, умножение, модульное деление переменной типа CLINT на переменную типа USHORT | Сдвиг влево на один бит | |
| Строкой 2-х цифр | Число значащих двоичных разрядов CLINT-объекта | Вычитание числа типа USHORT из числа типа CLINT, декремент, умножение | Сдвиг вправо на один бит | |
| Строкой 10-х цифр | Перестановка значений двух CLlNT-объектов | Сложение, , модульное деление,смешанное сложение переменных типа CLINT и USHORT | Поразрядное “исключающее ИЛИ” | |
| Числом типа ULONG | Копирование CLINT | Вычитание, декремент,умножение | Проверка и задание значения бита | |
| Вектором байт | Преобр. CLINT-объекта в байтовый вектор | Сложение, возведение в квадрат,модульное деление переменной типа CLINT на переменную типа USHORT | Проверка и обнуление значения бита |
-
- Отчет должен содержать содержать:
1. Hаименование и номер лабораторной работы;
2. Условие задачи;
3. Распечатка листинга программы;
4. Распечатка результатов выполнения задачи;
5. Выводы по результатам выполнения задач, анализ возможностей библиотеки “FLINT\C” .
FLINT/C
Лабораторная работа № 1
Использование библиотеки математических функций для больших чисел применительно к криптографии
“FLINT\C”.
Цель работы
- Ознакомиться с основами использования библиотеки “FLINT\C”.
- Научиться создавать Win32-консольные приложения с основами использования библиотеки “FLINT\C”.
Изучить функции для выполнения основных операции с большими числами (ввода-вывода, арифметические и поразрядные операции)
В ходе выполнения данной лабораторной работы необходимо создать консольное Win32-приложение, которое реализует некоторые математические вычисления
Методические указания к работе
FLINT\C(Functions for Large Integers in Number Theory and Criptography) является свободно распространяемой библиотекой функций и классов для реализации различных математических операций и алгоритмов с использованием больших чисел. Она включает в себя следующие группы функций:
· основные арифметические операции с большими числами
· функции модульной арифметики
· функции битовых операций
· теоретико-числовые функции
· функции генерации больших псевдослучайных чисел
И другие.
Подключение библиотеки
Для подключения “FLINT\C” в программы С\С++ достаточно подключить к проекту модуль flint.h - #include ”z:\xxxx\flint.h ”,а исходный код этого модуля flint.с необходимо включить в состав разрабатываемого проекта.
Создание проекта в Borland C++
· Создать новый проект – Project->Open Project (например Lab1.prj)
· Влючить в состав проекта библиотеку flinta.lib
Project->Open Project->Add item…
· Влючить в состав проекта файл flinta.h
Project->Open Project->Add item…
· Включить в состав проекта основной файл программы (например Lab1.cpp ) Project->Open Project->Add item
· Проверить состав проекта Windows-> Project
· Выполнить компиляцию проекта Compile->Make
· Выполнить программу Compile->Run
1. Представление больших чисел в “FLINT\C”
В основе “FLINT\C” лежит обработка многоразрядных натуральных чисел, длина которых намного превосходит допустимый размер стандартных типов данных.Эти числа представлены в виде вектора стандартного типа данных unsigned short int.Эти числа могут представляться числом длиной до 4094 бита(1024 десятичных разряда) и описываются специальным типом данных
CLINT.
2. Семантика интерфейса
Представление FLINT/C-функций начинается с заголовка, который содержит синтаксическое и семантическое описание интерфейса функции. Такие заголовки функций обычно выглядят следующим образом
Функция Краткое описание функции
Синтаксис: int f_l (CLINT a_l, CLINT b_l, CLINT c_l);
Вход: a_l, b_l (операнды)
Выход:c_l (результат)
Возврат:0, если все в порядке
предупреждение или сообщение об ошибке в противном случае
Здесь нужно различать между собой значения выхода и возврата.
В то время как выход относится к значениям, которые функция хранит в переданных аргументах, под возвратом подразумеваются значения, которые функция возвращает посредством команды return.
За исключением нескольких случаев,значение возврата содержит сведения о состоянии или сообщения об ошибке.
Другие параметры, не связанные с выходом, функция не изменяет.
Обращения вида f_l(a_j, b_j, a_j), где a_j и b_j - аргументы и в конце вычислении прежнее значение a+j затирается результатом, вполне допустимы, так как результат записывается в возвращаемую nepеменную только после завершения операции.