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

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

Наши рекомендации