Использование библиотеки математических функций для больших чисел применительно к криптографии

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

Модульное деление на степень двойки (вычет по модулю 2^k)

Синтаксис: 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));

 

// Модульное деление на степень двойки (вычет по модулю 2^k)

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еменную только после завершения операции.